What is the best way to get the level from a tree data structure using LINQ?

I have a collection demonstrates a tree data structure, it's node is:

Node:
Id
Name
ParentID

Now, I want to get the level for each node in this collection, I tried with the following code but I wonder if it's the best way to implement that.

Func<int, int> GetLevel = (nodeID) =>
{
    int _level = 0;
    var _node = source.First(p => p.Id == nodeID);

    // while hasn't reached the root yet
    while (_node .ParentID.HasValue)
    {
        _level++;
        _node = source.First(p => p.Id == _node.ParentID);
    }
    return _level;
};

// source is a collection of Node.

var query =   from node in source
              select new
              {
                  Id = node.Id,
                  Name = node.Name,
                  ParentID = node.ParentID,
                  Level = GetLevel(node.Id)
              };

I think that the overhead in GetLevel function is able to decrease. or maybe there is a better way to get it directly without this function!开发者_StackOverflow中文版

Any idea!

With this Node class you can do this easily.

public class Subject
{
    public int Id { get; set; }
    public int? ParentId { get; set; }
    public string Name { get; set; }
}

Create a tree and show the level of each node:

var list = new List<Subject>
{
    new Subject {Id = 0, ParentId = null, Name = "A"},
    new Subject {Id = 1, ParentId = 0, Name = "B"},
    new Subject {Id = 2, ParentId = 1, Name = "C"},
    new Subject {Id = 3, ParentId = 1, Name = "D"},
    new Subject {Id = 4, ParentId = 2, Name = "E"},
    new Subject {Id = 5, ParentId = 3, Name = "F"},
    new Subject {Id = 6, ParentId = 0, Name = "G"},
    new Subject {Id = 7, ParentId = 4, Name = "H"},
    new Subject {Id = 8, ParentId = 3, Name = "I"},
};
var rootNode = Node<Subject>.CreateTree(list, n => n.Id, n => n.ParentId).Single();

foreach (var node in rootNode.All)
{
    Console.WriteLine("Name {0} , Level {1}", node.Value.Name, node.Level);
}

You could do it top-down in n steps with Breadth First Traversal. Your approach is n*log(n)as far as I can see?

A quick hack in LinqPad with a node class with Level field

class Node
{
    public string Id;
    public string ParentID;
    public int Level;
    public Node SetLevel(int i)
    {
        Level = i;
        return this;
    }
}

void Main()
{
    var source = new List<Node>(){
     new Node(){ Id = "1" },
     new Node(){ Id = "2", ParentID="1"},
     new Node(){ Id = "3", ParentID="1"},
     new Node(){ Id = "4", ParentID="2"}
     };

    var queue = source.Where(p => p.ParentID == null).Select(s => s.SetLevel(0)).ToList();
    var cur = 0;

    while (queue.Any())
    {
        var n = queue[0];
        queue.AddRange(source.Where(p => p.ParentID == n.Id).Select(s => s.SetLevel(n.Level + 1)));
        queue.RemoveAt(0);
    }
    source.Dump();
}

Outputs:

Id ParentID Level
 1  null      0
 2    1       1 
 3    1       1
 4    2       2

But this all depends on the complexity of the Linq parts (.Where)

Since you say you need to get the level for each node in this collection, you might as produce a map from node to level eagerly.

This can be done in O(n) time with a proper breadth-first traversal.

(Untested):

public static Dictionary<Node, int> GetLevelsForNodes(IEnumerable<Node> nodes)
{
    //argument-checking omitted.

    // Thankfully, lookup accepts null-keys.
    var nodesByParentId = nodes.ToLookup(n => n.ParentID);

    var levelsForNodes = new Dictionary<Node, int>();

    // Singleton list comprising the root.
    var nodesToProcess = nodesByParentId[null].ToList();

    int currentLevel = 0;

    while (nodesToProcess.Any())
    {
        foreach (var node in nodesToProcess)
            levelsForNodes.Add(node, currentLevel);

        nodesToProcess = nodesToProcess.SelectMany(n => nodesByParentId[n.Id])
                                       .ToList();
        currentLevel++;
    }

    return levelsForNodes;
}

A more compact version of what you're doing is below, note I used a simplified data structure for my test and Flatten returns an IEnumerable < Tree > of every node in the tree from the variable tree on down. I would make the recursive depth function part of the tree class if you have access to that source. If you are doing this often or your trees are huge (or both) I'm particular to the solution of caching the depth in a dictionary or the tree structure itself. If you don't do it often this will work fine. I use it for going through relatively small tree structures from a GUI and no one has ever thought the operation was slow. Complexity is O(N log N) average case for getting the depth of every node. If you would like to see all of the code I can put it in tomorrow.

Func<Tree, int> Depth = null;
Depth = p => p.Parent == null ? 0 : Depth(p.Parent) + 1;

var depth = tree.Flatten().Select(p => new { ID = p.NodeID(), HowDeep = Depth(p) });

Right now you are processing a lot of things multiple times. I would recursively build the levels. This way you don't have any processing overhead.

Also, if you run this functionality a lot, I would put in the level in the node class as a variable which is computed automatically when a node is added.

Source code follows.

Try using .ToDictionary like this:

var dictionary =
    source.ToDictionary(n => n.Id, n => n.ParentId);

Func<int, int> GetLevel = nid =>
{
    var level = -1;
    if (dictionary.ContainsKey(nid))
    {
        level = 0;
        var pid = dictionary[nid];
        while (pid.HasValue)
        {
            level++;
            pid = dictionary[pid.Value];
        }
    }
    return level;
};

This is fairly efficient since your final query is going to recurse thru all of the nodes. The expense to build a dictionary is therefore cheap.

Depending how deep your nodes go you might find that building a dictionary is quicker than doing multi-level brute force searches in any case.