Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/generators/trees.py: 17%

1"""Functions for generating trees. 

2 

3The functions sampling trees at random in this module come 

4in two variants: labeled and unlabeled. The labeled variants 

5sample from every possible tree with the given number of nodes 

6uniformly at random. The unlabeled variants sample from every 

7possible *isomorphism class* of trees with the given number 

8of nodes uniformly at random. 

9 

10To understand the difference, consider the following example. 

11There are two isomorphism classes of trees with four nodes. 

12One is that of the path graph, the other is that of the 

13star graph. The unlabeled variant will return a line graph or 

14a star graph with probability 1/2. 

15 

16The labeled variant will return the line graph 

17with probability 3/4 and the star graph with probability 1/4, 

18because there are more labeled variants of the line graph 

19than of the star graph. More precisely, the line graph has 

20an automorphism group of order 2, whereas the star graph has 

21an automorphism group of order 6, so the line graph has three 

22times as many labeled variants as the star graph, and thus 

23three more chances to be drawn. 

24 

25Additionally, some functions in this module can sample rooted 

26trees and forests uniformly at random. A rooted tree is a tree 

27with a designated root node. A rooted forest is a disjoint union 

28of rooted trees. 

29""" 

30 

31import warnings 

32from collections import Counter, defaultdict 

33from math import comb, factorial 

34 

35import networkx as nx 

36from networkx.utils import py_random_state 

37 

38__all__ = [ 

39 "prefix_tree", 

40 "prefix_tree_recursive", 

41 "random_tree", 

42 "random_labeled_tree", 

43 "random_labeled_rooted_tree", 

44 "random_labeled_rooted_forest", 

45 "random_unlabeled_tree", 

46 "random_unlabeled_rooted_tree", 

47 "random_unlabeled_rooted_forest", 

48] 

49 

50 

51@nx._dispatch(graphs=None) 

52def prefix_tree(paths): 

53 """Creates a directed prefix tree from a list of paths. 

54 

55 Usually the paths are described as strings or lists of integers. 

56 

57 A "prefix tree" represents the prefix structure of the strings. 

58 Each node represents a prefix of some string. The root represents 

59 the empty prefix with children for the single letter prefixes which 

60 in turn have children for each double letter prefix starting with 

61 the single letter corresponding to the parent node, and so on. 

62 

63 More generally the prefixes do not need to be strings. A prefix refers 

64 to the start of a sequence. The root has children for each one element 

65 prefix and they have children for each two element prefix that starts 

66 with the one element sequence of the parent, and so on. 

67 

68 Note that this implementation uses integer nodes with an attribute. 

69 Each node has an attribute "source" whose value is the original element 

70 of the path to which this node corresponds. For example, suppose `paths` 

71 consists of one path: "can". Then the nodes `[1, 2, 3]` which represent 

72 this path have "source" values "c", "a" and "n". 

73 

74 All the descendants of a node have a common prefix in the sequence/path 

75 associated with that node. From the returned tree, the prefix for each 

76 node can be constructed by traversing the tree up to the root and 

77 accumulating the "source" values along the way. 

78 

79 The root node is always `0` and has "source" attribute `None`. 

80 The root is the only node with in-degree zero. 

81 The nil node is always `-1` and has "source" attribute `"NIL"`. 

82 The nil node is the only node with out-degree zero. 

83 

84 

85 Parameters 

86 ---------- 

87 paths: iterable of paths 

88 An iterable of paths which are themselves sequences. 

89 Matching prefixes among these sequences are identified with 

90 nodes of the prefix tree. One leaf of the tree is associated 

91 with each path. (Identical paths are associated with the same 

92 leaf of the tree.) 

93 

94 

95 Returns 

96 ------- 

97 tree: DiGraph 

98 A directed graph representing an arborescence consisting of the 

99 prefix tree generated by `paths`. Nodes are directed "downward", 

100 from parent to child. A special "synthetic" root node is added 

101 to be the parent of the first node in each path. A special 

102 "synthetic" leaf node, the "nil" node `-1`, is added to be the child 

103 of all nodes representing the last element in a path. (The 

104 addition of this nil node technically makes this not an 

105 arborescence but a directed acyclic graph; removing the nil node 

106 makes it an arborescence.) 

107 

108 

109 Notes 

110 ----- 

111 The prefix tree is also known as a *trie*. 

112 

113 

114 Examples 

115 -------- 

116 Create a prefix tree from a list of strings with common prefixes:: 

117 

118 >>> paths = ["ab", "abs", "ad"] 

119 >>> T = nx.prefix_tree(paths) 

120 >>> list(T.edges) 

121 [(0, 1), (1, 2), (1, 4), (2, -1), (2, 3), (3, -1), (4, -1)] 

122 

123 The leaf nodes can be obtained as predecessors of the nil node:: 

124 

125 >>> root, NIL = 0, -1 

126 >>> list(T.predecessors(NIL)) 

127 [2, 3, 4] 

128 

129 To recover the original paths that generated the prefix tree, 

130 traverse up the tree from the node `-1` to the node `0`:: 

131 

132 >>> recovered = [] 

133 >>> for v in T.predecessors(NIL): 

134 ... prefix = "" 

135 ... while v != root: 

136 ... prefix = str(T.nodes[v]["source"]) + prefix 

137 ... v = next(T.predecessors(v)) # only one predecessor 

138 ... recovered.append(prefix) 

139 >>> sorted(recovered) 

140 ['ab', 'abs', 'ad'] 

141 """ 

