Re: [Boost-users] [Graph] Computing reachable vertices on a graph

Subject: Re: [Boost-users] [Graph] Computing reachable vertices on a graph
From: Florian.PONROY_at_[hidden]
Date: 2009-03-23 04:55:29

Hi Andrew,
 
Thank you very much for your reply. I eventually implemented Steven
Watanabe's solution, which seems easier to me. Since I only need to know
which nodes are actually reachable, I may get rid of distances for now.
 
Thanks again,
 
Florian

-----Message d'origine-----
De : boost-users-bounces_at_[hidden]
[mailto:boost-users-bounces_at_[hidden]]De la part de Andrew Sutton
Envoyé : vendredi 20 mars 2009 18:35
À : boost-users_at_[hidden]
Objet : Re: [Boost-users] [Graph] Computing reachable vertices on a graph

However, I encounter the following issue : in this example, vertices are
numbered from 0 to 5. However, in my project, this is not the case, vertices
could be numbered 5, 38, 42, 384... Using a vector in that case might not
work as expected, a map<vertex, distance> would probably be better. I'm not
quite familiar with BGL so far, maybe should I deal with a specific property
map? Or using a visitor to record a vertex distance upon graph discovery?
I'm a little bit lost, any help will be greatly appreciated!

You probably shouldn't rely on vertex indices as the canonical id of the
vertex. The method of identifying vertices (and edges) in an adjacency list
varies with the vertex set and edge set type selectors (indices or
identifeirs for vecS aren't the same as listS).

There are a couple of different approaches. The easiest would be to simply
maintain a mapping of id to vertex descriptor. For example:

map<int, graph_traits<Graph>::vertex_descriptor> verts;

verts[5] = add_vertex(g);
verts[58] = add_vertex(g);
// and so on. 

You can couple that bundled vertex properties to get a kind of bimap.

struct vertex_props { int id; }
typedef adj_list<vecS, vecS, directedS, vertex_props> Graph;

template <typename Graph, typename Map>
void add_vertex(Graph& g, Map& verts, int id) {
  vertex_descriptor v = add_vertex(g);
  verts[id] = v;
  g[v].id = id;
}

add_vertex(g, verts, 5);
add_vertex(g, verts, 58);
...
cout << g[*vertices(g).begin]->id << "\n";

Hope that helps,

Andrew Sutton
andrew.n.sutton_at_[hidden] <mailto:andrew.n.sutton_at_[hidden]>