9

Suppose I have the following class structure:

enter image description here

  1. A forest can have any number of trees, but each tree can belong to only one forest. If the forest is deleted, the tree is deleted.

  2. A tree must have at least one branch, but can have many more, however each branch can belong to only one tree. If the tree is deleted, the branch is deleted.

  3. A branch can have any number of leaves, and each leaf can belong to only one branch. If the branch is deleted, the leaf is deleted.

I believe this is a 'composition' structure, where each child depends on its parent for existence.

How might I represent a structure where each branch can contain other branches, which can contain other branches, and so on and so forth, essentially like this:

enter image description here

Notice the infinite loop I've added to branch, suggesting that a branch can contain any number of 'child' branches, which can in turn contain any number of child branches etc etc, similar to how a real tree might function, where each branch can contain smaller branches, which can in turn contain smaller branches:

enter image description here

How might I therefore create a structure where:

  1. Each branch class can contain an infinite (and unknown) number of 'child' branch classes

  2. Each branch can have access to itself and its child branches only (i.e it cannot see parent data)

  3. Each branch has the ability to make decisions for itself and its child branches only (i.e. the chain of power over subordinates increases as you move up the chain towards the parent)

In other words, a simple heirarchy structure, but with a flexible hierarchy depth.

It is this unknown number of parent/child generations which is causing me difficulty. If I knew that a 'grandparent' branch can only contain 'parent' branches, which in turn can only contain 'child' branches, then I could easily hardcode 3 classes to represent grandparent/parent/child branches.

However since the number of 'generations' is unknown, I can't seem to get my head around how this might be represented in a UML Class Diagram, and later implemented.

How might I best approach this?

5
  • 1
    Composite – gnat May 4 at 10:12
  • 11
    Just the way you did it; that's perfectly fine (the objection by qwerty_so is about the notational semantics of the filled diamond in UML, but that's besides the point). It's just a recursive structure; implementation wise, all you need is a member variable that stores a collection of branches (e.g. List<Branch>) in your Branch class, and possibly a mechanism to determine if the branch has child branches. – Filip Milovanović May 4 at 10:43
  • 2
    Sure, this is pretty common. For example the browser DOM is such a tree. – JacquesB May 4 at 12:09
  • 12
    Have you learned about "class structures" before you have learned about data structures? What you describe is, perhaps ironically, called a tree. – Carsten S May 4 at 19:03
  • 1
    The class per se doesn't contain anything; instances of the class can contain other instances, even of the same class. I know, it's largely just a matter of terminology, but I think using the right terminology can clear up possible misconceptions and offer a better mental model. – Roel Schroeven May 5 at 13:36
9

Can a class contain its own class?

Yes. Case in point:

public class Foo
{
    public Foo Parent { get; set; }
}

var parent = new Foo();
var child = new Foo() { Parent = parent };

However, a class cannot then have only constructors which require a parameter of the same class, such as

public class Foo
{
    public Foo Parent { get; }

    public Foo(Foo parent)
    {
        this.Parent = parent;
    }
}

The language allows it, but it's impossible to ever create such an object, as it leads to an infinitely recursing chain of constructors:

var parent = new Foo(new Foo(new Foo(new Foo(...)))); // to infinity!

This just never ends.

