পাইথনে ডিকশনারি ব্যবহার করে গ্রাফ ইমপ্লিমেন্ট করা যায়। ডিকশনারিতে প্রতিটি কী হবে ভার্টেক্স, এবং ভ্যালু হিসেবে এটি সংযুক্ত ভার্টেক্সের একটি লিস্ট ধারণ করবে। তাই পুরো স্ট্রাকচারটি একটি গ্রাফ G(V, E)-এর এডজেসেন্সি লিস্টের মতো দেখাবে।
আমরা বেসিক ডিকশনারি অবজেক্ট ব্যবহার করতে পারি, কিন্তু এখানে defaultdict ব্যবহার করা হয়েছে। এর কিছু অতিরিক্ত ফিচার রয়েছে। এর একটি অতিরিক্ত রাইটেবল ইনস্ট্যান্স ভেরিয়েবল রয়েছে।
আমরা একটি টেক্সট ফাইল প্রদান করছি, যাতে ভার্টেক্সের সংখ্যা, এজের সংখ্যা, ভার্টেক্সের নাম, এবং এজের লিস্ট রয়েছে। অনডাইরেক্টেড গ্রাফের জন্য, আমরা (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
def create_graph(filename):
graph = defaultdict(list) # কী এবং সংশ্লিষ্ট লিস্টের সাথে dict তৈরি
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') # ট্রেইলিং নিউলাইন ক্যারেক্টার সরান
nodes = vert_Names.split('|') # ভার্টেক্স নামগুলো কাটুন
for node in nodes:
# প্রতিটি ভার্টেক্সের জন্য খালি লিস্ট তৈরি করুন
graph[node] = []
# ফাইল থেকে এজ পড়ে লিস্টগুলো পূরণ করুন
for line in graph_file:
line = line.rstrip('\n') # ট্রেইলিং নিউলাইন ক্যারেক্টার সরান
edge = line.split(',')
graph[edge[0]].append(edge[1]) # edge[0] হলো সোর্স এবং edge[1] হলো ডেস্টিনেশন
return graph
my_graph = create_graph('Graph_Input.txt')
for node in my_graph.keys():
# গ্রাফ প্রিন্ট করুন
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)-এর ওপর কিছু বেসিক অপারেশন দেখব। প্রথমে সোর্স ভার্টেক্স থেকে ডেস্টিনেশন ভার্টেক্স পর্যন্ত পাথ পাওয়ার পদ্ধতি দেখব। দেওয়া কোডটি এই অপারেশনের একটি অংশ। এক্সিকিউট করতে হলে আগের মেথড দিয়ে গ্রাফ জেনারেট করতে হবে।
উদাহরণ কোড
# সোর্স থেকে ডেস্টিনেশন পর্যন্ত পাথ খুঁজে বের করার ফাংশন
def get_path(graph, src, dest, path=[]):
path = path + [src]
if src == dest: # ডেস্টিনেশন পাওয়া গেলে প্রসেস বন্ধ করুন
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']
এখন সোর্স ভার্টেক্স থেকে ডেস্টিনেশন ভার্টেক্স পর্যন্ত সব সম্ভাব্য পাথ পাওয়ার পদ্ধতি দেখব। দেওয়া কোডটি এই অপারেশনের একটি অংশ। এক্সিকিউট করতে হলে আগের মেথড দিয়ে গ্রাফ জেনারেট করতে হবে।
উদাহরণ কোড
# সোর্স থেকে ডেস্টিনেশন পর্যন্ত সব পাথ খুঁজে বের করার ফাংশন
def get_all_path(graph, src, dest, path=[]):
path = path + [src]
if src == dest: # ডেস্টিনেশন পাওয়া গেলে প্রসেস বন্ধ করুন
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']
শেষে, সোর্স থেকে ডেস্টিনেশন ভার্টেক্স পর্যন্ত শর্টেস্ট পাথ পাওয়ার পদ্ধতি দেখব। দেওয়া কোডটি এই অপারেশনের একটি অংশ। এক্সিকিউট করতে হলে আগের মেথড দিয়ে গ্রাফ জেনারেট করতে হবে।
উদাহরণ কোড
# সোর্স থেকে ডেস্টিনেশন পর্যন্ত শর্টেস্ট পাথ খুঁজে বের করার ফাংশন
def get_shortest_path(graph, src, dest, path=[]):
path = path + [src]
if src == dest: # ডেস্টিনেশন পাওয়া গেলে প্রসেস বন্ধ করুন
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']
