Wrapping my head around N parent->child associations

Question

I'll try to explain this the best I can. I'm having quite a bit of difficulty trying to figure out this logic.

Basically, I have a collection that includes thousands of objects which are each made up of a Parent and a Child property.

So, roughly, this:

public class MyObject{
     public string Parent { get; set; }
     public string Child { get; set; }
}

What I'm trying to figure out is how to build this out into a plain TreeView control. I need to build the relationships but I can't figure out how to because they can be mixed. I can probably explain this better with what the tree should look like:

So if I have the following items inside of my collection:

0. Parent: "A", Child: "B"
1. Parent: "B", Child: "C"
2. Parent: "B", Child: "D"

I would want my tree to look this like:

-A
--B
---C
-A
--B
---D
-B
--C
-B
--D

How can I do this in C#? I would need it to support up to N relationships as we have some branches I would expect to reach about 50 nodes deep.

Answer 1

UPDATE

This problem actually turned out to be considerably more complex than I originally realized, given the requirement of repeating the entire tree for each path. I've simply deleted the old code as I don't want to add any further confusion.

I do want to keep it on record that using a recursive data structure makes this easier:

public class MyRecursiveObject
{
    public MyRecursiveObject Parent { get; set; }
    public string Name { get; set; }
    public List<MyRecursiveObject> Children { get; set; }
}

You'll see very clearly why this is easier after reading the implementation code below:

private void PopulateTree(IEnumerable<MyObject> items)
{
    var groupedItems =
        from i in items
        group i by i.Parent into g
        select new { Name = g.Key, Children = g.Select(c => c.Child) };
    var lookup = groupedItems.ToDictionary(i => i.Name, i => i.Children);
    foreach (string parent in lookup.Keys)
    {
        if (lookup.ContainsKey(parent))
            AddToTree(lookup, Enumerable.Empty<string>(), parent);
    }
}

private void AddToTree(Dictionary<string, IEnumerable<string>> lookup,
    IEnumerable<string> path, string name)
{
    IEnumerable<string> children;
    if (lookup.TryGetValue(name, out children))
    {
        IEnumerable<string> newPath = path.Concat(new string[] { name });
        foreach (string child in children)
            AddToTree(lookup, newPath, child);
    }
    else
    {
        TreeNode parentNode = null;
        foreach (string item in path)
            parentNode = AddTreeNode(parentNode, item);
        AddTreeNode(parentNode, name);
    }
}

private TreeNode AddTreeNode(TreeNode parent, string name)
{
    TreeNode node = new TreeNode(name);
    if (parent != null)
        parent.Nodes.Add(node);
    else
        treeView1.Nodes.Add(node);
    return node;
}

First of all, I realized that the dictionary will contain keys for intermediate nodes as well as just the root nodes, so we don't need two recursive calls in the recursive AddToTree method in order to get the "B" nodes as roots; the initial walk in the PopulateTree method already does it.

What we do need to guard against is adding leaf nodes in the initial walk; using the data structure in question, these are detectable by checking whether or not there is a key in the parent dictionary. With a recursive data structure, this would be way easier: Just check for Parent == null. But, a recursive structure is not what we have, so the code above is what we have to use.

The AddTreeNode is mostly a utility method, so we don't have to keep repeating this null-checking logic later.

The real ugliness is in the second, recursive AddToTree method. Because we are trying to create a unique copy of every single subtree, we can't simply add a tree node and then recurse with that node as the parent. "A" only has one child here, "B", but "B" has two children, "C" and "D". There needs to be two copies of "A", but there's no way to know about that when "A" is originally passed to the AddToTree method.

So what we actually have to do is not create any nodes until the final stage, and store a temporary path, for which I've chosen IEnumerable<string> because it's immutable and therefore impossible to mess up. When there are more children to add, this method simply adds to the path and recurses; when there are no more children, it walks the entire saved path and adds a node for each.

This is extremely inefficient because we are now creating a new enumerable on every invocation of AddToTree. For large numbers of nodes, it is likely to chew up a lot of memory. This works, but it would be a lot more efficient with a recursive data structure. Using the example structure at the top, you wouldn't have to save the path at all or create the dictionary; when no children are left, simply walk up the path in a while loop using the Parent reference.

Anyway, I guess that's academic because this isn't a recursive object, but I thought it was worth pointing out anyway as something to keep in mind for future designs. The code above will produce exactly the results you want, I've gone ahead and tested it on a real TreeView.

---

