9

我创建了一个轻量级图形库，它有 3 个对象（顶点、边缘、图形）和 1 个函数（topo_sort），如下所示：

class DAGError(Exception): pass

def topo_sort(graph):
    sorted_list = []
    def visit(vertex):
        nonlocal sorted_list
        if vertex.idle:
            raise DAGError('Graph has at least one cycle.')
        if not vertex.done:
            vertex.idle = True
            for neighbor in vertex.vertices():
                visit(neighbor)
            vertex.done = True
            vertex.idle = False
            sorted_list.insert(0, vertex)
    queue = [vertex for vertex in graph.vertices() if not vertex.done]
    while queue:
        visit(queue.pop(0))
    return iter(sorted_list)

如果我有一个扁平的 DAG，这可以正常工作。但我想要实现的是在我的主图中添加子图（或嵌套图），正如你在我绘制的插图中看到的那样：

嵌套/子图说明

这仍然是一个 DAG，所以如果我对此运行我的函数，正常 topo_sort输出将是这样的：

V0, V3, V1, V5, V4, V8, V7, V12, V11, V13, V14, V2, V6, V10, V9, V15, V17, V16

然而，我的首选输出是当子图所依赖的所有顶点在处理子图的顶点之前“处理”时 - 所以它应该是这样的：

V0, V1, V8,        # vertices of maingraph
V3, V5, V4, V12    # vertices of subgraph_0
V7, V11, V13,      # vertices of subgraph_1
V14                # vertex   of subgraph_0
V2                 # vertex   of maingraph
V6, V10, V9, V15   # vertices of subgraph_2
V16, V17           # vertices of maingraph

但我找不到任何资源：

  • 如何将图中的顶点“标记”或“存储”为子图的一部分？
  • 如何根据顶点的子图依赖关系对顶点进行排序（如上面的示例）？
  • 如何将子图作为独立图获取或处理？

我希望我能足够详细地解释我的问题——尽管如果有什么遗漏，请告诉我，我会用遗漏的部分来扩展我的问题。

提前致谢！

编辑：

我发现了这个（Boost Graph Library，BGL），它看起来解决了我遇到的一个非常相似（或完全相同？）的问题，虽然我不熟悉 C++，所以我不明白它是怎么回事工作以及它到底在做什么——但我把它放在这里，也许有人会发现回答我的问题很有帮助..

编辑2：

我也接受伪代码，而不仅仅是 python！当然，如果现有的 python 库知道这一点，我对此很感兴趣，但是，我不想使用如此庞大的库graph-tools，例如——这就是我创建自己的库的原因，所以我更喜欢实现而不是库。

4

2 回答 2

2

对你来说可能有点晚了，但对于其他有类似问题的人来说：

如何将图中的顶点“标记”或“存储”为子图的一部分？

为什么不只给顶点对象一个属性，该属性subgraph包含一个整数或一个字符串标签，该属性标记顶点所属的子图？（如果要使用 NetworkX，请使用节点属性字典）这样，您可以在排序算法中检查此子图属性。

如何根据顶点的子图依赖关系对顶点进行排序（如上面的>示例）？

我不是拓扑排序方面的专家，但假设每个顶点“知道”它所属的子图，这就是我想出的（使用 NetworkX，但您可以轻松实现我在您自己的库中使用的部分）：下面的代码收集了您描述的所有“依赖项”（所有需要在当前顶点之前出现的顶点）。您可以使用此信息来修改您的 topol_sort() 函数，如果不是其依赖项中的所有顶点都已经在列表中，它只会将当前顶点附加到列表中。

import networkx as nx

# define the graph and the subgraphs suitable for NetworkX
G = ...
subgraphs = ...

for subgraph in subgraphs:
    # find all vertices that the current subgraph depends on
    dependencies = set()
    for vertex in subgraph:
        anc = nx.ancestors(G, vertex) # anc is the set of all vertices having a path to 'vertex'
        dependencies.union(anc)
    dependencies -= subgraph.nodes()
    # store these dependencies under every vertex of the current subgraph
    for vertex in subgraph:
        G[vertex].node['depends'] = dependencies

# run modified topological sorting
topo_sort_mod(G)

如何将子图作为独立图获取或处理？

我不确定你到底想要什么。也许这会有所帮助（再次使用 NetworkX），尤其是这一部分：

要创建具有自己的边/节点属性副本的子图，请使用：nx.Graph(G.subgraph(nbunch))

如果边缘属性是容器，则可以使用以下方法获得深拷贝： G.subgraph(nbunch).copy()

我希望这对任何人都有帮助...... :)

于 2015-02-26T11:01:03.193 回答
0

阅读您关于 Graph-tools 的声明，但仍然不确定您是否喜欢使用库来完成某项工作，或者您想了解如何自己编写它。

也许你看

General Samples
[http://networkx.github.io/examples.html][1]

DAG Example
[http://networkx.lanl.gov/archive/networkx-1.6/_modules/networkx/algorithms/dag.html][2]

看看它是否可以帮助您解决问题？

于 2013-08-19T15:10:55.877 回答