Networkx（Python）を使ったグラフトラバーサル

Question

Networkxを使って依存関係のグラフを管理しています。 各文字は、そこでここでは、Aを開始する前に、我々はHとBを開始するために、我々はCを開始し、その後、Bを起動する必要がHを開始する必要があることがわかりますサーバー

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

を表す私はこのグラフを持っているのは、言ってみましょうNetworkxでビットをいじることでCとD

を開始するためにおしっこ必要性私は、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だということを正確にしたいです。

が

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"を新しいエッジで接続します。

このように、あなたの写真では6つではなく、5つのノードしか作成しません。

編集 Networkxノードの値として、任意のハッシュ可能を取ることができ、そしてグラフには、各輪にラベルを付けるためにSTR（ノード）を使用します。したがって、独自のNodeクラス（単に「サーバー」と呼ぶ）を定義し、それに望ましい動作を与えることができます。

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

くれ ので、あなたが欲しいものを提供します。

Answer 2

あなたはDAG（有向非巡回グラフ）を持っている場合、私はこれだけ作品あなたが探していることはトポロジカルソートである http://networkx.github.com/documentation/latest/reference/generated/networkx.algorithms.dag.topological_sort.html

と思います。 もしそうなら、あなたも、あなたがしたいツリーを描くことができます - このように：

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をマップするためにラベルマッピングを使用しています。