ioftools / networkxMiCe / networkxmaster / networkx / algorithms / dominance.py @ 5cef0f13
History  View  Annotate  Download (3.55 KB)
1 
# Copyright (C) 20142019 by


2 
# Aric Hagberg <hagberg@lanl.gov>

3 
# Dan Schult <dschult@colgate.edu>

4 
# Pieter Swart <swart@lanl.gov>

5 
# All rights reserved.

6 
# BSD license.

7 
#

8 
# Authors: ysitu (ysitu@users.noreply.github.com)

9 
"""

10 
Dominance algorithms.

11 
"""

12  
13 
from functools import reduce 
14 
import networkx as nx 
15 
from networkx.utils import not_implemented_for 
16  
17 
__all__ = ['immediate_dominators', 'dominance_frontiers'] 
18  
19  
20 
@not_implemented_for('undirected') 
21 
def immediate_dominators(G, start): 
22 
"""Returns the immediate dominators of all nodes of a directed graph.

23 

24 
Parameters

25 


26 
G : a DiGraph or MultiDiGraph

27 
The graph where dominance is to be computed.

28 

29 
start : node

30 
The start node of dominance computation.

31 

32 
Returns

33 


34 
idom : dict keyed by nodes

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

36 
`start`.

37 

38 
Raises

39 


40 
NetworkXNotImplemented

41 
If `G` is undirected.

42 

43 
NetworkXError

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

45 

46 
Notes

47 


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

49 
corresponding nodes in the dominator tree.

50 

51 
Examples

52 


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

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

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

56 

57 
References

58 


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

60 
A simple, fast dominance algorithm.

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

62 
"""

63 
if start not in G: 
64 
raise nx.NetworkXError('start is not in G') 
65  
66 
idom = {start: start} 
67  
68 
order = list(nx.dfs_postorder_nodes(G, start))

69 
dfn = {u: i for i, u in enumerate(order)} 
70 
order.pop() 
71 
order.reverse() 
72  
73 
def intersect(u, v): 
74 
while u != v:

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

76 
u = idom[u] 
77 
while dfn[u] > dfn[v]:

78 
v = idom[v] 
79 
return u

80  
81 
changed = True

82 
while changed:

83 
changed = False

84 
for u in order: 
85 
new_idom = reduce(intersect, (v for v in G.pred[u] if v in idom)) 
86 
if u not in idom or idom[u] != new_idom: 
87 
idom[u] = new_idom 
88 
changed = True

89  
90 
return idom

91  
92  
93 
def dominance_frontiers(G, start): 
94 
"""Returns the dominance frontiers of all nodes of a directed graph.

95 

96 
Parameters

97 


98 
G : a DiGraph or MultiDiGraph

99 
The graph where dominance is to be computed.

100 

101 
start : node

102 
The start node of dominance computation.

103 

104 
Returns

105 


106 
df : dict keyed by nodes

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

108 
`start` as lists.

109 

110 
Raises

111 


112 
NetworkXNotImplemented

113 
If `G` is undirected.

114 

115 
NetworkXError

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

117 

118 
Examples

119 


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

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

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

123 

124 
References

125 


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

127 
A simple, fast dominance algorithm.

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

129 
"""

130 
idom = nx.immediate_dominators(G, start) 
131  
132 
df = {u: set() for u in idom} 
133 
for u in idom: 
134 
if len(G.pred[u]) >= 2: 
135 
for v in G.pred[u]: 
136 
if v in idom: 
137 
while v != idom[u]:

138 
df[v].add(u) 
139 
v = idom[v] 
140 
return df
