Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# Source code for networkx.algorithms.dominance

"""
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')
[docs]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.

Raises
------
NetworkXNotImplemented
If G is undirected.

NetworkXError
If start is not in G.

Notes
-----
Except for start, the immediate dominators are the parents of their
corresponding nodes in the dominator tree.

Examples
--------
>>> G = nx.DiGraph([(1, 2), (1, 3), (2, 5), (3, 4), (4, 5)])
>>> sorted(nx.immediate_dominators(G, 1).items())
[(1, 1), (2, 1), (3, 1), (4, 3), (5, 1)]

References
----------
..  K. D. Cooper, T. J. Harvey, and K. Kennedy.
A simple, fast dominance algorithm.
Software Practice & Experience, 4:110, 2001.
"""
if start not in G:
raise nx.NetworkXError('start is not in G')

idom = {start: start}

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

return idom

[docs]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, ), (3, ), (4, ), (5, [])]

References
----------
..  K. D. Cooper, T. J. Harvey, and K. Kennedy.
A simple, fast dominance algorithm.
Software Practice & Experience, 4:110, 2001.
"""
idom = nx.immediate_dominators(G, start)

df = {u: [] for u in idom}

for u in idom:
if len(G.pred[u]) - int(u in G.pred[u]) >= 2:
p = set()
for v in G.pred[u]:
while v != idom[u] and v not in p: