__init__.py 16.3 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1
#! /usr/bin/env python
2
# -*- coding: utf-8 -*-
Tiago Peixoto's avatar
Tiago Peixoto committed
3
#
4
5
# graph_tool -- a general graph manipulation python module
#
Tiago Peixoto's avatar
Tiago Peixoto committed
6
# Copyright (C) 2007-2010 Tiago de Paula Peixoto <tiago@skewed.de>
Tiago Peixoto's avatar
Tiago Peixoto committed
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.

"""
``graph_tool.flow`` - Maximum flow algorithms
---------------------------------------------
24
25
26
27
28
29
30
31
32

Summary
+++++++

.. autosummary::
   :nosignatures:

   edmonds_karp_max_flow
   push_relabel_max_flow
33
   boykov_kolmogorov_max_flow
34
35
36
37
   max_cardinality_matching

Contents
++++++++
Tiago Peixoto's avatar
Tiago Peixoto committed
38
39
40
41
42
43
44
"""

from .. dl_import import dl_import
dl_import("import libgraph_tool_flow")

from .. core import _prop, _check_prop_scalar, _check_prop_writable
__all__ = ["edmonds_karp_max_flow", "push_relabel_max_flow",
45
           "boykov_kolmogorov_max_flow", "max_cardinality_matching"]
Tiago Peixoto's avatar
Tiago Peixoto committed
46

Tiago Peixoto's avatar
Tiago Peixoto committed
47

Tiago Peixoto's avatar
Tiago Peixoto committed
48
def edmonds_karp_max_flow(g, source, target, capacity, residual=None):
49
    r"""
50
    Calculate maximum flow on the graph with the Edmonds-Karp algorithm.
51
52
53

    Parameters
    ----------
54
    g : :class:`~graph_tool.Graph`
55
56
57
58
59
        Graph to be used.
    source : Vertex
        The source vertex.
    target : Vertex
        The target (or "sink") vertex.
60
    capacity : :class:`~graph_tool.PropertyMap`
61
        Edge property map with the edge capacities.
62
    residual : :class:`~graph_tool.PropertyMap` (optional, default: none)
63
64
65
66
        Edge property map where the residuals should be stored.

    Returns
    -------
67
    residual : :class:`~graph_tool.PropertyMap`
68
69
70
71
        Edge property map with the residual capacities (capacity - flow).

    Notes
    -----
72
73
74
    The algorithm is due to [edmonds-theoretical-1972]_, though we are using the
    variation called the "labeling algorithm" described in
    [ravindra-network-1993]_.
75
76
77

    This algorithm provides a very simple and easy to implement solution to the
    maximum flow problem. However, there are several reasons why this algorithm
78
79
    is not as good as the push_relabel_max_flow() or the
    boykov_kolmogorov_max_flow() algorithm.
80
81
82
83
84
85
86
87
88
89
90

    - In the non-integer capacity case, the time complexity is :math:`O(V E^2)`
      which is worse than the time complexity of the push-relabel algorithm
      :math:`O(V^2E^{1/2})` for all but the sparsest of graphs.

    - In the integer capacity case, if the capacity bound U is very large then
      the algorithm will take a long time.

    Examples
    --------
    >>> from numpy.random import seed, random
Tiago Peixoto's avatar
Tiago Peixoto committed
91
    >>> seed(43)
92
93
94
95
96
97
    >>> g = gt.random_graph(100, lambda: (2,2))
    >>> c = g.new_edge_property("double")
    >>> c.a = random(len(c.a))
    >>> res = gt.edmonds_karp_max_flow(g, g.vertex(0), g.vertex(1), c)
    >>> res.a = c.a - res.a  # the actual flow
    >>> print res.a[0:g.num_edges()]
Tiago Peixoto's avatar
Tiago Peixoto committed
98
    [ 0.13339096  0.13339096  0.          0.          0.          0.          0.
Tiago Peixoto's avatar
Tiago Peixoto committed
99
      0.          0.          0.          0.          0.          0.          0.
100
      0.          0.          0.          0.          0.          0.          0.
Tiago Peixoto's avatar
Tiago Peixoto committed
101
      0.          0.          0.          0.          0.          0.          0.
102
103
104
105
      0.          0.          0.          0.          0.          0.          0.
      0.          0.          0.          0.          0.          0.          0.
      0.          0.          0.          0.          0.          0.          0.
      0.          0.          0.          0.          0.          0.          0.
Tiago Peixoto's avatar
Tiago Peixoto committed
106
107
108
109
110
      0.          0.          0.20608185  0.          0.          0.
      0.08000038  0.          0.          0.          0.          0.          0.
      0.12608147  0.          0.          0.          0.          0.          0.
      0.          0.          0.          0.08000038  0.          0.
      0.00730949  0.          0.          0.          0.          0.          0.
Tiago Peixoto's avatar
Tiago Peixoto committed
111
      0.          0.          0.          0.          0.          0.          0.
Tiago Peixoto's avatar
Tiago Peixoto committed
112
113
114
115
      0.          0.13339096  0.          0.          0.          0.          0.
      0.08000038  0.08000038  0.          0.          0.          0.          0.
      0.          0.12608147  0.          0.          0.          0.          0.
      0.          0.          0.          0.          0.          0.00730949
Tiago Peixoto's avatar
Tiago Peixoto committed
116
117
      0.          0.          0.          0.          0.          0.          0.
      0.          0.          0.          0.          0.          0.          0.
Tiago Peixoto's avatar
Tiago Peixoto committed
118
      0.08000038  0.          0.          0.          0.          0.          0.
Tiago Peixoto's avatar
Tiago Peixoto committed
119
120
      0.          0.          0.          0.          0.          0.          0.
      0.          0.          0.          0.          0.          0.          0.
Tiago Peixoto's avatar
Tiago Peixoto committed
121
122
123
124
125
126
      0.          0.          0.          0.          0.          0.          0.
      0.          0.          0.          0.          0.          0.          0.
      0.          0.          0.          0.          0.          0.          0.
      0.          0.          0.          0.          0.          0.          0.
      0.08000038  0.          0.          0.          0.          0.          0.
      0.00730949  0.          0.12608147  0.          0.          0.          0.        ]
127
128
129

    References
    ----------
130
131
    .. [boost-edmonds-karp] http://www.boost.org/libs/graph/doc/edmonds_karp_max_flow.html
    .. [edmonds-theoretical-1972] Jack Edmonds and Richard M. Karp, "Theoretical
132
       improvements in the algorithmic efficiency for network flow problems.
Tiago Peixoto's avatar
Tiago Peixoto committed
133
       Journal of the ACM", 19:248-264, 1972 :doi:`10.1145/321694.321699`
134
    .. [ravindra-network-1993] Ravindra K. Ahuja and Thomas L. Magnanti and
135
136
137
138
       James B. Orlin,"Network Flows: Theory, Algorithms, and Applications".
       Prentice Hall, 1993.
    """

