boostorg / boostorg/graph

Euclidian Random Graphs Utilities

Offen
#452 5 Kommentare 1 Reaktion 0 zugewiesene Personen Auf GitHub ansehen
generator
Vorherrschende Sprache
C++
Sterne
392
Forks
239
Ø Merge
1 T. 11 Min.
Gemergte PRs (30 T.)
20

Beschreibung

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

Beitragsleitfaden

Beitragsleitfaden öffnen

Bewertung

Dieses Issue wurde noch nicht bewertet.

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.