LabAlg17/tests.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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
from graph import Graph
from scc import SCC
from timeit import default_timer as timer


class Tests:

    def __init__(self):
        self.grandezza_fissata = 5
        self.grandezze_crescenti = range(1, 30)

        self.prob_fissata = 2
        self.prob_crescenti = range(0, 11)

    # Variazione numero di scc per grafi di dimensione crescente e probabilita' fissata 0.2
    def execute_first(self):
        numbers = []
        for i in self.grandezze_crescenti:
            g = Graph(i)
            m = g.matrice_adiacenza(self.prob_fissata)
            n, _ = SCC(m).scc()
            numbers.append(n)
        return numbers

    # Variazione numero di scc per grafi di dimensione fissata 5 e probabilita' crescente
    def execute_second(self):
        numbers = []
        for i in self.prob_crescenti:
            g = Graph(self.grandezza_fissata)
            m = g.matrice_adiacenza(i)
            n, _ = SCC(m).scc()
            numbers.append(n)
        return numbers

    # Variazione grandezza massima scc per grafi di dimensione crescente e probabilita' fissata 0.2
    def execute_third(self):
        grandezze = []
        for i in self.grandezze_crescenti:
            g = Graph(i)
            m = g.matrice_adiacenza(self.prob_fissata)
            _, d = SCC(m).scc()

            grandezza_max = 1
            for j in range(len(d)):
                if len(d[j]) > grandezza_max:
                    grandezza_max = len(d[j])
            grandezze.append(grandezza_max)

        return grandezze

    # Variazione dei tempi dell'algoritmo per trovare scc per grafi di dimensione crescente e probabilita' fissata 0.2
    def execute_fourth(self):
        tempi = []
        for i in self.grandezze_crescenti:
            g = Graph(i)
            m = g.matrice_adiacenza(self.prob_fissata)
            start = timer()
            _, _ = SCC(m).scc()
            end = timer()
            tempi.append(end-start)
        return tempi

    def execute_fifth(self):
        for i in [5, 10, 15, 20, 25, 30, 35, 40]:
            scc = []
            vol = []
            g = Graph(i)

            for j in range(0, 11, 1):
                m = g.matrice_adiacenza(j)
                n, d = SCC(m).scc()

                grandezza_max = 1
                for a in range(len(d)):
                    if len(d[a]) > grandezza_max:
                        grandezza_max = len(d[a])

                scc.append(grandezza_max)
                vol.append(grandezza_max)

            # Stampa sequenza di valori separati da &, utile per tabella LaTeX
            print ' & '.join([str(a) for a in scc])
            print ' & '.join([str(a) for a in vol])