寻求反转（反转？镜像？翻转）DAG 的算法

我正在寻找一种算法来“反转”（反转？从里到外？） 有向无环图：

       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，我可以通过它映射每个节点 第一棵树到第二棵树的“镜像”（以及后面 再次）为我的查询规则提供更多的导航灵活性。）

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

首先使用叶节点（现在是根节点）对反向边执行拓扑排序。

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

如果您使用跟踪与节点关联的两个方向上的所有链接的中间表示结构，则为 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