142 

143 def get_children(parent, paths): 

144 children = defaultdict(list) 

145 # Populate dictionary with key(s) as the child/children of the root and 

146 # value(s) as the remaining paths of the corresponding child/children 

147 for path in paths: 

148 # If path is empty, we add an edge to the NIL node. 

149 if not path: 

150 tree.add_edge(parent, NIL) 

151 continue 

152 child, *rest = path 

153 # `child` may exist as the head of more than one path in `paths`. 

154 children[child].append(rest) 

155 return children 

156 

157 # Initialize the prefix tree with a root node and a nil node. 

158 tree = nx.DiGraph() 

159 root = 0 

160 tree.add_node(root, source=None) 

161 NIL = -1 

162 tree.add_node(NIL, source="NIL") 

163 children = get_children(root, paths) 

164 stack = [(root, iter(children.items()))] 

165 while stack: 

166 parent, remaining_children = stack[-1] 

167 try: 

168 child, remaining_paths = next(remaining_children) 

169 # Pop item off stack if there are no remaining children 

170 except StopIteration: 

171 stack.pop() 

172 continue 

173 # We relabel each child with an unused name. 

174 new_name = len(tree) - 1 

175 # The "source" node attribute stores the original node name. 

176 tree.add_node(new_name, source=child) 

177 tree.add_edge(parent, new_name) 

178 children = get_children(new_name, remaining_paths) 

179 stack.append((new_name, iter(children.items()))) 

180 

181 return tree 

182 

183 

184@nx._dispatch(graphs=None) 

185def prefix_tree_recursive(paths): 

186 """Recursively creates a directed prefix tree from a list of paths. 

187 

188 The original recursive version of prefix_tree for comparison. It is 

189 the same algorithm but the recursion is unrolled onto a stack. 

190 

191 Usually the paths are described as strings or lists of integers. 

192 

193 A "prefix tree" represents the prefix structure of the strings. 

194 Each node represents a prefix of some string. The root represents 

195 the empty prefix with children for the single letter prefixes which 

196 in turn have children for each double letter prefix starting with 

197 the single letter corresponding to the parent node, and so on. 

198 

199 More generally the prefixes do not need to be strings. A prefix refers 

200 to the start of a sequence. The root has children for each one element 

201 prefix and they have children for each two element prefix that starts 

202 with the one element sequence of the parent, and so on. 

203 

204 Note that this implementation uses integer nodes with an attribute. 

205 Each node has an attribute "source" whose value is the original element 

206 of the path to which this node corresponds. For example, suppose `paths` 

207 consists of one path: "can". Then the nodes `[1, 2, 3]` which represent 

208 this path have "source" values "c", "a" and "n". 

209 

210 All the descendants of a node have a common prefix in the sequence/path 

211 associated with that node. From the returned tree, ehe prefix for each 

212 node can be constructed by traversing the tree up to the root and 

213 accumulating the "source" values along the way. 

214 

215 The root node is always `0` and has "source" attribute `None`. 

216 The root is the only node with in-degree zero. 

217 The nil node is always `-1` and has "source" attribute `"NIL"`. 

218 The nil node is the only node with out-degree zero. 

219 

220 

221 Parameters 

222 ---------- 

223 paths: iterable of paths 

224 An iterable of paths which are themselves sequences. 

225 Matching prefixes among these sequences are identified with 

226 nodes of the prefix tree. One leaf of the tree is associated 

227 with each path. (Identical paths are associated with the same 

228 leaf of the tree.) 

229 

230 

231 Returns 

232 ------- 

233 tree: DiGraph 

234 A directed graph representing an arborescence consisting of the 

235 prefix tree generated by `paths`. Nodes are directed "downward", 

236 from parent to child. A special "synthetic" root node is added 

237 to be the parent of the first node in each path. A special 

238 "synthetic" leaf node, the "nil" node `-1`, is added to be the child 

239 of all nodes representing the last element in a path. (The 

240 addition of this nil node technically makes this not an 

241 arborescence but a directed acyclic graph; removing the nil node 

242 makes it an arborescence.) 

243 

244 

245 Notes 

246 ----- 

247 The prefix tree is also known as a *trie*. 

248 

249 

250 Examples 

251 -------- 

252 Create a prefix tree from a list of strings with common prefixes:: 

253 

254 >>> paths = ["ab", "abs", "ad"] 

255 >>> T = nx.prefix_tree(paths) 

256 >>> list(T.edges) 

257 [(0, 1), (1, 2), (1, 4), (2, -1), (2, 3), (3, -1), (4, -1)] 

258 

259 The leaf nodes can be obtained as predecessors of the nil node. 

260 

261 >>> root, NIL = 0, -1 

262 >>> list(T.predecessors(NIL)) 

263 [2, 3, 4] 

264 

265 To recover the original paths that generated the prefix tree, 

266 traverse up the tree from the node `-1` to the node `0`:: 

267 

268 >>> recovered = [] 

269 >>> for v in T.predecessors(NIL): 

270 ... prefix = "" 

271 ... while v != root: 

272 ... prefix = str(T.nodes[v]["source"]) + prefix 

273 ... v = next(T.predecessors(v)) # only one predecessor 

274 ... recovered.append(prefix) 

275 >>> sorted(recovered) 

276 ['ab', 'abs', 'ad'] 

277 """ 

