forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
test_graph.py
44 lines (36 loc) · 1.18 KB
/
test_graph.py
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
from algorithms.graph import Tarjan
import unittest
class TestTarjan(unittest.TestCase):
"""
Test for the file tarjan.py
Arguments:
unittest {[type]} -- [description]
"""
def test_tarjan_example_1(self):
# Graph from https://en.wikipedia.org/wiki/File:Scc.png
example = {
'A': ['B'],
'B': ['C', 'E', 'F'],
'C': ['D', 'G'],
'D': ['C', 'H'],
'E': ['A', 'F'],
'F': ['G'],
'G': ['F'],
'H': ['D', 'G']
}
g = Tarjan(example)
self.assertEqual(g.sccs, [['F', 'G'], ['C', 'D', 'H'], ['A', 'B', 'E']])
def test_tarjan_example_2(self):
# Graph from https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm#/media/File:Tarjan%27s_Algorithm_Animation.gif
example = {
'A': ['E'],
'B': ['A'],
'C': ['B', 'D'],
'D': ['C'],
'E': ['B'],
'F': ['B', 'E', 'G'],
'G': ['F', 'C'],
'H': ['G', 'H', 'D']
}
g = Tarjan(example)
self.assertEqual(g.sccs, [['A', 'B', 'E'], ['C', 'D'], ['F', 'G'], ['H']])