3
\$\begingroup\$

I have put together some code that creates a tree structure from a large list of nodes (entities) and connections and am looking to speed it up.

HierarchyWorker: Converts the list data into the tree

public class HierarchyWorker
{
    public List<int> EntityIDs;

    public ILookup<int, HierarchyConnection> Connections;

    public Dictionary<int, HierarchyNode> Hierarchies;

    public void Initialise(List<int> entityIDs, ILookup<int, HierarchyConnection> connections)
    {
        EntityIDs = entityIDs;

        Connections = connections;

        Hierarchies = new Dictionary<int, HierarchyNode>();

        AddAllEntityHierarchies();
    }

    public void AddAllEntityHierarchies()
    {
        foreach (var entityId in EntityIDs)
        {
            if (!Hierarchies.ContainsKey(entityId))
            {
                AddHierarchy(entityId);
            }
        }
    }

    public void AddHierarchy(int sourceEntityId)
    {
        var node = new HierarchyNode()
        {
            EntityID = sourceEntityId,
            IsController = true,
            IsOwner = true,
            ParentNode = null,
            ChildNodes = new List<HierarchyNode>()
        };

        Hierarchies.Add(sourceEntityId, node);

        AddChildren(node);
    }

    public void AddChildren(HierarchyNode parent)
    {
        var connections = Connections[parent.EntityID].ToList();

        foreach (var entity in connections)
        {
            if (!parent.WouldCauseInfiniteLoop(entity.EntityID))
            {
                if (Hierarchies.ContainsKey(entity.EntityID))
                {
                    var node = new HierarchyNode(Hierarchies[entity.EntityID])
                    {
                        ParentNode = parent,
                        IsController = entity.IsControllerOfParent,
                        IsOwner = entity.IsOwnerOfParent
                    };

                    parent.ChildNodes.Add(node);
                }
                else
                {
                    var node = new HierarchyNode()
                    {
                        EntityID = entity.EntityID,
                        IsController = entity.IsControllerOfParent,
                        IsOwner = entity.IsOwnerOfParent,
                        ParentNode = parent,
                        ChildNodes = new List<HierarchyNode>()
                    };

                    parent.ChildNodes.Add(node);

                    AddChildren(node);

                    if (!Hierarchies.ContainsKey(node.EntityID))
                    {
                        var newNode = new HierarchyNode(node)
                        {
                            ParentNode = null,
                            IsController = true,
                            IsOwner = true
                        };

                        Hierarchies.Add(newNode.EntityID, newNode);
                    }
                }
            }
        }
    }
}

HierarchyNode: Models each node and provides methods for certain checks

public class HierarchyNode
{
    public int EntityID { get; set; }

    public HierarchyNode ParentNode { get; set; }

    public List<HierarchyNode> ChildNodes { get; set; }

    public bool IsOwner { get; set; }

    public bool IsController { get; set; }

    public HierarchyNode()
    {
    }

    public HierarchyNode(HierarchyNode copyFrom)
    {
        EntityID = copyFrom.EntityID;
        ChildNodes = copyFrom.ChildNodes;
    }

    public HierarchyNode GetSourceNode()
    {
        if (ParentNode == null)
        {
            return this;
        }
        else
        {
            return GetSourceNode(ParentNode);
        }
    }

    private HierarchyNode GetSourceNode(HierarchyNode node)
    {
        if (node.ParentNode == null)
        {
            return node;
        }
        else
        {
            return GetSourceNode(node.ParentNode);
        }
    }

    public int GetLevel()
    {
        var level = 0;

        if (ParentNode == null)
        {
            return level;
        }
        else
        {
            level++;
            return GetLevel(level, ParentNode);
        }
    }

    private int GetLevel(int level, HierarchyNode node)
    {
        if (node.ParentNode == null)
        {
            return level;
        }
        else
        {
            level++;
            return GetLevel(level, node.ParentNode);
        }
    }

    public bool WouldCauseInfiniteLoop(int entityId)
    {
        if (ParentNode == null)
        {
            return EntityID == entityId;
        }
        else
        {
            return WouldCauseInfiniteLoop(ParentNode, entityId);
        }
    }

