Successive Shortest Path for Min Cost Max Flow

Calculates the minimum cost maximum flow of a network with nonnegative edge weights using successive shortest path augmentation.

Complexity: O(U * (|E| + |V| log |V|)) for integer capacities with max flow U
Defined in: <boost/graph/successive_shortest_path_nonnegative_weights.hpp>

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/successive_shortest_path_nonnegative_weights.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;
    g[e].residual_capacity = 0;
    g[r].residual_capacity = 0;
}

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<Descriptor> pred(num_vertices(g));
    std::vector<int> dist(num_vertices(g));
    std::vector<int> dist2(num_vertices(g));

    successive_shortest_path_nonnegative_weights(g, Vertex(0), Vertex(3),
        cap, res, wgt, rev, idx,
        make_iterator_property_map(pred.begin(), idx),
        make_iterator_property_map(dist.begin(), idx),
        make_iterator_property_map(dist2.begin(), idx));

    std::cout << "Min cost: " << find_flow_cost(g, cap, res, wgt) << "\n";
}
Min cost: 10

(1) Positional version

template <class Graph, class Capacity, class ResidualCapacity,
          class Reversed, class Pred, class Weight,
          class Distance, class Distance2, class VertexIndex>
void successive_shortest_path_nonnegative_weights(
    const Graph& g,
    typename graph_traits<Graph>::vertex_descriptor s,
    typename graph_traits<Graph>::vertex_descriptor t,
    Capacity capacity,
    ResidualCapacity residual_capacity,
    Weight weight,
    Reversed rev,
    VertexIndex index,
    Pred pred,
    Distance distance,
    Distance2 distance_prev);
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

vertex_descriptor s

The source vertex for the flow network graph.

IN

vertex_descriptor t

The sink vertex for the flow network 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.

OUT

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 weights must all be non-negative, and the algorithm will throw a negative_edge exception if one of the edges is negative. 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.

IN

Reversed rev

An edge property map that maps every edge (u,v) in the graph to the reverse edge (v,u). The map must be a model of constant Lvalue Property Map. The key type of the map must be the graph’s edge descriptor type.

IN

VertexIndex index

Maps each vertex of the graph to a unique integer in the range [0, num_vertices(g)). The vertex index map must be a model of Readable Property Map. The key type of the map must be the graph’s vertex descriptor type.

UTIL

Pred pred

Used by the algorithm to store augmenting paths. The map must be a model of mutable Lvalue Property Map. The key type must be the graph’s vertex descriptor type and the value type must be the graph’s edge descriptor type.

UTIL

Distance distance

The shortest path weight from the source vertex s to each vertex in the graph g is recorded in this property map. The shortest path weight is the sum of the edge weights along the shortest path. The type Distance must be a model of Read/Write Property Map. The vertex descriptor type of the graph needs to be usable as the key type of the distance map.

UTIL

Distance2 distance_prev

The shortest path computation in iteration k uses distances computed in iteration k. The type Distance2 must be a model of Read/Write Property Map. The vertex descriptor type of the graph needs to be usable as the key type of the distance map.

(2) Named parameter version

template <class Graph, class P, class T, class R>
void successive_shortest_path_nonnegative_weights(
    Graph& g,
    typename graph_traits<Graph>::vertex_descriptor s,
    typename graph_traits<Graph>::vertex_descriptor t,
    const bgl_named_params<P, T, R>& params = all defaults);
Direction Parameter Description

IN

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

vertex_descriptor s

The source vertex for the flow network graph.

IN

vertex_descriptor t

The sink vertex for the flow network 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)

OUT

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

reverse_edge_map(ReverseEdgeMap rev)

An edge property map that maps every edge (u,v) in the graph to the reverse edge (v,u). The map must be a model of constant Lvalue Property Map. The key type of the map must be the graph’s edge descriptor type.
Default: get(edge_reverse, g)

IN

weight_map(WeightMap w_map)

The weight or "cost" of each edge in the graph. The weights must all be non-negative, and the algorithm will throw a negative_edge exception if one of the edges is negative. 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)

UTIL

predecessor_map(PredEdgeMap pred)

Used by the algorithm to store augmenting paths. The map must be a model of mutable Lvalue Property Map. The key type must be the graph’s vertex descriptor type and the value type must be the graph’s edge descriptor type.
Default: an iterator_property_map created from a std::vector of edge descriptors of size num_vertices(g) and using the i_map for the index map.

UTIL

distance_map(DistanceMap d_map)

The shortest path weight from the source vertex s to each vertex in the graph g is recorded in this property map. The shortest path weight is the sum of the edge weights along the shortest path. The type DistanceMap must be a model of Read/Write Property Map. The vertex descriptor type of the graph needs to be usable as the key type of the distance map.
Default: iterator_property_map created from a std::vector of the WeightMap’s value type of size `num_vertices(g) and using the i_map for the index map.

UTIL

distance_map2(DistanceMap2 d_map2)

The shortest path computation in iteration k uses distances computed in iteration k. The type DistanceMap2 must be a model of Read/Write Property Map. The vertex descriptor type of the graph needs to be usable as the key type of the distance map.
Default: iterator_property_map created from a std::vector of the WeightMap’s value type of size `num_vertices(g) and using the i_map for the index map.

IN

vertex_index_map(VertexIndexMap i_map)

Maps each vertex of the graph to a unique integer in the range [0, num_vertices(g)). This property map is only needed if the default for the distance or distance2 or predecessor map is used. The vertex index map must be a model of Readable Property Map. The key type of the map must be the graph’s vertex descriptor type.
Default: get(vertex_index, g). Note: if you use this default, make sure your graph has an internal vertex_index property. For example, adjacency_list with VertexList=listS does not have an internal vertex_index property.

Description

The successive_shortest_path_nonnegative_weights() function calculates the minimum cost maximum flow of a network. See Section Network Flow Algorithms for a description of maximum flow. The function calculates the flow values f(u,v) for all (u,v) in E, which are returned in the form of the residual capacity r(u,v) = c(u,v) - f(u,v).

There are several special requirements on the input graph and property map parameters for this algorithm. First, the directed graph G=(V,E) that represents the network must be augmented to include the reverse edge for every edge in E. That is, the input graph should be Gin = (V,{E U ET}). The ReverseEdgeMap argument rev must map each edge in the original graph to its reverse edge, that is (u,v) → (v,u) for all (u,v) in E. The CapacityEdgeMap argument cap must map each edge in E to a positive number, and each edge in ET to 0. The WeightMap has to map each edge from E to nonnegative number, and each edge from ET to -weight of its reversed edge.

The algorithm is described in Network Flows.

This algorithm starts with empty flow and in each round augments the shortest path (in terms of weight) in the residual graph.

In order to find the cost of the result flow use: find_flow_cost().

See also example/successive_shortest_path_nonnegative_weights_example.cpp for an additional example of using this algorithm.

Notes

The return type is void. The result of the algorithm is obtained through the residual capacity property map, which encodes the flow as r(u,v) = c(u,v) - f(u,v). To obtain the cost of the computed flow, use find_flow_cost().

Edit this Page