[Ruby] フォード・ファルカーソン法でネットワークの最大フローを求める

フォード・ファルカーソンのアルゴリズム で、ネットワークの最大フローを算出してみます。

最大フローとは

以下のようなそうめん流しシステム(=ネットワーク)があるとします。

• 「→」は「竹とい」を示します。「○」は、「竹とい」の接点。
• 「→」の横の数値は、1分間に転送可能なそうめんの量を表します。

このシステムで、「1分間に 任意の二点間(例: a→f) に転送可能な最大そうめん量」が「最大フロー」となります。

ネットワークのデータ構造

例によって、構築と探索に必要な最低限の機能のみ用意。

• Networkは、頂点(Vertex)と、頂点と頂点を結ぶ辺(edge)を持ちます。
• 各辺は「capacity」フィールドで最大転送量を持ちます。
• 各頂点は、頂点から出る辺(=edge.fromが頂点の辺 =前進辺)の集合(forward)と、頂点に入る辺(=edge.toが頂点の辺 =後退辺)の集合(backward)をそれぞれ持ちます。
  • フォード・ファルカーソンのアルゴリズム では、ネットワークを逆順にたどる場合があるため、両方を保持しています。

# ネットワーク
class Network
 
  def initialize
    @serial = 0
    @vertices = []
    @edges = []
  end

  def connect( from, to, capacity )
    assert_vertex_exist from
    assert_vertex_exist to
    edge = Edge.new( from, to, capacity )
    @vertices[from].connect_to( edge )
    @vertices[to].connect_from( edge )
    @edges << edge
  end
 
  def add_vertex( data )
    id = @serial
    @serial += 1
    @vertices[id] = Vertex.new( id, data, self )
    return id
  end

  def inspect
    return "---\n" + vertices.collect {|v| v.inspect }.join("\n")
  end
 
  attr_reader :vertices, :edges
 
private
  def assert_vertex_exist( id )
    if ( id < 0 || id >= @vertices.length || !@vertices[id] )
      raise "vertex not exist. id=#{id}"
    end
  end
 
end

# 頂点
class Vertex
  def initialize( id, data, graph )
    @id = id
    @data = data
    @graph = graph
    @forward = []
    @backward = []
  end
  def connect_to( edge )
    @forward.push( edge )
  end
  def connect_from( edge )
    @backward.push( edge )
  end
  def inspect
    return "#{@id}:#{@data.inspect}\n" + @forward.collect{|e|
        "  -> #{@graph.vertices[e.to].data.inspect} : #{e.capacity}"
      }.join("\n")
  end
  attr_reader :id, :data, :forward, :backward
end

# 辺。不変です。
class Edge
  def initialize( from, to, capacity )
    @from = from
    @to = to
    @capacity = capacity
  end
  def inspect
    return "#{from} -> #{to} : #{capacity}"
  end
  attr_reader :to, :from, :capacity
end

↑のそうめん流しシステムは、以下のコードで表現できます。

network = Network.new

ids = []
('a'..'f').each{|i|
  ids << network.add_vertex( i )
}
network.connect(ids[0], ids[1], 3)
network.connect(ids[0], ids[2], 2)
network.connect(ids[1], ids[3], 2)
network.connect(ids[1], ids[4], 2)
network.connect(ids[2], ids[3], 2)
network.connect(ids[2], ids[4], 3)
network.connect(ids[3], ids[5], 3)
network.connect(ids[4], ids[5], 2)

最大フローを求める

フォード・ファルカーソンのアルゴリズム では、開始位置から終了位置に到達可能な空きのあるパス(=増加道:augmenting path と呼ばれます)を、パスがなくなるまでひたすら探索することで、最大フローを算出します。

• 大雑把な流れ
  1. パス(増加道)を探索します。
  2. 1.でパスがあれば
     1. パスに流せる最大転送量(=パスを構成する辺の残り転送量のうち、最小の値)を算出します。
     2. 算出した転送量を、各辺の「利用済み転送量」としてマークします。
     3. 1.に戻り、他にパスがないか探索を継続します。
  3. パスがなければ、計算は終了です。
