Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (12.2 KB)

1
# -*- coding: utf-8 -*-
2
"""
3
Minimum cost flow algorithms on directed connected graphs.
4
"""
5

    
6
__author__ = """Loïc Séguin-C. <loicseguin@gmail.com>"""
7
# Copyright (C) 2010 Loïc Séguin-C. <loicseguin@gmail.com>
8
# All rights reserved.
9
# BSD license.
10

    
11

    
12
__all__ = ['min_cost_flow_cost',
13
           'min_cost_flow',
14
           'cost_of_flow',
15
           'max_flow_min_cost']
16

    
17
import networkx as nx
18

    
19

    
20
def min_cost_flow_cost(G, demand='demand', capacity='capacity',
21
                       weight='weight'):
22
    r"""Find the cost of a minimum cost flow satisfying all demands in digraph G.
23

24
    G is a digraph with edge costs and capacities and in which nodes
25
    have demand, i.e., they want to send or receive some amount of
26
    flow. A negative demand means that the node wants to send flow, a
27
    positive demand means that the node want to receive flow. A flow on
28
    the digraph G satisfies all demand if the net flow into each node
29
    is equal to the demand of that node.
30

31
    Parameters
32
    ----------
33
    G : NetworkX graph
34
        DiGraph on which a minimum cost flow satisfying all demands is
35
        to be found.
36

37
    demand : string
38
        Nodes of the graph G are expected to have an attribute demand
39
        that indicates how much flow a node wants to send (negative
40
        demand) or receive (positive demand). Note that the sum of the
41
        demands should be 0 otherwise the problem in not feasible. If
42
        this attribute is not present, a node is considered to have 0
43
        demand. Default value: 'demand'.
44

45
    capacity : string
46
        Edges of the graph G are expected to have an attribute capacity
47
        that indicates how much flow the edge can support. If this
48
        attribute is not present, the edge is considered to have
49
        infinite capacity. Default value: 'capacity'.
50

51
    weight : string
52
        Edges of the graph G are expected to have an attribute weight
53
        that indicates the cost incurred by sending one unit of flow on
54
        that edge. If not present, the weight is considered to be 0.
55
        Default value: 'weight'.
56

57
    Returns
58
    -------
59
    flowCost : integer, float
60
        Cost of a minimum cost flow satisfying all demands.
61

62
    Raises
63
    ------
64
    NetworkXError
65
        This exception is raised if the input graph is not directed or
66
        not connected.
67

68
    NetworkXUnfeasible
69
        This exception is raised in the following situations:
70

71
            * The sum of the demands is not zero. Then, there is no
72
              flow satisfying all demands.
73
            * There is no flow satisfying all demand.
74

75
    NetworkXUnbounded
76
        This exception is raised if the digraph G has a cycle of
77
        negative cost and infinite capacity. Then, the cost of a flow
78
        satisfying all demands is unbounded below.
79

80
    See also
81
    --------
82
    cost_of_flow, max_flow_min_cost, min_cost_flow, network_simplex
83

84
    Notes
85
    -----
86
    This algorithm is not guaranteed to work if edge weights or demands
87
    are floating point numbers (overflows and roundoff errors can
88
    cause problems). As a workaround you can use integer numbers by
89
    multiplying the relevant edge attributes by a convenient
90
    constant factor (eg 100).
91

92
    Examples
93
    --------
94
    A simple example of a min cost flow problem.
95

96
    >>> import networkx as nx
97
    >>> G = nx.DiGraph()
98
    >>> G.add_node('a', demand = -5)
99
    >>> G.add_node('d', demand = 5)
100
    >>> G.add_edge('a', 'b', weight = 3, capacity = 4)
101
    >>> G.add_edge('a', 'c', weight = 6, capacity = 10)
102
    >>> G.add_edge('b', 'd', weight = 1, capacity = 9)
103
    >>> G.add_edge('c', 'd', weight = 2, capacity = 5)
104
    >>> flowCost = nx.min_cost_flow_cost(G)
105
    >>> flowCost
106
    24
107
    """
108
    return nx.network_simplex(G, demand=demand, capacity=capacity,
109
                              weight=weight)[0]
110

    
111

    
112
def min_cost_flow(G, demand='demand', capacity='capacity',
113
                  weight='weight'):