278 

279 def _helper(paths, root, tree): 

280 """Recursively create a trie from the given list of paths. 

281 

282 `paths` is a list of paths, each of which is itself a list of 

283 nodes, relative to the given `root` (but not including it). This 

284 list of paths will be interpreted as a tree-like structure, in 

285 which two paths that share a prefix represent two branches of 

286 the tree with the same initial segment. 

287 

288 `root` is the parent of the node at index 0 in each path. 

289 

290 `tree` is the "accumulator", the :class:`networkx.DiGraph` 

291 representing the branching to which the new nodes and edges will 

292 be added. 

293 

294 """ 

295 # For each path, remove the first node and make it a child of root. 

296 # Any remaining paths then get processed recursively. 

297 children = defaultdict(list) 

298 for path in paths: 

299 # If path is empty, we add an edge to the NIL node. 

300 if not path: 

301 tree.add_edge(root, NIL) 

302 continue 

303 child, *rest = path 

304 # `child` may exist as the head of more than one path in `paths`. 

305 children[child].append(rest) 

306 # Add a node for each child, connect root, recurse to remaining paths 

307 for child, remaining_paths in children.items(): 

308 # We relabel each child with an unused name. 

309 new_name = len(tree) - 1 

310 # The "source" node attribute stores the original node name. 

311 tree.add_node(new_name, source=child) 

312 tree.add_edge(root, new_name) 

313 _helper(remaining_paths, new_name, tree) 

314 

315 # Initialize the prefix tree with a root node and a nil node. 

316 tree = nx.DiGraph() 

317 root = 0 

318 tree.add_node(root, source=None) 

319 NIL = -1 

320 tree.add_node(NIL, source="NIL") 

321 # Populate the tree. 

322 _helper(paths, root, tree) 

323 return tree 

324 

325 

326@py_random_state(1) 

327@nx._dispatch(graphs=None) 

328def random_tree(n, seed=None, create_using=None): 

329 """Returns a uniformly random tree on `n` nodes. 

330 

331 .. deprecated:: 3.2 

332 

333 ``random_tree`` is deprecated and will be removed in NX v3.4 

334 Use ``random_labeled_tree`` instead. 

335 

336 Parameters 

337 ---------- 

338 n : int 

339 A positive integer representing the number of nodes in the tree. 

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

341 Indicator of random number generation state. 

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

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

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

345 

346 Returns 

347 ------- 

348 NetworkX graph 

349 A tree, given as an undirected graph, whose nodes are numbers in 

350 the set {0, …, *n* - 1}. 

351 

352 Raises 

353 ------ 

354 NetworkXPointlessConcept 

355 If `n` is zero (because the null graph is not a tree). 

356 

357 Notes 

358 ----- 

359 The current implementation of this function generates a uniformly 

360 random Prüfer sequence then converts that to a tree via the 

361 :func:`~networkx.from_prufer_sequence` function. Since there is a 

362 bijection between Prüfer sequences of length *n* - 2 and trees on 

363 *n* nodes, the tree is chosen uniformly at random from the set of 

364 all trees on *n* nodes. 

365 

366 Examples 

367 -------- 

368 >>> tree = nx.random_tree(n=10, seed=0) 

369 >>> nx.write_network_text(tree, sources=[0]) 

370 ╙── 0 

371 ├── 3 

372 └── 4 

373 ├── 6 

374 │ ├── 1 

375 │ ├── 2 

376 │ └── 7 

377 │ └── 8 

378 │ └── 5 

379 └── 9 

380 

381 >>> tree = nx.random_tree(n=10, seed=0, create_using=nx.DiGraph) 

382 >>> nx.write_network_text(tree) 

383 ╙── 0 

384 ├─╼ 3 

385 └─╼ 4 

386 ├─╼ 6 

387 │ ├─╼ 1 

388 │ ├─╼ 2 

389 │ └─╼ 7 

390 │ └─╼ 8 

391 │ └─╼ 5 

392 └─╼ 9 

393 """ 

