Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/dag.py: 21%

1"""Algorithms for directed acyclic graphs (DAGs). 

2 

3Note that most of these functions are only guaranteed to work for DAGs. 

4In general, these functions do not check for acyclic-ness, so it is up 

5to the user to check for that. 

6""" 

7 

8import heapq 

9from collections import deque 

10from functools import partial 

11from itertools import chain, combinations, product, starmap 

12from math import gcd 

13 

14import networkx as nx 

15from networkx.utils import arbitrary_element, not_implemented_for, pairwise 

16 

17__all__ = [ 

18 "descendants", 

19 "ancestors", 

20 "topological_sort", 

21 "lexicographical_topological_sort", 

22 "all_topological_sorts", 

23 "topological_generations", 

24 "is_directed_acyclic_graph", 

25 "is_aperiodic", 

26 "transitive_closure", 

27 "transitive_closure_dag", 

28 "transitive_reduction", 

29 "antichains", 

30 "dag_longest_path", 

31 "dag_longest_path_length", 

32 "dag_to_branching", 

33 "compute_v_structures", 

34] 

35 

36chaini = chain.from_iterable 

37 

38 

39@nx._dispatch 

40def descendants(G, source): 

41 """Returns all nodes reachable from `source` in `G`. 

42 

43 Parameters 

44 ---------- 

45 G : NetworkX Graph 

46 source : node in `G` 

47 

48 Returns 

49 ------- 

50 set() 

51 The descendants of `source` in `G` 

52 

53 Raises 

54 ------ 

55 NetworkXError 

56 If node `source` is not in `G`. 

57 

58 Examples 

59 -------- 

60 >>> DG = nx.path_graph(5, create_using=nx.DiGraph) 

61 >>> sorted(nx.descendants(DG, 2)) 

62 [3, 4] 

63 

64 The `source` node is not a descendant of itself, but can be included manually: 

65 

66 >>> sorted(nx.descendants(DG, 2) | {2}) 

67 [2, 3, 4] 

68 

69 See also 

70 -------- 

71 ancestors 

72 """ 

73 return {child for parent, child in nx.bfs_edges(G, source)} 

74 

75 

76@nx._dispatch 

77def ancestors(G, source): 

78 """Returns all nodes having a path to `source` in `G`. 

79 

80 Parameters 

81 ---------- 

82 G : NetworkX Graph 

83 source : node in `G` 

84 

85 Returns 

86 ------- 

87 set() 

88 The ancestors of `source` in `G` 

89 

90 Raises 

91 ------ 

92 NetworkXError 

93 If node `source` is not in `G`. 

94 

95 Examples 

96 -------- 

97 >>> DG = nx.path_graph(5, create_using=nx.DiGraph) 

98 >>> sorted(nx.ancestors(DG, 2)) 

99 [0, 1] 

100 

101 The `source` node is not an ancestor of itself, but can be included manually: 

102 

103 >>> sorted(nx.ancestors(DG, 2) | {2}) 

104 [0, 1, 2] 

105 

106 See also 

107 -------- 

108 descendants 

109 """ 

110 return {child for parent, child in nx.bfs_edges(G, source, reverse=True)} 

111 

112 

113@nx._dispatch 

114def has_cycle(G): 

115 """Decides whether the directed graph has a cycle.""" 

116 try: 

117 # Feed the entire iterator into a zero-length deque. 

118 deque(topological_sort(G), maxlen=0) 

119 except nx.NetworkXUnfeasible: 

120 return True 

121 else: 

122 return False 

123 

124 

125@nx._dispatch 

126def is_directed_acyclic_graph(G): 

127 """Returns True if the graph `G` is a directed acyclic graph (DAG) or 

128 False if not. 

129 

130 Parameters 

131 ---------- 

132 G : NetworkX graph 

133 

134 Returns 

135 ------- 

136 bool 

137 True if `G` is a DAG, False otherwise 

138 

139 Examples 

140 -------- 

141 Undirected graph:: 

142 

143 >>> G = nx.Graph([(1, 2), (2, 3)]) 

144 >>> nx.is_directed_acyclic_graph(G) 

145 False 

146 

147 Directed graph with cycle:: 

148 

149 >>> G = nx.DiGraph([(1, 2), (2, 3), (3, 1)]) 

150 >>> nx.is_directed_acyclic_graph(G) 

151 False 

152 

153 Directed acyclic graph:: 

154 

155 >>> G = nx.DiGraph([(1, 2), (2, 3)]) 

156 >>> nx.is_directed_acyclic_graph(G) 

157 True 

158 

159 See also 

160 -------- 

161 topological_sort 

162 """ 

163 return G.is_directed() and not has_cycle(G) 

164 

165 

166@nx._dispatch 

167def topological_generations(G): 