114
    r"""Returns a minimum cost flow satisfying all demands in digraph G.
115

116
    G is a digraph with edge costs and capacities and in which nodes
117
    have demand, i.e., they want to send or receive some amount of
118
    flow. A negative demand means that the node wants to send flow, a
119
    positive demand means that the node want to receive flow. A flow on
120
    the digraph G satisfies all demand if the net flow into each node
121
    is equal to the demand of that node.
122

123
    Parameters
124
    ----------
125
    G : NetworkX graph
126
        DiGraph on which a minimum cost flow satisfying all demands is
127
        to be found.
128

129
    demand : string
130
        Nodes of the graph G are expected to have an attribute demand
131
        that indicates how much flow a node wants to send (negative
132
        demand) or receive (positive demand). Note that the sum of the
133
        demands should be 0 otherwise the problem in not feasible. If
134
        this attribute is not present, a node is considered to have 0
135
        demand. Default value: 'demand'.
136

137
    capacity : string
138
        Edges of the graph G are expected to have an attribute capacity
139
        that indicates how much flow the edge can support. If this
140
        attribute is not present, the edge is considered to have
141
        infinite capacity. Default value: 'capacity'.
142

143
    weight : string
144
        Edges of the graph G are expected to have an attribute weight
145
        that indicates the cost incurred by sending one unit of flow on
146
        that edge. If not present, the weight is considered to be 0.
147
        Default value: 'weight'.
148

149
    Returns
150
    -------
151
    flowDict : dictionary
152
        Dictionary of dictionaries keyed by nodes such that
153
        flowDict[u][v] is the flow edge (u, v).
154

155
    Raises
156
    ------
157
    NetworkXError
158
        This exception is raised if the input graph is not directed or
159
        not connected.
160

161
    NetworkXUnfeasible
162
        This exception is raised in the following situations:
163

164
            * The sum of the demands is not zero. Then, there is no
165
              flow satisfying all demands.
166
            * There is no flow satisfying all demand.
167

168
    NetworkXUnbounded
169
        This exception is raised if the digraph G has a cycle of
170
        negative cost and infinite capacity. Then, the cost of a flow
171
        satisfying all demands is unbounded below.
172

173
    See also
174
    --------
175
    cost_of_flow, max_flow_min_cost, min_cost_flow_cost, network_simplex
176

177
    Notes
178
    -----
179
    This algorithm is not guaranteed to work if edge weights or demands
180
    are floating point numbers (overflows and roundoff errors can
181
    cause problems). As a workaround you can use integer numbers by
182
    multiplying the relevant edge attributes by a convenient
183
    constant factor (eg 100).
184

185
    Examples
186
    --------
187
    A simple example of a min cost flow problem.
188

189
    >>> import networkx as nx
190
    >>> G = nx.DiGraph()
191
    >>> G.add_node('a', demand = -5)
192
    >>> G.add_node('d', demand = 5)
193
    >>> G.add_edge('a', 'b', weight = 3, capacity = 4)
194
    >>> G.add_edge('a', 'c', weight = 6, capacity = 10)
195
    >>> G.add_edge('b', 'd', weight = 1, capacity = 9)
196
    >>> G.add_edge('c', 'd', weight = 2, capacity = 5)
197
    >>> flowDict = nx.min_cost_flow(G)
198
    """
199
    return nx.network_simplex(G, demand=demand, capacity=capacity,
200
                              weight=weight)[1]
201

    
202

    
203
def cost_of_flow(G, flowDict, weight='weight'):
204
    """Compute the cost of the flow given by flowDict on graph G.
205

206
    Note that this function does not check for the validity of the
207
    flow flowDict. This function will fail if the graph G and the
208
    flow don't have the same edge set.
209

210
    Parameters
211
    ----------
212
    G : NetworkX graph
213
        DiGraph on which a minimum cost flow satisfying all demands is
214
        to be found.
215

216
    weight : string
217
        Edges of the graph G are expected to have an attribute weight
218
        that indicates the cost incurred by sending one unit of flow on
219
        that edge. If not present, the weight is considered to be 0.
220
        Default value: 'weight'.
221

222
    flowDict : dictionary
223
        Dictionary of dictionaries keyed by nodes such that
224
        flowDict[u][v] is the flow edge (u, v).
225

226
    Returns
227
    -------
228
    cost : Integer, float
229
        The total cost of the flow. This is given by the sum over all
230
        edges of the product of the edge's flow and the edge's weight.
231

232
    See also
233
    --------
234
    max_flow_min_cost, min_cost_flow, min_cost_flow_cost, network_simplex
235

236
    Notes
237
    -----
238
    This algorithm is not guaranteed to work if edge weights or demands
239
    are floating point numbers (overflows and roundoff errors can
240
    cause problems). As a workaround you can use integer numbers by
241
    multiplying the relevant edge attributes by a convenient
242
    constant factor (eg 100).
243
    """
