ioftools / networkxMiCe / networkxmaster / networkx / generators / degree_seq.py @ 5cef0f13
History  View  Annotate  Download (29.9 KB)
1 
# * coding: utf8 *


2 
# Copyright (C) 20042019 by

3 
# Aric Hagberg <hagberg@lanl.gov>

4 
# Dan Schult <dschult@colgate.edu>

5 
# Pieter Swart <swart@lanl.gov>

6 
# All rights reserved.

7 
# BSD license.

8 
#

9 
# Authors: Aric Hagberg (aric.hagberg@gmail.com)

10 
# Pieter Swart (swart@lanl.gov)

11 
# Dan Schult (dschult@colgate.edu)

12 
# Joel Miller (joel.c.miller.research@gmail.com)

13 
# Nathan Lemons (nlemons@gmail.com)

14 
# Brian Cloteaux (brian.cloteaux@nist.gov)

15 
"""Generate graphs with a given degree sequence or expected degree sequence.

16 
"""

17 
from __future__ import division 
18  
19 
import heapq 
20 
from itertools import chain 
21 
from itertools import combinations 
22 
# In Python 3, the function is `zip_longest`, in Python 2 `izip_longest`.

23 
try:

24 
from itertools import zip_longest 
25 
except ImportError: 
26 
from itertools import izip_longest as zip_longest 
27 
import math 
28 
from operator import itemgetter 
29  
30 
import networkx as nx 
31 
from networkx.utils import random_weighted_sample, py_random_state 
32  
33 
__all__ = ['configuration_model',

34 
'directed_configuration_model',

35 
'expected_degree_graph',

36 
'havel_hakimi_graph',

37 
'directed_havel_hakimi_graph',

38 
'degree_sequence_tree',

39 
'random_degree_sequence_graph']

40  
41 
chaini = chain.from_iterable 
42  
43  
44 
def _to_stublist(degree_sequence): 
45 
"""Returns a list of degreerepeated node numbers.

46 

47 
``degree_sequence`` is a list of nonnegative integers representing

48 
the degrees of nodes in a graph.

49 

50 
This function returns a list of node numbers with multiplicities

51 
according to the given degree sequence. For example, if the first

52 
element of ``degree_sequence`` is ``3``, then the first node number,

53 
``0``, will appear at the head of the returned list three times. The

54 
node numbers are assumed to be the numbers zero through

55 
``len(degree_sequence)  1``.

56 

57 
Examples

58 


59 

60 
>>> degree_sequence = [1, 2, 3]

61 
>>> _to_stublist(degree_sequence)

62 
[0, 1, 1, 2, 2, 2]

63 

64 
If a zero appears in the sequence, that means the node exists but

65 
has degree zero, so that number will be skipped in the returned

66 
list::

67 

68 
>>> degree_sequence = [2, 0, 1]

69 
>>> _to_stublist(degree_sequence)

70 
[0, 0, 2]

71 

72 
"""

73 
return list(chaini([n] * d for n, d in enumerate(degree_sequence))) 
74  
75  
76 
def _configuration_model(deg_sequence, create_using, directed=False, 
77 
in_deg_sequence=None, seed=None): 
78 
"""Helper function for generating either undirected or directed

79 
configuration model graphs.

80 

81 
``deg_sequence`` is a list of nonnegative integers representing the

82 
degree of the node whose label is the index of the list element.

83 

84 
``create_using`` see :func:`~networkx.empty_graph`.

85 

86 
``directed`` and ``in_deg_sequence`` are required if you want the

87 
returned graph to be generated using the directed configuration

88 
model algorithm. If ``directed`` is ``False``, then ``deg_sequence``

89 
is interpreted as the degree sequence of an undirected graph and

90 
``in_deg_sequence`` is ignored. Otherwise, if ``directed`` is

91 
``True``, then ``deg_sequence`` is interpreted as the outdegree

92 
sequence and ``in_deg_sequence`` as the indegree sequence of a

93 
directed graph.

94 

95 
.. note::

96 

97 
``deg_sequence`` and ``in_deg_sequence`` need not be the same

98 
length.

99 

100 
``seed`` is a random.Random or numpy.random.RandomState instance

101 

102 
This function returns a graph, directed if and only if ``directed``

103 
is ``True``, generated according to the configuration model

104 
algorithm. For more information on the algorithm, see the

105 
:func:`configuration_model` or :func:`directed_configuration_model`

106 
functions.

107 

108 
"""

