Repeated cycles from mincyclebasis

[jd-foster]

I was testing a new implementation of a minimum cycle basis algorithm and was using this package's mincyclebasis for reference. Thanks.
However, it appears I have an example demonstrating a bug in the mincyclebasis() function, showing that the function creates a list with repeated (non-unique) cycles.

Here is a file in Graphs.jl LGFormat:
case57_ieee-MCB-ce.txt

Usage Details

julia> using MolecularGraph

julia> const MG = MolecularGraph
MolecularGraph

julia> g = MG.Graphs.loadgraph("case57_ieee-MCB-ce.txt")
{57, 78} undirected simple Int64 graph

julia> h = MG.mincyclebasis(g);

julia> sort(h, by=sum)
22-element Vector{Vector{Int64}}:
 [4, 6, 5]
 [1, 2, 3, 15]
 [6, 7, 8]
 [9, 12, 10]
 [9, 11, 13]
 [9, 12, 13]
 [13, 14, 15]
 [13, 14, 15]
 [1, 17, 12, 16]
 [3, 4, 6, 8, 9, 13, 15]
 [3, 4, 6, 8, 9, 13, 15]
 [11, 41, 43]
 [38, 49, 48]
 [41, 56, 42]
 [9, 10, 51, 50, 49, 13]
 [13, 49, 38, 44, 45, 15]
 [13, 49, 48, 47, 46, 14]
 [3, 4, 18, 19, 20, 21, 22, 38, 49, 13, 15]
 [36, 37, 39, 57, 56, 40]
 [7, 29, 52, 53, 54, 55, 9, 8]
 [11, 13, 49, 38, 37, 36, 40, 56, 41]
 [22, 38, 37, 36, 35, 34, 32, 31, 30, 25, 24, 23]

The non-unique cycles are

2-element Vector{Vector{Int64}}:
 [13, 14, 15]
 [3, 4, 6, 8, 9, 13, 15]

cc. @frederikgeth

[mojaie]

Thank you very match for catching it.
It looks simply a bug in spanning tree algorithm

g = Graphs.loadgraph("/Users/riken/Downloads/case57_ieee-MCB-ce.txt")
MolecularGraph.cotree_edges(g)

Set{Graphs.SimpleGraphs.SimpleEdge{Int64}} with 22 elements:
  Edge 9 => 13
  Edge 14 => 15   -> cycle 13, 14, 15
  Edge 8 => 9
  Edge 3 => 15
  Edge 36 => 40
  Edge 9 => 55
  Edge 9 => 11
  Edge 4 => 5
  Edge 6 => 8
  Edge 15 => 45
  Edge 9 => 10
  Edge 12 => 16
  Edge 21 => 22
  Edge 10 => 51
  Edge 11 => 43
  Edge 13 => 15   -> also cycle 13, 14, 15
  Edge 2 => 3
  Edge 11 => 41
  Edge 14 => 46

This will be fixed soon.

[mojaie]

It looks I just forgot to close cycles in mincyclebasis.

After fixed:

22-element Vector{Vector{Int64}}:
 [4, 6, 5]
 [1, 2, 3, 15]
 [6, 7, 8]
 [9, 12, 10]
 [9, 11, 13]
 [9, 12, 13]
 [13, 14, 15]
 [1, 17, 12, 16]
 [1, 16, 12, 13, 15]
 [3, 4, 6, 8, 9, 13, 15]
 [11, 41, 43]
 [38, 49, 48]
 [41, 56, 42]
 [9, 10, 51, 50, 49, 13]
 [13, 49, 38, 44, 45, 15]
 [13, 49, 48, 47, 46, 14]
 [3, 4, 18, 19, 20, 21, 22, 38, 49, 13, 15]
 [36, 37, 39, 57, 56, 40]
 [7, 29, 52, 53, 54, 55, 9, 8]
 [7, 29, 28, 27, 26, 24, 23, 22, 38, 49, 13, 9, 8]
 [11, 13, 49, 38, 37, 36, 40, 56, 41]
 [22, 38, 37, 36, 35, 34, 32, 31, 30, 25, 24, 23]