Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-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 

31from collections import Counter, defaultdict 

32from math import comb, factorial 

33 

34import networkx as nx 

35from networkx.utils import py_random_state 

36 

37__all__ = [ 

38 "prefix_tree", 

39 "prefix_tree_recursive", 

40 "random_labeled_tree", 

41 "random_labeled_rooted_tree", 

42 "random_labeled_rooted_forest", 

43 "random_unlabeled_tree", 

44 "random_unlabeled_rooted_tree", 

45 "random_unlabeled_rooted_forest", 

46] 

47 

48 

49@nx._dispatchable(graphs=None, returns_graph=True) 

50def prefix_tree(paths): 

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

52 

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

54 

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

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

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

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

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

60 

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

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

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

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

65 

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

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

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

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

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

71 

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

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

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

75 accumulating the "source" values along the way. 

76 

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

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

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

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

81 

82 

83 Parameters 

84 ---------- 

85 paths: iterable of paths 

86 An iterable of paths which are themselves sequences. 

87 Matching prefixes among these sequences are identified with 

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

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

90 leaf of the tree.) 

91 

92 

93 Returns 

94 ------- 

95 tree: DiGraph 

96 A directed graph representing an arborescence consisting of the 

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

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

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

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

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

102 addition of this nil node technically makes this not an 

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

104 makes it an arborescence.) 

105 

106 

107 Notes 

108 ----- 

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

110 

111 

112 Examples 

113 -------- 

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

115 

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

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

118 >>> list(T.edges) 

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

120 

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

122 

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

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

125 [2, 3, 4] 

126 

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

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

129 

130 >>> recovered = [] 

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

132 ... prefix = "" 

133 ... while v != root: 

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

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

136 ... recovered.append(prefix) 

137 >>> sorted(recovered) 

138 ['ab', 'abs', 'ad'] 

139 """ 

140 

141 def get_children(parent, paths): 

142 children = defaultdict(list) 

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

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

145 for path in paths: 

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

147 if not path: 

148 tree.add_edge(parent, NIL) 

149 continue 

150 child, *rest = path 

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

152 children[child].append(rest) 

153 return children 

154 

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

156 tree = nx.DiGraph() 

157 root = 0 

158 tree.add_node(root, source=None) 

159 NIL = -1 

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

161 children = get_children(root, paths) 

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

163 while stack: 

164 parent, remaining_children = stack[-1] 

165 try: 

166 child, remaining_paths = next(remaining_children) 

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

168 except StopIteration: 

169 stack.pop() 

170 continue 

171 # We relabel each child with an unused name. 

172 new_name = len(tree) - 1 

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

174 tree.add_node(new_name, source=child) 

175 tree.add_edge(parent, new_name) 

176 children = get_children(new_name, remaining_paths) 

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

178 

179 return tree 

180 

181 

182@nx._dispatchable(graphs=None, returns_graph=True) 

183def prefix_tree_recursive(paths): 

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

185 

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

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

188 

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

190 

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

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

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

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

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

196 

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

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

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

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

201 

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

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

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

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

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

207 

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

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

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

211 accumulating the "source" values along the way. 

212 

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

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

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

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

217 

218 

219 Parameters 

220 ---------- 

221 paths: iterable of paths 

222 An iterable of paths which are themselves sequences. 

223 Matching prefixes among these sequences are identified with 

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

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

226 leaf of the tree.) 

227 

228 

229 Returns 

230 ------- 

231 tree: DiGraph 

232 A directed graph representing an arborescence consisting of the 

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

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

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

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

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

238 addition of this nil node technically makes this not an 

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

240 makes it an arborescence.) 

241 

242 

243 Notes 

244 ----- 

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

246 

247 

248 Examples 

249 -------- 

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

251 

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

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

254 >>> list(T.edges) 

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

256 

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

258 

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

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

261 [2, 3, 4] 

262 

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

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

265 

266 >>> recovered = [] 

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

268 ... prefix = "" 

269 ... while v != root: 

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

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

272 ... recovered.append(prefix) 

273 >>> sorted(recovered) 

274 ['ab', 'abs', 'ad'] 

275 """ 

