Thank you for your replies. 2010/2/7 Andrew Sutton

...

...

std::pair< graph_traits<Graph>::edge_descriptor, bool > p = add_edge (*vertices(g).first, *vertices(g).second, g);

The function vertices returns an iterator range. In my understanding an iterator range is a pair of iterators [first, second) so that second can be reached from first with increment operations, _but_ is not part of the iterator range itself. It could be an iterator like one returned by the end-function of a stl-vector. It shall not be dereferenced!

I'll also add that adjacency_list with vecS as a vertex set will add vertices in add_edge if an invalid vertex descriptor is given -- of which vertices(g).second is an invalid itetator. It's equivalent to end(vertices(g)) if you're using Boost.Range.

I understand. Obviously, dereferencing a past the end iterator is a bad idea. I am now facing another problem using kolmogorov_max_flow algorithm. Here is the code: #include <iostream> #include <vector> using namespace std; #include #include using namespace boost; typedef adjacency_list_traits < vecS, vecS, directedS > Traits; typedef adjacency_list < vecS, vecS, directedS, property < vertex_index_t, long, property < vertex_color_t, boost::default_color_type, property < vertex_distance_t, long, property < vertex_potential_t, long, // stores the unary energy associated to each vertex property < vertex_predecessor_t, Traits::edge_descriptor > > > > >, property < edge_capacity_t, long, // stores the binary energy associated to each edge property < edge_residual_capacity_t, long, property < edge_reverse_t, Traits::edge_descriptor > > > > Graph; int main(int argc, char** argv) { Graph g; property_map::type capacity = get(edge_capacity, g); property_map::type rev = get(edge_reverse, g); graph_traits<Graph>::vertex_iterator v_first, v_second, v_third; v_first = vertices(g).first; v_second = v_first; ++v_second; v_third = v_second; ++v_third; std::pair< graph_traits<Graph>::edge_descriptor, bool > p = add_edge(*v_first, *v_second, g); capacity[p.first] = 10; std::pair< graph_traits<Graph>::edge_descriptor, bool > p_reverse = add_edge(*v_second, *v_first, g); rev[p.first] = p_reverse.first; capacity[p_reverse.first] = -10; std::pair< graph_traits<Graph>::edge_descriptor, bool > p2 = add_edge(*v_second, *v_third, g); capacity[p2.first] = 11; std::pair< graph_traits<Graph>::edge_descriptor, bool > p2_reverse = add_edge(*v_third, *v_second, g); rev[p2.first] = p2_reverse.first; capacity[p2_reverse.first] = -11; std::cout << "num_vertices = " << num_vertices(g) << std::endl; std::cout << "num_edges = " << num_edges(g) << std::endl; long flow = kolmogorov_max_flow(g , *v_first, *v_third); std::cout << "flow = " << flow << std::endl; return 0; } The code below crashes (segfault) in the max_flow() function. Could you tell me what am I doing wrong ? It seems to work when I set a capacity capacity[p2.first] with a value smaller than 10 (capacity[p.first]). Am I missing something? Do I correctly use the reverse property_map? Hope you could help. Regards, Olivier

Andrew Sutton andrew.n.sutton@gmail.com

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

Hi Andrew, 2010/2/8 Andrew Sutton

The code below crashes (segfault) in the max_flow() function. Could you

...

tell me what am I doing wrong ? It seems to work when I set a capacity capacity[p2.first] with a value smaller than 10 (capacity[p.first]). Am I missing something? Do I correctly use the reverse property_map?

Where precisely does it crash?

Here is the backtrace from gdb (sorry ...). Eric, no I did not forget to add vertices in my graph. It is build in another function that I removed for clarity. I have 333 vertices in my graph, and 4 edges. Do I correctly use the edge_reverse property_map? Regards, Olivier Program received signal SIGSEGV, Segmentation fault. #0 0x08075839 in boost::detail::kolmogorov, boost::no_property> > > > >, boost::property, boost::no_property> > >, boost::no_property, boost::listS>, boost::adj_list_edge_property_map, boost::no_property> > > const, boost::edge_capacity_t>, boost::adj_list_edge_property_map, boost::no_property> > >, boost::edge_residual_capacity_t>, boost::adj_list_edge_property_map, boost::detail::edge_desc_impl const&, unsigned int, boost::property, boost::no_property> > > const, boost::edge_reverse_t>, boost::vec_adj_list_vertex_property_map, boost::no_property> > > > >, boost::property, boost::no_property> > >, boost::no_property, boost::listS>, boost::adjacency_list, boost::no_property> > > > >, boost::property, boost::no_property> > >, boost::no_property, boost::listS>*, boost::detail::edge_desc_impl, boost::detail::edge_desc_impl&, boost::vertex_predecessor_t>, boost::vec_adj_list_vertex_property_map, boost::no_property> > > > >, boost::property, boost::no_property> > >, boost::no_property, boost::listS>, boost::adjacency_list, boost::no_property> > > > >, boost::property, boost::no_property> > >, boost::no_property, boost::listS>*, boost::default_color_type, boost::default_color_type&, boost::vertex_color_t>, boost::vec_adj_list_vertex_property_map, boost::no_property> > > > >, boost::property, boost::no_property> > >, boost::no_property, boost::listS>, boost::adjacency_list, boost::no_property> > > > >, boost::property, boost::no_property> > >, boost::no_property, boost::listS>*, long, long&, boost::vertex_distance_t>, boost::vec_adj_list_vertex_id_map, boost::no_property> > > > >, unsigned int> >::max_flow() () #1 0x08063fab in main ()

Andrew Sutton andrew.n.sutton@gmail.com

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

Andrew, 2010/2/8 Andrew Sutton

Here is the backtrace from gdb (sorry ...). Eric, no I did not forget to

...

add vertices in my graph. It is build in another function that I removed for clarity. I have 333 vertices in my graph, and 4 edges. Do I correctly use the edge_reverse property_map?

Can you pin down a line number?

Sorry for my previous message. Enabling debug flags, I had a better idea of the problem: /usr/include/boost/graph/kolmogorov_max_flow.hpp:115: [...] Assertion `m_rev_edge_map[m_rev_edge_map[*ei]] == *ei' failed. So, I add in my code: rev[p_reverse.first] = p.first; // ... rev[p2_reverse.first] = p2.first; It seems now to work correctly. Thanks for your help. Regards, Olivier

Andrew Sutton andrew.n.sutton@gmail.com

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users