Hello Tamas, yes I do use weights, and they are indeed not integers but floating point values. I only read in the documentation that the method uses push-relabel, but the information you just gave me already helps a a lot, as I have to write a theoretical part about my work, too, which should describe the algorithm applied. Following the description on wikipedia, the hungarian method can be implemented in O(n^4) and optimized to O(n^3). But nevertheless, the weight matrix should be square. If not, dummy values are to be inserted. 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. Thank you a lot for your support. Sincerely,
Lars ________________________________________ Von: [email protected] <[email protected]> im Auftrag von Tamas Nepusz <[email protected]> Gesendet: Donnerstag, 26. November 2015 11:33 An: Help for igraph users Betreff: Re: [igraph] Performance issue on dymanic networks Hello Lars, Just to clarify: are you using weights in the maximum bipartite matching, and if so, are they integers or not? I'm asking because I thought that particle tracking algorithms involve a bipartite matching in a weighted graph, but the push-relabel algorithm is used for unweighted graphs only. If you have a weighted graph, then igraph will use the Hungarian algorithm instead, but then you have to be careful how you select the "eps" parameter of the algorithm if your weights are not integers. I'll try to run some profiling experiments if you clarify this. In particular, I know that there's a point in the Hungarian algorithm where we use an O(n^2) loop even though we could probably be smarter there, so that's a possible hot spot - but if you do not use any weights, then there's no point for me in poking around there. T. T. On Thu, Nov 26, 2015 at 12:34 AM, Hadidi, Lars <[email protected]> wrote: > I am using the igraph_maximum_bipartite_matching function to implement a > multi particle tracking algorithm. > > I already have been informed that thelibrary is optimized for graphs that do > not change a lot. > > As I create a new graph for every new frame, this isn't the optimal use case > for the library, but a profiling session showed that it doesn't appear to be > a performance drop at all, as the removing of all vertices and using > add_edges are still pretty fast, only the index rebuild invoked by > add_vertices cosumes some time. > > Most of the time is spent on the bipartite matching, and I'd like to know if > there is any way to increase performance ? > > The optimized push-relabel method used by igraph is theoretically one of the > fastest methods out there, but the more nodes the graph has, the slower the > code works, seemingly exponentially slower. (processing 5GB of data takes > about 12 hours, 30GB won't finish after 60 hours) > > > _______________________________________________ > 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 _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
