Pythonで辞書を使用してグラフを生成する

グラフは、Pythonの辞書を使用して実装できます。辞書では、各キーが頂点になり、値として、接続されている頂点のリストが保持されます。したがって、構造全体はグラフG（V、E）の隣接リストのようになります。

基本的な辞書オブジェクトを使用できますが、デフォルトのdictを使用しています。いくつかの追加機能があります。追加の書き込み可能なインスタンス変数が1つあります。

頂点の数、エッジの数、頂点の名前、およびエッジのリストを含むテキストファイルを提供しています。無向グラフの場合、（u、v）と（v、u）のような2つのエッジを提供します。

この例では、このグラフを使用しています。

グラフのファイルは以下のようになります-

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']