244
    return sum((flowDict[u][v] * d.get(weight, 0)
245
                for u, v, d in G.edges(data=True)))
246

    
247

    
248
def max_flow_min_cost(G, s, t, capacity='capacity', weight='weight'):
249
    """Returns a maximum (s, t)-flow of minimum cost.
250

251
    G is a digraph with edge costs and capacities. There is a source
252
    node s and a sink node t. This function finds a maximum flow from
253
    s to t whose total cost is minimized.
254

255
    Parameters
256
    ----------
257
    G : NetworkX graph
258
        DiGraph on which a minimum cost flow satisfying all demands is
259
        to be found.
260

261
    s: node label
262
        Source of the flow.
263

264
    t: node label
265
        Destination of the flow.
266

267
    capacity: string
268
        Edges of the graph G are expected to have an attribute capacity
269
        that indicates how much flow the edge can support. If this
270
        attribute is not present, the edge is considered to have
271
        infinite capacity. Default value: 'capacity'.
272

273
    weight: string
274
        Edges of the graph G are expected to have an attribute weight
275
        that indicates the cost incurred by sending one unit of flow on
276
        that edge. If not present, the weight is considered to be 0.
277
        Default value: 'weight'.
278

279
    Returns
280
    -------
281
    flowDict: dictionary
282
        Dictionary of dictionaries keyed by nodes such that
283
        flowDict[u][v] is the flow edge (u, v).
284

285
    Raises
286
    ------
287
    NetworkXError
288
        This exception is raised if the input graph is not directed or
289
        not connected.
290

291
    NetworkXUnbounded
292
        This exception is raised if there is an infinite capacity path
293
        from s to t in G. In this case there is no maximum flow. This
294
        exception is also raised if the digraph G has a cycle of
295
        negative cost and infinite capacity. Then, the cost of a flow
296
        is unbounded below.
297

298
    See also
299
    --------
300
    cost_of_flow, min_cost_flow, min_cost_flow_cost, network_simplex
301

302
    Notes
303
    -----
304
    This algorithm is not guaranteed to work if edge weights or demands
305
    are floating point numbers (overflows and roundoff errors can
306
    cause problems). As a workaround you can use integer numbers by
307
    multiplying the relevant edge attributes by a convenient
308
    constant factor (eg 100).
309

310
    Examples
311
    --------
312
    >>> G = nx.DiGraph()
313
    >>> G.add_edges_from([(1, 2, {'capacity': 12, 'weight': 4}),
314
    ...                   (1, 3, {'capacity': 20, 'weight': 6}),
315
    ...                   (2, 3, {'capacity': 6, 'weight': -3}),
316
    ...                   (2, 6, {'capacity': 14, 'weight': 1}),
317
    ...                   (3, 4, {'weight': 9}),
318
    ...                   (3, 5, {'capacity': 10, 'weight': 5}),
319
    ...                   (4, 2, {'capacity': 19, 'weight': 13}),
320
    ...                   (4, 5, {'capacity': 4, 'weight': 0}),
321
    ...                   (5, 7, {'capacity': 28, 'weight': 2}),
322
    ...                   (6, 5, {'capacity': 11, 'weight': 1}),
323
    ...                   (6, 7, {'weight': 8}),
324
    ...                   (7, 4, {'capacity': 6, 'weight': 6})])
325
    >>> mincostFlow = nx.max_flow_min_cost(G, 1, 7)
326
    >>> mincost = nx.cost_of_flow(G, mincostFlow)
327
    >>> mincost
328
    373
329
    >>> from networkx.algorithms.flow import maximum_flow
330
    >>> maxFlow = maximum_flow(G, 1, 7)[1]
331
    >>> nx.cost_of_flow(G, maxFlow) >= mincost
332
    True
333
    >>> mincostFlowValue = (sum((mincostFlow[u][7] for u in G.predecessors(7)))
334
    ...                     - sum((mincostFlow[7][v] for v in G.successors(7))))
335
    >>> mincostFlowValue == nx.maximum_flow_value(G, 1, 7)
336
    True
337

338
    """
339
    maxFlow = nx.maximum_flow_value(G, s, t, capacity=capacity)
340
    H = nx.DiGraph(G)
341
    H.add_node(s, demand=-maxFlow)
342
    H.add_node(t, demand=maxFlow)
343
    return min_cost_flow(H, capacity=capacity, weight=weight)