AlgebraicJulia / AlgebraicJulia/GraphsTreewidth.jl

Indexing out of bounds on directed graphs.

Aperta
#1 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub
Lingua principale
Julia
Stelle
4
Fork
0
Metriche di merge delle PR
Nessuna PR unita negli ultimi 30g

Descrizione

I'm not entirely sure whether this is supposed to work with directed graphs, if not it would be nice with a clear error stating that.

Assuming that it should work, there are some bugs to track down:
```
$ julia --check-bounds=yes
_
_ _ _(_)_ | Documentation: https://docs.julialang.org
(_) | (_) (_) |
_ _ _| |_ __ _ | Type "?" for help, "]?" for Pkg help.
| | | | | | |/ _` | |
| | |_| | | | (_| | | Version 1.12.4 (2026-01-06)
_/ |\__'_|_|_|\__'_| | Official https://julialang.org release
|__/ |

julia> using GraphsTreewidth, Graphs

julia> g = erdos_renyi(5, 0.5, is_directed = true, seed = 1)
{5, 9} directed simple Int64 graph

julia> Solver(g)
ERROR: BoundsErrorLight: attempt to access array of type FixedSizeArrays.FixedSizeArray{Int64, 1, Memory{Int64}} and shape (10029,) at index [-1]
Stacktrace:
[1] throw_boundserrorlight
@ ~/.julia/packages/FixedSizeArrays/VHLXx/src/BoundsErrorLight.jl:32 [inlined]
[2] check_bounds_light
@ ~/.julia/packages/FixedSizeArrays/VHLXx/src/BoundsErrorLight.jl:37 [inlined]
[3] getindex
@ ~/.julia/packages/FixedSizeArrays/VHLXx/src/FixedSizeArray.jl:166 [inlined]
[4] hamf_impl!(norig::Int64, n::Int64, nbelts::Int64, nbbuck::Int64, iwlen::Int64, pe::FixedSizeArrays.FixedSizeArray{…}, pfree::Int64, len::FixedSizeArrays.FixedSizeArray{…}, iw::FixedSizeArrays.FixedSizeArray{…}, nv::FixedSizeArrays.FixedSizeArray{…}, elen::FixedSizeArrays.FixedSizeArray{…}, last::FixedSizeArrays.FixedSizeArray{…}, degree::FixedSizeArrays.FixedSizeArray{…}, wf::FixedSizeArrays.FixedSizeArray{…}, next::FixedSizeArrays.FixedSizeArray{…}, w::FixedSizeArrays.FixedSizeArray{…}, head::FixedSizeArrays.FixedSizeArray{…})
@ CliqueTrees.AMFLib ~/.julia/packages/CliqueTrees/Tzv8B/src/AMFLib.jl/src/AMFLib.jl:1254
[5] amf_impl!(norig::Int64, n::Int64, nbbuck::Int64, iwlen::Int64, pe::FixedSizeArrays.FixedSizeArray{…}, len::FixedSizeArrays.FixedSizeArray{…}, iw::FixedSizeArrays.FixedSizeArray{…}, nv::FixedSizeArrays.FixedSizeArray{…}, elen::FixedSizeArrays.FixedSizeArray{…}, last::FixedSizeArrays.FixedSizeArray{…}, degree::FixedSizeArrays.FixedSizeArray{…}, wf::FixedSizeArrays.FixedSizeArray{…}, next::FixedSizeArrays.FixedSizeArray{…}, w::FixedSizeArrays.FixedSizeArray{…}, head::FixedSizeArrays.FixedSizeArray{…}, vwght::FillArrays.Ones{…}, xadj::FixedSizeArrays.FixedSizeArray{…}, adjncy::FixedSizeArrays.FixedSizeArray{…})
@ CliqueTrees.AMFLib ~/.julia/packages/CliqueTrees/Tzv8B/src/AMFLib.jl/src/AMFLib.jl:131
[6] amf(n::Int64, vwght::FillArrays.Ones{…}, xadj::FixedSizeArrays.FixedSizeArray{…}, adjncy::FixedSizeArrays.FixedSizeArray{…})
@ CliqueTrees.AMFLib ~/.julia/packages/CliqueTrees/Tzv8B/src/AMFLib.jl/src/AMFLib.jl:86
[7] amf
@ ~/.julia/packages/CliqueTrees/Tzv8B/src/elimination_algorithms.jl:2092 [inlined]
[8] permutation
@ ~/.julia/packages/CliqueTrees/Tzv8B/src/elimination_algorithms.jl:1376 [inlined]
[9] cliquetree(weights::FillArrays.Ones{…}, graph::SimpleDiGraph{…}, alg::CliqueTrees.AMF, snd::CliqueTrees.Maximal)
@ CliqueTrees ~/.julia/packages/CliqueTrees/Tzv8B/src/clique_trees.jl:127
[10] cliquetree
@ ~/.julia/packages/CliqueTrees/Tzv8B/src/clique_trees.jl:99 [inlined]
[11] #cliquetree#51
@ ~/.julia/packages/CliqueTrees/Tzv8B/src/clique_trees.jl:81 [inlined]
[12] cliquetree
@ ~/.julia/packages/CliqueTrees/Tzv8B/src/clique_trees.jl:76 [inlined]
[13] #Solver#7
@ ~/.julia/dev/GraphsTreewidth/src/solvers.jl:8 [inlined]
[14] Solver(graph::SimpleDiGraph{Int64})
@ GraphsTreewidth ~/.julia/dev/GraphsTreewidth/src/solvers.jl:7
```

Guida per i contributori

Nessuna guida per i contributori indicizzata per questo repository

Valutazione

Questa issue non è ancora stata valutata.

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.