[BGL] add_edge also adds a vertex
Hi all, I am facing a problem with BGL. Here is a minimal piece of code which reproduces the problem 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<Graph, edge_capacity_t>::type capacity = get(edge_capacity, g); //property_map<Graph, edge_reverse_t>::type rev = get(edge_reverse, g); add_vertex(g); add_vertex(g); std::pair< graph_traits<Graph>::edge_descriptor, bool > p = add_edge(*vertices(g).first, *vertices(g).second, g); std::pair< graph_traits<Graph>::edge_descriptor, bool > p_reverse = add_edge(*vertices(g).second, *vertices(g).first, g); std::cout << "num_vertices = " << num_vertices(g) << std::endl; // output: 3!!!! std::cout << "num_edges = " << num_edges(g) << std::endl; // output: 2 long flow = kolmogorov_max_flow(g , *vertices(g).first, *vertices(g).second); // crashes ... return 0; } So, I add 2 vertices in my graph, insert 2 edges between these vertices, and I finally have 3 vertices in my graph. What am I doing wrong? I am on a 32 bit Ubuntu box, with g++ 4.3.4 and boost 1.40 Best regards, Olivier ----------------------------------------------------- Olivier Tournaire MATIS - Institut Géographique National 73, Ave de Paris 94165 St Mandé cedex, France tel: (+33) 1 43 98 84 29 fax: (+33) 1 43 98 85 81
Hi Olivier, please post an example, which compiles. For example with all necessary #include directives. Olivier Tournaire <olitour@gmail.com> writes:
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! Therefore If I alter your code to read the following, everything is ok. #include <iostream> #include <boost/property_map/property_map.hpp> #include <boost/graph/graph_concepts.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/kolmogorov_max_flow.hpp> 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<Graph, edge_capacity_t>::type capacity = get(edge_capacity, //g); //property_map<Graph, edge_reverse_t>::type rev = get(edge_reverse, g); add_vertex(g); add_vertex(g); graph_traits<Graph>::vertex_iterator v_first, v_second; v_first = vertices(g).first; v_second = v_first; ++v_second; std::pair< graph_traits<Graph>::edge_descriptor, bool > p = add_edge (*v_first, *v_second, g); std::pair< graph_traits<Graph>::edge_descriptor, bool > p_reverse = add_edge(*v_second, *v_first, g); std::cout << "num_vertices = " << num_vertices(g) << std::endl; // output: //3!!!! std::cout << "num_edges = " << num_edges(g) << std::endl; // output: 2 return 0; } Yours sincerely, Eric
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. Andrew Sutton andrew.n.sutton@gmail.com
Thank you for your replies. 2010/2/7 Andrew Sutton <andrew.n.sutton@gmail.com>
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 <boost/graph/kolmogorov_max_flow.hpp> #include <boost/graph/adjacency_list.hpp> 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<Graph, edge_capacity_t>::type capacity = get(edge_capacity, g); property_map<Graph, edge_reverse_t>::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
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? Andrew Sutton andrew.n.sutton@gmail.com
Hi Andrew, 2010/2/8 Andrew Sutton <andrew.n.sutton@gmail.com>
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::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_index_t, long, boost::property<boost::vertex_color_t, boost::default_color_type, boost::property<boost::vertex_distance_t, long, boost::property<boost::vertex_potential_t, long, boost::property<boost::vertex_predecessor_t, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, boost::no_property> > > > >, boost::property<boost::edge_capacity_t, long, boost::property<boost::edge_residual_capacity_t, long, boost::property<boost::edge_reverse_t, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, boost::no_property> > >, boost::no_property, boost::listS>, boost::adj_list_edge_property_map<boost::directed_tag, long, long const&, unsigned int, boost::property<boost::edge_capacity_t, long, boost::property<boost::edge_residual_capacity_t, long, boost::property<boost::edge_reverse_t, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, boost::no_property> > > const, boost::edge_capacity_t>, boost::adj_list_edge_property_map<boost::directed_tag, long, long&, unsigned int, boost::property<boost::edge_capacity_t, long, boost::property<boost::edge_residual_capacity_t, long, boost::property<boost::edge_reverse_t, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, boost::no_property> > >, boost::edge_residual_capacity_t>, boost::adj_list_edge_property_map<boost::directed_tag, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int> const&, unsigned int, boost::property<boost::edge_capacity_t, long, boost::property<boost::edge_residual_capacity_t, long, boost::property<boost::edge_reverse_t, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, boost::no_property> > > const, boost::edge_reverse_t>, boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_index_t, long, boost::property<boost::vertex_color_t, boost::default_color_type, boost::property<boost::vertex_distance_t, long, boost::property<boost::vertex_potential_t, long, boost::property<boost::vertex_predecessor_t, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, boost::no_property> > > > >, boost::property<boost::edge_capacity_t, long, boost::property<boost::edge_residual_capacity_t, long, boost::property<boost::edge_reverse_t, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, boost::no_property> > >, boost::no_property, boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_index_t, long, boost::property<boost::vertex_color_t, boost::default_color_type, boost::property<boost::vertex_distance_t, long, boost::property<boost::vertex_potential_t, long, boost::property<boost::vertex_predecessor_t, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, boost::no_property> > > > >, boost::property<boost::edge_capacity_t, long, boost::property<boost::edge_residual_capacity_t, long, boost::property<boost::edge_reverse_t, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, boost::no_property> > >, boost::no_property, boost::listS>*, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>&, boost::vertex_predecessor_t>, boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_index_t, long, boost::property<boost::vertex_color_t, boost::default_color_type, boost::property<boost::vertex_distance_t, long, boost::property<boost::vertex_potential_t, long, boost::property<boost::vertex_predecessor_t, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, boost::no_property> > > > >, boost::property<boost::edge_capacity_t, long, boost::property<boost::edge_residual_capacity_t, long, boost::property<boost::---Type <return> to continue, or q <return> to quit--- edge_reverse_t, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, boost::no_property> > >, boost::no_property, boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_index_t, long, boost::property<boost::vertex_color_t, boost::default_color_type, boost::property<boost::vertex_distance_t, long, boost::property<boost::vertex_potential_t, long, boost::property<boost::vertex_predecessor_t, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, boost::no_property> > > > >, boost::property<boost::edge_capacity_t, long, boost::property<boost::edge_residual_capacity_t, long, boost::property<boost::edge_reverse_t, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, 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::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_index_t, long, boost::property<boost::vertex_color_t, boost::default_color_type, boost::property<boost::vertex_distance_t, long, boost::property<boost::vertex_potential_t, long, boost::property<boost::vertex_predecessor_t, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, boost::no_property> > > > >, boost::property<boost::edge_capacity_t, long, boost::property<boost::edge_residual_capacity_t, long, boost::property<boost::edge_reverse_t, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, boost::no_property> > >, boost::no_property, boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_index_t, long, boost::property<boost::vertex_color_t, boost::default_color_type, boost::property<boost::vertex_distance_t, long, boost::property<boost::vertex_potential_t, long, boost::property<boost::vertex_predecessor_t, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, boost::no_property> > > > >, boost::property<boost::edge_capacity_t, long, boost::property<boost::edge_residual_capacity_t, long, boost::property<boost::edge_reverse_t, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, boost::no_property> > >, boost::no_property, boost::listS>*, long, long&, boost::vertex_distance_t>, boost::vec_adj_list_vertex_id_map<boost::property<boost::vertex_index_t, long, boost::property<boost::vertex_color_t, boost::default_color_type, boost::property<boost::vertex_distance_t, long, boost::property<boost::vertex_potential_t, long, boost::property<boost::vertex_predecessor_t, boost::detail::edge_desc_impl<boost::directed_tag, unsigned int>, 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
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? Andrew Sutton andrew.n.sutton@gmail.com
Andrew, 2010/2/8 Andrew Sutton <andrew.n.sutton@gmail.com>
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
Hi Olivier, Olivier Tournaire <olitour@gmail.com> writes:
Here is the code:
#include <iostream> #include <vector> using namespace std;
#include <boost/graph/kolmogorov_max_flow.hpp> #include <boost/graph/adjacency_list.hpp> 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<Graph, edge_capacity_t>::type capacity = get(edge_capacity, g); property_map<Graph, edge_reverse_t>::type rev = get(edge_reverse, g);
add_vertex(g); add_vertex(g); add_vertex(g); or so ...
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;
Did you forget to add a few vertices before calling vertices(g) ? Eric
participants (4)
-
Andrew Sutton -
Eric Wolf -
eric＠boese-wolf.eu
-
Olivier Tournaire