__init__.py 17.2 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
6
# graph_tool -- a general graph manipulation python module
#
# Copyright (C) 2007-2010 Tiago de Paula Peixoto <tiago@forked.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
33
34
35
36
37

Summary
+++++++

.. autosummary::
   :nosignatures:

   edmonds_karp_max_flow
   push_relabel_max_flow
   kolmogorov_max_flow
   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
           "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
50
    r"""
    Calculate maximum flow on the graph with 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
78
79
80
81
82
83
84
85
86
87
88
89
90

    This algorithm provides a very simple and easy to implement solution to the
    maximum flow problem. However, there are several reasons why this algorithm
    is not as good as the push_relabel_max_flow() or the kolmogorov_max_flow()
    algorithm.

    - 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
99
100
101
102
    [ 0.          0.24058962  0.          0.          0.          0.          0.
      0.05688494  0.39495002  0.03148888  0.          0.05688494  0.          0.
      0.          0.          0.          0.          0.          0.          0.
      0.          0.          0.          0.          0.          0.03148888
      0.          0.          0.          0.          0.52856316  0.          0.
103
104
      0.          0.          0.          0.          0.          0.          0.
      0.          0.          0.          0.          0.          0.
Tiago Peixoto's avatar
Tiago Peixoto committed
105
106
107
108
109
110
111
112
113
114
115
      0.23696565  0.          0.          0.          0.          0.          0.
      0.          0.          0.          0.          0.13361314  0.
      0.03148888  0.          0.13361314  0.          0.          0.
      0.10335251  0.          0.          0.          0.          0.
      0.03148888  0.          0.          0.          0.          0.          0.
      0.          0.80064166  0.          0.          0.          0.          0.
      0.          0.          0.          0.          0.          0.          0.
      0.          0.          0.          0.          0.61693698  0.10335251
      0.13723711  0.          0.          0.05688494  0.          0.          0.
      0.          0.          0.          0.          0.08837382  0.          0.
      0.          0.          0.          0.          0.03148888  0.          0.
116
      0.          0.          0.          0.          0.          0.          0.
Tiago Peixoto's avatar
Tiago Peixoto committed
117
118
      0.          0.          0.          0.          0.          0.13361314
      0.          0.23696565  0.          0.          0.          0.          0.
119
120
121
      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
122
123
124
125
126
127
128
      0.13361314  0.          0.16872599  0.          0.          0.
      0.13361314  0.13723711  0.          0.          0.          0.          0.
      0.13723711  0.          0.          0.          0.          0.          0.
      0.          0.          0.          0.          0.          0.13361314
      0.          0.40569164  0.          0.          0.          0.          0.
      0.          0.          0.08837382  0.          0.          0.        ]

129
130
131

    References
    ----------
132
133
    .. [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
134
135
       improvements in the algorithmic efficiency for network flow problems.
       Journal of the ACM", 1972 19:248-264
136
    .. [ravindra-network-1993] Ravindra K. Ahuja and Thomas L. Magnanti and
137
138
139
140
       James B. Orlin,"Network Flows: Theory, Algorithms, and Applications".
       Prentice Hall, 1993.
    """

Tiago Peixoto's avatar
Tiago Peixoto committed
141
142
143
144
145
146
147
148
149
150
151
152
    _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")

    libgraph_tool_flow.\
           edmonds_karp_max_flow(g._Graph__graph, int(source), int(target),
                                 _prop("e", g, capacity),
                                 _prop("e", g, residual))
    return residual

Tiago Peixoto's avatar
Tiago Peixoto committed
153

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

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

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

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

    Examples
    --------
    >>> from numpy.random import seed, random
Tiago Peixoto's avatar
Tiago Peixoto committed
184
    >>> seed(43)
185
186
187
188
189
190
    >>> 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
