Re: [Boost-users] Iterater for subset extraction?

From: Thom DeCarlo (t.r.decarlo_at_[hidden])
Date: 2006-11-09 11:04:48

> -----Original Message-----
> From: Stephan Diederich
> 
> Hi Thom,
> 
> 2006/11/8, Thom DeCarlo <t.r.decarlo_at_[hidden]>:
> > I have a couple of n00b questions. I have constructed a BGL graph that
> > uses the edge_name_t property to road names. I want to change the
> > weights of some of the roads based on input from the user. Is there a
> > way to set up an iterator to step through edges that have names which
> > match elements of a set? (e.g., "A,B,B1,L,M")
> >
> > In a related question, I need to extract a vertex whose vertex_index_t
> > value matches a specific value. The vertices were not entered in any
> > specific order, so the "vertex(1, g)" function returns the first vertex
> > to have been entered into the graph, but not necessarily the one whose
> > index value is "1".
> 
> If I don't get you wrong, there's no direct way in the BGL to do that.
> The properties you attach to a vertex or an edge are normally accessed
> through the edge or vertex descriptor respectively.
> What you want to do is the other way around. Get from a property to
> the edge desciptor(s)  that match that property or in the case of
> vertex_index to the vertex descriptor.
> Maybe you can use Bimap (http://tinyurl.com/y95qng), where you can get
> keys (edge/vertex-descriptors) from values together with the concept
> of exterior property maps (http://tinyurl.com/yhju58) and Constructing
> an Exterior Property Map.
> 
> Reading further in the Bimap docs, I think I found what you want:
> http://tinyurl.com/yxzpme
> 
> HTH,
> Stephan

Well, once I figure out how to use it, I've found the Filter Iterator
(http://www.boost.org/libs/iterator/doc/filter_iterator.html) which may
solve the first part of my problem.

For the second part, I'm not sure exactly what you mean. Let me describe the
problem a bit more. Each vertex has an internal property that I've created:

// define a struct for the vertex coordinate properties
typedef struct vCoord
{
    double Lon; //degrees
    double Lat; //degrees
    double Alt; //meters above WGS84 ellipsoid
} Coord;

The user will provide a specific coordinate for his starting and ending
points and a preferred route of street names. I need to traverse the BGL
graph to find the vertex nearest the user's coordinate that is also on the
route. (Initially, I thought I was going to give each vertex a name and the
user would provide that name, hence the search for a specific vertex index
value. But, it is more likely that the user will know his position than the
neighborhood of road names.)

I think the filter iterator will also help with this problem. At least it
will let me narrow down the number of vertices that need to be compared when
searching for the closest one.

Does this sound reasonable?

Thanks,
Thom