/usr/lib/python3/dist-packages/networkx/algorithms/traversal/tests/test_edgedfs.py is in python3-networkx 1.11-1ubuntu2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 | from nose.tools import *
import networkx as nx
edge_dfs = nx.algorithms.edge_dfs
FORWARD = nx.algorithms.edgedfs.FORWARD
REVERSE = nx.algorithms.edgedfs.REVERSE
# These tests can fail with hash randomization. The easiest and clearest way
# to write these unit tests is for the edges to be output in an expected total
# order, but we cannot guarantee the order amongst outgoing edges from a node,
# unless each class uses an ordered data structure for neighbors. This is
# painful to do with the current API. The alternative is that the tests are
# written (IMO confusingly) so that there is not a total order over the edges,
# but only a partial order. Due to the small size of the graphs, hopefully
# failures due to hash randomization will not occur. For an example of how
# this can fail, see TestEdgeDFS.test_multigraph.
class TestEdgeDFS(object):
def setUp(self):
self.nodes = [0, 1, 2, 3]
self.edges = [(0, 1), (1, 0), (1, 0), (2, 1), (3, 1)]
def test_empty(self):
G = nx.Graph()
edges = list(edge_dfs(G))
assert_equal(edges, [])
def test_graph(self):
G = nx.Graph(self.edges)
x = list(edge_dfs(G, self.nodes))
x_ = [(0, 1), (1, 2), (1, 3)]
assert_equal(x, x_)
def test_digraph(self):
G = nx.DiGraph(self.edges)
x = list(edge_dfs(G, self.nodes))
x_= [(0, 1), (1, 0), (2, 1), (3, 1)]
assert_equal(x, x_)
def test_digraph2(self):
G = nx.DiGraph()
nodes = range(4)
G.add_path(nodes)
x = list(edge_dfs(G, [0]))
x_ = [(0, 1), (1, 2), (2, 3)]
assert_equal(x, x_)
def test_digraph_rev(self):
G = nx.DiGraph(self.edges)
x = list(edge_dfs(G, self.nodes, orientation='reverse'))
x_= [(1, 0, REVERSE), (0, 1, REVERSE),
(2, 1, REVERSE), (3, 1, REVERSE)]
assert_equal(x, x_)
def test_digraph_rev2(self):
G = nx.DiGraph()
nodes = range(4)
G.add_path(nodes)
x = list(edge_dfs(G, [3], orientation='reverse'))
x_ = [(2, 3, REVERSE), (1, 2, REVERSE), (0, 1, REVERSE)]
assert_equal(x, x_)
def test_multigraph(self):
G = nx.MultiGraph(self.edges)
x = list(edge_dfs(G, self.nodes))
x_ = [(0, 1, 0), (1, 0, 1), (0, 1, 2), (1, 2, 0), (1, 3, 0)]
# This is an example of where hash randomization can break.
# There are 3! * 2 alternative outputs, such as:
# [(0, 1, 1), (1, 0, 0), (0, 1, 2), (1, 3, 0), (1, 2, 0)]
# But note, the edges (1,2,0) and (1,3,0) always follow the (0,1,k)
# edges. So the algorithm only guarantees a partial order. A total
# order is guaranteed only if the graph data structures are ordered.
assert_equal(x, x_)
def test_multidigraph(self):
G = nx.MultiDiGraph(self.edges)
x = list(edge_dfs(G, self.nodes))
x_ = [(0, 1, 0), (1, 0, 0), (1, 0, 1), (2, 1, 0), (3, 1, 0)]
assert_equal(x, x_)
def test_multidigraph_rev(self):
G = nx.MultiDiGraph(self.edges)
x = list(edge_dfs(G, self.nodes, orientation='reverse'))
x_ = [(1, 0, 0, REVERSE),
(0, 1, 0, REVERSE),
(1, 0, 1, REVERSE),
(2, 1, 0, REVERSE),
(3, 1, 0, REVERSE)]
assert_equal(x, x_)
def test_digraph_ignore(self):
G = nx.DiGraph(self.edges)
x = list(edge_dfs(G, self.nodes, orientation='ignore'))
x_ = [(0, 1, FORWARD), (1, 0, FORWARD),
(2, 1, REVERSE), (3, 1, REVERSE)]
assert_equal(x, x_)
def test_digraph_ignore2(self):
G = nx.DiGraph()
nodes = range(4)
G.add_path(nodes)
x = list(edge_dfs(G, [0], orientation='ignore'))
x_ = [(0, 1, FORWARD), (1, 2, FORWARD), (2, 3, FORWARD)]
assert_equal(x, x_)
def test_multidigraph_ignore(self):
G = nx.MultiDiGraph(self.edges)
x = list(edge_dfs(G, self.nodes, orientation='ignore'))
x_ = [(0, 1, 0, FORWARD), (1, 0, 0, FORWARD),
(1, 0, 1, REVERSE), (2, 1, 0, REVERSE),
(3, 1, 0, REVERSE)]
assert_equal(x, x_)
|