Finding a class within list

Question

I have a class (Node) which has a property of SubNodes which is a List of the Node class

I have a list of Nodes (of which each Node may or may not have a list of SubNodes within itself) I need to be able to find a Node within the Node list/subNodes.

I have tried to do Find on the list but that will only search the Node classes within the list not the SubNodes list. Looked at the C5 library and a few binary trees but can't find anything suitable. any advice?

The class

 public class Node
 {
        public Guid Id { get; set; }
        public DateTime Created { get; set; }
        public List<Node> Nodes { get;set;}
 }

The function (result is the end result)

private void GetRecersive(List<Node> list, ref List<Node> result)
        {
            foreach (Node item in list)
            {

                if (item.ParentId.Equals(Guid.Empty))
                {
                    result.Add(item);
                }
                else
                {
                    result.ForEach(x => x.FindNodes(y => y.Id.Equals(item.ParentId)).FirstOrDefault().Nodes.Add(item));
                }

                List<Node> nodes = GetNodesByParent(item.Id);

                GetRecersive(nodes, ref result);
            }
        }

Answer 1

You will have to search for this recursively (search in Nodes list, then in the Nodes list of every node in previous Nodes list and so on) and keep the list of visited nodes (otherwise you will never finish if there are cycles in the structure). Have you tried doing this?

Answer 2

As empi says, a recursive search is the ideal here. If you've really got a tree, i.e. there are no cycles, it's as simple as this:

public class Node
{
    // Properties as before

    public Node FindById(Guid id)
    {
        if (id == Id)
        {
            return this;
        }
        foreach (Node node in Nodes)
        {
            Node found = node.FindById(id);
            if (found != null)
            {
                return found;
            }
        }
        return null; // Not found in this subtree
    }
}

Otherwise you'll need to keep a set (e.g. HashSet<Node>) of nodes you've already visited. Cycles make all kinds of things nasty :)

You could rewrite the foreach loop using LINQ:

return Nodes.Select(x => x.FindById(id)).FirstOrDefault();

but I'm not sure that's really as clear as the explicit loop in this particular case (and that's despite me being a huge LINQ fan).

Answer 3

This is how I would do it to cover a list of Nodes no matter how deep it is:

The Node class:

public class Node
{
    public Guid Id { get; set; }
    public DateTime Created { get; set; }
    public List<Node> Nodes { get; set; }

    public Node()
    {
     this.Nodes = new List<Node>();
    }

    public List<Node> FindNodes(Func<Node, bool> condition)
    {
     List<Node> resList = new List<Node>();

     if (this.Nodes != null && this.Nodes.Count > 0)
     {
      this.Nodes.ForEach(x =>
       {
        resList.AddRange(x.FindNodes(condition));
        if (condition(x))
         resList.Add(x);
       }
      );
     }

     return resList;
    }
}

Having this list of Nodes for example:

List<Node> nodeList = new List<Node>()
{
    new Node() { Id = Guid.NewGuid(), Created = new DateTime(2009, 01, 10), 
     Nodes = { 
      new Node() { Id = Guid.NewGuid(), Created = new DateTime(2009, 01, 11) }, 
      new Node() { Id = Guid.NewGuid(), Created = new DateTime(2009, 01, 12) } } },
    new Node() { Id = Guid.NewGuid(), Created = new DateTime(2009, 02, 10), 
     Nodes = { 
      new Node() { Id = Guid.NewGuid(), Created = new DateTime(2009, 02, 11), 
       Nodes = {
        new Node() { Id = Guid.NewGuid(), Created = new DateTime(2009, 11, 11) }, 
        new Node() { Id = Guid.NewGuid(), Created = new DateTime(2009, 12, 12),
         Nodes = {
          new Node() { Id = Guid.NewGuid(), Created = new DateTime(2011, 11, 11) }, 
          new Node() { Id = Guid.NewGuid(), Created = new DateTime(2011, 12, 12) } } } } }, 
      new Node() { Id = Guid.NewGuid(), Created = new DateTime(2009, 02, 12) } } },
    new Node() { Id = Guid.NewGuid(), Created = new DateTime(2009, 03, 10), 
     Nodes = { 
      new Node() { Id = Guid.NewGuid(), Created = new DateTime(2009, 03, 11) }, 
      new Node() { Id = Guid.NewGuid(), Created = new DateTime(2009, 03, 12) } } },
};

I can find any sub-node I want like that:

List<Node> resList = new List<Node>();

nodeList.ForEach(x =>
    resList.AddRange(x.FindNodes(y => y.Created.Day == 12)));

You can look by anything you want to. In the above example I search for nodes that are Created on the 12th day of any month and year.

Answer 4

You can add code that flatterns you hierarchy and use LINQ:

public class Node
{
    // Properties

    public IEnumerable<Node> AllNodes
    {
        get
        {
            yield return this;

            foreach (var node in Nodes.SelectMany(n => n.AllNodes))
                yield return node;
        }
    }
}

and use LINQ to Objects:

var matches = nodes.SelectMany(n => n.AllNodes).Where(n => n.Created < DateTime.Today);

Answer 5

It seems we all have over complicated it all. I showed the problem to a colleague of mine and he produced the below which works perfectly.

private void BuildUpChildren(List<Node> list)
        {
            foreach (Node item in list)
            {
                List<Node> nodes = GetNodesByParent(item.Id);
                item.Nodes.AddRange(nodes);
                BuildUpChildren(nodes);
            }
}