109 
n = len(deg_sequence)

110 
G = nx.empty_graph(n, create_using) 
111 
# If empty, return the null graph immediately.

112 
if n == 0: 
113 
return G

114 
# Build a list of available degreerepeated nodes. For example,

115 
# for degree sequence [3, 2, 1, 1, 1], the "stub list" is

116 
# initially [0, 0, 0, 1, 1, 2, 3, 4], that is, node 0 has degree

117 
# 3 and thus is repeated 3 times, etc.

118 
#

119 
# Also, shuffle the stub list in order to get a random sequence of

120 
# node pairs.

121 
if directed:

122 
pairs = zip_longest(deg_sequence, in_deg_sequence, fillvalue=0)

123 
# Unzip the list of pairs into a pair of lists.

124 
out_deg, in_deg = zip(*pairs)

125  
126 
out_stublist = _to_stublist(out_deg) 
127 
in_stublist = _to_stublist(in_deg) 
128  
129 
seed.shuffle(out_stublist) 
130 
seed.shuffle(in_stublist) 
131 
else:

132 
stublist = _to_stublist(deg_sequence) 
133 
# Choose a random balanced bipartition of the stublist, which

134 
# gives a random pairing of nodes. In this implementation, we

135 
# shuffle the list and then split it in half.

136 
n = len(stublist)

137 
half = n // 2

138 
seed.shuffle(stublist) 
139 
out_stublist, in_stublist = stublist[:half], stublist[half:] 
140 
G.add_edges_from(zip(out_stublist, in_stublist))

141 
return G

142  
143  
144 
@py_random_state(2) 
145 
def configuration_model(deg_sequence, create_using=None, seed=None): 
146 
"""Returns a random graph with the given degree sequence.

147 

148 
The configuration model generates a random pseudograph (graph with

149 
parallel edges and self loops) by randomly assigning edges to

150 
match the given degree sequence.

151 

152 
Parameters

153 


154 
deg_sequence : list of nonnegative integers

155 
Each list entry corresponds to the degree of a node.

156 
create_using : NetworkX graph constructor, optional (default MultiGraph)

157 
Graph type to create. If graph instance, then cleared before populated.

158 
seed : integer, random_state, or None (default)

159 
Indicator of random number generation state.

160 
See :ref:`Randomness<randomness>`.

161 

162 
Returns

163 


164 
G : MultiGraph

165 
A graph with the specified degree sequence.

166 
Nodes are labeled starting at 0 with an index

167 
corresponding to the position in deg_sequence.

168 

169 
Raises

170 


171 
NetworkXError

172 
If the degree sequence does not have an even sum.

173 

174 
See Also

175 


176 
is_graphical

177 

178 
Notes

179 


180 
As described by Newman [1]_.

181 

182 
A nongraphical degree sequence (not realizable by some simple

183 
graph) is allowed since this function returns graphs with self

184 
loops and parallel edges. An exception is raised if the degree

185 
sequence does not have an even sum.

186 

187 
This configuration model construction process can lead to

188 
duplicate edges and loops. You can remove the selfloops and

189 
parallel edges (see below) which will likely result in a graph

190 
that doesn't have the exact degree sequence specified.

191 

192 
The density of selfloops and parallel edges tends to decrease as

193 
the number of nodes increases. However, typically the number of

194 
selfloops will approach a Poisson distribution with a nonzero mean,

195 
and similarly for the number of parallel edges. Consider a node

196 
with *k* stubs. The probability of being joined to another stub of

197 
the same node is basically (*k*  *1*) / *N*, where *k* is the

198 
degree and *N* is the number of nodes. So the probability of a

199 
selfloop scales like *c* / *N* for some constant *c*. As *N* grows,

200 
this means we expect *c* selfloops. Similarly for parallel edges.

201 

202 
References

203 


204 
.. [1] M.E.J. Newman, "The structure and function of complex networks",

205 
SIAM REVIEW 452, pp 167256, 2003.

206 

207 
Examples

208 


209 
You can create a degree sequence following a particular distribution

210 
by using the one of the distribution functions in

211 
:mod:`~networkx.utils.random_sequence` (or one of your own). For

212 
example, to create an undirected multigraph on one hundred nodes

213 
with degree sequence chosen from the power law distribution:

214 

215 
>>> sequence = nx.random_powerlaw_tree_sequence(100, tries=5000)

216 
>>> G = nx.configuration_model(sequence)

217 
>>> len(G)

218 
100

219 
>>> actual_degrees = [d for v, d in G.degree()]

220 
>>> actual_degrees == sequence

221 
True

222 

223 
The returned graph is a multigraph, which may have parallel

224 
edges. To remove any parallel edges from the returned graph:

225 

226 
>>> G = nx.Graph(G)

227 

228 
Similarly, to remove selfloops:

229 

230 
>>> G.remove_edges_from(nx.selfloop_edges(G))

231 

232 
"""