394 warnings.warn( 

395 ( 

396 "\n\nrandom_tree is deprecated and will be removed in NX v3.4\n" 

397 "Use random_labeled_tree instead." 

398 ), 

399 DeprecationWarning, 

400 stacklevel=2, 

401 ) 

402 if n == 0: 

403 raise nx.NetworkXPointlessConcept("the null graph is not a tree") 

404 # Cannot create a Prüfer sequence unless `n` is at least two. 

405 if n == 1: 

406 utree = nx.empty_graph(1, create_using) 

407 else: 

408 sequence = [seed.choice(range(n)) for i in range(n - 2)] 

409 utree = nx.from_prufer_sequence(sequence) 

410 

411 if create_using is None: 

412 tree = utree 

413 else: 

414 tree = nx.empty_graph(0, create_using) 

415 if tree.is_directed(): 

416 # Use a arbitrary root node and dfs to define edge directions 

417 edges = nx.dfs_edges(utree, source=0) 

418 else: 

419 edges = utree.edges 

420 

421 # Populate the specified graph type 

422 tree.add_nodes_from(utree.nodes) 

423 tree.add_edges_from(edges) 

424 

425 return tree 

426 

427 

428@py_random_state("seed") 

429@nx._dispatch(graphs=None) 

430def random_labeled_tree(n, *, seed=None): 

431 """Returns a labeled tree on `n` nodes chosen uniformly at random. 

432 

433 Generating uniformly distributed random Prüfer sequences and 

434 converting them into the corresponding trees is a straightforward 

435 method of generating uniformly distributed random labeled trees. 

436 This function implements this method. 

437 

438 Parameters 

439 ---------- 

440 n : int 

441 The number of nodes, greater than zero. 

442 seed : random_state 

443 Indicator of random number generation state. 

444 See :ref:`Randomness<randomness>` 

445 

446 Returns 

447 ------- 

448 :class:`networkx.Graph` 

449 A `networkx.Graph` with nodes in the set {0, …, *n* - 1}. 

450 

451 Raises 

452 ------ 

453 NetworkXPointlessConcept 

454 If `n` is zero (because the null graph is not a tree). 

455 """ 

456 # Cannot create a Prüfer sequence unless `n` is at least two. 

457 if n == 0: 

458 raise nx.NetworkXPointlessConcept("the null graph is not a tree") 

459 if n == 1: 

460 return nx.empty_graph(1) 

461 return nx.from_prufer_sequence([seed.choice(range(n)) for i in range(n - 2)]) 

462 

463 

464@py_random_state("seed") 

465@nx._dispatch(graphs=None) 

466def random_labeled_rooted_tree(n, *, seed=None): 

467 """Returns a labeled rooted tree with `n` nodes. 

468 

469 The returned tree is chosen uniformly at random from all labeled rooted trees. 

470 

471 Parameters 

472 ---------- 

473 n : int 

474 The number of nodes 

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

476 Indicator of random number generation state. 

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

478 

479 Returns 

480 ------- 

481 :class:`networkx.Graph` 

482 A `networkx.Graph` with integer nodes 0 <= node <= `n` - 1. 

483 The root of the tree is selected uniformly from the nodes. 

484 The "root" graph attribute identifies the root of the tree. 

485 

486 Notes 

487 ----- 

488 This function returns the result of :func:`random_labeled_tree` 

489 with a randomly selected root. 

490 

491 Raises 

492 ------ 

493 NetworkXPointlessConcept 

494 If `n` is zero (because the null graph is not a tree). 

495 """ 

496 t = random_labeled_tree(n, seed=seed) 

497 t.graph["root"] = seed.randint(0, n - 1) 

498 return t 

499 

500 

501@py_random_state("seed") 

502@nx._dispatch(graphs=None) 

503def random_labeled_rooted_forest(n, *, seed=None): 

504 """Returns a labeled rooted forest with `n` nodes. 

505 

506 The returned forest is chosen uniformly at random using a 

507 generalization of Prüfer sequences [1]_ in the form described in [2]_. 

508 

509 Parameters 

510 ---------- 

511 n : int 

512 The number of nodes. 

513 seed : random_state 

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

515 

516 Returns 

517 ------- 

518 :class:`networkx.Graph` 

519 A `networkx.Graph` with integer nodes 0 <= node <= `n` - 1. 

520 The "roots" graph attribute is a set of integers containing the roots. 

521 

522 References 

523 ---------- 

524 .. [1] Knuth, Donald E. "Another Enumeration of Trees." 

525 Canadian Journal of Mathematics, 20 (1968): 1077-1086. 

526 https://doi.org/10.4153/CJM-1968-104-8 

527 .. [2] Rubey, Martin. "Counting Spanning Trees". Diplomarbeit 

528 zur Erlangung des akademischen Grades Magister der 

529 Naturwissenschaften an der Formal- und Naturwissenschaftlichen 

530 Fakultät der Universität Wien. Wien, May 2000. 

531 """ 

