From 146bd6d7a53ddea97b1f4a4660db7d5b9d863454 Mon Sep 17 00:00:00 2001 From: Laurens Van Houtven Date: Fri, 10 Oct 2008 08:46:28 +0200 Subject: [PATCH] More tests + GUI Added the GUI and some of its helper functions. Loads of tests have been modified or added. On branch master Changes to be committed: new file: calculateHeuristics.m new file: exportData.m modified: ltspsEnumerativeSolver.m modified: t/001_tests_exist.t new file: t/203_typical_enumerative_solver_use.t new file: t/204_ten_point_closest_heuristic.t new file: t/205_ten_point_furthest_heuristic.t new file: t/302_pathological_furthest_heuristic_use.t modified: tspGUI.m --- calculateHeuristics.m | 23 ++++++ exportData.m | 71 ++++++++++++++++ ltspsEnumerativeSolver.m | 5 +- t/001_tests_exist.t | 2 +- t/203_typical_enumerative_solver_use.t | 41 ++++++++++ t/204_ten_point_closest_heuristic.t | 41 ++++++++++ t/205_ten_point_furthest_heuristic.t | 41 ++++++++++ t/302_pathological_furthest_heuristic_use.t | 41 ++++++++++ tspGUI.m | 121 ++++++++++++++++++---------- 9 files changed, 339 insertions(+), 47 deletions(-) create mode 100644 calculateHeuristics.m create mode 100644 exportData.m create mode 100644 t/203_typical_enumerative_solver_use.t create mode 100644 t/204_ten_point_closest_heuristic.t create mode 100644 t/205_ten_point_furthest_heuristic.t create mode 100644 t/302_pathological_furthest_heuristic_use.t diff --git a/calculateHeuristics.m b/calculateHeuristics.m new file mode 100644 index 0000000..7c6af31 --- /dev/null +++ b/calculateHeuristics.m @@ -0,0 +1,23 @@ +function [routeRandom, distanceRandom, routeNearest, distanceNearest, ... + routeFarthest, distanceFarthest, routeEnum, distanceEnum] ... + = calculateHeuristics (distanceMatrix) +% Calculate the best route and its distance using the different +% heuristics: Random, Nearest Neighbour, Farthest Neighbour and +% Enumerative (if the number of cities does not exceed ten). + +% Calculate the routes and distances using the three standard heuristics. +[routeRandom,distanceRandom] = ltspsRandomHeuristic(distanceMatrix); +[routeNearest,distanceNearest] = ltspsClosestNeighbourHeuristic(distanceMatrix); +[routeFarthest,distanceFarthest] = ltspsFurthestNeighbourHeuristic(distanceMatrix); + +% Initialize the route and distance of the Enumerative solution. +routeEnum = 0; +distanceEnum = 0; + +% Calculate using the Enumerative Solver if the number of cities does not +% exceed 10. +if size(distanceMatrix,1) <= 10 + [routeEnum,distanceEnum] = ltspsEnumerativeSolver(distanceMatrix); +end + +end diff --git a/exportData.m b/exportData.m new file mode 100644 index 0000000..29cfddc --- /dev/null +++ b/exportData.m @@ -0,0 +1,71 @@ +function exportData (randomR,randomD,nearestR,nearestD,farthestR,... + farthestD,enumR,enumD,coordMatrix,distanceMatrix) +% Prompts the user to specify a location to save the file containing the +% exported TSP data and then exports it to the specified file. +% author: Gert Thijs +% date: 9 Oct 2008 + +% Specify filepath +[FileName,PathName] = uiputfile('*.txt','Export Data','ExportData'); +filePath = [PathName FileName]; + +% Open the file in write mode +fid = fopen(filePath, 'wt'); + +% Create the header for the file +fprintf(fid,'### TRAVELLING SALESMAN PROBLEM ###\n\n'); + +% Enter the matrix data +fprintf(fid,'=== Location Matrix ===\n\n'); +fprintf(fid,'-#-\t -X-\t -Y-\t\n\n'); +fprintf(fid,'%.0f\t %.0f\t %.0f\t\n',coordMatrix'); +fprintf(fid,'\n\n'); + +fprintf(fid,'=== Distance Matrix ===\n\n'); +for i = 1:size(distanceMatrix,1) + for j = 1:size(distanceMatrix,2) + fprintf(fid,'%.0f\t',distanceMatrix(i,j)); + end + fprintf(fid,'\n'); +end +fprintf(fid,'\n\n'); + +% Enter the Random Heuristic data +fprintf(fid,'=== Random Heuristic ===\n\n'); +fprintf(fid,'Route:\t\t'); +fprintf(fid,randomR); +fprintf(fid,'\n\n'); +fprintf(fid,'Distance:\t'); +fprintf(fid,'%.3f km\n\n',randomD); + +% Enter the Nearest Neighbour Heuristic data +fprintf(fid,'=== Nearest Neighbour Heuristic ===\n\n'); +fprintf(fid,'Route:\t\t'); +fprintf(fid,nearestR); +fprintf(fid,'\n\n'); +fprintf(fid,'Distance:\t'); +fprintf(fid,'%.3f km\n\n',nearestD); + +% Enter the Farthest Neighbour Heuristic data +fprintf(fid,'=== Farthest Neighbour Heuristic ===\n\n'); +fprintf(fid,'Route:\t\t'); +fprintf(fid,farthestR); +fprintf(fid,'\n\n'); +fprintf(fid,'Distance:\t'); +fprintf(fid,'%.3f km\n\n',farthestD); + +% Enter the Enumerative Heuristic data +fprintf(fid,'=== Enumerative Heuristic ===\n\n'); +if enumD ~= 0 + fprintf(fid,'Route:\t\t'); + fprintf(fid,enumR); + fprintf(fid,'\n\n'); + fprintf(fid,'Distance:\t'); + fprintf(fid,'%.3f km\n',enumD); +else + fprintf(fid,'Route:\t\t'); + fprintf(fid,'Not Available\n\n'); + fprintf(fid,'Distance:\t'); + fprintf(fid,'Not Available\n'); +end +fclose(fid); \ No newline at end of file diff --git a/ltspsEnumerativeSolver.m b/ltspsEnumerativeSolver.m index eff2201..36c3a92 100644 --- a/ltspsEnumerativeSolver.m +++ b/ltspsEnumerativeSolver.m @@ -32,10 +32,7 @@ for i = 1:rowLimit % Place yourself in the next city. currentCity = thisRoute(1,j); end - - % Finally, travel fron this city to the start vertex (1). - currentDistance = currentDistance + distanceMatrix(currentCity,thisRoute(1)); - + if currentDistance < bestLength bestLength = currentDistance; bestRoute = [thisRoute thisRoute(1)]; diff --git a/t/001_tests_exist.t b/t/001_tests_exist.t index 3b2302c..5b94b8c 100644 --- a/t/001_tests_exist.t +++ b/t/001_tests_exist.t @@ -3,7 +3,7 @@ use strict; use Test::More qw(no_plan); -my @mfiles = qw(draw.m +my @mfiles = qw(drawAll.m drawCities.m drawRoute.m calculateRouteDistance.m diff --git a/t/203_typical_enumerative_solver_use.t b/t/203_typical_enumerative_solver_use.t new file mode 100644 index 0000000..b76df39 --- /dev/null +++ b/t/203_typical_enumerative_solver_use.t @@ -0,0 +1,41 @@ +use warnings; +use strict; + +use Test::More qw(no_plan); +use Digest::MD5; +use Data::Dumper; + +require 't/lib/Common.pm'; + +my $erm; +my $tm; +my $d = Digest::MD5->new; + +{ +my $cmd = "M = [1 2 3; 2 3 2; 3 4 5; 4 5 4];"; +$cmd .= "D=generateDistanceMatrix(M); "; +$cmd .= "ltspsEnumerativeSolver(D);"; +run_matlab_cmd($cmd); +} + + +{## + $erm = "output didn't match what I expected"; + $tm = "typical enumerative solver use (4 cities in a square)"; + + my $expected_fn = "t/expected_output/203_typical_enumerative_solver_use"; + + open(my $expected, "<", $expected_fn); + open(my $got, "<", "t/matlab_output/output"); + + $d->addfile($expected); + my $d_expected = $d->hexdigest; + + $d->addfile($got); + my $d_got = $d->hexdigest; + + print Dumper($d_expected); + print Dumper($d_got); + + ok(($d_expected eq $d_got or die($erm)),$tm); +}## diff --git a/t/204_ten_point_closest_heuristic.t b/t/204_ten_point_closest_heuristic.t new file mode 100644 index 0000000..b8bc7ca --- /dev/null +++ b/t/204_ten_point_closest_heuristic.t @@ -0,0 +1,41 @@ +use warnings; +use strict; + +use Test::More qw(no_plan); +use Digest::MD5; +use Data::Dumper; + +require 't/lib/Common.pm'; + +my $erm; +my $tm; +my $d = Digest::MD5->new; + +{ +my $cmd = "M = [1 7 7; 2 7 10; 3 3 8; 4 3 2; 5 7 5; 6 5 7; 7 8 4; 8 7 5; 9 9 9; 10 3 7];"; +$cmd .= "D = generateDistanceMatrix(M); "; +$cmd .= "ltspsClosestNeighbourHeuristic(M);"; +run_matlab_cmd($cmd); +} + +## +$erm = "output didn't match what I expected"; +$tm = "ten point closest neighbour heuristic use"; + +my $expected_fn = "t/expected_output/204_ten_point_closest_heuristic"; + +open(my $expected, "<", $expected_fn); +open(my $got, "<", "t/matlab_output/output"); + +$d->addfile($expected); +my $d_expected = $d->hexdigest; + +$d->addfile($got); +my $d_got = $d->hexdigest; + +print Dumper($d_expected); +print Dumper($d_got); + +ok(($d_expected eq $d_got or die($erm)),$tm); +## + diff --git a/t/205_ten_point_furthest_heuristic.t b/t/205_ten_point_furthest_heuristic.t new file mode 100644 index 0000000..e790462 --- /dev/null +++ b/t/205_ten_point_furthest_heuristic.t @@ -0,0 +1,41 @@ +use warnings; +use strict; + +use Test::More qw(no_plan); +use Digest::MD5; +use Data::Dumper; + +require 't/lib/Common.pm'; + +my $erm; +my $tm; +my $d = Digest::MD5->new; + +{ +my $cmd = "M = [1 7 7; 2 7 10; 3 3 8; 4 3 2; 5 7 5; 6 5 7; 7 8 4; 8 7 5; 9 9 9; 10 3 7];"; +$cmd .= "D = generateDistanceMatrix(M); "; +$cmd .= "ltspsFurthestNeighbourHeuristic(M);"; +run_matlab_cmd($cmd); +} + +## +$erm = "output didn't match what I expected"; +$tm = "ten point furthest neighbour heuristic use"; + +my $expected_fn = "t/expected_output/205_ten_point_furthest_heuristic"; + +open(my $expected, "<", $expected_fn); +open(my $got, "<", "t/matlab_output/output"); + +$d->addfile($expected); +my $d_expected = $d->hexdigest; + +$d->addfile($got); +my $d_got = $d->hexdigest; + +print Dumper($d_expected); +print Dumper($d_got); + +ok(($d_expected eq $d_got or die($erm)),$tm); +## + diff --git a/t/302_pathological_furthest_heuristic_use.t b/t/302_pathological_furthest_heuristic_use.t new file mode 100644 index 0000000..a057ca8 --- /dev/null +++ b/t/302_pathological_furthest_heuristic_use.t @@ -0,0 +1,41 @@ +use warnings; +use strict; + +use Test::More qw(no_plan); +use Digest::MD5; +use Data::Dumper; + +require 't/lib/Common.pm'; + +my $erm; +my $tm; +my $d = Digest::MD5->new; + +{ +my $cmd = "M = [1 0 0; 2 0 0; 3 0 0; 4 0 0];"; +$cmd .= "D=generateDistanceMatrix(M); "; +$cmd .= "ltspsFurthestNeighbourHeuristic(M);"; +run_matlab_cmd($cmd); +} + +## +$erm = "output didn't match what I expected"; +$tm = "pathological furthest neighbour heuristic use (4 cities on the same point)"; + +my $expected_fn = "t/expected_output/302_pathological_furthest_heuristic_use"; + +open(my $expected, "<", $expected_fn); +open(my $got, "<", "t/matlab_output/output"); + +$d->addfile($expected); +my $d_expected = $d->hexdigest; + +$d->addfile($got); +my $d_got = $d->hexdigest; + +print Dumper($d_expected); +print Dumper($d_got); + +ok(($d_expected eq $d_got or die($erm)),$tm); +## + diff --git a/tspGUI.m b/tspGUI.m index 2a14180..1978d94 100644 --- a/tspGUI.m +++ b/tspGUI.m @@ -1,6 +1,27 @@ -function testGUI -% TEST_GUI A simple test GUI, meant to experiment with MATLAB's -% GUI elements and syntax. +function tspGUI +% A GUI for the Travelling Salesman Problem. Four different heuristics are +% available to solve the TSP: Random, Nearest Neighbour, Farthest +% Neighbour and Enumerative Solving. +% +% Using the buttons on the left, a matrix containing the locations of the +% cities can be imported. The same is possible for a matrix containing +% with the distances between the cities (if the TSP is an asymmetric one). +% +% Next to importing its own data, the user can also randomly generate +% symmetric or asymmetric TSPs and choose between 5, 10, 15, 20, 25 or 30 cities. +% +% The Calculate button will then run the heuristics and calculate routes +% and distances based on the imported or generated data (the Enumerative +% Solver will only work if the number of cities does not exceed ten). +% +% For each heuristic, a plot will be made available. Using the popup menu, +% the user can switch between the different heuristics. +% +% Finally, the calculated data can be exported to the hard drive as a +% txt-file. +% +% author: Gert Thijs +% date: 9 Oct 2008 % Initialize and hide the GUI as it is being constructed. f = figure('Visible','off','Position',[495,325,640,640]); @@ -37,6 +58,7 @@ function testGUI 'Callback',{@resetbutton_Callback}); ha = axes('Units','pixels','Position',[200,215,400,400]); + % Initliaze static text concerning 'Random' sth1 = uicontrol('Style','text','String','RANDOM',... 'Position',[10, 175, 70, 11]); sth2 = uicontrol('Style','text','String','Route:',... @@ -48,6 +70,7 @@ function testGUI sth5 = uicontrol('Style','text','String','0',... 'Position',[90, 145, 530, 11]); + % Initliaze static text concerning 'Nearest' sth6 = uicontrol('Style','text','String','NEAREST',... 'Position',[10, 130, 70, 11]); sth7 = uicontrol('Style','text','String','Route:',... @@ -59,6 +82,7 @@ function testGUI sth10 = uicontrol('Style','text','String','0',... 'Position',[90, 100, 530, 11]); + % Initliaze static text concerning 'Farthest' sth11 = uicontrol('Style','text','String','FARTHEST',... 'Position',[10, 85, 70, 11]); sth12 = uicontrol('Style','text','String','Route:',... @@ -70,7 +94,8 @@ function testGUI sth15 = uicontrol('Style','text','String','0',... 'Position',[90, 55, 530, 11]); - sth16 = uicontrol('Style','text','String','ENUMS',... + % Initliaze static text concerning 'Enumerative' + sth16 = uicontrol('Style','text','String','ENUMERATIVE',... 'Position',[10, 40, 70, 11]); sth17 = uicontrol('Style','text','String','Route:',... 'Position',[20, 25, 70, 11]); @@ -81,6 +106,7 @@ function testGUI sth20 = uicontrol('Style','text','String','0',... 'Position',[90, 10, 530, 11]); + % Align the GUI elemtens (except the static text and the axes) align([himport1,himport2,cbh,hrandom,hcalc,hpopup2,hexport,sth0,... hpopup1,hreset],'Center','None'); @@ -90,14 +116,14 @@ function testGUI asymmetric = 1; % Whether the TSP is an asymmetric one or not plottype = 1; % The current plot type (1=Random,2=Nearest,3=Farthest,4=Enum) numberOfCities = 5; % Number of cities to be used in the 'Random' function - routeRandom = 0; - distanceRandom = 0; - routeNearest = 0; - distanceNearest = 0; - routeFarthest = 0; - distanceFarthest = 0; - routeEnum = 0; - distanceEnum = 0; + routeRandom = 0; % Initializes the 'Random' route + distanceRandom = 0; % Initializes the 'Random' distance + routeNearest = 0; % Initializes the 'Nearest' route + distanceNearest = 0; % Initializes the 'Nearest' distance + routeFarthest = 0; % Initializes the 'Farthest' route + distanceFarthest = 0; % Initializes the 'Farthest' distance + routeEnum = 0;% Initializes the 'Enumerative' route + distanceEnum = 0; % Initializes the 'Enumerative' distance % Initialize the GUI. % Change units to normalized so components resize automatically. @@ -118,7 +144,7 @@ function testGUI % Determine the selected integer. str = get(source, 'String'); val = get(source,'Value'); - % Set numberOFCities to the selected data set. + % Set numberOFCities to the selected integer. switch str{val}; case '5' % User selects 5. numberOfCities = 5; @@ -139,10 +165,10 @@ function testGUI % determine which heuristic plot is currently displayed and make it the % current plot type. function popup_menu2_Callback(source,eventdata) - % Determine the selected data set. + % Determine the selected plot type. str = get(source, 'String'); val = get(source,'Value'); - % Set current data to the selected data set. + % Set current plot type to the selected one. switch str{val}; case 'Random' % User selects Random. plottype = 1; % Sets the plot type to Random (=1) @@ -156,7 +182,7 @@ function testGUI case 'Enum' % User selects Farthest. plottype = 4; % Sets the plottype to Enumerative (=4) if size(coordMatrix,1) <= 10 - drawAll(routeEnum,coordMatrix) + drawAll(routeEnum,coordMatrix) % Draw only if # of cities <=10 end end end @@ -166,7 +192,7 @@ function testGUI function import1button_Callback(source,eventdata) % Open the import dialog and import a matrix with the locations of % the cities. - importedMatrix = importLocation; + importedMatrix = importLocation; % Matrix to be imported % Check if it's a correct location matrix n = size(importedMatrix,1); @@ -177,10 +203,9 @@ function testGUI resetData; coordMatrix = importedMatrix; drawCities(coordMatrix); - else + else % Invalid input h = warndlg('This is not a valid location matrix! Try again!',... 'Incorrect location matrix'); % Show the user a warning dialog - coordMatrix = 0; end end @@ -190,14 +215,14 @@ function testGUI % between the cities. importedMatrix = importDistance; - % Check if it's a correct distance-matrix - n = size(importedMatrix,1); + % Check if it's a correct distance matrix + n = size(importedMatrix,1); % Get number of cities i = zeros(n,1); if n == size(importedMatrix,1) && n == size(importedMatrix,2) && i == diag(importedMatrix) distanceMatrix = importedMatrix; - asymmetric = 1; + asymmetric = 1; % TSP is an asymmetric (will not conflict should distanceMatrix be symmetric) set(cbh,'Value',1); - else + else % Invalid input h = warndlg('This is not a valid distance matrix! Try again!',... 'Incorrect distance matrix'); % Show the user a warning dialog distanceMatrix = 0; @@ -208,7 +233,7 @@ function testGUI function randombutton_Callback(source,eventdata) % Generate a random matrix containing the locations of the cities % and the corresponding matrix containing the distances between the - % cities. If the 'Asymmetric'-checkbox is checked, this latter matrix + % cities. If the 'Asymmetric' checkbox is checked, this latter matrix % will also be a random one. % Reset the previous routes and distances @@ -241,37 +266,37 @@ function testGUI % Check for both a location matrix and distance matrix. If any of them % are not present, display an error message. - passedChecks = 0; + passedChecks = 0; % Boolean variable % Check for location matrix. - if coordMatrix == 0 - if distanceMatrix == 0 + if coordMatrix == 0 % No location matrix has been imported + if distanceMatrix == 0 % No distance matrix has been imported h = warndlg('Please import a location (and distance) matrix or generate random ones!',... 'No data found'); - else + else % A distance matrix has been imported h = warndlg('Please import a location matrix!',... 'No location matrix found'); end - else - if distanceMatrix == 0 - if asymmetric == 1 + else % A location matrix has been imported + if distanceMatrix == 0 % No distance matrix has been imported + if asymmetric == 1 % The TSP is an asymmetric one h = warndlg('Please import a distance matrix or uncheck ''Asymmetric''!',... 'No distance matrix found'); - else + else % The TSP is symmetric distanceMatrix = generateDistanceMatrix(coordMatrix); - passedChecks = 1; + passedChecks = 1; % Inputs OK. Data can be calculated end - else - if asymmetric == 1 - if size(coordMatrix,1)==size(distanceMatrix,1) - passedChecks = 1; + else % A distance matrix has been imported + if asymmetric == 1 % TSP is asymmetric + if size(coordMatrix,1)== size(distanceMatrix,1) % Check if both matrices match + passedChecks = 1; % Inputs OK. Data can be calculated else h = warndlg('Please import matrices that match!',... 'Matrices don''t match'); end - else + else % TSP is symmetric distanceMatrix = generateDistanceMatrix(coordMatrix); - passedChecks = 1; + passedChecks = 1; % Inputs OK. Data can be calculated end end end @@ -279,19 +304,24 @@ function testGUI % Calculate the routes using the different heuristics if the checks % were passed. if passedChecks == 1 + % Calculate the routes and distances [routeRandom,distanceRandom,routeNearest,distanceNearest,... routeFarthest,distanceFarthest,routeEnum,... distanceEnum] = calculateHeuristics(distanceMatrix); + % Update the static text on 'Random' set(sth4,'String',int2str(routeRandom)) set(sth5,'String',distanceRandom) + % Update the static text on 'Nearest' set(sth9,'String',int2str(routeNearest)) set(sth10,'String',distanceNearest) - + + % Update the static text on 'Farthest' set(sth14,'String',int2str(routeFarthest)) set(sth15,'String',distanceFarthest) + % Update the static text on 'Enum' if routeEnum == 0 set(sth19,'String','Too difficult to calculate!') set(sth20,'String','Too difficult to calculate!') @@ -316,6 +346,13 @@ function testGUI end + function exportbutton_Callback(source,eventdata) + % Exports the route data + exportData(int2str(routeRandom),distanceRandom,int2str(routeNearest), ... + distanceNearest,int2str(routeFarthest),distanceFarthest,... + int2str(routeEnum),distanceEnum,coordMatrix,distanceMatrix); + end + function resetbutton_Callback(source,eventdata) % Resets the GUI resetData; @@ -324,7 +361,7 @@ function testGUI end function resetData - % Controls whether asymmetric is checked or not. + % Reset the data displayed on the GUI cla; routeRandom = 0; distanceRandom = 0; @@ -344,4 +381,4 @@ function testGUI set(sth20,'String','0'); end -end \ No newline at end of file +end -- 2.11.4.GIT