使用Networkx(Python)进行图遍历

Question

我正在使用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 

所以在这里我们可以看到,在启动A之前我们需要启动H和B并启动H我们需要启动C然后启动B我们需要启动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(节点)标记每个圆.所以我们可以简单地定义我们自己的Node类(您可能想要调用Server？)并为其提供所需的行为.

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映射到原始标签.