diff options
Diffstat (limited to 'lib/python2.7/site-packages/setoolsgui/networkx/algorithms/traversal/tests/test_dfs.py')
-rw-r--r-- | lib/python2.7/site-packages/setoolsgui/networkx/algorithms/traversal/tests/test_dfs.py | 68 |
1 files changed, 68 insertions, 0 deletions
diff --git a/lib/python2.7/site-packages/setoolsgui/networkx/algorithms/traversal/tests/test_dfs.py b/lib/python2.7/site-packages/setoolsgui/networkx/algorithms/traversal/tests/test_dfs.py new file mode 100644 index 0000000..9fad985 --- /dev/null +++ b/lib/python2.7/site-packages/setoolsgui/networkx/algorithms/traversal/tests/test_dfs.py @@ -0,0 +1,68 @@ +#!/usr/bin/env python +from nose.tools import * +import networkx as nx + +class TestDFS: + + def setUp(self): + # simple graph + G=nx.Graph() + G.add_edges_from([(0,1),(1,2),(1,3),(2,4),(3,4)]) + self.G=G + # simple graph, disconnected + D=nx.Graph() + D.add_edges_from([(0,1),(2,3)]) + self.D=D + + + def test_preorder_nodes(self): + assert_equal(list(nx.dfs_preorder_nodes(self.G,source=0)), + [0, 1, 2, 4, 3]) + assert_equal(list(nx.dfs_preorder_nodes(self.D)),[0, 1, 2, 3]) + + def test_postorder_nodes(self): + assert_equal(list(nx.dfs_postorder_nodes(self.G,source=0)), + [3, 4, 2, 1, 0]) + assert_equal(list(nx.dfs_postorder_nodes(self.D)),[1, 0, 3, 2]) + + def test_successor(self): + assert_equal(nx.dfs_successors(self.G,source=0), + {0: [1], 1: [2], 2: [4], 4: [3]}) + assert_equal(nx.dfs_successors(self.D), {0: [1], 2: [3]}) + + def test_predecessor(self): + assert_equal(nx.dfs_predecessors(self.G,source=0), + {1: 0, 2: 1, 3: 4, 4: 2}) + assert_equal(nx.dfs_predecessors(self.D), {1: 0, 3: 2}) + + def test_dfs_tree(self): + T=nx.dfs_tree(self.G,source=0) + assert_equal(sorted(T.nodes()),sorted(self.G.nodes())) + assert_equal(sorted(T.edges()),[(0, 1), (1, 2), (2, 4), (4, 3)]) + + def test_dfs_edges(self): + edges=nx.dfs_edges(self.G,source=0) + assert_equal(list(edges),[(0, 1), (1, 2), (2, 4), (4, 3)]) + edges=nx.dfs_edges(self.D) + assert_equal(list(edges),[(0, 1), (2, 3)]) + + def test_dfs_labeled_edges(self): + edges=list(nx.dfs_labeled_edges(self.G,source=0)) + forward=[(u,v) for (u,v,d) in edges if d['dir']=='forward'] + assert_equal(forward,[(0,0), (0, 1), (1, 2), (2, 4), (4, 3)]) + + def test_dfs_labeled_disconnected_edges(self): + edges=list(nx.dfs_labeled_edges(self.D)) + forward=[(u,v) for (u,v,d) in edges if d['dir']=='forward'] + assert_equal(forward,[(0, 0), (0, 1), (2, 2), (2, 3)]) + + def test_dfs_tree_isolates(self): + G = nx.Graph() + G.add_node(1) + G.add_node(2) + T=nx.dfs_tree(G,source=1) + assert_equal(sorted(T.nodes()),[1]) + assert_equal(sorted(T.edges()),[]) + T=nx.dfs_tree(G,source=None) + assert_equal(sorted(T.nodes()),[1, 2]) + assert_equal(sorted(T.edges()),[]) |