/usr/lib/python2.7/dist-packages/networkx/algorithms/tests/test_dag.py is in python-networkx 1.8.1-0ubuntu3.
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 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 | #!/usr/bin/env python
from nose.tools import *
import networkx as nx
class TestDAG:
def setUp(self):
pass
def test_topological_sort1(self):
DG=nx.DiGraph()
DG.add_edges_from([(1,2),(1,3),(2,3)])
assert_equal(nx.topological_sort(DG),[1, 2, 3])
assert_equal(nx.topological_sort_recursive(DG),[1, 2, 3])
DG.add_edge(3,2)
assert_raises(nx.NetworkXUnfeasible, nx.topological_sort, DG)
assert_raises(nx.NetworkXUnfeasible, nx.topological_sort_recursive, DG)
DG.remove_edge(2,3)
assert_equal(nx.topological_sort(DG),[1, 3, 2])
assert_equal(nx.topological_sort_recursive(DG),[1, 3, 2])
def test_is_directed_acyclic_graph(self):
G = nx.generators.complete_graph(2)
assert_false(nx.is_directed_acyclic_graph(G))
assert_false(nx.is_directed_acyclic_graph(G.to_directed()))
assert_false(nx.is_directed_acyclic_graph(nx.Graph([(3, 4), (4, 5)])))
assert_true(nx.is_directed_acyclic_graph(nx.DiGraph([(3, 4), (4, 5)])))
def test_topological_sort2(self):
DG=nx.DiGraph({1:[2],2:[3],3:[4],
4:[5],5:[1],11:[12],
12:[13],13:[14],14:[15]})
assert_raises(nx.NetworkXUnfeasible, nx.topological_sort, DG)
assert_raises(nx.NetworkXUnfeasible, nx.topological_sort_recursive, DG)
assert_false(nx.is_directed_acyclic_graph(DG))
DG.remove_edge(1,2)
assert_equal(nx.topological_sort_recursive(DG),
[11, 12, 13, 14, 15, 2, 3, 4, 5, 1])
assert_equal(nx.topological_sort(DG),
[11, 12, 13, 14, 15, 2, 3, 4, 5, 1])
assert_true(nx.is_directed_acyclic_graph(DG))
def test_topological_sort3(self):
DG=nx.DiGraph()
DG.add_edges_from([(1,i) for i in range(2,5)])
DG.add_edges_from([(2,i) for i in range(5,9)])
DG.add_edges_from([(6,i) for i in range(9,12)])
DG.add_edges_from([(4,i) for i in range(12,15)])
assert_equal(nx.topological_sort_recursive(DG),
[1, 4, 14, 13, 12, 3, 2, 7, 6, 11, 10, 9, 5, 8])
assert_equal(nx.topological_sort(DG),
[1, 2, 8, 5, 6, 9, 10, 11, 7, 3, 4, 12, 13, 14])
DG.add_edge(14,1)
assert_raises(nx.NetworkXUnfeasible, nx.topological_sort, DG)
assert_raises(nx.NetworkXUnfeasible, nx.topological_sort_recursive, DG)
def test_topological_sort4(self):
G=nx.Graph()
G.add_edge(1,2)
assert_raises(nx.NetworkXError, nx.topological_sort, G)
assert_raises(nx.NetworkXError, nx.topological_sort_recursive, G)
def test_topological_sort5(self):
G=nx.DiGraph()
G.add_edge(0,1)
assert_equal(nx.topological_sort_recursive(G), [0,1])
assert_equal(nx.topological_sort(G), [0,1])
def test_nbunch_argument(self):
G=nx.DiGraph()
G.add_edges_from([(1,2), (2,3), (1,4), (1,5), (2,6)])
assert_equal(nx.topological_sort(G), [1, 2, 3, 6, 4, 5])
assert_equal(nx.topological_sort_recursive(G), [1, 5, 4, 2, 6, 3])
assert_equal(nx.topological_sort(G,[1]), [1, 2, 3, 6, 4, 5])
assert_equal(nx.topological_sort_recursive(G,[1]), [1, 5, 4, 2, 6, 3])
assert_equal(nx.topological_sort(G,[5]), [5])
assert_equal(nx.topological_sort_recursive(G,[5]), [5])
def test_ancestors(self):
G=nx.DiGraph()
ancestors = nx.algorithms.dag.ancestors
G.add_edges_from([
(1, 2), (1, 3), (4, 2), (4, 3), (4, 5), (2, 6), (5, 6)])
assert_equal(ancestors(G, 6), set([1, 2, 4, 5]))
assert_equal(ancestors(G, 3), set([1, 4]))
assert_equal(ancestors(G, 1), set())
assert_raises(nx.NetworkXError, ancestors, G, 8)
def test_descendants(self):
G=nx.DiGraph()
descendants = nx.algorithms.dag.descendants
G.add_edges_from([
(1, 2), (1, 3), (4, 2), (4, 3), (4, 5), (2, 6), (5, 6)])
assert_equal(descendants(G, 1), set([2, 3, 6]))
assert_equal(descendants(G, 4), set([2, 3, 5, 6]))
assert_equal(descendants(G, 3), set())
assert_raises(nx.NetworkXError, descendants, G, 8)
def test_is_aperiodic_cycle():
G=nx.DiGraph()
G.add_cycle([1,2,3,4])
assert_false(nx.is_aperiodic(G))
def test_is_aperiodic_cycle2():
G=nx.DiGraph()
G.add_cycle([1,2,3,4])
G.add_cycle([3,4,5,6,7])
assert_true(nx.is_aperiodic(G))
def test_is_aperiodic_cycle3():
G=nx.DiGraph()
G.add_cycle([1,2,3,4])
G.add_cycle([3,4,5,6])
assert_false(nx.is_aperiodic(G))
def test_is_aperiodic_cycle4():
G = nx.DiGraph()
G.add_cycle([1,2,3,4])
G.add_edge(1,3)
assert_true(nx.is_aperiodic(G))
def test_is_aperiodic_selfloop():
G = nx.DiGraph()
G.add_cycle([1,2,3,4])
G.add_edge(1,1)
assert_true(nx.is_aperiodic(G))
def test_is_aperiodic_raise():
G = nx.Graph()
assert_raises(nx.NetworkXError,
nx.is_aperiodic,
G)
def test_is_aperiodic_bipartite():
#Bipartite graph
G = nx.DiGraph(nx.davis_southern_women_graph())
assert_false(nx.is_aperiodic(G))
def test_is_aperiodic_rary_tree():
G = nx.full_rary_tree(3,27,create_using=nx.DiGraph())
assert_false(nx.is_aperiodic(G))
def test_is_aperiodic_disconnected():
#disconnected graph
G = nx.DiGraph()
G.add_cycle([1,2,3,4])
G.add_cycle([5,6,7,8])
assert_false(nx.is_aperiodic(G))
G.add_edge(1,3)
G.add_edge(5,7)
assert_true(nx.is_aperiodic(G))
def test_is_aperiodic_disconnected2():
G = nx.DiGraph()
G.add_cycle([0,1,2])
G.add_edge(3,3)
assert_false(nx.is_aperiodic(G))
|