test_graph.py 5.86 KB
Newer Older
Bram Schoenmakers's avatar
Bram Schoenmakers committed
1
# Topydo - A todo.txt client written in Python.
2
# Copyright (C) 2014 - 2015 Bram Schoenmakers <bram@topydo.org>
Bram Schoenmakers's avatar
Bram Schoenmakers committed
3
#
Bram Schoenmakers's avatar
Bram Schoenmakers committed
4 5 6 7
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
Bram Schoenmakers's avatar
Bram Schoenmakers committed
8
#
Bram Schoenmakers's avatar
Bram Schoenmakers committed
9 10 11 12
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
Bram Schoenmakers's avatar
Bram Schoenmakers committed
13
#
Bram Schoenmakers's avatar
Bram Schoenmakers committed
14 15 16
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.

17
import unittest
18

MinchinWeb's avatar
MinchinWeb committed
19
from topydo.lib.Graph import DirectedGraph
20

21 22
from .topydo_testcase import TopydoTest

MinchinWeb's avatar
MinchinWeb committed
23

Bram Schoenmakers's avatar
Bram Schoenmakers committed
24
class GraphTest(TopydoTest):
25
    def setUp(self):
26
        super().setUp()
27

Bram Schoenmakers's avatar
Bram Schoenmakers committed
28
        self.graph = DirectedGraph()
29

30
        self.graph.add_edge(1, 2, 1)
31
        self.graph.add_edge(2, 4, "Test")
32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
        self.graph.add_edge(4, 3)
        self.graph.add_edge(4, 6)
        self.graph.add_edge(6, 2)
        self.graph.add_edge(1, 3)
        self.graph.add_edge(3, 5)

        #         1
        #       /   \
        #      v     v
        #    />2   />3
        #   /  |  /  |
        #  /   v /   v
        # 6 <- 4     5

    def test_has_nodes(self):
        for i in range(1, 7):
            self.assertTrue(self.graph.has_node(i))

50 51 52 53 54
    def test_has_edge_ids(self):
        self.assertTrue(self.graph.has_edge_id(1))
        self.assertTrue(self.graph.has_edge_id("Test"))
        self.assertFalse(self.graph.has_edge_id("1"))

55
    def test_incoming_neighbors1(self):
56
        self.assertEqual(self.graph.incoming_neighbors(1), set())
57

58 59 60
    def test_edge_id_of_nonexistent_edge(self):
        self.assertFalse(self.graph.edge_id(1, 6))

61
    def test_incoming_neighbors2(self):
62
        self.assertEqual(self.graph.incoming_neighbors(2), set([1, 6]))
63 64

    def test_incoming_neighbors3(self):
65
        self.assertEqual(self.graph.incoming_neighbors(1, True), set())
66 67

    def test_incoming_neighbors4(self):
MinchinWeb's avatar
MinchinWeb committed
68 69
        self.assertEqual(self.graph.incoming_neighbors(5, True),
                         set([1, 2, 3, 4, 6]))
70 71

    def test_outgoing_neighbors1(self):
72
        self.assertEqual(self.graph.outgoing_neighbors(1), set([2, 3]))
73 74

    def test_outgoing_neighbors2(self):
75
        self.assertEqual(self.graph.outgoing_neighbors(2), set([4]))
76 77

    def test_outgoing_neighbors3(self):
MinchinWeb's avatar
MinchinWeb committed
78 79
        self.assertEqual(self.graph.outgoing_neighbors(1, True),
                         set([2, 3, 4, 5, 6]))
80 81

    def test_outgoing_neighbors4(self):
82
        self.assertEqual(self.graph.outgoing_neighbors(3), set([5]))
83 84

    def test_outgoing_neighbors5(self):
85
        self.assertEqual(self.graph.outgoing_neighbors(5), set([]))
86 87 88 89 90 91

    def test_remove_edge1(self):
        self.graph.remove_edge(1, 2)

        self.assertFalse(self.graph.has_path(1, 4))
        self.assertTrue(self.graph.has_path(2, 4))
92
        self.assertFalse(self.graph.has_edge_id(1))
93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146

    def test_remove_edge2(self):
        self.graph.remove_edge(3, 5, True)

        self.assertFalse(self.graph.has_path(1, 5))
        self.assertFalse(self.graph.has_node(5))

    def test_remove_edge3(self):
        self.graph.remove_edge(3, 5, False)

        self.assertFalse(self.graph.has_path(1, 5))
        self.assertTrue(self.graph.has_node(5))

    def test_remove_edge4(self):
        """ Remove non-existing edge. """
        self.graph.remove_edge(4, 5)

    def test_remove_edge5(self):
        self.graph.remove_edge(3, 5, True)

        self.assertFalse(self.graph.has_path(1, 5))
        self.assertFalse(self.graph.has_node(5))

    def test_remove_edge6(self):
        self.graph.remove_edge(1, 3, True)

        self.assertTrue(self.graph.has_path(1, 5))

    def test_remove_node1(self):
        self.graph.remove_node(2)

        self.assertTrue(self.graph.has_node(1))
        self.assertTrue(self.graph.has_node(4))
        self.assertTrue(self.graph.has_node(6))
        self.assertFalse(self.graph.has_node(2))

        self.assertFalse(self.graph.has_edge(2, 4))
        self.assertFalse(self.graph.has_edge(1, 2))

    def test_remove_node2(self):
        self.graph.remove_node(3, True)

        self.assertFalse(self.graph.has_node(5))
        self.assertFalse(self.graph.has_edge(1, 3))
        self.assertFalse(self.graph.has_edge(3, 5))
        self.assertFalse(self.graph.has_path(1, 5))

    def test_remove_node3(self):
        self.graph.remove_node(3, False)

        self.assertTrue(self.graph.has_node(5))
        self.assertFalse(self.graph.has_edge(1, 3))
        self.assertFalse(self.graph.has_edge(3, 5))
        self.assertFalse(self.graph.has_path(1, 5))
147 148 149 150 151 152 153

    def test_transitive_reduce1(self):
        self.graph.transitively_reduce()

        self.assertTrue(self.graph.has_edge(4, 3))
        self.assertFalse(self.graph.has_edge(1, 3))

154 155 156 157 158 159
    def test_add_double_edge(self):
        self.graph.add_edge(1, 3)
        self.graph.remove_edge(1, 3)

        # the one and only edge must be removed now
        self.assertFalse(self.graph.has_edge(1, 3))
160

161 162 163 164 165 166 167 168 169
    def test_add_double_edge_with_id(self):
        self.graph.add_edge(1, 3, "Dummy")
        self.assertFalse(self.graph.has_edge_id("Dummy"))

        self.graph.remove_edge(1, 3)

        # the one and only edge must be removed now
        self.assertFalse(self.graph.has_edge(1, 3))

170
    def test_str_output(self):
171
        out = 'digraph g {\n  1\n  1 -> 2 [label="1"]\n  1 -> 3\n  2\n  2 -> 4 [label="Test"]\n  3\n  3 -> 5\n  4\n  4 -> 3\n  4 -> 6\n  5\n  6\n  6 -> 2\n}\n'
172
        self.assertEqual(str(self.graph), out)
173 174 175

    def test_dot_output_without_labels(self):
        out = 'digraph g {\n  1\n  1 -> 2\n  1 -> 3\n  2\n  2 -> 4\n  3\n  3 -> 5\n  4\n  4 -> 3\n  4 -> 6\n  5\n  6\n  6 -> 2\n}\n'
176
        self.assertEqual(self.graph.dot(False), out)
177 178 179

if __name__ == '__main__':
    unittest.main()