Создайте k-арное дерево из списка координат и списка ребер, соединяющих их.

Question

У меня есть список узлов / вершин и список линий / ребер, соединяющих эти узлы. Списки не сортируются и не упорядочиваются каким-либо образом, но содержат все ребра и узлы для определенного набора данных.

Ребра представляют собой отрезки, определяемые декартовыми координатами (x1,y1) и (x2,y2), и каждая позиция узла также представляется координатами в форме (x,y). Прикрепленное изображение изображает типичный тестовый пример, на котором четко показаны два дерева с корнями R1 и R2, каждый узел, включая листовые узлы (обозначенные Lx, выделенный оранжевый текст и синие кружки), показан с соответствующими координатами.

class Node
{
  Point coordinates;   // x,y coordinates of node <int,int>
  Node parentNode;     // parent node of current node. ( may not be necessary as parentID may suffice to keep reference to parent node)
  List<Node> children; // List of all child nodes of this node
  List<Edge> edges;    // list of all edges connected to this node
  string Data;         // relevant data of each node
  long   nodeID;       // current nodes ID
  long   parentID;     // ID of current node's parent node
}

И каждый край представлен как:

class Edge
{
    Point p1;     // first end coordinates of line segment
    Point p2;     // coordinates of the other end of the segment
}

Из приложенного изображения ясно, что Edge N1-N2 будет представлен как p1= (0,0), p2=(20,20) или p1 =(20,20), p2 = (0,0). порядок случайный.

Предположение 1: узлы R1 и R2 могут быть четко распознаны как корневые узлы из-за типа узла на них. (Концентрические круги с красным внешним кругом). Предположение 2: Список всех ребер, непосредственно связанных с узлом, также доступен, например, узел N8 будет иметь сегменты:N8-L7,N8-R2,N8-N9, N8-N7.

Мой вопрос заключается в том, как мне написать функцию в C#, которая имеет два входа: список ребер и список узлов, и возвращает корневой узел или корневые узлы деревьев со ссылкой на дочерние узлы, которые также будут идентичны / Верно тому, что изображено на прилагаемом чертеже.

List<Node> getRootNodes(List<Node> nodes, List<Edge> edges)
{
     // implementation here
     List<Node> roots = new List<Node>();
     //more logic
     //
     //
     return roots;  //returned list may have more than one root node!
}

Я был в состоянии перечислить края каждого узла, но не могу найти способ построить дерево. Я читал об алгоритме Крускала, но не уверен, смогу ли я адаптировать его к этой проблеме. Я не уверен, сохранит ли он порядок, показанный на диаграмме.

Весь код написан на C#, но подойдет любое решение на языке C.

NB. Ответы, которые я видел на этом сайте, предполагают, что упорядочение узлов дерева с точки зрения родительских и дочерних узлов уже известно. Я могу сказать, что два узла соединены ребром, но не могут определить, какой узел является родительским, а какой - дочерним.

Спасибо,

Грег М

Answer 1

Вы сказали, что есть два предположения:

1. Узлы R1 и R2 могут быть четко распознаны как корневые узлы из-за типа узла на них. (Концентрические круги с красным внешним кругом).
2. Также доступен список всех ребер, напрямую соединенных с узлом, например, узел N8 будет иметь сегменты N8-L7, N8-R2, N8-N9, N8-N7,

Я собираюсь предположить, что есть также сегменты L7-N8, R2-N8, N9-N8, N7-N8, Если нет, вы можете построить их достаточно легко из существующих сегментов, которые вы упомянули.

В ответ на мои вопросы вы также сказали, что у корней нет родителей, и у каждого узла есть только один родитель. Это делает это намного проще.

Сначала создайте словарь с именами узлов в качестве ключей, а значением является список узлов, к которым он подключается. Это было бы Dictionary<string, List<string>>, В приведенном выше примере вы получите:

key    value
N8     L7, R2, N9, N7
L7     N8
R2     N8
N9     N8
N7     N8

В приведенном выше списке только N8 полностью заполнен. Ваш словарь будет содержать все соединения для всех узлов.

Чтобы построить это:

var segmentDict = new Dictionary<string, List<string>>();
foreach (var segment in SegmentList)
{
    List<string> nodeConnections;
    if (!segmentDict.TryGetValue(segment.From, out nodeConnections))
    {
        // This node is not in dictionary. Create it.
        nodeConnections = new List<string>();
        segmentDict.Add(segment.From, nodeConnections);
    }
    nodeConnections.Add(segment.To);
}

Теперь мы будем строить новый Dictionary<string, List<string>> это изначально пусто. Это будет последнее дерево, в котором есть только дочерние элементы для каждого узла.

Поскольку вы знаете, что корневые узлы не имеют родителей, и что узел имеет не более одного родителя, вы можете начать с корней и начать устанавливать соединения. Просканируйте словарь и для каждого корневого узла добавьте его в очередь и создайте запись в finalTree с пустым списком детей:

var finalTree = new Dictionary<string, List<string>>();
var nodeQueue = new Queue<string>();

foreach (var nodeName in segmentDict.Keys)
{
    if (nodeName.StartsWith("R")) // if it's a root node
    {
        finalTree.Add(nodeName, new List<string>()); // add tree node
        nodeQueue.Enqueue(nodeName); // and add node to queue
    }
}

Теперь начните обработку очереди. Для каждого имени узла, которое вы извлекаете из очереди:

1. Создать запись в finalTree для этого узла.
2. Получить список соединений для этого узла из segmentDict,
3. Для каждого из соединений узла, если нет записи для этого узла в finalTreeдобавьте узел в очередь и добавьте его в список соединений для этого узла в finalTree,

Повторяйте это, пока очередь не станет пустой.

Код выглядит примерно так:

while (nodeQueue.Count > 0)
{
    var fromNode = nodeQueue.Dequeue();
    var nodeChildren = finalTree[fromNode];
    foreach (var toNode in segmentDict[fromNode])
    {
        if (finalTree.ContainsKey(toNode))
        {
            // This node has already been seen as a child node.
            // So this connection is from child to parent. Ignore it.
            break;
        }
        nodeChildren.Add(toNode);  // update children for this node
        finalTree.Add(toNode, new List<string>()); // create tree entry for child node
        nodeQueue.Enqueue(toNode); // add child to queue
    }
}

Здесь я следовал по дереву от корней до листьев, поэтому, когда я впервые сталкиваюсь с узлом, я знаю, что это ссылка "родитель-потомок", а не "потомок-родитель". Таким образом, все дочерние родительские ссылки удаляются.

Вы можете получить свое дерево, пройдя через finalTree и выполняем обход в глубину на каждом корневом узле:

foreach (var kvp in finalTree)
{
    if (kvp.Key.StartsWith("R"))
    {
        PrintTree(kvp.Key, kvp.Value);
    }
}

void PrintTree(string nodeName, List<string> children)
{
    Console.WriteLine("node {1} has children {2}.", nodeName, string.Join(",", children);
    foreach (var child in children)
    {
        PrintTree(child, finalTree[child]);
    }
}

Вы, конечно, захотите подправить вывод, но это показывает, как пройтись по деревьям от корней.