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

Subject: [Boost-users] [BFL] Efficient neighbourhood search in trees
From: Vincent Spruyt (v.spruyt_at_[hidden])
Date: 2010-11-03 11:00:31

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?

Tnx a lot,

Kind regards,
Vincent