Re: [Boost-users] [EXTERNAL] [BGL] [push_relabel_max_flow]

Subject: Re: [Boost-users] [EXTERNAL] [BGL] [push_relabel_max_flow]
From: Pablo Madoery (madoerypablo_at_[hidden])
Date: 2014-11-19 10:54:57

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_at_[hidden]>
wrote:

> Hi Pablo,
>
> On Nov 18, 2014, at 8:41 AM, Pablo Madoery <madoerypablo_at_[hidden]> 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_at_[hidden]
> > http://lists.boost.org/mailman/listinfo.cgi/boost-users
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>