168 """Stratifies a DAG into generations. 

169 

170 A topological generation is node collection in which ancestors of a node in each 

171 generation are guaranteed to be in a previous generation, and any descendants of 

172 a node are guaranteed to be in a following generation. Nodes are guaranteed to 

173 be in the earliest possible generation that they can belong to. 

174 

175 Parameters 

176 ---------- 

177 G : NetworkX digraph 

178 A directed acyclic graph (DAG) 

179 

180 Yields 

181 ------ 

182 sets of nodes 

183 Yields sets of nodes representing each generation. 

184 

185 Raises 

186 ------ 

187 NetworkXError 

188 Generations are defined for directed graphs only. If the graph 

189 `G` is undirected, a :exc:`NetworkXError` is raised. 

190 

191 NetworkXUnfeasible 

192 If `G` is not a directed acyclic graph (DAG) no topological generations 

193 exist and a :exc:`NetworkXUnfeasible` exception is raised. This can also 

194 be raised if `G` is changed while the returned iterator is being processed 

195 

196 RuntimeError 

197 If `G` is changed while the returned iterator is being processed. 

198 

199 Examples 

200 -------- 

201 >>> DG = nx.DiGraph([(2, 1), (3, 1)]) 

202 >>> [sorted(generation) for generation in nx.topological_generations(DG)] 

203 [[2, 3], [1]] 

204 

205 Notes 

206 ----- 

207 The generation in which a node resides can also be determined by taking the 

208 max-path-distance from the node to the farthest leaf node. That value can 

209 be obtained with this function using `enumerate(topological_generations(G))`. 

210 

211 See also 

212 -------- 

213 topological_sort 

214 """ 

215 if not G.is_directed(): 

216 raise nx.NetworkXError("Topological sort not defined on undirected graphs.") 

217 

218 multigraph = G.is_multigraph() 

219 indegree_map = {v: d for v, d in G.in_degree() if d > 0} 

220 zero_indegree = [v for v, d in G.in_degree() if d == 0] 

221 

222 while zero_indegree: 

223 this_generation = zero_indegree 

224 zero_indegree = [] 

225 for node in this_generation: 

226 if node not in G: 

227 raise RuntimeError("Graph changed during iteration") 

228 for child in G.neighbors(node): 

229 try: 

230 indegree_map[child] -= len(G[node][child]) if multigraph else 1 

231 except KeyError as err: 

232 raise RuntimeError("Graph changed during iteration") from err 

233 if indegree_map[child] == 0: 

234 zero_indegree.append(child) 

235 del indegree_map[child] 

236 yield this_generation 

237 

238 if indegree_map: 

239 raise nx.NetworkXUnfeasible( 

240 "Graph contains a cycle or graph changed during iteration" 

241 ) 

242 

243 

244@nx._dispatch 

245def topological_sort(G): 

246 """Returns a generator of nodes in topologically sorted order. 

247 

248 A topological sort is a nonunique permutation of the nodes of a 

249 directed graph such that an edge from u to v implies that u 

250 appears before v in the topological sort order. This ordering is 

251 valid only if the graph has no directed cycles. 

252 

253 Parameters 

254 ---------- 

255 G : NetworkX digraph 

256 A directed acyclic graph (DAG) 

257 

258 Yields 

259 ------ 

260 nodes 

261 Yields the nodes in topological sorted order. 

262 

263 Raises 

264 ------ 

265 NetworkXError 

266 Topological sort is defined for directed graphs only. If the graph `G` 

267 is undirected, a :exc:`NetworkXError` is raised. 

268 

269 NetworkXUnfeasible 

270 If `G` is not a directed acyclic graph (DAG) no topological sort exists 

271 and a :exc:`NetworkXUnfeasible` exception is raised. This can also be 

272 raised if `G` is changed while the returned iterator is being processed 

273 

274 RuntimeError 

275 If `G` is changed while the returned iterator is being processed. 

276 

277 Examples 

278 -------- 

279 To get the reverse order of the topological sort: 

280 

281 >>> DG = nx.DiGraph([(1, 2), (2, 3)]) 

282 >>> list(reversed(list(nx.topological_sort(DG)))) 

283 [3, 2, 1] 

284 

285 If your DiGraph naturally has the edges representing tasks/inputs 

286 and nodes representing people/processes that initiate tasks, then 

287 topological_sort is not quite what you need. You will have to change 

288 the tasks to nodes with dependence reflected by edges. The result is 

289 a kind of topological sort of the edges. This can be done 

290 with :func:`networkx.line_graph` as follows: 

291 

292 >>> list(nx.topological_sort(nx.line_graph(DG))) 

293 [(1, 2), (2, 3)] 

294 

295 Notes 

296 ----- 

297 This algorithm is based on a description and proof in 

298 "Introduction to Algorithms: A Creative Approach" [1]_ . 

299 

300 See also 

301 -------- 

302 is_directed_acyclic_graph, lexicographical_topological_sort 

303 

304 References 

305 ---------- 

306 .. [1] Manber, U. (1989). 

307 *Introduction to Algorithms - A Creative Approach.* Addison-Wesley. 

308 """ 

309 for generation in nx.topological_generations(G): 

