Mincut

[etiennedeg]

The implementation was mostly wrong. It was doing a single max adjacency visit, whereas Stoer Wagner do multiple cut of the case, shrinks two vertex at each phase, and repeat until there is one vertex remaining. I optimized Stoer Wagner a bit with the simple realization that an edge can be contracted if its weight is higher than the current mincut. Each additional merged edge spare a whole minimum cut phase. As the graphs shrinks, edge weights sum up, so more and more edges can be merged.

I also fixed a bug in max adjacency visit when the graph contains loops.

[codecov[bot]]

Codecov Report

Merging #105 (384ba30) into master (745add6) will increase coverage by 0.01%. The diff coverage is 100.00%.

@@            Coverage Diff             @@
##           master     #105      +/-   ##
==========================================
+ Coverage   97.19%   97.20%   +0.01%     
==========================================
  Files         114      114              
  Lines        6656     6701      +45     
==========================================
+ Hits         6469     6514      +45     
  Misses        187      187              

[simonschoelly]

I haven't had time to refresh my memory on min-cut algorithms, but I was wondering, was the old algorithm just incorrect for weighted graphs or are there also unweighted graphs where it would perform incorrectly?

The reason am asking is, that your new implementation allocates quite a lot of memory, so it will probably not as efficient anymore. Still your regression test shows that the old implementation was incorrect and being correct is better than being efficient.

[etiennedeg]

The old implementation was very wrong and failing also for unweighted graphs (see the example provided in the original issue). It is expected that the new implementation is much slower than the previous one, but it might be possible that it can be implemented more efficiently, merging vertices is a quite delicate operation to do efficiently. I also fixed a bug for graphs with self-loops and also for directed graphs. It is possible to be a bit more efficient for dense graphs, and for undirected graphs but not that much. Maybe it is worth specializing, I don't know...

[etiennedeg]

Just realized that Stoer-Wagner does not work on directed graphs, reverted the commit and disabled the function for directed graphs.

[etiennedeg]

I added a new heuristic. During a phase, the connection of a non visited vertex with the visited vertices is a lower bound on the size of the minimal cut between this vertex and the last visited vertex. If the connection is higher than the best mincut found, we can already merge these two vertices, saving one cut of the phase. This is a much better heuristic than the one I described above in this PR. I also fixed many things (I really don't know what the heck I did in my last commit, I added a check to guarantee the validity of @inbounds, I corrected the initialization of the phase)

[gdalle]

This bug has been standing there for far too long, so given @etiennedeg's track record I'd be in favor of merging even though I haven't delved into the algorithm details.

One thing I'd like to understand though is how the new test ensures non regression vis-à-vis https://github.com/sbromberger/LightGraphs.jl/issues/1589, since they appear to be different graphs

[etiennedeg]

The bug was due to the fact that the algorithm was never doing merging logic. The example is built such that it can't be solved without using the merging logic, no matter what starting vertex and what lexicographic ordering of the vertices is chosen, so it should do a much better job as ensuring there is no regression.