• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest May 25th, 2019 74 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.

Top