Edit: user1937198 correctly pointed out that you can simply pass in null (barring some constraints such as C#'s non-nullable types), but that is in my opinion off-label usage as it's conceptually contradictory to (a) have a constructor ask for an object (b) not provide any constructor which doesn't aks for that object, and then (c) not passing an object.

However, if there are other constructors available as well, then there is no problem. The first created object is simply limited to using the constructors without the same class as constructor parameter

public class Foo
{
    public Foo Parent { get; }

    public Foo(Foo parent)
    {
        this.Parent = parent;
    }

    public Foo()
    {

    }
}

var parent = new Foo();
var child = new Foo(parent);

As a general rule, there are three ways to model this relationship:

  1. Parent-oriented:
public class Foo
{
    public Foo Parent { get; set; }
}

var parent = new Foo();
var child = new Foo() { Parent = parent };
  1. Child-oriented:
public class Foo
{
    public List<Foo> Children { get; set; }
}

var child = new Foo();
var parent = new Foo();
parent.Children.Add(child);
  1. Both (this is commonly used for navigational properties such as in Entity Framework)
public class Foo
{
    public Foo Parent { get; set; }
    public List<Foo> Children { get; set; }
}

var parent = new Foo();
var child = new Foo() { Parent = parent };
parent.Children.Add(child);

How might I therefore create a Branch?

I believe this is a 'composition' structure, where each child depends on its parent for existence.
How might I represent a structure where each branch can contain other branches, which can contain other branches, and so on and so forth

For reference, what you're looking for here is a 'recursive' structure, as opposed to a 'composite' structure.

Note that 'recursive' doesn't inherently mean a self-relationship (i.e. Branch->Branch->Branch->...), it could also be a longer chain without self-relationships (e.g. A->B->C->A->B->C->...), though that distinction is irrelevant for your specific use case.

  1. Each branch class can contain an infinite (and unknown) number of 'child' branch classes

This is describing a collection, e.g. List<Branch>. Other collection types exist but I'm using List<> for simplicity's sake.

  1. Each branch can have access to itself and its child branches only (i.e it cannot see parent data)

Therefore, a branch needs to contain such a collection of (child) branches:

public class Branch
{
    public List<Branch> Branches { get; set; }
}

This is the child-oriented example from the previous examples.

  1. Each branch has the ability to make decisions for itself and its child branches only (i.e. the chain of power over subordinates increases as you move up the chain towards the parent)

3 is a logical consequence of 2, so it is automatically achieved when 2 is achieved.

I can't seem to get my head around how this might be represented in a UML Class Diagram

Branch-to-branch

Your UML is perfectly fine in regards to the self-relationship. You drew a relationship from Branch to Branch, which does express it.

This kind of relationship is inherently recursive (i.e. what you call "infinite depth"). It's actually impossible to avoid recursion here, because that would require using multiple types to denote branches that can/can't have further children.

Note that while the relationship itself is inherently recursive, it's possible that your business logic might enforce a maximum depth. Maybe not necessary for your case, but it is a general possibility.
However, that sort of depth-limit is not visible on a UML diagram, and shouldn't particularly be visible as UML diagrams do not contain validation or business logic.

Tree-to-branch

However, do note that the relationship a branch has with its tree has changed. The "child" branches won't be related to a tree, they'll be related to their parent branch. And the "top" branch will have the relationship to the tree.

This means that your tree-to-branch relationship is now a 0..1 to many relationship.


Complexity vs security

I just want to point out that there are circumstances which can change the outcome.

If only a branch which has no child branches is allowed to have leaves, and branches with child branches are not allowed to, your UML is flawed, as all branches can have leaves.
If this is what you need, then you're going to need to model different types for a "branch-having branch" and a "leaf-having branch".

Note: I'm aware that in your drawing of a tree you drew leaves on all kinds of branches, but I also suspect that your tree scenario is an example and not indicative of what you may be trying to build in reality.

Similarly, your UML is relying on your business logic ensuring that only the ancestor branch is connected to the tree, not any other branch. If you wish to model this more securely, then you would also need to distinguish between a "tree-related branch" and a "branch-related branch".

However, there is some degree of freedom here. You could model that in your UML, but it will complicate the diagram. You could also stick to simple modeling with only a Branch type which could all be related to a tree, child branches, and leaves; and then rely on your business logic to ensure that you build your graph the right way.

This very much depends on whether you're willing to take on the added model complexity in order to outright prevent "bad" graphs, which requires context from how bad an error in your application is.

  • For example, if it could kill people by malfunctioning, prioritize security (enforcing it through the diagram) over simplicity (relying on business logic).
  • On the other hand, if this is a simple app that e.g. tracks cooking recipes, at the very worst you're going to get some dirty data that needs cleaning, which is a negligible issue and is not worth the headaches that such a complex UML diagram would cause.
11
  • 1
    @Alan: Your UML can specify a 0..1 to 1..many relationship, but in code it's not possible to do so through class design alone (that I am aware of). Collections are inherently 0..*. Requiring a tree to have at least one branch in its collection of branches is validation logic on that collection, which is the avenue you should explore to enforce this rule; but this kind of validation is separate from the class design itself. Before then, you can write it on the human-readable UML, but not enshrine it in the class structure which is based on your UML. – Flater May 4 at 12:43
  • 1
    @Alan: At the end of the day, UML is a human-readable chart. This chart is not consumed by an algorithm, so you don't need to confirm to pedantic preset rules. As long as it remains human-readable and the readers value the information, it's a good diagram. You're always able to add the comment if you truly feel it adds value to the reader, but it's not "prescribed" UML usage. Similarly, I tend to never distinguish 0..* vs 1..* relationships, I just use * because that's how the class will be designed anyway. That's my opinion, and you may disagree and find this an important distinction. – Flater May 4 at 12:54
  • 1
    @Alan: Just for completeness, the only relationships I tend to model are 1 (required), 0..1 (optional) and * (many). So far, I have not had any complaints about the diagram being unclear or unreadable. You could add the "at least one" constraint to the diagram, but that's in my opinion business logic, and the rest of the business logic doesn't belong on a UML chart, so why would this specific bit of logic be relevant? Again, this is just my opinion, I like to keep a clean separation between class design and business logic because not all business logic fits in a class design diagram. – Flater May 4 at 12:57
  • 1
    @Alan: My advice may offend some UML purists because I don't use strict UML, but I tend to favor practicality over preaching dogma. I'm not a stickler for diagrams, I use them as they suit me, commonly as a "zoomed out" visualization of a group of classes (which an IDE is not great at visualizing). To be honest, I can never tell the difference between the arrow types, and it's not something I've needed to know to do my job. I didn't even need the arrows on your lines to understand your diagram and intention. – Flater May 4 at 13:08
  • 4
    At least in Java, there is a fairly simple way to construct the class which requires itself in the constructor: null. To take your example class, new Foo(null) is a perfectly valid way of creating the final Foo. – user1937198 May 4 at 19:58
2

Besides the already given suggestion to use the composite pattern, I see two ways to fix this model:

  1. Replace the 1:* relationships between "trees -> branches" and "branches -> branches" by a {0,1}:* aggregation. Add a constraint to the model enforcing that exactly one of the two parent-child references must be valid for each branch object.

  2. Keep the 1:* aggregation between "trees -> branches", but make the relationship for "branches -> branches" a {0,1}:* association. Here, the tree is the "owner" of all of its branches, if regardless if they are directly "starting" at the tree or somewhere in the middle.

The first approach has the advantage that it will make easier to take out a branch with sub-branches from the first tree and move it to anothe tree. But it may be more effort to run an algorithm which does something "for all branches", this will always require a recursive scan.

Finally, you wrote

Notice the infinite loop I've added to branch

You didn't. You added a loop. The loop only becomes "infinite" if someone interconnects the objects in a cyclic way.

I can't seem to get my head around how this might be later implemented.

Here is a very simplistic implementation in C#. It might not be sufficient for a real application, but I guess you get the idea:

// Variant 1
class Branch
{
    public Tree MyTree{get; private set;}

    public Branch ParentBranch{get; private set;}

    public Branch(Tree tree){MyTree = tree;}
    public Branch(Branch parentBranch)
    {
        // MyTree stays null here
        ParentBranch = parentBranch;
    }

    public Branch AddNewBranch(){return new Branch(this);}
    // the "Tree" class will contain a similar method
}
// Variant 2
class Branch
{
    public Tree MyTree{get; private set;}

    public Branch ParentBranch{get; private set;}

    public Branch(Tree tree){MyTree = tree;}

    public Branch(Branch parentBranch)
    {
         MyTree = parentBranch.MyTree;
         ParentBranch= parentBranch;
    }
    public Branch AddNewBranch(){return new Branch(this);}
}
1

I am not sure about the UML, but here is a C++ implementation which compiles and runs. This solution uses abstract base classes. So a Branch contains "children" each of which can be either a Leaf or a another Branch.

#include <iostream>
#include <vector>

using std::cout;

 // Base class for formatted output of structure
class WoodBase {
public:
    virtual ~WoodBase() {
    }

    virtual const char *getType() = 0;

    virtual void outputChildren(int depth) {}

    void output(int depth = 0) {
        int tabs = depth;
        while (tabs--) cout << '\t';
        cout << getType() << '\n';
        outputChildren(depth + 1);

    }
};

// Base class for container classes
template<class T> class WoodParent : public WoodBase {
protected:
    std::vector<T *> _children;

    template<class CHILD> CHILD *addChild() {
        CHILD *child = new CHILD();
        _children.push_back(child);
        return child;
    }

public:
    virtual ~WoodParent() {
        for (auto i: _children) delete i;
    }

    virtual void outputChildren(int depth) {
        for (auto i: _children) i->output(depth);
    }
};

class Leaf : public WoodBase {
public:
    const char *getType() { return "Leaf"; }
};

class Branch : public WoodParent<WoodBase> {
public:
    const char *getType() { return "Branch"; }

    Branch *addBranch() { return addChild<Branch>(); }

    Leaf *addLeaf() { return addChild<Leaf>(); }
};

class Tree : public WoodParent<Branch> {
public:
    const char *getType() { return "Tree"; }

    Branch *addBranch() { return addChild<Branch>(); }
};

class Forest : public WoodParent<Tree> {
public:
    const char *getType() { return "Forest"; }

    Tree *addTree() { return addChild<Tree>(); }
};

int main() {
    Forest forest;

    // Create trees, branches and leaves
    Tree *tree1 = forest.addTree();
    Branch *branch = tree1->addBranch();
    branch->addLeaf();
    branch->addLeaf();
    tree1->addBranch()->addBranch()->addLeaf();

    //Another tree with many sub branches
    forest.addTree()->addBranch()->addBranch()->addBranch()->addBranch()->addLeaf();

    forest.output();
    return 0;
}

Here is the output:

Forest
    Tree
        Branch
            Leaf
            Leaf
        Branch
            Branch
                Leaf
    Tree
        Branch
            Branch
                Branch
                    Branch
                        Leaf
0

Yes it can, a class can contain objects of it's own class;

So what you want to do is create a branch class that contains details of all it's children, the implementation of what you've described could be like this:

class Branch
{
    private String name;
    private List<Branch> childBranches; //only tracking child branches of current branch

    public Branch(String name)
    {
        this.name = name;
    }

    public void addChild(Branch branchToBeAdded)
    {
        childBranches.add(branchToBeAdded);
    }

}

So now each branch can contain infinite number of child branches.

1
  • In particular, childBranches will often be empty. – J.G. May 4 at 19:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.