Re: [Boost-users] [Graph] Adjacency list scalability with a Dijks tra algorithm
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>
Hi Andrew,
Would you please tell me which
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 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
participants (2)
-
Florian.PONROY＠fr.thalesgroup.com -
Juan Antonio Farré Basurte