求算法反转（反转？镜像？转内到外的）一个DAG [英] Seeking algorithm to invert (reverse? mirror? turn inside-out) a DAG

问题描述

我在寻找一种算法为反转（反向？转内到外的？）一 DAG：

I'm looking for an algorithm to "invert" (reverse? turn inside-out?) a 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

我正在使用的重presentation是不可变的一个真正的DAG（有没有 父指针）。我想遍历图形以某种方式 同时建立一个镜像图与等效节点，但与 反转节点之间关系的方向。

The representation I'm using is immutable truly a DAG (there are no "parent" pointers). I'd like to traverse the graph in some fashion while building a "mirror image" graph with equivalent nodes, but with the direction of relations between nodes inverted.

         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我的意思是一个节点 没有进入的参考。叶是一个没有传出节点 参考。）

So the input is a set of "roots" (here, {A}). The output should be a set of "roots" in the result graph: {G, F}. (By root I mean a node with no incoming references. A leaf is a node with no outgoing references.)

输入的成为输出和签证的叶根 反之亦然。转变应该是本身的逆

The roots of the input become the leaves of the output and visa versa. The transformation should be an inverse of itself.

（对于好奇，我想一个功能添加到我使用到库 再present XML的结构查询通过它我可以映射中的每个节点 第一棵树在第二树中的镜像（和背 再次）为我的查询规则的详细导航灵活性。）

(For the curious, I'd like to add a feature to a library I'm using to represent XML for structural querying by which I can map each node in the first tree to its "mirror image" in the second tree (and back again) to provide more navigational flexibility for my query rules.)

推荐答案

遍历图形构建一套颠倒边和叶节点的列表。

Traverse the graph building a set of reversed edges and a list of leaf nodes.

执行拓扑排序使用叶（其现在根）节点开始与反向边缘。

Perform a topological sort of the reversed edges using the leaf (which are now root) nodes to start with.

构建基于从已排序列表的末尾开始逆转边缘反转图形。由于节点反向拓扑为了构造，保证您构建节点，所以创建一个不变的再presentation可能之前已经构建了一个给定节点的孩子。

Construct the reversed graph based on the reversed edges starting from the end of the sorted list. As the nodes are constructed in reverse topological order, you are guaranteed to have constructed the children of a given node before constructing the node, so creating an immutable representation is possible.

这或者是O（N），如果你使用结构的中间再presentation其跟踪与节点，或O（NlnN）相关联的，如果您使用排序找到的所有链接两个方向上的所有链接节点。对于小图，或语言不堆栈溢出痛苦，你可以构造图懒洋洋的，而不是明确地执行拓扑排序。所以，这取决于你正在实现这一切多么不同，这将是一点点。

This is either O(N) if you use structures for your intermediate representation which track all links in both directions associated with a node, or O(NlnN) if you use sorting to find all the links of a node. For small graphs, or languages which don't suffer from stack overflows, you can just construct the graph lazily rather than explicitly performing the topological sort. So it depends a little what you're implementing it all in how different this would be.

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

这篇关于求算法反转（反转？镜像？转内到外的）一个DAG的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！