__init__.py 12.8 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-2011 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
++++++++
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

The following network will be used as an example throughout the documentation.

.. testcode::

    from numpy.random import seed, random
    from scipy.linalg import norm
    seed(42)
    points = random((400, 2)) * 10
    points[0] = [0, 0]
    points[1] = [10, 10]
    g, pos = gt.triangulation(points, type="delaunay")
    g.set_directed(True)
    edges = list(g.edges())
    # reciprocate edges
    for e in edges:
        g.add_edge(e.target(), e.source())
    # The capacity will be defined as the inverse euclidian distance
    cap = g.new_edge_property("double")
    for e in g.edges():
        cap[e] = min(1.0 / norm(pos[e.target()].a - pos[e.source()].a), 10)
    g.edge_properties["cap"] = cap
    g.vertex_properties["pos"] = pos
    g.save("flow-example.xml.gz")
62
    gt.graph_draw(g, pos=pos, pin=True, penwidth=cap, output="flow-example.pdf")
63
64


65
.. figure:: flow-example.*
66
67
68
69
70
    :align: center

    Example network used in the documentation below. The edge capacities are
    represented by the edge width.

Tiago Peixoto's avatar
Tiago Peixoto committed
71
72
73
74
75
"""

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

76
from .. import _prop, _check_prop_scalar, _check_prop_writable
Tiago Peixoto's avatar
Tiago Peixoto committed
77
__all__ = ["edmonds_karp_max_flow", "push_relabel_max_flow",
78
           "boykov_kolmogorov_max_flow", "max_cardinality_matching"]
Tiago Peixoto's avatar
Tiago Peixoto committed
79

Tiago Peixoto's avatar
Tiago Peixoto committed
80

Tiago Peixoto's avatar
Tiago Peixoto committed
81
def edmonds_karp_max_flow(g, source, target, capacity, residual=None):
82
    r"""
83
    Calculate maximum flow on the graph with the Edmonds-Karp algorithm.
84
85
86

    Parameters
    ----------
87
    g : :class:`~graph_tool.Graph`
88
89
90
91
92
        Graph to be used.
    source : Vertex
        The source vertex.
    target : Vertex
        The target (or "sink") vertex.
93
    capacity : :class:`~graph_tool.PropertyMap`
94
        Edge property map with the edge capacities.
95
    residual : :class:`~graph_tool.PropertyMap` (optional, default: none)
96
97
98
99
        Edge property map where the residuals should be stored.

    Returns
    -------
100
    residual : :class:`~graph_tool.PropertyMap`
101
102
103
104
        Edge property map with the residual capacities (capacity - flow).

    Notes
    -----
105
106
107
    The algorithm is due to [edmonds-theoretical-1972]_, though we are using the
    variation called the "labeling algorithm" described in
    [ravindra-network-1993]_.
108
109
110

    This algorithm provides a very simple and easy to implement solution to the
    maximum flow problem. However, there are several reasons why this algorithm
111
112
    is not as good as the push_relabel_max_flow() or the
    boykov_kolmogorov_max_flow() algorithm.
113
114
115
116
117
118
119
120
121
122

    - 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
    --------
123
124
125
126
127
128
129
130
131
    >>> g = gt.load_graph("flow-example.xml.gz")
    >>> cap = g.edge_properties["cap"]
    >>> src, tgt = g.vertex(0), g.vertex(1)
    >>> res = gt.edmonds_karp_max_flow(g, src, tgt, cap)
    >>> res.a = cap.a - res.a  # the actual flow
    >>> max_flow = sum(res[e] for e in tgt.in_edges())
    >>> print max_flow
    6.92759897841
    >>> pos = g.vertex_properties["pos"]
132
    >>> gt.graph_draw(g, pos=pos, pin=True, penwidth=res, output="example-edmonds-karp.pdf")
133
134
    <...>

135
    .. figure:: example-edmonds-karp.*
