Mercurial > repos > shellac > sam_consensus_v3

comparison env/lib/python3.9/site-packages/networkx/algorithms/dominance.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author shellac
date Mon, 22 Mar 2021 18:12:50 +0000
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:4f3585e2f14b
1 """
2 Dominance algorithms.
3 """
4
5 from functools import reduce
6 import networkx as nx
7 from networkx.utils import not_implemented_for
8
9 __all__ = ["immediate_dominators", "dominance_frontiers"]
10
11
12 @not_implemented_for("undirected")
13 def immediate_dominators(G, start):
14 """Returns the immediate dominators of all nodes of a directed graph.
15
16 Parameters
17 ----------
18 G : a DiGraph or MultiDiGraph
19 The graph where dominance is to be computed.
20
21 start : node
22 The start node of dominance computation.
23
24 Returns
25 -------
26 idom : dict keyed by nodes
27 A dict containing the immediate dominators of each node reachable from
28 `start`.
29
30 Raises
31 ------
32 NetworkXNotImplemented
33 If `G` is undirected.
34
35 NetworkXError
36 If `start` is not in `G`.
37
38 Notes
39 -----
40 Except for `start`, the immediate dominators are the parents of their
41 corresponding nodes in the dominator tree.
42
43 Examples
44 --------
45 >>> G = nx.DiGraph([(1, 2), (1, 3), (2, 5), (3, 4), (4, 5)])
46 >>> sorted(nx.immediate_dominators(G, 1).items())
47 [(1, 1), (2, 1), (3, 1), (4, 3), (5, 1)]
48
49 References
50 ----------
51 .. [1] K. D. Cooper, T. J. Harvey, and K. Kennedy.
52 A simple, fast dominance algorithm.
53 Software Practice & Experience, 4:110, 2001.
54 """
55 if start not in G:
56 raise nx.NetworkXError("start is not in G")
57
58 idom = {start: start}
59
60 order = list(nx.dfs_postorder_nodes(G, start))
61 dfn = {u: i for i, u in enumerate(order)}
62 order.pop()
63 order.reverse()
64
65 def intersect(u, v):
66 while u != v:
67 while dfn[u] < dfn[v]:
68 u = idom[u]
69 while dfn[u] > dfn[v]:
70 v = idom[v]
71 return u
72
73 changed = True
74 while changed:
75 changed = False
76 for u in order:
77 new_idom = reduce(intersect, (v for v in G.pred[u] if v in idom))
78 if u not in idom or idom[u] != new_idom:
79 idom[u] = new_idom
80 changed = True
81
82 return idom
83
84
85 def dominance_frontiers(G, start):
86 """Returns the dominance frontiers of all nodes of a directed graph.
87
88 Parameters
89 ----------
90 G : a DiGraph or MultiDiGraph
91 The graph where dominance is to be computed.
92
93 start : node
94 The start node of dominance computation.
95
96 Returns
97 -------
98 df : dict keyed by nodes
99 A dict containing the dominance frontiers of each node reachable from
100 `start` as lists.
101
102 Raises
103 ------
104 NetworkXNotImplemented
105 If `G` is undirected.
106
107 NetworkXError
108 If `start` is not in `G`.
109
110 Examples
111 --------
112 >>> G = nx.DiGraph([(1, 2), (1, 3), (2, 5), (3, 4), (4, 5)])
113 >>> sorted((u, sorted(df)) for u, df in nx.dominance_frontiers(G, 1).items())
114 [(1, []), (2, [5]), (3, [5]), (4, [5]), (5, [])]
115
116 References
117 ----------
118 .. [1] K. D. Cooper, T. J. Harvey, and K. Kennedy.
119 A simple, fast dominance algorithm.
120 Software Practice & Experience, 4:110, 2001.
121 """
122 idom = nx.immediate_dominators(G, start)
123
124 df = {u: set() for u in idom}
125 for u in idom:
126 if len(G.pred[u]) >= 2:
127 for v in G.pred[u]:
128 if v in idom:
129 while v != idom[u]:
130 df[v].add(u)
131 v = idom[v]
132 return df