233 
if sum(deg_sequence) % 2 != 0: 
234 
msg = 'Invalid degree sequence: sum of degrees must be even, not odd'

235 
raise nx.NetworkXError(msg)

236  
237 
G = nx.empty_graph(0, create_using, default=nx.MultiGraph)

238 
if G.is_directed():

239 
raise nx.NetworkXNotImplemented('not implemented for directed graphs') 
240  
241 
G = _configuration_model(deg_sequence, G, seed=seed) 
242  
243 
return G

244  
245  
246 
@py_random_state(3) 
247 
def directed_configuration_model(in_degree_sequence, 
248 
out_degree_sequence, 
249 
create_using=None, seed=None): 
250 
"""Returns a directed_random graph with the given degree sequences.

251 

252 
The configuration model generates a random directed pseudograph

253 
(graph with parallel edges and self loops) by randomly assigning

254 
edges to match the given degree sequences.

255 

256 
Parameters

257 


258 
in_degree_sequence : list of nonnegative integers

259 
Each list entry corresponds to the indegree of a node.

260 
out_degree_sequence : list of nonnegative integers

261 
Each list entry corresponds to the outdegree of a node.

262 
create_using : NetworkX graph constructor, optional (default MultiDiGraph)

263 
Graph type to create. If graph instance, then cleared before populated.

264 
seed : integer, random_state, or None (default)

265 
Indicator of random number generation state.

266 
See :ref:`Randomness<randomness>`.

267 

268 
Returns

269 


270 
G : MultiDiGraph

271 
A graph with the specified degree sequences.

272 
Nodes are labeled starting at 0 with an index

273 
corresponding to the position in deg_sequence.

274 

275 
Raises

276 


277 
NetworkXError

278 
If the degree sequences do not have the same sum.

279 

280 
See Also

281 


282 
configuration_model

283 

284 
Notes

285 


286 
Algorithm as described by Newman [1]_.

287 

288 
A nongraphical degree sequence (not realizable by some simple

289 
graph) is allowed since this function returns graphs with self

290 
loops and parallel edges. An exception is raised if the degree

291 
sequences does not have the same sum.

292 

293 
This configuration model construction process can lead to

294 
duplicate edges and loops. You can remove the selfloops and

295 
parallel edges (see below) which will likely result in a graph

296 
that doesn't have the exact degree sequence specified. This

297 
"finitesize effect" decreases as the size of the graph increases.

298 

299 
References

300 


301 
.. [1] Newman, M. E. J. and Strogatz, S. H. and Watts, D. J.

302 
Random graphs with arbitrary degree distributions and their applications

303 
Phys. Rev. E, 64, 026118 (2001)

304 

305 
Examples

306 


307 
One can modify the in and outdegree sequences from an existing

308 
directed graph in order to create a new directed graph. For example,

309 
here we modify the directed path graph:

310 

311 
>>> D = nx.DiGraph([(0, 1), (1, 2), (2, 3)])

312 
>>> din = list(d for n, d in D.in_degree())

313 
>>> dout = list(d for n, d in D.out_degree())

314 
>>> din.append(1)

315 
>>> dout[0] = 2

316 
>>> # We now expect an edge from node 0 to a new node, node 3.

317 
... D = nx.directed_configuration_model(din, dout)

318 

319 
The returned graph is a directed multigraph, which may have parallel

320 
edges. To remove any parallel edges from the returned graph:

321 

322 
>>> D = nx.DiGraph(D)

323 

324 
Similarly, to remove selfloops:

325 

326 
>>> D.remove_edges_from(nx.selfloop_edges(D))

327 

328 
"""

329 
if sum(in_degree_sequence) != sum(out_degree_sequence): 
330 
msg = 'Invalid degree sequences: sequences must have equal sums'

331 
raise nx.NetworkXError(msg)

332  
333 
if create_using is None: 
334 
create_using = nx.MultiDiGraph 
335  
336 
G = _configuration_model(out_degree_sequence, create_using, directed=True,

337 
in_deg_sequence=in_degree_sequence, seed=seed) 
338  
339 
name = "directed configuration_model {} nodes {} edges"

340 
return G

341  
342  
343 
@py_random_state(1) 
344 
def expected_degree_graph(w, seed=None, selfloops=True): 
345 
r"""Returns a random graph with given expected degrees.

346 

347 
Given a sequence of expected degrees $W=(w_0,w_1,\ldots,w_{n1})$

348 
of length $n$ this algorithm assigns an edge between node $u$ and

349 
node $v$ with probability

350 

351 
.. math::

352 

353 
p_{uv} = \frac{w_u w_v}{\sum_k w_k} .

354 

355 
Parameters

356 


357 
w : list

358 
The list of expected degrees.

359 
selfloops: bool (default=True)

360 
Set to False to remove the possibility of selfloop edges.

361 
seed : integer, random_state, or None (default)

362 
Indicator of random number generation state.

363 
See :ref:`Randomness<randomness>`.

364 

365 
Returns

366 


367 
Graph

368 

369 
Examples

370 


371 
>>> z=[10 for i in range(100)]

372 
>>> G=nx.expected_degree_graph(z)

373 

374 
Notes

375 


376 
The nodes have integer labels corresponding to index of expected degrees

377 
input sequence.

378 

379 
The complexity of this algorithm is $\mathcal{O}(n+m)$ where $n$ is the

380 
number of nodes and $m$ is the expected number of edges.

381 

382 
The model in [1]_ includes the possibility of selfloop edges.

383 
Set selfloops=False to produce a graph without self loops.

384 

385 
For finite graphs this model doesn't produce exactly the given

386 
expected degree sequence. Instead the expected degrees are as

387 
follows.

388 

389 
For the case without self loops (selfloops=False),

390 

391 
.. math::

392 

393 
E[deg(u)] = \sum_{v \ne u} p_{uv}

394 
= w_u \left( 1  \frac{w_u}{\sum_k w_k} \right) .

395 

396 

397 
NetworkX uses the standard convention that a selfloop edge counts 2

398 
in the degree of a node, so with self loops (selfloops=True),

399 

400 
.. math::

401 

402 
E[deg(u)] = \sum_{v \ne u} p_{uv} + 2 p_{uu}

403 
= w_u \left( 1 + \frac{w_u}{\sum_k w_k} \right) .

404 

405 
References

406 


407 
.. [1] Fan Chung and L. Lu, Connected components in random graphs with

408 
given expected degree sequences, Ann. Combinatorics, 6,

409 
pp. 125145, 2002.

410 
.. [2] Joel Miller and Aric Hagberg,

411 
Efficient generation of networks with given expected degrees,

412 
in Algorithms and Models for the WebGraph (WAW 2011),

413 
Alan Frieze, Paul Horn, and PaweÅ‚ PraÅ‚at (Eds), LNCS 6732,

414 
pp. 115126, 2011.

415 
"""

416 
n = len(w)

417 
G = nx.empty_graph(n) 
418  
419 
# If there are no nodes are no edges in the graph, return the empty graph.

420 
if n == 0 or max(w) == 0: 
421 
return G

422  
423 
rho = 1 / sum(w) 
424 
# Sort the weights in decreasing order. The original order of the

425 
# weights dictates the order of the (integer) node labels, so we

426 
# need to remember the permutation applied in the sorting.

427 
order = sorted(enumerate(w), key=itemgetter(1), reverse=True) 
428 
mapping = {c: u for c, (u, v) in enumerate(order)} 
429 
seq = [v for u, v in order] 
430 
last = n 
431 
if not selfloops: 
432 
last = 1

433 
for u in range(last): 
434 
v = u 
435 
if not selfloops: 
436 
v += 1

437 
factor = seq[u] * rho 
438 
p = min(seq[v] * factor, 1) 
439 
while v < n and p > 0: 
440 
if p != 1: 
441 
r = seed.random() 
442 
v += int(math.floor(math.log(r, 1  p))) 
443 
if v < n:

444 
q = min(seq[v] * factor, 1) 
445 
if seed.random() < q / p:

446 
G.add_edge(mapping[u], mapping[v]) 
447 
v += 1

448 
p = q 
449 
return G

450  
451  
452 
def havel_hakimi_graph(deg_sequence, create_using=None): 
453 
"""Returns a simple graph with given degree sequence constructed

454 
using the HavelHakimi algorithm.

455 

456 
Parameters

457 


458 
deg_sequence: list of integers

459 
Each integer corresponds to the degree of a node (need not be sorted).

460 
create_using : NetworkX graph constructor, optional (default=nx.Graph)

461 
Graph type to create. If graph instance, then cleared before populated.

462 
Directed graphs are not allowed.

463 

464 
Raises

465 


466 
NetworkXException

467 
For a nongraphical degree sequence (i.e. one

468 
not realizable by some simple graph).

469 

470 
Notes

471 


472 
The HavelHakimi algorithm constructs a simple graph by

473 
successively connecting the node of highest degree to other nodes

474 
of highest degree, resorting remaining nodes by degree, and

475 
repeating the process. The resulting graph has a high

476 
degreeassociativity. Nodes are labeled 1,.., len(deg_sequence),

477 
corresponding to their position in deg_sequence.

478 

479 
The basic algorithm is from Hakimi [1]_ and was generalized by

480 
Kleitman and Wang [2]_.

481 

482 
References

483 


484 
.. [1] Hakimi S., On Realizability of a Set of Integers as

485 
Degrees of the Vertices of a Linear Graph. I,

486 
Journal of SIAM, 10(3), pp. 496506 (1962)

487 
.. [2] Kleitman D.J. and Wang D.L.

488 
Algorithms for Constructing Graphs and Digraphs with Given Valences

489 
and Factors Discrete Mathematics, 6(1), pp. 7988 (1973)

490 
"""

491 
if not nx.is_graphical(deg_sequence): 
492 
raise nx.NetworkXError('Invalid degree sequence') 
493  
494 
p = len(deg_sequence)

495 
G = nx.empty_graph(p, create_using) 
496 
if G.is_directed():

497 
raise nx.NetworkXError("Directed graphs are not supported") 
498 
num_degs = [[] for i in range(p)] 
499 
dmax, dsum, n = 0, 0, 0 
500 
for d in deg_sequence: 
501 
# Process only the nonzero integers

502 
if d > 0: 
503 
num_degs[d].append(n) 
504 
dmax, dsum, n = max(dmax, d), dsum + d, n + 1 
505 
# Return graph if no edges

506 
if n == 0: 
507 
return G

508  
509 
modstubs = [(0, 0)] * (dmax + 1) 
510 
# Successively reduce degree sequence by removing the maximum degree

511 
while n > 0: 
512 
# Retrieve the maximum degree in the sequence

513 
while len(num_degs[dmax]) == 0: 
514 
dmax = 1

515 
# If there are not enough stubs to connect to, then the sequence is

516 
# not graphical

517 
if dmax > n  1: 
518 
raise nx.NetworkXError('Nongraphical integer sequence') 
519  
520 
# Remove largest stub in list

521 
source = num_degs[dmax].pop() 
522 
n = 1

523 
# Reduce the next dmax largest stubs

524 
mslen = 0

525 
k = dmax 
526 
for i in range(dmax): 
527 
while len(num_degs[k]) == 0: 
528 
k = 1

529 
target = num_degs[k].pop() 
530 
G.add_edge(source, target) 
531 
n = 1

532 
if k > 1: 
533 
modstubs[mslen] = (k  1, target)

534 
mslen += 1

535 
# Add back to the list any nonzero stubs that were removed

536 
for i in range(mslen): 
537 
(stubval, stubtarget) = modstubs[i] 
538 
num_degs[stubval].append(stubtarget) 
539 
n += 1

540  
541 
return G

542  
543  
544 
def directed_havel_hakimi_graph(in_deg_sequence, 
545 
out_deg_sequence, 
546 
create_using=None):