532 

533 # Select the number of roots by iterating over the cumulative count of trees 

534 # with at most k roots 

535 def _select_k(n, seed): 

536 r = seed.randint(0, (n + 1) ** (n - 1) - 1) 

537 cum_sum = 0 

538 for k in range(1, n): 

539 cum_sum += (factorial(n - 1) * n ** (n - k)) // ( 

540 factorial(k - 1) * factorial(n - k) 

541 ) 

542 if r < cum_sum: 

543 return k 

544 

545 return n 

546 

547 F = nx.empty_graph(n) 

548 if n == 0: 

549 F.graph["roots"] = {} 

550 return F 

551 # Select the number of roots k 

552 k = _select_k(n, seed) 

553 if k == n: 

554 F.graph["roots"] = set(range(n)) 

555 return F # Nothing to do 

556 # Select the roots 

557 roots = seed.sample(range(n), k) 

558 # Nonroots 

559 p = set(range(n)).difference(roots) 

560 # Coding sequence 

561 N = [seed.randint(0, n - 1) for i in range(n - k - 1)] 

562 # Multiset of elements in N also in p 

563 degree = Counter([x for x in N if x in p]) 

564 # Iterator over the elements of p with degree zero 

565 iterator = iter(x for x in p if degree[x] == 0) 

566 u = last = next(iterator) 

567 # This loop is identical to that for Prüfer sequences, 

568 # except that we can draw nodes only from p 

569 for v in N: 

570 F.add_edge(u, v) 

571 degree[v] -= 1 

572 if v < last and degree[v] == 0: 

573 u = v 

574 else: 

575 last = u = next(iterator) 

576 

577 F.add_edge(u, roots[0]) 

578 F.graph["roots"] = set(roots) 

579 return F 

580 

581 

582# The following functions support generation of unlabeled trees and forests. 

583 

584 

585def _to_nx(edges, n_nodes, root=None, roots=None): 

586 """ 

587 Converts the (edges, n_nodes) input to a :class:`networkx.Graph`. 

588 The (edges, n_nodes) input is a list of even length, where each pair 

589 of consecutive integers represents an edge, and an integer `n_nodes`. 

590 Integers in the list are elements of `range(n_nodes)`. 

591 

592 Parameters 

593 ---------- 

594 edges : list of ints 

595 The flattened list of edges of the graph. 

596 n_nodes : int 

597 The number of nodes of the graph. 

598 root: int (default=None) 

599 If not None, the "root" attribute of the graph will be set to this value. 

600 roots: collection of ints (default=None) 

601 If not None, he "roots" attribute of the graph will be set to this value. 

602 

603 Returns 

604 ------- 

605 :class:`networkx.Graph` 

606 The graph with `n_nodes` nodes and edges given by `edges`. 

607 """ 

608 G = nx.empty_graph(n_nodes) 

609 G.add_edges_from(edges) 

610 if root is not None: 

611 G.graph["root"] = root 

612 if roots is not None: 

613 G.graph["roots"] = roots 

614 return G 

615 

616 

617def _num_rooted_trees(n, cache_trees): 

618 """Returns the number of unlabeled rooted trees with `n` nodes. 

619 

620 See also https://oeis.org/A000081. 

621 

622 Parameters 

623 ---------- 

624 n : int 

625 The number of nodes 

626 cache_trees : list of ints 

627 The $i$-th element is the number of unlabeled rooted trees with $i$ nodes, 

628 which is used as a cache (and is extended to length $n+1$ if needed) 

629 

630 Returns 

631 ------- 

632 int 

633 The number of unlabeled rooted trees with `n` nodes. 

634 """ 

635 for n_i in range(len(cache_trees), n + 1): 

