LabAlg17/scc.py at master · n3d1117/LabAlg17 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
from dfs import DFS
import numpy as np


class SCC:

    def __init__(self, matrice_adiacenza):
        self.matrice_adiacenza = matrice_adiacenza

    def scc(self):

        # calcola i tempi di completamento per ciascun vertice
        dfs = DFS(self.matrice_adiacenza)

        # memorizzo i vertici in una variabile locale
        vertici = dfs.vertici

        # calcolo il grafo trasposto formato dagli archi del grafo originale con direzioni invertite
        matrice_trasposta = self.trasposta(self.matrice_adiacenza)

        # chiamo DFS su grafo trasposto passando i vertici calcolati in precedenza
        dfs_t = DFS(matrice_trasposta, vertici)

        return dfs_t.numero_di_scc, dfs_t.dizionario_scc

    @staticmethod
    def trasposta(matrice):
        return np.array(matrice).transpose()

if __name__ == '__main__':

    # from graph import Graph
    # a = Graph(5)
    # m = a.matrice_adiacenza(3)

    # Esempio libro
    m = [[0, 1, 0, 0, 0, 0, 0, 0],
         [0, 0, 1, 0, 1, 1, 0, 0],
         [0, 0, 0, 1, 0, 0, 1, 0],
         [0, 0, 1, 0, 0, 0, 0, 1],
         [1, 0, 0, 0, 0, 1, 0, 0],
         [0, 0, 0, 0, 0, 0, 1, 0],
         [0, 0, 0, 0, 0, 1, 0, 1],
         [0, 0, 0, 0, 0, 0, 0, 1]]

    n, d = SCC(m).scc()

    print "ho trovato %s componenti fortemente connesse!" % n

    for i in range(n):
        print "la scc #%s ha %s vertici: %s" % (i + 1, len(d[i]), d[i])