547 
"""Returns a directed graph with the given degree sequences.

548 

549 
Parameters

550 


551 
in_deg_sequence : list of integers

552 
Each list entry corresponds to the indegree of a node.

553 
out_deg_sequence : list of integers

554 
Each list entry corresponds to the outdegree of a node.

555 
create_using : NetworkX graph constructor, optional (default DiGraph)

556 
Graph type to create. If graph instance, then cleared before populated.

557 

558 
Returns

559 


560 
G : DiGraph

561 
A graph with the specified degree sequences.

562 
Nodes are labeled starting at 0 with an index

563 
corresponding to the position in deg_sequence

564 

565 
Raises

566 


567 
NetworkXError

568 
If the degree sequences are not digraphical.

569 

570 
See Also

571 


572 
configuration_model

573 

574 
Notes

575 


576 
Algorithm as described by Kleitman and Wang [1]_.

577 

578 
References

579 


580 
.. [1] D.J. Kleitman and D.L. Wang

581 
Algorithms for Constructing Graphs and Digraphs with Given Valences

582 
and Factors Discrete Mathematics, 6(1), pp. 7988 (1973)

583 
"""

584 
assert(nx.utils.is_list_of_ints(in_deg_sequence))

585 
assert(nx.utils.is_list_of_ints(out_deg_sequence))

586  
587 
# Process the sequences and form two heaps to store degree pairs with

588 
# either zero or nonzero out degrees

589 
sumin, sumout = 0, 0 
590 
nin, nout = len(in_deg_sequence), len(out_deg_sequence) 
591 
maxn = max(nin, nout)

592 
G = nx.empty_graph(maxn, create_using, default=nx.DiGraph) 
593 
if maxn == 0: 
594 
return G

595 
maxin = 0

596 
stubheap, zeroheap = [], [] 
597 
for n in range(maxn): 
598 
in_deg, out_deg = 0, 0 
599 
if n < nout:

600 
out_deg = out_deg_sequence[n] 
601 
if n < nin:

602 
in_deg = in_deg_sequence[n] 
603 
if in_deg < 0 or out_deg < 0: 
604 
raise nx.NetworkXError(

605 
'Invalid degree sequences. Sequence values must be positive.')

606 
sumin, sumout, maxin = sumin + in_deg, sumout + out_deg, max(maxin, in_deg)

607 
if in_deg > 0: 
608 
stubheap.append((1 * out_deg, 1 * in_deg, n)) 
609 
elif out_deg > 0: 
610 
zeroheap.append((1 * out_deg, n))

611 
if sumin != sumout:

612 
raise nx.NetworkXError(

613 
'Invalid degree sequences. Sequences must have equal sums.')

614 
heapq.heapify(stubheap) 
615 
heapq.heapify(zeroheap) 
616  
617 
modstubs = [(0, 0, 0)] * (maxin + 1) 
618 
# Successively reduce degree sequence by removing the maximum

619 
while stubheap:

620 
# Remove first value in the sequence with a nonzero in degree

621 
(freeout, freein, target) = heapq.heappop(stubheap) 
622 
freein *= 1

623 
if freein > len(stubheap) + len(zeroheap): 
624 
raise nx.NetworkXError('Nondigraphical integer sequence') 
625  
626 
# Attach arcs from the nodes with the most stubs

627 
mslen = 0

628 
for i in range(freein): 
629 
if zeroheap and (not stubheap or stubheap[0][0] > zeroheap[0][0]): 
630 
(stubout, stubsource) = heapq.heappop(zeroheap) 
631 
stubin = 0

632 
else:

633 
(stubout, stubin, stubsource) = heapq.heappop(stubheap) 
634 
if stubout == 0: 
635 
raise nx.NetworkXError('Nondigraphical integer sequence') 
636 
G.add_edge(stubsource, target) 
637 
# Check if source is now totally connected

638 
if stubout + 1 < 0 or stubin < 0: 
639 
modstubs[mslen] = (stubout + 1, stubin, stubsource)

640 
mslen += 1

641  
642 
# Add the nodes back to the heaps that still have available stubs

643 
for i in range(mslen): 
644 
stub = modstubs[i] 
645 
if stub[1] < 0: 
646 
heapq.heappush(stubheap, stub) 
647 
else:

648 
heapq.heappush(zeroheap, (stub[0], stub[2])) 
649 
if freeout < 0: 
650 
heapq.heappush(zeroheap, (freeout, target)) 
651  
652 
return G

