图的遍历与Networkx（蟒蛇）(Graph traversal with Networkx (P

我打了一下，用Networkx管理依赖性的曲线图。 比方说，我有这个图表，每个字母代表一个服务器

>>> G = nx.Graph()
>>> G.add_edge("A","B")
>>> G.add_edge("A","H")
>>> G.add_edge("H","C")
>>> G.add_edge("B","C")
>>> G.add_edge("B","D")

           A
         /   \
       H       B
     /        /  \
   C         C     D 

所以在这里我们可以看到，一开始之前，我们需要开始H和B和开始^ h我们需要开始C，然后到入门C凌晨必要启动C和d

通过摆弄了一下与Networkx我发现我可以通过做一个DFS遍历

print nx.dfs_successors(G,"A")
{A:[H,B], H:[C], B:[D] }

但是我有这种方法的问题。 正如你可以看到，当有在树上有两个相同的字母，Networkx只选择了把他们中的一个在最终结构（这是正确的），但我需要有完整的结构如何可以强制Networkx在结构B添加：[d，C] ??

我想精确，通过做

>>> nx.dfs_successors(G,"B")
{'B': ['C', 'D']}

所以，一切都是“内部”是正确的，它只是显示它不是我希望的方式dfs_successors。

谢谢

Answer 1:

以你的代码，你的图不出来，你会期望。 如果你这样做：

import pylab as p
import networkx as nx

G = nx.Graph()
G.add_edge("A","B")
G.add_edge("A","H")
G.add_edge("H","C")
G.add_edge("B","C")
G.add_edge("B","D")

nx.draw(G)
p.show()

你会看到你的曲线图：

这是由于逻辑G.add_edge("A", "B")

1. 如果G没有ID为“A”的节点，添加它。
2. 如果G没有ID为“B”的节点，添加它。
3. 连接“A”至“B”用新的边缘。

因此，你只能创建五个节点，而不是六个在画面中。

编辑 Networkx可以采取任何可哈希值作为对于一个节点，并在图中它用STR（节点）来标记每个圆。 因此，我们可以简单地定义我们自己的节点类（您也许要调用服务器？），并给它所需的行为。

import pylab as p
import networkx as nx


class Node(object):
    nodes = []

    def __init__(self, label):
        self._label = label

    def __str__(self):
        return self._label

nodes = [Node(l) for l in ["A","B","C","C","D","H"]]
edges = [(0,1),(0,5),(5,2),(1,3),(1,4)]

G = nx.Graph()
for i,j in edges:
    G.add_edge(nodes[i], nodes[j])

nx.draw(G)
p.show()

给我们 所以你想要的东西。

Answer 2:

我知道你在寻找的是一个拓扑排序http://networkx.github.com/documentation/latest/reference/generated/networkx.algorithms.dag.topological_sort.html

如果你有一个DAG（有向无环图）这仅适用。 如果是这样，你可以画出你想要过的树 - 是这样的：

import uuid
import networkx as nx
import matplotlib.pyplot as plt
G = nx.DiGraph()
G.add_edge("A","B")
G.add_edge("A","H")
G.add_edge("H","C")
G.add_edge("B","C")
G.add_edge("B","D")

order =  nx.topological_sort(G)
print "topological sort"
print order

# build tree
start = order[0]
nodes = [order[0]] # start with first node in topological order
labels = {}
print "edges"
tree = nx.Graph()
while nodes:
    source = nodes.pop()
    labels[source] = source
    for target in G.neighbors(source):
        if target in tree:
            t = uuid.uuid1() # new unique id
        else:
            t = target
        labels[t] = target
        tree.add_edge(source,t)
        print source,target,source,t
        nodes.append(target)

nx.draw(tree,labels=labels)
plt.show()

该图采用了标签映射到该节点的ID映射到原始标签。

文章来源: Graph traversal with Networkx (Python)