1import pytest 2import networkx as nx 3 4 5class TestTreeRecognition: 6 7 graph = nx.Graph 8 multigraph = nx.MultiGraph 9 10 @classmethod 11 def setup_class(cls): 12 13 cls.T1 = cls.graph() 14 15 cls.T2 = cls.graph() 16 cls.T2.add_node(1) 17 18 cls.T3 = cls.graph() 19 cls.T3.add_nodes_from(range(5)) 20 edges = [(i, i + 1) for i in range(4)] 21 cls.T3.add_edges_from(edges) 22 23 cls.T5 = cls.multigraph() 24 cls.T5.add_nodes_from(range(5)) 25 edges = [(i, i + 1) for i in range(4)] 26 cls.T5.add_edges_from(edges) 27 28 cls.T6 = cls.graph() 29 cls.T6.add_nodes_from([6, 7]) 30 cls.T6.add_edge(6, 7) 31 32 cls.F1 = nx.compose(cls.T6, cls.T3) 33 34 cls.N4 = cls.graph() 35 cls.N4.add_node(1) 36 cls.N4.add_edge(1, 1) 37 38 cls.N5 = cls.graph() 39 cls.N5.add_nodes_from(range(5)) 40 41 cls.N6 = cls.graph() 42 cls.N6.add_nodes_from(range(3)) 43 cls.N6.add_edges_from([(0, 1), (1, 2), (2, 0)]) 44 45 cls.NF1 = nx.compose(cls.T6, cls.N6) 46 47 def test_null_tree(self): 48 with pytest.raises(nx.NetworkXPointlessConcept): 49 nx.is_tree(self.graph()) 50 51 def test_null_tree2(self): 52 with pytest.raises(nx.NetworkXPointlessConcept): 53 nx.is_tree(self.multigraph()) 54 55 def test_null_forest(self): 56 with pytest.raises(nx.NetworkXPointlessConcept): 57 nx.is_forest(self.graph()) 58 59 def test_null_forest2(self): 60 with pytest.raises(nx.NetworkXPointlessConcept): 61 nx.is_forest(self.multigraph()) 62 63 def test_is_tree(self): 64 assert nx.is_tree(self.T2) 65 assert nx.is_tree(self.T3) 66 assert nx.is_tree(self.T5) 67 68 def test_is_not_tree(self): 69 assert not nx.is_tree(self.N4) 70 assert not nx.is_tree(self.N5) 71 assert not nx.is_tree(self.N6) 72 73 def test_is_forest(self): 74 assert nx.is_forest(self.T2) 75 assert nx.is_forest(self.T3) 76 assert nx.is_forest(self.T5) 77 assert nx.is_forest(self.F1) 78 assert nx.is_forest(self.N5) 79 80 def test_is_not_forest(self): 81 assert not nx.is_forest(self.N4) 82 assert not nx.is_forest(self.N6) 83 assert not nx.is_forest(self.NF1) 84 85 86class TestDirectedTreeRecognition(TestTreeRecognition): 87 graph = nx.DiGraph 88 multigraph = nx.MultiDiGraph 89 90 91def test_disconnected_graph(): 92 # https://github.com/networkx/networkx/issues/1144 93 G = nx.Graph() 94 G.add_edges_from([(0, 1), (1, 2), (2, 0), (3, 4)]) 95 assert not nx.is_tree(G) 96 97 G = nx.DiGraph() 98 G.add_edges_from([(0, 1), (1, 2), (2, 0), (3, 4)]) 99 assert not nx.is_tree(G) 100 101 102def test_dag_nontree(): 103 G = nx.DiGraph() 104 G.add_edges_from([(0, 1), (0, 2), (1, 2)]) 105 assert not nx.is_tree(G) 106 assert nx.is_directed_acyclic_graph(G) 107 108 109def test_multicycle(): 110 G = nx.MultiDiGraph() 111 G.add_edges_from([(0, 1), (0, 1)]) 112 assert not nx.is_tree(G) 113 assert nx.is_directed_acyclic_graph(G) 114 115 116def test_emptybranch(): 117 G = nx.DiGraph() 118 G.add_nodes_from(range(10)) 119 assert nx.is_branching(G) 120 assert not nx.is_arborescence(G) 121 122 123def test_path(): 124 G = nx.DiGraph() 125 nx.add_path(G, range(5)) 126 assert nx.is_branching(G) 127 assert nx.is_arborescence(G) 128 129 130def test_notbranching1(): 131 # Acyclic violation. 132 G = nx.MultiDiGraph() 133 G.add_nodes_from(range(10)) 134 G.add_edges_from([(0, 1), (1, 0)]) 135 assert not nx.is_branching(G) 136 assert not nx.is_arborescence(G) 137 138 139def test_notbranching2(): 140 # In-degree violation. 141 G = nx.MultiDiGraph() 142 G.add_nodes_from(range(10)) 143 G.add_edges_from([(0, 1), (0, 2), (3, 2)]) 144 assert not nx.is_branching(G) 145 assert not nx.is_arborescence(G) 146 147 148def test_notarborescence1(): 149 # Not an arborescence due to not spanning. 150 G = nx.MultiDiGraph() 151 G.add_nodes_from(range(10)) 152 G.add_edges_from([(0, 1), (0, 2), (1, 3), (5, 6)]) 153 assert nx.is_branching(G) 154 assert not nx.is_arborescence(G) 155 156 157def test_notarborescence2(): 158 # Not an arborescence due to in-degree violation. 159 G = nx.MultiDiGraph() 160 nx.add_path(G, range(5)) 161 G.add_edge(6, 4) 162 assert not nx.is_branching(G) 163 assert not nx.is_arborescence(G) 164