310 yield from generation 

311 

312 

313@nx._dispatch 

314def lexicographical_topological_sort(G, key=None): 

315 """Generate the nodes in the unique lexicographical topological sort order. 

316 

317 Generates a unique ordering of nodes by first sorting topologically (for which there are often 

318 multiple valid orderings) and then additionally by sorting lexicographically. 

319 

320 A topological sort arranges the nodes of a directed graph so that the 

321 upstream node of each directed edge precedes the downstream node. 

322 It is always possible to find a solution for directed graphs that have no cycles. 

323 There may be more than one valid solution. 

324 

325 Lexicographical sorting is just sorting alphabetically. It is used here to break ties in the 

326 topological sort and to determine a single, unique ordering. This can be useful in comparing 

327 sort results. 

328 

329 The lexicographical order can be customized by providing a function to the `key=` parameter. 

330 The definition of the key function is the same as used in python's built-in `sort()`. 

331 The function takes a single argument and returns a key to use for sorting purposes. 

332 

333 Lexicographical sorting can fail if the node names are un-sortable. See the example below. 

334 The solution is to provide a function to the `key=` argument that returns sortable keys. 

335 

336 

337 Parameters 

338 ---------- 

339 G : NetworkX digraph 

340 A directed acyclic graph (DAG) 

341 

342 key : function, optional 

343 A function of one argument that converts a node name to a comparison key. 

344 It defines and resolves ambiguities in the sort order. Defaults to the identity function. 

345 

346 Yields 

347 ------ 

348 nodes 

349 Yields the nodes of G in lexicographical topological sort order. 

350 

351 Raises 

352 ------ 

353 NetworkXError 

354 Topological sort is defined for directed graphs only. If the graph `G` 

355 is undirected, a :exc:`NetworkXError` is raised. 

356 

357 NetworkXUnfeasible 

358 If `G` is not a directed acyclic graph (DAG) no topological sort exists 

359 and a :exc:`NetworkXUnfeasible` exception is raised. This can also be 

360 raised if `G` is changed while the returned iterator is being processed 

361 

362 RuntimeError 

363 If `G` is changed while the returned iterator is being processed. 

364 

365 TypeError 

366 Results from un-sortable node names. 

367 Consider using `key=` parameter to resolve ambiguities in the sort order. 

368 

369 Examples 

370 -------- 

371 >>> DG = nx.DiGraph([(2, 1), (2, 5), (1, 3), (1, 4), (5, 4)]) 

372 >>> list(nx.lexicographical_topological_sort(DG)) 

373 [2, 1, 3, 5, 4] 

374 >>> list(nx.lexicographical_topological_sort(DG, key=lambda x: -x)) 

375 [2, 5, 1, 4, 3] 

376 

377 The sort will fail for any graph with integer and string nodes. Comparison of integer to strings 

378 is not defined in python. Is 3 greater or less than 'red'? 

379 

380 >>> DG = nx.DiGraph([(1, 'red'), (3, 'red'), (1, 'green'), (2, 'blue')]) 

381 >>> list(nx.lexicographical_topological_sort(DG)) 

382 Traceback (most recent call last): 

383 ... 

384 TypeError: '<' not supported between instances of 'str' and 'int' 

385 ... 

386 

387 Incomparable nodes can be resolved using a `key` function. This example function 

388 allows comparison of integers and strings by returning a tuple where the first 

389 element is True for `str`, False otherwise. The second element is the node name. 

390 This groups the strings and integers separately so they can be compared only among themselves. 

391 

392 >>> key = lambda node: (isinstance(node, str), node) 

393 >>> list(nx.lexicographical_topological_sort(DG, key=key)) 

394 [1, 2, 3, 'blue', 'green', 'red'] 

395 

396 Notes 

397 ----- 

398 This algorithm is based on a description and proof in 

399 "Introduction to Algorithms: A Creative Approach" [1]_ . 

400 

401 See also 

402 -------- 

403 topological_sort 

404 

405 References 

406 ---------- 

407 .. [1] Manber, U. (1989). 

408 *Introduction to Algorithms - A Creative Approach.* Addison-Wesley. 

409 """ 

410 if not G.is_directed(): 

411 msg = "Topological sort not defined on undirected graphs." 

412 raise nx.NetworkXError(msg) 

413 

414 if key is None: 

415 

416 def key(node): 

417 return node 

418 

419 nodeid_map = {n: i for i, n in enumerate(G)} 

420 

421 def create_tuple(node): 

422 return key(node), nodeid_map[node], node 

423 

424 indegree_map = {v: d for v, d in G.in_degree() if d > 0} 

425 # These nodes have zero indegree and ready to be returned. 

426 zero_indegree = [create_tuple(v) for v, d in G.in_degree() if d == 0] 

427 heapq.heapify(zero_indegree) 

428 

429 while zero_indegree: 

430 _, _, node = heapq.heappop(zero_indegree) 

431 

432 if node not in G: 

433 raise RuntimeError("Graph changed during iteration") 

