How to implement a dependency tree of updating objects?

Question

Edit: I am not looking for an implementation but just for some keywords to search and methodologies to get me started.

I am struggling with generating a dependency tree where child nodes are updated by an external process and the requirement is to update all parent nodes of updated child nodes.

Example: Imagine a tree such as this: O [parent], O(l) [left child], O(r) [right child], O(ll), O(lr), O(rl), and O(rr). O(ll), O(lr), O(rl), and O(rr) have reference to a data collection that is updated at random intervals).

I want to implement a pull process, where at certain intervals a process checks whether O is updated. "Updated" is defined as being updated when all child nodes are updated, else just the cached value(result) of that node is used. The pull process's job is to ensure that O is updated when any of the child nodes is not updated. This means that the process needs to traverse the tree and check whether O(ll), O(lr), O(rl), and O(rr) are updated. If the data collection, those child nodes reference, are updated since the last update of those child nodes then those child nodes need to be updated as function of the changed data collection. If the data collection is updated and hence the child nodes O(ll), O(lr), O(rl), and O(rr) are updated as well and this means that O(l) and O(r) also need to be updated and subsequently O will also be updated. Each child node is input to its parent node.

The complexity here is that each child node is shared among different trees, meaning, a child node of one tree can also be any child node of another tree. The purpose of this structure is to avoid the re-calculation of a child node when it is already up-to-date. The child nodes are shared if different trees implement a child node with the exact same functionality (function and parameterization) as the already existing child node.

I am stuck with the design of this structure and how to go about implementing it. I have not provided code yet because I am stuck with the design thought process. Essentially each child is function and depends on dependent functions itself.

What makes me wonder is whether C# offers the ability to decorate methods and classes in order to simplify the checking of whether a node is updated or not. Also does lazy evaluation play a role in this process at all?

Answer 1

I suggest defining a class that keeps track whether its children have been updated via a flag, e.g. a Boolean named Dirty. A node in the tree can tell its parents to become dirty by raising an event. When a node returns its own value, it should check the flag and recompute its own value only when needed. When recomputing, it should check the Value of each child, each of which will then check its own dirty flag, and so on, recursively.

class Node<T> 
{
    event EventHandler Changed;

    private T _value;
    private bool _dirty = true;
    private List<Node<T>> _children = new List<Node<T>>();

    public void AddChild(Node<T> child)
    {
        child.Changed += (s,e) => _dirty = true;
        _children.Add(child);
    }

    protected void OnChanged()
    {
        if (Changed != null) Changed(this, new EventArgs());
    }

    public T Value
    {
        get
        {
            if (_dirty)
            {
                this.Value = ComputeValueFromChildren();
                _dirty = false;
            }
            return _value;
        }
        set
        {
            _value = value;
            OnChanged();
        }
    }

    private T ComputeValueFromChildren()
    {
        var values = _children.Select( child => child.Value );
        //Return the new value based on the children
    }
}