boostorg / boostorg/graph

Euclidian Random Graphs Utilities

Abierto
#452 5 comentarios 1 reacción 0 asignados Ver en GitHub
generator
Lenguaje dominante
C++
Estrellas
392
Forks
239
Merge medio
1 d 11 min
PR fusionados (30 d)
20

Descripción

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)
```

Guía de contribución

Abrir la guía de contribución

Evaluación

Este issue todavía no se ha evaluado.

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.