boostorg / boostorg/graph

Boost small-world generator produces parallel edges

オープン
#256 コメント 1 件 リアクション 0 件 担当者 0 名 GitHub で見る
generator priority: medium
主要言語
C++
スター
392
フォーク
239
平均マージ
1日 11分
マージ済み PR(30日)
20

説明

The Boost small-world generator as defined in [small_world_generator.hpp](https://github.com/boostorg/graph/blob/develop/include/boost/graph/small_world_generator.hpp) can produce parallel edges.

The problem lies in lines 74–76:

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

コントリビューションガイド

コントリビューションガイドを開く

評価

この issue はまだ評価されていません。

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

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