276 

277 def _helper(paths, root, tree): 

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

279 

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

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

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

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

284 the tree with the same initial segment. 

285 

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

287 

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

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

290 be added. 

291 

292 """ 

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

294 # Any remaining paths then get processed recursively. 

295 children = defaultdict(list) 

296 for path in paths: 

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

298 if not path: 

299 tree.add_edge(root, NIL) 

300 continue 

301 child, *rest = path 

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

303 children[child].append(rest) 

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

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

306 # We relabel each child with an unused name. 

307 new_name = len(tree) - 1 

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

309 tree.add_node(new_name, source=child) 

310 tree.add_edge(root, new_name) 

311 _helper(remaining_paths, new_name, tree) 

312 

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

314 tree = nx.DiGraph() 

315 root = 0 

316 tree.add_node(root, source=None) 

317 NIL = -1 

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

319 # Populate the tree. 

320 _helper(paths, root, tree) 

321 return tree 

322 

323 

324@py_random_state("seed") 

325@nx._dispatchable(graphs=None, returns_graph=True) 

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

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

328 

329 Generating uniformly distributed random Prüfer sequences and 

330 converting them into the corresponding trees is a straightforward 

331 method of generating uniformly distributed random labeled trees. 

332 This function implements this method. 

333 

334 Parameters 

335 ---------- 

336 n : int 

337 The number of nodes, greater than zero. 

338 seed : random_state 

339 Indicator of random number generation state. 

340 See :ref:`Randomness<randomness>` 

341 

342 Returns 

343 ------- 

344 :class:`networkx.Graph` 

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

346 

347 Raises 

348 ------ 

349 NetworkXPointlessConcept 

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

351 

352 Examples 

353 -------- 

354 >>> G = nx.random_labeled_tree(5, seed=42) 

355 >>> nx.is_tree(G) 

356 True 

357 >>> G.edges 

358 EdgeView([(0, 1), (0, 3), (0, 2), (2, 4)]) 

359 

360 A tree with *arbitrarily directed* edges can be created by assigning 

361 generated edges to a ``DiGraph``: 

362 

363 >>> DG = nx.DiGraph() 

364 >>> DG.add_edges_from(G.edges) 

365 >>> nx.is_tree(DG) 

366 True 

367 >>> DG.edges 

368 OutEdgeView([(0, 1), (0, 3), (0, 2), (2, 4)]) 

369 """ 

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

371 if n == 0: 

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

373 if n == 1: 

374 return nx.empty_graph(1) 

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

376 

377 

378@py_random_state("seed") 

379@nx._dispatchable(graphs=None, returns_graph=True) 

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

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

382 

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

384 

385 Parameters 

386 ---------- 

387 n : int 

388 The number of nodes 

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

390 Indicator of random number generation state. 

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

392 

393 Returns 

394 ------- 

395 :class:`networkx.Graph` 

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

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

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

399 

400 Notes 

401 ----- 

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

403 with a randomly selected root. 

404 

405 Raises 

406 ------ 

407 NetworkXPointlessConcept 

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

409 """ 

410 t = random_labeled_tree(n, seed=seed) 

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

412 return t 

413 

414 

415@py_random_state("seed") 

416@nx._dispatchable(graphs=None, returns_graph=True) 

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

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

419 

420 The returned forest is chosen uniformly at random using a 

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

422 

423 Parameters 

424 ---------- 

425 n : int 

426 The number of nodes. 

427 seed : random_state 

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

429 

430 Returns 

431 ------- 

432 :class:`networkx.Graph` 

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

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

435 

436 References 

437 ---------- 

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

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

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

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

442 zur Erlangung des akademischen Grades Magister der 

443 Naturwissenschaften an der Formal- und Naturwissenschaftlichen 

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

445 """ 

