Boost logo

Boost Users :

Subject: [Boost-users] [BGL] Edmund Karps works with long, but does not with doubles
From: Matthias Teich (matthias_teich_at_[hidden])
Date: 2008-11-16 04:03:37


I have some problems with the max-flow algorithms in the boost graph
The only algorithm that worked for me was edmund karps, but only when I use
long or int values as edge capacities.

Here is my graph:

typedef adjacency_list<listS, vecS, bidirectionalS, Node, Edge> Graph;
typedef graph_traits<Graph> Traits;
typedef Traits::vertex_iterator vertex_iter;
typedef graph_traits<Graph>::edge_iterator edge_iter;
typedef property_map<Graph, default_color_type Node::*>::type ColorMap;
typedef property_map<Graph, int Edge::*>::type CapacityMap;
typedef property_map<Graph, Graph::edge_descriptor Edge::*>::type
typedef property_map<Graph, Graph::edge_descriptor Node::*>::type
typedef property_map<Graph, CapacityMap::value_type Node::*>::type
typedef property_map<Graph, long Node::*>::type IndexMap;

struct Edge
        CapacityMap::value_type capacity;
        CapacityMap::value_type residual_capacity;
        Graph::edge_descriptor reverse;

struct Node
        Mesh::FaceHandle faceHandle;
        CapacityMap::value_type distance;
        long index;
        Traits::edge_descriptor predecessor;
        boost::default_color_type color;

Before calling edmund karps I add an edge with zero capacity to each
existing edge and set the reverse edges.

It would be very nice if anyone could give me a hint why this does not work.
The push relabel and the kolmogorov algorithm always return 0 as result :(

Best Regards,

View this message in context:
Sent from the Boost - Users mailing list archive at

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at