使用Networkx(Python)进行图遍历 [英] Graph traversal with Networkx (Python)

问题描述

我正在与Networkx一起管理依赖关系图. 假设我有这个图，每个字母代表一个服务器

I'm playing a bit with Networkx to manage a graph of dependencies. Let's say I have this Graph which each letter represent a server

>>> 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.

So here we can see that before starting A we need to start H and B and to start H we need to start C and then to start B wee need to start C and D

通过对Networkx的摆弄，我发现可以通过遍历dfs来实现这一点

By fiddling a bit with Networkx I found that I can get that by doing a dfs traversal

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

但是我对该方法有疑问.如您所见，当树中有两个相同的字母时，Networkx只选择将其中一个放入最终结构中(这是正确的)，但是我需要具有完整的结构 如何强制Networkx添加结构B:[D，C] ??

But I have a problem with that method. As you can see when there is two same letter in the tree, Networkx only chose to put one of them in the final structure (which is correct) But I need to have the complete structure How can I force Networkx to add in the structure B:[D,C] ??

我想通过这样做

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

所以一切都是内部"正确的，只是dfs_successors不能按我希望的方式显示它.

So everything is "Internally" correct, it's just the dfs_successors that displays it not in the way I wish.

谢谢

推荐答案

采用代码，图形不会按您期望的那样出现.如果您这样做:

Taking your code, your graph doesn't come out as you'd expect. If you do:

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

您将看到以下图形:

you will see your graph as:

这是由于G.add_edge("A", "B")的逻辑造成的:

This is due to the logic of G.add_edge("A", "B"):

1. 如果G没有ID为"A"的节点，请添加它.
2. 如果G没有ID为"B"的节点，请添加它.
3. 用新的边缘将"A"连接到"B".

1. If G has no node of id "A", add it.
2. If G has no node of id "B", add it.
3. Connect "A" to "B" with a new edge.

因此，您只能创建五个节点，而不是图片中的六个节点.

Thus, you only create five nodes, not six as in your picture.

修改 Networkx可以将任何可哈希值用作节点的值，并且在图中使用str(node)标记每个圆圈.因此，我们可以简单地定义我们自己的Node类(您可能想称其为Server?)并赋予其所需的行为.

Edit Networkx can take any hashable as value for a node, and in the graph it uses str(node) to label each circle. So we can simply define our own Node class (which you maybe want to call Server?) and give it the desired behavior.

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

给我们 还有你想要的.

gives us and so what you wanted.

这篇关于使用Networkx(Python)进行图遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！