Re: [Boost-users] [BFL] Efficient neighbourhood search in trees

Subject: Re: [Boost-users] [BFL] Efficient neighbourhood search in trees
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-11-03 17:09:36

On Wed, 3 Nov 2010, Vincent Spruyt wrote:

> Hi all,
>
> I'm trying to calculate the average edge weight within a certain 
> neighbourhood for each vertex in a tree.
> Basically, I have a (minimum spanning) tree and I want to remove all edges 
> whose weight is much larger than the weight of edges closeby.
> The result would be a forrest of several connected components (I'm working on 
> a clustering algorithm).
>
> Currently I naively iterate over each edge. For each edge, I find the source 
> and target vertex. Then, for both the source and the target vertices, I 
> calculate the average weight in a certain neighbourhood using a recursive 
> function as following simplified pseudocode indicates:
>
>
> E: List of edges in MST
>
> getNeighbourhoodStats( depth, startvertex, edge ){
>
>  out_edges = getIncedentEdges(startvertex)
>
>  foreach out_edges as out
>     if( out!=edge){
>        totweight += getWeight(out);
>
>        if(depth>0)
>           getNeighbourhoodStats(depth-1, target(out), out)
>
>     }
>     end
> }
>
> main(){
>  foreach E as e
>
>     //Get the total weight on the left of the edge
>     int totweight_left=0;
>     getNeighbourhoodStats( 5, source( e), E, totweight_left )
>
>     //Get the total weight on the right of the edge
>     int totweight_right=0;
>     getNeighbourhoodStats( 5, target( e), E, totweight_right )
>     end
> }
>
> However, this approach is rather inefficient as a lot of calculations are 
> redundant (takes about 10ms for 300 edges which is way too slow for the 
> purpose I had in mind).
> Any ideas for a better solution?

I would suggest using dynamic programming.  Keep a map from <vertex, 
depth> to total weight.  First, fill in <v, 0> with zero for all v, then 
recursively fill in <v, n+1> with the sum of <w, n> for all neighbors w of 
each v.  This will not exclude the edge you're currently testing from the 
sum, though.

-- Jeremiah Willcock