Design of double linked Parent - Child relation

Question

Hi folks,

I have defined a C#-class, that shall be the elements of a directed graph (basically a tree, but an element can have multiple parents - I do not know if there is a special name for that).

Each element shall now all its children and all its parents. It exposes those lists as IEnumarable

public interface IMyClass
{
  public IEnumerable<MyClass> Children { get; }
  public IEnumerable<MyClass> Parents { get; }
}

public class MyClass : IMyClass
{
  private List<MyClass> _parents;
  private List<MyClass> _children;

  public IEnumerable<MyClass> Children
  {
    get { foreach (var child in _children) yield return child; }
  }

  public IEnumerable<MyClass> Parents
  {
    get { foreach (var parent in _parents) yield return parent; }
  }

When adding or removing a child to a given element, I want to make sure, that the given element is added or removed to the parents list of the child too.

First idea was to only expose an AddChild(MyClass theChild) method. Problem is, that I can't add the parent to the theChild object because it doesn't expose an AddParent(parent) method and I can't call private methods of the theChild-object.

So I tried to go with exposing an AddParent(MyClass theParent) method too. To still make sure that both objects links are set, my first shot was calling the AddParent/AddChild in the other function like this:

public void AddChild(IMyClass theChild)
{
  _children.Add(theChild);
  theChild.AddParent(this);
}

public void AddParent(IMyClass theParent)
{
  _parent.Add(theParent);
  theParent.AddChild(this);
}

but obviously, that is a deadly loop.

To make things worse, I want to allow that an element can be the child of another element multiple times (this isn't a requirement yet, but I want to make sure, that WHEN this requirement comes, my code need not to be touched.)

Are there any algorithms / standard approaches that allow me to make sure, that when adding a child to the parent always both object links are set?

Thanks in advance,
Frank

Edith: Added the interfaces to correct the example.

Answer 1

You could do this:

public void AddChild(MyClass theChild)
{
    _children.Add(theChild);
    theChild._parent.Add(this);
}

public void AddParent(MyClass theParent)
{
    _parent.Add(theParent);
    theParent._children.Add(this);
}

There should be no problems with that; just because you're referring to a different instance of the class you're writing the method for doesn't mean you can't access it's members (even if they are private).

---

OK with the revised code, you can add two new members to your interface: NotifyChildAdded and NotifyParentAdded, and implement like this:

public void AddChild(MyClass theChild)
{
    _children.Add(theChild);
    theChild.NotifyParentAdded(this);
}

public void AddParent(MyClass theParent)
{
    _parent.Add(theParent);
    theParent.NotifyChildAdded(this);
}

public void NotifyChildAdded(MyClass theChild)
{
    _children.Add(theChild);
}

public void NotifyParentAdded(MyClass theParent)
{
    _parent.Add(theParent);
}

Hope that helps!

Answer 2

... but I want to make sure, that WHEN this requirement comes, my code need not to be touched.
That's a clear violation of the YAGNI-principle (you ain't gonna need it). Maybe you should just start to code it the way you need it right now (that means using Contains() ^^). And care about changes to your requirement when they come ...

Answer 3

One option is to expose the list properties as internal, and have public add methods that will call access the internal properties of the other class.

Another option is to have dumb data and a separate business logic layer which is what outside code calls.

Answer 4

Another possible design is to store the relationship between the nodes in the Graph object rather than embedding this information in the Node objects. If you still want to operate from the Node classes, you can pass an interface for the Graph to the Nodes so that they can provide 'convenience' functions like GetParents(), GetChildren(), AddParent(), AddChild() that call the appropriate public Graph functions. The idea here is that the Nodes shouldn't be responsible for managing Graph operations; this should be the Graph's responsibility.

One simple implementation is an adjacency matrix. This is an NxN boolean array where N is the number of nodes and the contents of A[i,j] indicates whether there is a link from node i to node j. This makes updating parent/child relationships O(1) (simply set/reset a flag) and makes enumerating parents and children for a given node O(N). The downside is that you use O(N^2) space. This is a good approach if you want to mutate the graph frequently. It also generalizes to a weighted graph if you store weights instead of flags.

You can use a 'list of lists' type of approach if you want to conserve space. This is really only beneficial if the number of links is much smaller than the number of nodes (i.e. the graph is sparsely connected) and the number of nodes is large.