Boost Graph Library: Find Flow Cost

# `find_flow_cost`

    // named parameter version
    template <class Graph>
    typename property_traits<typename property_map < Graph, edge_capacity_t >::type>::value_type
    find_flow_cost(const Graph & g,
            const bgl_named_params<P, T, R> & params  = all defaults)

    // non-named parameter version
    template<class Graph, class Capacity, class ResidualCapacity, class Weight>
    typename property_traits<typename property_map < Graph, edge_capacity_t >::type>::value_type
    find_flow_cost(const Graph & g, Capacity capacity, ResidualCapacity residual_capacity, Weight weight)

The `find_flow_cost()` function calculates the minimum cost maximum flow value of a network and given flow. See Section Network Flow Algorithms for a description of maximum flow. The function calculates the cost from the flow values f(u,v) for (u,v) in E, which are passed in the form of the residual capacity r(u,v) = c(u,v) - f(u,v).

In order to compute the min cost max flow use : `successive_shortest_path_nonnegative_weights()` or `cycle_canceling()`.

### Where Defined

`boost/graph/successive_shortest_path_nonnegative_weights.hpp`

### Parameters

IN: `const Graph& g`

> A directed graph. The graph's type must be a model of VertexListGraph and IncidenceGraph For each edge (u,v) in the graph, the reverse edge (v,u) must also be in the graph.

### Named Parameters

IN: `capacity_map(CapacityEdgeMap cap)`

> The edge capacity property map. The type must be a model of a constant Lvalue Property Map. The key type of the map must be the graph's edge descriptor type.
> Default: `get(edge_capacity, g)`

IN: `residual_capacity_map(ResidualCapacityEdgeMap res)`

> This maps edges to their residual capacity. The type must be a model of a mutable Lvalue Property Map. The key type of the map must be the graph's edge descriptor type.
> Default: `get(edge_residual_capacity, g)`

IN: `weight_map(WeightMap w_map)`

> The weight or ``cost'' of each edge in the graph. The type `WeightMap` must be a model of Readable Property Map. The edge descriptor type of the graph needs to be usable as the key type for the weight map. The value type for this map must be the same as the value type of the distance map.
> Default: `get(edge_weight, g)`

### Complexity

The complexity is O(|E|),

### Example

The function is used in the successive_shortest_path_nonnegative_weights example. The program in `example/successive_shortest_path_nonnegative_weights_example.cpp`.

### See Also

`cycle_canceling()`
`successive_shortest_path_nonnegative_weights()`.

Copyright © 2013 | Piotr Wygocki, University of Warsaw (wygos at mimuw.edu.pl)