8

opencv has an implementation of max-flow algorithm (class GCGRAPH in file gcgraph.hpp). It's available here.

Does anyone know which particular max-flow algorithm is implemented by this class?

Shai
  • 111,146
  • 38
  • 238
  • 371
  • @taocp I'm having trouble reading the algorithm from the implementation, as the implementation is more performance oriented than readability oriented – Shai Jun 20 '13 at 19:52
  • 1
    I'm trying to figure it out now, but this is the least-readable code I've seen in a while. Comment your code, folks! – templatetypedef Jun 20 '13 at 19:57

1 Answers1

9

I am not 100% confident about this, but I believe that the algorithm is based on this research paper describing max-flow algorithms for computer vision. Specifically, Section 3 describes a new algorithm for computing maximum flows.

I haven't lined up every detail of the paper's algorithm with the implementation of the algorithm, but many details seem to match:

  • The algorithm described works by using a bidirectional search from both s and t, which the implementation is doing as well: for example, there's a comment reading // grow S & T search trees, find an edge connecting them.
  • The algorithm described keeps track of a set of orphaned nodes, which the variable std::vector<Vtx*> orphans seems to track in the implementation.
  • The algorithm described works by building up a set of trees and reusing them; the algorithm implementation keeps track of a tree associated with each node.

I hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065