ioftools / networkxMiCe / networkxmaster / 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 
# Precondition: 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 nonempty') 
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 selfloops nor

75 
multiedges, 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 selfloop 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 outdegrees 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 outdegrees 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.hpiweb.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 
outneighbors 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.hpiweb.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) 