[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] Performance issue on dymanic networks

From: Hadidi, Lars
Subject: Re: [igraph] Performance issue on dymanic networks
Date: Thu, 26 Nov 2015 13:57:19 +0000

Hello Tamas,

yes I do use weights, and they are indeed not integers but floating point 
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 
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.


Von: address@hidden <address@hidden> im Auftrag von Tamas Nepusz 
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.



On Thu, Nov 26, 2015 at 12:34 AM, Hadidi, Lars
<address@hidden> 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
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help

igraph-help mailing list

reply via email to

[Prev in Thread] Current Thread [Next in Thread]