446 

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

448 # with at most k roots 

449 def _select_k(n, seed): 

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

451 cum_sum = 0 

452 for k in range(1, n): 

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

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

455 ) 

456 if r < cum_sum: 

457 return k 

458 

459 return n 

460 

461 F = nx.empty_graph(n) 

462 if n == 0: 

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

464 return F 

465 # Select the number of roots k 

466 k = _select_k(n, seed) 

467 if k == n: 

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

469 return F # Nothing to do 

470 # Select the roots 

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

472 # Nonroots 

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

474 # Coding sequence 

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

476 # Multiset of elements in N also in p 

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

478 # Iterator over the elements of p with degree zero 

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

480 u = last = next(iterator) 

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

482 # except that we can draw nodes only from p 

483 for v in N: 

484 F.add_edge(u, v) 

485 degree[v] -= 1 

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

487 u = v 

488 else: 

489 last = u = next(iterator) 

490 

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

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

493 return F 

494 

495 

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

497 

498 

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

500 """ 

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

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

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

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

505 

506 Parameters 

507 ---------- 

508 edges : list of ints 

509 The flattened list of edges of the graph. 

510 n_nodes : int 

511 The number of nodes of the graph. 

512 root: int (default=None) 

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

514 roots: collection of ints (default=None) 

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

516 

517 Returns 

518 ------- 

519 :class:`networkx.Graph` 

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

521 """ 

522 G = nx.empty_graph(n_nodes) 

523 G.add_edges_from(edges) 

524 if root is not None: 

525 G.graph["root"] = root 

526 if roots is not None: 

527 G.graph["roots"] = roots 

528 return G 

529 

530 

531def _num_rooted_trees(n, cache_trees): 

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

533 

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

535 

536 Parameters 

537 ---------- 

538 n : int 

539 The number of nodes 

540 cache_trees : list of ints 

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

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

543 

544 Returns 

545 ------- 

546 int 

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

548 """ 

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

550 cache_trees.append( 

551 sum( 

552 [ 

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

554 for d in range(1, n_i) 

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

556 ] 

557 ) 

558 // (n_i - 1) 

559 ) 

560 return cache_trees[n] 

561 

562 

563def _select_jd_trees(n, cache_trees, seed): 

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

565 

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

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

568 

569 Parameters 

570 ---------- 

571 n : int 

572 The number of nodes 

573 cache_trees : list of ints 

574 Cache for :func:`_num_rooted_trees`. 

575 seed : random_state 

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

577 

578 Returns 

579 ------- 

580 (int, int) 

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

582 Chapter 29 of [1]_. 

583 

584 References 

585 ---------- 

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

587 "Combinatorial algorithms: for computers and calculators." 

588 Academic Press, 1978. 

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

590 """ 

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

592 cumsum = 0 

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

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

595 cumsum += ( 

596 d 

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

598 * _num_rooted_trees(d, cache_trees) 

599 ) 

600 if p < cumsum: 

601 return (j, d) 

602 

603 

604def _random_unlabeled_rooted_tree(n, cache_trees, seed): 

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

606 

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

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

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

610 

611 Parameters 

612 ---------- 

613 n : int 

614 The number of nodes, greater than zero. 

615 cache_trees : list ints 

616 Cache for :func:`_num_rooted_trees`. 

617 seed : random_state 

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

619 

620 Returns 

621 ------- 

622 (list_of_edges, number_of_nodes) : list, int 

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

624 ``(list_of_edges, number_of_nodes)``. 

625 The root is node 0. 

626 

627 References 

628 ---------- 

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

630 "Combinatorial algorithms: for computers and calculators." 

631 Academic Press, 1978. 

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

