Re: [igraph] Performance issue on dymanic networks

[Tamas Nepusz]

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