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

Boost small-world generator produces parallel edges

オープン
  • 何か問題がありますか？
#256 コメント 1 件 リアクション 0 件 担当者 0 名 GitHub で見る

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

まだ誰も着手していません。

評価

難易度
3/5
見積もり時間
1〜2日
初心者へのやさしさ
55/100
issue の種類
バグ
明瞭さ
おおむね明確
活発さ
静か
技術スタック
cpp
領域
data

調査の方向性

include/boost/graph/small_world_generator.hpp、特に 74–76 行目から始め、rewiring が対象頂点をどのように選択するかを追跡します。rewired target を受け入れる前に既存のエッジを確認し、その後、生成された small-world グラフに、距離-k 近傍の外側にあるエッジも含めて、平行エッジが存在しないことを検証します。

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

説明

generator priority: medium

The Boost small-world generator as defined in small_world_generator.hpp can produce parallel edges.

The problem lies in lines 74–76:

if (x < prob)
        {
            vertices_size_type lower = (source + n - k / 2) % n;
            vertices_size_type upper = (source + k / 2) % n;
            do
            {
                current.second = rand_vertex_gen(*gen);
            } while ((current.second >= lower && current.second <= upper)    // <---- L74 
                || (upper < lower  
                    && (current.second >= lower || current.second <= upper)));
        }
else
        {
            current.second = target;
        }

While this guarantees that parallel edges cannot be created between neighbouring vertices in range < k, it does not prevent edges being rewired to already rewired edges, i.e. edges outside the distance-k-neighbourhood.

Proposed fix:

Inserting a check à la if not boost::edge(v, w, g).second should solve the issue

主要言語
C++
スター
399
フォーク
247
平均マージ
1日 9時間
マージ済み PR（30日）
40

環境構築

はじめの一歩

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

boostorg/graph のほかの issue

boostorg/graph の issue をすべて見る

似ている issue

C++ の issue をもっと見る

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

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