PROGRAM NNA
! Copyright 2008 Matthew Norton
!
!    This program is free software; you can redistribute it and/or modify
!    it under the terms of the GNU General Public License as published by
!    the Free Software Foundation; either version 2 of the License, or
!    (at your option) any later version.
!
!    This program is distributed in the hope that it will be useful,
!    but WITHOUT ANY WARRANTY; without even the implied warranty of
!    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
!    GNU General Public License for more details.
!
!    You should have received a copy of the GNU General Public License
!    along with this program; if not, write to the Free Software
!    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
!
! NOTE: This is in FORTRAN 90 and you will need a FORTRAN 90 complier to run this code
! ------------------------------------------------------------------------------------
!
! This program attempts to solve the traveling salesman problem by using the nearest 
! neighbor algorithm. This program starts at every vertex of teh input graph in an 
! attempt to find the shortest path between the vertices. The input to this program is
! a modified adjacency matrix, where the i, j element of the matrix is the distance between
! vertex i and vertes j. This matrix is inputted through the file NNInp.txt. The program 
! automatically finds the number of rows in the matrix. The program assumes that each
! element of the matrix is three (3) numbers wide. For example, 290 is allowed, but
! 29 is not. In addition, each number must be an integer. In order to use numbers greater
! than 999, change I3 in lines 77 and 82 to reflect however large of a number you require.
! ------------------------------------------------------------------------------------

IMPLICIT NONE

INTEGER :: I, MatSize, EStat, J, Point, Dummy, Count = 0, L, MinTrip, M, MinSum
INTEGER :: CountSum = 0, Sumss = 0
INTEGER, DIMENSION(1) :: Points, MinSumVal
INTEGER, ALLOCATABLE, DIMENSION(:,:) :: Adjac, PAdjac, Visited
INTEGER, ALLOCATABLE, DIMENSION(:) :: Temp, Sum
INTEGER, DIMENSION(8) :: Now

CALL Date_and_Time(values=Now)
PRINT *, Now(5:7)
OPEN(UNIT = 10, FILE = "NNInp.txt", STATUS = "OLD", IOSTAT = EStat)
IF (EStat /= 0) STOP "*** ERROR IN OPENING INPUT FILE ***"
! CALL SYSTEM('clear')
 DO 
    READ(10,'(1X, I1)', IOSTAT = EStat) Dummy
    IF (EStat /= 0) EXIT
    Count = Count + 1
 END DO
! PRINT *, "Matrix is of size ", Count
 MatSize = Count
 REWIND(10)
 ! Allocate arrays
 ALLOCATE(Adjac(MatSize, MatSize), STAT = EStat)
 IF (EStat /= 0) STOP "*** ERROR ALLOCATING MEMORY FOR MATRIX ***"
 ALLOCATE(PAdjac(MatSize, MatSize), STAT = EStat)
 IF (EStat /= 0) STOP "*** ERROR ALLOCATING MEMORY FOR MATRIX ***"
 ALLOCATE(Visited(MatSize,MatSize), STAT = EStat)
 IF (EStat /= 0) STOP "*** ERROR ALLOCATING MEMORY FOR MATRIX ***"
 ALLOCATE(Temp(MatSize), STAT = EStat)
 IF (EStat /= 0) STOP "*** ERROR ALLOCATING MEMORY FOR MATRIX ***"
 ALLOCATE(Sum(MatSize), STAT = EStat)
 IF (EStat /= 0) STOP "*** ERROR ALLOCATING MEMORY FOR MATRIX ***"
 ! Set up arrays
 DO I = 1, MatSize
    Temp(I) = 0
    Sum(I) = 0
    CountSum = CountSum + I
    DO J = 1, MatSize
       Visited(I,J) = 0
    END DO
 END DO
 DO I = 1, MatSize
    DO J = 1, MatSize - 1
       Dummy = 0
       READ(10, '(1X, I3)', ADVANCE = 'NO') Dummy 
       Adjac(I,J) = Dummy ! Read in adjacency matrix
       PAdjac(I,J) = Adjac(I,J) ! Create permanent adjacency matrix
    END DO
    Dummy = 0
    READ(10, '(1X, I3)', ADVANCE = 'YES') Dummy 
    Adjac(I,MatSize) = Dummy ! read last line of matrix
    PAdjac(I,MatSize) = Adjac(I,MatSize)
 END DO
