9

我正在使用 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 没有以我希望的方式显示它。

谢谢

4

2 回答 2

7

我认为您正在寻找的是拓扑排序 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 映射到原始标签。

在此处输入图像描述

于 2013-01-11T00:49:37.843 回答
7

使用您的代码，您的图表并没有像您预期的那样出现。如果你这样做：

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()

给我们 新图表 ，所以你想要什么。

于 2013-01-10T14:31:11.767 回答