Hacktoberfest 2026：メンテナが10月に向けて印を付けた、オープンで初心者向けの issue。 Hacktoberfest の issue を見る

sequential_vertex_coloring out-of-bounds memory access

クローズ 初心者向け
  • 何か問題がありますか？
#627 コメント 1 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

@Becheler がすでに取り組んでいます。

2026年10月7日 から。

評価

難易度
2/5
見積もり時間
1〜3時間
初心者へのやさしさ
78/100
issue の種類
バグ
明瞭さ
明確に書かれている
活発さ
活発
技術スタック
cpp
領域
backend

調査の方向性

sequential_vertex_coloring.hpp と添付の tests.cpp reproducer から始めます。グラフがフィルタリングされ、order property map が指定されていない場合に、デフォルトの order property map がどのように構築され、使用されるかを確認してください。reproducer を元のグラフとフィルタリング後のグラフの両方で実行します。フィルタリング後のグラフに対する呼び出しが範囲外アクセスなしで完了すれば完了です。

索引モデルが issue の本文から書いたものです。

説明

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

主要言語
C++
スター
397
フォーク
246
平均マージ
1日 15時間
マージ済み PR（30日）
31

環境構築

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

boostorg/graph のほかの issue

boostorg/graph の issue をすべて見る

似ている issue

C++ の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。