More efficiently compute transitive closures of each dependents while incrementally building the directed graph
I need to answer the question: given a node in a dependency graph, group its dependents by their own transitive dependents which would be impacted by a particular start node.
In other words, given a node in a dependency graph, find the set of sets of direct dependents which transitively have common dependents that derive from that particular starting node.
e.g. given the pseudo code:
let a = 1
let b = 2
let c = a + b
let d = a + b
let e = a
let f = a + e
let g = c + d
You could compute this graph:
If we used a as the start node we can see that of the dependents of a, both c and d have a dependent of g. And f has a dependent of e and a.
Notice that a has no impact on b at all, so it should not be taken into account when deciding how to group the dependents of a.
Using a as the start node, we'd want to get this grouped sets of dependents:
groups = {{c, d}, {e, f}}
c and d have direct or transitive downstream relations, and e and f together as well. But, for example, e and f have no dependent (downstream) relation at all with c or d either directly or indirectly (transitively). And b doesn't derive from a directly or indirectly, so it should not have any impact on deciding our grouping.
Also keep in mind that this graph is small for simplicity. It could be that transitive dependents happen much further down the subgraph than this example happens to have.
I did a bunch of paper research and indeed there are numerous solutions, however they don't have the performance characteristics I'm looking for. The graph is incrementally created over time, and at each stage I need to be able to answer this question so traversing the entire graph each time is a dealbreaker.
I think I have a major advantage that isn't referenced in the various approaches I could find: I have full control over the creation of the graph and the dependents are added in reverse topological order, so the graph is correctly sorted. With that in mind, I considered the obvious solution of computing the answer incrementally (dynamic programming).
I figured a bitmask would be a fast way to store and look up what dependents a given node has. When a dependent is added to a node, I would update that node's mask to include the bits of that dependent (which itself includes its dependents and so on)
let maskCounter = 0;
class Node {
constructor(name) {
this.name = name;
this.dependents = [];
this.mask = 1 << maskCounter;
maskCounter++;
}
addDependent(dependent) {
// Now our mask contains the bits representing all of
// its direct and transitive dependents
this.mask = this.mask | dependent.mask;
// Need to see if this dependent has a transitive
// dependent of its own that exists in one of the groups
for (const group of this.dependents) {
const result = group.mask & dependent.mask;
if (result) {
group.mask |= dependent.mask;
group.values.push(dependent);
return;
}
}
// If reached, this dependent has no transitive dependents
// of its own with any of this node's other dependents.
// That's confusing, huh?
this.dependents.push({
mask: dependent.mask,
values: [dependent]
});
}
}
The dependents would, however, need to be added in reverse order up the graph so that the graph sorted correctly and the top of the graph contains the masks of all its dependents.
const a = new Node('a');
const b = new Node('b');
const c = new Node('c');
const d = new Node('d');
const e = new Node('e');
const f = new Node('f');
const g = new Node('g');
b.addDependent(c);
b.addDependent(d);
c.addDependent(g);
d.addDependent(g);
e.addDependent(f);
a.addDependent(c);
a.addDependent(d);
a.addDependent(e);
a.addDependent(f);
The bitmasks would incrementally look like this:
b = b 00000010 | c 00000100
b = b 00000110 | d 00001000
c = c 00000100 | g 01000000
d = d 00001000 | g 01000000
e = e 00010000 | f 00100000
a = a 00000001 | c 01000100
a = a 01000101 | d 01001000
a = a 01001101 | e 00110000
a = a 01111101 | f 00100000
===========================
a = 01111101
At the end a has a mask of 01111101, each bit represents each of its downstream transitive dependents. Notice that the second to last bit is not flipped, that's the bit for b which does not depend on a at all.
If we look at the resulting value of a.dependents we see:
[
{ values: [c, d], mask: 0b00110000 },
{ values: [e, f], mask: 0b01001100 }
]
which provides the answer we're looking for, ultimately a set of sets. a.dependents.map(group => group.values)--this an array aka list but it's being used as a set for simplicity.
Here's a JSBin: https://jsbin.com/jexofip/edit?js,console
This works, and CPU-wise is acceptable because I'll very frequently need to know the grouped dependents but dependents change far less often.
The example above uses JavaScript for simplicity of demo, which uses 32-bit signed integers for bitwise operations so we can only create 31 unique nodes. We could use an arbitrary precision integer (e.g. BigInt) to create a "unlimited" number of nodes, but the problem is memory usage.
Because each node needs their own unique bit flipped, I think the memory usage is:
N * (N + 1) / 2 = bits (where N = number of nodes)
e.g. 10,000 nodes is about 6.25 megabytes!
That's excluding any platform overhead for using arbitrary precision integers (or a similar custom data structure).
In my use case, it would be common to have 10k+ and in fact 100k+ is probable in some cases (625 MB !!!) and it's also possible for new nodes to be created indefinitely, using an infinite amount of memory, so this solution isn't practical because there is no easy way to "garbage collect" no longer used mask bits from nodes that drop off the graph--it's of course possible, but it's the traditional GC problem I'd like to avoid if possible.
Side note: depending on the size and depth of the graph, this might not actually perform well either. Even though bitwise operations themselves are relatively fast, doing it on on a BigInt of 100,000 bits for each node at the top of the graph is not. So completely rethinking my approach is also welcome.
Ultimately trading memory for CPU is the usual give and take, but I'm wondering if perhaps I'm missing another approach that strikes a better balance or requires significantly less memory?
There may be other unique considerations I haven't thought of that could be used.
School me!
Storing the 'reachable' nodes for each node as a bitmask and doing a bitwise AND certainly sounds hard to beat computationally. If the main issue with this is the high memory usage then perhaps this could be seen as a memory compression issue.
If the bitmasks are very sparse (lots of zeros) there is a chance they will compress down to a much smaller size.
I image you'll want to find a compression library that could de-compress the bitmasks as a stream. That way you could do the bitwise AND as it decompresses - allowing you to avoid storing the fully decompresses bitmask.