Tiago Peixoto's avatar
Tiago Peixoto committed
139
140
141
142
143
144
    _check_prop_scalar(capacity, "capacity")
    if residual == None:
        residual = g.new_edge_property(capacity.value_type())
    _check_prop_scalar(residual, "residual")
    _check_prop_writable(residual, "residual")

145
146
147
    if not g.is_directed():
        raise ValueError("The graph provided must be directed!")

Tiago Peixoto's avatar
Tiago Peixoto committed
148
    libgraph_tool_flow.\
149
150
151
               edmonds_karp_max_flow(g._Graph__graph, int(source), int(target),
                                     _prop("e", g, capacity),
                                     _prop("e", g, residual))
Tiago Peixoto's avatar
Tiago Peixoto committed
152
153
    return residual

Tiago Peixoto's avatar
Tiago Peixoto committed
154

Tiago Peixoto's avatar
Tiago Peixoto committed
155
def push_relabel_max_flow(g, source, target, capacity, residual=None):
156
    r"""
157
    Calculate maximum flow on the graph with the push-relabel algorithm.
158
159
160

    Parameters
    ----------
161
    g : :class:`~graph_tool.Graph`
162
163
164
165
166
        Graph to be used.
    source : Vertex
        The source vertex.
    target : Vertex
        The target (or "sink") vertex.
167
    capacity : :class:`~graph_tool.PropertyMap`
168
        Edge property map with the edge capacities.
169
    residual : :class:`~graph_tool.PropertyMap` (optional, default: none)
170
171
172
173
        Edge property map where the residuals should be stored.

    Returns
    -------
174
    residual : :class:`~graph_tool.PropertyMap`
175
176
177
178
        Edge property map with the residual capacities (capacity - flow).

    Notes
    -----
179
    The algorithm is defined in [goldberg-new-1985]_. The complexity is
180
181
182
183
184
    :math:`O(V^3)`.

    Examples
    --------
    >>> from numpy.random import seed, random
Tiago Peixoto's avatar
Tiago Peixoto committed
185
    >>> seed(43)
186
187
188
189
190
191
    >>> g = gt.random_graph(100, lambda: (2,2))
    >>> c = g.new_edge_property("double")
    >>> c.a = random(len(c.a))
    >>> res = gt.push_relabel_max_flow(g, g.vertex(0), g.vertex(1), c)
    >>> res.a = c.a - res.a  # the actual flow
    >>> print res.a[0:g.num_edges()]
Tiago Peixoto's avatar
Tiago Peixoto committed
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
    [ 0.00730949  0.0835572   0.          0.          0.          0.          0.
      0.06926091  0.06926091  0.          0.07624771  0.          0.03957485
      0.05028544  0.05028544  0.          0.          0.          0.07624771
      0.07624771  0.          0.07624771  0.          0.          0.07624771
      0.          0.          0.          0.          0.          0.20608185
      0.03395359  0.          0.          0.06926091  0.          0.          0.
      0.          0.          0.          0.          0.06926091  0.
      0.03957485  0.          0.          0.          0.          0.
      0.02596227  0.05028544  0.12983414  0.          0.          0.
      0.06926091  0.          0.20608185  0.          0.          0.          0.
      0.12983414  0.          0.          0.          0.04480769  0.          0.
      0.          0.06926091  0.          0.          0.06926091  0.03957485
      0.06926091  0.05028544  0.          0.06057324  0.          0.
      0.00730949  0.          0.          0.          0.          0.02596227
      0.          0.03667285  0.          0.          0.          0.          0.
      0.          0.          0.0835572   0.          0.          0.          0.
      0.07624771  0.12983414  0.12983414  0.          0.          0.
      0.02596227  0.          0.          0.          0.          0.05028544
      0.          0.          0.          0.04480769  0.          0.          0.
      0.          0.00730949  0.          0.          0.06926091  0.
      0.05028544  0.          0.          0.03395359  0.          0.          0.
      0.          0.          0.          0.06057324  0.          0.          0.
      0.03395359  0.          0.          0.          0.          0.01633184
      0.          0.          0.          0.          0.02596227  0.          0.
      0.          0.          0.          0.          0.03395359  0.          0.
      0.          0.          0.          0.00547774  0.          0.12983414
      0.03395359  0.          0.          0.          0.          0.00547774
      0.          0.          0.          0.          0.          0.03957485
      0.03395359  0.          0.06926091  0.          0.          0.          0.
      0.          0.          0.          0.          0.          0.          0.
      0.00730949  0.07624771  0.20608185  0.          0.          0.          0.        ]
223
224
225

    References
    ----------
226
227
    .. [boost-push-relabel] http://www.boost.org/libs/graph/doc/push_relabel_max_flow.html
    .. [goldberg-new-1985] A. V. Goldberg, "A New Max-Flow Algorithm",  MIT
228
229
230
       Tehnical report MIT/LCS/TM-291, 1985.
    """

