AlgebraicJulia / AlgebraicJulia/GraphsTreewidth.jl

Indexing out of bounds on directed graphs.

Aberta
#1 0 comentários 0 reações 0 responsáveis Ver no GitHub
Linguagem predominante
Julia
Estrelas
4
Forks
0
Métricas de merge de PRs
Nenhum PR com merge em 30d

Descrição

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
```

Guia de contribuição

Nenhum guia de contribuição indexado para este repositório

Avaliação

Esta issue ainda não foi avaliada.

Receba novas issues na sua caixa de entrada

Um resumo curto de issues do GitHub para quem está começando.