[boost] [BGL] [push_relabel_max_flow]

Subject: [boost] [BGL] [push_relabel_max_flow]
From: Pablo Madoery (madoerypablo_at_[hidden])
Date: 2014-11-18 10:41:06

Hello, I am having trouble using the push_relabel_max_flow algorithm when i
put std::numeric_limits<double>::max() as capacity attribute in some edges.
is there a maximum value that I can use as capacities. which ?.

This is the example I am using :

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/push_relabel_max_flow.hpp>
#include <boost/graph/graphviz.hpp>

using namespace std;
using namespace boost;

struct vertexInfo
{

};

struct edgeInfo
{
double capacity;
double residualCapacity;
double flow;
adjacency_list_traits<vecS, vecS, bidirectionalS>::edge_descriptor rev;

edgeInfo()
{
residualCapacity = 1000;
}
};

typedef adjacency_list<vecS, vecS, bidirectionalS, vertexInfo, edgeInfo>
Graph;
typedef Graph::edge_descriptor edge_d;

const char* names[] =
{ "SV", "L1", "L2", "L3", "L4", "ET"};

template<typename Vertex>
void create_edge(Graph& g, Vertex v0, Vertex v1, double capacity)
{
//the algorithm requires that for each edge u-v in the graph, the edge v-u
also exists
Graph::edge_descriptor ep0 = (add_edge(v0, v1, g)).first;
Graph::edge_descriptor ep1 = (add_edge(v1, v0, g)).first;
g[ep0].capacity = capacity;
g[ep0].rev = ep1;
g[ep1].capacity = 0; // the capacity of v-u needs to be 0
g[ep1].rev = ep0;
}

int main()
{
Graph graph;

Graph::vertex_descriptor SV = add_vertex(graph);
Graph::vertex_descriptor L1 = add_vertex(graph);
Graph::vertex_descriptor L2 = add_vertex(graph);
Graph::vertex_descriptor L3 = add_vertex(graph);
Graph::vertex_descriptor L4 = add_vertex(graph);
Graph::vertex_descriptor ET = add_vertex(graph);

create_edge(graph, SV, L1, std::numeric_limits<double>::max());
create_edge(graph, SV, L2, std::numeric_limits<double>::max());
create_edge(graph, SV, L3, std::numeric_limits<double>::max());
create_edge(graph, SV, L4, std::numeric_limits<double>::max());

create_edge(graph, L3, ET, 1000);

create_edge(graph, L4, L3, 1000);
create_edge(graph, L2, L3, 1000);
create_edge(graph, L1, L2, 1000);

// arcos de vuelta
create_edge(graph, L3, L4, 1000);
create_edge(graph, L3, L2, 1000);
create_edge(graph, L2, L1, 1000);

std::cout << "Max flow: "
<< push_relabel_max_flow(graph, SV, ET, get(&edgeInfo::capacity, graph),
get(&edgeInfo::residualCapacity, graph),
get(&edgeInfo::rev, graph), get(boost::vertex_index, graph)) << std::endl;

graph_traits<Graph>::vertex_iterator vi, vi_end;
graph_traits<Graph>::out_edge_iterator ei, ei_end;

cout.precision(20);
for (tie(vi, vi_end) = vertices(graph); vi!= vi_end; ++vi)
{
for (tie(ei, ei_end) = out_edges(*vi, graph); ei != ei_end; ++ei)
{
graph[*ei].flow = graph[*ei].capacity - graph[*ei].residualCapacity;

if (graph[*ei].capacity > 0)
{
std::cout << names[*vi] << " " << names[target(*ei, graph)] << " "
<< (graph[*ei].capacity - graph[*ei].residualCapacity) << "/" <<
graph[*ei].capacity << std::endl;
}
}
}

cout<<"end"<<endl;
return 0;
}

-----------------------------------------------------------------------------------------------------------------------------
And this is the exception:

/home/madoery/boost_1_55_0/boost/graph/push_relabel_max_flow.hpp:706:
typename boost::property_traits<CapacityEdgeMap>::value_type
boost::push_relabel_max_flow(Graph&, typename
boost::graph_traits<Graph>::vertex_descriptor, typename
boost::graph_traits<Graph>::vertex_descriptor, CapacityEdgeMap,
ResidualCapacityEdgeMap, ReverseEdgeMap, VertexIndexMap) [with Graph =
boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS,
vertexInfo, edgeInfo>, CapacityEdgeMap =
boost::adj_list_edge_property_map<boost::bidirectional_tag, double,
double&, long unsigned int, edgeInfo, double edgeInfo::*>,
ResidualCapacityEdgeMap =
boost::adj_list_edge_property_map<boost::bidirectional_tag, double,
double&, long unsigned int, edgeInfo, double edgeInfo::*>, ReverseEdgeMap =
boost::adj_list_edge_property_map<boost::bidirectional_tag,
boost::detail::edge_desc_impl<boost::bidirectional_tag, long unsigned int>,
boost::detail::edge_desc_impl<boost::bidirectional_tag, long unsigned
int>&, long unsigned int, edgeInfo,
boost::detail::edge_desc_impl<boost::bidirectional_tag, long unsigned int>
edgeInfo::*>, VertexIndexMap =
boost::vec_adj_list_vertex_id_map<vertexInfo, long unsigned int>, typename
boost::property_traits<CapacityEdgeMap>::value_type = double, typename
boost::graph_traits<Graph>::vertex_descriptor = long unsigned int]:
Assertion `algo.is_flow()' failed.

Thank You