Эдмонд Карпс в Boost Graph Library - PullRequest
Новая
       17

Эдмонд Карпс в Boost Graph Library

4 голосов
/ 16 февраля 2012

Часть моего алгоритма требует вычисления максимального потока в сети с целочисленной пропускной способностью.Я хочу использовать алгоритм boost :: edmonds_karp_max_flow, чтобы найти максимальный поток.

Я пытался читать документацию, но это было очень трудно для меня, так как я никогда раньше не использовал BGL.Я создал график следующим образом, где атрибут веса Edge должен использоваться в качестве емкости ребер на графике.

struct Vertex{
    int id;
    bool flag;
};
struct Edge{
    int weight;
};
 typedef boost::adjacency_list<  
    boost::listS,               
    boost::vecS,                
    boost::undirectedS,         
    Vertex,                     
    Edge                        
 >MyGraph;

Моя цель - написать следующую функцию 

 int max_flow( const MyGraph& gr, int u, int v) {
       // compute the maximum flow between vertices with ids u,v
 }

Может кто-нибудь показать мне пример того, как реализовать эту функцию?

...