Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / dominance.py @ 5cef0f13

History | View | Annotate | Download (3.55 KB)

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