Hacktoberfest 2026: los issues que los mantenedores marcaron para octubre, abiertos y aptos para principiantes. Explorar issues de Hacktoberfest

sequential_vertex_coloring out-of-bounds memory access

Cerrado Apto para principiantes
  • ¿Algo no está bien?
#627 1 comentario 0 reacciones 0 asignados Ver en GitHub

Los mantenedores suelen responder en 1 día

@Becheler ya está trabajando en esto.

Desde el 7/10/2026.

Evaluación

Dificultad
2/5
Tiempo estimado
1-3 horas
Aptitud para principiantes
78/100
Tipo de issue
Error
Claridad
Bien especificado
Estado de actividad
Activo
Stack tecnológico
cpp
Área
backend

Línea de trabajo

Empieza con sequential_vertex_coloring.hpp y el reproducer tests.cpp adjunto. Comprueba cómo se construye y utiliza el mapa de propiedades de orden predeterminado cuando el grafo está filtrado y no se proporciona ningún mapa de propiedades de orden. Ejecuta el reproducer tanto en el grafo original como en el filtrado; el trabajo estará terminado cuando la llamada sobre el grafo filtrado se complete sin acceder fuera de los límites.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

The algorithm encoded in sequential_vertex_coloring.hpp accesses memory out of bounds when called with (i) a filtered graph, i.e., one for which num_vertices(g) > distance(vertices(g).first,vertices(g).second), and (ii) no order property map. This is because, for a filtered graph, the order property map constructed by the algorithm is too small. The algorithm documents the order property map to have the following property:

 A mapping from integers in the range [0, num_vertices(g)) to the vertices of the graph.

However, it is constructed from vertices(g), not num_vertices(g). For filtered graphs, the former range may be smaller than the latter, yet the algorithm itself accesses all the vertices returned by num_vertices(g), i.e., in the range referred to above. Therefore, out-of-bounds memory access is possible.

See below for a reproducer and a patch that works for me. Although I have tested this only on Boost v1.86.0, the file in question is unchanged for seven years and contains the same code.

Before filing
  • [ x] I searched the existing issues and did not find a duplicate.
  • [x ] I have reproduced the bug against the develop branch or the latest Boost release.
  • [x ] I have a minimal reproducer (or I will paste my full failing code below).
Boost version

1.86.0

Compiler family
  • GCC / g++
  • [ x] Clang / clang++
  • MSVC (Visual Studio)
  • Intel / oneAPI
  • Other (specify below)

Exact compiler version:

Apple clang version 16.0.0 (clang-1600.0.26.4)

Standard library
  • libstdc++
  • libc++
  • MSVC STL
  • Other (specify below)
Operating system
  • Linux
  • [ x] macOS
  • Windows
  • Other (specify below)
Kind of component affected
  • Graph data structure (e.g. adjacency_list, adjacency_matrix)
  • [ x] Algorithm (e.g. dijkstra_shortest_paths, breadth_first_search)
  • Property map
  • I/O or file-format reader (e.g. read_graphml, read_graphviz)
  • Visitor / event hooks
  • Other (specify below)

Exact name of the affected component:

sequential_vertex_coloring

Steps to reproduce

(i) create a filtered graph (g) that reduces the number of vertices
(ii) call sequential_vertex_coloring(g,color_map), i.e., without an order property map

See the attached reproducer, which colors both the original and filtered graphs to demonstrate the problem only with the latter.

Expected behavior

The algorithm should complete.

Actual behavior

Segmentation fault, i.e., signal 11.

Are you willing to help?
  • I'd like to submit a fix as a pull request.
  • I can help diagnose or test a candidate fix.
  • [ x] I'm only reporting the issue.

I am happy to help test as needed, but this report should be entirely self-contained with a reproducer and a patch (see below).

tests.cpp

sequential_vertex_coloring.hpp.patch

Lenguaje dominante
C++
Estrellas
399
Forks
247
Merge medio
1 d 9 h
PR fusionados (30 d)
40

Preparar el entorno

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de boostorg/graph

Todos los issues de boostorg/graph

Issues similares

Más issues de C++

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.