Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / tournament.py @ 5cef0f13

History | View | Annotate | Download (10.4 KB)

1
# tournament.py - functions for tournament graphs
2
#
3
# Copyright 2015 NetworkX developers.
4
#
5
# This file is part of NetworkX.
6
#
7
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
8
# information.
9
"""Functions concerning tournament graphs.
10

11
A `tournament graph`_ is a complete oriented graph. In other words, it
12
is a directed graph in which there is exactly one directed edge joining
13
each pair of distinct nodes. For each function in this module that
14
accepts a graph as input, you must provide a tournament graph. The
15
responsibility is on the caller to ensure that the graph is a tournament
16
graph.
17

18
To access the functions in this module, you must access them through the
19
:mod:`networkx.algorithms.tournament` module::
20

21
    >>> import networkx as nx
22
    >>> from networkx.algorithms import tournament
23
    >>> G = nx.DiGraph([(0, 1), (1, 2), (2, 0)])
24
    >>> tournament.is_tournament(G)
25
    True
26

27
.. _tournament graph: https://en.wikipedia.org/wiki/Tournament_%28graph_theory%29
28

29
"""
30
from itertools import combinations
31

    
32
import networkx as nx
33
from networkx.algorithms.simple_paths import is_simple_path as is_path
34
from networkx.utils import arbitrary_element
35
from networkx.utils import not_implemented_for
36
from networkx.utils import py_random_state
37

    
38
__all__ = ['hamiltonian_path', 'is_reachable', 'is_strongly_connected',
39
           'is_tournament', 'random_tournament', 'score_sequence']
40

    
41

    
42
def index_satisfying(iterable, condition):
43
    """Returns the index of the first element in `iterable` that
44
    satisfies the given condition.
45

46
    If no such element is found (that is, when the iterable is
47
    exhausted), this returns the length of the iterable (that is, one
48
    greater than the last index of the iterable).
49

50
    `iterable` must not be empty. If `iterable` is empty, this
51
    function raises :exc:`ValueError`.
52

53
    """
54
    # Pre-condition: iterable must not be empty.
55
    for i, x in enumerate(iterable):
56
        if condition(x):
57
            return i
58
    # If we reach the end of the iterable without finding an element
59
    # that satisfies the condition, return the length of the iterable,
60
    # which is one greater than the index of its last element. If the
61
    # iterable was empty, `i` will not be defined, so we raise an
62
    # exception.
63
    try:
64
        return i + 1
65
    except NameError:
66
        raise ValueError('iterable must be non-empty')
67

    
68

    
69
@not_implemented_for('undirected')
70
@not_implemented_for('multigraph')
71
def is_tournament(G):
72
    """Returns True if and only if `G` is a tournament.
73

74
    A tournament is a directed graph, with neither self-loops nor
75
    multi-edges, in which there is exactly one directed edge joining
76
    each pair of distinct nodes.
77

78
    Parameters
79
    ----------
80
    G : NetworkX graph
81
        A directed graph representing a tournament.
82

83
    Returns
84
    -------
85
    bool
86
        Whether the given graph is a tournament graph.
87

88
    Notes
89
    -----
90
    Some definitions require a self-loop on each node, but that is not
91
    the convention used here.
92

93
    """
94
    # In a tournament, there is exactly one directed edge joining each pair.
95
    return (all((v in G[u]) ^ (u in G[v]) for u, v in combinations(G, 2)) and
96
            nx.number_of_selfloops(G) == 0)
97

    
98

    
99
@not_implemented_for('undirected')
100
@not_implemented_for('multigraph')
101
def hamiltonian_path(G):
102
    """Returns a Hamiltonian path in the given tournament graph.
103

104
    Each tournament has a Hamiltonian path. If furthermore, the
105
    tournament is strongly connected, then the returned Hamiltonian path
106
    is a Hamiltonian cycle (by joining the endpoints of the path).
107

108
    Parameters
109
    ----------
110
    G : NetworkX graph
111
        A directed graph representing a tournament.
112

113
    Returns
114
    -------
115
    bool
116
        Whether the given graph is a tournament graph.
117

118
    Notes
119
    -----
120
    This is a recursive implementation with an asymptotic running time
121
    of $O(n^2)$, ignoring multiplicative polylogarithmic factors, where
122
    $n$ is the number of nodes in the graph.
123

124
    """
