Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tournament.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 """Functions concerning tournament graphs. | |
2 | |
3 A `tournament graph`_ is a complete oriented graph. In other words, it | |
4 is a directed graph in which there is exactly one directed edge joining | |
5 each pair of distinct nodes. For each function in this module that | |
6 accepts a graph as input, you must provide a tournament graph. The | |
7 responsibility is on the caller to ensure that the graph is a tournament | |
8 graph. | |
9 | |
10 To access the functions in this module, you must access them through the | |
11 :mod:`networkx.algorithms.tournament` module:: | |
12 | |
13 >>> from networkx.algorithms import tournament | |
14 >>> G = nx.DiGraph([(0, 1), (1, 2), (2, 0)]) | |
15 >>> tournament.is_tournament(G) | |
16 True | |
17 | |
18 .. _tournament graph: https://en.wikipedia.org/wiki/Tournament_%28graph_theory%29 | |
19 | |
20 """ | |
21 from itertools import combinations | |
22 | |
23 import networkx as nx | |
24 from networkx.algorithms.simple_paths import is_simple_path as is_path | |
25 from networkx.utils import arbitrary_element | |
26 from networkx.utils import not_implemented_for | |
27 from networkx.utils import py_random_state | |
28 | |
29 __all__ = [ | |
30 "hamiltonian_path", | |
31 "is_reachable", | |
32 "is_strongly_connected", | |
33 "is_tournament", | |
34 "random_tournament", | |
35 "score_sequence", | |
36 ] | |
37 | |
38 | |
39 def index_satisfying(iterable, condition): | |
40 """Returns the index of the first element in `iterable` that | |
41 satisfies the given condition. | |
42 | |
43 If no such element is found (that is, when the iterable is | |
44 exhausted), this returns the length of the iterable (that is, one | |
45 greater than the last index of the iterable). | |
46 | |
47 `iterable` must not be empty. If `iterable` is empty, this | |
48 function raises :exc:`ValueError`. | |
49 | |
50 """ | |
51 # Pre-condition: iterable must not be empty. | |
52 for i, x in enumerate(iterable): | |
53 if condition(x): | |
54 return i | |
55 # If we reach the end of the iterable without finding an element | |
56 # that satisfies the condition, return the length of the iterable, | |
57 # which is one greater than the index of its last element. If the | |
58 # iterable was empty, `i` will not be defined, so we raise an | |
59 # exception. | |
60 try: | |
61 return i + 1 | |
62 except NameError as e: | |
63 raise ValueError("iterable must be non-empty") from e | |
64 | |
65 | |
66 @not_implemented_for("undirected") | |
67 @not_implemented_for("multigraph") | |
68 def is_tournament(G): | |
69 """Returns True if and only if `G` is a tournament. | |
70 | |
71 A tournament is a directed graph, with neither self-loops nor | |
72 multi-edges, in which there is exactly one directed edge joining | |
73 each pair of distinct nodes. | |
74 | |
75 Parameters | |
76 ---------- | |
77 G : NetworkX graph | |
78 A directed graph representing a tournament. | |
79 | |
80 Returns | |
81 ------- | |
82 bool | |
83 Whether the given graph is a tournament graph. | |
84 | |
85 Notes | |
86 ----- | |
87 Some definitions require a self-loop on each node, but that is not | |
88 the convention used here. | |
89 | |
90 """ | |
91 # In a tournament, there is exactly one directed edge joining each pair. | |
92 return ( | |
93 all((v in G[u]) ^ (u in G[v]) for u, v in combinations(G, 2)) | |
94 and nx.number_of_selfloops(G) == 0 | |
95 ) | |
96 | |
97 | |
98 @not_implemented_for("undirected") | |
99 @not_implemented_for("multigraph") | |
100 def hamiltonian_path(G): | |
101 """Returns a Hamiltonian path in the given tournament graph. | |
102 | |
103 Each tournament has a Hamiltonian path. If furthermore, the | |
104 tournament is strongly connected, then the returned Hamiltonian path | |
105 is a Hamiltonian cycle (by joining the endpoints of the path). | |
106 | |
107 Parameters | |
108 ---------- | |
109 G : NetworkX graph | |
110 A directed graph representing a tournament. | |
111 | |
112 Returns | |
113 ------- | |
114 bool | |
115 Whether the given graph is a tournament graph. | |
116 | |
117 Notes | |
118 ----- | |
119 This is a recursive implementation with an asymptotic running time | |
120 of $O(n^2)$, ignoring multiplicative polylogarithmic factors, where | |
121 $n$ is the number of nodes in the graph. | |
122 | |
123 """ | |
124 if len(G) == 0: | |
125 return [] | |
126 if len(G) == 1: | |
127 return [arbitrary_element(G)] | |
128 v = arbitrary_element(G) | |
129 hampath = hamiltonian_path(G.subgraph(set(G) - {v})) | |
130 # Get the index of the first node in the path that does *not* have | |
131 # an edge to `v`, then insert `v` before that node. | |
132 index = index_satisfying(hampath, lambda u: v not in G[u]) | |
133 hampath.insert(index, v) | |
134 return hampath | |
135 | |
136 | |
137 @py_random_state(1) | |
138 def random_tournament(n, seed=None): | |
139 r"""Returns a random tournament graph on `n` nodes. | |
140 | |
141 Parameters | |
142 ---------- | |
143 n : int | |
144 The number of nodes in the returned graph. | |
145 seed : integer, random_state, or None (default) | |
146 Indicator of random number generation state. | |
147 See :ref:`Randomness<randomness>`. | |
148 | |
149 Returns | |
150 ------- | |
151 bool | |
152 Whether the given graph is a tournament graph. | |
153 | |
154 Notes | |
155 ----- | |
156 This algorithm adds, for each pair of distinct nodes, an edge with | |
157 uniformly random orientation. In other words, `\binom{n}{2}` flips | |
158 of an unbiased coin decide the orientations of the edges in the | |
159 graph. | |
160 | |
161 """ | |
162 # Flip an unbiased coin for each pair of distinct nodes. | |
163 coins = (seed.random() for i in range((n * (n - 1)) // 2)) | |
164 pairs = combinations(range(n), 2) | |
165 edges = ((u, v) if r < 0.5 else (v, u) for (u, v), r in zip(pairs, coins)) | |
166 return nx.DiGraph(edges) | |
167 | |
168 | |
169 @not_implemented_for("undirected") | |
170 @not_implemented_for("multigraph") | |
171 def score_sequence(G): | |
172 """Returns the score sequence for the given tournament graph. | |
173 | |
174 The score sequence is the sorted list of the out-degrees of the | |
175 nodes of the graph. | |
176 | |
177 Parameters | |
178 ---------- | |
179 G : NetworkX graph | |
180 A directed graph representing a tournament. | |
181 | |
182 Returns | |
183 ------- | |
184 list | |
185 A sorted list of the out-degrees of the nodes of `G`. | |
186 | |
187 """ | |
188 return sorted(d for v, d in G.out_degree()) | |
189 | |
190 | |
191 @not_implemented_for("undirected") | |
192 @not_implemented_for("multigraph") | |
193 def tournament_matrix(G): | |
194 r"""Returns the tournament matrix for the given tournament graph. | |
195 | |
196 This function requires SciPy. | |
197 | |
198 The *tournament matrix* of a tournament graph with edge set *E* is | |
199 the matrix *T* defined by | |
200 | |
201 .. math:: | |
202 | |
203 T_{i j} = | |
204 \begin{cases} | |
205 +1 & \text{if } (i, j) \in E \\ | |
206 -1 & \text{if } (j, i) \in E \\ | |
207 0 & \text{if } i == j. | |
208 \end{cases} | |
209 | |
210 An equivalent definition is `T = A - A^T`, where *A* is the | |
211 adjacency matrix of the graph `G`. | |
212 | |
213 Parameters | |
214 ---------- | |
215 G : NetworkX graph | |
216 A directed graph representing a tournament. | |
217 | |
218 Returns | |
219 ------- | |
220 SciPy sparse matrix | |
221 The tournament matrix of the tournament graph `G`. | |
222 | |
223 Raises | |
224 ------ | |
225 ImportError | |
226 If SciPy is not available. | |
227 | |
228 """ | |
229 A = nx.adjacency_matrix(G) | |
230 return A - A.T | |
231 | |
232 | |
233 @not_implemented_for("undirected") | |
234 @not_implemented_for("multigraph") | |
235 def is_reachable(G, s, t): | |
236 """Decides whether there is a path from `s` to `t` in the | |
237 tournament. | |
238 | |
239 This function is more theoretically efficient than the reachability | |
240 checks than the shortest path algorithms in | |
241 :mod:`networkx.algorithms.shortest_paths`. | |
242 | |
243 The given graph **must** be a tournament, otherwise this function's | |
244 behavior is undefined. | |
245 | |
246 Parameters | |
247 ---------- | |
248 G : NetworkX graph | |
249 A directed graph representing a tournament. | |
250 | |
251 s : node | |
252 A node in the graph. | |
253 | |
254 t : node | |
255 A node in the graph. | |
256 | |
257 Returns | |
258 ------- | |
259 bool | |
260 Whether there is a path from `s` to `t` in `G`. | |
261 | |
262 Notes | |
263 ----- | |
264 Although this function is more theoretically efficient than the | |
265 generic shortest path functions, a speedup requires the use of | |
266 parallelism. Though it may in the future, the current implementation | |
267 does not use parallelism, thus you may not see much of a speedup. | |
268 | |
269 This algorithm comes from [1]. | |
270 | |
271 References | |
272 ---------- | |
273 .. [1] Tantau, Till. | |
274 "A note on the complexity of the reachability problem for | |
275 tournaments." | |
276 *Electronic Colloquium on Computational Complexity*. 2001. | |
277 <http://eccc.hpi-web.de/report/2001/092/> | |
278 | |
279 """ | |
280 | |
281 def two_neighborhood(G, v): | |
282 """Returns the set of nodes at distance at most two from `v`. | |
283 | |
284 `G` must be a graph and `v` a node in that graph. | |
285 | |
286 The returned set includes the nodes at distance zero (that is, | |
287 the node `v` itself), the nodes at distance one (that is, the | |
288 out-neighbors of `v`), and the nodes at distance two. | |
289 | |
290 """ | |
291 # TODO This is trivially parallelizable. | |
292 return { | |
293 x for x in G if x == v or x in G[v] or any(is_path(G, [v, z, x]) for z in G) | |
294 } | |
295 | |
296 def is_closed(G, nodes): | |
297 """Decides whether the given set of nodes is closed. | |
298 | |
299 A set *S* of nodes is *closed* if for each node *u* in the graph | |
300 not in *S* and for each node *v* in *S*, there is an edge from | |
301 *u* to *v*. | |
302 | |
303 """ | |
304 # TODO This is trivially parallelizable. | |
305 return all(v in G[u] for u in set(G) - nodes for v in nodes) | |
306 | |
307 # TODO This is trivially parallelizable. | |
308 neighborhoods = [two_neighborhood(G, v) for v in G] | |
309 return all(not (is_closed(G, S) and s in S and t not in S) for S in neighborhoods) | |
310 | |
311 | |
312 @not_implemented_for("undirected") | |
313 @not_implemented_for("multigraph") | |
314 def is_strongly_connected(G): | |
315 """Decides whether the given tournament is strongly connected. | |
316 | |
317 This function is more theoretically efficient than the | |
318 :func:`~networkx.algorithms.components.is_strongly_connected` | |
319 function. | |
320 | |
321 The given graph **must** be a tournament, otherwise this function's | |
322 behavior is undefined. | |
323 | |
324 Parameters | |
325 ---------- | |
326 G : NetworkX graph | |
327 A directed graph representing a tournament. | |
328 | |
329 Returns | |
330 ------- | |
331 bool | |
332 Whether the tournament is strongly connected. | |
333 | |
334 Notes | |
335 ----- | |
336 Although this function is more theoretically efficient than the | |
337 generic strong connectivity function, a speedup requires the use of | |
338 parallelism. Though it may in the future, the current implementation | |
339 does not use parallelism, thus you may not see much of a speedup. | |
340 | |
341 This algorithm comes from [1]. | |
342 | |
343 References | |
344 ---------- | |
345 .. [1] Tantau, Till. | |
346 "A note on the complexity of the reachability problem for | |
347 tournaments." | |
348 *Electronic Colloquium on Computational Complexity*. 2001. | |
349 <http://eccc.hpi-web.de/report/2001/092/> | |
350 | |
351 """ | |
352 # TODO This is trivially parallelizable. | |
353 return all(is_reachable(G, u, v) for u in G for v in G) |