push_relabel_max_flow

// named parameter version
template <class Graph, class P, class T, class R>
typename property_traits<CapacityEdgeMap>::value_type
push_relabel_max_flow(Graph& g,
   typename graph_traits<Graph>::vertex_descriptor src,
   typename graph_traits<Graph>::vertex_descriptor sink,
   const bgl_named_params<P, T, R>& params = all defaults)

// non-named parameter version
template <class Graph,
	  class CapacityEdgeMap, class ResidualCapacityEdgeMap,
	  class ReverseEdgeMap, class VertexIndexMap>
typename property_traits<CapacityEdgeMap>::value_type
push_relabel_max_flow(Graph& g,
   typename graph_traits<Graph>::vertex_descriptor src,
   typename graph_traits<Graph>::vertex_descriptor sink,
   CapacityEdgeMap cap, ResidualCapacityEdgeMap res,
   ReverseEdgeMap rev, VertexIndexMap index_map)

push_relabel_max_flow() 函数计算网络的最大流。参见 网络流算法 章节以获取最大流的描述。计算出的最大流将作为函数的返回值。该函数还计算所有 (u,v) 在 E 中的流量值 f(u,v)，这些值以剩余容量 r(u,v) = c(u,v) - f(u,v) 的形式返回。

对于此算法的输入图和属性映射参数，有几个特殊要求。首先，表示网络的有向图 G=(V,E) 必须被扩充，以包含 E 中每条边的反向边。也就是说，输入图应为 G_in = (V,{E U E^T})。 反向边映射参数rev必须将原始图中的每条边映射到其反向边，即对于所有 (u,v) 在 E 中，(u,v) -> (v,u)。容量边映射参数cap必须将 E 中的每条边映射到一个正数，并将 E^T 中的每条边映射到 0。

此算法由 Goldberg 开发。

复杂度

定义位置

boost/graph/push_relabel_max_flow.hpp

参数

一个有向图。该图的类型必须是 Vertex List Graph 的模型。对于图中的每条边 (u,v)，反向边 (v,u) 也必须在图中。

流网络图的源顶点。

流网络图的汇聚顶点。

命名参数

边容量属性映射。该类型必须是常量 Lvalue Property Map 的模型。映射的键类型必须是图的边描述符类型。
默认 get(edge_capacity, g)

边剩余容量属性映射。该类型必须是可变 Lvalue Property Map 的模型。映射的键类型必须是图的边描述符类型。
默认 get(edge_residual_capacity, g)

一个边属性映射，将图中的每条边 (u,v) 映射到反向边 (v,u)。该映射必须是常量 Lvalue Property Map 的模型。映射的键类型必须是图的边描述符类型。
默认 get(edge_reverse, g)

将图的每个顶点映射到范围内的唯一整数[0, num_vertices(g))。该映射必须是常量 LvaluePropertyMap 的模型。映射的键类型必须是图的顶点描述符类型。
默认 get(vertex_index, g)注意：如果您使用此默认值，请确保您的图具有内部vertex_index属性。例如，adjacency_list使用VertexList=listS不具有内部vertex_index属性。

示例

#include <boost/config.hpp>
#include <iostream>
#include <string>
#include <boost/graph/push_relabel_max_flow.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/read_dimacs.hpp>

int
main()
{
  using namespace boost;

  typedef adjacency_list_traits<vecS, vecS, directedS> Traits;
  typedef adjacency_list<vecS, vecS, directedS,
    property<vertex_name_t, std::string>,
    property<edge_capacity_t, long,
      property<edge_residual_capacity_t, long,
	property<edge_reverse_t, Traits::edge_descriptor> > >
  > Graph;

  Graph g;
  long flow;

  property_map<Graph, edge_capacity_t>::type
    capacity = get(edge_capacity, g);
  property_map<Graph, edge_reverse_t>::type
    rev = get(edge_reverse, g);
  property_map<Graph, edge_residual_capacity_t>::type
    residual_capacity = get(edge_residual_capacity, g);

  Traits::vertex_descriptor s, t;
  read_dimacs_max_flow(g, capacity, rev, s, t);

  flow = push_relabel_max_flow(g, s, t);

  std::cout << "c  The total flow:" << std::endl;
  std::cout << "s " << flow << std::endl << std::endl;

  std::cout << "c flow values:" << std::endl;
  graph_traits<Graph>::vertex_iterator u_iter, u_end;
  graph_traits<Graph>::out_edge_iterator ei, e_end;
  for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
    for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
      if (capacity[*ei] > 0)
        std::cout << "f " << *u_iter << " " << target(*ei, g) << " "
                  << (capacity[*ei] - residual_capacity[*ei]) << std::endl;
  return 0;
}

c  The total flow:
s 4

c flow values:
f 0 1 4
f 1 2 4
f 2 3 2
f 2 4 2
f 3 1 0
f 3 6 2
f 4 5 3
f 5 6 0
f 5 7 3
f 6 4 1
f 6 7 1

参见