home *** CD-ROM | disk | FTP | other *** search
/ Maximum CD 2012 January / maximum-cd-2012-01.iso / DiscContents / digsby_setup.exe / lib / util / primitives / topological_sort.pyo (.txt) < prev   
Encoding:
Python Compiled Bytecode  |  2011-10-05  |  2.4 KB  |  97 lines
  1. # Source Generated with Decompyle++
  2. # File: in.pyo (Python 2.6)
  3.  
  4.  
  5. def topological_sort(items, partial_order):
  6.     
  7.     def add_node(graph, node):
  8.         if not graph.has_key(node):
  9.             graph[node] = [
  10.                 0]
  11.         
  12.  
  13.     
  14.     def add_arc(graph, fromnode, tonode):
  15.         graph[fromnode].append(tonode)
  16.         graph[tonode][0] = graph[tonode][0] + 1
  17.  
  18.     graph = { }
  19.     for v in items:
  20.         add_node(graph, v)
  21.     
  22.     for a, b in partial_order:
  23.         add_arc(graph, a, b)
  24.     
  25.     roots = _[1]
  26.     sorted = []
  27.     while len(roots) != 0:
  28.         root = roots.pop()
  29.         sorted.append(root)
  30.         for child in graph[root][1:]:
  31.             graph[child][0] = graph[child][0] - 1
  32.             if graph[child][0] == 0:
  33.                 roots.append(child)
  34.                 continue
  35.             []
  36.         
  37.         del graph[root]
  38.         continue
  39.         []
  40.     if len(graph.items()) != 0:
  41.         return None
  42.     return sorted
  43.  
  44.  
  45. def topological_sort_chains(chains):
  46.     
  47.     def add_node(graph, node):
  48.         if not graph.has_key(node):
  49.             graph[node] = [
  50.                 0]
  51.         
  52.  
  53.     
  54.     def add_arc(graph, fromnode, tonode):
  55.         graph[fromnode].append(tonode)
  56.         graph[tonode][0] = graph[tonode][0] + 1
  57.  
  58.     graph = { }
  59.     for chain in chains:
  60.         if not len(chain):
  61.             continue
  62.         
  63.         add_node(graph, chain[0])
  64.         for i in range(len(chain) - 1):
  65.             add_node(graph, chain[i + 1])
  66.             add_arc(graph, chain[i], chain[i + 1])
  67.         
  68.     
  69.     oset = oset
  70.     import structures
  71.     total = oset()
  72.     for chain in chains:
  73.         total.update(chain)
  74.     
  75.     roots = [](_[1])
  76.     roots = list(total & roots)
  77.     sorted = []
  78.     while len(roots) != 0:
  79.         root = roots.pop(0)
  80.         sorted.append(root)
  81.         newroots = []
  82.         for child in graph[root][1:]:
  83.             graph[child][0] = graph[child][0] - 1
  84.             if graph[child][0] == 0:
  85.                 newroots.append(child)
  86.                 continue
  87.             []
  88.         
  89.         roots = newroots + roots
  90.         del graph[root]
  91.         continue
  92.         oset
  93.     if len(graph.items()) != 0:
  94.         return None
  95.     return sorted
  96.  
  97.