Tour

This option attempts to find a path that visits every node

Input

format

The first line specifies the calculation required. It must contain

format tour

Links

Column	Description
1	l for link
2	vertex name
3	vertex name
4	cost

Example

format tour
l 1 2 1
l 2 3 1
l 2 4 10
l 4 3 1

Algorithm

The algorithm is an approximation of the travelling salesman algorithm.

While it is not guaranteed to find the best possible path ( in terms of cost, visiting every vertex, not revisiting vertices ) it will usually quickly find a reasonable path.

The algorithm finds a spanning tree of the graph, then does a depth search through the tree. When it becomes 'trapped' at a leaf of the tree it will 'jump' to another unvisited leaf and continue the search from there.