# How to improve this algorithm for building a graphs closures

We have a large directed acyclic graph and a requirement to filter it by allowing a user to select certain nodes and then we remove all nodes that are not selected nodes, ancestors of those nodes, or descendants of those nodes.

As you can see in the above image nodes 6 and 9 have been selected and so nodes which do not route to those nodes are removed.

We are trying to build the closures (transitive closures?) of the graph so we can quickly filter it. We used the below code which was very slow. Profiling it shows around half of the time is spent in garbage collection.

public static class NodeClosureAnalyser
{
public static NodeClosures Analyse(Node root)
{
var results = new NodeClosures
{
AncestorClosures = new Dictionary<int, HashSet<int>>(),
DescendantClosures = new Dictionary<int, HashSet<int>>()
};
//walk the tree and build the closures lists
var stack = new Stack<Node>();
stack.Push(root);

var route = new Stack<Node>();

while (stack.Count != 0)
{
var current = stack.Pop();
//keep track of the route to root
while (route.Any() && !route.Peek().Children.Any(n => n.Id == current.Id))
{
route.Pop();
}
route.Push(current);

foreach (var child in current.Children)
{
stack.Push(child);
}
}
return results;
}

private static void AddNodeRelationships(NodeClosures results, Node current, IEnumerable<Node> route)
{
foreach (var node in route)
{
}
}
}

public struct NodeClosures
{
public Dictionary<int, HashSet<int>> AncestorClosures { get; set; }
public Dictionary<int, HashSet<int>> DescendantClosures { get; set; }
}

public static class DictionaryExtension
{
public static HashSet<int> GetOrCreateValuesList(
this IDictionary<int, HashSet<int>> dictionary, int key)
{
HashSet<int> ret;
if (!dictionary.TryGetValue(key, out ret))
{
ret = new HashSet<int>(new List<int>());
dictionary[key] = ret;
}
return ret;
}
}


A program with tests to demonstrate the issue is available on Github

Many thanks for any input!

Since your nodes are double-linked (i.e. each has a list of all parents and children), creating the list of closures for all children of a certain node (especially the root node) seems like an overkill, especially if you're doing that whenever you start to filter. If you have a doubly linked graph, descendant and ancestor lists seem pretty cheap to get for each node, and for a large graph you will have to waste an awful lot of memory to keep them around.

If I am not mistaken, for each "chosen" node, you need to mark that node as safe, mark its children as safe, then traverse back to the root and mark all nodes you encounter as safe, and finally remove all non marked nodes. That should be much less work than you're doing now, if I didn't misunderstand the problem completely.

Some minor issues:

1. To merge two HashSets, it's much cheaper to use HashSet.UnionWith, than to create a new HastSet each time (like you're doing in your Filter method).

2. Btw, by looking at your code, it seems that Node.AnyDescendant should iterate through Children, not Parents.

I.e. wouldn't this work:

public static Node Filter(Node startNode, IEnumerable<int> includedNodes)
{
var explicitlyIncludedNodes = startNode
.Descendants()
.Where(n => includedNodes.Contains(n.Id));

var nodesToKeep = new HashSet<int>();
foreach (var node in explicitlyIncludedNodes)
{
nodesToKeep.UnionWith(node.Ancestors().Select(n => n.Id));
nodesToKeep.UnionWith(node.Descendants().Select(n => n.Id));
}

}


Ancestors() should simply return all ancestors all the way to the root:

public IEnumerable<Node> Ancestors()
{
var stack = new Stack<Node>();
stack.Push(this);
while (stack.Count != 0)
{
var current = stack.Pop();
yield return current;

foreach (var child in current.Parents)
stack.Push(child);
}
}


(Descendants the same way but for Children instead of Parents)

Expanding on Groo's answer a bit. One classic solution to this problem which avoids building temporary node sets is to add a Tag to your Node class. For simplicities sake lets say we make it a Guid

class Node
{
...
public Guid Tag { get; set; }
...
}


Then your problem can be solved by traversing the graph and tagging interesting nodes:

private Guid TagReachableNodes(IEnumerable<Node> selectedNodes)
{
var tag = Guid.NewGuid();
foreach (var node in selectedNodes)
{
node.Tag = tag;
TagChildren(node, tag);
TagParents(node, tag);
}
return tag;
}

private void TagChildren(Node node, Guid tag)
{
foreach (var child in node.Children)
{
child.Tag = tag;
TagChildren(child, tag);
}
}

private void TagParents(Node node, Guid tag)
{
// assuming root has an empty Parents list
foreach (var parent in node.Parents)
{
parent.Tag = tag;
TagParents(parent, tag);
}
}


And then you can simply remove all nodes which don't match the tag. That said I didn;t fully comprehend the BreadthFirstDeletion algorithm you have implemented. From what I understand removing a node is:

• Removing it from the Children collection of all it's parent AND
• Removing it from the Parents collection of all its children

Should be something like this:

void RemoveUntaggedNodes(Node root, Guid tag)
{
var stack = new Stack<Node>();
stack.Push(root);
while (stack.Count > 0)
{
var current = stack.Pop();
foreach (var child in current.Children)
{
stack.Push(child);
}
if (current.Tag != tag)
{
foreach (var parent in current.Parents)
{
parent.RemoveChild(current);
}
foreach (var child in current.Children)
{
child.RemoveParent(current);
}
}
}
}


In total your removal algorithm would then be:

void RemoveUnreachableNodes(IEnumerable<Node> selectedNodes)
{
var tag = TagUnreachableNodes(selectedNodes);
RemoveUntaggedNodes(root, tag);
}


Note that with the tagging approach you can't have multiple traversals running in parallel (although you could parallelize the tagging traversal itself)

• This approach has a persistent overhead (16 bytes per node in your case) besides the problems you have already mentioned. You can achieve the same with ConditionalWeakTable'2, but I'm not sure about performance in this case. Commented Nov 19, 2016 at 8:12