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:18:18

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 <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.

The way I suggested can also counting some edge weights multiple times, so 
the update formula may need to be <v, n+1> = sum(w in neighbors(v), <w, 
n>) - degree(v) * <v, n-1> or something like that.  You might want to do 
some small examples by hand to make sure you get the formula right.

-- Jeremiah Willcock