125
    if len(G) == 0:
126
        return []
127
    if len(G) == 1:
128
        return [arbitrary_element(G)]
129
    v = arbitrary_element(G)
130
    hampath = hamiltonian_path(G.subgraph(set(G) - {v}))
131
    # Get the index of the first node in the path that does *not* have
132
    # an edge to `v`, then insert `v` before that node.
133
    index = index_satisfying(hampath, lambda u: v not in G[u])
134
    hampath.insert(index, v)
135
    return hampath
136

    
137

    
138
@py_random_state(1)
139
def random_tournament(n, seed=None):
140
    r"""Returns a random tournament graph on `n` nodes.
141

142
    Parameters
143
    ----------
144
    n : int
145
        The number of nodes in the returned graph.
146
    seed : integer, random_state, or None (default)
147
        Indicator of random number generation state.
148
        See :ref:`Randomness<randomness>`.
149

150
    Returns
151
    -------
152
    bool
153
        Whether the given graph is a tournament graph.
154

155
    Notes
156
    -----
157
    This algorithm adds, for each pair of distinct nodes, an edge with
158
    uniformly random orientation. In other words, `\binom{n}{2}` flips
159
    of an unbiased coin decide the orientations of the edges in the
160
    graph.
161

162
    """
163
    # Flip an unbiased coin for each pair of distinct nodes.