! DO I = 1, MatSize
!    DO J = 1, Matsize
!       WRITE(*,'(1X, I4)', ADVANCE = "NO") Adjac(I,J) ! output matrix to screen
!    END DO
!    WRITE(*,*)
! END DO
 PAUSE
 DO M = 1, MatSize
    Point = M ! set starting point
    DO I = 1, MatSize
       DO J = 1, MatSize
          Adjac(I,J) = PAdjac(I,J) ! Update Adjac to originl values
       END DO
    END DO
    DO I = 1, MatSize
       Find: DO
          Points = 0
          Visited(M,I) = Point ! Starting point
          DO J = 1, MatSize
             Temp(J) = Adjac(Point,J) ! Create temp
          END DO
          Points = MINLOC(Temp, Temp > 0) ! Find location of min value
          DO J = 1, MatSize
             Adjac(Point, J) =  10000 ! if visited, change value of 10000
             Adjac(J, Point) =  10000 ! if visited, change value of 10000
         END DO 
          DO J = 1, MatSize
             IF (Visited(M,J) == Points(1)) THEN
                PRINT *, J, Points(1), "ERROR, Already visited this vertex!"
                Adjac(Point, Points(1)) = 10000 ! check if vertix has been visited
             ELSE
                EXIT Find
             END IF
          END DO
       END DO  Find
       Point = Points(1)
    END DO
    DO I = 1, MatSize - 1 ! Find sum
       Sum(M) = Sum(M) + PAdjac(Visited(M,I), Visited(M,I+1))
    END DO
    PRINT *, "Length of trip is: ", Sum(M)
 END DO
 DO I = 1, MatSize
    Sumss = 0 ! Check sum = 0
    DO J = 1, MatSize
       Sumss = Sumss + Visited(I,J) ! Sum of values of vertices
    END DO ! 1 + 2 + 3 + 4 + .. + n
    IF (Sumss /= CountSum) THEN ! If check fails, change value of calculated trip
       Sum(I) = Sum(I) + 10000  ! to be length + 10000
    END IF
 END DO
 DO I = 1, MatSize ! Check if a circuit exists
!    PRINT *, PAdjac(Visited(I,MatSize),Visited(I,1)), Visited(I,MatSize),Visited(I,1)  
    IF (PAdjac(Visited(I,MatSize),Visited(I,1)) == 0) THEN
       Sum(I) = Sum(I) + 10000 ! No circuit, increment SUM(I) by 10000
    ELSE ! Circut found! add weight of edge connecting first and last vertices to sum(I)
       SUM(I) = SUM(I) + PAdjac(Visited(I,MatSize),Visited(I,1))
    END IF
 END DO
 MinTrip = MinVal(Sum) ! Find length of the minimum length trip
 IF (MinTrip > 10000) STOP "No complete circuit Found!" ! No circuit found
 MinSumVal = MinLoc(Sum) ! Pick the trip with shortest length
 MinSum = MinSumVal(1) ! Which of the trials had the shortest length
 PRINT *, "Length of shortest trip is: ", MinTrip
 PRINT *
 PRINT *, "The shortest trip started at vertex: ", MinSum
 DO I = 2, MatSize
    PRINT *, "Then went to vertex: ", Visited(MinSum,I)
 END DO
 PRINT *, "And returned to vertex: ", Visited(MinSum,1)
CALL Date_and_Time(values=Now)
PRINT *, Now(5:7)

END PROGRAM