Create a k-ary tree from a list of coordinates and list of edges connecting them.

Question

I have a list of Nodes/Vertices, and a list of lines/edges connecting these nodes.The lists are not sorted or ordered in any way, but contain all the edges and nodes for a particular data set.

The edges are line segments defined by Cartesian coordinates, (x1,y1) and (x2,y2), and each node position is also represented by coordinates in the form (x,y). The image attached depicts a typical test case, clearly showing two trees, with roots R1 and R2, each Node, including leaf nodes (labelled Lx, and highlighted orange text and blue circles) is shown with corresponding coordinates.

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
}

And each edge is represented as:

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

From the image attached, it is clear that Edge N1-N2 will be represented as either p1= (0,0), p2=(20,20) or p1 =(20,20), p2 = (0,0). the order is random.

Assumption 1: Nodes R1 and R2 can be clearly recognized as root nodes, because of the type of node on them. (Concentric circles with Red outer circle). Assumption 2: A list of all edges directly connected to a node are also available, e.g, node N8 will have segments :N8-L7,N8-R2,N8-N9, N8-N7.

My question is how do I write a function in C# that has two inputs,a List of edges and a List of nodes, and returns a root node, or root nodes of trees with reference to the child nodes, which would also be identical/true to the what is depicted in the drawing attached.

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!
}

I have been able to list each nodes edges, but can't figure out a way to construct the tree. I have read about Kruskal's Algorithm, but I'm not sure if i can adapt it to this problem. I'm not sure if it will preserve the order shown in the diagram.

All code is in C#, but any C style language solution will do.

NB:The answers I have seen on this website assume that the ordering of the tree nodes in terms of parent nodes and children is already known. I can tell that two nodes are connected by an edge, but cannot determine which node is the parent and which is the child node.

Thank you,

Greg M

Answer 1

You said that there are two assumptions:

1. Nodes R1 and R2 can be clearly recognized as root nodes, because of the type of node on them. (Concentric circles with Red outer circle).
2. A list of all edges directly connected to a node are also available, e.g, node N8 will have segments N8-L7, N8-R2, N8-N9, N8-N7.

I'm going to assume that there are also segments L7-N8, R2-N8, N9-N8, N7-N8. If not, you can build them easily enough from the existing segments that you mentioned.

You also said, in response to my questions, that roots have no parents, and each node has only one parent. That makes this a lot easier.

First, create a dictionary that has node names as keys, and the value is the list of nodes to which it connects. This would be a Dictionary<string, List<string>>. In the example above, you'd have:

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

In the above list, only N8 is fully populated. Your dictionary would contain all the connections for all the nodes.

To build this:

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);
}

Now, we'll build a new Dictionary<string, List<string>> that is initially empty. This will be the final tree, that has only the children for each node.

Because you know that root nodes have no parents, and that a node has no more than a single parent, you can start at the roots and start making connections. Scan the dictionary and for each root node, add it to a queue, and create an entry in the finalTree with an empty child list:

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
    }
}

Now, start processing the queue. For each node name you pull from the queue:

1. Create an entry in the finalTree for that node.
2. Get the list of connections for that node from the segmentDict.
3. For each of the node connections, if there is no entry for that node in the finalTree, add the node to the queue, and add it to the list of connections for this node in finalTree.

Repeat that until the queue is empty.

The code looks something like this:

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
    }
}

What I've done here is followed the tree from the roots to the leaves, so the first time I encounter a node, I know that it's a parent-child link rather than a child-parent link. So all child-parent links get removed.

You can get your tree, then, by going through finalTree and doing a depth-first traversal on each root node:

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]);
    }
}

You'll want to pretty up the output, of course, but that shows how to traverse the trees from the roots.