Hi
Juan,
Thanks
for your answer. I definitly agree with the map overhead, I will try to better
understand how the property map works in order to implement your
solution.
Florian
Hi,
It's as easy as instantiating the
adjacency_list template with mapS for the vertex list selector.
This is the
second template argument.
For example,
typedef
boost::adjacency_list<boost::vecS,boost::mapS> myGraph;
Anyway,
remember that a map is more expensive than a vector in terms of both space and
time (access time to an element is logarithmic).
Another option is that you
stay with the default vector for the vertex list, and you use a property to
store the vertex id.
This way, your vertex 4242 would have descriptor 6 and
you'd store 4242 as its id-property value.
Cheers,
Juan
>
Hi Andrew,
>
> Would you please tell me which part of the
documentation I should rely on to use a std::map as you'd suggested? I should
actually admit I'm not yet
> familiar with the BGL :-)
>
>
> -----Message d'origine-----
>
De :
boost-users-bounces@lists.boost.org
[mailto:boost-users-bounces@lists.boost.org]De la part de Andrew
Sutton
> Envoyé : mercredi 25 mars 2009 17:25
> À :
boost-users@lists.boost.org
> Objet : Re: [Boost-users] [Graph]
Adjacency list scalability with a Dijkstra algorithm
>
>
>
>
> Here is the problem: I would have imagined that, in my
case,
> boost::num_vertices(graph) would have returned 6, but it
actually returns
> the higher vertex number + 1, that is... 4243 ! So
each of my vector has a
> size of 4243 * sizeof(tVertex) bytes... Is
there a way to handle that? I
> probably misuse the API, but it would be
better if the container would be
> dimensioned to the actual number of
vertices, since I am in a CPU and memory
> constraint
environment...
>
>
>
> You're confusing the notions
of "index" and "descriptor". With the vertex set using vecS, the descriptor of
a vertex is the same as its index --
> hence the confusion. Therefore,
when you call add_edge(4242, 1, ...), the graph thinks you mean the vertex
whose descriptor is 4242 and resizes
> itself accordingly.
>
> You have to remember - whatever the examples may indicate - that you
should never actually use a literal value and descriptors interchangeably.
This
> isn't documented very well, either.
>
> You could
use a std::map to associate your own identifiers with vertex
descriptors.
>
>
> Andrew Sutton
>
andrew.n.sutton@gmail.com <mailto:andrew.n.sutton@gmail.com>
>
>
> _______________________________________________
>
Boost-users mailing list
> Boost-users@lists.boost.org
>
http://lists.boost.org/mailman/listinfo.cgi/boost-users