[Graph] Checking if a vertex_descriptor is valid
Hi, I want to check if a vertex_descriptor is valid before using it. As I saw on this list, I perform the following test : Graph_t graph(10); vertexDescriptor srcVertex = boost::vertex(424242, graph); if (Graph_t::null_vertex() == boost::vertex(424242, graph)) { return; } Obviously, vertex indice 424242 does not exist, but test fails, and function does not return, leading the a crash of the following algorithm (BFS or Dijkstra). What did I do wrong? Thanks for your help. -- Florian PONROY Thales Land & Joint France Tel. : +33(0)1 41 304 363 Fax : +33(0)1 41 303 560 Email : florian.ponroy@fr.thalesgroup.com
On Apr 1, 2009, at 6:19 AM, Florian.PONROY@fr.thalesgroup.com wrote:
Hi,
I want to check if a vertex_descriptor is valid before using it. As I saw on this list, I perform the following test :
Graph_t graph(10);
vertexDescriptor srcVertex = boost::vertex(424242, graph);
if (Graph_t::null_vertex() == boost::vertex(424242, graph)) { return; }
Obviously, vertex indice 424242 does not exist, but test fails, and function does not return, leading the a crash of the following algorithm (BFS or Dijkstra).
What did I do wrong?
Thanks for your help.
Hi, Florian. The call: boost::vertex(424242, graph); attempts to return the vertex_descriptor for the 424242 vertex in the graph, without validating that there in fact are 424242 in the graph. Here is the implementation for adjacency_list using a random access container for vertices (boost 1.37): template <class Graph, class Config, class Base> inline typename Config::vertex_descriptor vertex(typename Config::vertices_size_type n, const vec_adj_list_impl<Graph, Config, Base>&) { return n; } static vertex_descriptor null_vertex() { return (std::numeric_limits<vertex_descriptor>::max)(); } Here is the implementation for adjacency_list using a non-random access container for vertices: template <class Derived, class Config, class Base> inline typename Config::vertex_descriptor vertex(typename Config::vertices_size_type n, const adj_list_impl<Derived, Config, Base>& g_) { const Derived& g = static_cast<const Derived&>(g_); typename Config::vertex_iterator i = vertices(g).first; while (n--) ++i; // std::advance(i, n); (not VC++ portable) return *i; } static vertex_descriptor null_vertex() { return 0; } So in neither case are you likely to get back something equal to null_vertex() when you ask for the vertex_descriptor of the 424242th vertex in graph with 10 vertices. You could validate the index before calling boost::vertex() by checking that it falls in [0, num_vertices(g)). -- Michael
Obviously, vertex indice 424242 does not exist, but test fails, and function does not return, leading the a crash of the following algorithm (BFS or Dijkstra).
What did I do wrong?
Thanks for your help.
I would guess that the vertex() function is actually constructing a vertex object or descriptor - not actually trying to access the given vertex. You probably need to use the vertices() function to access the collection and then get the vertex that you need. Andrew Sutton andrew.n.sutton@gmail.com
participants (3)
-
Andrew Sutton
-
Florian.PONROY@fr.thalesgroup.com
-
Michael Olea