[BGL] [push_relabel_max_flow]
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
Hi Pablo, On Nov 18, 2014, at 8:41 AM, Pablo Madoery <madoerypablo@gmail.com> wrote:
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 ?.
I can reproduce this failure with clang on the develop branch. Can you submit a bug in trac for this issue so it doesn’t get lost? Thanks. — Noel Belcourt
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 _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hi, I have submitted it as a bug ticket in : https://svn.boost.org/trac/boost/ticket/10805 Thanks On Tue, Nov 18, 2014 at 4:13 PM, Belcourt, Kenneth <kbelco@sandia.gov> wrote:
Hi Pablo,
On Nov 18, 2014, at 8:41 AM, Pablo Madoery <madoerypablo@gmail.com> wrote:
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 ?.
I can reproduce this failure with clang on the develop branch. Can you submit a bug in trac for this issue so it doesn’t get lost?
Thanks.
— Noel Belcourt
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 _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (1)
-
Belcourt, Kenneth -
Pablo Madoery