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