434 for _, child in G.edges(node): 

435 try: 

436 indegree_map[child] -= 1 

437 except KeyError as err: 

438 raise RuntimeError("Graph changed during iteration") from err 

439 if indegree_map[child] == 0: 

440 try: 

441 heapq.heappush(zero_indegree, create_tuple(child)) 

442 except TypeError as err: 

443 raise TypeError( 

444 f"{err}\nConsider using `key=` parameter to resolve ambiguities in the sort order." 

445 ) 

446 del indegree_map[child] 

447 

448 yield node 

449 

450 if indegree_map: 

451 msg = "Graph contains a cycle or graph changed during iteration" 

452 raise nx.NetworkXUnfeasible(msg) 

453 

454 

455@not_implemented_for("undirected") 

456@nx._dispatch 

457def all_topological_sorts(G): 

458 """Returns a generator of _all_ topological sorts of the directed graph G. 

459 

460 A topological sort is a nonunique permutation of the nodes such that an 

461 edge from u to v implies that u appears before v in the topological sort 

462 order. 

463 

464 Parameters 

465 ---------- 

466 G : NetworkX DiGraph 

467 A directed graph 

468 

469 Yields 

470 ------ 

471 topological_sort_order : list 

472 a list of nodes in `G`, representing one of the topological sort orders 

473 

474 Raises 

475 ------ 

476 NetworkXNotImplemented 

477 If `G` is not directed 

478 NetworkXUnfeasible 

479 If `G` is not acyclic 

480 

481 Examples 

482 -------- 

483 To enumerate all topological sorts of directed graph: 

484 

485 >>> DG = nx.DiGraph([(1, 2), (2, 3), (2, 4)]) 

486 >>> list(nx.all_topological_sorts(DG)) 

487 [[1, 2, 4, 3], [1, 2, 3, 4]] 

488 

489 Notes 

490 ----- 

491 Implements an iterative version of the algorithm given in [1]. 

492 

493 References 

494 ---------- 

495 .. [1] Knuth, Donald E., Szwarcfiter, Jayme L. (1974). 

496 "A Structured Program to Generate All Topological Sorting Arrangements" 

497 Information Processing Letters, Volume 2, Issue 6, 1974, Pages 153-157, 

498 ISSN 0020-0190, 

499 https://doi.org/10.1016/0020-0190(74)90001-5. 

500 Elsevier (North-Holland), Amsterdam 

501 """ 

502 if not G.is_directed(): 

503 raise nx.NetworkXError("Topological sort not defined on undirected graphs.") 

504 

505 # the names of count and D are chosen to match the global variables in [1] 

506 # number of edges originating in a vertex v 

507 count = dict(G.in_degree()) 

508 # vertices with indegree 0 

509 D = deque([v for v, d in G.in_degree() if d == 0]) 

510 # stack of first value chosen at a position k in the topological sort 

511 bases = [] 

512 current_sort = [] 

513 

514 # do-while construct 

515 while True: 

516 assert all(count[v] == 0 for v in D) 

517 

518 if len(current_sort) == len(G): 

519 yield list(current_sort) 

520 

521 # clean-up stack 

522 while len(current_sort) > 0: 

523 assert len(bases) == len(current_sort) 

524 q = current_sort.pop() 

525 

526 # "restores" all edges (q, x) 

527 # NOTE: it is important to iterate over edges instead 

528 # of successors, so count is updated correctly in multigraphs 

529 for _, j in G.out_edges(q): 

530 count[j] += 1 

531 assert count[j] >= 0 

532 # remove entries from D 

533 while len(D) > 0 and count[D[-1]] > 0: 

534 D.pop() 

535 

536 # corresponds to a circular shift of the values in D 

537 # if the first value chosen (the base) is in the first 

538 # position of D again, we are done and need to consider the 

539 # previous condition 

540 D.appendleft(q) 

541 if D[-1] == bases[-1]: 

542 # all possible values have been chosen at current position 

543 # remove corresponding marker 

544 bases.pop() 

545 else: 

546 # there are still elements that have not been fixed 

547 # at the current position in the topological sort 

548 # stop removing elements, escape inner loop 

549 break 

550 

551 else: 

552 if len(D) == 0: 

553 raise nx.NetworkXUnfeasible("Graph contains a cycle.") 

554 

555 # choose next node 

556 q = D.pop() 

557 # "erase" all edges (q, x) 

558 # NOTE: it is important to iterate over edges instead 

559 # of successors, so count is updated correctly in multigraphs 

560 for _, j in G.out_edges(q): 

561 count[j] -= 1 

562 assert count[j] >= 0 

563 if count[j] == 0: 

564 D.append(j) 

565 current_sort.append(q) 

566 

567 # base for current position might _not_ be fixed yet 

568 if len(bases) < len(current_sort): 

569 bases.append(q) 

570 

571 if len(bases) == 0: 

572 break 

573 

574 

575@nx._dispatch 

576def is_aperiodic(G): 

