Guest User

Untitled

a guest
Mar 6th, 2018
135
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Link:
  2.     "A link in a linked list."
  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.    
  18.     def insert(self, link):
  19.         "Insert link after self in the linked list and return link."
  20.         link.next = self.next
  21.         self.next = link
  22.         return link
  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]
  35.     cur = Link(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]
  49.             cur = cur.insert(Link(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