fork download
copy 
  1. from collections import deque
  2.  
  3. graph = [
  4.     ['a', 'b', 'c', 'd', 'e', 'f'],
  5.     ['g', 'e', 'h', 'i', 'j'],
  6.     ['k', 'l', 'i', 'n', 'm']
  7. ]
  8.  
  9.  
  10. def graph_nodes(a_graph):
  11.     return list(set([node for _ in a_graph for node in _]))
  12.  
  13.  
  14. def neighbours(a_graph, a_node):
  15.     node_neighbours = []
  16.  
  17.     """
  18.     Przegladamy kazda z list reprezentujacych graf i jesli napotkamy zadany wierzcholek, to zapamietujemy jego 
  19.     poprzednika i nastepnika (o ile istnieja).
  20.     """
  21.     for a_list in a_graph:
  22.         for i, element in enumerate(a_list):
  23.             if element == a_node and i + 1 < len(a_list):
  24.                 node_neighbours.append(a_list[i + 1])
  25.  
  26.             if element == a_node and i - 1 >= 0:
  27.                 node_neighbours.append(a_list[i - 1])
  28.  
  29.     return list(set(node_neighbours))
  30.  
  31. # Zwykle przechodzenie grafu
  32. def find_path(a_graph, from_node, to_node):
  33.     nodes = graph_nodes(a_graph)
  34.  
  35.     if from_node not in nodes or to_node not in nodes:
  36.         return None
  37.  
  38.     visited = {n: False for n in nodes}
  39.  
  40.     """ W kolejce pamietamy sciezke od zadanego wierzcholka"""
  41.     queue = deque([from_node])
  42.  
  43.     while len(queue) > 0:
  44.         remembered_path = queue.pop()
  45.         current_node = remembered_path[-1] # Ostatni element sciezki to wierzcholek do dalszej analizy
  46.         visited[current_node] = True
  47.  
  48.         if current_node == to_node:
  49.             return remembered_path
  50.  
  51.         for node in neighbours(a_graph, current_node):
  52.             if not visited[node]:
  53.                 visited[node] = True
  54.                 new_path = [n for n in remembered_path]
  55.                 new_path.append(node)
  56.                 queue.append(new_path)
  57.     return None
  58.  
  59.  
  60. print("Path={}".format(find_path(graph, 'd', 'n')))
  61. print("Path={}".format(find_path(graph, 'a', 'm')))
  62. print("Path={}".format(find_path(graph, 'k', 'j')))
  63. print("Path={}".format(find_path(graph, 'FOO', 'BAR')))
  64. print("Path={}".format(find_path(graph, 'a', 'BAR')))
  65. # your code goes here
Success #stdin #stdout 0.02s 27712KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Path=['d', 'e', 'h', 'i', 'n']
Path=['a', 'b', 'c', 'd', 'e', 'h', 'i', 'n', 'm']
Path=['k', 'l', 'i', 'j']
Path=None
Path=None
https://ideone.com/mQObpQ
language:
Python 3 (python  3.9.5)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!