577 """Returns True if `G` is aperiodic. 

578 

579 A directed graph is aperiodic if there is no integer k > 1 that 

580 divides the length of every cycle in the graph. 

581 

582 Parameters 

583 ---------- 

584 G : NetworkX DiGraph 

585 A directed graph 

586 

587 Returns 

588 ------- 

589 bool 

590 True if the graph is aperiodic False otherwise 

591 

592 Raises 

593 ------ 

594 NetworkXError 

595 If `G` is not directed 

596 

597 Examples 

598 -------- 

599 A graph consisting of one cycle, the length of which is 2. Therefore ``k = 2`` 

600 divides the length of every cycle in the graph and thus the graph 

601 is *not aperiodic*:: 

602 

603 >>> DG = nx.DiGraph([(1, 2), (2, 1)]) 

604 >>> nx.is_aperiodic(DG) 

605 False 

606 

607 A graph consisting of two cycles: one of length 2 and the other of length 3. 

608 The cycle lengths are coprime, so there is no single value of k where ``k > 1`` 

609 that divides each cycle length and therefore the graph is *aperiodic*:: 

610 

611 >>> DG = nx.DiGraph([(1, 2), (2, 3), (3, 1), (1, 4), (4, 1)]) 

612 >>> nx.is_aperiodic(DG) 

613 True 

614 

615 A graph consisting of two cycles: one of length 2 and the other of length 4. 

616 The lengths of the cycles share a common factor ``k = 2``, and therefore 

617 the graph is *not aperiodic*:: 

618 

619 >>> DG = nx.DiGraph([(1, 2), (2, 1), (3, 4), (4, 5), (5, 6), (6, 3)]) 

620 >>> nx.is_aperiodic(DG) 

621 False 

622 

623 An acyclic graph, therefore the graph is *not aperiodic*:: 

624 

625 >>> DG = nx.DiGraph([(1, 2), (2, 3)]) 

626 >>> nx.is_aperiodic(DG) 

627 False 

628 

629 Notes 

630 ----- 

631 This uses the method outlined in [1]_, which runs in $O(m)$ time 

632 given $m$ edges in `G`. Note that a graph is not aperiodic if it is 

633 acyclic as every integer trivial divides length 0 cycles. 

634 

635 References 

636 ---------- 

637 .. [1] Jarvis, J. P.; Shier, D. R. (1996), 

638 "Graph-theoretic analysis of finite Markov chains," 

639 in Shier, D. R.; Wallenius, K. T., Applied Mathematical Modeling: 

640 A Multidisciplinary Approach, CRC Press. 

641 """ 

642 if not G.is_directed(): 

643 raise nx.NetworkXError("is_aperiodic not defined for undirected graphs") 

644 

645 s = arbitrary_element(G) 

646 levels = {s: 0} 

647 this_level = [s] 

648 g = 0 

649 lev = 1 

650 while this_level: 

651 next_level = [] 

652 for u in this_level: 

653 for v in G[u]: 

654 if v in levels: # Non-Tree Edge 

655 g = gcd(g, levels[u] - levels[v] + 1) 

656 else: # Tree Edge 

657 next_level.append(v) 

658 levels[v] = lev 

659 this_level = next_level 

660 lev += 1 

661 if len(levels) == len(G): # All nodes in tree 

662 return g == 1 

663 else: 

664 return g == 1 and nx.is_aperiodic(G.subgraph(set(G) - set(levels))) 

665 

666 

667@nx._dispatch(preserve_all_attrs=True) 

668def transitive_closure(G, reflexive=False): 

