function travel(action)
%TRAVEL Traveling salesman problem demonstration.
%   This demo animates the solution of the
%   so-called "Traveling Salesman" problem.
%   The problem is to form a closed circuit of a
%   number of cities while traveling the shortest
%   total distance along the way.
%
%   Use the "Cities" popup menu to determine the
%   number of cities to be visited. The "Start"
%   and "Stop" buttons control the animation. Cities
%   are chosen completely at random.

%   Ned Gulley, 6-21-93
%   Copyright 1984-2004 The MathWorks, Inc.
%   $Revision: 5.21.4.4 $  $Date: 2004/12/20 16:44:41 $

% Information regarding the play status will be held in
% the axis user data according to the following table:
play= 1;
stop=-1;

if nargin<1,
    action='initialize';
end;

switch action
    case 'initialize',
        oldFigNumber=watchon;

        figNumber=figure( ...
            'Name','Travel: The Traveling Salesman Problem', ...
            'NumberTitle','off', ...
            'Visible','off', ...
            'DoubleBuffer','on', ...
            'Color', [0 0 0], ...
            'BackingStore','off');
        axes( ...
            'Units','normalized', ...
            'Position',[0.05 0.05 0.75 0.90], ...
            'Visible','off', ...
            'NextPlot','add');

        text(0,0,'Press the "Start" button to see the Traveling Salesman demo', ...
            'HorizontalAlignment','center');
        axis([-1 1 -1 1]);

        %===================================
        % Information for all buttons
        labelColor=[0.8 0.8 0.8];
        yInitPos=0.90;
        xPos=0.85;
        btnWid=0.10;
        btnHt=0.10;
        % Spacing between the button and the next command's label
        spacing=0.05;

        %====================================
        % The CONSOLE frame
        frmBorder=0.02;
        yPos=0.05-frmBorder;
        frmPos=[xPos-frmBorder yPos btnWid+2*frmBorder 0.9+2*frmBorder];
        h=uicontrol( ...
            'Style','frame', ...
            'Units','normalized', ...
            'Position',frmPos, ...
            'BackgroundColor',[0.50 0.50 0.50]);

        %====================================
        % The START button
        btnNumber=1;
        yPos=0.90-(btnNumber-1)*(btnHt+spacing);
        labelStr='Start';
        cmdStr='start';
        callbackStr='travel(''start'');';

        % Generic button information
        btnPos=[xPos yPos-spacing btnWid btnHt];
        startHndl=uicontrol( ...
            'Style','pushbutton', ...
            'Units','normalized', ...
            'Position',btnPos, ...
            'String',labelStr, ...
            'Interruptible','on', ...
            'Callback',callbackStr);

        %====================================
        % The CITIES popup button
        btnNumber=2;
        yPos=0.90-(btnNumber-1)*(btnHt+spacing);
        textStr='Cities';
        popupStr=reshape(' 15  20  25  30  35  40  45  50 ',4,8)';

        % Generic button information
        btnPos1=[xPos yPos-spacing+btnHt/2 btnWid btnHt/2];
        btnPos2=[xPos yPos-spacing btnWid btnHt/2];
        popupHndl=uicontrol( ...
            'Style','text', ...
            'Units','normalized', ...
            'Position',btnPos1, ...
            'String',textStr);
        btnPos=[xPos yPos-spacing btnWid btnHt/2];
        popupHndl=uicontrol( ...
            'Style','popup', ...
            'Value',4, ...t
            'Units','normalized', ...
            'Position',btnPos2, ...
            'String',popupStr);

        %====================================
        % The STOP button
        btnNumber=3;
        yPos=0.90-(btnNumber-1)*(btnHt+spacing);
        labelStr='Stop';
        % Setting userdata to -1 (=stop) will stop the demo.
        callbackStr='set(gca,''Userdata'',-1)';

        % Generic button information
        btnPos=[xPos yPos-spacing btnWid btnHt];
        stopHndl=uicontrol( ...
            'Style','pushbutton', ...
            'Units','normalized', ...
            'Position',btnPos, ...
            'Enable','off', ...
            'String',labelStr, ...
            'Callback',callbackStr);

        %====================================
        % The INFO button
        labelStr='Info';
        callbackStr='travel(''info'')';
        infoHndl=uicontrol( ...
            'Style','push', ...
            'Units','normalized', ...
            'Position',[xPos 0.20 btnWid 0.10], ...
            'String',labelStr, ...
            'Callback',callbackStr);

        %====================================
        % The CLOSE button
        labelStr='Close';
        callbackStr='close(gcf)';
        closeHndl=uicontrol( ...
            'Style','push', ...
            'Units','normalized', ...
            'Position',[xPos 0.05 btnWid 0.10], ...
            'String',labelStr, ...
            'Callback',callbackStr);

        % Uncover the figure
        hndlList=[startHndl popupHndl stopHndl infoHndl closeHndl];
        set(figNumber, ...
            'Visible','on', ...
            'UserData',hndlList);
        watchoff(oldFigNumber);
        figure(figNumber);

    case 'start',
        WNumber=watchon;
        axHndl=gca;
        figNumber=gcf;
        hndlList=get(figNumber,'Userdata');
        startHndl=hndlList(1);
        popupHndl=hndlList(2);
        stopHndl=hndlList(3);
        infoHndl=hndlList(4);
        closeHndl=hndlList(5);
        set([startHndl closeHndl infoHndl],'Enable','off');
        set(stopHndl,'Enable','on');
        set(axHndl,'Userdata',play);
        set(popupHndl, 'Enable', 'off');
        % ====== Start of Demo
        % Travel problem
        % This is the main program for the Traveling Salesman Problem.
        % This function makes use of the function INPOLYGON

        % Lay down a picture of the United States for graphic appeal.
        load('usborder.mat','x','y');
        % The file usborder.mat contains a map of the US in the variables
        % x and y
        cla;
        plot(x,y,'Color','cyan');
        axis off;
        axis([-0.1 1.5 -0.2 1.2]);
        hold on;
        drawnow;

        nptsStr=get(popupHndl,'String');
        nptsVal=get(popupHndl,'Value');

        npts=str2double(nptsStr(nptsVal,:));
        set(popupHndl, 'Enable', 'off');
        % ...else generate the random cities to visit
        X=[];
        Y=[];

        % Use the INPOLYGON routine to help find cities
        n=0;
        while n<npts,
            nx = rand*1.4;
            ny = rand;
            if inpolygon(nx,ny,x,y)
                X=[X; nx];
                Y=[Y; ny];
                n = n+1;
            end;
        end;
        xy=[X Y];

        % Calculate the distance matrix for all of the cities
        distmatrix = zeros(npts);
        for count1=1:npts,
            for count2=1:count1,
                x1 = xy(count1,1);
                y1 = xy(count1,2);
                x2 = xy(count2,1);
                y2 = xy(count2,2);
                distmatrix(count1,count2)=sqrt((x1-x2)^2+(y1-y2)^2);
                distmatrix(count2,count1)=distmatrix(count1,count2);
            end;
        end;

        % Generate an initial random path between those cities
        p=1:npts;

        newxy=xy(p,:);
        newxy=[newxy; newxy(1,:)];
        xdata=newxy(:,1);
        ydata=newxy(:,2);
        watchoff(WNumber);
        plot(xdata,ydata,'r.','Markersize',24);
        plothandle=plot(xdata,ydata,'yellow','LineWidth',2);
        axis off;
        drawnow;

        len=LocalPathLength(p,distmatrix);
        lenhist=len;

        while (ishandle(axHndl) == 1) && (get(axHndl,'Userdata')==play)
            drawnow;
            drawFlag=0;

            % Try a point for point swap
            % ========================
            swpt1=floor(npts*rand)+1;
            swpt2=floor(npts*rand)+1;

            swptlo=min(swpt1,swpt2);
            swpthi=max(swpt1,swpt2);

            order=1:npts;
            order(swptlo:swpthi)=order(swpthi:-1:swptlo);
            pnew = p(order);

            lennew=LocalPathLength(pnew,distmatrix);
            if lennew<len,
                p=pnew;
                len=lennew;
                drawFlag=1;
            end;
            % ========================

            % Try a single point insertion
            % ========================
            swpt1=floor(npts*rand)+1;
            swpt2=floor((npts-1)*rand)+1;

            order=1:npts;
            order(swpt1)=[];
            order=[order(1:swpt2) swpt1 order((swpt2+1):(npts-1))];
            pnew = p(order);

            lennew=LocalPathLength(pnew,distmatrix);
            if lennew<len,
                p=pnew;
                len=lennew;
                drawFlag=1;
            end

            if drawFlag,
                newxy=xy(p,:);
                newxy=[newxy; newxy(1,:)];
                xdata=newxy(:,1);
                ydata=newxy(:,2);
                if ~ishandle(plothandle)
                    % If plothandle is not valid, figure may have been deleted.
                    % Bail out in that case.
                    return;
                end
                set(plothandle,'XData',xdata,'YData',ydata);
                drawnow;
            end;
            % ========================
        end;

        if ~ishandle(figNumber)
            % If figNumber is not valid, figure may have been deleted. Bail out
            % in that case.
            return;
        end

        % ====== End of Demo
        set([startHndl closeHndl infoHndl],'Enable','on');
        set(stopHndl,'Enable','off');
        set(popupHndl, 'Enable', 'on');

    case 'info',
        helpwin(mfilename)

end;    % if strcmp(action, ...

function total=LocalPathLength(p,distmatrix)
% Calculate current path length for traveling salesman problem.
% This function calculates the total length of the current path
% p in the traveling salesman problem.

npts = size(p,2);
% This is a vectorized distance calculation
%
% We're creating two vectors: p and p([end 1:(end-1)]
% The first is the list of first cities in any leg, and the second
% is the list of destination cities for that same leg.
% (the second vector is an element-shift-right version of the first)
%
% We then use column indexing into distmatrix to create a vector of
% lengths of each leg which can then be summed.
total=sum(distmatrix((p-1)*npts + p([end 1:(end-1)])));