Euclidian Random Graphs Utilities

Open
#452 5 comments 1 reaction 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
48/100
Issue type
Feature
Clarity
Mostly clear
Activity status
Quiet
Tech stack
cpp
Domain
testing

Research direction

Locate the existing Traveling Salesperson generators and the example or testing code where these Euclidean graph utilities were created as a side effect. Review the named generate_random_points, connect_all_euclidean, and make_random_euclidean_graph interfaces, then verify that configurable distributions, scales, point counts, and fully connected weighted graphs are covered by tests or examples.

Written by the indexing model from the issue text.

Description

generator

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)
Dominant language
C++
Stars
395
Forks
239
Avg merge
18h 50m
Merged PRs (30d)
20

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from boostorg/graph

All issues in boostorg/graph

Similar issues

More C++ issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.