Tiago Peixoto's avatar
Tiago Peixoto committed
231
232
233
234
235
236
    _check_prop_scalar(capacity, "capacity")
    if residual == None:
        residual = g.new_edge_property(capacity.value_type())
    _check_prop_scalar(residual, "residual")
    _check_prop_writable(residual, "residual")

237
238
239
    if not g.is_directed():
        raise ValueError("The graph provided must be directed!")

Tiago Peixoto's avatar
Tiago Peixoto committed
240
    libgraph_tool_flow.\
241
242
243
244
               push_relabel_max_flow(g._Graph__graph, int(source), int(target),
                                     _prop("e", g, capacity),
                                     _prop("e", g, residual))

Tiago Peixoto's avatar
Tiago Peixoto committed
245
246
    return residual

Tiago Peixoto's avatar
Tiago Peixoto committed
247

248
249
def boykov_kolmogorov_max_flow(g, source, target, capacity, residual=None):
    r"""Calculate maximum flow on the graph with the Boykov-Kolmogorov algorithm.
250
251
252

    Parameters
    ----------
253
    g : :class:`~graph_tool.Graph`
254
255
256
257
258
        Graph to be used.
    source : Vertex
        The source vertex.
    target : Vertex
        The target (or "sink") vertex.
259
    capacity : :class:`~graph_tool.PropertyMap`
260
        Edge property map with the edge capacities.
261
    residual : :class:`~graph_tool.PropertyMap` (optional, default: none)
262
263
264
265
        Edge property map where the residuals should be stored.

    Returns
    -------
266
    residual : :class:`~graph_tool.PropertyMap`
267
268
269
270
271
        Edge property map with the residual capacities (capacity - flow).

    Notes
    -----

272
273
    The algorithm is defined in [kolmogorov-graph-2003]_ and
    [boykov-experimental-2004]_. The worst case complexity is
274
    :math:`O(EV^2|C|)`, where :math:`|C|` is the minimum cut (but typically
Tiago Peixoto's avatar
Tiago Peixoto committed
275
    performs much better).
276

277
    For a more detailed description, see [boost-kolmogorov]_.
278
279
280
281

    Examples
    --------
    >>> from numpy.random import seed, random
Tiago Peixoto's avatar
Tiago Peixoto committed
282
    >>> seed(43)
283
284
285
    >>> g = gt.random_graph(100, lambda: (2,2))
    >>> c = g.new_edge_property("double")
    >>> c.a = random(len(c.a))
286
    >>> res = gt.boykov_kolmogorov_max_flow(g, g.vertex(0), g.vertex(1), c)
287
288
    >>> res.a = c.a - res.a  # the actual flow
    >>> print res.a[0:g.num_edges()]
289
290
    [ 0.13339096  0.13339096  0.          0.          0.          0.          0.
      0.          0.00730949  0.          0.          0.          0.          0.
Tiago Peixoto's avatar
Tiago Peixoto committed
291
      0.          0.          0.          0.          0.          0.          0.
292
293
294
295
296
297
298
299
300
301
302
      0.          0.          0.          0.          0.          0.          0.
      0.          0.          0.          0.          0.          0.          0.
      0.          0.          0.          0.          0.          0.          0.
      0.          0.          0.          0.          0.          0.          0.
      0.          0.          0.          0.          0.          0.          0.
      0.          0.          0.20608185  0.          0.          0.
      0.07269089  0.          0.00730949  0.          0.          0.          0.
      0.13339096  0.          0.          0.          0.          0.          0.
      0.          0.          0.          0.07269089  0.          0.          0.
      0.          0.          0.          0.          0.          0.          0.
      0.          0.          0.          0.          0.          0.          0.        ]
303
304
305

    References
    ----------
306
307
    .. [boost-kolmogorov] http://www.boost.org/libs/graph/doc/kolmogorov_max_flow.html
    .. [kolmogorov-graph-2003] Vladimir Kolmogorov, "Graph Based Algorithms for
308
       Scene Reconstruction from Two or More Views", PhD thesis, Cornell
309
       University, September 2003.
310
    .. [boykov-experimental-2004] Yuri Boykov and Vladimir Kolmogorov, "An
311
       Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy
312
       Minimization in Vision", IEEE Transactions on Pattern Analysis and
313
       Machine Intelligence, vol. 26, no. 9, pp. 1124-1137, Sept. 2004.
314
       :doi:`10.1109/TPAMI.2004.60`
315
    """