653  
654  
655 
def degree_sequence_tree(deg_sequence, create_using=None): 
656 
"""Make a tree for the given degree sequence.

657 

658 
A tree has #nodes#edges=1 so

659 
the degree sequence must have

660 
len(deg_sequence)sum(deg_sequence)/2=1

661 
"""

662 
# The sum of the degree sequence must be even (for any undirected graph).

663 
degree_sum = sum(deg_sequence)

664 
if degree_sum % 2 != 0: 
665 
msg = 'Invalid degree sequence: sum of degrees must be even, not odd'

666 
raise nx.NetworkXError(msg)

667 
if len(deg_sequence)  degree_sum // 2 != 1: 
668 
msg = ('Invalid degree sequence: tree must have number of nodes equal'

669 
' to one less than the number of edges')

670 
raise nx.NetworkXError(msg)

671 
G = nx.empty_graph(0, create_using)

672 
if G.is_directed():

673 
raise nx.NetworkXError("Directed Graph not supported") 
674  
675 
# Sort all degrees greater than 1 in decreasing order.

676 
#

677 
# TODO Does this need to be sorted in reverse order?

678 
deg = sorted((s for s in deg_sequence if s > 1), reverse=True) 
679  
680 
# make path graph as backbone

681 
n = len(deg) + 2 
682 
nx.add_path(G, range(n))

683 
last = n 
684  
685 
# add the leaves

686 
for source in range(1, n  1): 
687 
nedges = deg.pop()  2

688 
for target in range(last, last + nedges): 
689 
G.add_edge(source, target) 
690 
last += nedges 
691  
692 
# in case we added one too many

693 
if len(G) > len(deg_sequence): 
694 
G.remove_node(0)

695 
return G

696  
697  
698 
@py_random_state(1) 
699 
def random_degree_sequence_graph(sequence, seed=None, tries=10): 
700 
r"""Returns a simple random graph with the given degree sequence.

701 

702 
If the maximum degree $d_m$ in the sequence is $O(m^{1/4})$ then the

703 
algorithm produces almost uniform random graphs in $O(m d_m)$ time

704 
where $m$ is the number of edges.

705 

706 
Parameters

707 


708 
sequence : list of integers

709 
Sequence of degrees

710 
seed : integer, random_state, or None (default)

711 
Indicator of random number generation state.

712 
See :ref:`Randomness<randomness>`.

713 
tries : int, optional

714 
Maximum number of tries to create a graph

715 

716 
Returns

717 


718 
G : Graph

719 
A graph with the specified degree sequence.

720 
Nodes are labeled starting at 0 with an index

721 
corresponding to the position in the sequence.

722 

723 
Raises

724 


725 
NetworkXUnfeasible

726 
If the degree sequence is not graphical.

727 
NetworkXError

728 
If a graph is not produced in specified number of tries

729 

730 
See Also

731 


732 
is_graphical, configuration_model

733 

734 
Notes

735 


736 
The generator algorithm [1]_ is not guaranteed to produce a graph.

737 

738 
References

739 


740 
.. [1] Moshen Bayati, Jeong Han Kim, and Amin Saberi,

741 
A sequential algorithm for generating random graphs.

742 
Algorithmica, Volume 58, Number 4, 860910,

743 
DOI: 10.1007/s0045300993401

744 

745 
Examples

746 


747 
>>> sequence = [1, 2, 2, 3]

748 
>>> G = nx.random_degree_sequence_graph(sequence, seed=42)

749 
>>> sorted(d for n, d in G.degree())

750 
[1, 2, 2, 3]

751 
"""

752 
DSRG = DegreeSequenceRandomGraph(sequence, seed) 
753 
for try_n in range(tries): 
754 
try:

755 
return DSRG.generate()

756 
except nx.NetworkXUnfeasible:

757 
pass

758 
raise nx.NetworkXError('failed to generate graph in %d tries' % tries) 
759  
760  
761 
class DegreeSequenceRandomGraph(object): 
762 
# class to generate random graphs with a given degree sequence

763 
# use random_degree_sequence_graph()

764 
def __init__(self, degree, rng): 
765 
if not nx.is_graphical(degree): 
766 
raise nx.NetworkXUnfeasible('degree sequence is not graphical') 
767 
self.rng = rng

768 
self.degree = list(degree) 
769 
# node labels are integers 0,...,n1

770 
self.m = sum(self.degree) / 2.0 # number of edges 
771 
try:

