daily pastebin goal
48%
SHARE
TWEET

Untitled

a guest Mar 6th, 2018 98 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top