最終更新日時: 2017年04月29日 15時27分05秒
E Kawashima が更新

edmunds_karp_max_flow

// 名前付きパラメータバージョン
template <class VertexListGraph, class P, class T, class R>
typename detail::edge_capacity_value<VertexListGraph, P, T, R>::value_type
edmunds_karp_max_flow(VertexListGraph& g, 
   typename graph_traits<VertexListGraph>::vertex_descriptor src,
   typename graph_traits<VertexListGraph>::vertex_descriptor sink,
   const bgl_named_params<P, T, R>& params = all defaults)

// 名前無しパラメータバージョン
template <class VertexListGraph, 
      class CapacityEdgeMap, class ResidualCapacityEdgeMap,
      class ReverseEdgeMap, class ColorMap, class PredEdgeMap>
typename property_traits<CapacityEdgeMap>::value_type
edmunds_karp_max_flow(VertexListGraph& g, 
   typename graph_traits<Graph>::vertex_descriptor src,
   typename graph_traits<Graph>::vertex_descriptor sink,
   CapacityEdgeMap cap, ResidualCapacityEdgeMap res, ReverseEdgeMap rev, 
   ColorMap color, PredEdgeMap pred)

edmunds_karp_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) を含むために増やされなければならない。換言すれば、入力グラフは G_in = (V,{E U ET}) であるべきである。ReverseEdgeMap 引数 rev は元のグラフ中の各辺をその逆辺にマップしなければならない。すなわち E 中の全ての (u,v) に対して (u,v) -> (v,u) である。CapacityEdgeMap 引数 cap は E 中の各辺を正の数にマップしなければならず、E^T 中の各辺は 0 にされなければならない。

このアルゴリズムは Edmonds and Karp に負っている。もっとも Network Flows に述べられている「ラベリング・アルゴリズム」と呼ばれる亜種を使っているが。

このアルゴリズムは、最大流問題を実装するための大変単純で容易な解答である。しかしながら、このアルゴリズムが push_relabel_max_flow() アルゴリズムほどには良くないいくつかの理由がある。

非整数の容量の場合、時間計算量は最疎グラフを除く全てのグラフにとって push-relabel アルゴリズムの O(V²E^1/2) より悪い O(V E²) である。
整数の容量の場合、もし容量の範囲 U が大変大きいならば、アルゴリズムに長い時間がかかるだろう。

定義場所

boost/graph/edmunds_karp_max_flow.hpp

パラメータ

IN: VertexListGraph& g
- 有向グラフ。グラフの型は VertexListGraph のモデルでなければならない。グラフ中の各辺 (u,v) のために、逆辺 (v,u) もまたグラフ中になければならない。
IN: vertex_descriptor src
- 流れのネットワーク・グラフのためのソース頂点。
IN: vertex_descriptor sink
- 流れのネットワーク・グラフのためのシンク頂点。

名前付きパラメータ

IN: capacity_map(CapacityEdgeMap 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)
UTIL: color_map(ColorMap color)
- 幅優先探索の段階の間、進行過程を保持するためにアルゴリズムによって使われる。アルゴリズムの終了時に、白色の頂点は最小カット集合を定義する。マップは Lvalue Property Map のモデルでなければならない。マップのキー型はグラフの頂点記述子型であるべきで、値型は ColorValue のモデルでなければならない。
- デフォルト: サイズ num_vertices(g) の default_color_type の std::vector から作られた iterator_property_mapで、添え字マップには i_map を用いる。
UTIL: predecessor_map(PredEdgeMap pred)
- 増大した道を格納するためにアルゴリズムによって使われる。マップは変更可能の Lvalue Property Map でなければならない。キー型はグラフの頂点記述子型であるべきで、値型はグラフの辺記述子型でなければならない。
- デフォルト: サイズ num_vertices(g) の辺記述子の std::vector から作られた iterator_property_mapで、添え字マップには i_map を用いる。
IN: vertex_index_map(VertexIndexMap i_map)
- グラフの各頂点を [0, num_vertices(g)) の範囲において唯一の整数にマップしなさい。このプロパティ・マップはカラー・マップまたは先行点マップのためにデフォルトが使われた時にのみ必要である。頂点添え字マップは Readable Property Map のモデルでなければならない。マップのキー型はグラフの頂点記述子型でなければならない。
- デフォルト: get(vertex_index, g)

計算量

時間計算量は、通常の場合には O(V E²) で、もしくは容量値が定数 U で範囲づけられた整数であるならば O(V E U) である。

コード例

examples/edmunds-karp-eg.cpp 中のプログラムは最大流問題の例 (辺容量を伴うグラフ) を DIMACS 形式で書かれたファイルから読み、最大流を計算する。

edmunds_karp_max_flow

定義場所

パラメータ

名前付きパラメータ

計算量

コード例

関連項目