Thank you for your support. I will try to adjust the eps-value which has been set to std::numeric_limits<double>::epsilon() in my case.
Sincerely, Lars ________________________________________ Von: [email protected] <[email protected]> im Auftrag von Tamas Nepusz <[email protected]> Gesendet: Mittwoch, 2. Dezember 2015 15:36 An: Help for igraph users Betreff: Re: [igraph] Performance issue on dymanic networks Hello Lars, > yes I do use weights, and they are indeed not integers but floating point > values. In that case, try to use a non-zero "eps" value; set it to some small number instead, e.g., 1e-6. The reason is that in the Hungarian algorithm, there are cases when one has to decide whether a (real or phantom) edge is "tight", where "tight" means that the sum of the labels of its two endpoints is equal to the weight of the edge. However, in floating-point arithmetics, it may happen that the equality check fails even if it would be true in reality; for instance, try this in Python: >>> 0.1 + 0.2 == 0.3 False (See http://0.30000000000000004.com/ for more details). That's why igraph uses a tolerance threshold of 'eps' where an edge is considered tight if the sum of the labels of its two endpoints minus the weight of the edge is less than 'eps' in absolute value. If you use eps=0 and the weights are not integers, some edges that are tight might not be considered tight by the algorithm. If you use a value of eps that is too large, then some non-tight edges might be considered tight. Both options could lead to suboptimal solutions, but I think that eps being equal to a small positive number such as 1e-6 should be fine. > Could you provide me an outline of how it is done in igraph's case, maybe > just a reference to a paper or a book, according to the implementation in > your library. The implementation in igraph uses the original graph data structure plus an additional adjacency list that contains the tight phantom edges that appeared during the course of the algorithm. That's the only trick if I remember correctly. The additional (dummy) entries of the matrix are not stored. For what it's worth, I think that the implementation in igraph could actually be improved a bit. Right now the problem is that we have an O(n^2) loop where we update the set of tight phantom edges - this is done by examining all possible pairs of vertices from the two parts of the graph. I think we could do better there by re-checking only those vertices where the label of the vertex was adjusted in the last iteration. All the best, T. _______________________________________________ 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
