Re: [Boost-users] [BGL] Neighbourhood as a subgraph.

From: Doug Gregor (dgregor_at_[hidden])
Date: 2006-04-10 16:00:49

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