633 """ 

634 if n == 1: 

635 edges, n_nodes = [], 1 

636 return edges, n_nodes 

637 if n == 2: 

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

639 return edges, n_nodes 

640 

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

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

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

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

645 t1.extend(t12) 

646 for _ in range(j): 

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

648 t1_nodes += t2_nodes 

649 

650 return t1, t1_nodes 

651 

652 

653@py_random_state("seed") 

654@nx._dispatchable(graphs=None, returns_graph=True) 

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

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

657 

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

659 unlabeled rooted trees with `n` nodes drawn uniformly 

660 at random. 

661 

662 Parameters 

663 ---------- 

664 n : int 

665 The number of nodes 

666 number_of_trees : int or None (default) 

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

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

669 Indicator of random number generation state. 

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

671 

672 Returns 

673 ------- 

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

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

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

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

678 

679 Notes 

680 ----- 

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

682 The algorithm needs to compute some counting functions 

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

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

685 to reuse the counting functions. 

686 

687 Raises 

688 ------ 

689 NetworkXPointlessConcept 

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

691 

692 References 

693 ---------- 

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

695 "Combinatorial algorithms: for computers and calculators." 

696 Academic Press, 1978. 

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

698 """ 

699 if n == 0: 

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

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

702 if number_of_trees is None: 

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

704 return [ 

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

706 for i in range(number_of_trees) 

707 ] 

708 

709 

710def _num_rooted_forests(n, q, cache_forests): 

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

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

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

714 recursion. 

715 

716 Parameters 

717 ---------- 

718 n : int 

719 The number of nodes. 

720 q : int 

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

722 cache_forests : list of ints 

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

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

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

726 

727 Returns 

728 ------- 

729 int 

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

731 `q` nodes per tree. 

732 

733 References 

734 ---------- 

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

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

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

738 """ 

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

740 q_i = min(n_i, q) 

741 cache_forests.append( 

742 sum( 

743 [ 

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

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

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

747 ] 

748 ) 

749 // n_i 

750 ) 

751 

752 return cache_forests[n] 

753 

754 

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

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

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

758 

759 Parameters 

760 ---------- 

761 n : int 

762 The number of nodes. 

763 q : int 

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

765 cache_forests : list of ints 

766 Cache for :func:`_num_rooted_forests`. 

767 seed : random_state 

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

769 

770 Returns 

771 ------- 

772 (int, int) 

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

774 

775 References 

776 ---------- 

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

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

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

780 """ 

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

782 cumsum = 0 

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

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

785 cumsum += ( 

786 d 

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

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

789 ) 

790 if p < cumsum: 

791 return (j, d) 

792 

793 

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

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

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

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

798 

799 Parameters 

800 ---------- 

801 n : int 

802 The number of nodes. 

803 q : int 

804 The maximum number of nodes per tree. 

805 cache_trees : 

806 Cache for :func:`_num_rooted_trees`. 

807 cache_forests : 

808 Cache for :func:`_num_rooted_forests`. 

809 seed : random_state 

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

811 

812 Returns 

813 ------- 

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

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

816 

817 References 

818 ---------- 

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

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

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

822 """ 

823 if n == 0: 

824 return ([], 0, []) 

825 

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

827 t1, t1_nodes, r1 = _random_unlabeled_rooted_forest( 

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

829 ) 

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

831 for _ in range(j): 

832 r1.append(t1_nodes) 

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

834 t1_nodes += t2_nodes 

835 return t1, t1_nodes, r1 

836 

837 

838@py_random_state("seed") 

839@nx._dispatchable(graphs=None, returns_graph=True) 

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

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

842 

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

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

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

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

847 

848 Parameters 

849 ---------- 

850 n : int 

851 The number of nodes 

852 q : int or None (default) 

853 The maximum number of nodes per tree. 

854 number_of_forests : int or None (default) 

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

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

857 Indicator of random number generation state. 

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

859 

860 Returns 

861 ------- 

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

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

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

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

866 of the trees in the forest. 

867 

868 Notes 

869 ----- 

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

871 The algorithm needs to compute some counting functions 

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

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

874 to reuse the counting functions. 

875 

876 Raises 

877 ------ 

878 ValueError 

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

880 

881 References 

882 ---------- 

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

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

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

886 """ 