772 
self.dmax = max(self.degree) # maximum degree 
773 
except ValueError: 
774 
self.dmax = 0 
775  
776 
def generate(self): 
777 
# remaining_degree is mapping from int>remaining degree

778 
self.remaining_degree = dict(enumerate(self.degree)) 
779 
# add all nodes to make sure we get isolated nodes

780 
self.graph = nx.Graph()

781 
self.graph.add_nodes_from(self.remaining_degree) 
782 
# remove zero degree nodes

783 
for n, d in list(self.remaining_degree.items()): 
784 
if d == 0: 
785 
del self.remaining_degree[n] 
786 
if len(self.remaining_degree) > 0: 
787 
# build graph in three phases according to how many unmatched edges

788 
self.phase1()

789 
self.phase2()

790 
self.phase3()

791 
return self.graph 
792  
793 
def update_remaining(self, u, v, aux_graph=None): 
794 
# decrement remaining nodes, modify auxiliary graph if in phase3

795 
if aux_graph is not None: 
796 
# remove edges from auxiliary graph

797 
aux_graph.remove_edge(u, v) 
798 
if self.remaining_degree[u] == 1: 
799 
del self.remaining_degree[u] 
800 
if aux_graph is not None: 
801 
aux_graph.remove_node(u) 
802 
else:

803 
self.remaining_degree[u] = 1 
804 
if self.remaining_degree[v] == 1: 
805 
del self.remaining_degree[v] 
806 
if aux_graph is not None: 
807 
aux_graph.remove_node(v) 
808 
else:

809 
self.remaining_degree[v] = 1 
810  
811 
def p(self, u, v): 
812 
# degree probability

813 
return 1  self.degree[u] * self.degree[v] / (4.0 * self.m) 
814  
815 
def q(self, u, v): 
816 
# remaining degree probability

817 
norm = float(max(self.remaining_degree.values()))**2 
818 
return self.remaining_degree[u] * self.remaining_degree[v] / norm 
819  
820 
def suitable_edge(self): 
821 
"""Returns True if and only if an arbitrary remaining node can

822 
potentially be joined with some other remaining node.

823 

824 
"""

825 
nodes = iter(self.remaining_degree) 
826 
u = next(nodes)

827 
return any(v not in self.graph[u] for v in nodes) 
828  
829 
def phase1(self): 
830 
# choose node pairs from (degree) weighted distribution

831 
rem_deg = self.remaining_degree

832 
while sum(rem_deg.values()) >= 2 * self.dmax**2: 
833 
u, v = sorted(random_weighted_sample(rem_deg, 2, self.rng)) 
834 
if self.graph.has_edge(u, v): 
835 
continue

836 
if self.rng.random() < self.p(u, v): # accept edge 
837 
self.graph.add_edge(u, v)

838 
self.update_remaining(u, v)

839  
840 
def phase2(self): 
841 
# choose remaining nodes uniformly at random and use rejection sampling

842 
remaining_deg = self.remaining_degree

843 
rng = self.rng

844 
while len(remaining_deg) >= 2 * self.dmax: 
845 
while True: 
846 
u, v = sorted(rng.sample(remaining_deg.keys(), 2)) 
847 
if self.graph.has_edge(u, v): 
848 
continue

849 
if rng.random() < self.q(u, v): 
850 
break

851 
if rng.random() < self.p(u, v): # accept edge 
852 
self.graph.add_edge(u, v)

853 
self.update_remaining(u, v)

854  
855 
def phase3(self): 
856 
# build potential remaining edges and choose with rejection sampling

857 
potential_edges = combinations(self.remaining_degree, 2) 
858 
# build auxiliary graph of potential edges not already in graph

859 
H = nx.Graph([(u, v) for (u, v) in potential_edges 
860 
if not self.graph.has_edge(u, v)]) 
861 
rng = self.rng

862 
while self.remaining_degree: 
863 
if not self.suitable_edge(): 
864 
raise nx.NetworkXUnfeasible('no suitable edges left') 
865 
while True: 
866 
u, v = sorted(rng.choice(list(H.edges()))) 
867 
if rng.random() < self.q(u, v): 
868 
break

869 
if rng.random() < self.p(u, v): # accept edge 
870 
self.graph.add_edge(u, v)

871 
self.update_remaining(u, v, aux_graph=H)
