एक ग्राफ का प्रतिनिधित्व करने के

Question

एक आसान तरीका कुछ डेटा संरचना में एक अजीब ग्राफ प्रतिनिधित्व करने के लिए कैसे फार्म के एक डेटा संरचना के साथ है:

{1:[2,3], 
2:[1,3], 
3:[1,2]} 

कहाँ इस शब्दकोश में कुंजी नोड्स, और किनारे प्रतिनिधित्व कर रहे हैं अन्य नोड्स की एक सूची से वे जुड़े हुए हैं। इस डेटा संरचना को भी आसानी से एक निर्देशित ग्राफ प्रतिनिधित्व करते हैं सकता है अगर लिंक सममित नहीं हैं:

{1:[2], 
2:[3], 
3:[1]} 

मैं ग्राफ-सिद्धांत के बारे में ज्यादा पता नहीं है, तो क्या मैं के बारे में प्रस्ताव करने के लिए कर रहा हूँ पहले से ही एक सरल उपाय हो सकता है , लेकिन मुझे नहीं पता कि क्या देखना है। मुझे लगता है कि मुझे लगता है कि एक ऐसी स्थिति है जहां एक ग्राफ कुछ हद तक निर्देशित होता है, जो नोड आप दोनों पर निर्भर करता है, और जिस नोड से आप आए थे। इसे समझने के लिए, मैं एक ड्राइंग है:

कल्पना कीजिए कि आप एक गो-कार्ट में बढ़त एक साथ तेजी से कर रहे हैं और नोड 1 में आप एक बढ़त बी पर बाएँ आप इतनी तेजी से जा रहे हैं के बाद से लटका, जब आप नोड 3 दबाते हैं, तो आपको किनारे पर जारी रखने के लिए मजबूर होना पड़ता है। हालांकि, अगर आप किनारे एफ से आ रहे थे, तो आप किनारे ई या बी पर जा सकते हैं। यह स्पष्ट है कि नोड तीन 1 से जुड़ा हुआ है और 2, लेकिन आप उस नोड से उन तक पहुंच सकते हैं या नहीं, इस पर निर्भर करता है कि आप किस दिशा से आए थे।

मुझे आश्चर्य है कि कोई ग्राफ सिद्धांत अवधारणा है जो इसका वर्णन करती है और/या यदि इसका वर्णन करने के लिए एक सरल डेटा संरचना है। जबकि मैं पाइथन में अपना कोड लिखूंगा, मैं किसी भी उचित रूप से लागू भाषा से सलाह लेता हूं।

संपादित करें: मैंने इसके साथ जाने के लिए एक छवि पोस्ट करने का प्रयास किया, लेकिन मुझे यकीन नहीं है कि यह दिखा रहा है या नहीं। यदि यह image

संपादित करें 2: मुझे यह स्पष्ट होना चाहिए था। पोस्ट की गई छवि को एक पूर्ण ग्राफ का एक हिस्सा माना जाता है, जिसमें ए, डी, और एफ

Answer 1

से स्क्रीन से अधिक नोड्स हैं, यह directed graph द्वारा प्रदर्शित किया जा सकता है।

आपके ग्राफ में नोड्स को ग्राफ में दो नोड्स के रूप में प्रदर्शित किया जा सकता है। सड़क के विशेष किनारों पर स्थानों का प्रतिनिधित्व करने के रूप में नोड्स के बारे में सोचें - किनारों को इनबाउंड और आउटबाउंड लेन की तरह होना चाहिए।

Answer 2

आप नोड्स और किनारों के साथ एक बुनियादी ग्राफ के रूप में इसे लागू कर सकते हैं। प्रत्येक नोड में, किनारों की एक सूची स्टोर करें। उन किनारों में से प्रत्येक के लिए, उस "एंट्री" किनारे से मैपिंग को वैध निकास किनारों पर स्टोर करें।

मुझे यह इंगित करना चाहिए कि आपके द्वारा पोस्ट की गई छवि एक ग्राफ नहीं है, क्योंकि ए, एफ, और डी किसी भी नोड से कनेक्ट नहीं होते हैं (जब तक वे केवल ऑफ-स्क्रीन नहीं होते)।

Answer 3

तारों के मैपिंग के लिए तारों के मैपिंग के रूप में अपने ग्राफ का प्रतिनिधित्व करें।

अधिक स्पष्ट रूप से, अजगर में आप होगा:

graph = { 
    'A': { 
     'B': set(['C', 'D', ...]), 
     'E': set(['F']), 
    }, 
    ... 
} 

एक किनारे A और B के बीच मौजूद है, तो कुंजी B मानचित्रण में प्रवेश A द्वारा निहित है।

यह किनारा चलाया जा सकता है यदि हम जिस नोड से आते हैं, वह graph['A']['B'] द्वारा मैप किए गए सेट में निहित है।

निम्नलिखित अजगर वर्ग इस विनिर्देश लागू करता है (यदि आप this gist पर एक टिप्पणी की संस्करण पा सकते हैं):

class Graph(object): 
    def __init__(self): 
     self.nodes = {} 

    def addEdge(self, (node1, comingFrom1), (node2, comingFrom2)): 
     self.nodes.setdefault(node1, {})[node2] = comingFrom1 
     self.nodes.setdefault(node2, {})[node1] = comingFrom2 

    def isEdge(self, comingFrom, passingBy, goingTo): 
     try: 
      return comingFrom in self.nodes[passingBy][goingTo] 
     except KeyError: 
      return False 

    def destinations(self, comingFrom, passingBy): 
     dests = set() 
     try: 
      for node, directions in self.nodes[passingBy].iteritems(): 
       if comingFrom in directions: 
        dests.add(node) 
     except KeyError: 
      pass 

     return dests 

    def sources(self, passingBy, goingTo): 
     return self.destinations(goingTo, passingBy) 

इस वर्ग के इस तरह इस्तेमाल किया जा सकता:

>>> graph = Graph() 
>>> graph.addEdge(('0', set([  ])), ('1', set(['3', '2']))) 
>>> graph.addEdge(('1', set(['0'  ])), ('3', set(['4'  ]))) 
>>> graph.addEdge(('1', set(['0'  ])), ('2', set(['5'  ]))) 
>>> graph.addEdge(('3', set(['1', '2'])), ('4', set([  ]))) 
>>> graph.addEdge(('3', set(['4'  ])), ('2', set(['5'  ]))) 
>>> graph.addEdge(('2', set(['1', '3'])), ('5', set([  ]))) 

>>> print graph.isEdge('0', '1', '3') 
True 
>>> print graph.isEdge('1', '3', '2') 
False 
>>> print graph.isEdge('1', '2', '5') 
True 
>>> print graph.isEdge('5', '2', '3') 
True 
>>> print graph.isEdge('3', '2', '5') 
True 

>>> print graph.destinations('0', '1') 
set(['3', '2']) 
>>> print graph.destinations('1', '3') 
set(['4']) 
>>> print graph.destinations('3', '4') 
set([]) 

>>> print graph.sources('0', '1') 
set([]) 
>>> print graph.sources('1', '3') 
set(['0']) 
>>> print graph.sources('3', '4') 

चुना डाटा संरचनाओं और उनके उपयोग पहले से ही एक निर्देशित ग्राफ बनाने की अनुमति देता है, केवल addEdge विधि को अनुकूलित करने की आवश्यकता होगी।