Satsuma
a delicious .NET graph library

Suppose that we have a bidirectional complete directed graph (that is, for each pair of nodes a, b there is a directed arc from a to b) and a cost function on the arcs.
We would like to find a minimum cost Hamiltonian cycle in the graph. This is called the traveling salesman problem.
The TSPrelated classes in Satsuma are: CheapestLinkTsp<TNode>, InsertionTsp<TNode>, Opt2Tsp<TNode>, HamiltonianCycle. They do not generally use the basic Satsuma types Node, Arc and IGraph, as the input graph in a TSP is always a bidirectional complete directed graph. Instead, there is a generic type parameter which is the type of the nodes to visit. TSPsolving classes like InsertionTsp<TNode> accept a collection of nodes and a cost function defined on node pairs, and produce a costeffective visiting order of the supplied nodes.
TSP cost functions must always be finite. The algorithms generally perform well if the cost function is symmetric (that is, the cost of traveling from a to b is the same as traveling from b to a). In particular, they perform the best for metric cost functions (that is, the triangle inequality must hold as well).
The following example demonstrates how a reasonably cheap tour on Euclidean points can be found using a Satsuma TSP solver: