igraph-help
[Top][All Lists]

## 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
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

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

_______________________________________________
igraph-help mailing list
https://lists.nongnu.org/mailman/listinfo/igraph-help

```