tsp_tour

Contents

tsp_tour#

graph_tool.topology.tsp_tour(g, src, weight=None)[source]#

Return a traveling salesman tour of the graph, which is guaranteed to be twice as long as the optimal tour in the worst case.

Parameters:
gGraph

Graph to be used. The graph must be undirected.

srcVertex

The source (and target) of the tour.

weightEdgePropertyMap (optional, default: None)

Edge weights.

Returns:
tournumpy.ndarray

List of vertex indices corresponding to the tour.

Notes

The algorithm runs with \(O(E\log V)\) complexity.

References

Examples

>>> g = gt.lattice([10, 10])
>>> tour = gt.tsp_tour(g, g.vertex(0))
>>> print(tour)
[ 0  1  2 11 12 21 22 31 32 41 42 51 52 61 62 71 72 81 82 83 73 63 53 43
 33 23 13  3  4  5  6  7  8  9 19 29 39 49 59 69 79 89 14 24 34 44 54 64
 74 84 91 92 93 94 95 85 75 65 55 45 35 25 15 16 17 18 27 28 37 38 47 48
 57 58 67 68 77 78 87 88 97 98 99 26 36 46 56 66 76 86 96 10 20 30 40 50
 60 70 80 90  0]
Contents