What algorithm opencv GCGRAPH (max flow) is based on?

Question

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?

Fungi

@taocp I'm having trouble reading the algorithm from the implementation, as the implementation is more performance oriented than readability oriented – Fungi

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! – Cynthiacynthie

Answer 1

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!

Cynthiacynthie