Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (6.66 KB)

1
# -*- coding: utf-8 -*-
2
# chains.py - functions for finding chains in a graph
3
#
4
# Copyright 2004-2019 NetworkX developers.
5
#
6
# This file is part of NetworkX.
7
#
8
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
9
# information.
10
"""Functions for finding chains in a graph."""
11

    
12
import networkx as nx
13
from networkx.utils import not_implemented_for
14

    
15

    
16
@not_implemented_for('directed')
17
@not_implemented_for('multigraph')
18
def chain_decomposition(G, root=None):
19
    """Returns the chain decomposition of a graph.
20

21
    The *chain decomposition* of a graph with respect a depth-first
22
    search tree is a set of cycles or paths derived from the set of
23
    fundamental cycles of the tree in the following manner. Consider
24
    each fundamental cycle with respect to the given tree, represented
25
    as a list of edges beginning with the nontree edge oriented away
26
    from the root of the tree. For each fundamental cycle, if it
27
    overlaps with any previous fundamental cycle, just take the initial
28
    non-overlapping segment, which is a path instead of a cycle. Each
29
    cycle or path is called a *chain*. For more information, see [1]_.
30

31
    Parameters
32
    ----------
33
    G : undirected graph
34

35
    root : node (optional)
36
       A node in the graph `G`. If specified, only the chain
37
       decomposition for the connected component containing this node
38
       will be returned. This node indicates the root of the depth-first
39
       search tree.
40

41
    Yields
42
    ------
43
    chain : list
44
       A list of edges representing a chain. There is no guarantee on
45
       the orientation of the edges in each chain (for example, if a
46
       chain includes the edge joining nodes 1 and 2, the chain may
47
       include either (1, 2) or (2, 1)).
48

49
    Raises
50
    ------
51
    NodeNotFound
52
       If `root` is not in the graph `G`.
53

54
    Notes
55
    -----
56
    The worst-case running time of this implementation is linear in the
57
    number of nodes and number of edges [1]_.
58

59
    References
60
    ----------
61
    .. [1] Jens M. Schmidt (2013). "A simple test on 2-vertex-
62
       and 2-edge-connectivity." *Information Processing Letters*,
63
       113, 241–244. Elsevier. <https://doi.org/10.1016/j.ipl.2013.01.016>
64

65
    """
66

    
67
    def _dfs_cycle_forest(G, root=None):
68
        """Builds a directed graph composed of cycles from the given graph.
69

70
        `G` is an undirected simple graph. `root` is a node in the graph
71
        from which the depth-first search is started.
72

73
        This function returns both the depth-first search cycle graph
74
        (as a :class:`~networkx.DiGraph`) and the list of nodes in
75
        depth-first preorder. The depth-first search cycle graph is a
76
        directed graph whose edges are the edges of `G` oriented toward
77
        the root if the edge is a tree edge and away from the root if
78
        the edge is a non-tree edge. If `root` is not specified, this
79
        performs a depth-first search on each connected component of `G`
80
        and returns a directed forest instead.
81

82
        If `root` is not in the graph, this raises :exc:`KeyError`.
83

84
        """
85
        # Create a directed graph from the depth-first search tree with
86
        # root node `root` in which tree edges are directed toward the
87
        # root and nontree edges are directed away from the root. For
88
        # each node with an incident nontree edge, this creates a
89
        # directed cycle starting with the nontree edge and returning to
90
        # that node.
91
        #
92
        # The `parent` node attribute stores the parent of each node in
93
        # the DFS tree. The `nontree` edge attribute indicates whether
94
        # the edge is a tree edge or a nontree edge.
95
        #
96
        # We also store the order of the nodes found in the depth-first
97
        # search in the `nodes` list.
98
        H = nx.DiGraph()
99
        nodes = []
100
        for u, v, d in nx.dfs_labeled_edges(G, source=root):
101
            if d == 'forward':
102
                # `dfs_labeled_edges()` yields (root, root, 'forward')
103
                # if it is beginning the search on a new connected
104
                # component.
105
                if u == v:
106
                    H.add_node(v, parent=None)
107
                    nodes.append(v)
108
                else:
109
                    H.add_node(v, parent=u)
110
                    H.add_edge(v, u, nontree=False)
111
                    nodes.append(v)
112
            # `dfs_labeled_edges` considers nontree edges in both
113
            # orientations, so we need to not add the edge if it its
114
            # other orientation has been added.
115
            elif d == 'nontree' and v not in H[u]:
116
                H.add_edge(v, u, nontree=True)
117
            else:
118
                # Do nothing on 'reverse' edges; we only care about
119
                # forward and nontree edges.
120
                pass
121
        return H, nodes
122

    
123
    def _build_chain(G, u, v, visited):
124
        """Generate the chain starting from the given nontree edge.
125

126
        `G` is a DFS cycle graph as constructed by
127
        :func:`_dfs_cycle_graph`. The edge (`u`, `v`) is a nontree edge
128
        that begins a chain. `visited` is a set representing the nodes
129
        in `G` that have already been visited.
130

131
        This function yields the edges in an initial segment of the
132
        fundamental cycle of `G` starting with the nontree edge (`u`,
133
        `v`) that includes all the edges up until the first node that
134
        appears in `visited`. The tree edges are given by the 'parent'
135
        node attribute. The `visited` set is updated to add each node in
136
        an edge yielded by this function.
137

138
        """
139
        while v not in visited:
140
            yield u, v
141
            visited.add(v)
142
            u, v = v, G.nodes[v]['parent']
143
        yield u, v
144

    
145
    # Create a directed version of H that has the DFS edges directed
146
    # toward the root and the nontree edges directed away from the root
147
    # (in each connected component).
148
    H, nodes = _dfs_cycle_forest(G, root)
149

    
150
    # Visit the nodes again in DFS order. For each node, and for each
151
    # nontree edge leaving that node, compute the fundamental cycle for
152
    # that nontree edge starting with that edge. If the fundamental
153
    # cycle overlaps with any visited nodes, just take the prefix of the
154
    # cycle up to the point of visited nodes.
155
    #
156
    # We repeat this process for each connected component (implicitly,
157
    # since `nodes` already has a list of the nodes grouped by connected
158
    # component).
159
    visited = set()
160
    for u in nodes:
161
        visited.add(u)
162
        # For each nontree edge going out of node u...
163
        edges = ((u, v) for u, v, d in H.out_edges(u, data='nontree') if d)
164
        for u, v in edges:
165
            # Create the cycle or cycle prefix starting with the
166
            # nontree edge.
167
            chain = list(_build_chain(H, u, v, visited))
168
            yield chain