Coverage for python / lsst / pipe / base / graph_walker.py: 25%

1# This file is part of pipe_base. 

2# 

3# Developed for the LSST Data Management System. 

4# This product includes software developed by the LSST Project 

5# (http://www.lsst.org). 

6# See the COPYRIGHT file at the top-level directory of this distribution 

7# for details of code ownership. 

8# 

9# This software is dual licensed under the GNU General Public License and also 

10# under a 3-clause BSD license. Recipients may choose which of these licenses 

11# to use; please see the files gpl-3.0.txt and/or bsd_license.txt, 

12# respectively. If you choose the GPL option then the following text applies 

13# (but note that there is still no warranty even if you opt for BSD instead): 

14# 

15# This program is free software: you can redistribute it and/or modify 

16# it under the terms of the GNU General Public License as published by 

17# the Free Software Foundation, either version 3 of the License, or 

18# (at your option) any later version. 

19# 

20# This program is distributed in the hope that it will be useful, 

21# but WITHOUT ANY WARRANTY; without even the implied warranty of 

22# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 

23# GNU General Public License for more details. 

24# 

25# You should have received a copy of the GNU General Public License 

26# along with this program. If not, see <http://www.gnu.org/licenses/>. 

27 

28from __future__ import annotations 

29 

30__all__ = ("GraphWalker",) 

31 

32from typing import Generic, Self, TypeVar 

33 

34import networkx 

35 

36_T = TypeVar("_T") 

37 

38 

39class GraphWalker(Generic[_T]): 

40 """A helper for traversing directed acyclic graphs. 

41 

42 Parameters 

43 ---------- 

44 xgraph : `networkx.DiGraph` or `networkx.MultiDiGraph` 

45 Networkx graph to process. Will be consumed during iteration, so this 

46 should often be a copy. 

47 

48 Notes 

49 ----- 

50 Each iteration yields a `frozenset` of nodes, which may be empty if there 

51 are no nodes ready for processing. A node is only considered ready if all 

52 of its predecessor nodes have been marked as complete with `finish`. 

53 Iteration only completes when all nodes have been finished or failed. 

54 

55 `GraphWalker` is not thread-safe; calling one `GraphWalker` method while 

56 another is in progress is undefined behavior. It is designed to be used 

57 in the management thread or process in a parallel traversal. 

58 """ 

59 

60 def __init__(self, xgraph: networkx.DiGraph | networkx.MultiDiGraph): 

61 self._xgraph = xgraph 

62 self._ready: set[_T] = set(next(iter(networkx.dag.topological_generations(self._xgraph)), [])) 

63 self._active: set[_T] = set() 

64 self._incomplete: set[_T] = set(self._xgraph) 

65 

66 def __iter__(self) -> Self: 

67 return self 

68 

69 def __next__(self) -> frozenset[_T]: 

70 if not self._incomplete: 

71 raise StopIteration() 

72 new_active = frozenset(self._ready) 

73 self._active.update(new_active) 

74 self._ready.clear() 

75 return new_active 

76 

77 def finish(self, key: _T) -> None: 

78 """Mark a node as successfully processed, unblocking (at least in part) 

79 iteration over successor nodes. 

80 

81 Parameters 

82 ---------- 

83 key : unspecified 

84 NetworkX key of the node to mark finished. Does not need to have 

85 been returned by the iterator yet. 

86 """ 

87 self._incomplete.remove(key) 

88 self._active.discard(key) 

89 self._ready.discard(key) 

90 successors = list(self._xgraph.successors(key)) 

91 for successor in successors: 

92 assert successor not in self._active, ( 

93 "A node downstream of an active one should not have been yielded yet." 

94 ) 

95 if all( 

96 predecessor not in self._incomplete for predecessor in self._xgraph.predecessors(successor) 

97 ): 

98 self._ready.add(successor) 

99 

100 def fail(self, key: _T) -> list[_T]: 

101 """Mark a node as unsuccessfully processed, permanently blocking all 

102 recursive descendants. 

103 

104 Parameters 

105 ---------- 

106 key : unspecified 

107 NetworkX key of the node to mark as a failure. Does not need to 

108 have been returned by the iterator yet. 

109 

110 Returns 

111 ------- 

112 blocked : `list` 

113 NetworkX keys of nodes that were recursive descendants of the 

114 failed node, and will hence never be yielded by the iterator. 

115 """ 

116 self._incomplete.remove(key) 

117 self._active.discard(key) 

118 self._ready.discard(key) 

119 descendants = list(networkx.dag.descendants(self._xgraph, key)) 

120 self._xgraph.remove_node(key) 

121 self._xgraph.remove_nodes_from(descendants) 

122 self._incomplete.difference_update(descendants) 

123 return descendants