boostorg / boostorg/graph

Boost small-world generator produces parallel edges

Open
#256 1 comment 0 reactions 0 assignees View on GitHub
generator priority: medium
Dominant language
C++
Stars
392
Forks
239
Avg merge
1d 11m
Merged PRs (30d)
20

Description

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

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.