This documentation is being rewritten. If something looks off, please cross-check with the Boost 1.91.0 Boost.Graph docs and open an issue.

find_flow_cost

Calculates the cost of a network flow from edge flow values and edge weights.

Complexity: O(|E|)
Defined in: <boost/graph/find_flow_cost.hpp>

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <boost/graph/find_flow_cost.hpp>
#include <iostream>
#include <vector>

using namespace boost;

using Traits = adjacency_list_traits<vecS, vecS, directedS>;
struct Edge {
    int capacity;
    int residual_capacity;
    int weight;
    Traits::edge_descriptor reverse;
};

using Graph = adjacency_list<vecS, vecS, directedS, no_property, Edge>;
using Descriptor = graph_traits<Graph>::edge_descriptor;
using Vertex = graph_traits<Graph>::vertex_descriptor;

void add_edge_pair(Graph& g, int u, int v, int cap, int cost) {
    Descriptor e = add_edge(u, v, g).first;
    Descriptor r = add_edge(v, u, g).first;
    g[e].capacity = cap;  g[r].capacity = 0;
    g[e].weight = cost;   g[r].weight = -cost;
    g[e].reverse = r;     g[r].reverse = e;
}

int main() {
    Graph g(4);
    add_edge_pair(g, 0, 1, 2, 1);
    add_edge_pair(g, 0, 2, 1, 3);
    add_edge_pair(g, 1, 3, 2, 2);
    add_edge_pair(g, 2, 3, 3, 1);

    auto cap = get(&Edge::capacity, g);
    auto res = get(&Edge::residual_capacity, g);
    auto wgt = get(&Edge::weight, g);
    auto rev = get(&Edge::reverse, g);
    auto idx = get(vertex_index, g);

    std::vector<default_color_type> color(num_vertices(g));
    std::vector<Descriptor> pred(num_vertices(g));

    edmonds_karp_max_flow(g, Vertex(0), Vertex(3), cap, res, rev,
        make_iterator_property_map(color.begin(), idx),
        make_iterator_property_map(pred.begin(), idx));

    // 4-arg positional form of find_flow_cost.
    int cost = find_flow_cost(g, cap, res, wgt);
    std::cout << "Flow cost: " << cost << "\n";
}
Flow cost: 10

(1) Positional 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);
Direction Parameter Description

IN

const Graph& g

A directed graph. The graph’s type must be a model of Vertex List Graph and Incidence Graph. For each edge (u,v) in the graph, the reverse edge (v,u) must also be in the graph.

IN

Capacity capacity

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.

IN

ResidualCapacity residual_capacity

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.

IN

Weight weight

The weight or "cost" of each edge in the graph. The type Weight 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.

(2) 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);
Direction Parameter Description

IN

const Graph& g

A directed graph. The graph’s type must be a model of Vertex List Graph and Incidence Graph. For each edge (u,v) in the graph, the reverse edge (v,u) must also be in the graph.

IN

params

Named parameters passed via bgl_named_params. The following are accepted:
Direction Named Parameter Description / Default

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)

Description

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().

Returns

The cost of the network flow, whose type is typename property_traits<typename property_map<Graph, edge_capacity_t>::type>::value_type.

Edit this Page