WOLFRAM

Wolfram Language & System Documentation Center

Chinese Postman Tours

Plan an inspection tour to visit border posts shared by countries at least once and minimize the travel length.

    
Construct a country graph of Africa:
Wolfram Language code: africa = CountryData["Africa"];
Wolfram Language code: borderQ[cont1_, cont2_] := MemberQ[CountryData[cont1, "BorderingCountries"], CountryData[cont2]];
Wolfram Language code: adjm = Table[If[borderQ[u, v] || borderQ[v, u], 1, 0], {u, africa}, {v, africa}];
Wolfram Language code: coords = Reverse[CountryData[#, "CenterCoordinates"]& /@ africa, 2];
Wolfram Language code: southgraph = AdjacencyGraph[africa, adjm, VertexCoordinates -> coords, EdgeStyle -> Directive[Thickness[.003], White], VertexStyle -> Directive[EdgeForm[GrayLevel[.8]], GrayLevel[.7]], VertexSize -> .8];
Find a Chinese postman tour of Africa:
Wolfram Language code: tour = FindPostmanTour[southgraph];
Show the tour:
Wolfram Language code: path = tour[[1, All, 1]]; vrule = Thread[VertexList[southgraph] -> Range[VertexCount[southgraph]]]; route = GraphEmbedding[southgraph][[Join[path, {path[[1]]}] /. vrule]];
Wolfram Language code: Show[{Graphics[{LightGray, CountryData[#, "Polygon"] & /@ africa}], HighlightGraph[southgraph, path[[1]], VertexLabels -> "Name"], Graphics[{Arrowheads[Join[{0}, ConstantArray[.018, 45]]], GrayLevel[.3], Arrow[BSplineCurve[route, SplineDegree -> 2]]}]}]