Hacktoberfest 2026: the issues maintainers tagged for October, open and beginner-friendly. Browse Hacktoberfest issues

Any interest in Nearest Neighbor greedy tour algorithm and/or cleaned up metric_tsp_approx?

Open
  • Is something wrong?
#448 15 comments 2 reactions 0 assignees View on GitHub

Maintainers usually reply within 1 day

Nobody has claimed this yet.

Assessment

Difficulty
5/5
Estimated time
Over a week
Newbie friendliness
25/100
Issue type
Feature
Clarity
Needs clarification
Activity status
Quiet
Tech stack
cpp
Domain
data

Research direction

Start by reviewing the existing metric_tsp_approx implementation and its example and test code, then compare them with the proposed nearest_neighbor_tour_from_vertex entry point. Before coding, confirm which algorithm or cleanup the project wants accepted. Done would require an agreed scope plus integrated examples and tests for the selected change.

Written by the indexing model from the issue text.

Description

algorithm generator

Hi,

I have written a Nearest Neighbor greedy tour heuristic w/ example and test code. I think this heuristic is a good pairing to the metric_tsp as it has less constraints on the graph/edge weight types (no triangle inequality required), does not require a global MST, uses less memory while running due to local greedy characteristic, and runs much faster albeit with the caveat that it does not have a defined upper bound on tour efficiency. However, typical results are very strong and it is a good starting point to the more advanced k-opt TSP algorithms (e.g. LKH) that require a starting tour.

 template < typename VertexListGraph, typename WeightMap,
     typename VertexIndexMap, typename TSPVertexVisitor >
 void nearest_neighbor_tour_from_vertex(const VertexListGraph& g,
     typename graph_traits< VertexListGraph >::vertex_descriptor start,
     WeightMap weightmap,
     VertexIndexMap indexmap,
     TSPVertexVisitor vis)

I also have cleaned up my original tsp_metric_approx code significantly, addressing all of Andrew Sutton's (who helped tremendously) original comments. I've also improved the test and example code for it.

I am also considering implementing Christofides 3/2 solution O(v^3) due to MWPM because it has the interesting characteristic of not requiring a complete graph as well as a lower upper bound solution, but I wanted to write a fast starter for LK first.

Let me know if there is any interest in either of these (cleaned up metric, new nearest neighbor). I haven't contributed to Boost BGL in nearly 20 years and I know much has changed, but I had interest over the holidays :-)

Dominant language
C++
Stars
396
Forks
244
Avg merge
2d 6h
Merged PRs (30d)
29

Getting set up

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.