Re: [Boost-users] [Graph] Checking if a vertex_descriptor is valid

Subject: Re: [Boost-users] [Graph] Checking if a vertex_descriptor is valid
From: Michael Olea (oleaj_at_[hidden])
Date: 2009-04-01 13:29:20

On Apr 1, 2009, at 6:19 AM, Florian.PONROY_at_[hidden] 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