| blob | 1978d9411c7e53741719afc2eb03fb8f0cab0e8b |
1 function tspGUI\r
2 % A GUI for the Travelling Salesman Problem. Four different heuristics are\r
3 % available to solve the TSP: Random, Nearest Neighbour, Farthest\r
4 % Neighbour and Enumerative Solving. \r
5 %\r
6 % Using the buttons on the left, a matrix containing the locations of the \r
7 % cities can be imported. The same is possible for a matrix containing \r
8 % with the distances between the cities (if the TSP is an asymmetric one).\r
9 % \r
10 % Next to importing its own data, the user can also randomly generate\r
11 % symmetric or asymmetric TSPs and choose between 5, 10, 15, 20, 25 or 30 cities.\r
12 % \r
13 % The Calculate button will then run the heuristics and calculate routes\r
14 % and distances based on the imported or generated data (the Enumerative\r
15 % Solver will only work if the number of cities does not exceed ten).\r
16 % \r
17 % For each heuristic, a plot will be made available. Using the popup menu,\r
18 % the user can switch between the different heuristics. \r
19 % \r
20 % Finally, the calculated data can be exported to the hard drive as a\r
21 % txt-file.\r
22 % \r
23 % author: Gert Thijs\r
24 % date: 9 Oct 2008\r
25 \r
26 % Initialize and hide the GUI as it is being constructed.\r
27 f = figure('Visible','off','Position',[495,325,640,640]);\r
28 \r
29 % Construct the components.\r
30 himport1 = uicontrol('Style','pushbutton',...\r
31 'String','Import Location','Position',[20,580,100,30],...\r
32 'Callback',{@import1button_Callback});\r
33 himport2 = uicontrol('Style','pushbutton',...\r
34 'String','Import Distance','Position',[20,545,100,30],...\r
35 'Callback',{@import2button_Callback});\r
36 cbh = uicontrol('Style','checkbox',...\r
37 'String','Asymmetric','Position',[20,480,100,30],...\r
38 'Value',1,'Callback',{@checkbox_Callback});\r
39 sth0 = uicontrol('Style','text','String','Number of Cities',...\r
40 'Position',[20, 465, 100, 11]);\r
41 hpopup1 = uicontrol('Style','popupmenu',...\r
42 'String',{'5','10','15','20','25','30'},...\r
43 'Position',[20,435,100,25],'Callback',{@popup_menu1_Callback});\r
44 hrandom = uicontrol('Style','pushbutton',...\r
45 'String','Random','Position',[20,400,100,30],...\r
46 'Callback',{@randombutton_Callback});\r
47 hcalc = uicontrol('Style','pushbutton',...\r
48 'String','Calculate','Position',[20,340,100,30],...\r
49 'Callback',{@calcbutton_Callback});\r
50 hpopup2 = uicontrol('Style','popupmenu',...\r
51 'String',{'Random','Nearest','Farthest','Enum'},...\r
52 'Position',[20,305,100,25],'Callback',{@popup_menu2_Callback});\r
53 hexport = uicontrol('Style','pushbutton',...\r
54 'String','Export','Position',[20,245,100,30],...\r
55 'Callback',{@exportbutton_Callback});\r
56 hreset = uicontrol('Style','pushbutton',...\r
57 'String','Reset','Position',[20,210,100,30],...\r
58 'Callback',{@resetbutton_Callback});\r
59 ha = axes('Units','pixels','Position',[200,215,400,400]);\r
60 \r
61 % Initliaze static text concerning 'Random'\r
62 sth1 = uicontrol('Style','text','String','RANDOM',...\r
63 'Position',[10, 175, 70, 11]);\r
64 sth2 = uicontrol('Style','text','String','Route:',...\r
65 'Position',[20, 160, 70, 11]);\r
66 sth3 = uicontrol('Style','text','String','Distance:',...\r
67 'Position',[20, 145, 70, 11]);\r
68 sth4 = uicontrol('Style','text','String','0',...\r
69 'Position',[90, 160, 530, 11]);\r
70 sth5 = uicontrol('Style','text','String','0',...\r
71 'Position',[90, 145, 530, 11]);\r
72 \r
73 % Initliaze static text concerning 'Nearest'\r
74 sth6 = uicontrol('Style','text','String','NEAREST',...\r
75 'Position',[10, 130, 70, 11]);\r
76 sth7 = uicontrol('Style','text','String','Route:',...\r
77 'Position',[20, 115, 70, 11]);\r
78 sth8 = uicontrol('Style','text','String','Distance:',...\r
79 'Position',[20, 100, 70, 11]);\r
80 sth9 = uicontrol('Style','text','String','0',...\r
81 'Position',[90, 115, 530, 11]);\r
82 sth10 = uicontrol('Style','text','String','0',...\r
83 'Position',[90, 100, 530, 11]);\r
84 \r
85 % Initliaze static text concerning 'Farthest'\r
86 sth11 = uicontrol('Style','text','String','FARTHEST',...\r
87 'Position',[10, 85, 70, 11]);\r
88 sth12 = uicontrol('Style','text','String','Route:',...\r
89 'Position',[20, 70, 70, 11]);\r
90 sth13 = uicontrol('Style','text','String','Distance:',...\r
91 'Position',[20, 55, 70, 11]);\r
92 sth14 = uicontrol('Style','text','String','0',...\r
93 'Position',[90, 70, 530, 11]);\r
94 sth15 = uicontrol('Style','text','String','0',...\r
95 'Position',[90, 55, 530, 11]);\r
96 \r
97 % Initliaze static text concerning 'Enumerative'\r
98 sth16 = uicontrol('Style','text','String','ENUMERATIVE',...\r
99 'Position',[10, 40, 70, 11]);\r
100 sth17 = uicontrol('Style','text','String','Route:',...\r
101 'Position',[20, 25, 70, 11]);\r
102 sth18 = uicontrol('Style','text','String','Distance:',...\r
103 'Position',[20, 10, 70, 11]);\r
104 sth19 = uicontrol('Style','text','String','0',...\r
105 'Position',[90, 25, 530, 11]);\r
106 sth20 = uicontrol('Style','text','String','0',...\r
107 'Position',[90, 10, 530, 11]);\r
108 \r
109 % Align the GUI elemtens (except the static text and the axes)\r
110 align([himport1,himport2,cbh,hrandom,hcalc,hpopup2,hexport,sth0,...\r
111 hpopup1,hreset],'Center','None');\r
112 \r
113 % Initialize the data.\r
114 coordMatrix = 0; % The coordinates of the cities\r
115 distanceMatrix = 0; % The distances between the cities \r
116 asymmetric = 1; % Whether the TSP is an asymmetric one or not\r
117 plottype = 1; % The current plot type (1=Random,2=Nearest,3=Farthest,4=Enum)\r
118 numberOfCities = 5; % Number of cities to be used in the 'Random' function\r
119 routeRandom = 0; % Initializes the 'Random' route\r
120 distanceRandom = 0; % Initializes the 'Random' distance\r
121 routeNearest = 0; % Initializes the 'Nearest' route\r
122 distanceNearest = 0; % Initializes the 'Nearest' distance\r
123 routeFarthest = 0; % Initializes the 'Farthest' route\r
124 distanceFarthest = 0; % Initializes the 'Farthest' distance\r
125 routeEnum = 0;% Initializes the 'Enumerative' route\r
126 distanceEnum = 0; % Initializes the 'Enumerative' distance\r
127 \r
128 % Initialize the GUI.\r
129 % Change units to normalized so components resize automatically.\r
130 set([f,himport1,himport2,cbh,hrandom,hcalc,hpopup2,hexport,ha,...\r
131 sth0,hpopup1,hreset],'Units','normalized');\r
132 % Assign the GUI a name to appear in the window title.\r
133 set(f,'Name','Travelling Salesman Problem','NumberTitle','off')\r
134 % Move the GUI to the center of the screen.\r
135 movegui(f,'center')\r
136 % Make the GUI visible.\r
137 set(f,'Visible','on');\r
138 \r
139 % Pop-up menu callback. Read the pop-up menu Value property to\r
140 % determine which item is currently displayed and set the number of\r
141 % cities to be generated using the 'Random' function to the current\r
142 % value.\r
143 function popup_menu1_Callback(source,eventdata) \r
144 % Determine the selected integer.\r
145 str = get(source, 'String');\r
146 val = get(source,'Value');\r
147 % Set numberOFCities to the selected integer.\r
148 switch str{val};\r
149 case '5' % User selects 5.\r
150 numberOfCities = 5;\r
151 case '10' % User selects 10.\r
152 numberOfCities = 10;\r
153 case '15' % User selects 15.\r
154 numberOfCities = 15;\r
155 case '20' % User selects 20.\r
156 numberOfCities = 20;\r
157 case '25' % User selects 25.\r
158 numberOfCities = 25;\r
159 case '30' % User selects 30.\r
160 numberOfCities = 30;\r
161 end\r
162 end\r
163 \r
164 % Pop-up menu callback. Read the pop-up menu Value property to\r
165 % determine which heuristic plot is currently displayed and make it the\r
166 % current plot type.\r
167 function popup_menu2_Callback(source,eventdata) \r
168 % Determine the selected plot type.\r
169 str = get(source, 'String');\r
170 val = get(source,'Value');\r
171 % Set current plot type to the selected one.\r
172 switch str{val};\r
173 case 'Random' % User selects Random.\r
174 plottype = 1; % Sets the plot type to Random (=1)\r
175 drawAll(routeRandom,coordMatrix)\r
176 case 'Nearest' % User selects Nearest.\r
177 plottype = 2; % Sets the plottype to Nearest (=2)\r
178 drawAll(routeNearest,coordMatrix)\r
179 case 'Farthest' % User selects Farthest.\r
180 plottype = 3; % Sets the plottype to Farthest (=3)\r
181 drawAll(routeFarthest,coordMatrix)\r
182 case 'Enum' % User selects Farthest.\r
183 plottype = 4; % Sets the plottype to Enumerative (=4)\r
184 if size(coordMatrix,1) <= 10\r
185 drawAll(routeEnum,coordMatrix) % Draw only if # of cities <=10\r
186 end\r
187 end\r
188 end\r
189 \r
190 % Push button callbacks.\r
191 \r
192 function import1button_Callback(source,eventdata) \r
193 % Open the import dialog and import a matrix with the locations of\r
194 % the cities.\r
195 importedMatrix = importLocation; % Matrix to be imported\r
196 \r
197 % Check if it's a correct location matrix\r
198 n = size(importedMatrix,1);\r
199 i = [1:n]';\r
200 if importedMatrix(:,1) == i && size(importedMatrix,2) == 3\r
201 % No problems have occured. Clear previous data and set new\r
202 % coordMatrix.\r
203 resetData;\r
204 coordMatrix = importedMatrix; \r
205 drawCities(coordMatrix);\r
206 else % Invalid input\r
207 h = warndlg('This is not a valid location matrix! Try again!',...\r
208 'Incorrect location matrix'); % Show the user a warning dialog\r
209 end\r
210 \r
211 end\r
212 \r
213 function import2button_Callback(source,eventdata) \r
214 % Open the import dialog and import a matrix with the distances\r
215 % between the cities.\r
216 importedMatrix = importDistance;\r
217 \r
218 % Check if it's a correct distance matrix\r
219 n = size(importedMatrix,1); % Get number of cities\r
220 i = zeros(n,1);\r
221 if n == size(importedMatrix,1) && n == size(importedMatrix,2) && i == diag(importedMatrix)\r
222 distanceMatrix = importedMatrix;\r
223 asymmetric = 1; % TSP is an asymmetric (will not conflict should distanceMatrix be symmetric)\r
224 set(cbh,'Value',1);\r
225 else % Invalid input\r
226 h = warndlg('This is not a valid distance matrix! Try again!',...\r
227 'Incorrect distance matrix'); % Show the user a warning dialog\r
228 distanceMatrix = 0;\r
229 end\r
230 \r
231 end\r
232 \r
233 function randombutton_Callback(source,eventdata) \r
234 % Generate a random matrix containing the locations of the cities\r
235 % and the corresponding matrix containing the distances between the\r
236 % cities. If the 'Asymmetric' checkbox is checked, this latter matrix\r
237 % will also be a random one.\r
238 \r
239 % Reset the previous routes and distances\r
240 resetData;\r
241 coordMatrix = 0;\r
242 distanceMatrix = 0;\r
243 \r
244 % Generate the random matrices\r
245 coordMatrix = generateRandomCoordMatrix(numberOfCities,100);\r
246 if asymmetric == 1\r
247 distanceMatrix = generateRandomDistanceMatrix(coordMatrix,100);\r
248 else\r
249 distanceMatrix = generateDistanceMatrix(coordMatrix);\r
250 end\r
251 drawCities(coordMatrix);\r
252 end\r
253 \r
254 function checkbox_Callback(source,eventdata) \r
255 % Controls whether asymmetric is checked or not.\r
256 if get(source,'Value') == 1\r
257 asymmetric = 1;\r
258 else\r
259 asymmetric = 0;\r
260 end\r
261 end\r
262 \r
263 function calcbutton_Callback(source,eventdata) \r
264 % Calculates the optimal route and its distance using three heuristics:\r
265 % Random, Nearest Neighbour and Farthest Neighbour.\r
266 \r
267 % Check for both a location matrix and distance matrix. If any of them\r
268 % are not present, display an error message.\r
269 passedChecks = 0; % Boolean variable\r
270 \r
271 % Check for location matrix.\r
272 if coordMatrix == 0 % No location matrix has been imported\r
273 if distanceMatrix == 0 % No distance matrix has been imported\r
274 h = warndlg('Please import a location (and distance) matrix or generate random ones!',...\r
275 'No data found');\r
276 else % A distance matrix has been imported\r
277 h = warndlg('Please import a location matrix!',...\r
278 'No location matrix found');\r
279 end\r
280 else % A location matrix has been imported\r
281 if distanceMatrix == 0 % No distance matrix has been imported\r
282 if asymmetric == 1 % The TSP is an asymmetric one\r
283 h = warndlg('Please import a distance matrix or uncheck ''Asymmetric''!',...\r
284 'No distance matrix found');\r
285 else % The TSP is symmetric\r
286 distanceMatrix = generateDistanceMatrix(coordMatrix);\r
287 passedChecks = 1; % Inputs OK. Data can be calculated\r
288 end\r
289 else % A distance matrix has been imported\r
290 if asymmetric == 1 % TSP is asymmetric\r
291 if size(coordMatrix,1)== size(distanceMatrix,1) % Check if both matrices match\r
292 passedChecks = 1; % Inputs OK. Data can be calculated\r
293 else\r
294 h = warndlg('Please import matrices that match!',...\r
295 'Matrices don''t match');\r
296 end\r
297 else % TSP is symmetric\r
298 distanceMatrix = generateDistanceMatrix(coordMatrix);\r
299 passedChecks = 1; % Inputs OK. Data can be calculated\r
300 end\r
301 end\r
302 end\r
303 \r
304 % Calculate the routes using the different heuristics if the checks\r
305 % were passed.\r
306 if passedChecks == 1\r
307 % Calculate the routes and distances\r
308 [routeRandom,distanceRandom,routeNearest,distanceNearest,...\r
309 routeFarthest,distanceFarthest,routeEnum,...\r
310 distanceEnum] = calculateHeuristics(distanceMatrix);\r
311 \r
312 % Update the static text on 'Random'\r
313 set(sth4,'String',int2str(routeRandom))\r
314 set(sth5,'String',distanceRandom)\r
315 \r
316 % Update the static text on 'Nearest'\r
317 set(sth9,'String',int2str(routeNearest))\r
318 set(sth10,'String',distanceNearest)\r
319 \r
320 % Update the static text on 'Farthest'\r
321 set(sth14,'String',int2str(routeFarthest))\r
322 set(sth15,'String',distanceFarthest)\r
323 \r
324 % Update the static text on 'Enum'\r
325 if routeEnum == 0\r
326 set(sth19,'String','Too difficult to calculate!')\r
327 set(sth20,'String','Too difficult to calculate!')\r
328 else\r
329 set(sth19,'String',int2str(routeEnum))\r
330 set(sth20,'String',distanceEnum)\r
331 end\r
332 \r
333 % Plot the cities and the route between them\r
334 if plottype == 1\r
335 drawAll(routeRandom,coordMatrix);\r
336 elseif plottype == 2\r
337 drawAll(routeNearest,coordMatrix);\r
338 elseif plottype == 3\r
339 drawAll(routeFarthest,coordMatrix);\r
340 else\r
341 if size(coordMatrix,1) <= 10\r
342 drawAll(routeEnum,coordMatrix)\r
343 end\r
344 end\r
345 end\r
346 \r
347 end\r
348 \r
349 function exportbutton_Callback(source,eventdata)\r
350 % Exports the route data\r
351 exportData(int2str(routeRandom),distanceRandom,int2str(routeNearest), ...\r
352 distanceNearest,int2str(routeFarthest),distanceFarthest,...\r
353 int2str(routeEnum),distanceEnum,coordMatrix,distanceMatrix);\r
354 end\r
355 \r
356 function resetbutton_Callback(source,eventdata)\r
357 % Resets the GUI\r
358 resetData;\r
359 coordMatrix = 0;\r
360 distanceMatrix = 0;\r
361 end\r
362 \r
363 function resetData\r
364 % Reset the data displayed on the GUI\r
365 cla; \r
366 routeRandom = 0; \r
367 distanceRandom = 0;\r
368 routeNearest = 0;\r
369 distanceNearest = 0;\r
370 routeFarthest = 0;\r
371 distanceFarthest = 0;\r
372 routeEnum = 0;\r
373 distanceEnum = 0;\r
374 set(sth4,'String','0');\r
375 set(sth5,'String','0');\r
376 set(sth9,'String','0');\r
377 set(sth10,'String','0');\r
378 set(sth14,'String','0');\r
379 set(sth15,'String','0');\r
380 set(sth19,'String','0');\r
381 set(sth20,'String','0');\r
382 end\r
383 \r
384 end\r