191
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
223
    [ 0.00508328  0.24058962  0.          0.          0.07640118  0.          0.0149749
      0.00476207  0.39495002  0.06036354  0.07755781  0.05688494  0.00984535
      0.0149749   0.00984535  0.06594114  0.          0.0149749   0.          0.
      0.1383694   0.00984535  0.07755781  0.          0.          0.0149749
      0.06036354  0.          0.00512955  0.0702089   0.          0.63637368
      0.13988182  0.12852405  0.00476207  0.          0.          0.00512955
      0.05247866  0.          0.          0.01940656  0.          0.05159229
      0.00984535  0.          0.07755781  0.19097437  0.          0.
      0.05159229  0.00984535  0.          0.0227834   0.05247866  0.          0.
      0.          0.20608185  0.          0.10979179  0.01073172  0.07755781
      0.2159272   0.13988182  0.          0.14805691  0.          0.0227834   0.
      0.          0.          0.          0.          0.00984535  0.04127632
      0.02525962  0.          0.00984535  0.          0.80064166  0.02416862
      0.06440315  0.00508328  0.06372057  0.00512955  0.00508328  0.
      0.07755781  0.          0.00984535  0.0149749   0.06232401  0.07755781
      0.02525962  0.          0.          0.61693698  0.10335251  0.13723711
      0.0447044   0.00508328  0.00476207  0.12852405  0.07755781  0.06277679
      0.06232401  0.          0.00476207  0.04093717  0.02183962  0.02057707
      0.00476207  0.01802133  0.          0.          0.00730949  0.
      0.00476207  0.          0.1383694   0.00476207  0.00730949  0.04851461
      0.00476207  0.          0.0149749   0.00984535  0.06036354  0.
      0.00476207  0.          0.00984535  0.          0.15790227  0.
      0.05582411  0.0149749   0.04023452  0.07755781  0.1383694   0.10352007
      0.          0.          0.07755781  0.          0.          0.
      0.04127632  0.          0.05247866  0.02596227  0.          0.12408411
      0.00512955  0.          0.          0.          0.05247866  0.
      0.07755781  0.30420045  0.05247866  0.21471727  0.          0.          0.1139163
      0.33016596  0.1445466   0.          0.01802133  0.          0.01715485
      0.02416862  0.14962989  0.          0.00508328  0.          0.          0.
      0.00730949  0.          0.0227834   0.          0.          0.00476207
      0.07755781  0.          0.40569164  0.          0.          0.00476207
      0.04874567  0.00512955  0.          0.0227834   0.          0.00730949
      0.          0.00730949]
224
225
226

    References
    ----------
