Back in around 2009/2010, my former colleague Libor Sarga (a beginner in TeX at that time), asked me if I could help him to get a vector form of his results obtained from Concorde. He was writing a chapter for a book about traveling salesman problem (TSP; optimization; operations research). Could it be achieved somehow?

up vote 9 down vote accepted

Concorde is quite effective tool for handling the TSP problem. We (Czechs and Slovaks) like it, because it implements Borůvka's algorithm and one of the developers and LaTeXists is Václav Chvátal, a serious mathematician by profession born in Czechoslovakia.

The problem is that we cannot File->Save as... our results to a vector format, e.g. PS, PDF, SVG as it is common these days.

If we use a printing driver (e.g. PDFCreator), we are still getting a raster format of the graphs in the PDF file.

I have noticed that we can save results to files with tsp (File->Save) and cyc (File->Save Tour) extensions, those files are written in plain text. My first version took those two files and generated a set of files suitable for the pgfplots package. One of the problems was that nodes are printed from 1, but the cycle is indexed from 0. The next problem is that Concorde can handle other operations research problems next to TSP, but the results are not a part of those two files.

By an accident, I used File->Save as... from the menu and I saved the results to a file with the txt extension. Such a file contains all nodes and edges we are getting in the program. I rewrote my initial version from Bash to Lua, I set several variables: we can get a graph with/out text in the nodes and with/out distance in the middle of the edges. I also programmed a basic for cycle, so we can process several input files from Concorde with their own setting.

The Lua snippet generates a series of TeX files using the pgfplots package by Chris­tian Feuer­sänger. It is easy to change graph parameters and a graph style later, therefore I didn't use basic TikZ commands.

I enclose a Lua snippet, TeX files and if you cannot run Concorde for any reason I enclose input files as well. We run texlua and any LaTeX engine, e.g.

texlua mal-concorde.lua
lualatex mal-nodes-edges.tex

This is the Lua snippet, the mal-concorde.lua file:

-- A Lua snippet for parsing text files (Save as...) from Concorde.
-- http://www.math.uwaterloo.ca/tsp/concorde.html
-- 2015-03-27, version 2, mal
-- (Version 1 was created around 2009 in Bash without any features, mal.)

-- Structure:
-- the middle part of the name of the file, 
-- do we want text in nodes (nil, anything else), 
-- do we want text in edges (nil, anything else)
data={
   {1,nil,nil},
   {1,1,nil},
   {1,nil,1},
   {1,1,1},
   {3,nil,nil},
   {4,nil,nil},   
   {2,nil,nil},
   }
-- Writing commands to draw graphs at a TeX level...
fortex=io.open("fortex.tex","w")

-- Finding minimum and maximum of a specific column
function minandmax(data,column)
for item=1,#data do
itemhere=tonumber(data[item][column])
if item==1 then malmin=itemhere; malmax=itemhere end
if malmin>itemhere then malmin=itemhere end
if malmax<itemhere then malmax=itemhere end
end -- for
return malmin, malmax
end -- function, minmax


-- The major cycle over data...
for majorcycle,keydata in pairs(data) do 
-- A cycle over available files and settings

nodes={} -- empty a set of nodes
edges={} -- empty a set of edges
textnodes=keydata[2] -- nil or 1, do we want text in nodes?
textedges=keydata[3] -- nil or 1, do we want text in edges?

-- Which file to load and where to save the results
file="concorde"..keydata[1]
filein=file.."-input.txt"
fileout=file.."-"..majorcycle.."-output.tex"
fortex:write("\\callforme "..fileout.."\n")

texts="" -- a temporary string for storing results
print("Converting text file ("..filein..")...")

-- Let's read and parse the first line of a text file from Concorde
file=io.open(filein)
firstline=file:read("*l") -- "*all", number of nodes and edges
nonodes,noedges=string.match(firstline,"(.-) (.-)$")
-- Reading and parsing nodes
for nodeline=1,nonodes do
line=file:read("*l")
x,y=string.match(line,"(.-) (.-)$")
nodes[nodeline]={x,y}
texts=texts.."\\coordinate ("..nodeline..") at (axis cs: "..x..", "..y..");\n"
end
-- Finding minimum and maximum in two columns (x, y)
xmin,xmax=minandmax(nodes,1)
ymin,ymax=minandmax(nodes,2)
-- print(xmin,xmax,ymin,ymax) -- printing coordinates of the "bounding box" from data

-- Loading and parsing edges
-- Is there a cycle from edges?
cycle=1
for edgeline=1,noedges do
line=file:read("*l")
from,to,distance=string.match(line,"(.-) (.-) (.-)$")
edges[edgeline]={from+1,to+1,distance}
if edgeline>1 then
   if edges[edgeline][1]~=edges[edgeline-1][2] then cycle=nil end
   end
if edgeline==noedges then
   if edges[edgeline][2]~=edges[1][1] then cycle=nil end
   end
end
file:close()

-- Writing edges with a specific style
if cycle then style="tour" else style="line" end
for edgeline=1,noedges do
texts=texts.."\\draw ["..style.."] ("..edges[edgeline][1]..")--("..edges[edgeline][2]..")"
if cycle and edgeline==noedges then texts=texts.."\\draw ["..style.."] ("..edges[noedges][2]..")--("..edges[1][1]..")" end
if textedges then extendstyle=" node [linetext,pos=0.5] {"..edges[edgeline][3].."}" else extendstyle="" end
texts=texts..extendstyle..";\n"
end

