Function list variable doesn't return the current state of a recursive variable

Question

I am working with a graph data structure and have a recursive function to calculate the depth of a node by counting the parents to the root node.

There are some other issues that I need to deal with, but for right now my main problem is to do with storing the current value of the recursive dictionary parameter, which stores the path branches.

using System;
using System.Collections.Generic;
using System.Linq;

public class Node {
    public string name;
    public int ID;
    public int maxDepth;
    public readonly List<Node> Dependencies = new List<Node>();
    public readonly List<Node> Children = new List<Node>();

    public bool isOrphan {
        get {
            return Dependencies.Count == 0;
        }
    }

    public bool isParent {
        get {
            return Children.Count != 0;
        }
    }
}

public class test {
    private static readonly List<Node> nodes = new List<Node>(); 
    public static void Main() {
        Node A = new Node() {
            name = "A",
            ID = 1
        };

        Node B = new Node() {
            name = "B",
            ID = 2
        };

        Node C = new Node() {
            name = "C",
            ID = 3
        };

        Node D = new Node() {
            name = "D",
            ID = 4
        };

        Node E = new Node() {
            name = "E",
            ID = 5
        };

        Node F = new Node() {
            name = "F",
            ID = 6
        };

        Node G = new Node() {
            name = "G",
            ID = 7
        };

        nodes.Add(A);
        nodes.Add(B);
        nodes.Add(C);
        nodes.Add(D);
        nodes.Add(E);
        nodes.Add(F);
        nodes.Add(G);

        A.Children.Add(B);
        A.Children.Add(G);
        B.Children.Add(C);
        B.Children.Add(D);
        C.Children.Add(D);
        D.Children.Add(E);
        E.Children.Add(F);

        B.Dependencies.Add(A);
        C.Dependencies.Add(B);
        D.Dependencies.Add(B);
        D.Dependencies.Add(C);
        E.Dependencies.Add(D);
        E.Dependencies.Add(G);
        F.Dependencies.Add(E);
        G.Dependencies.Add(A);

        foreach (Node n in nodes) {
            n.maxDepth = getMaxNodeDepth(n);
        }

        Console.ReadLine();
    }

    private static int getMaxNodeDepth(Node n, string listIndex = "base",
                    Dictionary<string, List<int>> paths = null) {
        bool firstIteration = false;

        if (paths == null) {
            firstIteration = true;
            listIndex = n.name.Replace(" ", "-");
            paths = new Dictionary<string, List<int>> {
                {listIndex, new List<int>(0)} 
            };
        }

        // Prevent the starting node from being added to the path
        if (!paths[listIndex].Contains(n.ID) && !firstIteration)
            paths[listIndex].Add(n.ID);

        // This variable should take the CURRENT path and store it; 
        // not the value after all the recursion has completed.
        // Right now, the current path is affected by the recursions, somehow...
        List<int> currentPath = new List<int>(paths[listIndex]);

        foreach (Node parent in n.Dependencies) {
            if (n.Dependencies.Count >= 2) {
                listIndex = parent.name;
                paths.Add(listIndex, currentPath);
            }
            getMaxNodeDepth(parent, listIndex, paths);
        }

        // Print out branches
        if (firstIteration) {
            string list = n.name + "\n";
            int listNumber = 1;
            foreach (List<int> iList in paths.Values) {
                list += string.Format("Branch#{0} -- ", paths.Keys.ElementAt(listNumber - 1));
                int total = 0;
                foreach (int i in iList) {
                    list += string.Format("{0}, ", nodes.First(x => x.ID == i).name);
                    total++;
                }
                listNumber++;
                list += string.Format(" -- ({0})\n", total);
            }
            Console.WriteLine(list);
        }

        // Order all paths by length, return the highest count
        // This is to be used to space out the hierarchy properly
        return paths.Values.OrderByDescending(path => path.Count).First().Count;
    }
}

When the foreach loop encounters a node with more than one parent, it creates a new branch and should populate it with the current IDs of the nodes.

C D \ / B | A | ...

What should happen

Using the above example, beginning with A, it will first iterate B, as its direct parent. Then it begins on B's parents, which it has two of and because of this, it creates a separate branch and should fill that branch with B and its children (until the starting node, this time being A).

What actually does

Somehow, when B has finished iterating over C, parent D polls the current path and is returned B, C, where it should actually be just B, as C is a sibling, not a direct child or parent.

Huge edit

The code I've attached runs completely out of the box and contains an example. You can see the result contains some anomalous results, such as

F Branch#G -- E, D, G, A, -- (4)

which should actually be

G Branch#G -- G, A, -- (2)

Answer 1

When you give a dictionary as a parameter to a method, the contents of the dictionary is not copied, only the reference to the dictionary is copied. So altering the dictionary in one recursion branch will change the dictionary for the other branch as well. To fix it, you can copy the dictionary explicitly yourself when passing the dictionary: getMaxNodeDepth(parent, listIndex, new Dictionary<string, List<int>>(paths));

EDIT: Actually that wouldn't be enough either since it will copy the reference to the inner list and not the contents of the inner list, so you'll need a more nested cloning code:

    private Dictionary<string, List<int>> clone(Dictionary<string, List<int>>  map)
    {
        Dictionary<string, List<int>> clone = new Dictionary<string,  List<int>>(map.Count);
        foreach (var pair in map)
        {
            clone[pair.Key] = new List<int>(pair.Value);
        }
        return clone;
    }

    //And then call it from your code:
    getMaxNodeDepth(parent, listIndex, clone(paths));

However, assuming you don't need to fill this paths dictionary for outside code, and the only output here is the "maximum depth" of the node, you can probably simplify your code a lot, for example:

private int getMaxNodeDepth(Node n)
{
     if (n.Dependencies == null || n.Dependencies.Count == 0) return 1;
     return 1 + n.Dependencies.Max(parent => getMaxNodeDepth(parent));
}

EDIT: edited to add a solution that returns the "maximum path" as well:

    private List<Node> getMaxNodeDepth(Node n)
    {
        List<Node> path =
            n.GetSubFolders().Select(getMaxNodeDepth).OrderByDescending(p => p.Count).
            FirstOrDefault() ?? new List<Node>();
        path.Insert(0, n);
        return path;
    }

EDIT: and based on the comment from the OP, here's a solution that returns all available paths:

    private static List<List<Node>> getAllPaths(Node n)
    {
        if (n.Dependencies == null || n.Dependencies.Count == 0)
            return new List<List<Node>> { new List<Node> { n }};
        List<List<Node>> allPaths = n.Dependencies.SelectMany(getAllPaths).ToList();
        allPaths.ForEach(path => path.Insert(0, n));
        return allPaths;
    }

    private static int getMaxDepth(Node n)
    {
        return getAllPaths(n).Max(p => p.Count);
    }