669 """Returns transitive closure of a graph 

670 

671 The transitive closure of G = (V,E) is a graph G+ = (V,E+) such that 

672 for all v, w in V there is an edge (v, w) in E+ if and only if there 

673 is a path from v to w in G. 

674 

675 Handling of paths from v to v has some flexibility within this definition. 

676 A reflexive transitive closure creates a self-loop for the path 

677 from v to v of length 0. The usual transitive closure creates a 

678 self-loop only if a cycle exists (a path from v to v with length > 0). 

679 We also allow an option for no self-loops. 

680 

681 Parameters 

682 ---------- 

683 G : NetworkX Graph 

684 A directed/undirected graph/multigraph. 

685 reflexive : Bool or None, optional (default: False) 

686 Determines when cycles create self-loops in the Transitive Closure. 

687 If True, trivial cycles (length 0) create self-loops. The result 

688 is a reflexive transitive closure of G. 

689 If False (the default) non-trivial cycles create self-loops. 

690 If None, self-loops are not created. 

691 

692 Returns 

693 ------- 

694 NetworkX graph 

695 The transitive closure of `G` 

696 

697 Raises 

698 ------ 

699 NetworkXError 

700 If `reflexive` not in `{None, True, False}` 

701 

702 Examples 

703 -------- 

704 The treatment of trivial (i.e. length 0) cycles is controlled by the 

705 `reflexive` parameter. 

706 

707 Trivial (i.e. length 0) cycles do not create self-loops when 

708 ``reflexive=False`` (the default):: 

709 

710 >>> DG = nx.DiGraph([(1, 2), (2, 3)]) 

711 >>> TC = nx.transitive_closure(DG, reflexive=False) 

712 >>> TC.edges() 

713 OutEdgeView([(1, 2), (1, 3), (2, 3)]) 

714 

715 However, nontrivial (i.e. length greater than 0) cycles create self-loops 

716 when ``reflexive=False`` (the default):: 

717 

718 >>> DG = nx.DiGraph([(1, 2), (2, 3), (3, 1)]) 

719 >>> TC = nx.transitive_closure(DG, reflexive=False) 

720 >>> TC.edges() 

721 OutEdgeView([(1, 2), (1, 3), (1, 1), (2, 3), (2, 1), (2, 2), (3, 1), (3, 2), (3, 3)]) 

722 

723 Trivial cycles (length 0) create self-loops when ``reflexive=True``:: 

724 

725 >>> DG = nx.DiGraph([(1, 2), (2, 3)]) 

726 >>> TC = nx.transitive_closure(DG, reflexive=True) 

727 >>> TC.edges() 

728 OutEdgeView([(1, 2), (1, 1), (1, 3), (2, 3), (2, 2), (3, 3)]) 

729 

730 And the third option is not to create self-loops at all when ``reflexive=None``:: 

731 

732 >>> DG = nx.DiGraph([(1, 2), (2, 3), (3, 1)]) 

733 >>> TC = nx.transitive_closure(DG, reflexive=None) 

734 >>> TC.edges() 

735 OutEdgeView([(1, 2), (1, 3), (2, 3), (2, 1), (3, 1), (3, 2)]) 

736 

737 References 

738 ---------- 

739 .. [1] https://www.ics.uci.edu/~eppstein/PADS/PartialOrder.py 

740 """ 

741 TC = G.copy() 

742 

743 if reflexive not in {None, True, False}: 

744 raise nx.NetworkXError("Incorrect value for the parameter `reflexive`") 

745 

746 for v in G: 

747 if reflexive is None: 

748 TC.add_edges_from((v, u) for u in nx.descendants(G, v) if u not in TC[v]) 

749 elif reflexive is True: 

750 TC.add_edges_from( 

751 (v, u) for u in nx.descendants(G, v) | {v} if u not in TC[v] 

752 ) 

753 elif reflexive is False: 

754 TC.add_edges_from((v, e[1]) for e in nx.edge_bfs(G, v) if e[1] not in TC[v]) 

755 

756 return TC 

757 

758 

759@not_implemented_for("undirected") 

760@nx._dispatch(preserve_all_attrs=True) 

761def transitive_closure_dag(G, topo_order=None): 

762 """Returns the transitive closure of a directed acyclic graph. 

763 

764 This function is faster than the function `transitive_closure`, but fails 

765 if the graph has a cycle. 

766 

767 The transitive closure of G = (V,E) is a graph G+ = (V,E+) such that 

768 for all v, w in V there is an edge (v, w) in E+ if and only if there 

769 is a non-null path from v to w in G. 

770 

771 Parameters 

772 ---------- 

773 G : NetworkX DiGraph 

774 A directed acyclic graph (DAG) 

775 

776 topo_order: list or tuple, optional 

777 A topological order for G (if None, the function will compute one) 

778 

779 Returns 

780 ------- 

781 NetworkX DiGraph 

782 The transitive closure of `G` 

783 

784 Raises 

785 ------ 

786 NetworkXNotImplemented 

787 If `G` is not directed 

788 NetworkXUnfeasible 

789 If `G` has a cycle 

790 

791 Examples 

792 -------- 

793 >>> DG = nx.DiGraph([(1, 2), (2, 3)]) 

794 >>> TC = nx.transitive_closure_dag(DG) 

795 >>> TC.edges() 

796 OutEdgeView([(1, 2), (1, 3), (2, 3)]) 

797 

798 Notes 

799 ----- 

800 This algorithm is probably simple enough to be well-known but I didn't find 

801 a mention in the literature. 

802 """ 

803 if topo_order is None: 

804 topo_order = list(topological_sort(G)) 

805 

806 TC = G.copy() 

807 

808 # idea: traverse vertices following a reverse topological order, connecting 

809 # each vertex to its descendants at distance 2 as we go 

810 for v in reversed(topo_order): 

811 TC.add_edges_from((v, u) for u in nx.descendants_at_distance(TC, v, 2)) 

812 

813 return TC 

814 

815 

816@not_implemented_for("undirected") 

817@nx._dispatch 

818def transitive_reduction(G): 

