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"""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"""
24from itertools import combinations
26import networkx as nx
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 "tournament_matrix",
37]
40def index_satisfying(iterable, condition):
41 """Returns the index of the first element in `iterable` that
42 satisfies the given condition.
44 If no such element is found (that is, when the iterable is
45 exhausted), this returns the length of the iterable (that is, one
46 greater than the last index of the iterable).
48 `iterable` must not be empty. If `iterable` is empty, this
49 function raises :exc:`ValueError`.
51 """
52 # Pre-condition: iterable must not be empty.
53 for i, x in enumerate(iterable):
54 if condition(x):
55 return i
56 # If we reach the end of the iterable without finding an element
57 # that satisfies the condition, return the length of the iterable,
58 # which is one greater than the index of its last element. If the
59 # iterable was empty, `i` will not be defined, so we raise an
60 # exception.
61 try:
62 return i + 1
63 except NameError as err:
64 raise ValueError("iterable must be non-empty") from err
67@not_implemented_for("undirected")
68@not_implemented_for("multigraph")
69@nx._dispatchable
70def is_tournament(G):
71 """Returns True if and only if `G` is a tournament.
73 A tournament is a directed graph, with neither self-loops nor
74 multi-edges, in which there is exactly one directed edge joining
75 each pair of distinct nodes.
77 Parameters
78 ----------
79 G : NetworkX graph
80 A directed graph representing a tournament.
82 Returns
83 -------
84 bool
85 Whether the given graph is a tournament graph.
87 Examples
88 --------
89 >>> G = nx.DiGraph([(0, 1), (1, 2), (2, 0)])
90 >>> nx.is_tournament(G)
91 True
93 Notes
94 -----
95 Some definitions require a self-loop on each node, but that is not
96 the convention used here.
98 """
99 # In a tournament, there is exactly one directed edge joining each pair.
100 return (
101 all((v in G[u]) ^ (u in G[v]) for u, v in combinations(G, 2))
102 and nx.number_of_selfloops(G) == 0
103 )
106@not_implemented_for("undirected")
107@not_implemented_for("multigraph")
108@nx._dispatchable
109def hamiltonian_path(G):
110 """Returns a Hamiltonian path in the given tournament graph.
112 Each tournament has a Hamiltonian path. If furthermore, the
113 tournament is strongly connected, then the returned Hamiltonian path
114 is a Hamiltonian cycle (by joining the endpoints of the path).
116 Parameters
117 ----------
118 G : NetworkX graph
119 A directed graph representing a tournament.
121 Returns
122 -------
123 path : list
124 A list of nodes which form a Hamiltonian path in `G`.
126 Examples
127 --------
128 >>> G = nx.DiGraph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)])
129 >>> nx.is_tournament(G)
130 True
131 >>> nx.tournament.hamiltonian_path(G)
132 [0, 1, 2, 3]
134 Notes
135 -----
136 This is a recursive implementation with an asymptotic running time
137 of $O(n^2)$, ignoring multiplicative polylogarithmic factors, where
138 $n$ is the number of nodes in the graph.
140 """
141 if len(G) == 0:
142 return []
143 if len(G) == 1:
144 return [arbitrary_element(G)]
145 v = arbitrary_element(G)
146 hampath = hamiltonian_path(G.subgraph(set(G) - {v}))
147 # Get the index of the first node in the path that does *not* have
148 # an edge to `v`, then insert `v` before that node.
149 index = index_satisfying(hampath, lambda u: v not in G[u])
150 hampath.insert(index, v)
151 return hampath
154@py_random_state(1)
155@nx._dispatchable(graphs=None, returns_graph=True)
156def random_tournament(n, seed=None):
157 r"""Returns a random tournament graph on `n` nodes.
159 Parameters
160 ----------
161 n : int
162 The number of nodes in the returned graph.
163 seed : integer, random_state, or None (default)
164 Indicator of random number generation state.
165 See :ref:`Randomness<randomness>`.
167 Returns
168 -------
169 G : DiGraph
170 A tournament on `n` nodes, with exactly one directed edge joining
171 each pair of distinct nodes.
173 Notes
174 -----
175 This algorithm adds, for each pair of distinct nodes, an edge with
176 uniformly random orientation. In other words, `\binom{n}{2}` flips
177 of an unbiased coin decide the orientations of the edges in the
178 graph.
180 """
181 # Flip an unbiased coin for each pair of distinct nodes.
182 coins = (seed.random() for i in range((n * (n - 1)) // 2))
183 pairs = combinations(range(n), 2)
184 edges = ((u, v) if r < 0.5 else (v, u) for (u, v), r in zip(pairs, coins))
185 return nx.DiGraph(edges)
188@not_implemented_for("undirected")
189@not_implemented_for("multigraph")
190@nx._dispatchable
191def score_sequence(G):
192 """Returns the score sequence for the given tournament graph.
194 The score sequence is the sorted list of the out-degrees of the
195 nodes of the graph.
197 Parameters
198 ----------
199 G : NetworkX graph
200 A directed graph representing a tournament.
202 Returns
203 -------
204 list
205 A sorted list of the out-degrees of the nodes of `G`.
207 Examples
208 --------
209 >>> G = nx.DiGraph([(1, 0), (1, 3), (0, 2), (0, 3), (2, 1), (3, 2)])
210 >>> nx.is_tournament(G)
211 True
212 >>> nx.tournament.score_sequence(G)
213 [1, 1, 2, 2]
215 """
216 return sorted(d for v, d in G.out_degree())
219@not_implemented_for("undirected")
220@not_implemented_for("multigraph")
221@nx._dispatchable(preserve_edge_attrs={"G": {"weight": 1}})
222def tournament_matrix(G):
223 r"""Returns the tournament matrix for the given tournament graph.
225 This function requires SciPy.
227 The *tournament matrix* of a tournament graph with edge set *E* is
228 the matrix *T* defined by
230 .. math::
232 T_{i j} =
233 \begin{cases}
234 +1 & \text{if } (i, j) \in E \\
235 -1 & \text{if } (j, i) \in E \\
236 0 & \text{if } i == j.
237 \end{cases}
239 An equivalent definition is `T = A - A^T`, where *A* is the
240 adjacency matrix of the graph `G`.
242 Parameters
243 ----------
244 G : NetworkX graph
245 A directed graph representing a tournament.
247 Returns
248 -------
249 SciPy sparse array
250 The tournament matrix of the tournament graph `G`.
252 Raises
253 ------
254 ImportError
255 If SciPy is not available.
257 """
258 A = nx.adjacency_matrix(G)
259 return A - A.T
262@not_implemented_for("undirected")
263@not_implemented_for("multigraph")
264@nx._dispatchable
265def is_reachable(G, s, t):
266 """Decides whether there is a path from `s` to `t` in the
267 tournament.
269 This function is more theoretically efficient than the reachability
270 checks than the shortest path algorithms in
271 :mod:`networkx.algorithms.shortest_paths`.
273 The given graph **must** be a tournament, otherwise this function's
274 behavior is undefined.
276 Parameters
277 ----------
278 G : NetworkX graph
279 A directed graph representing a tournament.
281 s : node
282 A node in the graph.
284 t : node
285 A node in the graph.
287 Returns
288 -------
289 bool
290 Whether there is a path from `s` to `t` in `G`.
292 Examples
293 --------
294 >>> G = nx.DiGraph([(1, 0), (1, 3), (1, 2), (2, 3), (2, 0), (3, 0)])
295 >>> nx.is_tournament(G)
296 True
297 >>> nx.tournament.is_reachable(G, 1, 3)
298 True
299 >>> nx.tournament.is_reachable(G, 3, 2)
300 False
302 Notes
303 -----
304 Although this function is more theoretically efficient than the
305 generic shortest path functions, a speedup requires the use of
306 parallelism. Though it may in the future, the current implementation
307 does not use parallelism, thus you may not see much of a speedup.
309 This algorithm comes from [1].
311 References
312 ----------
313 .. [1] Tantau, Till.
314 "A note on the complexity of the reachability problem for
315 tournaments."
316 *Electronic Colloquium on Computational Complexity*. 2001.
317 <http://eccc.hpi-web.de/report/2001/092/>
318 """
320 def two_neighborhood(G, v):
321 """Returns the set of nodes at distance at most two from `v`.
323 `G` must be a graph and `v` a node in that graph.
325 The returned set includes the nodes at distance zero (that is,
326 the node `v` itself), the nodes at distance one (that is, the
327 out-neighbors of `v`), and the nodes at distance two.
329 """
330 v_adj = G._adj[v]
331 return {
332 x
333 for x, x_pred in G._pred.items()
334 if x == v or x in v_adj or any(z in v_adj for z in x_pred)
335 }
337 def is_closed(G, S):
338 """Decides whether the given set of nodes is closed.
340 A set *S* of nodes is *closed* if for each node *u* in the graph
341 not in *S* and for each node *v* in *S*, there is an edge from
342 *u* to *v*.
344 """
345 return all(u in S or all(v in unbrs for v in S) for u, unbrs in G._adj.items())
347 neighborhoods = (two_neighborhood(G, v) for v in G)
348 return not any(s in S and t not in S and is_closed(G, S) for S in neighborhoods)
351@not_implemented_for("undirected")
352@not_implemented_for("multigraph")
353@nx._dispatchable(name="tournament_is_strongly_connected")
354def is_strongly_connected(G):
355 """Decides whether the given tournament is strongly connected.
357 This function is more theoretically efficient than the
358 :func:`~networkx.algorithms.components.is_strongly_connected`
359 function.
361 The given graph **must** be a tournament, otherwise this function's
362 behavior is undefined.
364 Parameters
365 ----------
366 G : NetworkX graph
367 A directed graph representing a tournament.
369 Returns
370 -------
371 bool
372 Whether the tournament is strongly connected.
374 Examples
375 --------
376 >>> G = nx.DiGraph([(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 0)])
377 >>> nx.is_tournament(G)
378 True
379 >>> nx.tournament.is_strongly_connected(G)
380 True
381 >>> G.remove_edge(3, 0)
382 >>> G.add_edge(0, 3)
383 >>> nx.is_tournament(G)
384 True
385 >>> nx.tournament.is_strongly_connected(G)
386 False
388 Notes
389 -----
390 Although this function is more theoretically efficient than the
391 generic strong connectivity function, a speedup requires the use of
392 parallelism. Though it may in the future, the current implementation
393 does not use parallelism, thus you may not see much of a speedup.
395 This algorithm comes from [1].
397 References
398 ----------
399 .. [1] Tantau, Till.
400 "A note on the complexity of the reachability problem for
401 tournaments."
402 *Electronic Colloquium on Computational Complexity*. 2001.
403 <http://eccc.hpi-web.de/report/2001/092/>
405 """
406 return all(is_reachable(G, u, v) for u in G for v in G)