Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / traversal / tests / test_edgedfs.py @ 5cef0f13

History | View | Annotate | Download (4.72 KB)

1
from nose.tools import *
2

    
3
import networkx as nx
4

    
5
edge_dfs = nx.algorithms.edge_dfs
6

    
7
FORWARD = nx.algorithms.edgedfs.FORWARD
8
REVERSE = nx.algorithms.edgedfs.REVERSE
9

    
10
# These tests can fail with hash randomization. The easiest and clearest way
11
# to write these unit tests is for the edges to be output in an expected total
12
# order, but we cannot guarantee the order amongst outgoing edges from a node,
13
# unless each class uses an ordered data structure for neighbors. This is
14
# painful to do with the current API. The alternative is that the tests are
15
# written (IMO confusingly) so that there is not a total order over the edges,
16
# but only a partial order. Due to the small size of the graphs, hopefully
17
# failures due to hash randomization will not occur. For an example of how
18
# this can fail, see TestEdgeDFS.test_multigraph.
19

    
20

    
21
class TestEdgeDFS(object):
22
    def setUp(self):
23
        self.nodes = [0, 1, 2, 3]
24
        self.edges = [(0, 1), (1, 0), (1, 0), (2, 1), (3, 1)]
25

    
26
    def test_empty(self):
27
        G = nx.Graph()
28
        edges = list(edge_dfs(G))
29
        assert_equal(edges, [])
30

    
31
    def test_graph(self):
32
        G = nx.Graph(self.edges)
33
        x = list(edge_dfs(G, self.nodes))
34
        x_ = [(0, 1), (1, 2), (1, 3)]
35
        assert_equal(x, x_)
36

    
37
    def test_digraph(self):
38
        G = nx.DiGraph(self.edges)
39
        x = list(edge_dfs(G, self.nodes))
40
        x_ = [(0, 1), (1, 0), (2, 1), (3, 1)]
41
        assert_equal(x, x_)
42

    
43
    def test_digraph_orientation_invalid(self):
44
        G = nx.DiGraph(self.edges)
45
        edge_iterator = edge_dfs(G, self.nodes, orientation='hello')
46
        assert_raises(nx.NetworkXError, list, edge_iterator)
47

    
48
    def test_digraph_orientation_none(self):
49
        G = nx.DiGraph(self.edges)
50
        x = list(edge_dfs(G, self.nodes, orientation=None))
51
        x_ = [(0, 1), (1, 0), (2, 1), (3, 1)]
52
        assert_equal(x, x_)
53

    
54
    def test_digraph_orientation_original(self):
55
        G = nx.DiGraph(self.edges)
56
        x = list(edge_dfs(G, self.nodes, orientation='original'))
57
        x_ = [(0, 1, FORWARD), (1, 0, FORWARD),
58
              (2, 1, FORWARD), (3, 1, FORWARD)]
59
        assert_equal(x, x_)
60

    
61
    def test_digraph2(self):
62
        G = nx.DiGraph()
63
        nx.add_path(G, range(4))
64
        x = list(edge_dfs(G, [0]))
65
        x_ = [(0, 1), (1, 2), (2, 3)]
66
        assert_equal(x, x_)
67

    
68
    def test_digraph_rev(self):
69
        G = nx.DiGraph(self.edges)
70
        x = list(edge_dfs(G, self.nodes, orientation='reverse'))
71
        x_ = [(1, 0, REVERSE), (0, 1, REVERSE),
72
              (2, 1, REVERSE), (3, 1, REVERSE)]
73
        assert_equal(x, x_)
74

    
75
    def test_digraph_rev2(self):
76
        G = nx.DiGraph()
77
        nx.add_path(G, range(4))
78
        x = list(edge_dfs(G, [3], orientation='reverse'))
79
        x_ = [(2, 3, REVERSE), (1, 2, REVERSE), (0, 1, REVERSE)]
80
        assert_equal(x, x_)
81

    
82
    def test_multigraph(self):
83
        G = nx.MultiGraph(self.edges)
84
        x = list(edge_dfs(G, self.nodes))
85
        x_ = [(0, 1, 0), (1, 0, 1), (0, 1, 2), (1, 2, 0), (1, 3, 0)]
86
        # This is an example of where hash randomization can break.
87
        # There are 3! * 2 alternative outputs, such as:
88
        #    [(0, 1, 1), (1, 0, 0), (0, 1, 2), (1, 3, 0), (1, 2, 0)]
89
        # But note, the edges (1,2,0) and (1,3,0) always follow the (0,1,k)
90
        # edges. So the algorithm only guarantees a partial order. A total
91
        # order is guaranteed only if the graph data structures are ordered.
92
        assert_equal(x, x_)
93

    
94
    def test_multidigraph(self):
95
        G = nx.MultiDiGraph(self.edges)
96
        x = list(edge_dfs(G, self.nodes))
97
        x_ = [(0, 1, 0), (1, 0, 0), (1, 0, 1), (2, 1, 0), (3, 1, 0)]
98
        assert_equal(x, x_)
99

    
100
    def test_multidigraph_rev(self):
101
        G = nx.MultiDiGraph(self.edges)
102
        x = list(edge_dfs(G, self.nodes, orientation='reverse'))
103
        x_ = [(1, 0, 0, REVERSE),
104
              (0, 1, 0, REVERSE),
105
              (1, 0, 1, REVERSE),
106
              (2, 1, 0, REVERSE),
107
              (3, 1, 0, REVERSE)]
108
        assert_equal(x, x_)
109

    
110
    def test_digraph_ignore(self):
111
        G = nx.DiGraph(self.edges)
112
        x = list(edge_dfs(G, self.nodes, orientation='ignore'))
113
        x_ = [(0, 1, FORWARD), (1, 0, FORWARD),
114
              (2, 1, REVERSE), (3, 1, REVERSE)]
115
        assert_equal(x, x_)
116

    
117
    def test_digraph_ignore2(self):
118
        G = nx.DiGraph()
119
        nx.add_path(G, range(4))
120
        x = list(edge_dfs(G, [0], orientation='ignore'))
121
        x_ = [(0, 1, FORWARD), (1, 2, FORWARD), (2, 3, FORWARD)]
122
        assert_equal(x, x_)
123

    
124
    def test_multidigraph_ignore(self):
125
        G = nx.MultiDiGraph(self.edges)
126
        x = list(edge_dfs(G, self.nodes, orientation='ignore'))
127
        x_ = [(0, 1, 0, FORWARD), (1, 0, 0, FORWARD),
128
              (1, 0, 1, REVERSE), (2, 1, 0, REVERSE),
129
              (3, 1, 0, REVERSE)]
130
        assert_equal(x, x_)