Advertisement
Guest User

eulerian

a guest
Jul 30th, 2016
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.03 KB | None | 0 0
  1. # Eulerian Tour Ver 1
  2. #
  3. # Write a function, `create_tour` that takes as
  4. # input a list of nodes
  5. # and outputs a list of tuples representing
  6. # edges between nodes that have an Eulerian tour.
  7. #
  8.  
  9. def create_tour(nodes):
  10. # your code here
  11. return []
  12.  
  13. #########
  14.  
  15. def get_degree(tour):
  16. degree = {}
  17. for x, y in tour:
  18. degree[x] = degree.get(x, 0) + 1
  19. degree[y] = degree.get(y, 0) + 1
  20. return degree
  21.  
  22. def check_edge(t, b, nodes):
  23. """
  24. t: tuple representing an edge
  25. b: origin node
  26. nodes: set of nodes already visited
  27.  
  28. if we can get to a new node from `b` following `t`
  29. then return that node, else return None
  30. """
  31. if t[0] == b:
  32. if t[1] not in nodes:
  33. return t[1]
  34. elif t[1] == b:
  35. if t[0] not in nodes:
  36. return t[0]
  37. return None
  38.  
  39. def connected_nodes(tour):
  40. """return the set of nodes reachable from
  41. the first node in `tour`"""
  42. a = tour[0][0]
  43. nodes = set([a])
  44. explore = set([a])
  45. while len(explore) > 0:
  46. # see what other nodes we can reach
  47. b = explore.pop()
  48. for t in tour:
  49. node = check_edge(t, b, nodes)
  50. if node is None:
  51. continue
  52. nodes.add(node)
  53. explore.add(node)
  54. return nodes
  55.  
  56. def is_eulerian_tour(nodes, tour):
  57. # all nodes must be even degree
  58. # and every node must be in graph
  59. degree = get_degree(tour)
  60. for node in nodes:
  61. try:
  62. d = degree[node]
  63. if d % 2 == 1:
  64. print "Node %s has odd degree" % node
  65. return False
  66. except KeyError:
  67. print "Node %s was not in your tour" % node
  68. return False
  69. connected = connected_nodes(tour)
  70. if len(connected) == len(nodes):
  71. return True
  72. else:
  73. print "Your graph wasn't connected"
  74. return False
  75.  
  76. def test():
  77. nodes = [20, 21, 22, 23, 24, 25]
  78. tour = create_tour(nodes)
  79. return is_eulerian_tour(nodes, tour)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement