igraph_maximum_bipartite_matching implements the Hungarian algorithm for weighted graphs. The reason why it is unstable for non-integer weights is because it performs several arithmetic operations (if I remember correctly, subtractions) on floating-point values, and at the same time it also relies on finding zeros in the matrix to decide which edges are "tight". Subtractions may not yield exactly zero values due to numerical inaccuracies in the floating-point representation. To this end, there is a parameter named "eps" in igraph_maximum_bipartite_matching and when the slack of an edge falls below eps (in absolute value), it is considered tight. However, setting eps is a tricky problem, so the most reliable thing to do is to use integer weights only and set eps to zero.
If your graph has non-integer weights, you can either experiment with setting eps to different values (depending on how accurate you want the algorithm to be - in the worst case, you'll end up with a suboptimal matching), or multiply your weights by some power of 10 and truncate the remaining fractional digits. T. On Mon, Sep 7, 2015 at 1:25 PM, Hadidi, Lars <[email protected]> wrote: > I plan to implement multi particle tracking on a time series of different > positions. In order to associate the data, I need to solve the minimum > weighted bipartite matching problem with maximum cardinality but not perfect > matching (particles may be created or annihilated) > According to the documentation of iGraph the method > "graph_maximum_bipartite_matching" solves for integer weights. > A note says that the algorithm is stable only for integer weights. > My question is what exactly is meant by stability in this context ? Which > algorithm is used to realize the matching ? (Hungarian, Blossom,...) > > > > _______________________________________________ > igraph-help mailing list > [email protected] > https://lists.nongnu.org/mailman/listinfo/igraph-help > _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
