Welchen Algorithmus opencv GCGRAPH (max Fluss) basiert auf?

opencv hat eine Implementierung des Max-Flow-Algorithmus (Klasse GCGRAPH in der Datei gcgraph.hpp). Es ist available here.Welchen Algorithmus opencv GCGRAPH (max Fluss) basiert auf?

Weiß jemand, welcher spezielle Max-Flow-Algorithmus von dieser Klasse implementiert wird?

Quelle

2013-06-20 Shai

@aocp Ich habe Probleme beim Lesen des Algorithmus aus der Implementierung, da die Implementierung leistungsorientierter als Lesbarkeit orientiert ist – Shai

@templatetypedef - danke für den Link – Shai

Ich versuche es jetzt herauszufinden, aber das ist die am wenigsten lesbaren Code, den ich seit einer Weile gesehen habe. Kommentiere deinen Code, Leute! – templatetypedef

Ich bin nicht 100% zuversichtlich, aber ich glaube, dass der Algorithmus auf basiert. Insbesondere beschreibt Abschnitt 3 einen neuen Algorithmus zum Berechnen maximaler Flüsse.

Ich habe nicht jedes Detail des Papiers Algorithmus mit der Implementierung des Algorithmus, aber viele Details scheinen aufgereiht zum Spiel:

Der Algorithmus funktioniert beschrieben unter Verwendung einer bidirektionalen Suche von beiden s und t , was auch die Implementierung tut: Es gibt zum Beispiel einen Kommentar // grow S & T search trees, find an edge connecting them.
Der beschriebene Algorithmus verfolgt eine Reihe von verwaisten Knoten, die die Variable std::vector<Vtx*> orphans in der Implementierung zu verfolgen scheint.
Der beschriebene Algorithmus funktioniert, indem eine Reihe von Bäumen aufgebaut und wiederverwendet wird; Die Algorithmusimplementierung verfolgt einen Baum, der jedem Knoten zugeordnet ist.

Ich hoffe, das hilft!

Quelle

2013-06-20 20:06:21 templatetypedef

Dies ist eine große Hilfe! Danke. – Shai

Welchen Algorithmus opencv GCGRAPH (max Fluss) basiert auf?

Antwort

Verwandte Themen