Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (5.44 KB)

1
# -*- coding: utf-8 -*-
2
#
3
# Copyright (C) 2014
4
# ysitu <ysitu@users.noreply.github.com>
5
# All rights reserved.
6
# BSD license.
7
"""
8
Stoer-Wagner minimum cut algorithm.
9
"""
10
from itertools import islice
11

    
12
import networkx as nx
13
from ...utils import BinaryHeap
14
from ...utils import not_implemented_for
15
from ...utils import arbitrary_element
16

    
17
__author__ = 'ysitu <ysitu@users.noreply.github.com>'
18

    
19
__all__ = ['stoer_wagner']
20

    
21

    
22
@not_implemented_for('directed')
23
@not_implemented_for('multigraph')
24
def stoer_wagner(G, weight='weight', heap=BinaryHeap):
25
    r"""Returns the weighted minimum edge cut using the Stoer-Wagner algorithm.
26

27
    Determine the minimum edge cut of a connected graph using the
28
    Stoer-Wagner algorithm. In weighted cases, all weights must be
29
    nonnegative.
30

31
    The running time of the algorithm depends on the type of heaps used:
32

33
    ============== =============================================
34
    Type of heap   Running time
35
    ============== =============================================
36
    Binary heap    $O(n (m + n) \log n)$
37
    Fibonacci heap $O(nm + n^2 \log n)$
38
    Pairing heap   $O(2^{2 \sqrt{\log \log n}} nm + n^2 \log n)$
39
    ============== =============================================
40

41
    Parameters
42
    ----------
43
    G : NetworkX graph
44
        Edges of the graph are expected to have an attribute named by the
45
        weight parameter below. If this attribute is not present, the edge is
46
        considered to have unit weight.
47

48
    weight : string
49
        Name of the weight attribute of the edges. If the attribute is not
50
        present, unit weight is assumed. Default value: 'weight'.
51

52
    heap : class
53
        Type of heap to be used in the algorithm. It should be a subclass of
54
        :class:`MinHeap` or implement a compatible interface.
55

56
        If a stock heap implementation is to be used, :class:`BinaryHeap` is
57
        recommended over :class:`PairingHeap` for Python implementations without
58
        optimized attribute accesses (e.g., CPython) despite a slower
59
        asymptotic running time. For Python implementations with optimized
60
        attribute accesses (e.g., PyPy), :class:`PairingHeap` provides better
61
        performance. Default value: :class:`BinaryHeap`.
62

63
    Returns
64
    -------
65
    cut_value : integer or float
66
        The sum of weights of edges in a minimum cut.
67

68
    partition : pair of node lists
69
        A partitioning of the nodes that defines a minimum cut.
70

71
    Raises
72
    ------
73
    NetworkXNotImplemented
74
        If the graph is directed or a multigraph.
75

76
    NetworkXError
77
        If the graph has less than two nodes, is not connected or has a
78
        negative-weighted edge.
79

80
    Examples
81
    --------
82
    >>> G = nx.Graph()
83
    >>> G.add_edge('x', 'a', weight=3)
84
    >>> G.add_edge('x', 'b', weight=1)
85
    >>> G.add_edge('a', 'c', weight=3)
86
    >>> G.add_edge('b', 'c', weight=5)
87
    >>> G.add_edge('b', 'd', weight=4)
88
    >>> G.add_edge('d', 'e', weight=2)
89
    >>> G.add_edge('c', 'y', weight=2)
90
    >>> G.add_edge('e', 'y', weight=3)
91
    >>> cut_value, partition = nx.stoer_wagner(G)
92
    >>> cut_value
93
    4
94
    """
95
    n = len(G)
96
    if n < 2:
97
        raise nx.NetworkXError('graph has less than two nodes.')
98
    if not nx.is_connected(G):
99
        raise nx.NetworkXError('graph is not connected.')
100

    
101
    # Make a copy of the graph for internal use.
102
    G = nx.Graph((u, v, {'weight': e.get(weight, 1)})
103
                 for u, v, e in G.edges(data=True) if u != v)
104

    
105
    for u, v, e, in G.edges(data=True):
106
        if e['weight'] < 0:
107
            raise nx.NetworkXError('graph has a negative-weighted edge.')
108

    
109
    cut_value = float('inf')
110
    nodes = set(G)
111
    contractions = []  # contracted node pairs
112

    
113
    # Repeatedly pick a pair of nodes to contract until only one node is left.
114
    for i in range(n - 1):
115
        # Pick an arbitrary node u and create a set A = {u}.
116
        u = arbitrary_element(G)
117
        A = set([u])
118
        # Repeatedly pick the node "most tightly connected" to A and add it to
119
        # A. The tightness of connectivity of a node not in A is defined by the
120
        # of edges connecting it to nodes in A.
121
        h = heap()  # min-heap emulating a max-heap
122
        for v, e in G[u].items():
123
            h.insert(v, -e['weight'])
124
        # Repeat until all but one node has been added to A.
125
        for j in range(n - i - 2):
126
            u = h.pop()[0]
127
            A.add(u)
128
            for v, e, in G[u].items():
129
                if v not in A:
130
                    h.insert(v, h.get(v, 0) - e['weight'])
131
        # A and the remaining node v define a "cut of the phase". There is a
132
        # minimum cut of the original graph that is also a cut of the phase.
133
        # Due to contractions in earlier phases, v may in fact represent
134
        # multiple nodes in the original graph.
135
        v, w = h.min()
136
        w = -w
137
        if w < cut_value:
138
            cut_value = w
139
            best_phase = i
140
        # Contract v and the last node added to A.
141
        contractions.append((u, v))
142
        for w, e in G[v].items():
143
            if w != u:
144
                if w not in G[u]:
145
                    G.add_edge(u, w, weight=e['weight'])
146
                else:
147
                    G[u][w]['weight'] += e['weight']
148
        G.remove_node(v)
149

    
150
    # Recover the optimal partitioning from the contractions.
151
    G = nx.Graph(islice(contractions, best_phase))
152
    v = contractions[best_phase][1]
153
    G.add_node(v)
154
    reachable = set(nx.single_source_shortest_path_length(G, v))
155
    partition = (list(reachable), list(nodes - reachable))
156

    
157
    return cut_value, partition