नेटवर्कक्स (पायथन) के साथ ग्राफ ट्रैवर्सल

Question

मैं निर्भरता के ग्राफ को प्रबंधित करने के लिए नेटवर्कक्स के साथ थोड़ा सा खेल रहा हूं। चलो कहते हैं कि मैं इस ग्राफ़ जो प्रत्येक अक्षर एक सर्वर

>>> 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 साथ एक सा नगण्य द्वारा की जरूरत मैंने पाया कि मैं एक DFS ट्रेवर्सल

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

करके कि प्राप्त कर सकते हैं लेकिन मुझे लगता है कि विधि के साथ एक समस्या है कि। जैसा कि आप देख सकते हैं कि पेड़ में दो समान पत्र कब होते हैं, नेटवर्कक्स ने केवल उनमें से एक को अंतिम संरचना (जो सही है) में डालना चुना है, लेकिन मुझे पूरी संरचना की आवश्यकता है मैं संरचना में जोड़ने के लिए नेटवर्कक्स को कैसे मजबूर कर सकता हूं बी: [डी, सी] ??

मैं

>>> 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 आईडी 'ए' का कोई नोड है, इसे जोड़ें।
2. यदि G में आईडी "बी" का कोई नोड नहीं है, तो इसे जोड़ें।
3. एक नए किनारे के साथ "ए" से "बी" कनेक्ट करें।

इस प्रकार, आप केवल पांच नोड्स बनाते हैं, आपकी तस्वीर में छः नहीं।

संपादित Networkx एक नोड के लिए मूल्य के रूप में किसी भी hashable ले जा सकते हैं, और ग्राफ़ में यह str (नोड) का उपयोग करता है प्रत्येक चक्र लेबल करने के लिए। तो हम बस अपने स्वयं के नोड क्लास को परिभाषित कर सकते हैं (जिसे आप शायद सर्वर पर कॉल करना चाहते हैं?) और इसे वांछित व्यवहार दें।

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

ड्राइंग मूल लेबल के लिए नोड के आईडी मैप करने के लिए एक लेबल मानचित्रण का उपयोग करता है।