Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/algorithms/dominance.py @ 1:56ad4e20f292 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
author guerler
date Fri, 31 Jul 2020 00:32:28 -0400
parents
children
comparison
equal deleted inserted replaced
0:d30785e31577 1:56ad4e20f292
1 # 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