algorithm - 寻求反转(反转？镜像？从里到外)DAG 的算法

Question

我正在寻找一种算法来“反转”(反转？从里到外？)有向图:

       A*      # I can't ascii-art the arrows, so just
      / \      # pretend the slashes are all pointing
     B   C     # "down" (south-east or south-west)
    /   / \    # e.g. 
   G   E   D   # A -> (B -> G, C -> (E -> F, D -> F))
        \ /
         F

我使用的表示是不可变的真正的 DAG(没有“父”指针)。我想以某种方式遍历图表在构建具有等效节点的“镜像”图时，但是节点间关系方向倒转。

         F*
        / \
   G*  E   D   # F -> (E -> C -> A, D -> C -> A), G -> B -> A
    \   \ /    # 
     B   C     # Again, arrows point "down"
      \ /      # 
       A       # 

所以输入是一组“根”(这里是{A})。输出应该是结果图中的一组“根”:{G, F}。 (根我的意思是一个节点没有传入的引用。叶子是没有出站的节点引用资料。)

输入的根成为输出的叶子和签证反之亦然。转换应该是其自身的逆。

(出于好奇，我想向我正在使用的库添加一个功能表示用于结构查询的 XML，我可以通过它映射每个节点第一棵树到它在第二棵树中的“镜像”(然后返回再次)为我的查询规则提供更多的导航灵 active 。)

Answer 1

遍历图形构建一组反向边和叶节点列表。

使用叶(现在是根)节点开始对反向边执行拓扑排序。

根据从排序列表末尾开始的反转边构造反转图。由于节点是按反向拓扑顺序构造的，因此可以保证在构造节点之前已经构造了给定节点的子节点，因此可以创建不可变表示。

如果您将结构用于跟踪与节点关联的两个方向上的所有链接的中间表示，则这是 O(N)，或者如果您使用排序来查找节点的所有链接，则为 O(NlnN)。对于小型图或不受堆栈溢出影响的语言，您可以延迟构建图而不是显式执行拓扑排序。因此，这在一定程度上取决于您正在实现的内容，这会有多不同。

A -> (B -> G, C -> (E -> F, D -> F))

original roots: [ A ]
original links: [ AB, BG, AC, CE, EF, CD, DF ] 
reversed links: [ BA, GB, CA, EC, FE, DC, FD ]
reversed roots: [ G, F ]
reversed links: [ BA, CA, DC, EC, FE, FD, GB ] (in order of source)
topologically sorted: [ G, B, F, E, D, C, A ]
construction order : A, C->A, D->C, E->C, F->(D,E), B->A, G->B