什么算法opencv GCGRAPH(最大流量)基于？

Question

opencv有一个max-flow算法的实现(GCGRAPH文件gcgraph.hpp中的类).它可以在这里找到.

有谁知道这个类实现了哪种特定的max-flow算法？

Answer 1

我对此并不是100%有信心,但我相信该算法是基于这篇描述计算机视觉最大流算法的研究论文.具体而言,第3节描述了一种用于计算最大流量的新算法.

我没有通过算法的实现排列论文算法的每个细节,但许多细节似乎匹配:

• 所描述的算法通过使用来自s和t的双向搜索来工作,实现也在这样做:例如,有一个注释读数// grow S & T search trees, find an edge connecting them.
• 所描述的算法跟踪一组孤立节点,该变量std::vector<Vtx*> orphans似乎在实现中跟踪.
• 所描述的算法通过构建一组树并重用它们来工作; 算法实现跟踪与每个节点相关联的树.

我希望这有帮助!