## iof-tools / networkxMiCe / networkx-master / networkx / algorithms / dominance.py @ 5cef0f13

History | View | Annotate | Download (3.55 KB)

1 | 5cef0f13 | tiamilani | ```
# Copyright (C) 2014-2019 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` |