ioftools / networkxMiCe / networkxmaster / networkx / algorithms / traversal / tests / test_dfs.py @ 5cef0f13
History  View  Annotate  Download (5.36 KB)
1 
#!/usr/bin/env python


2 
from nose.tools import * 
3 
import networkx as nx 
4  
5  
6 
class TestDFS: 
7  
8 
def setUp(self): 
9 
# simple graph

10 
G = nx.Graph() 
11 
G.add_edges_from([(0, 1), (1, 2), (1, 3), (2, 4), (3, 4)]) 
12 
self.G = G

13 
# simple graph, disconnected

14 
D = nx.Graph() 
15 
D.add_edges_from([(0, 1), (2, 3)]) 
16 
self.D = D

17  
18 
def test_preorder_nodes(self): 
19 
assert_equal(list(nx.dfs_preorder_nodes(self.G, source=0)), 
20 
[0, 1, 2, 4, 3]) 
21 
assert_equal(list(nx.dfs_preorder_nodes(self.D)), [0, 1, 2, 3]) 
22  
23 
def test_postorder_nodes(self): 
24 
assert_equal(list(nx.dfs_postorder_nodes(self.G, source=0)), 
25 
[3, 4, 2, 1, 0]) 
26 
assert_equal(list(nx.dfs_postorder_nodes(self.D)), [1, 0, 3, 2]) 
27  
28 
def test_successor(self): 
29 
assert_equal(nx.dfs_successors(self.G, source=0), 
30 
{0: [1], 1: [2], 2: [4], 4: [3]}) 
31 
assert_equal(nx.dfs_successors(self.D), {0: [1], 2: [3]}) 
32  
33 
def test_predecessor(self): 
34 
assert_equal(nx.dfs_predecessors(self.G, source=0), 
35 
{1: 0, 2: 1, 3: 4, 4: 2}) 
36 
assert_equal(nx.dfs_predecessors(self.D), {1: 0, 3: 2}) 
37  
38 
def test_dfs_tree(self): 
39 
exp_nodes = sorted(self.G.nodes()) 
40 
exp_edges = [(0, 1), (1, 2), (2, 4), (4, 3)] 
41 
# Search from first node

42 
T = nx.dfs_tree(self.G, source=0) 
43 
assert_equal(sorted(T.nodes()), exp_nodes)

44 
assert_equal(sorted(T.edges()), exp_edges)

45 
# Check source=None

46 
T = nx.dfs_tree(self.G, source=None) 
47 
assert_equal(sorted(T.nodes()), exp_nodes)

48 
assert_equal(sorted(T.edges()), exp_edges)

49 
# Check source=None is the default

50 
T = nx.dfs_tree(self.G)

51 
assert_equal(sorted(T.nodes()), exp_nodes)

52 
assert_equal(sorted(T.edges()), exp_edges)

53  
54 
def test_dfs_edges(self): 
55 
edges = nx.dfs_edges(self.G, source=0) 
56 
assert_equal(list(edges), [(0, 1), (1, 2), (2, 4), (4, 3)]) 
57 
edges = nx.dfs_edges(self.D)

58 
assert_equal(list(edges), [(0, 1), (2, 3)]) 
59  
60 
def test_dfs_labeled_edges(self): 
61 
edges = list(nx.dfs_labeled_edges(self.G, source=0)) 
62 
forward = [(u, v) for (u, v, d) in edges if d == 'forward'] 
63 
assert_equal(forward, [(0, 0), (0, 1), (1, 2), (2, 4), (4, 3)]) 
64  
65 
def test_dfs_labeled_disconnected_edges(self): 
66 
edges = list(nx.dfs_labeled_edges(self.D)) 
67 
forward = [(u, v) for (u, v, d) in edges if d == 'forward'] 
68 
assert_equal(forward, [(0, 0), (0, 1), (2, 2), (2, 3)]) 
69  
70 
def test_dfs_tree_isolates(self): 
71 
G = nx.Graph() 
72 
G.add_node(1)

