使用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进行微调，我发现可以通过进行深度优先遍历来获得这个结果。

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显示它的方式不符合我的意愿。

谢谢

- Johny19

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)来标记每个圆圈。因此，我们可以简单地定义自己的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()

给我们 所以这就是你想要的。

- Thorsten Kranz

---

谢谢您绘制图表。这正是我认为Networkx在背后所做的。因此我的问题是：如何使用Networkx创建类似于我的示例中的树形结构？ 通常对我来说理想的情况是，当我创建G.add_edge("B","C")时，会创建一个新的节点"C"，而不是重复使用连接到H的节点。 - Johny19

那么你需要给新节点起一个不同的名称，比如C1和C2。据我所知，NetworkX不允许具有相同标签的多个节点。 - brentlance

但是我需要节点保持相同，就像我在主线程中说的那样。我的节点是服务器名称，我不能更改名称，否则我就不知道哪个是哪个... 但是真正的图表Thorsten Kranz并没有“错误”，它是正确的，“B依赖于C和D”。只是算法“dfs_successors()”输出B仅依赖于D，这是错误的。 如果我的树在Networkx中不可行，那么其他库是否可以实现？谢谢 - Johny19

添加了第二个示例，希望符合您的需求。 - Thorsten Kranz

边缘也可以被标记吗？ - alancalvitti

Answer 2

我认为你正在寻找的是拓扑排序https://networkx.org/documentation/stable/reference/algorithms/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映射到原始标签。

- Aric

---

提供的链接已损坏。 - schade96