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

给了我们 所以你想要什么。