Re: [igraph] iGraph Matching Algorithm

[Tamas Nepusz]

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
<address@hidden> 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
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>