Na czym oparty jest algorytm opencv GCGRAPH (maksymalny przepływ)?

Question

opencv ma implementację algorytmu max-flow (klasa GCGRAPH w pliku gcgraph.hpp). To jest available here.

Czy ktoś wie, który algorytm maksymalnego przepływu jest zaimplementowany przez tę klasę?

Answer 1

Nie jestem w 100% pewny, ale uważam, że algorytm jest oparty na this research paper describing max-flow algorithms for computer vision. W szczególności sekcja 3 opisuje nowy algorytm obliczania maksymalnych przepływów.

nie ustawiły się każdy szczegół algorytm gazety z realizacji algorytmu, ale wiele szczegółów wydaje się dopasować:

• Algorytm opisany prace przy użyciu dwukierunkowego wyszukiwanie z obu S oraz T , które implementacja również wykonuje: na przykład istnieje komentarz do czytania // grow S & T search trees, find an edge connecting them.
• Opisany algorytm śledzi zbiór osieroconych węzłów, który wydaje się śledzić w trakcie implementacji zmiennej std::vector<Vtx*> orphans.
• Opisany algorytm działa poprzez budowanie zestawu drzew i ich ponowne wykorzystanie; implementacja algorytmu śledzi drzewo powiązane z każdym węzłem.

Mam nadzieję, że to pomoże!