73 
G.add_node(2)

74 
T = nx.dfs_tree(G, source=1)

75 
assert_equal(sorted(T.nodes()), [1]) 
76 
assert_equal(sorted(T.edges()), [])

77 
T = nx.dfs_tree(G, source=None)

78 
assert_equal(sorted(T.nodes()), [1, 2]) 
79 
assert_equal(sorted(T.edges()), [])

80  
81  
82 
class TestDepthLimitedSearch: 
83  
84 
def setUp(self): 
85 
# a tree

86 
G = nx.Graph() 
87 
nx.add_path(G, [0, 1, 2, 3, 4, 5, 6]) 
88 
nx.add_path(G, [2, 7, 8, 9, 10]) 
89 
self.G = G

90 
# a disconnected graph

91 
D = nx.Graph() 
92 
D.add_edges_from([(0, 1), (2, 3)]) 
93 
nx.add_path(D, [2, 7, 8, 9, 10]) 
94 
self.D = D

95  
96 
def dls_test_preorder_nodes(self): 
97 
assert_equal(list(nx.dfs_preorder_nodes(self.G, source=0, 
98 
depth_limit=2)), [0, 1, 2]) 
99 
assert_equal(list(nx.dfs_preorder_nodes(self.D, source=1, 
100 
depth_limit=2)), ([1, 0])) 
101  
102 
def dls_test_postorder_nodes(self): 
103 
assert_equal(list(nx.dfs_postorder_nodes(self.G, 
104 
source=3, depth_limit=3)), [1, 7, 2, 5, 4, 3]) 
105 
assert_equal(list(nx.dfs_postorder_nodes(self.D, 
106 
source=2, depth_limit=2)), ([3, 7, 2])) 
107  
108 
def dls_test_successor(self): 
109 
result = nx.dfs_successors(self.G, source=4, depth_limit=3) 
110 
assert_equal({n: set(v) for n, v in result.items()}, 
111 
{2: {1, 7}, 3: {2}, 4: {3, 5}, 5: {6}}) 
112 
result = nx.dfs_successors(self.D, source=7, depth_limit=2) 
113 
assert_equal({n: set(v) for n, v in result.items()}, 
114 
{8: {9}, 2: {3}, 7: {8, 2}}) 
115  
116 
def dls_test_predecessor(self): 
117 
assert_equal(nx.dfs_predecessors(self.G, source=0, depth_limit=3), 
118 
{1: 0, 2: 1, 3: 2, 7: 2}) 
119 
assert_equal(nx.dfs_predecessors(self.D, source=2, depth_limit=3), 
120 
{8: 7, 9: 8, 3: 2, 7: 2}) 
121  
122 
def test_dls_tree(self): 
123 
T = nx.dfs_tree(self.G, source=3, depth_limit=1) 
124 
assert_equal(sorted(T.edges()), [(3, 2), (3, 4)]) 
125  
126 
def test_dls_edges(self): 
127 
edges = nx.dfs_edges(self.G, source=9, depth_limit=4) 
128 
assert_equal(list(edges), [(9, 8), (8, 7), 
129 
(7, 2), (2, 1), (2, 3), (9, 10)]) 
130  
131 
def test_dls_labeled_edges(self): 
132 
edges = list(nx.dfs_labeled_edges(self.G, source=5, depth_limit=1)) 
133 
forward = [(u, v) for (u, v, d) in edges if d == 'forward'] 
134 
assert_equal(forward, [(5, 5), (5, 4), (5, 6)]) 
135  
136 
def test_dls_labeled_disconnected_edges(self): 
137 
edges = list(nx.dfs_labeled_edges(self.G, source=6, depth_limit=2)) 
138 
forward = [(u, v) for (u, v, d) in edges if d == 'forward'] 
139 
assert_equal(forward, [(6, 6), (6, 5), (5, 4)]) 