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

[Florian...@fr.thalesgroup.com]

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...@fr.thalesgroup.com

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

[Michael Olea]

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

[Andrew Sutton]

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....@gmail.com