boostorg / boostorg/graph

Euclidian Random Graphs Utilities

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

Description

As per discussion with Arnaud Becheler, he suggested I create an issue related to Euclidian Graph Utilities that I created as a side effect (part of examples/testing) of implementing Traveling Salesperson generators (metric_tsp, nearest_neighbor).

These utilities allow the user to generate fully connected graphs based on configurable random distributions (normal, uniform, clusters, etc), scale (max x, max y), and number of points. These kinds of graphs are useful in the context of TSP algorithms as many rely on fully connectedness and this allows for tuning of graph shape for testing and benchmarking purposes. Utilities include:

```
template < typename OutputIterator, typename XDistribution,
typename YDistribution, typename RandomEngine >
void generate_random_points(std::size_t num_points, XDistribution x_dist,
YDistribution y_dist, OutputIterator out, RandomEngine& rng)
```

```
template < typename VertexListGraph, typename PointContainer,
typename WeightMap, typename VertexIndexMap >
void connect_all_euclidean(VertexListGraph& g, const PointContainer& points,
WeightMap wmap, VertexIndexMap vmap)
```

```
template < typename VertexListGraph, typename WeightMap,
typename VertexIndexMap, typename XDistribution, typename YDistribution >
void make_random_euclidean_graph(VertexListGraph& g, std::size_t num_points,
XDistribution x_dist, YDistribution y_dist, WeightMap weight_map,
VertexIndexMap vertex_index_map)
```

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.