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

Question

I have a collection demonstrating the data structure of a tree, node:

Node: Id Name ParentID 

Now I want to get the level for each node in this collection, I tried to use the following code, but I'm wondering if this is the best for implementation.

 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 the overhead in the GetLevel function may decrease. or maybe there is a better way to get it directly without this feature!

Any idea!

Answer 1

With this Node class, you can do it 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); } 

Answer 2

You can do this from top to bottom in steps n with Preadth First Traversal. As far as I understand, your approach is n*log(n) ?

Quick hack in LinqPad with 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 it all depends on the complexity of the parts of Linq (anywhere)

Answer 3

Since you are saying that you need to get a level for each node in this collection, you can create a map from node to level the level.

This can be done O (n) times with the correct intersection in width.

(unverified):

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

Answer 4

A more compact version of what you are doing is below, note that I used a simplified data structure for my test, and Flatten returns the IEnumerable <Tree> of each node in the tree from the variable tree down. I would do part of a recursive depth function of a tree class if you have access to this source. If you do this often or your trees are huge (or both), I especially like the decision to cache the depth in the dictionary or the tree structure itself. If you do not, this will work fine. I use it to traverse relatively small tree structures from the GUI, and no one ever thought the operation was slow. Complexity is the O (N log N) average case for getting the depth of each node. If you want to see all the code that I can put in it 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) }); 

Answer 5

Now you process many things many times. I would build levels recursively. Thus, you do not have processing overhead.

In addition, if you run this function a lot, I would set the level in the node class as a variable that is automatically calculated when a node is added.

The following is the source code.

Answer 6

Try using .ToDictionary as follows:

 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 quite effective, as your final request will be processed through all nodes. Therefore, the cost of creating a dictionary is cheap.

Depending on how deep your nodes are, you may find that creating a dictionary is faster than performing multi-level brute force searches anyway.