পাইথনে অভিধান ব্যবহার করে একটি গ্রাফ তৈরি করুন

গ্রাফগুলি পাইথনে অভিধান ব্যবহার করে প্রয়োগ করা যেতে পারে। অভিধানে, প্রতিটি কী শীর্ষবিন্দু হবে, এবং মান হিসাবে, এটি সংযুক্ত শীর্ষবিন্দুগুলির একটি তালিকা ধারণ করে। সুতরাং পুরো কাঠামোটি একটি গ্রাফ G(V, E) এর সংলগ্নতা তালিকার মতো দেখাবে।

আমরা মৌলিক অভিধান অবজেক্ট ব্যবহার করতে পারি, কিন্তু আমরা ডিফল্ট ডিক্ট ব্যবহার করছি। এর কিছু অতিরিক্ত বৈশিষ্ট্য রয়েছে। এটিতে একটি অতিরিক্ত লিখনযোগ্য উদাহরণ ভেরিয়েবল রয়েছে৷

আমরা একটি টেক্সট ফাইল প্রদান করছি, যাতে শীর্ষবিন্দুর সংখ্যা, প্রান্তের সংখ্যা, শীর্ষবিন্দুর নাম এবং প্রান্তের তালিকা রয়েছে। অনির্দেশিত গ্রাফের জন্য, আমরা দুটি প্রান্ত যেমন (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']