File size: 3,897 Bytes
2216aae |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 |
"""
Dominance algorithms.
"""
from functools import reduce
import networkx as nx
from networkx.utils import not_implemented_for
__all__ = ["immediate_dominators", "dominance_frontiers"]
@not_implemented_for("undirected")
@nx._dispatchable
def immediate_dominators(G, start):
"""Returns the immediate dominators of all nodes of a directed graph.
Parameters
----------
G : a DiGraph or MultiDiGraph
The graph where dominance is to be computed.
start : node
The start node of dominance computation.
Returns
-------
idom : dict keyed by nodes
A dict containing the immediate dominators of each node reachable from
`start`, except for `start` itself.
Raises
------
NetworkXNotImplemented
If `G` is undirected.
NetworkXError
If `start` is not in `G`.
Notes
-----
The immediate dominators are the parents of their corresponding nodes in
the dominator tree. Every node reachable from `start` has an immediate
dominator, except for `start` itself.
Examples
--------
>>> G = nx.DiGraph([(1, 2), (1, 3), (2, 5), (3, 4), (4, 5)])
>>> sorted(nx.immediate_dominators(G, 1).items())
[(2, 1), (3, 1), (4, 3), (5, 1)]
References
----------
.. [1] Cooper, Keith D., Harvey, Timothy J. and Kennedy, Ken.
"A simple, fast dominance algorithm." (2006).
https://hdl.handle.net/1911/96345
.. [2] Lengauer, Thomas; Tarjan, Robert Endre (July 1979).
"A fast algorithm for finding dominators in a flowgraph".
ACM Transactions on Programming Languages and Systems. 1 (1): 121--141.
https://dl.acm.org/doi/10.1145/357062.357071
"""
if start not in G:
raise nx.NetworkXError("start is not in G")
idom = {start: None}
order = list(nx.dfs_postorder_nodes(G, start))
dfn = {u: i for i, u in enumerate(order)}
order.pop()
order.reverse()
def intersect(u, v):
while u != v:
while dfn[u] < dfn[v]:
u = idom[u]
while dfn[u] > dfn[v]:
v = idom[v]
return u
changed = True
while changed:
changed = False
for u in order:
new_idom = reduce(intersect, (v for v in G.pred[u] if v in idom))
if u not in idom or idom[u] != new_idom:
idom[u] = new_idom
changed = True
del idom[start]
return idom
@not_implemented_for("undirected")
@nx._dispatchable
def dominance_frontiers(G, start):
"""Returns the dominance frontiers of all nodes of a directed graph.
Parameters
----------
G : a DiGraph or MultiDiGraph
The graph where dominance is to be computed.
start : node
The start node of dominance computation.
Returns
-------
df : dict keyed by nodes
A dict containing the dominance frontiers of each node reachable from
`start` as lists.
Raises
------
NetworkXNotImplemented
If `G` is undirected.
NetworkXError
If `start` is not in `G`.
Examples
--------
>>> G = nx.DiGraph([(1, 2), (1, 3), (2, 5), (3, 4), (4, 5)])
>>> sorted((u, sorted(df)) for u, df in nx.dominance_frontiers(G, 1).items())
[(1, []), (2, [5]), (3, [5]), (4, [5]), (5, [])]
References
----------
.. [1] Cooper, Keith D., Harvey, Timothy J. and Kennedy, Ken.
"A simple, fast dominance algorithm." (2006).
https://hdl.handle.net/1911/96345
"""
idom = nx.immediate_dominators(G, start) | {start: None}
df = {u: set() for u in idom}
for u in idom:
if u == start or len(G.pred[u]) >= 2:
for v in G.pred[u]:
if v in idom:
while v != idom[u]:
df[v].add(u)
v = idom[v]
return df
|