Random Graphs inconsistencies and usability issues
- 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
Assessment
This issue has not been assessed yet.