Flattening a tree of classes using SelectMany()

Question

I have a class that tracks relations between owner classes. The tree can potentially be infinite--in the DB, each record has a parent ID that is a self-reference to the same table. The class basically looks like this:

public class ObjectRelation
{

    public ObjectRelation(GetObjectParentChildList_Result relation)
    {
        this.ObjectId = relation.Object_ID;
        this.ParentObjectId = relation.Parent_Object_ID;
        this.ChildObjects = new List<ObjectRelation>();
    }

    public int ObjectId { get; set; }
    public int? ParentObjectId { get; set; }
    public List<ObjectRelation> ChildObjects { get; set; }

}

I'd like a way given a reference to a single instance of this class to end up with a list of every unique ID in the tree in one list to ensure that as a user is entering data they don't create a infinite parent/child loop (ie, IDs 1 & 2 being parents of each other) and it looks as though SelectMany is the way to go. Is such a query feasible in LINQ, or am I stuck writing a separate method to recurse down the whole tree and return the calculated list of IDs once I run out of child nodes?

Is this a tree, or a directed graph? Trees cannot have infinite patent-child loops. — Sergey Kalinichenko, Jun 20 '17 at 16:47
[Here is a solution that requires a tree](https://stackoverflow.com/a/11830287/335858). It will not work for graphs with cycles, and it would not remove duplicates. — Sergey Kalinichenko, Jun 20 '17 at 16:48
ObjectRelation should have a parent property, then just navigate up the graph looking for a repeated id. Or create an extension method on ObjectRelation called Parents that returns an IEnumerable, then check if any Parents are the child in question. `if (x.Parents.Any(p=>p.ObjectId == x.ObjectId)) throw Exception();` — Robert McKee, Jun 20 '17 at 17:34

score 0 · Accepted Answer · answered Jun 20 '17 at 17:40

public class ObjectRelation
{
    public ObjectRelation(GetObjectParentChildList_Result relation)
    {
        this.ObjectId = relation.Object_ID;
        this.Parent = relation.Parent_Object;
        this.ChildObjects = new List<ObjectRelation>();
    }

    public int ObjectId { get; set; }
    public ObjectRelation Parent { get; set; }
    public List<ObjectRelation> ChildObjects { get; set; }
}

public static class ObjectRelationExtensions
{
  public static IEnumerable<ObjectRelation> Parents(this ObjectRelation obj)
  {
    while(obj.Parent!=null)
    {
      obj = obj.Parent;
      yield return obj;
    }
  }
}

Then to check:

if (x.Parents.Any(p=>p==x)) throw Exception();

or

if (x.Parents.Any(p=>p.ObjectId==x.ObjectId)) throw Exception();

Flattening a tree of classes using SelectMany()

1 Answers1