Open hansenjakob opened 3 years ago
Description of bug The mincut function produces incorrect partitions for some graphs.
mincut
How to reproduce The following code produces incorrect results:
edge_list = [(1,2), (1,3), (1,4), (1,5), (2,6), (3,4), (3,6), (4,6), (5,6)] g = SimpleGraphFromIterator([Edge(e...) for e in edge_list]) labels, cut_size = mincut(g)
Expected behavior cut_size should be at most 2 because both vertex 2 and vertex 5 have degree 2.
cut_size
Actual behavior cut_size is 3. In this instance, the cut given separates vertex 4 from the rest of the graph.
In experiments with random graphs, this behavior arises fairly frequently.
Version information
versioninfo()
Julia Version 1.6.0 Commit f9720dc2eb (2021-03-24 12:55 UTC) Platform Info: OS: macOS (x86_64-apple-darwin19.6.0) CPU: Apple M1 WORD_SIZE: 64 LIBM: libopenlibm LLVM: libLLVM-11.0.1 (ORCJIT, westmere) Environment: JULIA_EDITOR = code JULIA_NUM_THREADS =
] status LightGraphs
Status `~/.julia/environments/v1.6/Project.toml` [093fc24a] LightGraphs v1.3.5
Description of bug The
mincut
function produces incorrect partitions for some graphs.How to reproduce The following code produces incorrect results:
Expected behavior
cut_size
should be at most 2 because both vertex 2 and vertex 5 have degree 2.Actual behavior
cut_size
is 3. In this instance, the cut given separates vertex 4 from the rest of the graph.In experiments with random graphs, this behavior arises fairly frequently.
Version information
versioninfo()
surrounded by backticks (``)] status LightGraphs
surrounded by backticks (``)