On Apr 4, 2006, at 3:02 PM, Seweryn Habdank-Wojewódzki wrote:

Hi!

Did any one check how to get neighbourhood of the node from given graph with respect to the properties or connections?

Like in example below:

V = { 1, 2, 3, 4, 5 }; E = { (1,2), (2,5), (5,4), (2,4), (1,4), (1,3), (3,4) };

So if there is no property, let assume that we are interesting in searching neighbourhood level 1 of point 1 we will have {1,2,3,4} level 2 {1,2,3,4,5}, but neighbourhood level 1 of point 4 is {1,2,3,4,5}. Of course I am interesting in copying proper edges too.

If we have numerical properties on edges we could define (as on all problems with paths) that distance between node A and B is a sum of properties between them. And if we set adjacent matrix as

0 1 3 2 0 1 0 0 1 1 3 0 0 2 0 2 1 2 0 2 0 1 0 2 0

Than neighbourhood of level (or in that case "distance") 1 of point 1 is {1,2} level 2 {1,2,4,5}, and for point 4 level 1 {2,4}.

The question is. If algorithms "breadth_first_*" will give me all functionality for that or not?

You can definitely use breadth_first_search/breadth_first_visit to compute the neighborhood out to some number of levels, just by keeping track of the distance from the source (initialized to zero) to each other vertex. For instance, the distance_recorder visitor marks the levels of each vertex: http://www.boost.org/libs/graph/doc/distance_recorder.html Doug