Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tree/recognition.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """ | |
2 Recognition Tests | |
3 ================= | |
4 | |
5 A *forest* is an acyclic, undirected graph, and a *tree* is a connected forest. | |
6 Depending on the subfield, there are various conventions for generalizing these | |
7 definitions to directed graphs. | |
8 | |
9 In one convention, directed variants of forest and tree are defined in an | |
10 identical manner, except that the direction of the edges is ignored. In effect, | |
11 each directed edge is treated as a single undirected edge. Then, additional | |
12 restrictions are imposed to define *branchings* and *arborescences*. | |
13 | |
14 In another convention, directed variants of forest and tree correspond to | |
15 the previous convention's branchings and arborescences, respectively. Then two | |
16 new terms, *polyforest* and *polytree*, are defined to correspond to the other | |
17 convention's forest and tree. | |
18 | |
19 Summarizing:: | |
20 | |
21 +-----------------------------+ | |
22 | Convention A | Convention B | | |
23 +=============================+ | |
24 | forest | polyforest | | |
25 | tree | polytree | | |
26 | branching | forest | | |
27 | arborescence | tree | | |
28 +-----------------------------+ | |
29 | |
30 Each convention has its reasons. The first convention emphasizes definitional | |
31 similarity in that directed forests and trees are only concerned with | |
32 acyclicity and do not have an in-degree constraint, just as their undirected | |
33 counterparts do not. The second convention emphasizes functional similarity | |
34 in the sense that the directed analog of a spanning tree is a spanning | |
35 arborescence. That is, take any spanning tree and choose one node as the root. | |
36 Then every edge is assigned a direction such there is a directed path from the | |
37 root to every other node. The result is a spanning arborescence. | |
38 | |
39 NetworkX follows convention "A". Explicitly, these are: | |
40 | |
41 undirected forest | |
42 An undirected graph with no undirected cycles. | |
43 | |
44 undirected tree | |
45 A connected, undirected forest. | |
46 | |
47 directed 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. | |
51 | |
52 directed 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. | |
56 | |
57 branching | |
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. | |
60 | |
61 arborescence | |
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. | |
64 | |
65 For trees and arborescences, the adjective "spanning" may be added to designate | |
66 that the graph, when considered as a forest/branching, consists of a single | |
67 tree/arborescence that includes all nodes in the graph. It is true, by | |
68 definition, that every tree/arborescence is spanning with respect to the nodes | |
69 that define the tree/arborescence and so, it might seem redundant to introduce | |
70 the notion of "spanning". However, the nodes may represent a subset of | |
71 nodes from a larger graph, and it is in this context that the term "spanning" | |
72 becomes a useful notion. | |
73 | |
74 """ | |
75 | |
76 import networkx as nx | |
77 | |
78 | |
79 __all__ = ["is_arborescence", "is_branching", "is_forest", "is_tree"] | |
80 | |
81 | |
82 @nx.utils.not_implemented_for("undirected") | |
83 def is_arborescence(G): | |
84 """ | |
85 Returns True if `G` is an arborescence. | |
86 | |
87 An arborescence is a directed tree with maximum in-degree equal to 1. | |
88 | |
89 Parameters | |
90 ---------- | |
91 G : graph | |
92 The graph to test. | |
93 | |
94 Returns | |
95 ------- | |
96 b : bool | |
97 A boolean that is True if `G` is an arborescence. | |
98 | |
99 Notes | |
100 ----- | |
101 In another convention, an arborescence is known as a *tree*. | |
102 | |
103 See Also | |
104 -------- | |
105 is_tree | |
106 | |
107 """ | |
108 return is_tree(G) and max(d for n, d in G.in_degree()) <= 1 | |
109 | |
110 | |
111 @nx.utils.not_implemented_for("undirected") | |
112 def is_branching(G): | |
113 """ | |
114 Returns True if `G` is a branching. | |
115 | |
116 A branching is a directed forest with maximum in-degree equal to 1. | |
117 | |
118 Parameters | |
119 ---------- | |
120 G : directed graph | |
121 The directed graph to test. | |
122 | |
123 Returns | |
124 ------- | |
125 b : bool | |
126 A boolean that is True if `G` is a branching. | |
127 | |
128 Notes | |
129 ----- | |
130 In another convention, a branching is also known as a *forest*. | |
131 | |
132 See Also | |
133 -------- | |
134 is_forest | |
135 | |
136 """ | |
137 return is_forest(G) and max(d for n, d in G.in_degree()) <= 1 | |
138 | |
139 | |
140 def is_forest(G): | |
141 """ | |
142 Returns True if `G` is a forest. | |
143 | |
144 A forest is a graph with no undirected cycles. | |
145 | |
146 For directed graphs, `G` is a forest if the underlying graph is a forest. | |
147 The underlying graph is obtained by treating each directed edge as a single | |
148 undirected edge in a multigraph. | |
149 | |
150 Parameters | |
151 ---------- | |
152 G : graph | |
153 The graph to test. | |
154 | |
155 Returns | |
156 ------- | |
157 b : bool | |
158 A boolean that is True if `G` is a forest. | |
159 | |
160 Notes | |
161 ----- | |
162 In another convention, a directed forest is known as a *polyforest* and | |
163 then *forest* corresponds to a *branching*. | |
164 | |
165 See Also | |
166 -------- | |
167 is_branching | |
168 | |
169 """ | |
170 if len(G) == 0: | |
171 raise nx.exception.NetworkXPointlessConcept("G has no nodes.") | |
172 | |
173 if G.is_directed(): | |
174 components = (G.subgraph(c) for c in nx.weakly_connected_components(G)) | |
175 else: | |
176 components = (G.subgraph(c) for c in nx.connected_components(G)) | |
177 | |
178 return all(len(c) - 1 == c.number_of_edges() for c in components) | |
179 | |
180 | |
181 def is_tree(G): | |
182 """ | |
183 Returns True if `G` is a tree. | |
184 | |
185 A tree is a connected graph with no undirected cycles. | |
186 | |
187 For directed graphs, `G` is a tree if the underlying graph is a tree. The | |
188 underlying graph is obtained by treating each directed edge as a single | |
189 undirected edge in a multigraph. | |
190 | |
191 Parameters | |
192 ---------- | |
193 G : graph | |
194 The graph to test. | |
195 | |
196 Returns | |
197 ------- | |
198 b : bool | |
199 A boolean that is True if `G` is a tree. | |
200 | |
201 Notes | |
202 ----- | |
203 In another convention, a directed tree is known as a *polytree* and then | |
204 *tree* corresponds to an *arborescence*. | |
205 | |
206 See Also | |
207 -------- | |
208 is_arborescence | |
209 | |
210 """ | |
211 if len(G) == 0: | |
212 raise nx.exception.NetworkXPointlessConcept("G has no nodes.") | |
213 | |
214 if G.is_directed(): | |
215 is_connected = nx.is_weakly_connected | |
216 else: | |
217 is_connected = nx.is_connected | |
218 | |
219 # A connected graph with no cycles has n-1 edges. | |
220 return len(G) - 1 == G.number_of_edges() and is_connected(G) |