819 """Returns transitive reduction of a directed graph 

820 

821 The transitive reduction of G = (V,E) is a graph G- = (V,E-) such that 

822 for all v,w in V there is an edge (v,w) in E- if and only if (v,w) is 

823 in E and there is no path from v to w in G with length greater than 1. 

824 

825 Parameters 

826 ---------- 

827 G : NetworkX DiGraph 

828 A directed acyclic graph (DAG) 

829 

830 Returns 

831 ------- 

832 NetworkX DiGraph 

833 The transitive reduction of `G` 

834 

835 Raises 

836 ------ 

837 NetworkXError 

838 If `G` is not a directed acyclic graph (DAG) transitive reduction is 

839 not uniquely defined and a :exc:`NetworkXError` exception is raised. 

840 

841 Examples 

842 -------- 

843 To perform transitive reduction on a DiGraph: 

844 

845 >>> DG = nx.DiGraph([(1, 2), (2, 3), (1, 3)]) 

846 >>> TR = nx.transitive_reduction(DG) 

847 >>> list(TR.edges) 

848 [(1, 2), (2, 3)] 

849 

850 To avoid unnecessary data copies, this implementation does not return a 

851 DiGraph with node/edge data. 

852 To perform transitive reduction on a DiGraph and transfer node/edge data: 

853 

854 >>> DG = nx.DiGraph() 

855 >>> DG.add_edges_from([(1, 2), (2, 3), (1, 3)], color='red') 

856 >>> TR = nx.transitive_reduction(DG) 

857 >>> TR.add_nodes_from(DG.nodes(data=True)) 

858 >>> TR.add_edges_from((u, v, DG.edges[u, v]) for u, v in TR.edges) 

859 >>> list(TR.edges(data=True)) 

860 [(1, 2, {'color': 'red'}), (2, 3, {'color': 'red'})] 

861 

862 References 

863 ---------- 

864 https://en.wikipedia.org/wiki/Transitive_reduction 

865 

866 """ 

867 if not is_directed_acyclic_graph(G): 

868 msg = "Directed Acyclic Graph required for transitive_reduction" 

869 raise nx.NetworkXError(msg) 

870 TR = nx.DiGraph() 

871 TR.add_nodes_from(G.nodes()) 

872 descendants = {} 

873 # count before removing set stored in descendants 

874 check_count = dict(G.in_degree) 

875 for u in G: 

876 u_nbrs = set(G[u]) 

877 for v in G[u]: 

878 if v in u_nbrs: 

879 if v not in descendants: 

880 descendants[v] = {y for x, y in nx.dfs_edges(G, v)} 

881 u_nbrs -= descendants[v] 

882 check_count[v] -= 1 

883 if check_count[v] == 0: 

884 del descendants[v] 

885 TR.add_edges_from((u, v) for v in u_nbrs) 

886 return TR 

887 

888 

889@not_implemented_for("undirected") 

890@nx._dispatch 

891def antichains(G, topo_order=None): 

892 """Generates antichains from a directed acyclic graph (DAG). 

893 

894 An antichain is a subset of a partially ordered set such that any 

895 two elements in the subset are incomparable. 

896 

897 Parameters 

898 ---------- 

899 G : NetworkX DiGraph 

900 A directed acyclic graph (DAG) 

901 

902 topo_order: list or tuple, optional 

903 A topological order for G (if None, the function will compute one) 

904 

905 Yields 

906 ------ 

907 antichain : list 

908 a list of nodes in `G` representing an antichain 

909 

910 Raises 

911 ------ 

912 NetworkXNotImplemented 

913 If `G` is not directed 

914 

915 NetworkXUnfeasible 

916 If `G` contains a cycle 

917 

918 Examples 

919 -------- 

920 >>> DG = nx.DiGraph([(1, 2), (1, 3)]) 

921 >>> list(nx.antichains(DG)) 

922 [[], [3], [2], [2, 3], [1]] 

923 

924 Notes 

925 ----- 

926 This function was originally developed by Peter Jipsen and Franco Saliola 

927 for the SAGE project. It's included in NetworkX with permission from the 

928 authors. Original SAGE code at: 

929 

930 https://github.com/sagemath/sage/blob/master/src/sage/combinat/posets/hasse_diagram.py 

931 

932 References 

933 ---------- 

934 .. [1] Free Lattices, by R. Freese, J. Jezek and J. B. Nation, 

935 AMS, Vol 42, 1995, p. 226. 

936 """ 

937 if topo_order is None: 

938 topo_order = list(nx.topological_sort(G)) 

939 

940 TC = nx.transitive_closure_dag(G, topo_order) 

941 antichains_stacks = [([], list(reversed(topo_order)))] 

942 

943 while antichains_stacks: 

944 (antichain, stack) = antichains_stacks.pop() 

945 # Invariant: 

946 # - the elements of antichain are independent 

947 # - the elements of stack are independent from those of antichain 

948 yield antichain 

949 while stack: 

950 x = stack.pop() 

951 new_antichain = antichain + [x] 

952 new_stack = [t for t in stack if not ((t in TC[x]) or (x in TC[t]))] 

953 antichains_stacks.append((new_antichain, new_stack)) 

954 

955 

956@not_implemented_for("undirected") 

