Calculation error in maximum spanning tree

[cre185]

When applying your codebase to my works, I discovered a problem within glomap/math/tree.cc. I think there's something wrong with this MaximumSpanningTree (mst) function. Specifically, I gave this function a rather small input - simply 10 images - and printed all the information about the graph:

edge: 7 9 65
edge: 7 8 233
edge: 9 10 154
edge: 2 4 103
edge: 2 3 134
edge: 3 7 38
edge: 5 6 311
edge: 3 6 45
edge: 3 5 95
edge: 1 5 41
edge: 3 4 268
edge: 1 4 41
edge: 1 3 138
edge: 4 6 79
edge: 1 2 314
edge: 6 7 38
edge: 5 7 93
edge: 6 8 52

These are the edges with their nodes and weight. And the result I get:

Total weight: 1247
9 10
8 6
7 9
6 5
5 7
4 6
3 1
2 1
1 4

I summed these weights up and can tell this is a legal spanning tree with correct total weight. However, I used other code to calculate the mst of the same problem, and after my verification, this is not the mst for the problem, as the following one is better:

Total weight: 1671
9 10
8 7
7 9
6 5
5 7
4 3
3 5
2 1
1 3

After my exploration I suppose that the problem originates from boost library, as its implementation may not support negative edge weights, so I changed the calculation of weights from weights_boost[e] = -image_pair.inliers.size(); to weights_boost[e] = 1e6-image_pair.inliers.size(); to avoid negative weights, then your code can calculate correct results too. Of course this is an easy fix, and I don't know the actual effect of this mathematical bug, just think it should work as it is supposed to do.

[cre185]

I've made a pull request here: https://github.com/colmap/glomap/pull/90#issue-2499002505. In my implementation I find out the biggest weight and add that value to all the weights, so that all weights should be >= 0.

[lpanaf]

Thanks for the contribution.