# Traveling Salesman Problem

Could anybody help me to convert to Mathematica 11.0?

 g = FromAdjacencyMatrix[{{0, 1, 1, 0, 1, 0, 0, 0}, {1, 0, 1, 1, 0, 1,
0, 1}, {1, 1, 0, 1, 0, 0, 1, 0}, {0, 1, 1, 0, 0, 0, 1, 1}, {1, 0,
0, 0, 0, 0, 1, 0}, {0, 1, 0, 0, 0, 0, 0, 1}, {0, 0, 1, 1, 1, 0, 0,
1}, {0, 1, 0, 1, 0, 1, 1, 0}}]
HamiltonianQ[g]
tour = TravelingSalesman[g]
edges = Partition[tour, 2, 1]
ShowGraph[Highlight[g, {edges}, HighlightedEdgeColors -> {Red}],
VertexStyle -> Disk[.05]]
Show[GraphicsArray[
Block[{\$DisplayFunction = Identity},
{
ShowGraph[g, VertexColor -> Black, VertexStyle -> Disk[.07]],
Graphics[{PointSize[.06],
ShowGraph[g, VertexColor -> Black, VertexStyle -> Disk[.07]][[
1]], ShowGraph[FromOrderedPairs[edges], EdgeColor -> Red][[
1]] /. Point[l_] :> {}}, AspectRatio -> Automatic,
PlotRange -> All]
}   ]]]


Can it be easily converted to a newer version? Thank you for your help.

• It can mostly be easily converted. See AdjacencyGraph, HamiltonianGraphQ, FindShortestTour, and HighlightGraph. The difficulty comes in converting the undirected edges to directed. – b3m2a1 Dec 5 '17 at 17:05

So the adaption is easy, but not entirely trivial so I'll post it here.

g =
AdjacencyGraph[{{0, 1, 1, 0, 1, 0, 0, 0}, {1, 0, 1, 1, 0, 1, 0,
1}, {1, 1, 0, 1, 0, 0, 1, 0}, {0, 1, 1, 0, 0, 0, 1, 1}, {1, 0, 0,
0, 0, 0, 1, 0}, {0, 1, 0, 0, 0, 0, 0, 1}, {0, 0, 1, 1, 1, 0, 0,
1}, {0, 1, 0, 1, 0, 1, 1, 0}}];
HamiltonianGraphQ[g];
tour = FindShortestTour[g][[2]];
edges =
Map[
{
# -> DirectedEdge @@ #,
Reverse[#] -> DirectedEdge @@ #
} &,
UndirectedEdge @@@ Partition[tour, 2, 1]
] // Flatten;
HighlightGraph[
EdgeList[g] /. edges,
Values[edges]
]


The only non-trivial bit was converting the UndirectedEdge into DirectedEdge.

That was still pretty easy though through a ReplaceAll.

• Can someone expand function FindShortestTour[g][[2]] because we can't use ready function from Mathematica? – Monika Dec 6 '17 at 11:22
• @Monika it’s just how Mathematica solves the traveling salesman problem. It’s the native function. – b3m2a1 Dec 6 '17 at 16:12