887 if q is None: 

888 q = n 

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

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

891 

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

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

894 

895 if number_of_forests is None: 

896 g, nodes, rs = _random_unlabeled_rooted_forest( 

897 n, q, cache_trees, cache_forests, seed 

898 ) 

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

900 

901 res = [] 

902 for i in range(number_of_forests): 

903 g, nodes, rs = _random_unlabeled_rooted_forest( 

904 n, q, cache_trees, cache_forests, seed 

905 ) 

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

907 return res 

908 

909 

910def _num_trees(n, cache_trees): 

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

912 

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

914 

915 Parameters 

916 ---------- 

917 n : int 

918 The number of nodes. 

919 cache_trees : list of ints 

920 Cache for :func:`_num_rooted_trees`. 

921 

922 Returns 

923 ------- 

924 int 

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

926 """ 

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

928 [ 

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

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

931 ] 

932 ) 

933 if n % 2 == 0: 

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

935 return r 

936 

937 

938def _bicenter(n, cache, seed): 

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

940 

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

942 

943 Parameters 

944 ---------- 

945 n : int 

946 The number of nodes (must be even). 

947 cache : list of ints. 

948 Cache for :func:`_num_rooted_trees`. 

949 seed : random_state 

950 See :ref:`Randomness<randomness>` 

951 

952 Returns 

953 ------- 

954 (edges, n) 

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

956 

957 References 

958 ---------- 

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

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

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

962 """ 

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

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

965 t2, t2_nodes = t, t_nodes 

966 else: 

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

968 t.extend([(n1 + (n // 2), n2 + (n // 2)) for n1, n2 in t2]) 

969 t.append((0, n // 2)) 

970 return t, t_nodes + t2_nodes 

971 

972 

973def _random_unlabeled_tree(n, cache_trees, cache_forests, seed): 

974 """Returns a tree on `n` nodes drawn uniformly at random. 

975 It implements the Wilf's algorithm "Free" of [1]_. 

976 

977 Parameters 

978 ---------- 

979 n : int 

980 The number of nodes, greater than zero. 

981 cache_trees : list of ints 

982 Cache for :func:`_num_rooted_trees`. 

983 cache_forests : list of ints 

984 Cache for :func:`_num_rooted_forests`. 

985 seed : random_state 

986 Indicator of random number generation state. 

987 See :ref:`Randomness<randomness>` 

988 

989 Returns 

990 ------- 

991 (edges, n) 

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

993 

994 References 

995 ---------- 

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

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

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

999 """ 

1000 if n % 2 == 1: 

1001 p = 0 

1002 else: 

1003 p = comb(_num_rooted_trees(n // 2, cache_trees) + 1, 2) 

1004 if seed.randint(0, _num_trees(n, cache_trees) - 1) < p: 

1005 return _bicenter(n, cache_trees, seed) 

1006 else: 

1007 f, n_f, r = _random_unlabeled_rooted_forest( 

1008 n - 1, (n - 1) // 2, cache_trees, cache_forests, seed 

1009 ) 

1010 for i in r: 

1011 f.append((i, n_f)) 

1012 return f, n_f + 1 

1013 

1014 

1015@py_random_state("seed") 

1016@nx._dispatchable(graphs=None, returns_graph=True) 

1017def random_unlabeled_tree(n, *, number_of_trees=None, seed=None): 

1018 """Returns a tree or list of trees chosen randomly. 

1019 

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

1021 unlabeled trees with `n` nodes drawn uniformly at random. 

1022 

1023 Parameters 

1024 ---------- 

1025 n : int 

1026 The number of nodes 

1027 number_of_trees : int or None (default) 

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

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

1030 Indicator of random number generation state. 

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

1032 

1033 Returns 

1034 ------- 

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

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

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

1038 

1039 Raises 

1040 ------ 

1041 NetworkXPointlessConcept