Re: [Boost-users] dijkstra_shortest_paths and vertex_index

From: Cromwell Enage (sponage_at_[hidden])
Date: 2004-10-16 00:12:43

Hello, Steve.

--- Steve Buchko <stevebu_at_[hidden]> wrote:
> I understand that when using listS to define
> vertices for a graph, I must also assign values to
> vertex_index before attempting to make use of
> dijkstra_shortest_paths.

You must assign a value to each vertex in the map a la

  put(get(vertex_index(), graph), vertex, value);

> My question is, do the values assigned to
> vertex_index need to be sequential (i.e. 0 to n
> where n is the number of vertices in the graph), or
> can I assign any "random" integer to each
> vertex_index, as long as the values assigned are
> unique for each node?

The mapping must be 1-to-1, the values must range from
0 to n so that the priority queue it uses internally
will function correctly, and the following
relationship must hold:

  get(get(vertex_index(), graph), vertex(value,
graph)) == value;

> Does dijkstra_shortest_paths simply use the
> vertex_index as a unique identifier for the vertex,
> or is it using those indices to build an internal
> data structure such as an array or vector ... in
> which case using relatively large (or
> non-sequential) integers for vertex_index might be
> prohibitive from a memory or performance viewpoint?

Like I said before, dijkstra_shortest_paths builds a
priority queue (actually a boost::mutable_queue)
internally, wrapped around a std::vector.  No idea
about memory footprint, but as for performance, I have
observed that dijkstra_shortest_paths does run slower
when listS is chosen over vecS as the VertexList.

                              HTH,
                              Cromwell Enage

                
_______________________________
Do you Yahoo!?
Declare Yourself - Register online to vote today!
http://vote.yahoo.com