JuliaGraphs / JuliaGraphs/Graphs.jl

[BUG] cycle_basis not returning the correct number of cycles

Open
#219 9 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug
Dominant language
Julia
Stars
538
Forks
128
Avg merge
10h 25m
Merged PRs (30d)
2

Description

Description of bug
The cycle_basis without root parameter has a problem with a graph in the shape of the following molecule: https://pubchem.ncbi.nlm.nih.gov/compound/149096
With root, the result is inconsistent depending on the root: Mostly 3 and sometimes the correct 4 cycles smaller than 10, see below.

How to reproduce
The BiochemicalAlgorithms.jl provides a core for loading 3D Conformers from the PubChem .json format.
Download the 3D Conformer via "Download" from: https://pubchem.ncbi.nlm.nih.gov/compound/149096#section=3D-Conformer
Add the BiochemicalAlgorithms.jl package from https://github.com/hildebrandtlab/BiochemicalAlgorithms.jl (the develop branch is sufficient for this purpose). Then in Console load the molecule:
mol_149096 = load_pubchem_json("your/path/here.json")[1]

Then build the graph with the following function:
function build_graph(mol::Molecule)
mol_graph = SimpleGraph(nrow(mol.atoms))
for i = (1:nrow(mol.bonds))
add_edge!(mol_graph, mol.bonds.a1[i], mol.bonds.a2[i])
end
return mol_graph
end

After building the graph of the molecule and naming it mol_graph_CID_149096:
filter(x -> lastindex(x) < 10, cycle_basis(mol_graph_CID_149096))

Expected behavior
filter(x -> lastindex(x) < 10, cycle_basis(mol_graph_CID_149096))
Should return 4 cycles smaller than 10:
[7, 20, 25, 23, 18, 13]
[14, 12, 19, 21, 18, 13]
[9, 15, 8, 16, 10, 6]
[7, 11, 17, 2, 14, 13]

Actual behavior
Only returns 3 cycles smaller than 10:
[13, 14, 12, 19, 21, 18]
[13, 7, 11, 17, 2, 14]
[9, 15, 8, 16, 10, 6]

Code demonstrating bug
see "How to reproduce" section above

Version information
Graphs.jl v1.7.4

Additional context
Add any other context about the problem here.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start at the cycle_basis entry point in Graphs.jl and reproduce the issue using the PubChem compound 149096 graph described above. Compare results with and without the root parameter, including the listed cycle-size filter; done means the reproduction returns all 4 expected cycles smaller than 10 consistently.

Written by the indexing model from the issue text.

Assessment

Tech stack
julia
Domain
data
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.