/usr/lib/python3/dist-packages/networkx/algorithms/dominance.py is in python3-networkx 1.11-1ubuntu2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 | """
Dominance algorithms.
"""
__author__ = 'ysitu <ysitu@users.noreply.github.com>'
# Copyright (C) 2014 ysitu <ysitu@users.noreply.github.com>
# All rights reserved.
# BSD license.
from functools import reduce
import networkx as nx
from networkx.utils import not_implemented_for
__all__ = ['immediate_dominators', 'dominance_frontiers']
@not_implemented_for('undirected')
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
----------
.. [1] 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
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] 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:
p.add(v)
v = idom[v]
p.discard(u)
for v in p:
df[v].append(u)
return df
|