Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/tournament.py: 52%
64 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Functions concerning tournament graphs.
3A `tournament graph`_ is a complete oriented graph. In other words, it
4is a directed graph in which there is exactly one directed edge joining
5each pair of distinct nodes. For each function in this module that
6accepts a graph as input, you must provide a tournament graph. The
7responsibility is on the caller to ensure that the graph is a tournament
8graph:
10 >>> G = nx.DiGraph([(0, 1), (1, 2), (2, 0)])
11 >>> nx.is_tournament(G)
12 True
14To access the functions in this module, you must access them through the
15:mod:`networkx.tournament` module::
17 >>> nx.tournament.is_reachable(G, 0, 1)
18 True
20.. _tournament graph: https://en.wikipedia.org/wiki/Tournament_%28graph_theory%29
22"""
23from itertools import combinations
25import networkx as nx
26from networkx.algorithms.simple_paths import is_simple_path as is_path
27from networkx.utils import arbitrary_element, not_implemented_for, py_random_state
29__all__ = [
30 "hamiltonian_path",
31 "is_reachable",
32 "is_strongly_connected",
33 "is_tournament",
34 "random_tournament",
35 "score_sequence",
36]
39def index_satisfying(iterable, condition):
40 """Returns the index of the first element in `iterable` that
41 satisfies the given condition.
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).
47 `iterable` must not be empty. If `iterable` is empty, this
48 function raises :exc:`ValueError`.
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 err:
63 raise ValueError("iterable must be non-empty") from err
66@not_implemented_for("undirected")
67@not_implemented_for("multigraph")
68@nx._dispatch
69def is_tournament(G):
70 """Returns True if and only if `G` is a tournament.
72 A tournament is a directed graph, with neither self-loops nor
73 multi-edges, in which there is exactly one directed edge joining
74 each pair of distinct nodes.
76 Parameters
77 ----------
78 G : NetworkX graph
79 A directed graph representing a tournament.
81 Returns
82 -------
83 bool
84 Whether the given graph is a tournament graph.
86 Examples
87 --------
88 >>> G = nx.DiGraph([(0, 1), (1, 2), (2, 0)])
89 >>> nx.is_tournament(G)
90 True
92 Notes
93 -----
94 Some definitions require a self-loop on each node, but that is not
95 the convention used here.
97 """
98 # In a tournament, there is exactly one directed edge joining each pair.
99 return (
100 all((v in G[u]) ^ (u in G[v]) for u, v in combinations(G, 2))
101 and nx.number_of_selfloops(G) == 0
102 )
105@not_implemented_for("undirected")
106@not_implemented_for("multigraph")
107@nx._dispatch
108def hamiltonian_path(G):
109 """Returns a Hamiltonian path in the given tournament graph.
111 Each tournament has a Hamiltonian path. If furthermore, the
112 tournament is strongly connected, then the returned Hamiltonian path
113 is a Hamiltonian cycle (by joining the endpoints of the path).
115 Parameters
116 ----------
117 G : NetworkX graph
118 A directed graph representing a tournament.
120 Returns
121 -------
122 path : list
123 A list of nodes which form a Hamiltonian path in `G`.
125 Examples
126 --------
127 >>> G = nx.DiGraph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)])
128 >>> nx.is_tournament(G)
129 True
130 >>> nx.tournament.hamiltonian_path(G)
131 [0, 1, 2, 3]
133 Notes
134 -----
135 This is a recursive implementation with an asymptotic running time
136 of $O(n^2)$, ignoring multiplicative polylogarithmic factors, where
137 $n$ is the number of nodes in the graph.
139 """
140 if len(G) == 0:
141 return []
142 if len(G) == 1:
143 return [arbitrary_element(G)]
144 v = arbitrary_element(G)
145 hampath = hamiltonian_path(G.subgraph(set(G) - {v}))
146 # Get the index of the first node in the path that does *not* have
147 # an edge to `v`, then insert `v` before that node.
148 index = index_satisfying(hampath, lambda u: v not in G[u])
149 hampath.insert(index, v)
150 return hampath
153@py_random_state(1)
154@nx._dispatch(graphs=None)
155def random_tournament(n, seed=None):
156 r"""Returns a random tournament graph on `n` nodes.
158 Parameters
159 ----------
160 n : int
161 The number of nodes in the returned graph.
162 seed : integer, random_state, or None (default)
163 Indicator of random number generation state.
164 See :ref:`Randomness<randomness>`.
166 Returns
167 -------
168 G : DiGraph
169 A tournament on `n` nodes, with exactly one directed edge joining
170 each pair of distinct nodes.
172 Notes
173 -----
174 This algorithm adds, for each pair of distinct nodes, an edge with
175 uniformly random orientation. In other words, `\binom{n}{2}` flips
176 of an unbiased coin decide the orientations of the edges in the
177 graph.
179 """
180 # Flip an unbiased coin for each pair of distinct nodes.
181 coins = (seed.random() for i in range((n * (n - 1)) // 2))
182 pairs = combinations(range(n), 2)
183 edges = ((u, v) if r < 0.5 else (v, u) for (u, v), r in zip(pairs, coins))
184 return nx.DiGraph(edges)
187@not_implemented_for("undirected")
188@not_implemented_for("multigraph")
189@nx._dispatch
190def score_sequence(G):
191 """Returns the score sequence for the given tournament graph.
193 The score sequence is the sorted list of the out-degrees of the
194 nodes of the graph.
196 Parameters
197 ----------
198 G : NetworkX graph
199 A directed graph representing a tournament.
201 Returns
202 -------
203 list
204 A sorted list of the out-degrees of the nodes of `G`.
206 Examples
207 --------
208 >>> G = nx.DiGraph([(1, 0), (1, 3), (0, 2), (0, 3), (2, 1), (3, 2)])
209 >>> nx.is_tournament(G)
210 True
211 >>> nx.tournament.score_sequence(G)
212 [1, 1, 2, 2]
214 """
215 return sorted(d for v, d in G.out_degree())
218@not_implemented_for("undirected")
219@not_implemented_for("multigraph")
220@nx._dispatch
221def tournament_matrix(G):
222 r"""Returns the tournament matrix for the given tournament graph.
224 This function requires SciPy.
226 The *tournament matrix* of a tournament graph with edge set *E* is
227 the matrix *T* defined by
229 .. math::
231 T_{i j} =
232 \begin{cases}
233 +1 & \text{if } (i, j) \in E \\
234 -1 & \text{if } (j, i) \in E \\
235 0 & \text{if } i == j.
236 \end{cases}
238 An equivalent definition is `T = A - A^T`, where *A* is the
239 adjacency matrix of the graph `G`.
241 Parameters
242 ----------
243 G : NetworkX graph
244 A directed graph representing a tournament.
246 Returns
247 -------
248 SciPy sparse array
249 The tournament matrix of the tournament graph `G`.
251 Raises
252 ------
253 ImportError
254 If SciPy is not available.
256 """
257 A = nx.adjacency_matrix(G)
258 return A - A.T
261@not_implemented_for("undirected")
262@not_implemented_for("multigraph")
263@nx._dispatch
264def is_reachable(G, s, t):
265 """Decides whether there is a path from `s` to `t` in the
266 tournament.
268 This function is more theoretically efficient than the reachability
269 checks than the shortest path algorithms in
270 :mod:`networkx.algorithms.shortest_paths`.
272 The given graph **must** be a tournament, otherwise this function's
273 behavior is undefined.
275 Parameters
276 ----------
277 G : NetworkX graph
278 A directed graph representing a tournament.
280 s : node
281 A node in the graph.
283 t : node
284 A node in the graph.
286 Returns
287 -------
288 bool
289 Whether there is a path from `s` to `t` in `G`.
291 Examples
292 --------
293 >>> G = nx.DiGraph([(1, 0), (1, 3), (1, 2), (2, 3), (2, 0), (3, 0)])
294 >>> nx.is_tournament(G)
295 True
296 >>> nx.tournament.is_reachable(G, 1, 3)
297 True
298 >>> nx.tournament.is_reachable(G, 3, 2)
299 False
301 Notes
302 -----
303 Although this function is more theoretically efficient than the
304 generic shortest path functions, a speedup requires the use of
305 parallelism. Though it may in the future, the current implementation
306 does not use parallelism, thus you may not see much of a speedup.
308 This algorithm comes from [1].
310 References
311 ----------
312 .. [1] Tantau, Till.
313 "A note on the complexity of the reachability problem for
314 tournaments."
315 *Electronic Colloquium on Computational Complexity*. 2001.
316 <http://eccc.hpi-web.de/report/2001/092/>
317 """
319 def two_neighborhood(G, v):
320 """Returns the set of nodes at distance at most two from `v`.
322 `G` must be a graph and `v` a node in that graph.
324 The returned set includes the nodes at distance zero (that is,
325 the node `v` itself), the nodes at distance one (that is, the
326 out-neighbors of `v`), and the nodes at distance two.
328 """
329 # TODO This is trivially parallelizable.
330 return {
331 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)
332 }
334 def is_closed(G, nodes):
335 """Decides whether the given set of nodes is closed.
337 A set *S* of nodes is *closed* if for each node *u* in the graph
338 not in *S* and for each node *v* in *S*, there is an edge from
339 *u* to *v*.
341 """
342 # TODO This is trivially parallelizable.
343 return all(v in G[u] for u in set(G) - nodes for v in nodes)
345 # TODO This is trivially parallelizable.
346 neighborhoods = [two_neighborhood(G, v) for v in G]
347 return all(not (is_closed(G, S) and s in S and t not in S) for S in neighborhoods)
350@not_implemented_for("undirected")
351@not_implemented_for("multigraph")
352@nx._dispatch(name="tournament_is_strongly_connected")
353def is_strongly_connected(G):
354 """Decides whether the given tournament is strongly connected.
356 This function is more theoretically efficient than the
357 :func:`~networkx.algorithms.components.is_strongly_connected`
358 function.
360 The given graph **must** be a tournament, otherwise this function's
361 behavior is undefined.
363 Parameters
364 ----------
365 G : NetworkX graph
366 A directed graph representing a tournament.
368 Returns
369 -------
370 bool
371 Whether the tournament is strongly connected.
373 Examples
374 --------
375 >>> G = nx.DiGraph([(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 0)])
376 >>> nx.is_tournament(G)
377 True
378 >>> nx.tournament.is_strongly_connected(G)
379 True
380 >>> G.remove_edge(3, 0)
381 >>> G.add_edge(0, 3)
382 >>> nx.is_tournament(G)
383 True
384 >>> nx.tournament.is_strongly_connected(G)
385 False
387 Notes
388 -----
389 Although this function is more theoretically efficient than the
390 generic strong connectivity function, a speedup requires the use of
391 parallelism. Though it may in the future, the current implementation
392 does not use parallelism, thus you may not see much of a speedup.
394 This algorithm comes from [1].
396 References
397 ----------
398 .. [1] Tantau, Till.
399 "A note on the complexity of the reachability problem for
400 tournaments."
401 *Electronic Colloquium on Computational Complexity*. 2001.
402 <http://eccc.hpi-web.de/report/2001/092/>
404 """
405 # TODO This is trivially parallelizable.
406 return all(is_reachable(G, u, v) for u in G for v in G)