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

3 Nov 2010


      On Wed, 3 Nov 2010, Jeremiah Willcock wrote:
...
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.
The way I suggested can also counting some edge weights multiple times, so 
the update formula may need to be  = sum(w in neighbors(v), ) - degree(v) *  or something like that.  You might want to do 
some small examples by hand to make sure you get the formula right.

-- Jeremiah Willcock