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] }

しかし、私はその方法に問題があります。ツリーに同じ文字が2つある場合にわかるように、Networkxはそのうちの1つだけを最終構造に配置することを選択しました（これは正しいです）が、完全な構造が必要ですNetworkxに構造Bを追加させるにはどうすればよいですか：[D、C] ??

私はそれをすることによってそれを正確にしたい

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

したがって、すべてが「内部的に」正しいので、私が望む方法でそれを表示しないのはdfs_successorsだけです。

ありがとうございました

score 7 · Accepted Answer

コードを取得すると、期待どおりにグラフが表示されません。もし、するなら：

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")。

GID「A」のノードがない場合は追加します。
GID「B」のノードがない場合は追加します。
「A」を「B」に新しいエッジで接続します。

したがって、作成するノードは5つだけで、図のように6つではありません。

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

新しいグラフ私たちにあなたが望んでいたものを与えてくれます。

score 7 · Accepted Answer

あなたが探しているのはトポロジカルソートだと思います 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を元のラベルにマップします。

ここに画像の説明を入力してください

python - Networkx（Python）を使用したグラフ走査

2 に答える 2

Related

Reference