home *** CD-ROM | disk | FTP | other *** search
/ Maximum CD 2011 February / maximum-cd-2011-02.iso / DiscContents / digsby_setup85.exe / lib / util / primitives / topo_sort.pyo (.txt) < prev    next >
Encoding:
Python Compiled Bytecode  |  2010-11-24  |  2.7 KB  |  125 lines
  1. # Source Generated with Decompyle++
  2. # File: in.pyo (Python 2.6)
  3.  
  4. from structures import oset
  5. from util.primitives.mapping import odict, dictreverse
  6. from collections import defaultdict
  7.  
  8. def add_node(graph, incidence, node):
  9.     graph.setdefault(node, oset())
  10.     incidence.setdefault(node, 0)
  11.  
  12.  
  13. def add_arc(graph, incidence, u, v):
  14.     graph[u].add(v)
  15.     incidence[v] = incidence.get(v, 0) + 1
  16.  
  17.  
  18. def create_graph(chains, incidence):
  19.     graph = odict()
  20.     for chain in chains:
  21.         if not len(chain):
  22.             continue
  23.         
  24.         add_node(graph, incidence, chain[0])
  25.         for i in range(len(chain)):
  26.             add_node(graph, incidence, chain[i])
  27.             for j in range(i, len(chain)):
  28.                 add_arc(graph, incidence, chain[i], chain[j])
  29.             
  30.         
  31.     
  32.     return graph
  33.  
  34. WHITE = 'WHITE'
  35. BLACK = 'BLACK'
  36. GREY = 'GREY'
  37.  
  38. def DFS(G, color, pred, disc, fin):
  39.     for u in G:
  40.         color[u] = WHITE
  41.         pred[u] = None
  42.     
  43.     time = 0
  44.     for u in G:
  45.         if color[u] == WHITE:
  46.             time = DFSvisit(u, G, color, pred, disc, fin, time)
  47.             continue
  48.     
  49.  
  50.  
  51. def DFSvisit(u, G, color, pred, disc, fin, time):
  52.     color[u] = GREY
  53.     time = time + 1
  54.     disc[u] = time
  55.     for v in G[u]:
  56.         if color[v] == WHITE:
  57.             pred[v] = u
  58.             time = DFSvisit(v, G, color, pred, disc, fin, time)
  59.             continue
  60.     
  61.     color[u] = BLACK
  62.     time = time + 1
  63.     fin[u] = time
  64.     return time
  65.  
  66.  
  67. def topological_sort_chains(chains):
  68.     incidence = dict()
  69.     G = create_graph(chains, incidence)
  70.     color = { }
  71.     pred = { }
  72.     disc = { }
  73.     fin = { }
  74.     DFS(G, color, pred, disc, fin)
  75.     fin2 = dictreverse(fin)
  76.     fin3 = []
  77.     for i in sorted(fin2, reverse = True):
  78.         fin3.append(fin2[i])
  79.     
  80.     return fin3
  81.  
  82. if __name__ == '__main__':
  83.     incidence = dict()
  84.     G = create_graph([
  85.         [
  86.             6,
  87.             0,
  88.             5],
  89.         [
  90.             5,
  91.             6,
  92.             9,
  93.             3,
  94.             8,
  95.             7,
  96.             4,
  97.             2],
  98.         [
  99.             1,
  100.             0],
  101.         [
  102.             5,
  103.             6,
  104.             1,
  105.             0,
  106.             9,
  107.             3,
  108.             8,
  109.             7,
  110.             4,
  111.             2]], incidence)
  112.     color = { }
  113.     pred = { }
  114.     disc = { }
  115.     fin = { }
  116.     DFS(G, color, pred, disc, fin)
  117.     from mapping import dictreverse
  118.     fin2 = dictreverse(fin)
  119.     fin3 = []
  120.     for i in sorted(fin2, reverse = True):
  121.         fin3.append(fin2[i])
  122.     
  123.     print fin3
  124.  
  125.