UPDATE 2 - So it turns out that the version above is pretty brutal with respect to memory/stack, most likely a result of creating all those IEnumerable<string> instances. Although it's not great design, we can remove that particular issue by changing to a mutable List<string>. The following snippet shows the differences:

private void PopulateTree(IEnumerable<MyObject> items)
{
    // Snip lookup-generation code - same as before ...

    List<string> path = new List<string>();
    foreach (string parent in lookup.Keys)
    {
        if (lookup.ContainsKey(parent))
            AddToTree(lookup, path, parent);
    }
}

private void AddToTree(Dictionary<string, IEnumerable<string>> lookup,
    IEnumerable<string> path, string name)
{
    IEnumerable<string> children;
    if (lookup.TryGetValue(name, out children))
    {
        path.Add(name);
        foreach (string child in children)
            AddToTree(lookup, newPath, child);
        path.Remove(name);
    }
    // Snip "else" block - again, this part is the same as before ...
}

Answer 2

like rubens, I tried both, but a little better I think A Generic Tree Collection

this tree collection got some nice functionality build-in to move around the tree, go read the whole article

sample with the link above

Static Class Module1
{

    public static void Main()
    {
        Common.ITree<myObj> myTree = default(Common.ITree<myObj>);
        myObj a = new myObj("a");
        myObj b = new myObj("b");
        myObj c = new myObj("c");
        myObj d = new myObj("d");

        myTree = Common.NodeTree<myObj>.NewTree;
        myTree.InsertChild(a).InsertChild(b).InsertChild(c).Parent.Parent.InsertNext(a).InsertChild(b).InsertChild(d).Parent.Parent.InsertNext(b).InsertChild(c).Parent.InsertNext(b).InsertChild(d);

        Console.WriteLine(myTree.ToStringRecursive);

        Console.ReadKey();
    }
}

Class myObj
{
    public string text;

    public myObj(string value)
    {
        text = value;
    }

    public override string ToString()
    {
        return text;
    }
}

would be exactly what you just showed

-A
--B
---C
-A
--B
---D
-B
--C
-B
--D

Answer 3

If I understand this correctly, what you're trying to do is take one tree and transform it into another. The transformation essentially takes each non-leaf-node in the input tree and creates a node for it (and its descendants) in the output tree.

First off, you'll be happier if you design a data structure for your nodes that is genuinely recursive:

public class Node
{
   public Node Parent { get; private set; }
   public IEnumerable<Node> Children { get; private set; }
   public bool HasChildren { get { return Children.Count() > 0; } }

   public Node()
   {
      Children = new List<Node>();
   }
}

Your MyObject class represents parent/child relationships between string values. As long as you're able to implement a FindChildren() method that returns the child values for a given parent value, using this class to rationalize the parent/child relationships is straightforward:

public string Value { get; set; }
public static Node Create(string parentKey)
{
   Node n = new Node();
   n.Value = parentKey;
   foreach (string childKey in FindChildren(parentKey))
   {
      Node child = n.Children.Add(Node.Create(childKey));
      child.Parent = n;
   } 
   return n;
}

It's simple to implement a property that returns a node's descendants:

public IEnumerable<Node> Descendants
{
   get
   {
      foreach (Node child in Children)
      {
         yield return child;
         foreach (Node descendant in child.Descendants)
         {
            yield return descendant;
         }
      }
   }
}

To add a Node to a TreeView, you need two methods. (Note that these aren't methods of the Node class!) I've made them overloads, but an argument can be made for giving them different names:

public void AddNode(Node n, TreeView tv)
{
   TreeNode tn = tv.Nodes.Add(n.Value);
   tn.Tag = n;
   foreach (Node child in n.Children)
   {
      AddNode(child, tn);
   }
}

public void AddNode(Node n, TreeNode parent)
{
   TreeNode tn = parent.Nodes.Add(n.Value);
   parent.Tag = n;
   foreach (Node child in n.Children)
   {
      AddNode(child, tn);
   }
}

I'm setting the Tag on each TreeNode so that you can find your way back to the original Node.

So to initialize your TreeView from a list of top-level parent keys, you need a method like this:

public void PopulateTreeView(IEnumerable<string> parents, TreeView t)
{
   foreach (string parentKey in parents)
   {
      Node n = Node.Create(parentKey);
      AddNode(n, t);
      foreach (Node descendant in n.Descendants)
      {
         if (n.HasChildren)
         {
            AddNode(descendant, t);
         }
      }
   }
}

Edit:

I didn't quite understand how your MyObject class was working; I think I do now, and I've edited this accordingly.