Is there an existing class in .Net for representing and querying hierarchical data; i.e. providing methods which allow you to test whether one item is an ancestor or descendant of another, or to provide a way to fetch all ancestors/descendants recursively from a given object?
Failing that, I've created a very basic example to illustrate the sort of thing I'm after... I've not done any optimisation as I'm hoping this is a common enough requirement that there's already something OOTB or a package I could use instead of rolling my own; though so far I haven't found one. I'd welcome feedback on this approach in case I've missed any good tricks which may improve this approach. Also, I realise this current approach allows the dictionary's key to be a mutable type, which may lead to issues with some use cases, so if there's a way to enforce the type to be immutable that would be helpful.
public class HierarchicalNode<T> where T : IComparable
{
public T Value {get;}
public HierarchicalNode<T> Parent {get;}
public List<HierarchicalNode<T>> Children {get;}
public HierarchicalNode(T value, HierarchicalNode<T> parent = null)
{
this.Children = new List<HierarchicalNode<T>>();
this.Value = value;
this.Parent = parent;
parent?.Children.Add(this);
}
public bool IsAncestorOf(HierarchicalNode<T> item, bool includeSelf = true)
{
return item != null
&& (
includeSelf && this.Value.CompareTo(item.Value) == 0
|| IsAncestorOf(item.Parent)
)
;
}
public bool IsDescendantOf(HierarchicalNode<T> item, bool includeSelf = true)
{
return item != null
&& (
includeSelf && this.Value.CompareTo(item.Value) == 0
|| (this.Parent?.IsDescendantOf(item) ?? false)
)
;
}
public bool IsRoot()
{
return this.Parent == null;
}
public IEnumerable<T> GetDescendants(bool includeSelf = false)
{
if (includeSelf)
{
yield return Value;
}
foreach (var child in Children)
{
yield return child.Value;
foreach (var descendant in child.GetDescendants())
{
yield return descendant;
}
}
}
public IEnumerable<T> GetAncestors(bool includeSelf = false)
{
if (includeSelf)
{
yield return Value;
}
foreach (var ancestor in this?.Parent?.GetAncestors(true) ?? Enumerable.Empty<T>())
{
yield return ancestor;
}
}
}
# Note: I'm including a dictionary so there's an easy way to get all values without having to traverse the graph / so we can represent islands of disconnected data; i.e. if there are several root nodes.
public class HierarchicalDictionary<Key, T>
where T : IComparable
where Key: class
{
private Dictionary<Key, HierarchicalNode<T>> dict = new Dictionary<Key, HierarchicalNode<T>>();
private Func<T, Key> getKey;
Func<T, Key> getParentKey;
public HierarchicalDictionary(Func<T, Key> getKey, Func<T, Key> getParentKey)
{
this.getKey = getKey;
this.getParentKey = getParentKey;
}
public void Add(T item) {
if (item == null) throw new ArgumentNullException(nameof(item));
var key = getKey(item);
var parentKey = getParentKey(item);
if (parentKey != null && !dict.Keys.Contains(parentKey)) {
throw new InvalidOperationException($"Parent must exist before child can be added. Key [{key}]. ParentKey [{parentKey}]");
}
if (dict.Keys.Contains(key)) {
throw new InvalidOperationException($"An object with the key [{key}] already exists");
}
var parent = parentKey == null ? null : dict[parentKey];
var node = new HierarchicalNode<T>(item, parent);
dict.Add(key, node);
}
public void AddRange(IEnumerable<T> item)
{
foreach (var i in item)
{
this.Add(i);
}
}
public bool IsAncestorOfByKey(Key a, Key b, bool includeSelf = true)
{
var objA = dict[a];
var objB = dict[b];
return objA.IsAncestorOf(objB);
}
public bool IsDescendantOfByKey(Key a, Key b, bool includeSelf = true)
{
var objA = dict[a];
var objB = dict[b];
return objA.IsDescendantOf(objB);
}
public IEnumerable<T> GetDescendantsOfByKey(Key key)
{
return dict[key].GetDescendants();
}
public IEnumerable<T> GetAncestorsOfByKey(Key key)
{
return dict[key].GetAncestors();
}
}
Example Implementation: DotNet Fiddle
void Main()
{
var employees = new Employee[]
{
new ("[email protected]","Brie Emmental", null),
new ("[email protected]","Adrian Steward","[email protected]"),
new ("[email protected]","Max Power", "[email protected]"),
new ("[email protected]","Robert Ott","[email protected]"),
new ("[email protected]","Anne Droid","[email protected]"),
new ("[email protected]","Simon Borg","[email protected]"),
new ("[email protected]","Person A",null),
new ("[email protected]","Person B","[email protected]"),
new ("[email protected]","Person C","[email protected]"),
new ("[email protected]","Person X","[email protected]"),
new ("[email protected]","Person Y","[email protected]"),
new ("[email protected]","Person Z","[email protected]")
};
var roster = new HierarchicalDictionary<string, Employee>(x => x.Id, x => x.ManagerId);
roster.AddRange(employees);
foreach (var a in employees)
{
foreach (var b in employees)
{
var relationship = roster.IsAncestorOfByKey(a.Id, b.Id) ? "manages" : "does not manage";
Console.WriteLine($"[{a.Name}] {relationship} [{b.Name}]");
relationship = roster.IsDescendantOfByKey(a.Id, b.Id) ? "reports to" : "does not report to";
Console.WriteLine($"[{a.Name}] {relationship} [{b.Name}]");
}
}
Console.WriteLine();
foreach (var descendant in roster.GetDescendantsOfByKey("[email protected]"))
{
Console.WriteLine($"Employees Of Max: [{descendant.Name}]");
}
Console.WriteLine();
foreach (var descendant in roster.GetAncestorsOfByKey("[email protected]"))
{
Console.WriteLine($"Managers Of Robert: [{descendant.Name}]");
}
Console.WriteLine("End of demo");
}
public class Employee: IComparable
{
public string Id {get;}
public string Name {get;}
public string ManagerId {get;}
public Employee (string id, string name, string managerId)
{
Id = id;
Name = name;
ManagerId = managerId;
}
public int CompareTo(object obj) {
return this.Id.CompareTo((obj as Employee)?.Id);
}
}
