寻求算法反转(反向镜像？从里到外翻转)DAG

我正在寻找一种算法来"反转"(反向？从里到外翻？)一个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}.(按root用户是指没有传入引用的节点.叶子是没有传出引用的节点.)

输入的根源成为输出的叶子,反之亦然.转型应该是自身的逆转.

(对于好奇的人,我想在我用来表示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