在逐步构建有向图的同时更有效地计算每个依赖项的传递闭包

Question

我需要回答这个问题：给定依赖图中的一个节点，将其依赖项按它们自己的传递依赖项分组，这些依赖项将受到特定起始节点的影响。

换句话说，给定依赖图中的一个节点，找到直接依赖集的集合，这些直接依赖集具有从该特定起始节点派生的共同依赖项。

例如给定伪代码：

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

你可以计算这个图：

如果我们使用 a 作为起始节点，我们可以看到 a 的依赖项，c 和 d 都有 [=21] 的依赖项=].并且 f 有 e 和 a 的依赖项。

注意a对b根本没有影响，所以在决定如何对a的家属进行分组时不应该考虑它。

使用 a 作为起始节点，我们想要得到这组依赖项：

groups = {{c, d}, {e, f}}

c和d有直接或传递的下游关系，e和f也有关系。但是，例如，e 和 f 与 c 或 d 没有任何直接或间接（传递）依赖（下游）关系。而且 b 不是直接或间接地从 a 派生出来的，所以它不应该对我们的分组产生任何影响。

另请记住，为简单起见，此图很小。可能传递依赖发生在子图的下方比这个例子碰巧有的更远。

我做了很多论文研究，确实有很多解决方案，但它们没有我正在寻找的性能特征。该图是随着时间的推移逐渐创建的，在每个阶段我都需要能够回答这个问题，因此每次遍历整个图都是一个破坏者。

我认为我有一个在我能找到的各种方法中都没有提到的主要优势：我可以完全控制图形的创建并且依赖项以反向拓扑顺序添加，因此图形是正确的排序。考虑到这一点，我考虑了增量计算答案的明显解决方案（动态规划）。

我认为位掩码是一种快速存储和查找给定节点所依赖的方法。当一个依赖项被添加到一个节点时，我会更新该节点的掩码以包含该依赖项的位（它本身包括它的依赖项等等）

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]
    });
  }
}

然而，依赖项需要以相反的顺序添加到图表中，以便图表正确排序并且图表的顶部包含其所有依赖项的掩码。

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);

位掩码将逐渐看起来像这样：

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

最后a有一个掩码01111101，每个位代表它的每个下游传递依赖。请注意，倒数第二位没有翻转，这是 b 的位，它根本不依赖于 a。

如果我们查看 a.dependents 的结果值，我们会看到：

[
  { values: [c, d], mask: 0b00110000 },
  { values: [e, f], mask: 0b01001100 }
]

里面提供了我们要找的答案，最终是一组集合。 a.dependents.map(group => group.values)--这是一个数组又名列表，但为简单起见，它被用作一个集合。

这是一个 JSBin：https://jsbin.com/jexofip/edit?js,console

这行得通，而且 CPU-wise 是可以接受的，因为我经常需要知道分组的家属，但家属的变化要少得多。

上面的示例使用JavaScript来简化演示，它使用32位有符号整数进行按位运算，因此我们只能创建31个唯一节点。我们可以使用任意精度整数（例如 BigInt）来创建 "unlimited" 个节点，但是 问题是内存使用。

因为每个节点都需要翻转自己唯一的位，所以我认为内存使用是：

N * (N + 1) / 2 = bits      (where N = number of nodes)

e.g. 10,000 nodes is about 6.25 megabytes!

这不包括使用任意精度整数（或类似的自定义数据结构）的任何平台开销。

在我的用例中，拥有 10k+ 是很常见的，实际上在某些情况下可能有 100k+ (625 MB !!!) 并且也有可能无限期地创建新节点，使用无限量的内存，所以这个解决方案不实用，因为没有简单的方法 "garbage collect" 不再使用从图上掉落的节点的掩码位——这当然是可能的，但这是我想要的传统 GC 问题尽可能避免。

旁注：根据图表的大小和深度，这实际上也可能表现不佳。尽管按位运算本身相对较快，但在图顶部的每个节点的 100,000 位 BigInt 上进行运算却不是这样。所以也欢迎完全重新考虑我的方法。

最终用内存换取 CPU 是通常的让步，但我想知道我是否错过了另一种可以达到更好平衡或需要更少内存的方法？

可能还有其他我没有想到的独特考虑因素可以使用。

给我上课！

Answer 1

如果是有向无环图，可以执行topological sorting of the nodes, and that seems like a good basis for subsequent steps. Toposorting itself can be done efficiently. There are implementations in FRP-inspired libraries such as my crosslink or paldepind's flyd

另外，查看 this answer。

Answer 2

您要分组的关系不是 equivalence relation。例如，考虑这个依赖关系图：

这里，b和c有共同的依赖，c和d，但是b和d之间没有共同依赖。在这种情况下，您可能希望在同一组中包含 b、c 和 d。但是，这种情况会变得更加棘手：

这里，a不依赖于c，所以你可能想要b 和 d 在不同的组中，现在您不需要关心 c。但是，在这种情况下，有一种 class 算法会将 b 和 d 组合在一起： algorithms which maintain grouping of 所有个节点，并以此为基础对新节点的直系后代进行分组。

其中一种算法使用 disjoint-set structure 来有效地跟踪连接了哪些节点。在我的示例中，在处理 a 之前，算法将具有节点 b、c、d, e, 和f 都在同一个集合中，所以将它们放在一起。

这是一个实现：

function find(node) {
  return node.parent == null ? node : (node.parent = find(node.parent));
}

function merge(a, b) {
  a = find(a);
  b = find(b);
  if (a.rank < b.rank) {
    a.parent = b;
  } else {
    b.parent = a;
    if (a.rank == b.rank) {
      ++a.rank;
    }
  }
}

class Node {
  constructor(name, dependents) {
    this.name = name;
    this.parent = null;
    this.rank = 0;
    let depMap = new Map();
    for (let d of dependents) {
      let dset = find(d);
      if (!depMap.has(dset)) {
        depMap.set(dset, []);
      }
      depMap.get(dset).push(d);
    }
    output += name + ': ' + Array.from(depMap.values()).map(a => '{' + a.join(', ') + '}').join(', ') + '\n';
    for (let d of depMap.keys()) {
    // or: for (let d of dependents) {
      merge(this, d);
    }
  }

  toString() {
    return this.name;
  }
}

let output = '';
const f = new Node('f', []);
const e = new Node('e', [f]);
const d = new Node('d', []);
const c = new Node('c', [d]);
const b = new Node('b', [d]);
const a = new Node('a', [b, c, e, f]);
document.getElementById('output').textContent = output;

<pre id=output></pre>

Answer 3

将每个节点的 'reachable' 节点存储为位掩码并执行按位 AND 当然听起来很难在计算上击败。如果此问题的主要问题是高内存使用率，那么这可能被视为内存压缩问题。

如果位掩码非常稀疏（很多零），它们有可能会压缩到更小的尺寸。

我想您会想要找到一个可以将位掩码解压缩为流的压缩库。这样您就可以在解压缩时执行按位 AND - 从而避免存储完全解压缩的位掩码。

在逐步构建有向图的同时更有效地计算每个依赖项的传递闭包

More efficiently compute transitive closures of each dependents while incrementally building the directed graph

graph-theory

dataflow

directed-graph

transitive-closure

transitive-dependency