Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2Recognition Tests
3=================
5A *forest* is an acyclic, undirected graph, and a *tree* is a connected forest.
6Depending on the subfield, there are various conventions for generalizing these
7definitions to directed graphs.
9In one convention, directed variants of forest and tree are defined in an
10identical manner, except that the direction of the edges is ignored. In effect,
11each directed edge is treated as a single undirected edge. Then, additional
12restrictions are imposed to define *branchings* and *arborescences*.
14In another convention, directed variants of forest and tree correspond to
15the previous convention's branchings and arborescences, respectively. Then two
16new terms, *polyforest* and *polytree*, are defined to correspond to the other
17convention's forest and tree.
19Summarizing::
21 +-----------------------------+
22 | Convention A | Convention B |
23 +=============================+
24 | forest | polyforest |
25 | tree | polytree |
26 | branching | forest |
27 | arborescence | tree |
28 +-----------------------------+
30Each convention has its reasons. The first convention emphasizes definitional
31similarity in that directed forests and trees are only concerned with
32acyclicity and do not have an in-degree constraint, just as their undirected
33counterparts do not. The second convention emphasizes functional similarity
34in the sense that the directed analog of a spanning tree is a spanning
35arborescence. That is, take any spanning tree and choose one node as the root.
36Then every edge is assigned a direction such there is a directed path from the
37root to every other node. The result is a spanning arborescence.
39NetworkX follows convention "A". Explicitly, these are:
41undirected forest
42 An undirected graph with no undirected cycles.
44undirected tree
45 A connected, undirected forest.
47directed forest
48 A directed graph with no undirected cycles. Equivalently, the underlying
49 graph structure (which ignores edge orientations) is an undirected forest.
50 In convention B, this is known as a polyforest.
52directed tree
53 A weakly connected, directed forest. Equivalently, the underlying graph
54 structure (which ignores edge orientations) is an undirected tree. In
55 convention B, this is known as a polytree.
57branching
58 A directed forest with each node having, at most, one parent. So the maximum
59 in-degree is equal to 1. In convention B, this is known as a forest.
61arborescence
62 A directed tree with each node having, at most, one parent. So the maximum
63 in-degree is equal to 1. In convention B, this is known as a tree.
65For trees and arborescences, the adjective "spanning" may be added to designate
66that the graph, when considered as a forest/branching, consists of a single
67tree/arborescence that includes all nodes in the graph. It is true, by
68definition, that every tree/arborescence is spanning with respect to the nodes
69that define the tree/arborescence and so, it might seem redundant to introduce
70the notion of "spanning". However, the nodes may represent a subset of
71nodes from a larger graph, and it is in this context that the term "spanning"
72becomes a useful notion.
74"""
76import networkx as nx
78__all__ = ["is_arborescence", "is_branching", "is_forest", "is_tree"]
81@nx.utils.not_implemented_for("undirected")
82@nx._dispatchable
83def is_arborescence(G):
84 """
85 Returns True if `G` is an arborescence.
87 An arborescence is a directed tree with maximum in-degree equal to 1.
89 Parameters
90 ----------
91 G : graph
92 The graph to test.
94 Returns
95 -------
96 b : bool
97 A boolean that is True if `G` is an arborescence.
99 Examples
100 --------
101 >>> G = nx.DiGraph([(0, 1), (0, 2), (2, 3), (3, 4)])
102 >>> nx.is_arborescence(G)
103 True
104 >>> G.remove_edge(0, 1)
105 >>> G.add_edge(1, 2) # maximum in-degree is 2
106 >>> nx.is_arborescence(G)
107 False
109 Notes
110 -----
111 In another convention, an arborescence is known as a *tree*.
113 See Also
114 --------
115 is_tree
117 """
118 return is_tree(G) and max(d for n, d in G.in_degree()) <= 1
121@nx.utils.not_implemented_for("undirected")
122@nx._dispatchable
123def is_branching(G):
124 """
125 Returns True if `G` is a branching.
127 A branching is a directed forest with maximum in-degree equal to 1.
129 Parameters
130 ----------
131 G : directed graph
132 The directed graph to test.
134 Returns
135 -------
136 b : bool
137 A boolean that is True if `G` is a branching.
139 Examples
140 --------
141 >>> G = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3, 4)])
142 >>> nx.is_branching(G)
143 True
144 >>> G.remove_edge(2, 3)
145 >>> G.add_edge(3, 1) # maximum in-degree is 2
146 >>> nx.is_branching(G)
147 False
149 Notes
150 -----
151 In another convention, a branching is also known as a *forest*.
153 See Also
154 --------
155 is_forest
157 """
158 return is_forest(G) and max(d for n, d in G.in_degree()) <= 1
161@nx._dispatchable
162def is_forest(G):
163 """
164 Returns True if `G` is a forest.
166 A forest is a graph with no undirected cycles.
168 For directed graphs, `G` is a forest if the underlying graph is a forest.
169 The underlying graph is obtained by treating each directed edge as a single
170 undirected edge in a multigraph.
172 Parameters
173 ----------
174 G : graph
175 The graph to test.
177 Returns
178 -------
179 b : bool
180 A boolean that is True if `G` is a forest.
182 Raises
183 ------
184 NetworkXPointlessConcept
185 If `G` is empty.
187 Examples
188 --------
189 >>> G = nx.Graph()
190 >>> G.add_edges_from([(1, 2), (1, 3), (2, 4), (2, 5)])
191 >>> nx.is_forest(G)
192 True
193 >>> G.add_edge(4, 1)
194 >>> nx.is_forest(G)
195 False
197 Notes
198 -----
199 In another convention, a directed forest is known as a *polyforest* and
200 then *forest* corresponds to a *branching*.
202 See Also
203 --------
204 is_branching
206 """
207 if len(G) == 0:
208 raise nx.exception.NetworkXPointlessConcept("G has no nodes.")
210 if G.is_directed():
211 components = (G.subgraph(c) for c in nx.weakly_connected_components(G))
212 else:
213 components = (G.subgraph(c) for c in nx.connected_components(G))
215 return all(len(c) - 1 == c.number_of_edges() for c in components)
218@nx._dispatchable
219def is_tree(G):
220 """
221 Returns True if `G` is a tree.
223 A tree is a connected graph with no undirected cycles.
225 For directed graphs, `G` is a tree if the underlying graph is a tree. The
226 underlying graph is obtained by treating each directed edge as a single
227 undirected edge in a multigraph.
229 Parameters
230 ----------
231 G : graph
232 The graph to test.
234 Returns
235 -------
236 b : bool
237 A boolean that is True if `G` is a tree.
239 Raises
240 ------
241 NetworkXPointlessConcept
242 If `G` is empty.
244 Examples
245 --------
246 >>> G = nx.Graph()
247 >>> G.add_edges_from([(1, 2), (1, 3), (2, 4), (2, 5)])
248 >>> nx.is_tree(G) # n-1 edges
249 True
250 >>> G.add_edge(3, 4)
251 >>> nx.is_tree(G) # n edges
252 False
254 Notes
255 -----
256 In another convention, a directed tree is known as a *polytree* and then
257 *tree* corresponds to an *arborescence*.
259 See Also
260 --------
261 is_arborescence
263 """
264 if len(G) == 0:
265 raise nx.exception.NetworkXPointlessConcept("G has no nodes.")
267 if G.is_directed():
268 is_connected = nx.is_weakly_connected
269 else:
270 is_connected = nx.is_connected
272 # A connected graph with no cycles has n-1 edges.
273 return len(G) - 1 == G.number_of_edges() and is_connected(G)