Hierarchical object and AutoFixture

Question

I have implemented a class for storing tags, the tag collection must be hierachical, and so my class is:

public class Tag
{
    public int Id { get; set; }
    public int Description { get; set; }
    public Tag ParentTag { get; set; }
    // … (methods for get children, add and remove children, etc.)
}

In this way root tags (user want to be able to have many separate trees) has no parent, while non-root tags must have a parent tag.

1. Is this a good way to implement hierarchy? I find Composite Pattern, but in my domain, all tags are simply tags, to the domain expert, there is no difference between parent and child tag.

2. Problem come using AutoFixture in test; when I need to create a simple tag, it raises this error:

   Failure: Ploeh.AutoFixture.ObjectCreationException: AutoFixture was unable to create an instance of type Ploeh.AutoFixture.Kernel.SeededRequest because the traversed object graph contains a circular reference.

Edit: i read Creating recursive tree with AutoFixture but it's different case: i have only one class, not 2 and i don't want autofixture to create a tree but only a single node

Answer 1

Is this a good way to implement hierarchy?

I see three problems with it, one minor, one a little more serious, and one obviously problematic in your concrete situation.

Potential issues:

1. Let's start with the minor issue, which is about the relationship between properties' names and their types. I would recommend that a property named ParentTag should be of the Tag type itself. The fact that you declared it as int (like you did for Id) suggests that you should call the property ParentTagId instead… or that you change the property's type to Tag.

2. Now to the more serious issue. I take it that Desc points to an immediate child tag. (In case that one tag can have more than one child tag, you have obviously chosen the wrong type for this property. You'd need some kind of collection. But that's yet another problem.)

Storing both parent and children links can easily lead to inconsistencies if you're not paying good attention. It might therefore be better not to have bi-directional links for each tag, but to only store links going in one direction.

That however will complicate traversing the hierarchy in the opposite direction. One way to solve this problem would be to store only child links; if you then wanted to find the parent tag of T, you'd first find T by recursively traversing the hierarchy starting at the root tag and continuously keep track of the "path" you're taking; the parent will then be the penultimate tag in the path.

3. Now to the most immediate issue. The exception hints at it:

Ploeh.AutoFixture.ObjectCreationException […] because the traversed object graph contains a circular reference.

With your current implementation of Tag, it's possible to build tag hierarchies that contain cycles. I assume that you don't want that.

For example, tag C can have P as its parent tag, although P is already a child tag of C. Therefore, if you started following the ParentTag chain starting at C, you would first get to P and then eventually arrive back at C, and if you kept going, you would find yourself caught in an infinite loop.

I don't know AutoFixture, but it seems likely that it cannot deal with your concrete tag hierarchy for similar reasons.

You should make your tag hierarchies directed acyclic graphs (DAGs) — the "acyclic" is the important bit here. However, with your current Tag class, you can build any directed graph; it does not guarantee that there won't be any cycles.

Ways to prevent cyclic tag hierarchies:

1. Implement a check for cycles in the ParentTag setter:

public Tag ParentTag
{
    …
    set
    {
        if (!IsOrIsAncestorOf(value))
        {
            parentTag = value;
        }
        else
        {
            throw new ArgumentException("ParentTag", "would cause a cycle");
        }
    }
}
private Tag parentTag;

private bool IsOrIsAncestorOf(Tag other)
{
    return this == other || IsOrIsAncestorOf(other.Parent));
    //     ^^^^^^^^^^^^^    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    //          Is   …   Or    …    IsAncestorOf
}

2. Even simpler, make ParentTag readonly, which forces you to set it in the constructor. This will automatically make it impossible to build cyclic tag hierarchies — try it, if you don't believe it:

public Tag(Tag parentTag)
{
    this.parentTag = parentTag;
}

private readonly Tag parentTag;

public Tag ParentTag
{
    get
    {
        return parentTag;
    }
}

I would recommend the second solution.