CODEWITHSUNDEEP
c#
Rkaede
Rkaede

Reputation: 62

Counting descendants in a tree

I have the following class which recurs on itself to form a tree-like data structure: 

public class chartObject
{
    public string name { get; set; }
    public int descendants { get; set; }
    public List<chartObject> children { get; set; }
}

For each object in the tree I would like to populate the descendant property with the amount objects that exist underneath it.

Example structure:

chartObject1 (descendants: 4)
└-chartObject2 (descendants: 0)
└-chartObject3 (descendants: 2)
└--chartObject4 (descendants: 1)
└---chartObject5 (descendants: 0)

What would be the most efficient way of doing this?

Upvotes: 3

Views: 1513

Answers (4)

Enigmativity
Enigmativity

Reputation: 117055

This works for me:

public void SetDescendants(chartObject current)
{
    foreach (var child in current.children)
    {
        SetDescendants(child);
    }
    current.descendants = current.children.Sum(x => 1 + x.descendants);
}

I tested with this code:

var co = new chartObject()
{
    name = "chartObject1",
    children = new List<chartObject>()
    {
        new chartObject()
        {
            name = "chartObject2",
            children = new List<chartObject>() { }
        },
        new chartObject()
        {
            name = "chartObject3",
            children = new List<chartObject>()
            {
                new chartObject()
                {
                    name = "chartObject4",
                    children = new List<chartObject>()
                    {
                        new chartObject()
                        {
                            name = "chartObject5",
                            children = new List<chartObject>() { }
                        }
                    }
                }
            }
        }
    }
};

And got this as the result:

result

Upvotes: 2

Alexei Levenkov
Alexei Levenkov

Reputation: 100537

Walk all nodes of the tree (depth first is ok) and when done with children set "descendants property to sum of children's descendants + child count. You have to do it on every change to the tree structure. You should be able to limit updates only to parents of element that is changed.

If nodes made immutable you can populate the field at creation time.

Side notes:

  • Your tree is mutable as it is now (one can easily add more child nodes anywhere), so it may be safer to have method that counts descendants instead of property on a node.
  • Having computed property int descendants { get; set; } to be read/write is confusing as anyone can set its value to whatever number. Consider if making it read only and updating when one of child nodes changes (requires some custom notification mechanism).
  • Code style - consider naming classes with upper case names for code that is intended to be public (follow Microsoft's C# coding guidelines). chartObject -> ChartObject

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726569

For calculations to be most efficient, cache their result in the node itself. Otherwise, you'll be re-calculating the count every time the descendants property is looked up.

The cost of doing that is the need to invalidate the cache all the way up the parent chain, like this:

public class chartObject
{
    private chartObject _parent;
    private int? _descCache = null;
    public string name { get; set; }
    public int descendants {
        get {
            return _descCache ?? calcDescendents();
        }
    }
    public List<chartObject> children { get; set; }
    public void AddChild(chartObject child) {
        child._parent = this;
        children.Add(child);
        chartObject tmp = this;
        while (tmp != null) {
            tmp._descCache = null;
            tmp = tmp._parent;
        }
    }
    private int calcDescendents() {
        return children.Count+children.Sum(child => child.descendants);
    }
}

Upvotes: 1

Ani
Ani

Reputation: 113402

How about the recursive formula:

children.Count + children.Sum(c => c.descendants)

This is suitable for eager-evaluation / caching if the tree is immutable (which it isn't from the class declaration). If you want efficiency even in the face of mutability, you'll find this a lot more difficult; you can consider marking parts of the tree "dirty" as it is mutated / eagerly force the re-evalutation of this metric to "bubble up" as part of a tree is mutated.

Upvotes: 4

Related Questions