## Mercurial > repos > shellac > sam_consensus_v3

### view 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 |

line wrap: on

line source

""" 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") 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: set() for u in idom} for u in idom: if 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