Tiago Peixoto's avatar
Tiago Peixoto committed
316
317
318
319
320
321
    _check_prop_scalar(capacity, "capacity")
    if residual == None:
        residual = g.new_edge_property(capacity.value_type())
    _check_prop_scalar(residual, "residual")
    _check_prop_writable(residual, "residual")

322
323
324
    if not g.is_directed():
        raise ValueError("The graph provided must be directed!")

Tiago Peixoto's avatar
Tiago Peixoto committed
325
    libgraph_tool_flow.\
326
327
328
               kolmogorov_max_flow(g._Graph__graph, int(source), int(target),
                                   _prop("e", g, capacity),
                                   _prop("e", g, residual))
Tiago Peixoto's avatar
Tiago Peixoto committed
329
    return residual
330

Tiago Peixoto's avatar
Tiago Peixoto committed
331

332
def max_cardinality_matching(g, match=None):
333
334
335
336
    r"""Find the maximum cardinality matching in the graph.

    Parameters
    ----------
337
    g : :class:`~graph_tool.Graph`
338
        Graph to be used.
339
    match : :class:`~graph_tool.PropertyMap` (optional, default: none)
340
341
342
343
        Edge property map where the matching will be specified.

    Returns
    -------
344
    match : :class:`~graph_tool.PropertyMap`
345
346
347
348
349
350
351
352
353
354
        Boolean edge property map where the matching is specified.
    is_maximal : bool
        True if the matching is indeed maximal, or False otherwise.

    Notes
    -----
    A *matching* is a subset of the edges of a graph such that no two edges
    share a common vertex. A *maximum cardinality matching* has maximum size
    over all matchings in the graph.

355
    For a more detailed description, see [boost-max-matching]_.
356
357
358
359

    Examples
    --------
    >>> from numpy.random import seed, random
Tiago Peixoto's avatar
Tiago Peixoto committed
360
    >>> seed(43)
361
362
363
364
365
366
367
368
369
370
371
372
373
374
    >>> g = gt.random_graph(100, lambda: (2,2))
    >>> res = gt.max_cardinality_matching(g)
    >>> print res[1]
    True
    >>> gt.graph_draw(g, ecolor=res[0], output="max_card_match.png")
    <...>

    .. figure:: max_card_match.png
        :align: center

        Edges belonging to the matching are in red.

    References
    ----------
375
    .. [boost-max-matching] http://www.boost.org/libs/graph/doc/maximum_matching.html
376
    """
377
378
379
380
381
    if match == None:
        match = g.new_edge_property("bool")
    _check_prop_scalar(match, "match")
    _check_prop_writable(match, "match")

382
383
384
385
386
387
388
389
    try:
        g.stash_filter(directed=True)
        g.set_directed(False)
        check = libgraph_tool_flow.\
                max_cardinality_matching(g._Graph__graph, _prop("e", g, match))
    finally:
        g.pop_filter(directed=True)

390
    return match, check