Re: [Boost-users] [BGL] Edmund Karps works with long, but does not with doubles

Subject: Re: [Boost-users] [BGL] Edmund Karps works with long, but does not with doubles
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2008-11-17 16:14:55

>
> I have some problems with the max-flow algorithms in the boost graph
> library.
> 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
> ReverseEdgeMap;
> typedef property_map<Graph, Graph::edge_descriptor Node::*>::type
> PredecessorMap;
> typedef property_map<Graph, CapacityMap::value_type Node::*>::type
> DistanceMap;
> 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 :(
>

I'm not entirely sure why you'd be getting the results that you are, but it
looks like you might be working to hard to define some of your types.
Specifically, you shouldn't be defining the capacity and residual capacity
in terms of the CapacityMap type. Just use int or float, and then bind the
map to that type. Also, you shouldn't rely on Graph to define
edge_descriptor. For example:

struct EdgeProp
{
  int capacity;
  int residual;
  graph_traits<Graph>::edge_descriptor reverse;
};

Are you getting any compiler errors?

Andrew Sutton
andrew.n.sutton_at_[hidden]