如何从 Concorde 程序中获取矢量图形？

Question

协和号是处理 TSP 问题的非常有效的工具。我们（捷克人和斯洛伐克人）喜欢它，因为它实现了 Borůvka 的算法，并且其中一位开发人员和 LaTeXists 是瓦茨拉夫·赫瓦塔尔，出生于捷克斯洛伐克的一位严肃的职业数学家。

问题是我们无法将File->Save as...结果转换为矢量格式，例如现在常见的 PS、PDF、SVG。

如果我们使用打印驱动程序（例如PDF创建器），我们仍然会得到 PDF 文件中图形的光栅格式。

我注意到我们可以将结果保存到扩展名为tsp( File->Save) 和cyc( File->Save Tour) 的文件中，这些文件以纯文本形式编写。我的第一个版本采用了这两个文件并生成了一组适合pgfplots包。其中一个问题是节点从 1 开始打印，但循环从 0 开始索引。下一个问题是 Concorde 可以处理 TSP 之后的其他运筹学问题，但结果不是这两个文件的一部分。

偶然间，我使用了File->Save as...菜单上的，并将结果保存到带有txt扩展名的文件中。这样的文件包含我们在程序中获取的所有节点和边。我将最初的版本从 Bash 重写为 Lua，设置了几个变量：我们可以得到一个节点中有/没有文本、边中间有/没有距离的图形。我还编写了一个基本for循环，这样我们就可以用自己的设置处理来自 Concorde 的几个输入文件。

Lua 代码片段使用pgfplotsChristian Feuersänger 的软件包。稍后可以轻松更改图形参数和图形样式，因此我没有使用基本的 TikZ 命令。

我附上了一个 Lua 代码片段、TeX 文件，如果您因任何原因无法运行 Concorde，我也会附上输入文件。我们运行texlua任何 LaTeX 引擎，例如

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

这是 Lua 代码片段，文件mal-concorde.lua：

-- 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()

这是 TeX 核心文件，该mal-nodes-edges.tex文件：

% *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}

该代码片段生成文件fortex.tex，内容如下：

\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

Lua代码还会生成一系列输出TeX文件，结构如下：

\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}

该代码片段查找数据的边界框并生成一系列节点和边（带/不带节点名称和边距离）。该设置在变量data（即 Lua 表）中的 Lua 级别完成。

第一个输入文件如下所示，例如，这是文件concorde1-input.txt。其他文件的结构类似，我们可以从中下载它们此服务器。

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

我附上了一些带有测试数据集的结果预览，以便更好地了解生成的输出。如果边构成一个循环/路线，Lua 会改变其样式（从黑色变为红色）。

德劳内三角剖分，没有节点名称，没有距离。
德劳内三角剖分，带有节点名称，但没有距离。
德劳内三角剖分，没有节点名称，有距离。
德劳内三角剖分，带有节点名称和距离。
最小生成树，没有节点名称，没有距离。
最优游览（TSP），问题集 1，没有节点名称，没有距离。
最优游览（TSP），问题集 2，没有节点名称，没有距离。

图表的几个例子

Answer 1