 # Untitled

a guest
Mar 6th, 2018
187
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
3.     def __init__(self, node):
4.         self.node = node
5.         self.next = None #changed this from self
6.
7.     #Simple method for debugging
8.     def __str__(self):
9.         cur = self
10.         string = "Link : "
11.         while True:
12.             string += str(cur.node) + " > "
13.             cur = cur.next
14.             if cur == None:
15.                 break
16.         return string + "..."
17.
23.
24. def eulerian_cycle_2(graph):
25.     """Return an Eulerian cycle in graph, if there is one, as a list of
26.    nodes. If there are no Eulerian cycles, raise ValueError.
27.
28.    """
29.     # Take a copy of the graph so that we can modify it.
30.     graph = {k:v[:] for k, v in graph.items()}
31.
32.     # Start at any node in the graph that has an edge.
33.     node = next(node for node, neighbours in graph.items() if neighbours)
34.     choices = graph[node]
36.     begin = cur #new
37.
38.     # Map from node we've visited (that still has edges) to a link for
39.     # that node in the linked list.
40.     visited = {}
41.
42.     while True:
43.         # Extend current cycle until no more edges can be followed.
44.         start = node
45.         while choices:
46.             visited[node] = cur
47.             node = choices.pop()
48.             choices = graph[node]
50.         if node != start:
51.             raise ValueError("graph has no Eulerian cycle")
52.
53.         # Find a visited node which still has edges, if any.
54.         while visited:
55.             node, cur = visited.popitem()
56.             choices = graph[node]
57.             if choices:
58.                 break
59.         else:
60.             break
61.
62.     if any(graph.values()):
63.         raise ValueError("graph has no Eulerian cycle")
64.
65.     # Reconstruct cycle by following linked list.
66.     cycle = []
67.     cur = begin #new
68.     while True:
69.         cycle.append(cur.node)
70.         cur = cur.next
71.         if cur == None: #changed from cur == start
72.             break
73.     return cycle
RAW Paste Data