Hacktoberfest 2026: the issues maintainers tagged for October, open and beginner-friendly. Browse Hacktoberfest issues

Boost small-world generator produces parallel edges

Open
  • Is something wrong?
#256 1 comment 0 reactions 0 assignees View on GitHub

Maintainers usually reply within 1 day

Nobody has claimed this yet.

Assessment

Difficulty
3/5
Estimated time
1-2 days
Newbie friendliness
55/100
Issue type
Bug
Clarity
Mostly clear
Activity status
Quiet
Tech stack
cpp
Domain
data

Research direction

Start in include/boost/graph/small_world_generator.hpp, especially lines 74–76, and trace how rewiring selects the target vertex. Check the existing edge before accepting a rewired target, then verify that generated small-world graphs contain no parallel edges, including edges outside the distance-k neighbourhood.

Written by the indexing model from the issue text.

Description

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

Dominant language
C++
Stars
396
Forks
244
Avg merge
2d 6h
Merged PRs (30d)
29

Getting set up

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from boostorg/graph

All issues in boostorg/graph

Similar issues

More C++ issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.