JuliaGraphs / JuliaGraphs/Graphs.jl
[BUG] cycle_basis not returning the correct number of cycles
Nobody has claimed this yet.
- 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
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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