Hacktoberfest 2026: the issues maintainers tagged for October, open and beginner-friendly. Browse Hacktoberfest issues

sequential_vertex_coloring out-of-bounds memory access

Closed Beginner friendly
  • Is something wrong?
#627 1 comment 0 reactions 0 assignees View on GitHub

Maintainers usually reply within 1 day

@Becheler is already working on this.

Since Oct 7, 2026.

Assessment

Difficulty
2/5
Estimated time
1-3 hours
Newbie friendliness
78/100
Issue type
Bug
Clarity
Clearly specified
Activity status
Active
Tech stack
cpp
Domain
backend

Research direction

Start with sequential_vertex_coloring.hpp and the attached tests.cpp reproducer. Check how the default order property map is built and used when the graph is filtered and no order property map is supplied. Run the reproducer on both the original and filtered graphs; done means the filtered-graph call completes without an out-of-bounds access.

Written by the indexing model from the issue text.

Description

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

Dominant language
C++
Stars
397
Forks
246
Avg merge
1d 15h
Merged PRs (30d)
31

Getting set up

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.

More from boostorg/graph

All issues in boostorg/graph

Similar issues

More C++ issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.