957@nx._dispatch(edge_attrs={"weight": "default_weight"}) 

958def dag_longest_path(G, weight="weight", default_weight=1, topo_order=None): 

959 """Returns the longest path in a directed acyclic graph (DAG). 

960 

961 If `G` has edges with `weight` attribute the edge data are used as 

962 weight values. 

963 

964 Parameters 

965 ---------- 

966 G : NetworkX DiGraph 

967 A directed acyclic graph (DAG) 

968 

969 weight : str, optional 

970 Edge data key to use for weight 

971 

972 default_weight : int, optional 

973 The weight of edges that do not have a weight attribute 

974 

975 topo_order: list or tuple, optional 

976 A topological order for `G` (if None, the function will compute one) 

977 

978 Returns 

979 ------- 

980 list 

981 Longest path 

982 

983 Raises 

984 ------ 

985 NetworkXNotImplemented 

986 If `G` is not directed 

987 

988 Examples 

989 -------- 

990 >>> DG = nx.DiGraph([(0, 1, {'cost':1}), (1, 2, {'cost':1}), (0, 2, {'cost':42})]) 

991 >>> list(nx.all_simple_paths(DG, 0, 2)) 

992 [[0, 1, 2], [0, 2]] 

993 >>> nx.dag_longest_path(DG) 

994 [0, 1, 2] 

995 >>> nx.dag_longest_path(DG, weight="cost") 

996 [0, 2] 

997 

998 In the case where multiple valid topological orderings exist, `topo_order` 

999 can be used to specify a specific ordering: 

1000 

1001 >>> DG = nx.DiGraph([(0, 1), (0, 2)]) 

1002 >>> sorted(nx.all_topological_sorts(DG)) # Valid topological orderings 

1003 [[0, 1, 2], [0, 2, 1]] 

1004 >>> nx.dag_longest_path(DG, topo_order=[0, 1, 2]) 

1005 [0, 1] 

1006 >>> nx.dag_longest_path(DG, topo_order=[0, 2, 1]) 

1007 [0, 2] 

1008 

1009 See also 

1010 -------- 

1011 dag_longest_path_length 

1012 

1013 """ 

1014 if not G: 

1015 return [] 

1016 

1017 if topo_order is None: 

1018 topo_order = nx.topological_sort(G) 

1019 

1020 dist = {} # stores {v : (length, u)} 

1021 for v in topo_order: 

1022 us = [ 

1023 ( 

1024 dist[u][0] 

1025 + ( 

1026 max(data.values(), key=lambda x: x.get(weight, default_weight)) 

1027 if G.is_multigraph() 

1028 else data 

1029 ).get(weight, default_weight), 

1030 u, 

1031 ) 

1032 for u, data in G.pred[v].items() 

1033 ] 

1034 

1035 # Use the best predecessor if there is one and its distance is 

1036 # non-negative, otherwise terminate. 

1037 maxu = max(us, key=lambda x: x[0]) if us else (0, v) 

1038 dist[v] = maxu if maxu[0] >= 0 else (0, v) 

1039 

1040 u = None 

1041 v = max(dist, key=lambda x: dist[x][0]) 

1042 path = [] 

1043 while u != v: 

1044 path.append(v) 

1045 u = v 

1046 v = dist[v][1] 

1047 

1048 path.reverse() 

1049 return path 

1050 

1051 

1052@not_implemented_for("undirected") 

1053@nx._dispatch(edge_attrs={"weight": "default_weight"}) 

1054def dag_longest_path_length(G, weight="weight", default_weight=1): 

1055 """Returns the longest path length in a DAG 

1056 

1057 Parameters 

1058 ---------- 

1059 G : NetworkX DiGraph 

1060 A directed acyclic graph (DAG) 

1061 

1062 weight : string, optional 

1063 Edge data key to use for weight 

1064 

1065 default_weight : int, optional 

1066 The weight of edges that do not have a weight attribute 

1067 

1068 Returns 

1069 ------- 

1070 int 

1071 Longest path length 

1072 

1073 Raises 

1074 ------ 

1075 NetworkXNotImplemented 

1076 If `G` is not directed 

1077 

1078 Examples 

1079 -------- 

1080 >>> DG = nx.DiGraph([(0, 1, {'cost':1}), (1, 2, {'cost':1}), (0, 2, {'cost':42})]) 

1081 >>> list(nx.all_simple_paths(DG, 0, 2)) 

1082 [[0, 1, 2], [0, 2]] 

1083 >>> nx.dag_longest_path_length(DG) 

1084 2 

1085 >>> nx.dag_longest_path_length(DG, weight="cost") 

1086 42 

1087 

1088 See also 

1089 -------- 

1090 dag_longest_path 

1091 """ 

1092 path = nx.dag_longest_path(G, weight, default_weight) 

1093 path_length = 0 

1094 if G.is_multigraph(): 

1095 for u, v in pairwise(path): 

1096 i = max(G[u][v], key=lambda x: G[u][v][x].get(weight, default_weight))