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

发布于 2024-07-14 03:16:32 字数 935 浏览 9 评论 0原文

我正在寻找一种算法来“反转”（反转？从里到外？） 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，我可以通过它映射每个节点第一棵树到第二棵树的“镜像”（以及后面再次）为我的查询规则提供更多的导航灵活性。）

原文

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

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       #

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.

(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.)

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

耳钉梦 2024-07-21 03:16:32

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

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

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

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

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.

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.

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

回复收藏 0 原文

丶情人眼里出诗心の 2024-07-21 03:16:32

只需在您已经去过的地方进行深度优先搜索标记，每次遍历箭头时，都会将相反的方向添加到结果 DAG 中。添加叶子作为根。

回复收藏 0 原文

迷乱花海 2024-07-21 03:16:32

我的直觉建议是对图进行深度优先遍历，并同时构建镜像图。

遍历每个节点时，在镜像图中创建一个新节点，并在新图中在该节点与其前任节点之间创建一条边。

如果在任何时候您到达一个没有子节点的节点，请将其标记为根。

回复收藏 0 原文

痴者 2024-07-21 03:16:32

我通过简单的图形遍历解决了这个问题。请记住，拓扑排序仅对有向无环图有用。

我使用了邻接列表，但您可以使用邻接矩阵执行类似的操作。

在 Python 中，它看起来像这样：

# Basic Graph Structure
g = {}
g[vertex] = [v1, v2, v3] # Each vertex contains a lists of its edges

要找到 v 的所有边，然后遍历列表 g[v]，这将给出所有 (v, u) 边。

要构建反向图，请创建一个新字典并构建如下所示的内容：

    reversed = {}
    for v in g:
        for e in g[v]:
            if e not in reversed:
                reversed[e] = []
            reversed[e].append(v)

对于大型图来说，这非常耗费内存（使内存使用量加倍），但这是一种非常简单的处理它们的方法，而且速度相当快。可能有更聪明的解决方案，涉及构建生成器和使用某种 dfs 算法，但我没有对此进行太多思考。

I solved this with a simple graph traversal. Keep in mind topological sorting will only be useful for directed acyclic graphs.

I used an adjacency list, but you can do a similar thing with an adjacency matrix.

In Python it looks like this:

# Basic Graph Structure
g = {}
g[vertex] = [v1, v2, v3] # Each vertex contains a lists of its edges

To find all the edges for v, you then traverse the list g[v] and that will give you all (v, u) edges.

To build the reversed graph make a new dictionary and build it something like this:

    reversed = {}
    for v in g:
        for e in g[v]:
            if e not in reversed:
                reversed[e] = []
            reversed[e].append(v)

This is very memory intensive for large graphs (doubling your memory usage), but it is a very easy way to work with them and quite quick. There may be more clever solutions out there involving building a generator and using a dfs algorithm of some sort, but I have not put a lot of thought into it.

回复收藏 0 原文