# `push_relabel_max_flow`

    // 名前付きパラメータバージョン
    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)

    // 名前無しパラメータバージョン
    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()` 関数はネットワークの最大流を計算する。 最大流の記述のために章 Network Flow Algorithms を見なさい。計算された最大流が関数の返却値になるだろう。 関数はさらに E 中の全ての (u,v) のために流量 f(u,v) を 計算する。そしてそれは残差容量 r(u,v) = c(u,v) - f(u,v) の形で 返される。

このアルゴリズムのために入力グラフとプロパティ・マップのパラメータに いくつかの特別な必要条件がある。最初に、ネットワークを表す有向グラフ G=(V,E) は E 中の各辺のための逆辺 (reverse edge) を含むために 増やされなければならない。換言すれば、入力グラフは Gin = (V,{E U ET}) であるべきである。 `ReverseEdgeMap` 引数 `rev` は元のグラフ中の各辺をその逆辺に マップしなければならない。すなわち E 中の全ての (u,v) に対して (u,v) -> (v,u) である。`CapacityEdgeMap` 引数 `cap` は E 中の各辺を正の数にマップしなければならず、ET 中の 各辺は 0 にされなければならない。

このアルゴリズムは Goldberg によって開発された。

### Where Defined

`boost/graph/preflow_push_max_flow.hpp`

### Parameters

IN: `VertexListGraph& g`

> 有向グラフ。グラフの型は Vertex List Graph のモデルでなければなら ない。グラフ中の各辺 (u,v) のために、逆辺 (v,u) もまた グラフ中になければならない。

IN: `vertex_descriptor src`

> 流れのネットワーク・グラフのためのソース頂点。

IN: `vertex_descriptor sink`

> 流れのネットワーク・グラフのためのシンク頂点。

### Named Parameters

IN: `capacity_map(EdgeCapacityMap cap)`

> 辺容量プロパティ・マップ。型は定数 Lvalue Property Map のモデルでなければならない。マップのキー型はグラフの辺記述子型でなければなら ない。
> デフォルト: `get(edge_capacity, g)`

OUT: `residual_capacity_map(ResidualCapacityEdgeMap res)`

> 辺残差容量プロパティ・マップ。型は変更可能の Lvalue Property Map のモデルでなければならない。マップのキー型はグラフの辺記述子型でなければなら ない。
> デフォルト: `get(edge_residual_capacity, g)`

IN: `reverse_edge_map(ReverseEdgeMap rev)`

> グラフ中の全ての辺 (u,v) を逆辺 (v,u) にマップする辺プロパティ・ マップ。マップは定数 Lvalue Property Map のモデルでなければならない。マップのキー型はグラフの辺記述子型でなければなら ない。
> デフォルト: `get(edge_reverse, g)`

IN: `vertex_index_map(VertexIndexMap index_map)`

> グラフの各頂点を `[0, num_vertices(g))` の範囲において唯一の整数に マップしなさい。マップは定数 LvaluePropertyMap のモデルでなければならない。マップのキー型はグラフの頂点記述子型でなければなら ない。
> デフォルト: `get(vertex_index, g)`

### Example

これは DIMACS 形式のファイルから最大流問題 (辺容量を伴うグラフ) の例を読み込む。この例のソースは `example/max_flow.cpp` にある。

    #include <boost/config.hpp>
    #include <iostream>
    #include <string>
    #include <boost/graph/push_relabel_map_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 (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
        for (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;
    }

The output is:

    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

### See Also

`edmunds_karp_max_flow()`.

Copyright © 2000-2001 | Jeremy Siek, Indiana University (jsiek@osl.iu.edu)

Japanese Translation Copyright © 2003 Takashi Itou
オリジナルの、及びこの著作権表示が全ての複製の中に現れる限り、この文書の複製、利用、変更、販売そして配布を認める。このドキュメントは「あるがまま」に提供されており、いかなる明示的、暗黙的保証も行わない。また、いかなる目的に対しても、その利用が適していることを関知しない。

このドキュメントの対象: Boost Version 1.30.0
最新版ドキュメント (英語)