• パス(増加道)の探索
  1. 開始位置から辺を順にたどり、終了位置までの経路を探します。
  2. ただし、すでに転送量を使い切ったパスは利用不可として除外します。
  3. また、探索時には前進辺だけでなく後進辺も探索します。
     • これは、以下のような状態になった場合に、「a → b → e →後進→ c → d → f」のパスを発見するために必要な操作です。
     • 
     • 「→」の横の数値のうち、分母はパスの最大転送量、分子は利用済み転送量を示します。
     • ここで、パス「a → b → e →後進→ c → d → f」は、
       • c → d → f ルートで、cからfまでの転送は可能。
       • a → b → e ルートで、aからeまでの転送は可能。
       • c → e のデータを c → d にまわすことでc → d → f でまだ転送できますよ。
       • eの不足分は、a → b → e ルートで転送すればよいよ。
       • ということを示す有効な増加道になります。
     • 
       • 後進辺は、利用済み転送量のキャンセル操作が必要であるため、マーク時の扱いも変わります。

というようなことをするクラスは以下。

# フォード・ファルカーソンアルゴリズム でネットワークの最大フローを算出する。
class MaxFlow
  
  def initialize( network )
    @network = network
  end
  
  # from から to への最大フローを計算する
  def compute( from, to )
    initialize_state
    while ( path = find_augmenting_path( from, to ))
      process_path( path )
    end
    return self
  end
  
  # 最大転送時の各辺の利用量を取得する
  def used( edge )
    @used[edge]
  end
  
private

  # 状態を初期化する
  def initialize_state
    @used = Hash.new(0)
  end
  
  # 転送容量が残っている経路を探索し、from から to へ到達可能なパスがあればそれを返す。
  # なければnilを返す。
  def find_augmenting_path( current, to, visited={} )
    visited[current] = true
    vertex = @network.vertices[current]
    vertex.forward.each {|e|
      if ( !visited[e.to] && used(e) < e.capacity )
        if ( e.to == to )
          path = []
        else
          path = find_augmenting_path( e.to, to, visited )
        end
        if path
          path.unshift({ :edge => e, :forward? => true } )
          return path
        end
      end
    }
    vertex.backward.each {|e|
      if ( !visited[e.from] && used(e) > 0 )
        path = find_augmenting_path( e.from, to, visited )
        if path 
          path.unshift({ :edge => e, :forward? => false } )
          return path
        end
      end
    }
    visited[current] = false
    return nil
  end
  
  # パスを処理して、利用転送量を再計算する
  def process_path( path )
    flow = path.collect{|step|
      e = step[:edge]
      step[:forward?] ? e.capacity - used(e) : used(e)
    }.min
    path.each{|step|
      e = step[:edge]
      if ( step[:forward?] ) 
        @used[e] += flow 
      else
        @used[e] -= flow 
      end
    }
  end
  
end

冒頭のそうめん流しシステムであれば、以下の流れで最大フローが算出されます。

• 1.初期状態

• 2.パス [ a → b → d → f ] のパスがヒット。
  • 「b → d」の残量に引っ張られる形で、このパスの転送量は2となります。2を各辺の利用済み転送量としてマーク。

• 3.パス [ a → b → e → f ] のパスがヒット。
  • 「a → b」の残量に引っ張られる形で、このパスの転送量は1となります。1を各辺の利用済み転送量としてマーク。

• 4.パス [ a → c → d → f ] のパスがヒット。
  • 「d → f」の残量に引っ張られる形で、このパスの転送量は1となります。1を各辺の利用済み転送量としてマーク。

• 5.パス [ a → c → d →後退→ b → e → f ] のパスがヒット。
  • 「e → f」「a → c」の残量が1なので、このパスの転送量は1となります。1を各辺の利用済み転送量としてマーク。「d → b」の転送量は-1されます。

• 6.パスがないので処理は完了。

max_flow = MaxFlow.new(network).compute(ids[0],ids[5])
network.edges.each {|edge|
  puts "#{network.vertices[edge.from].data} -> #{network.vertices[edge.to].data}" \
       + ": #{max_flow.used(edge)}/#{edge.capacity}"
}

実行結果は以下。最大転送時の各辺の「利用転送量/最大転送量」です。

a -> b: 3/3
a -> c: 2/2
b -> d: 1/2
b -> e: 2/2
c -> d: 2/2
c -> e: 0/3
d -> f: 3/3
e -> f: 2/2

「a → b,c」「d,e → f」 あたりがネックですね。