136
137
138
139
140
141
        :align: center

        Edge flows obtained with the Edmonds-Karp algorithm. The source and
        target are on the lower left and upper right corners, respectively. The
        edge flows are represented by the edge width.

142
143
144

    References
    ----------
145
146
    .. [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
147
       improvements in the algorithmic efficiency for network flow problems.
Tiago Peixoto's avatar
Tiago Peixoto committed
148
       Journal of the ACM", 19:248-264, 1972 :doi:`10.1145/321694.321699`
149
    .. [ravindra-network-1993] Ravindra K. Ahuja and Thomas L. Magnanti and
150
151
152
153
       James B. Orlin,"Network Flows: Theory, Algorithms, and Applications".
       Prentice Hall, 1993.
    """

Tiago Peixoto's avatar
Tiago Peixoto committed
154
155
156
157
158
159
    _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")

160
161
162
    if not g.is_directed():
        raise ValueError("The graph provided must be directed!")

Tiago Peixoto's avatar
Tiago Peixoto committed
163
    libgraph_tool_flow.\
164
165
166
               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
167
168
    return residual

Tiago Peixoto's avatar
Tiago Peixoto committed
169

Tiago Peixoto's avatar
Tiago Peixoto committed
170
def push_relabel_max_flow(g, source, target, capacity, residual=None):
171
    r"""
172
    Calculate maximum flow on the graph with the push-relabel algorithm.
173
174
175

    Parameters
    ----------
176
    g : :class:`~graph_tool.Graph`
177
178
179
180
181
        Graph to be used.
    source : Vertex
        The source vertex.
    target : Vertex
        The target (or "sink") vertex.
182
    capacity : :class:`~graph_tool.PropertyMap`
183
        Edge property map with the edge capacities.
184
    residual : :class:`~graph_tool.PropertyMap` (optional, default: none)
185
186
187
188
        Edge property map where the residuals should be stored.

    Returns
    -------
189
    residual : :class:`~graph_tool.PropertyMap`
190
191
192
193
        Edge property map with the residual capacities (capacity - flow).

    Notes
    -----
194
    The algorithm is defined in [goldberg-new-1985]_. The complexity is
195
196
197
198
    :math:`O(V^3)`.

    Examples
    --------
199
200
201
202
203
204
205
206
207
    >>> g = gt.load_graph("flow-example.xml.gz")
    >>> cap = g.edge_properties["cap"]
    >>> src, tgt = g.vertex(0), g.vertex(1)
    >>> res = gt.push_relabel_max_flow(g, src, tgt, cap)
    >>> res.a = cap.a - res.a  # the actual flow
    >>> max_flow = sum(res[e] for e in tgt.in_edges())
    >>> print max_flow
    6.92759897841
    >>> pos = g.vertex_properties["pos"]
208
    >>> gt.graph_draw(g, pos=pos, pin=True, penwidth=res, output="example-push-relabel.pdf")
209
210
    <...>

211
    .. figure:: example-push-relabel.*
212
213
214
215
216
217
        :align: center


        Edge flows obtained with the push-relabel algorithm. The source and
        target are on the lower left and upper right corners, respectively. The
        edge flows are represented by the edge width.
218
219
220

    References
    ----------
221
222
    .. [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
223
224
225
       Tehnical report MIT/LCS/TM-291, 1985.
    """

Tiago Peixoto's avatar
Tiago Peixoto committed
226
227
228
229
230
231
    _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")

232
233
234
    if not g.is_directed():
        raise ValueError("The graph provided must be directed!")

Tiago Peixoto's avatar
Tiago Peixoto committed
235
    libgraph_tool_flow.\
236
237
238
239
               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
240
241
    return residual

Tiago Peixoto's avatar
Tiago Peixoto committed
242

243
244
def boykov_kolmogorov_max_flow(g, source, target, capacity, residual=None):
    r"""Calculate maximum flow on the graph with the Boykov-Kolmogorov algorithm.
245
246
247

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

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

    Notes
    -----

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

272
    For a more detailed description, see [boost-kolmogorov]_.
273
274
275

    Examples
    --------
276
277
278
279
280
281
282
283
284
    >>> g = gt.load_graph("flow-example.xml.gz")
    >>> cap = g.edge_properties["cap"]
    >>> src, tgt = g.vertex(0), g.vertex(1)
    >>> res = gt.boykov_kolmogorov_max_flow(g, src, tgt, cap)
    >>> res.a = cap.a - res.a  # the actual flow
    >>> max_flow = sum(res[e] for e in tgt.in_edges())
    >>> print max_flow
    6.92759897841
    >>> pos = g.vertex_properties["pos"]
285
    >>> gt.graph_draw(g, pos=pos, pin=True, penwidth=res, output="example-kolmogorov.pdf")
286
287
    <...>

288
    .. figure:: example-kolmogorov.*
289
290
291
292
293
        :align: center

        Edge flows obtained with the Boykov-Kolmogorov algorithm. The source and
        target are on the lower left and upper right corners, respectively. The
        edge flows are represented by the edge width.
294
295
296

    References
    ----------
297
    .. [boost-kolmogorov] http://www.boost.org/libs/graph/doc/boykov_kolmogorov_max_flow.html
298
    .. [kolmogorov-graph-2003] Vladimir Kolmogorov, "Graph Based Algorithms for
299
       Scene Reconstruction from Two or More Views", PhD thesis, Cornell
300
       University, September 2003.
301
    .. [boykov-experimental-2004] Yuri Boykov and Vladimir Kolmogorov, "An
302
       Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy
303
       Minimization in Vision", IEEE Transactions on Pattern Analysis and
304
       Machine Intelligence, vol. 26, no. 9, pp. 1124-1137, Sept. 2004.
305
       :doi:`10.1109/TPAMI.2004.60`
306
    """
Tiago Peixoto's avatar
Tiago Peixoto committed
307
308
309
310
311
312
    _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")

313
314
315
    if not g.is_directed():
        raise ValueError("The graph provided must be directed!")

Tiago Peixoto's avatar
Tiago Peixoto committed
316
    libgraph_tool_flow.\
317
318
319
               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
320
    return residual
321

Tiago Peixoto's avatar
Tiago Peixoto committed
322

323
def max_cardinality_matching(g, match=None):
324
325
326
327
    r"""Find the maximum cardinality matching in the graph.

    Parameters
    ----------
328
    g : :class:`~graph_tool.Graph`
329
        Graph to be used.
330
    match : :class:`~graph_tool.PropertyMap` (optional, default: none)
331
332
333
334
        Edge property map where the matching will be specified.

    Returns
    -------
335
    match : :class:`~graph_tool.PropertyMap`
336
337
338
339
340
341
342
343
344
345
        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.

346
    For a more detailed description, see [boost-max-matching]_.
347
348
349
350

    Examples
    --------
    >>> from numpy.random import seed, random
Tiago Peixoto's avatar
Tiago Peixoto committed
351
    >>> seed(43)
352
353
354
355
    >>> g = gt.random_graph(100, lambda: (2,2))
    >>> res = gt.max_cardinality_matching(g)
    >>> print res[1]
    True
356
    >>> gt.graph_draw(g, ecolor=res[0], output="max_card_match.pdf")
357
358
    <...>

359
    .. figure:: max_card_match.*
360
361
362
363
364
365
        :align: center

        Edges belonging to the matching are in red.

    References
    ----------
366
    .. [boost-max-matching] http://www.boost.org/libs/graph/doc/maximum_matching.html
367
    """
368
369
370
371
372
    if match == None:
        match = g.new_edge_property("bool")
    _check_prop_scalar(match, "match")
    _check_prop_writable(match, "match")

373
374
375
376
377
378
379
380
    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)

381
    return match, check