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

1""" 

2Dominance algorithms. 

3""" 

4 

5from functools import reduce 

6 

7import networkx as nx 

8from networkx.utils import not_implemented_for 

9 

10__all__ = ["immediate_dominators", "dominance_frontiers"] 

11 

12 

13@not_implemented_for("undirected") 

14@nx._dispatch 

15def immediate_dominators(G, start): 

16 """Returns the immediate dominators of all nodes of a directed graph. 

17 

18 Parameters 

19 ---------- 

20 G : a DiGraph or MultiDiGraph 

21 The graph where dominance is to be computed. 

22 

23 start : node 

24 The start node of dominance computation. 

25 

26 Returns 

27 ------- 

28 idom : dict keyed by nodes 

29 A dict containing the immediate dominators of each node reachable from 

30 `start`. 

31 

32 Raises 

33 ------ 

34 NetworkXNotImplemented 

35 If `G` is undirected. 

36 

37 NetworkXError 

38 If `start` is not in `G`. 

39 

40 Notes 

41 ----- 

42 Except for `start`, the immediate dominators are the parents of their 

43 corresponding nodes in the dominator tree. 

44 

45 Examples 

46 -------- 

47 >>> G = nx.DiGraph([(1, 2), (1, 3), (2, 5), (3, 4), (4, 5)]) 

48 >>> sorted(nx.immediate_dominators(G, 1).items()) 

49 [(1, 1), (2, 1), (3, 1), (4, 3), (5, 1)] 

50 

51 References 

52 ---------- 

53 .. [1] K. D. Cooper, T. J. Harvey, and K. Kennedy. 

54 A simple, fast dominance algorithm. 

55 Software Practice & Experience, 4:110, 2001. 

56 """ 

57 if start not in G: 

58 raise nx.NetworkXError("start is not in G") 

59 

60 idom = {start: start} 

61 

62 order = list(nx.dfs_postorder_nodes(G, start)) 

63 dfn = {u: i for i, u in enumerate(order)} 

64 order.pop() 

65 order.reverse() 

66 

67 def intersect(u, v): 

68 while u != v: 

69 while dfn[u] < dfn[v]: 

70 u = idom[u] 

71 while dfn[u] > dfn[v]: 

72 v = idom[v] 

73 return u 

74 

75 changed = True 

76 while changed: 

77 changed = False 

78 for u in order: 

79 new_idom = reduce(intersect, (v for v in G.pred[u] if v in idom)) 

80 if u not in idom or idom[u] != new_idom: 

81 idom[u] = new_idom 

82 changed = True 

83 

84 return idom 

85 

86 

87@nx._dispatch 

88def dominance_frontiers(G, start): 

89 """Returns the dominance frontiers of all nodes of a directed graph. 

90 

91 Parameters 

92 ---------- 

93 G : a DiGraph or MultiDiGraph 

94 The graph where dominance is to be computed. 

95 

96 start : node 

97 The start node of dominance computation. 

98 

99 Returns 

100 ------- 

101 df : dict keyed by nodes 

102 A dict containing the dominance frontiers of each node reachable from 

103 `start` as lists. 

104 

105 Raises 

106 ------ 

107 NetworkXNotImplemented 

108 If `G` is undirected. 

109 

110 NetworkXError 

111 If `start` is not in `G`. 

112 

113 Examples 

114 -------- 

115 >>> G = nx.DiGraph([(1, 2), (1, 3), (2, 5), (3, 4), (4, 5)]) 

116 >>> sorted((u, sorted(df)) for u, df in nx.dominance_frontiers(G, 1).items()) 

117 [(1, []), (2, [5]), (3, [5]), (4, [5]), (5, [])] 

118 

119 References 

120 ---------- 

121 .. [1] K. D. Cooper, T. J. Harvey, and K. Kennedy. 

122 A simple, fast dominance algorithm. 

123 Software Practice & Experience, 4:110, 2001. 

124 """ 

125 idom = nx.immediate_dominators(G, start) 

126 

127 df = {u: set() for u in idom} 

128 for u in idom: 

129 if len(G.pred[u]) >= 2: 

130 for v in G.pred[u]: 

131 if v in idom: 

132 while v != idom[u]: 

133 df[v].add(u) 

134 v = idom[v] 

135 return df