1 #!/usr/bin/env python 2 from nose.tools import * 3 import networkx as nx 4 5 class TestDAG: 6 7 def setUp(self): 8 pass 9 10 def test_topological_sort1(self): 11 DG=nx.DiGraph() 12 DG.add_edges_from([(1,2),(1,3),(2,3)]) 13 assert_equal(nx.topological_sort(DG),[1, 2, 3]) 14 assert_equal(nx.topological_sort_recursive(DG),[1, 2, 3]) 15 16 DG.add_edge(3,2) 17 assert_raises(nx.NetworkXUnfeasible, nx.topological_sort, DG) 18 assert_raises(nx.NetworkXUnfeasible, nx.topological_sort_recursive, DG) 19 20 DG.remove_edge(2,3) 21 assert_equal(nx.topological_sort(DG),[1, 3, 2]) 22 assert_equal(nx.topological_sort_recursive(DG),[1, 3, 2]) 23 24 def test_is_directed_acyclic_graph(self): 25 G = nx.generators.complete_graph(2) 26 assert_false(nx.is_directed_acyclic_graph(G)) 27 assert_false(nx.is_directed_acyclic_graph(G.to_directed())) 28 assert_false(nx.is_directed_acyclic_graph(nx.Graph([(3, 4), (4, 5)]))) 29 assert_true(nx.is_directed_acyclic_graph(nx.DiGraph([(3, 4), (4, 5)]))) 30 31 def test_topological_sort2(self): 32 DG=nx.DiGraph({1:[2],2:[3],3:[4], 33 4:[5],5:[1],11:[12], 34 12:[13],13:[14],14:[15]}) 35 assert_raises(nx.NetworkXUnfeasible, nx.topological_sort, DG) 36 assert_raises(nx.NetworkXUnfeasible, nx.topological_sort_recursive, DG) 37 38 assert_false(nx.is_directed_acyclic_graph(DG)) 39 40 DG.remove_edge(1,2) 41 assert_equal(nx.topological_sort_recursive(DG), 42 [11, 12, 13, 14, 15, 2, 3, 4, 5, 1]) 43 assert_equal(nx.topological_sort(DG), 44 [11, 12, 13, 14, 15, 2, 3, 4, 5, 1]) 45 assert_true(nx.is_directed_acyclic_graph(DG)) 46 47 def test_topological_sort3(self): 48 DG=nx.DiGraph() 49 DG.add_edges_from([(1,i) for i in range(2,5)]) 50 DG.add_edges_from([(2,i) for i in range(5,9)]) 51 DG.add_edges_from([(6,i) for i in range(9,12)]) 52 DG.add_edges_from([(4,i) for i in range(12,15)]) 53 assert_equal(nx.topological_sort_recursive(DG), 54 [1, 4, 14, 13, 12, 3, 2, 7, 6, 11, 10, 9, 5, 8]) 55 assert_equal(nx.topological_sort(DG), 56 [1, 2, 8, 5, 6, 9, 10, 11, 7, 3, 4, 12, 13, 14]) 57 58 DG.add_edge(14,1) 59 assert_raises(nx.NetworkXUnfeasible, nx.topological_sort, DG) 60 assert_raises(nx.NetworkXUnfeasible, nx.topological_sort_recursive, DG) 61 62 def test_topological_sort4(self): 63 G=nx.Graph() 64 G.add_edge(1,2) 65 assert_raises(nx.NetworkXError, nx.topological_sort, G) 66 assert_raises(nx.NetworkXError, nx.topological_sort_recursive, G) 67 68 def test_topological_sort5(self): 69 G=nx.DiGraph() 70 G.add_edge(0,1) 71 assert_equal(nx.topological_sort_recursive(G), [0,1]) 72 assert_equal(nx.topological_sort(G), [0,1]) 73 74 def test_nbunch_argument(self): 75 G=nx.DiGraph() 76 G.add_edges_from([(1,2), (2,3), (1,4), (1,5), (2,6)]) 77 assert_equal(nx.topological_sort(G), [1, 2, 3, 6, 4, 5]) 78 assert_equal(nx.topological_sort_recursive(G), [1, 5, 4, 2, 6, 3]) 79 assert_equal(nx.topological_sort(G,[1]), [1, 2, 3, 6, 4, 5]) 80 assert_equal(nx.topological_sort_recursive(G,[1]), [1, 5, 4, 2, 6, 3]) 81 assert_equal(nx.topological_sort(G,[5]), [5]) 82 assert_equal(nx.topological_sort_recursive(G,[5]), [5]) 83 84 def test_ancestors(self): 85 G=nx.DiGraph() 86 ancestors = nx.algorithms.dag.ancestors 87 G.add_edges_from([ 88 (1, 2), (1, 3), (4, 2), (4, 3), (4, 5), (2, 6), (5, 6)]) 89 assert_equal(ancestors(G, 6), set([1, 2, 4, 5])) 90 assert_equal(ancestors(G, 3), set([1, 4])) 91 assert_equal(ancestors(G, 1), set()) 92 assert_raises(nx.NetworkXError, ancestors, G, 8) 93 94 def test_descendants(self): 95 G=nx.DiGraph() 96 descendants = nx.algorithms.dag.descendants 97 G.add_edges_from([ 98 (1, 2), (1, 3), (4, 2), (4, 3), (4, 5), (2, 6), (5, 6)]) 99 assert_equal(descendants(G, 1), set([2, 3, 6])) 100 assert_equal(descendants(G, 4), set([2, 3, 5, 6])) 101 assert_equal(descendants(G, 3), set()) 102 assert_raises(nx.NetworkXError, descendants, G, 8) 103 104 105 def test_is_aperiodic_cycle(): 106 G=nx.DiGraph() 107 G.add_cycle([1,2,3,4]) 108 assert_false(nx.is_aperiodic(G)) 109 110 def test_is_aperiodic_cycle2(): 111 G=nx.DiGraph() 112 G.add_cycle([1,2,3,4]) 113 G.add_cycle([3,4,5,6,7]) 114 assert_true(nx.is_aperiodic(G)) 115 116 def test_is_aperiodic_cycle3(): 117 G=nx.DiGraph() 118 G.add_cycle([1,2,3,4]) 119 G.add_cycle([3,4,5,6]) 120 assert_false(nx.is_aperiodic(G)) 121 122 def test_is_aperiodic_cycle4(): 123 G = nx.DiGraph() 124 G.add_cycle([1,2,3,4]) 125 G.add_edge(1,3) 126 assert_true(nx.is_aperiodic(G)) 127 128 def test_is_aperiodic_selfloop(): 129 G = nx.DiGraph() 130 G.add_cycle([1,2,3,4]) 131 G.add_edge(1,1) 132 assert_true(nx.is_aperiodic(G)) 133 134 def test_is_aperiodic_raise(): 135 G = nx.Graph() 136 assert_raises(nx.NetworkXError, 137 nx.is_aperiodic, 138 G) 139 140 def test_is_aperiodic_bipartite(): 141 #Bipartite graph 142 G = nx.DiGraph(nx.davis_southern_women_graph()) 143 assert_false(nx.is_aperiodic(G)) 144 145 def test_is_aperiodic_rary_tree(): 146 G = nx.full_rary_tree(3,27,create_using=nx.DiGraph()) 147 assert_false(nx.is_aperiodic(G)) 148 149 def test_is_aperiodic_disconnected(): 150 #disconnected graph 151 G = nx.DiGraph() 152 G.add_cycle([1,2,3,4]) 153 G.add_cycle([5,6,7,8]) 154 assert_false(nx.is_aperiodic(G)) 155 G.add_edge(1,3) 156 G.add_edge(5,7) 157 assert_true(nx.is_aperiodic(G)) 158 159 def test_is_aperiodic_disconnected2(): 160 G = nx.DiGraph() 161 G.add_cycle([0,1,2]) 162 G.add_edge(3,3) 163 assert_false(nx.is_aperiodic(G)) 164