164
    coins = (seed.random() for i in range((n * (n - 1)) // 2))
165
    pairs = combinations(range(n), 2)
166
    edges = ((u, v) if r < 0.5 else (v, u) for (u, v), r in zip(pairs, coins))
167
    return nx.DiGraph(edges)
168

    
169

    
170
@not_implemented_for('undirected')
171
@not_implemented_for('multigraph')
172
def score_sequence(G):
173
    """Returns the score sequence for the given tournament graph.
174

175
    The score sequence is the sorted list of the out-degrees of the
176
    nodes of the graph.
177

178
    Parameters
179
    ----------
180
    G : NetworkX graph
181
        A directed graph representing a tournament.
182

183
    Returns
184
    -------
185
    list
186
        A sorted list of the out-degrees of the nodes of `G`.
187

188
    """
189
    return sorted(d for v, d in G.out_degree())
190

    
191

    
192
@not_implemented_for('undirected')
193
@not_implemented_for('multigraph')
194
def tournament_matrix(G):
195
    r"""Returns the tournament matrix for the given tournament graph.
196

197
    This function requires SciPy.
198

199
    The *tournament matrix* of a tournament graph with edge set *E* is
200
    the matrix *T* defined by
201

202
    .. math::
203

204
       T_{i j} =
205
       \begin{cases}
206
       +1 & \text{if } (i, j) \in E \\
207
       -1 & \text{if } (j, i) \in E \\
208
       0 & \text{if } i == j.
209
       \end{cases}
210

211
    An equivalent definition is `T = A - A^T`, where *A* is the
212
    adjacency matrix of the graph `G`.
213

214
    Parameters
215
    ----------
216
    G : NetworkX graph
217
        A directed graph representing a tournament.
218

219
    Returns
220
    -------
221
    SciPy sparse matrix
222
        The tournament matrix of the tournament graph `G`.
223

224
    Raises
225
    ------
226
    ImportError
227
        If SciPy is not available.
228

229
    """
230
    A = nx.adjacency_matrix(G)
231
    return A - A.T
232

    
233

    
234
@not_implemented_for('undirected')
235
@not_implemented_for('multigraph')
236
def is_reachable(G, s, t):
237
    """Decides whether there is a path from `s` to `t` in the
238
    tournament.
239

240
    This function is more theoretically efficient than the reachability
241
    checks than the shortest path algorithms in
242
    :mod:`networkx.algorithms.shortest_paths`.
243

244
    The given graph **must** be a tournament, otherwise this function's
245
    behavior is undefined.
246

247
    Parameters
248
    ----------
249
    G : NetworkX graph
250
        A directed graph representing a tournament.
251

252
    s : node
253
        A node in the graph.
254

255
    t : node
256
        A node in the graph.
257

258
    Returns
259
    -------
260
    bool
261
        Whether there is a path from `s` to `t` in `G`.
262

263
    Notes
264
    -----
265
    Although this function is more theoretically efficient than the
266
    generic shortest path functions, a speedup requires the use of
267
    parallelism. Though it may in the future, the current implementation
268
    does not use parallelism, thus you may not see much of a speedup.
269

270
    This algorithm comes from [1].
271

272
    References
273
    ----------
274
    .. [1] Tantau, Till.
275
           "A note on the complexity of the reachability problem for
276
           tournaments."
277
           *Electronic Colloquium on Computational Complexity*. 2001.
278
           <http://eccc.hpi-web.de/report/2001/092/>
279

280
    """
281

    
282
    def two_neighborhood(G, v):
283
        """Returns the set of nodes at distance at most two from `v`.
284

285
        `G` must be a graph and `v` a node in that graph.
286

287
        The returned set includes the nodes at distance zero (that is,
288
        the node `v` itself), the nodes at distance one (that is, the
289
        out-neighbors of `v`), and the nodes at distance two.
290

291
        """
292
        # TODO This is trivially parallelizable.
293
        return {x for x in G
294
                if x == v or x in G[v] or
295
                any(is_path(G, [v, z, x]) for z in G)}
296

    
297
    def is_closed(G, nodes):
298
        """Decides whether the given set of nodes is closed.
299

300
        A set *S* of nodes is *closed* if for each node *u* in the graph
301
        not in *S* and for each node *v* in *S*, there is an edge from
302
        *u* to *v*.
303

304
        """
305
        # TODO This is trivially parallelizable.
306
        return all(v in G[u] for u in set(G) - nodes for v in nodes)
307

    
308
    # TODO This is trivially parallelizable.
309
    neighborhoods = [two_neighborhood(G, v) for v in G]
310
    return all(not (is_closed(G, S) and s in S and t not in S)
311
               for S in neighborhoods)
312

    
313

    
314
@not_implemented_for('undirected')
315
@not_implemented_for('multigraph')
316
def is_strongly_connected(G):
317
    """Decides whether the given tournament is strongly connected.
318

319
    This function is more theoretically efficient than the
320
    :func:`~networkx.algorithms.components.is_strongly_connected`
321
    function.
322

323
    The given graph **must** be a tournament, otherwise this function's
324
    behavior is undefined.
325

326
    Parameters
327
    ----------
328
    G : NetworkX graph
329
        A directed graph representing a tournament.
330

331
    Returns
332
    -------
333
    bool
334
        Whether the tournament is strongly connected.
335

336
    Notes
337
    -----
338
    Although this function is more theoretically efficient than the
339
    generic strong connectivity function, a speedup requires the use of
340
    parallelism. Though it may in the future, the current implementation
341
    does not use parallelism, thus you may not see much of a speedup.
342

343
    This algorithm comes from [1].
344

345
    References
346
    ----------
347
    .. [1] Tantau, Till.
348
           "A note on the complexity of the reachability problem for
349
           tournaments."
350
           *Electronic Colloquium on Computational Complexity*. 2001.
351
           <http://eccc.hpi-web.de/report/2001/092/>
352

353
    """
354
    # TODO This is trivially parallelizable.
355
    return all(is_reachable(G, u, v) for u in G for v in G)