Boost logo

Boost Users :

From: Stephan Diederich (stephan.diederich_at_[hidden])
Date: 2006-11-12 18:09:27


Hi Thom,

> 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.

The filter iterator can be used, if you want to iterate over all of
your container (linear time), and extract "on the fly" only those
values you are interested in.
With your edge_name_t example, you can take an iterator to the edges,
and a predicate which extracts the edge name from the edge-property
and compares those names to the list of searched streets. But still,
this is a linear time operation.

The other way would be to have a map of street-names, which maps to
the edge_descriptors in your graph (if the edge_name_t is attached to
you edges). In this map you can search (e.g. map::find) in logarithmic
time.(But only with starting letters)
To summarize:
In BGL, you have properties attached to edges/vertices. To access
them, you have to specify the {vertex,edge}descriptor.
In your case, if I understand your problem, you want to specify the
street-name (or part of it) to get the descriptor (and therefrom use
the BGL to get to the next street, and so on)

That's why I came up with Bimap. It provides both ways.

>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.)

The case with you vertex properties is quite different. To find the
next vertex to the specified vertex you need to calculate a distance
value (e.g. euclidian). If you don't want to check all vertices
against your initial coordinates, you need a data structure which
limits the search space for you, e.g. a simple grid.

>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.

Hm, how are you going to do this?

Cheers,
Stephan


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net