boostorg / boostorg/graph

Boost small-world generator produces parallel edges

未关闭
#256 1 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看
generator priority: medium
主要语言
C++
星标
392
派生
239
平均合并
1 天 11 分钟
30 天内合并 PR
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 摘要。