program tspexact6

!
! This program is an example of how the Travelling Salesman Problem may be solved
! exactly by testing all city orders.
! Author: C. Savage, for PHYS3038
! Last Updated: 24/7/03
! Adapted for 6 cities by Felix Andrews 29/7/03
!

implicit none                              ! all variables must be explicitly declared

integer :: n_repeats=1000                  ! number of times to repeat the program
integer :: i_repeat                        ! repeat index

integer :: n_cities=6                      ! number of cities
integer :: i,i1,i2,i3,i4,i5                ! loop indicies
integer :: swap_temp                       ! temporary variable used in swapping city order
integer :: n_orders=0                      ! number of city orders tried

real :: distance                           ! trip distance
real :: distance_min                       ! minimum trip distance so far

real :: time_begin, time_end               ! cpu timers

integer, dimension(6) ::  city_order       ! city ordering
integer, dimension(6,3) ::  city_store     ! saved city orderings
integer, dimension(6) ::  city_order_min   ! city ordering giving minimum distance so far
integer, dimension(6) ::  loopindex        ! loops for creating permutations of city order
real, dimension(6) :: city_x, city_y       ! city coordinates
  
  call cpu_time( time_begin )   ! CPU timer

  !
  ! city location data
  !
  
  city_x(1) = 0d0; city_y(1) = 0d0
  city_x(2) = 0d0; city_y(2) = 2d0
  city_x(3) = 1d0; city_y(3) = 1d0
  city_x(4) = 2d0; city_y(4) = 1d0
  city_x(5) = 3d0; city_y(5) = 2d0
  city_x(6) = 1.5d0; city_y(6) = 0.5d0

  distance_min = 0d0    ! initialise minimum distance found so far
  
  print *,'Running with ', n_cities, ' cities'

  !
  ! Title for diagnostic printout. Comment out if not required.
  !

  print *,'  Trip distance          City order'

loop_repeat: do i_repeat = 1, n_repeats

loop_1:  do i1 = 1, n_cities
   city_order = (/ (i,i=1,n_cities) /)   ! start with cities in numerical order
                
   !
   ! current city -> beginning of list, that city is replaced by 1
   !
   city_order(1) = i1; city_order( i1 ) = 1

   !
   ! save the current order for each iteration of the next loop
   !
   city_store(:,1) = city_order
                
loop_2:  do i2 = 2, n_cities
   city_order = city_store(:,1)  ! start from order at end of last loop

   !
   ! swap current city with that at next list position 
   !
   swap_temp = city_order(2); city_order(2) = city_order(i2); city_order(i2) = swap_temp

   city_store(:,2) = city_order   ! save the current order

loop_3:  do i3 = 3, n_cities      ! repeats plan of previous loop
   city_order = city_store(:,2)
   swap_temp = city_order(3); city_order(3) = city_order(i3); city_order(i3) = swap_temp

   city_store(:,3) = city_order   ! save the current order

loop_4:  do i4 = 4, n_cities      ! repeats plan of previous loop
   city_order = city_store(:,3)
   swap_temp = city_order(4); city_order(4) = city_order(i4); city_order(i4) = swap_temp

   city_store(:,4) = city_order   ! save the current order

loop_5:  do i5 = 5, n_cities      ! repeats plan
   city_order = city_store(:,4)
   swap_temp = city_order(5); city_order(5) = city_order(i5); city_order(i5) = swap_temp

   n_orders = n_orders +1         ! one more order tried

   !
   ! calculate trip distance
   !

   distance = 0d0 
   do i = 1, n_cities-1
      distance = distance + sqrt( &
           & ( city_x( city_order(i+1) ) -city_x( city_order(i) ) )**2 + &
           &( city_y( city_order(i+1) ) -city_y( city_order(i) ) )**2 )
   end do
              
   !
   ! add distance between first and last cities
   !
              
   distance = distance + sqrt( &
        &( city_x( city_order(n_cities) )-city_x( city_order(1) ) )**2 + &
        &( city_y( city_order(n_cities) )-city_y( city_order(1) ) )**2 )
              
   if ( distance < distance_min .or. distance_min == 0d0 ) then
      distance_min = distance
      city_order_min = city_order
   end if
                
   !
   ! prints out each city order tried
   ! comment this out if there are too many.
   ! N.B. output can really slow it down
   !
              
   !print *,distance, city_order

end do loop_5
end do loop_4    
end do loop_3
end do loop_2
end do loop_1
             
end do loop_repeat

  call cpu_time( time_end )

  !
  !  output results
  !
  print *,''  ! blank line for formatting output
  print *,'Number of city orders tried=',n_orders
  print *,'Minimum trip distance= ', distance_min
  print *,'City order is: ', city_order_min

  print *, ''  ! blank line for formatting output
  print *, 'Execution time was ', time_end - time_begin,' seconds'

end