636 cache_trees.append( 

637 sum( 

638 [ 

639 d * cache_trees[n_i - j * d] * cache_trees[d] 

640 for d in range(1, n_i) 

641 for j in range(1, (n_i - 1) // d + 1) 

642 ] 

643 ) 

644 // (n_i - 1) 

645 ) 

646 return cache_trees[n] 

647 

648 

649def _select_jd_trees(n, cache_trees, seed): 

650 """Returns a pair $(j,d)$ with a specific probability 

651 

652 Given $n$, returns a pair of positive integers $(j,d)$ with the probability 

653 specified in formula (5) of Chapter 29 of [1]_. 

654 

655 Parameters 

656 ---------- 

657 n : int 

658 The number of nodes 

659 cache_trees : list of ints 

660 Cache for :func:`_num_rooted_trees`. 

661 seed : random_state 

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

663 

664 Returns 

665 ------- 

666 (int, int) 

667 A pair of positive integers $(j,d)$ satisfying formula (5) of 

668 Chapter 29 of [1]_. 

669 

670 References 

671 ---------- 

672 .. [1] Nijenhuis, Albert, and Wilf, Herbert S. 

673 "Combinatorial algorithms: for computers and calculators." 

674 Academic Press, 1978. 

675 https://doi.org/10.1016/C2013-0-11243-3 

676 """ 

677 p = seed.randint(0, _num_rooted_trees(n, cache_trees) * (n - 1) - 1) 

678 cumsum = 0 

679 for d in range(n - 1, 0, -1): 

680 for j in range(1, (n - 1) // d + 1): 

681 cumsum += ( 

682 d 

683 * _num_rooted_trees(n - j * d, cache_trees) 

684 * _num_rooted_trees(d, cache_trees) 

685 ) 

686 if p < cumsum: 

687 return (j, d) 

688 

689 

690def _random_unlabeled_rooted_tree(n, cache_trees, seed): 

691 """Returns an unlabeled rooted tree with `n` nodes. 

692 

693 Returns an unlabeled rooted tree with `n` nodes chosen uniformly 

694 at random using the "RANRUT" algorithm from [1]_. 

695 The tree is returned in the form: (list_of_edges, number_of_nodes) 

696 

697 Parameters 

698 ---------- 

699 n : int 

700 The number of nodes, greater than zero. 

701 cache_trees : list ints 

702 Cache for :func:`_num_rooted_trees`. 

703 seed : random_state 

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

705 

706 Returns 

707 ------- 

708 (list_of_edges, number_of_nodes) : list, int 

709 A random unlabeled rooted tree with `n` nodes as a 2-tuple 

710 ``(list_of_edges, number_of_nodes)``. 

711 The root is node 0. 

712 

713 References 

714 ---------- 

715 .. [1] Nijenhuis, Albert, and Wilf, Herbert S. 

716 "Combinatorial algorithms: for computers and calculators." 

717 Academic Press, 1978. 

718 https://doi.org/10.1016/C2013-0-11243-3 

719 """ 

720 if n == 1: 

721 edges, n_nodes = [], 1 

722 return edges, n_nodes 

723 if n == 2: 

724 edges, n_nodes = [(0, 1)], 2 

725 return edges, n_nodes 

726 

727 j, d = _select_jd_trees(n, cache_trees, seed) 

728 t1, t1_nodes = _random_unlabeled_rooted_tree(n - j * d, cache_trees, seed) 

729 t2, t2_nodes = _random_unlabeled_rooted_tree(d, cache_trees, seed) 

730 t12 = [(0, t2_nodes * i + t1_nodes) for i in range(j)] 

731 t1.extend(t12) 

732 for _ in range(j): 

733 t1.extend((n1 + t1_nodes, n2 + t1_nodes) for n1, n2 in t2) 

734 t1_nodes += t2_nodes 

735 

736 return t1, t1_nodes 

737 

738 

739@py_random_state("seed") 

740@nx._dispatch(graphs=None) 

741def random_unlabeled_rooted_tree(n, *, number_of_trees=None, seed=None): 

742 """Returns a number of unlabeled rooted trees uniformly at random 

743 

744 Returns one or more (depending on `number_of_trees`) 

745 unlabeled rooted trees with `n` nodes drawn uniformly 

746 at random. 

747 

748 Parameters 

749 ---------- 

750 n : int 

751 The number of nodes 

752 number_of_trees : int or None (default) 

753 If not None, this number of trees is generated and returned. 

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

755 Indicator of random number generation state. 

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

757 

758 Returns 

759 ------- 

760 :class:`networkx.Graph` or list of :class:`networkx.Graph` 

761 A single `networkx.Graph` (or a list thereof, if `number_of_trees` 

762 is specified) with nodes in the set {0, …, *n* - 1}. 

763 The "root" graph attribute identifies the root of the tree. 

764 

765 Notes 

766 ----- 

767 The trees are generated using the "RANRUT" algorithm from [1]_. 

768 The algorithm needs to compute some counting functions 

769 that are relatively expensive: in case several trees are needed, 

770 it is advisable to use the `number_of_trees` optional argument 

771 to reuse the counting functions. 

772 

773 Raises 

774 ------ 

775 NetworkXPointlessConcept 

776 If `n` is zero (because the null graph is not a tree). 

777 

778 References 

779 ---------- 

780 .. [1] Nijenhuis, Albert, and Wilf, Herbert S. 

781 "Combinatorial algorithms: for computers and calculators." 

782 Academic Press, 1978. 

783 https://doi.org/10.1016/C2013-0-11243-3 

784 """ 

785 if n == 0: 

786 raise nx.NetworkXPointlessConcept("the null graph is not a tree") 

787 cache_trees = [0, 1] # initial cache of number of rooted trees 

788 if number_of_trees is None: 

789 return _to_nx(*_random_unlabeled_rooted_tree(n, cache_trees, seed), root=0) 

790 return [ 

791 _to_nx(*_random_unlabeled_rooted_tree(n, cache_trees, seed), root=0) 

792 for i in range(number_of_trees) 

793 ] 

794 

795 

796def _num_rooted_forests(n, q, cache_forests): 

797 """Returns the number of unlabeled rooted forests with `n` nodes, and with 

798 no more than `q` nodes per tree. A recursive formula for this is (2) in 

799 [1]_. This function is implemented using dynamic programming instead of 

800 recursion. 

801 

802 Parameters 

803 ---------- 

804 n : int 

805 The number of nodes. 

806 q : int 

807 The maximum number of nodes for each tree of the forest. 

808 cache_forests : list of ints 

809 The $i$-th element is the number of unlabeled rooted forests with 

810 $i$ nodes, and with no more than `q` nodes per tree; this is used 

811 as a cache (and is extended to length `n` + 1 if needed). 

812 

813 Returns 

814 ------- 

815 int 

816 The number of unlabeled rooted forests with `n` nodes with no more than 

817 `q` nodes per tree. 

818 

819 References 

820 ---------- 

821 .. [1] Wilf, Herbert S. "The uniform selection of free trees." 

822 Journal of Algorithms 2.2 (1981): 204-207. 

823 https://doi.org/10.1016/0196-6774(81)90021-3 

824 """ 

825 for n_i in range(len(cache_forests), n + 1): 

826 q_i = min(n_i, q) 

827 cache_forests.append( 

828 sum( 

829 [ 

830 d * cache_forests[n_i - j * d] * cache_forests[d - 1] 

831 for d in range(1, q_i + 1) 

832 for j in range(1, n_i // d + 1) 

833 ] 

834 ) 

835 // n_i 

836 ) 

837 

838 return cache_forests[n] 

839 

840 

841def _select_jd_forests(n, q, cache_forests, seed): 

842 """Given `n` and `q`, returns a pair of positive integers $(j,d)$ 

843 such that $j\\leq d$, with probability satisfying (F1) of [1]_. 

844 

845 Parameters 

846 ---------- 

847 n : int 

848 The number of nodes. 

849 q : int 

850 The maximum number of nodes for each tree of the forest. 

851 cache_forests : list of ints 

852 Cache for :func:`_num_rooted_forests`. 

853 seed : random_state 

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

855 

856 Returns 

857 ------- 

858 (int, int) 

859 A pair of positive integers $(j,d)$ 

860 

861 References 

862 ---------- 

863 .. [1] Wilf, Herbert S. "The uniform selection of free trees." 

864 Journal of Algorithms 2.2 (1981): 204-207. 

865 https://doi.org/10.1016/0196-6774(81)90021-3 

866 """ 

867 p = seed.randint(0, _num_rooted_forests(n, q, cache_forests) * n - 1) 

868 cumsum = 0 

869 for d in range(q, 0, -1): 

870 for j in range(1, n // d + 1): 

871 cumsum += ( 

872 d 

873 * _num_rooted_forests(n - j * d, q, cache_forests) 

874 * _num_rooted_forests(d - 1, q, cache_forests) 

875 ) 

876 if p < cumsum: 

877 return (j, d) 

878 

879 

880def _random_unlabeled_rooted_forest(n, q, cache_trees, cache_forests, seed): 

881 """Returns an unlabeled rooted forest with `n` nodes, and with no more 

882 than `q` nodes per tree, drawn uniformly at random. It is an implementation 

883 of the algorithm "Forest" of [1]_. 

884 

885 Parameters 

886 ---------- 

887 n : int 

888 The number of nodes. 

889 q : int 

890 The maximum number of nodes per tree. 

891 cache_trees : 

892 Cache for :func:`_num_rooted_trees`. 

893 cache_forests : 

894 Cache for :func:`_num_rooted_forests`. 

895 seed : random_state 

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

897 

898 Returns 

899 ------- 

900 (edges, n, r) : (list, int, list) 

901 The forest (edges, n) and a list r of root nodes. 

902 

903 References 

904 ---------- 

905 .. [1] Wilf, Herbert S. "The uniform selection of free trees." 

906 Journal of Algorithms 2.2 (1981): 204-207. 

907 https://doi.org/10.1016/0196-6774(81)90021-3 

908 """ 

909 if n == 0: 

910 return ([], 0, []) 

911 

912 j, d = _select_jd_forests(n, q, cache_forests, seed) 

913 t1, t1_nodes, r1 = _random_unlabeled_rooted_forest( 

914 n - j * d, q, cache_trees, cache_forests, seed 

915 ) 

916 t2, t2_nodes = _random_unlabeled_rooted_tree(d, cache_trees, seed) 

917 for _ in range(j): 

918 r1.append(t1_nodes) 

919 t1.extend((n1 + t1_nodes, n2 + t1_nodes) for n1, n2 in t2) 

920 t1_nodes += t2_nodes 

921 return t1, t1_nodes, r1 

922 

923 

924@py_random_state("seed") 

925@nx._dispatch(graphs=None) 

926def random_unlabeled_rooted_forest(n, *, q=None, number_of_forests=None, seed=None): 

927 """Returns a forest or list of forests selected at random. 

928 

929 Returns one or more (depending on `number_of_forests`) 

930 unlabeled rooted forests with `n` nodes, and with no more than 

931 `q` nodes per tree, drawn uniformly at random. 

932 The "roots" graph attribute identifies the roots of the forest. 

933 

934 Parameters 

935 ---------- 

936 n : int 

937 The number of nodes 

938 q : int or None (default) 

939 The maximum number of nodes per tree. 

940 number_of_forests : int or None (default) 

941 If not None, this number of forests is generated and returned. 

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

943 Indicator of random number generation state. 

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

945 

946 Returns 

947 ------- 

948 :class:`networkx.Graph` or list of :class:`networkx.Graph` 

949 A single `networkx.Graph` (or a list thereof, if `number_of_forests` 

950 is specified) with nodes in the set {0, …, *n* - 1}. 

951 The "roots" graph attribute is a set containing the roots 

952 of the trees in the forest. 

953 

954 Notes 

955 ----- 

956 This function implements the algorithm "Forest" of [1]_. 

957 The algorithm needs to compute some counting functions 

958 that are relatively expensive: in case several trees are needed, 

959 it is advisable to use the `number_of_forests` optional argument 

960 to reuse the counting functions. 

961 

962 Raises 

963 ------ 

964 ValueError 

965 If `n` is non-zero but `q` is zero. 

966 

967 References 

968 ---------- 

969 .. [1] Wilf, Herbert S. "The uniform selection of free trees." 

970 Journal of Algorithms 2.2 (1981): 204-207. 

971 https://doi.org/10.1016/0196-6774(81)90021-3 

972 """ 

973 if q is None: 

974 q = n 

975 if q == 0 and n != 0: 

976 raise ValueError("q must be a positive integer if n is positive.") 

977 

978 cache_trees = [0, 1] # initial cache of number of rooted trees 

979 cache_forests = [1] # initial cache of number of rooted forests 

980 

981 if number_of_forests is None: 

982 g, nodes, rs = _random_unlabeled_rooted_forest( 

983 n, q, cache_trees, cache_forests, seed 

984 ) 

985 return _to_nx(g, nodes, roots=set(rs)) 

986 

987 res = [] 

988 for i in range(number_of_forests): 

989 g, nodes, rs = _random_unlabeled_rooted_forest( 

990 n, q, cache_trees, cache_forests, seed 

991 ) 

992 res.append(_to_nx(g, nodes, roots=set(rs))) 

993 return res 

994 

995 

996def _num_trees(n, cache_trees): 

997 """Returns the number of unlabeled trees with `n` nodes. 

998 

999 See also https://oeis.org/A000055. 

1000 

1001 Parameters 

1002 ---------- 

1003 n : int 

1004 The number of nodes. 

1005 cache_trees : list of ints 

1006 Cache for :func:`_num_rooted_trees`. 

1007 

1008 Returns 

1009 ------- 

1010 int 

1011 The number of unlabeled trees with `n` nodes. 

1012 """ 

1013 r = _num_rooted_trees(n, cache_trees) - sum( 

1014 [ 

1015 _num_rooted_trees(j, cache_trees) * _num_rooted_trees(n - j, cache_trees) 

1016 for j in range(1, n // 2 + 1) 

1017 ] 

1018 ) 

1019 if n % 2 == 0: 

1020 r += comb(_num_rooted_trees(n // 2, cache_trees) + 1, 2) 

1021 return r 

1022 

1023 

1024def _bicenter(n, cache, seed): 

1025 """Returns a bi-centroidal tree on `n` nodes drawn uniformly at random. 

1026 

1027 This function implements the algorithm Bicenter of [1]_. 

1028 

1029 Parameters 

1030 ---------- 

1031 n : int 

1032 The number of nodes (must be even). 

1033 cache : list of ints. 

1034 Cache for :func:`_num_rooted_trees`. 

1035 seed : random_state 

1036 See :ref:`Randomness<randomness>` 

1037 

1038 Returns 

1039 ------- 

1040 (edges, n) 

1041 The tree as a list of edges and number of nodes. 

1042 

1043 References 

1044 ---------- 

1045 .. [1] Wilf, Herbert S. "The uniform selection of free trees." 

1046 Journal of Algorithms 2.2 (1981): 204-207. 

1047 https://doi.org/10.1016/0196-6774(81)90021-3 

1048 """ 

1049 t, t_nodes = _random_unlabeled_rooted_tree(n // 2, cache, seed) 

1050 if seed.randint(0, _num_rooted_trees(n // 2, cache)) == 0: 

1051 t2, t2_nodes = t, t_nodes 

1052 else: 

1053 t2, t2_nodes = _random_unlabeled_rooted_tree(n // 2, cache, seed)