C# Data structure to store items in a hierarchical way that once a branch is built, it allows me to retrieve it and add it as part of another one

Question

I'm struggling with a problem in which I have to find a way to store all the possible paths a program might follow. Take this image as an example.

In that image each number represents a complex process that might call other processes to execute itself, describing all the paths you can see in the image.

All the continuous lines represent paths that the process necessarily has to follow, while the dashed lines represent paths that are optional.

Knowing the execution starts from left to right and from top to bottom, one must always keep in mind that if a branch has already been built it must be reused and never rebuilt again.

In this another image for example the yellow line represents all the paths that were follow during the execution of process number 37.

In it you can see that the path starting with the process 18 (18->17->16) was previously built and so when process 19 is reached it shouldn't be rebuilt as all these processes take quite some time and it'd be a waste of time to try to build them again already knowing the results they produced. Instead, if a certain number in found to have been built previously (e.g process 18) it should be copy/attached to the process that called it (process 19 in the image). All this is for a log in which I have to store all the paths complete, that's why I mention the part of copying/reusing branches as I'll later have to query that log to display all these paths.

To execute all these process currently a recursive process is used, but since it doesn't consider that it can reuse paths that were previously build, the whole thing takes ages.

Do you know of any data structure that might help me optimize this process so that if a process was already executed it is only reused. As for the log, as I mentioned above I need to store the complete paths.

Any ideas or resources would be highly appreciated.

Thanks

Edit 1

----------------------------

One thing that perhaps I didn't make very clear, is that the data struture I need to create has two purposes:

1. To keep track of all the paths that the main process (37 in the example) followed during its execution,giving me the chance to tell at any time if a certain path was already followed, being able to then copy that path to the node that was supposed to called it (in the example, copying the whole branch: 18->17->16 to process 19.
2. By, giving me the opportunity to tell whether a path is already in this data structure or not, I can avoid executing subprocesses that were already executed and which results are known and with that, optimizing the whole proccess of execution.

Edit 2

----------------------------

Regarding the question about why I didn't consider using a Dictionary, well I had that idea at first, but then I couldn't find a way that I dictionary could tell me ,for example, that the path starting with 18 (18->17->16) descends from both process 37 and 19. You see, a node can have one or more parents. How could I express that with a Dictionary?

Answer 1

I believe this is the data structure that you're looking for:

var paths = new Dictionary<int, HashSet<int>>()
{
    { 37, new HashSet<int>() { 18, 33, 34, 35, 36, } },
    { 18, new HashSet<int>() { 17, } },
    { 33, new HashSet<int>() { } },
    { 34, new HashSet<int>() { 19, 17, 15, } },
    { 35, new HashSet<int>() { 17, } },
    { 36, new HashSet<int>() { } },
    { 17, new HashSet<int>() { 16, } },
    { 19, new HashSet<int>() { 12, 18, } },
    { 15, new HashSet<int>() { 14, } },
    { 16, new HashSet<int>() { } },
    { 12, new HashSet<int>() { 11, } },
    { 14, new HashSet<int>() { } },
    { 11, new HashSet<int>() { } },
};

Here's the code to add a path to the paths:

public bool TryAddPath(Dictionary<int, HashSet<int>> paths, int x, int y)
{
    if (!paths.ContainsKey(x))
    {
        paths[x] = new HashSet<int>() { };
    }

    if (!paths[x].Contains(y))
    {
        paths[x].Add(y);
        if (!paths.ContainsKey(y))
        {
            paths[y] = new HashSet<int>() { };
        }
        return true;
    }
    return false;
}

The data structure above can be built by:

var paths = new Dictionary<int, HashSet<int>>();
var results = new bool[]
{
    TryAddPath(paths, 37, 18),
    TryAddPath(paths, 37, 33),
    TryAddPath(paths, 37, 34),
    TryAddPath(paths, 37, 35),
    TryAddPath(paths, 37, 36),
    TryAddPath(paths, 18, 17),
    TryAddPath(paths, 17, 16),
    TryAddPath(paths, 34, 19),
    TryAddPath(paths, 34, 17),
    TryAddPath(paths, 34, 15),
    TryAddPath(paths, 19, 12),
    TryAddPath(paths, 19, 18),
    TryAddPath(paths, 12, 11),
    TryAddPath(paths, 18, 17),
    TryAddPath(paths, 17, 16),
    TryAddPath(paths, 17, 16),
    TryAddPath(paths, 15, 14),
    TryAddPath(paths, 35, 17),
    TryAddPath(paths, 17, 16),
};

This returns the array { true, true, true, true, true, true, true, true, true, true, true, true, true, false, false, false, true, true, false, } which shows the paths that didn't need to be processed.

To then get a way to backtrack up the list do this:

ILookup<int?, int> parents =
    paths
        .Keys
        .AsEnumerable()
        .SelectMany(
            k => paths[k].Select(x => (int?)x).DefaultIfEmpty(),
            (k, v) => new { k, v })
        .ToLookup(x => x.v, x => x.k);

Now I can ask parents[17] and I get { 18, 34, 35, } returned. I can even do parents[null] and I get back { 33, 36, 16, 14, 11, } which shows the nodes that are leaves.

Answer 2

Use two data structures. It seems that you're already using a tree that you traverse to find the next node that you need to process; that's fine, keep that tree. But also create a new data structure such as a Dictionary to keep track of the already-processed nodes, allowing you to quickly look up a node by its ID and see the results of previous computations of it.

Answer 3

To eloborate on my comment of simply using a List here is what I meant (partial):

void Main()
{
  var data = new Dictionary<int, List<int[]>>();

  data.Add(16, new List<int[]> {
    new int[]{ 37, 18, 17, 16 },
    new int[]{ 37, 34, 19, 18, 17, 16 },
    new int[]{ 37, 34, 17, 16 },
    new int[]{ 37, 35, 17, 16 }});

  data.Add(17, new List<int[]> {
    new int[]{ 37, 18, 17 },
    new int[]{ 37, 34, 17 },
    new int[]{ 37, 35, 17 }});


  data.Add(18, new List<int[]> {
    new int[]{ 37, 18 },
    new int[]{ 37, 34, 19, 18 } });

  var node35_IsAncestorOf = data
    .Where(d => d.Value.Any(v => v.Contains(35)))
    .Select( d => d.Key);   

  node35_IsAncestorOf.Dump();    // LinqPad
}

Also this structure is like a directory structure where 16, 17 etc are NodeText and not NodeId so a tree structure would work (like a filename could exist with the same name under different directories).

PS: At database level, this looks like a graph database like Neo4j, OrientDb, VelocityGraph ... Most of them are opensource if you want to check their data structures.