grapresso/tests/test_algorithm.py at master · kdevo/grapresso · 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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
import math

from grapresso import DiGraph, UnDiGraph
from grapresso.backends import NetworkXBackend
from grapresso.backends.memory import InMemoryBackend
from grapresso.components.path import Flow


class TestAlgorithm:
    def test_breadth_search(self, create_backend):
        g = DiGraph(create_backend()) \
            .add_edge(1, 2) \
            .add_edge(1, 2) \
            .add_edge(2, 3) \
            .add_edge(2, 1)

        visited = [n.name for n in g.perform_dfs(1, None)]
        assert 1 in visited and 2 in visited and 3 in visited and 4 not in visited

    def test_depth_search(self, create_backend):
        g = DiGraph(create_backend()) \
            .add_edge(1, 2) \
            .add_edge(1, 2) \
            .add_edge(2, 3) \
            .add_edge(2, 1)

        visited = [n.name for n in g.perform_dfs(1, None)]
        assert 1 in visited and 2 in visited and 3 in visited and 4 not in visited

    def test_depth_vs_breath_search(self, create_backend):
        g = DiGraph(create_backend()) \
            .add_edge("a", "b") \
            .add_edge("a", "c") \
            .add_edge("c", "d") \
            .add_edge('d', 'e')

        l1 = []
        g.perform_dfs('a', lambda n: l1.append(n.name))
        assert ''.join(l1) == "acdeb"

        l2 = []
        g.perform_bfs('a', lambda n: l2.append(n.name))
        assert ''.join(l2) == "abcde"

        assert l1 != l2

    def test_full_enumeration(self, create_backend):
        g = UnDiGraph(create_backend()) \
            .add_edge("Aachen", "Amsterdam", cost=230) \
            .add_edge("Amsterdam", "Brussels", cost=200) \
            .add_edge("Brussels", "Aachen", cost=142)

        print(g.enumerate("Aachen").all_tours)

        # Now also add Luxembourg:
        for city, w in zip(("Aachen", "Brussels", "Amsterdam"), (200, 212, 420)):
            g.add_edge(city, "Luxembourg", cost=w)

        #            A m s t e r d a m ---------
        #      200 /                   \ 230    |
        # Brussels---------142---------Aachen   | 420
        #     142 \                   / 200     |
        #          L u x e m b o u r g ---------

        tours = g.enumerate("Aachen", True)
        print(tours.all_tours)
        # Number of tours must backend `(n-1)!` but we ignore the "direction" - that's why we multiply with 0.5.
        # For example: "a -> b -> c -> a" is the same as "a -> c -> b -> a" (i.e. "a <-> b <-> c <-> a")
        assert len(tours.all_tours) == math.factorial(len(g._nodes_data) - 1) * 0.5

    def test_shortest_tour(self, create_backend):
        g = UnDiGraph(create_backend()) \
            .add_edge("Aachen", "Amsterdam", cost=230) \
            .add_edge("Amsterdam", "Brussels", cost=200) \
            .add_edge("Brussels", "Aachen", cost=142)

        assert g.cheapest_tour("Aachen").cost == 572

        # Now also add Luxembourg:
        for city, c in zip(("Aachen", "Brussels", "Amsterdam"), (200, 212, 420)):
            g.add_edge(city, "Luxembourg", cost=c)

        tour = g.cheapest_tour("Aachen")
        assert tour.cost == 842
        print(tour)

        # nxg = g.copy_to(UnDiGraph(NetworkXBackend(directed=False)))
        # nxg.backend.quick_draw(
        #     # Map ISO codes to the nodes so that the text fits in the boundaries:
        #     labels={'Aachen': 'AC', 'Amsterdam': 'AMS', 'Brussels': 'BR', 'Luxembourg': 'LUX'},
        #     label_pos=0.42,
        #     mark_edges=tour.edges,
        # )

    def test_residual(self, create_backend):
        graph = DiGraph(create_backend()) \
            .add_edge("Aachen", "Amsterdam", cost=230, capacity=100) \
            .add_edge("Amsterdam", "Brussels", cost=200, capacity=60) \
            .add_edge("Brussels", "Aachen", cost=142, capacity=50)

        res_graph, edges_info = graph.build_residual_graph(DiGraph(InMemoryBackend()),
                                                           Flow({graph.edge("Aachen", "Amsterdam"): 55}))
        assert res_graph.edge("Aachen", "Amsterdam").capacity == 45
        assert res_graph.edge("Amsterdam", "Aachen").capacity == 55

    def test_get_edge(self, create_backend):
        graph = UnDiGraph(create_backend()) \
            .add_edge("Aachen", "Amsterdam", cost=230, capacity=100) \
            .add_edge("Amsterdam", "Brussels", cost=200, capacity=60) \
            .add_edge("Brussels", "Aachen", cost=142, capacity=50)

        edge = graph.edge("Aachen", "Amsterdam")
        assert edge.capacity == 100