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

On Thu, November 04, Simonon Lucanus J wrote:

...

On Wed, 3 Nov 2010, Jeremiah Willcock wrote:

...

On Wed, 3 Nov 2010, Jeremiah Willcock wrote:

...

On Wed, 3 Nov 2010, Vincent Spruyt wrote:

[...] 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: [...] 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?

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

He said it was a tree so there shouldn't be multiple paths from any vertex to another vertex in its neighborhood. You should be able to accumulate total weight from the bottom up traversal of the topological order starting at the leaves. Then do the reverse topological order and sum the two. Don't count your own weight twice. Store total weight as a vector indexed by depth and shift of the last element then merge vectors of out edges and add your own weight at the beginning of the vector for each node as you traverse up the tree. Delete the vectors on the out edges as you go up to save memory. [...]

Thank you both for your responses. I eventually decided to use the naive approach anyway. Actually, I did implement a dynamic programming version of the algorithm, but tracking the weight of the 'depth' neighbouring edges and merging them when paths come together actually slows down the method a lot. In the end, the dynamic programming based implementation of the algorithm is faster than the naive whan if a depth of more than 130 is used because it is linear in complexity. However, in my application I only need a depth of 5 or something in which case the naive approach is way faster. Actually, the naive implementation does what I need in about 0.7ms and not the 10ms I reported earlier. The 9.3ms difference here is only because I used a filtered_graph as a view into a larger graph... which obviously was not a good idea :) So just copying the tree into a new graph and then naively solving the problem seems to be the best solution here. Kind regards, Vincent