227
228
    .. [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
229
230
231
       Tehnical report MIT/LCS/TM-291, 1985.
    """

Tiago Peixoto's avatar
Tiago Peixoto committed
232
233
234
235
236
237
238
239
240
241
242
243
    _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")

    libgraph_tool_flow.\
           push_relabel_max_flow(g._Graph__graph, int(source), int(target),
                                 _prop("e", g, capacity),
                                 _prop("e", g, residual))
    return residual

Tiago Peixoto's avatar
Tiago Peixoto committed
244

Tiago Peixoto's avatar
Tiago Peixoto committed
245
def kolmogorov_max_flow(g, source, target, capacity, residual=None):
246
247
248
249
    r"""Calculate maximum flow on the graph with Kolmogorov algorithm.

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

    Returns
    -------
263
    residual : :class:`~graph_tool.PropertyMap`
264
265
266
267
268
        Edge property map with the residual capacities (capacity - flow).

    Notes
    -----

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

274
    For a more detailed description, see [boost-kolmogorov]_.
275
276
277
278

    Examples
    --------
    >>> from numpy.random import seed, random
Tiago Peixoto's avatar
Tiago Peixoto committed
279
    >>> seed(43)
280
281
282
283
284
285
    >>> 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
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
    [ 0.00508328  0.24058962  0.          0.          0.07640118  0.          0.0149749
      0.00476207  0.39495002  0.06036354  0.07755781  0.05688494  0.00984535
      0.0149749   0.00984535  0.06594114  0.          0.0149749   0.          0.
      0.1383694   0.00984535  0.07755781  0.          0.          0.0149749
      0.06036354  0.          0.00512955  0.0702089   0.          0.63637368
      0.13988182  0.12852405  0.00476207  0.          0.          0.00512955
      0.05247866  0.          0.          0.01940656  0.          0.05159229
      0.00984535  0.          0.07755781  0.19097437  0.          0.
      0.05159229  0.00984535  0.          0.0227834   0.05247866  0.          0.
      0.          0.20608185  0.          0.10979179  0.01073172  0.07755781
      0.2159272   0.13988182  0.          0.14805691  0.          0.0227834   0.
      0.          0.          0.          0.          0.00984535  0.04127632
      0.02525962  0.          0.00984535  0.          0.80064166  0.02416862
      0.06440315  0.00508328  0.06372057  0.00512955  0.00508328  0.
      0.07755781  0.          0.00984535  0.0149749   0.06232401  0.07755781
      0.02525962  0.          0.          0.61693698  0.10335251  0.13723711
      0.0447044   0.00508328  0.00476207  0.12852405  0.07755781  0.06277679
      0.06232401  0.          0.00476207  0.04093717  0.02183962  0.02057707
      0.00476207  0.01802133  0.          0.          0.00730949  0.
      0.00476207  0.          0.1383694   0.00476207  0.00730949  0.04851461
      0.00476207  0.          0.0149749   0.00984535  0.06036354  0.
      0.00476207  0.          0.00984535  0.          0.15790227  0.
      0.05582411  0.0149749   0.04023452  0.07755781  0.1383694   0.10352007
      0.          0.          0.07755781  0.          0.          0.
      0.04127632  0.          0.05247866  0.02596227  0.          0.12408411
      0.00512955  0.          0.          0.          0.05247866  0.
      0.07755781  0.30420045  0.05247866  0.21471727  0.          0.          0.1139163
      0.33016596  0.1445466   0.          0.01802133  0.          0.01715485
      0.02416862  0.14962989  0.          0.00508328  0.          0.          0.
      0.00730949  0.          0.0227834   0.          0.          0.00476207
      0.07755781  0.          0.40569164  0.          0.          0.00476207
      0.04874567  0.00512955  0.          0.0227834   0.          0.00730949
      0.          0.00730949]
319
320
321

    References
    ----------
322
323
    .. [boost-kolmogorov] http://www.boost.org/libs/graph/doc/kolmogorov_max_flow.html
    .. [kolmogorov-graph-2003] Vladimir Kolmogorov, "Graph Based Algorithms for
324
325
       Scene Reconstruction from Two or More Views", PhD thesis, Cornell
        University, September 2003.
326
    .. [boykov-experimental-2004] Yuri Boykov and Vladimir Kolmogorov, "An
327
328
329
330
       Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy
       Minimization", Vision In IEEE Transactions on Pattern Analysis and
       Machine Intelligence, vol. 26, no. 9, pp. 1124-1137, Sept. 2004.
    """
Tiago Peixoto's avatar
Tiago Peixoto committed
331
332
333
334
335
336
337
338
339
340
341
    _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")

    libgraph_tool_flow.\
           kolmogorov_max_flow(g._Graph__graph, int(source), int(target),
                                 _prop("e", g, capacity),
                                 _prop("e", g, residual))
    return residual
342

Tiago Peixoto's avatar
Tiago Peixoto committed
343

344
def max_cardinality_matching(g, match=None):
345
346
347
348
    r"""Find the maximum cardinality matching in the graph.

    Parameters
    ----------
349
    g : :class:`~graph_tool.Graph`
350
        Graph to be used.
351
    match : :class:`~graph_tool.PropertyMap` (optional, default: none)
352
353
354
355
        Edge property map where the matching will be specified.

    Returns
    -------
356
    match : :class:`~graph_tool.PropertyMap`
357
358
359
360
361
362
363
364
365
366
        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.

367
    For a more detailed description, see [boost-max-matching]_.
368
369
370
371

    Examples
    --------
    >>> from numpy.random import seed, random
Tiago Peixoto's avatar
Tiago Peixoto committed
372
    >>> seed(43)
373
374
375
376
377
378
379
380
381
382
383
384
385
386
    >>> 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
    ----------
387
    .. [boost-max-matching] http://www.boost.org/libs/graph/doc/maximum_matching.html
388
    """
389
390
391
392
393
394
395
396
397
398
399
    if match == None:
        match = g.new_edge_property("bool")
    _check_prop_scalar(match, "match")
    _check_prop_writable(match, "match")

    g.stash_filter(directed=True)
    g.set_directed(False)
    check = libgraph_tool_flow.\
            max_cardinality_matching(g._Graph__graph, _prop("e", g, match))
    g.pop_filter(directed=True)
    return match, check