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

3 Nov 2010


      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  to total weight.  First, fill in  with zero for all v, then 
recursively fill in  with the sum of  for all neighbors w of 
each v.  This will not exclude the edge you're currently testing from the 
sum, though.

-- Jeremiah Willcock