diff options
author | Sylvain Th?nault <sylvain.thenault@logilab.fr> | 2009-11-12 11:30:13 +0100 |
---|---|---|
committer | Sylvain Th?nault <sylvain.thenault@logilab.fr> | 2009-11-12 11:30:13 +0100 |
commit | 1b4d12cbd2ab6e6e586743df592648faa42fa26e (patch) | |
tree | 3712c032158bbca5d0f6cb75834c2490271f6698 | |
parent | 6505d63fb9e53b28ff54b60954f63a9840959905 (diff) | |
download | logilab-common-1b4d12cbd2ab6e6e586743df592648faa42fa26e.tar.gz |
fix has_path returned value to include the destination node, else we get
an empty list which makes think there is no path (test added)
-rw-r--r-- | ChangeLog | 2 | ||||
-rw-r--r-- | graph.py | 6 | ||||
-rw-r--r-- | test/unittest_graph.py | 18 |
3 files changed, 21 insertions, 5 deletions
@@ -6,6 +6,8 @@ ChangeLog for logilab.common - proper bytes and time option types support - make Method usable as 'callback' value - fix #8849 Using plugins, options and .pylintrc crashes PyLint + * graph: fix has_path returned value to include the destination node, else we get + an empty list which makes think there is no path (test added) 2009-08-26 -- 0.45.0 * added function for parsing XML processing instructions @@ -189,16 +189,16 @@ def has_path(graph_dict, fromnode, tonode, path=None): node has key associated to a list of nodes directly reachable from it. Return None if no path exists to go from `fromnode` to `tonode`, else the - first path found + first path found (as a list including the destination node at last) """ if path is None: path = [] elif fromnode in path: - return False + return None path.append(fromnode) for destnode in graph_dict[fromnode]: if destnode == tonode or has_path(graph_dict, destnode, tonode, path): - return path[1:] + return path[1:] + [tonode] path.pop() return None diff --git a/test/unittest_graph.py b/test/unittest_graph.py index b8f5394..ce272e5 100644 --- a/test/unittest_graph.py +++ b/test/unittest_graph.py @@ -1,9 +1,9 @@ # unit tests for the cache module from logilab.common.testlib import TestCase, unittest_main -from logilab.common.graph import get_cycles +from logilab.common.graph import get_cycles, has_path -class getCycleTestCase(TestCase): +class getCyclesTC(TestCase): def test_known0(self): self.assertEqual(get_cycles({1:[2], 2:[3], 3:[1]}), [[1, 2, 3]]) @@ -15,5 +15,19 @@ class getCycleTestCase(TestCase): self.assertEqual(get_cycles({1:[2], 2:[3], 3:[0], 0:[]}), []) +class hasPathTC(TestCase): + + def test_direct_connection(self): + self.assertEquals(has_path({'A': ['B'], 'B': ['A']}, 'A', 'B'), ['B']) + + def test_indirect_connection(self): + self.assertEquals(has_path({'A': ['B'], 'B': ['A', 'C'], 'C': ['B']}, 'A', 'C'), ['B', 'C']) + + def test_no_connection(self): + self.assertEquals(has_path({'A': ['B'], 'B': ['A']}, 'A', 'C'), None) + + def test_cycle(self): + self.assertEquals(has_path({'A': ['A']}, 'A', 'B'), None) + if __name__ == "__main__": unittest_main() |