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

ग्राफ़ को Python में डिक्शनरी का उपयोग करके लागू किया जा सकता है। डिक्शनरी में, प्रत्येक कुंजी वर्टेक्स होगी, और वैल्यू के रूप में यह कनेक्टेड वर्टेक्स की सूची रखती है। इसलिए पूरी संरचना ग्राफ़ 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)
    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])
    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 = []
    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']