पायथन में डिक्शनरी का उपयोग करके एक ग्राफ बनाएं

पायथन में डिक्शनरी का उपयोग करके रेखांकन को लागू किया जा सकता है। शब्दकोश में, प्रत्येक कुंजी शिखर होगी, और मूल्य के रूप में, इसमें जुड़े शिखरों की एक सूची होती है। तो पूरी संरचना एक ग्राफ जी (वी, ई) की आसन्न सूची की तरह दिखेगी।

हम मूल शब्दकोश वस्तु का उपयोग कर सकते हैं, लेकिन हम डिफ़ॉल्ट तानाशाही का उपयोग कर रहे हैं। इसमें कुछ अतिरिक्त विशेषताएं हैं। इसमें एक अतिरिक्त लिखने योग्य आवृत्ति चर है।

हम एक टेक्स्ट फ़ाइल प्रदान कर रहे हैं, जिसमें शीर्षों की संख्या, किनारों की संख्या, शीर्षों के नाम और किनारों की सूची शामिल है। अप्रत्यक्ष ग्राफ़ के लिए, हम दो किनारों जैसे (u,v) और (v,u) प्रदान कर रहे हैं।

हम इस उदाहरण में इस ग्राफ का उपयोग कर रहे हैं।

ग्राफ़ के लिए फ़ाइल नीचे की तरह है -

Graph_Input.txt

6
8
A|B|C|D|E|F
A,B
B,A
A,C
C,A
B,D
D,B
B,E
E,B
C,E
E,C
D,E
E,D
D,F
F,D
E,F
F,E

तो सबसे पहले, हम शीर्षों के नाम ले रहे हैं, और फिर किनारों को सूची में सम्मिलित करने के लिए पढ़ते हैं।

उदाहरण कोड

from collections import defaultdict
defcreate_graph(filename):
   graph = defaultdict(list) #create dict with keys and corresponding lists
   with open(filename, 'r') as graph_file:
   vertex = int(graph_file.readline())
   edges = int(graph_file.readline())
   vert_Names = graph_file.readline()
   vert_Names = vert_Names.rstrip('\n') #Remove the trailing new line character
   nodes = vert_Names.split('|') #Cut the vertex names
   for node in nodes: #For each vertex, create empty list
      graph[node] = []
   #Read edges from file and fill the lists
   for line in graph_file:
      line = line.rstrip('\n') #Remove the trailing new line character
      edge = line.split(',')
      graph[edge[0]].append(edge[1]) #The edge[0] is source and edge[1] is dest
   return graph
my_graph = create_graph('Graph_Input.txt')
for node in my_graph.keys(): #Print the graph
   print(node + ': ' + str(my_graph[node]))

आउटपुट

A: ['B', 'C']
B: ['A', 'D', 'E']
C: ['A', 'E']
D: ['B', 'E', 'F']
E: ['B', 'C', 'D', 'F']
F: ['D', 'E']

अब हम दिए गए ग्राफ G(V,E) पर कुछ बुनियादी संक्रियाओं को देखेंगे। सबसे पहले हम देखेंगे कि सोर्स वर्टेक्स से डेस्टिनेशन वर्टेक्स तक पथ कैसे प्राप्त करें। दिया गया कोड इस ऑपरेशन का एक हिस्सा है। इसे निष्पादित करने के लिए, आपको पिछली विधि का उपयोग करके ग्राफ बनाना होगा।

उदाहरण कोड

#Function to find path from source to destination
defget_path(graph, src, dest, path = []):
   path = path + [src]
   if src == dest: #when destination is found, stop the process
      return path
   for vertex in graph[src]:
      if vertex not in path:
         path_new = get_path(graph, vertex, dest, path)
         if path_new:
            return path_new
         return None
my_graph = create_graph('Graph_Input.txt')
path = get_path(my_graph, 'A', 'C')
print('Path From Node A to C: ' + str(path))

आउटपुट

Path From Node A to C: ['A', 'B', 'D', 'E', 'C']

अब हम देखेंगे कि सोर्स वर्टेक्स से डेस्टिनेशन वर्टेक्स तक सभी संभावित पथ कैसे प्राप्त करें। दिया गया कोड इस ऑपरेशन का एक हिस्सा है। इसे निष्पादित करने के लिए, आपको पिछली विधि का उपयोग करके ग्राफ बनाना होगा।

उदाहरण कोड

#Function to find all paths from source to destination
defget_all_path(graph, src, dest, path = []):
   path = path + [src]
   if src == dest: #when destination is found, stop the process
      return [path]
   paths = []
   new_path_list = []
   for vertex in graph[src]:
      if vertex not in path:
         new_path_list = get_all_path(graph, vertex, dest, path)
      for new_path in new_path_list:
         paths.append(new_path)
   return paths
my_graph = create_graph('Graph_Input.txt')
paths = get_all_path(my_graph, 'A', 'C')
print('All Paths From Node A to C: ')
for path in paths:
   print(path)

आउटपुट

All Paths From Node A to C:
['A', 'B', 'D', 'E', 'C']
['A', 'B', 'D', 'E', 'C']
['A', 'B', 'D', 'F', 'E', 'C']
['A', 'B', 'D', 'F', 'E', 'C']
['A', 'B', 'D', 'F', 'E', 'C']
['A', 'B', 'E', 'C']
['A', 'C']

अंत में, हम देखेंगे कि स्रोत से गंतव्य शीर्ष तक का सबसे छोटा पथ कैसे प्राप्त करें। दिया गया कोड इस ऑपरेशन का एक हिस्सा है। इसे निष्पादित करने के लिए, आपको पिछली विधि का उपयोग करके ग्राफ बनाना होगा।

उदाहरण कोड

#Function to find shortest path from source to destination
def get_shortest_path(graph, src, dest, path = []):
   path = path + [src]
   if src == dest: #when destination is found, stop the process
      return path
   short = None
   for vertex in graph[src]:
      if vertex not in path:
         new_path_list = get_shortest_path(graph, vertex, dest, path)
         if new_path_list:
            if not short or len(new_path_list) <len(short):
               short = new_path_list
   return short
my_graph = create_graph('Graph_Input.txt')
path = get_shortest_path(my_graph, 'A', 'C')
print('Shortest Paths From Node A to C: ' + str(path))

आउटपुट

Shortest Paths From Node A to C: ['A', 'C']