fork download
  1. graph = {
  2. "A" : {"B" : 13, "C" : 3, "D" : 9, "E" : 9},
  3. "B" : {"A" : 13, "C" : 11, "D" : 11, "E" : 13},
  4. "C" : {"A" : 3, "B" : 11, "D" : 9, "E" : 7},
  5. "D" : {"A" : 9, "B" : 11, "C" : 9, "E" : 2},
  6. "E" : {"A" : 9, "B" : 13, "C" : 7, "D" : 2},
  7. }
  8.  
  9. NotAllowedNodes = {
  10. "A" : [],
  11. "B" : [],
  12. "C" : [],
  13. "D" : [],
  14. "E" : [],
  15. }
  16.  
  17. def build_ost_tree():
  18. for tup in get_sorted_nodes():
  19. node, edge, value = tup
  20. print("NODE | EDGE | NotAllowedNodes => ", node, edge, "NODES [node | edge] => ", NotAllowedNodes[node], NotAllowedNodes[edge])
  21. if not cycle_test(edge, node):
  22. continue
  23.  
  24. connect_node(edge, node)
  25. print(node, edge)
  26.  
  27.  
  28.  
  29. def get_sorted_nodes():
  30. return sorted([(key, tup[0], tup[1]) for key in graph for tup in graph[key].items()], key=lambda x: x[2])
  31.  
  32.  
  33.  
  34. def connect_node(key, node):
  35. NotAllowedNodes[key].append(node)
  36. NotAllowedNodes[node].append(key)
  37.  
  38.  
  39.  
  40. def cycle_test(start, end, visited=[]):
  41.  
  42.  
  43. if start in visited:
  44. return False
  45. visited.append(start)
  46. if end in NotAllowedNodes[start]:
  47. return False
  48. elif start in NotAllowedNodes[end]:
  49. return False
  50. else:
  51. for element in NotAllowedNodes[start]:
  52. if element not in visited:
  53. cycle_test(element, end, visited)
  54. return True
  55.  
  56.  
  57. build_ost_tree()
Success #stdin #stdout 0.03s 44680KB
stdin
Standard input is empty
stdout
('NODE | EDGE | NotAllowedNodes => ', 'D', 'E', 'NODES [node | edge] => ', [], [])
('D', 'E')
('NODE | EDGE | NotAllowedNodes => ', 'E', 'D', 'NODES [node | edge] => ', ['D'], ['E'])
('NODE | EDGE | NotAllowedNodes => ', 'A', 'C', 'NODES [node | edge] => ', [], [])
('A', 'C')
('NODE | EDGE | NotAllowedNodes => ', 'C', 'A', 'NODES [node | edge] => ', ['A'], ['C'])
('NODE | EDGE | NotAllowedNodes => ', 'C', 'E', 'NODES [node | edge] => ', ['A'], ['D'])
('NODE | EDGE | NotAllowedNodes => ', 'E', 'C', 'NODES [node | edge] => ', ['D'], ['A'])
('NODE | EDGE | NotAllowedNodes => ', 'A', 'D', 'NODES [node | edge] => ', ['C'], ['E'])
('NODE | EDGE | NotAllowedNodes => ', 'A', 'E', 'NODES [node | edge] => ', ['C'], ['D'])
('NODE | EDGE | NotAllowedNodes => ', 'C', 'D', 'NODES [node | edge] => ', ['A'], ['E'])
('NODE | EDGE | NotAllowedNodes => ', 'D', 'A', 'NODES [node | edge] => ', ['E'], ['C'])
('NODE | EDGE | NotAllowedNodes => ', 'D', 'C', 'NODES [node | edge] => ', ['E'], ['A'])
('NODE | EDGE | NotAllowedNodes => ', 'E', 'A', 'NODES [node | edge] => ', ['D'], ['C'])
('NODE | EDGE | NotAllowedNodes => ', 'B', 'C', 'NODES [node | edge] => ', [], ['A'])
('NODE | EDGE | NotAllowedNodes => ', 'B', 'D', 'NODES [node | edge] => ', [], ['E'])
('NODE | EDGE | NotAllowedNodes => ', 'C', 'B', 'NODES [node | edge] => ', ['A'], [])
('C', 'B')
('NODE | EDGE | NotAllowedNodes => ', 'D', 'B', 'NODES [node | edge] => ', ['E'], ['C'])
('NODE | EDGE | NotAllowedNodes => ', 'A', 'B', 'NODES [node | edge] => ', ['C'], ['C'])
('NODE | EDGE | NotAllowedNodes => ', 'B', 'A', 'NODES [node | edge] => ', ['C'], ['C'])
('NODE | EDGE | NotAllowedNodes => ', 'B', 'E', 'NODES [node | edge] => ', ['C'], ['D'])
('NODE | EDGE | NotAllowedNodes => ', 'E', 'B', 'NODES [node | edge] => ', ['D'], ['C'])