-- Writing nodes with a specific style
if textnodes then nstyle="nodetext" else nstyle="node" end
for nodeline=1,nonodes do
if textnodes then enterhere=nodeline else enterhere="" end
texts=texts.."\\node ["..nstyle.."] at ("..nodeline..") {"..enterhere.."};\n"
end

-- Creating a TeX file
writeme=io.open(fileout, "w")
writeme:write("\\begin{axis}[xmin="..xmin..", xmax="..xmax..", ymin="..ymin..", ymax="..ymax..",\n   axis equal image, enlargelimits]\n")
writeme:write(texts)
writeme:write("\\end{axis}\n")
writeme:close()

end -- for, majorcycle over files and settings

-- Close that support file which is loaded by TeX little later.
fortex:close()

This is the TeX core file, the mal-nodes-edges.tex file:

% *latex mal-nodes-edges.tex
\documentclass[a4paper]{article}
\pagestyle{empty}
\usepackage{pgfplots}
\parindent=0pt
\addtolength{\voffset}{-1in}
\addtolength{\hoffset}{-1in}
\textwidth=1.5\textwidth
\pgfplotsset{width=\textwidth, height=\textheight, compat=1.12}
\begin{document}

\def\callforme#1 {%
\newpage
\begin{tikzpicture}
  [node/.style={draw=blue, circle, fill=white, outer sep=0pt, inner sep=1.5pt},
  nodetext/.style={node, text height=2ex, text depth=0.5ex, font=\small\bfseries},
  line/.style={black},
  tour/.style={red},
  linetext/.style={fill=white, circle, inner sep=0.5pt, outer sep=0pt, font=\footnotesize},
  ]
\input #1
\end{tikzpicture}}

\input fortex.tex

\end{document}

The snippet generates the fortex.tex file, the content looks like this:

\callforme concorde1-1-output.tex
\callforme concorde1-2-output.tex
\callforme concorde1-3-output.tex
\callforme concorde1-4-output.tex
\callforme concorde3-5-output.tex
\callforme concorde4-6-output.tex
\callforme concorde2-7-output.tex

The Lua code also generates a series of output TeX files, the structure looks like this:

\begin{axis}[xmin=9.006012, xmax=91.778314, ymin=1.394696, ymax=97.01529,
   axis equal image, enlargelimits]
\coordinate (1) at (axis cs: 87.951292, 2.658162);
\coordinate (2) at (axis cs: 33.466597, 66.682943);
[... omitted ...]
\coordinate (26) at (axis cs: 56.185567, 74.907063);
\draw [line] (1)--(15);
\draw [line] (1)--(20);
[... omitted ...]
\draw [line] (24)--(25);
\draw [line] (25)--(26);
\node [node] at (1) {};
\node [node] at (2) {};
[... omitted ...]
\node [node] at (25) {};
\node [node] at (26) {};
\end{axis}

The snippet finds the bounding box of the data and generates a series of nodes and edges with/out the name of the nodes and the edge distances. The setting is done at a Lua level in the data variable (that's a Lua table).

The first input file looks like this, for example this is the concorde1-input.txt file. The other files look similar in structure, we can download them from this server.

26 67
87.951292 2.658162
33.466597 66.682943
91.778314 53.807184
18.127148 53.717472
9.006012 81.185339
20.032350 2.761925
77.181310 31.922361
41.059603 32.578509
18.692587 97.015290
51.658681 33.808405
44.563128 47.541734
37.806330 50.599689
9.961241 20.337535
28.186895 70.415357
62.129582 6.183050
50.376904 42.796106
71.285134 43.671987
34.156316 49.113437
85.201575 71.837519
27.466659 1.394696
30.756014 76.579926
42.697595 79.925651
42.525773 78.624535
37.371134 66.914498
47.079038 68.401487
56.185567 74.907063
0 14 26
0 19 60
0 6 31
0 2 51
1 17 18
1 11 17
1 23 4
1 3 20
1 13 6
1 20 10
2 16 23
2 6 26
2 18 19
3 17 17
3 12 34
3 13 19
3 4 29
4 13 22
4 20 22
4 8 19
4 12 61
5 19 8
5 12 20
6 14 30
6 9 26
6 16 13
7 14 34
7 19 34
7 9 11
7 12 33
7 15 14
7 10 15
7 17 18
8 20 24
8 21 29
8 25 44
8 18 71
9 14 30
9 15 9
9 16 22
10 15 8
10 17 11
10 11 7
10 24 21
11 17 4
11 23 16
11 24 20
12 19 26
12 17 38
13 20 7
14 19 35
15 16 21
15 24 26
16 18 31
16 24 35
16 25 35
18 25 29
20 23 12
20 22 12
20 21 12
21 25 14
21 22 1
22 23 13
22 24 11
22 25 14
23 24 10
24 25 11 

I enclose a preview of some results with testing data sets to get a better idea of the generated outputs. If edges consist a cycle/tour, Lua changes its style (from black to red).

  1. Delaunay Triangulation, without node names, without distances.
  2. Delaunay Triangulation, with node names, without distances.
  3. Delaunay Triangulation, without node names, with distances.
  4. Delaunay Triangulation, with node names, with distances.
  5. Min Spanning Tree, without node names, without distances.
  6. Optimal Tour (TSP), problem set 1, without node names, without distances.
  7. Optimal Tour (TSP), problem set 2, without node names, without distances.

several examples of the graph

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.