1. Pypy
  2. Untitled project
  3. pypy

Source

pypy / pypy / tool / algo / graphlib.py

Diff from to

File pypy/tool/algo/graphlib.py

  • Ignore whitespace
   'edges' is a dict mapping vertices to a list of edges with its source.
   Note that we can usually use 'edges' as the set of 'vertices' too.
 """
+from pypy.tool.identity_dict import identity_dict
+
 
 class Edge:
     def __init__(self, source, target):
                 roots_finished.add(root)
                 continue
             #print 'from root %r: %d cycles' % (root, len(cycles))
-            allcycles = {}
+            allcycles = identity_dict()
             edge2cycles = {}
             for cycle in cycles:
-                allcycles[id(cycle)] = cycle
+                allcycles[cycle] = cycle
                 for edge in cycle:
-                    edge2cycles.setdefault(edge, []).append(id(cycle))
+                    edge2cycles.setdefault(edge, []).append(cycle)
             edge_weights = {}
             for edge, cycle in edge2cycles.iteritems():
                 edge_weights[edge] = len(cycle)
                 yield max_edge
                 progress = True
                 # unregister all cycles that have just been broken
-                for broken_cycle_id in edge2cycles[max_edge]:
-                    broken_cycle = allcycles.pop(broken_cycle_id, ())
+                for broken_cycle in edge2cycles[max_edge]:
+                    broken_cycle = allcycles.pop(broken_cycle, ())
                     for edge in broken_cycle:
                         edge_weights[edge] -= 1
 
             v_depths = compute_depths(roots, vertices, edges)
             assert len(v_depths) == len(vertices)  # ...so far.  We remove
             # from v_depths the vertices at which we choose to break cycles
-        print '%d inital roots' % (len(roots,))
+        #print '%d inital roots' % (len(roots,))
         progress = False
         for root in roots:
             if root in roots_finished:
             if not cycles:
                 roots_finished.add(root)
                 continue
-            print 'from root %r: %d cycles' % (root, len(cycles))
+            #print 'from root %r: %d cycles' % (root, len(cycles))
             # compute the "depth" of each cycles: how far it goes from any root
             allcycles = []
             for cycle in cycles: