SHARE
TWEET

Untitled

a guest May 25th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from collections import deque
  2. import random
  3. class Graph:
  4.     """Trida Graph drzi graf reprezentovany matici sousednosti.
  5.     Atributy:
  6.         size: velikost (pocet vrcholu) grafu
  7.         matrix: matice sousednosti
  8.                 [u][v] reprezentuje hranu u -> v
  9.     """
  10.  
  11.     def __init__(self, size):
  12.         self.size = size
  13.         self.matrix = [[False] * size for _ in range(size)]
  14.         self.color =  ['w'] * size
  15.         self.stack = []
  16.         self.label = [None]*size
  17.  
  18.  
  19.  
  20.  
  21. def Transpose(graph):
  22.     rev_graph = Graph(graph.size)
  23.  
  24.     for i in range(graph.size):
  25.         for j in range(graph.size):
  26.             rev_graph.matrix[i][j] = graph.matrix[j][i]
  27.     return rev_graph
  28.  
  29. def push_DFS(graph,u):
  30.     graph.color[u] = 'g'
  31.     for i in range(graph.size):
  32.         if graph.matrix[u][i] == True:
  33.             if graph.color[i] == 'w':
  34.                 push_DFS(graph,i)
  35.     graph.color[u] = 'b'
  36.     graph.stack.append(u)
  37.  
  38. def label_DFS(graph,u,count):
  39.     graph.color[u] = 'g'
  40.     for i in range(graph.size):
  41.         if graph.matrix[u][i] == True:
  42.             if graph.color[i] == 'w':
  43.                 label_DFS(graph,i,count)
  44.     graph.color[u] = 'b'
  45.     graph.label[u] = count
  46.  
  47.  
  48.  
  49.  
  50. def kosaraju_sharir(graph):
  51.  
  52.     for i in range(graph.size):
  53.         if graph.color[i] == 'w':
  54.             push_DFS(graph,i)
  55.     count = 0
  56.  
  57.     rev_graph = Transpose(graph)
  58.     graph.color = ['w'] * graph.size
  59.     while graph.stack:
  60.         u = graph.stack.pop()
  61.         if rev_graph.color[u] == 'w':
  62.             count += 1
  63.             label_DFS(rev_graph,u,count)
  64.  
  65.  
  66.     print(rev_graph.label)
  67.     ret = {}
  68.     for i in range(len(rev_graph.label)):
  69.         ret.setdefault(rev_graph.label[i],[])
  70.         ret[rev_graph.label[i]].append(i)
  71.     return list(ret.values())
  72.  
  73.  
  74.  
  75. g = Graph(4)
  76. g.matrix = [[1, 1, 1, 1],
  77. [0, 1, 1, 1],
  78. [0, 1, 0, 0],
  79. [1, 1, 0, 1]]
  80. print(kosaraju_sharir(g))
  81.  
  82.  
  83. def test_generated_strong_compo():
  84.     d = 0
  85.     while d < 1:
  86.         # Generate random graph
  87.         test_int = 4
  88.         test_graph = Graph(test_int)
  89.         test_matrix = []
  90.         for i in range(test_int):
  91.             test_matrix.append([])
  92.             for j in range(test_int):
  93.                 if random.randint(0, 1) == 0:
  94.                     test_matrix[i].append(0)
  95.                 else:
  96.                     test_matrix[i].append(1)
  97.         test_graph.matrix = test_matrix
  98.  
  99.         # Compute strong components
  100.         components = kosaraju_sharir(test_graph)
  101.         if len(components) == 4:
  102.             continue
  103.  
  104.         # Print out its matrix
  105.         print("Graph no." + str(d + 1))
  106.         for i in range(test_int):
  107.             print(test_matrix[i])
  108.  
  109.         # Print out its strong components
  110.         print("Strong components no." + str(d + 1))
  111.         for j in range(len(components)):
  112.             print(components[j])
  113.  
  114.         d += 1
  115.  
  116.  
  117. test_generated_strong_compo()
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