    private bool WouldCauseInfiniteLoop(HierarchyNode node, int entityId)
    {
        if (node.EntityID == entityId)
        {
            return true;
        }

        if (node.ParentNode == null)
        {
            return false;
        }

        return WouldCauseInfiniteLoop(node.ParentNode, entityId);
    }

    public bool IsUnbrokenOwner()
    {
        if (ParentNode == null)
        {
            return IsOwner;
        }

        if (!IsOwner)
        {
            return false;
        }

        return IsUnbrokenOwner(ParentNode);
    }

    private bool IsUnbrokenOwner(HierarchyNode node)
    {
        if (node.ParentNode == null)
        {
            return IsOwner;
        }

        if (!node.IsOwner)
        {
            return false;
        }

        return IsUnbrokenOwner(node.ParentNode);
    }

    public bool IsUnbrokenController()
    {
        if (ParentNode == null)
        {
            return IsController;
        }

        if (!IsController)
        {
            return false;
        }

        return IsUnbrokenController(ParentNode);
    }

    private bool IsUnbrokenController(HierarchyNode node)
    {
        if (node.ParentNode == null)
        {
            return IsController;
        }

        if (!node.IsController)
        {
            return false;
        }

        return IsUnbrokenController(node.ParentNode);
    }
}

HierarchyConnection Models the connection

public class HierarchyConnection
{
    public int EntityID { get; set; }

    public int ParentID { get; set; }

    public bool IsOwnerOfParent { get; set; }

    public bool IsControllerOfParent { get; set; }
}

Console Program Generates some sample data (1000 sets of 100 level deep trees) and times how long the Initialise takes.

class Program
{
    static void Main(string[] args)
    {
        var entityIDs = Enumerable.Range(1, 100000).ToList();

        var connections = new List<HierarchyConnection>();

        for (int i = 0; i < 1000; i++)
        {
            connections.AddRange(entityIDs.Skip((i * 100) + 1).Take(99).Select(x => new HierarchyConnection()
            {
                EntityID = x,
                ParentID = x - 1,
                IsControllerOfParent = true,
                IsOwnerOfParent = true
            }));
        }

        var hierarchyWorker = new HierarchyWorker();

        var stopwatch = new Stopwatch();
        stopwatch.Start();

        hierarchyWorker.Initialise(entityIDs, connections.ToLookup(x => x.ParentID));

        stopwatch.Stop();

        Console.WriteLine($"Complete in {stopwatch.ElapsedMilliseconds} milliseconds");
        Console.ReadLine();
    }
}

A few notes:

  • There are some references to dataWorkers in the HierarchyWorker class, those are outside of the scope of this review.
  • The connections represent an "entity" that is an owner or a controller of another entity.
  • Unfortunately our data isn't in the best place and we have instances where infinite loops are caused (e.g. a is owner of b, b is owner of c and c is owner of a). There is a method on the HierarchyNode class that detects whether adding a child would cause an infinite loop.
  • One of the requirements is finding "unbroken" chains of ownership or control. I.e. in the structure of A > owner > B > controller > c > owner > D, the ownership chain would only be A > B.
  • The code creates one hierarchy per entity in order to be able to see the structure for a given entity easily at any time.

I am mostly interested in performance improvements (but welcome any comments), I have managed to get HierarchyWorker.Initialise to run in about 30 0.5 (I have edited the question with some improvements) seconds on our real dataset but I am sure there are more improvements to be made.

The data set I am working with involves about 30,000 entities and 125,000 connections. (I am not sure if providing this data would be helpful, if it would be what would be the best way/format to upload the data?)

\$\endgroup\$
  • 1
    \$\begingroup\$ You don't have to provide all this test data - this would be really to much - but it would be great if you could put another couple of lines together and add a small example with some fake data showing how to use this - like a really simple console app ;-) \$\endgroup\$ – t3chb0t Jul 23 '18 at 14:39
  • \$\begingroup\$ @t3chb0t I have added a console program to generate some test data. I have also updated the code with a few improvements I made this morning. \$\endgroup\$ – Jacob Regan Jul 24 '18 at 9:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.