boostorg / boostorg/graph

Random Graphs inconsistencies and usability issues

Open
#475 0 comments 0 reactions 0 assignees View on GitHub
api generator
Dominant language
C++
Stars
392
Forks
239
Avg merge
1d 11m
Merged PRs (30d)
20

Description

While documenting the random graph generators and utilities and drafting examples, I bumped into some issues. It happens that several generator APIs seem to have inconsistencies and silent failures. I will drop my findings here for future reference.

Most of them seem easy fixes, but the ER directed case looks like a full feature that would need some math guy backup and a more in-depth dive in the existing literature.

---

### A) `erdos_renyi_iterator` has ambiguous constructors

The class has two constructors:

```cpp
erdos_renyi_iterator(gen, n, double fraction = 0.0, bool allow_self_loops = false);
erdos_renyi_iterator(gen, n, edges_size_type m, bool allow_self_loops = false);
```

Passing an integer literal is ambiguous (`int` converts equally to both `double` and `edges_size_type`):

```cpp
erdos_renyi_iterator(gen, 100, 50); // compile error: ambiguous
```

Both gcc and clang reject this with "call is ambiguous". The fix is an explicit cast, but the error message does not explain this:

```cpp
using EdgeCount = graph_traits::edges_size_type;
erdos_renyi_iterator(gen, 100, EdgeCount(50)); // OK
```

[See on Compiler Explorer](https://godbolt.org/z/McfTPE9MG)

---

### B) `small_world_iterator` silently assumes undirected graphs

The original Watts-Strogatz model is strictly undirected. The algorithm starts from an undirected ring lattice and rewires undirected edges with probability `p`. There is no canonical directed version in the [original paper](https://www.hajim.rochester.edu/ece/sites/gmateos/ECE442/Readings/watts_strogatz.pdf).

Directed variants have been proposed in the literature, but they require explicit decisions and there is no consensus formulation:

- [Algebraic approach to small-world network models](https://journals.aps.org/pre/pdf/10.1103/PhysRevE.89.012812)
- [Simple, distance-dependent formulation of the Watts-Strogatz model for directed and undirected small-world networks](https://arxiv.org/pdf/1408.4461)

However, in BGL when instantiated with a directed graph `watts_strogatz_iterator`, the iterator emits n * (k/2) directed edges (each source connects to its k/2 clockwise neighbors).
- For undirected graphs, each edge implicitly exists in both directions, giving every vertex degree k.
- For directed graphs, each edge exists in one direction only, giving every vertex out_degree = k/2.
- The Graph template parameter is only used for `vertices_size_type` : `directed_category` is never checked.

[See on Compiler Explorer](https://godbolt.org/z/6xzc1evr1)

Because generating a directed small-world graph requires explicit design choices, silently producing a broken/arbitrary result that does not check against any theory is probably worse than refusing to compile.

---

### C) Default probability parameters mean different things across generators

| Generator | Default | Meaning |
|-----------|---------|---------|
| `erdos_renyi_iterator` | `fraction = 0.0` | Empty graph |
| `sorted_erdos_renyi_iterator` | `prob = 0.5` | 50% density |
| `small_world_iterator` | `prob = 0.0` | No rewiring (ring lattice) |

A user familiar with one generator will be surprised by the others.

---

### D) Parameter naming inconsistency in the same header

In `erdos_renyi_generator.hpp`:
- `erdos_renyi_iterator`: parameter named `allow_self_loops`
- `sorted_erdos_renyi_iterator`: parameter named `loops`

Same concept, same header but different names is not very consistent.

---

### E) Precondition violation behavior unspecified

- `random_vertex(g, gen)` requires `num_vertices(g) > 0`
- `random_edge(g, gen)` requires `num_edges(g) > 0`

But neither the code nor the documentation specifies what happens on violation (undefined behavior, assertion, exception). Consequently:
- `random_vertex` on empty graphs returns a boggus descriptor
- `random_edge` on empty graph triggers assertion deep inside boost optional

[See on Compiler Explorer](https://godbolt.org/z/WWc48nEEr)

```
output.s: /app/boost/include/boost/optional/optional.hpp:908: pointer_const_type boost::optional *, std::vector>>, unsigned long, boost::detail::edge_desc_impl, long>, boost::detail::out_edge_iter<__gnu_cxx::__normal_iterator *, std::vector>>, unsigned long, boost::detail::edge_desc_impl, long>>>::operator->() const [T = std::pair *, std::vector>>, unsigned long, boost::detail::edge_desc_impl, long>, boost::detail::out_edge_iter<__gnu_cxx::__normal_iterator *, std::vector>>, unsigned long, boost::detail::edge_desc_impl, long>>]: Assertion `this->is_initialized()' failed.
```

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.