...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

// named parameter versiontemplate <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)// non-named parameter versiontemplate <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)

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 *G _{in} = (V,{E U
E^{T}})*. The

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

`boost/graph/successive_shortest_path_nonnegative_weights.hpp`

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

The source vertex for the flow network graph.IN:

The sink vertex for the flow network graph.

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:

Default:get(edge_capacity, g)

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:

Default:get(edge_residual_capacity, g)

An edge property map that maps every edgeIN:(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)

The weight or ``cost'' of each edge in the graph. The weights must all be non-negative, and the algorithm will throw aUTIL:negative_edgeexception if one of the edges is negative. The typeWeightMapmust 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)

Use 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:

Default:aniterator_property_mapcreated from astd::vectorof edge descriptors of sizenum_vertices(g)and using thei_mapfor the index map.

The shortest path weight from the source vertexUTIL:sto each vertex in the graphgis recorded in this property map. The shortest path weight is the sum of the edge weights along the shortest path. The typeDistanceMapmust 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_mapcreated from astd::vectorof theWeightMap's value type of sizenum_vertices(g)and using thei_mapfor the index map.

The shortest path computation in iteration nrIN:kuses distances computed in iterationk. The typeDistanceMap2must 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_mapcreated from astd::vectorof theWeightMap's value type of sizenum_vertices(g)and using thei_mapfor the index 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 internalvertex_indexproperty. For example,adjacenty_listwithVertexList=listSdoes not have an internalvertex_indexproperty.

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