#! /usr/bin/env python3
#
def i4mat_shortest_path ( n, m ):

#*****************************************************************************80
#
## i4mat_shortest_path() computes the shortest distance between all pairs of points.
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    28 January 2016
#
#  Author:
#
#    John Burkardt
#
#  Reference:
#
#    Robert Floyd,
#    Algorithm 97, Shortest Path,
#    Communications of the ACM,
#    Volume 5, Number 6, June 1962, page 345.
#
#  Input:
#
#    integer N, the number of points.
#
#    integer M(N,N).  M(I,J) contains the length of the direct link between 
#    nodes I and J, or Inf if there is no direct link.
#
#  Output:
#
#    integer M(N,N).  M(I,J) contains the distance between nodes I and J,
#    that is, the length of the shortest path between them.  If there
#    is no such path, then M(I,J) will remain Inf.
#
  import numpy as np

  huge = 2147483647

  for i in range ( 0, n ):
    for j in range ( 0, n ):
      if ( m[j,i] < huge ):
        for k in range ( 0, n ):
          if ( m[i,k] < huge ):
            s = m[j,i] + m[i,k]
            if ( s < m[j,k] ):
              m[j,k] = s

  return m

def i4mat_shortest_path_test ( ):

#*****************************************************************************80
#
## i4mat_shortest_path_test() tests i4mat_shortest_path().
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    28 January 2016
#
#  Author:
#
#    John Burkardt
#
  import numpy as np

  n = 6

  a = np.array ( [ \
    [  0,  2,  5, -1, -1, -1 ], \
    [ -1,  0,  7,  1, -1,  8 ], \
    [ -1, -1,  0,  4, -1, -1 ], \
    [ -1, -1, -1,  0,  3, -1 ], \
    [ -1, -1,  2, -1,  0,  3 ], \
    [ -1,  5, -1,  2,  4,  0 ] ] )

  huge = 2147483647

  print ( '' )
  print ( 'i4mat_shortest_path_test():' )
  print ( '  i4mat_shortest_path() uses Floyd\'s algorithm to find the' )
  print ( '  shortest distance between all pairs of nodes' )
  print ( '  in a directed graph, starting from the initial array' )
  print ( '  of direct node-to-node distances.' )

  print ( '' )
  print ( '  In the initial direct distance array, if' )
  print ( '    A(I,J) = Inf,' )
  print ( '  this indicates there is NO directed link from' )
  print ( '  node I to node J.  In that case, the value of' )
  print ( '  of A(I,J) is essentially "infinity".' )

  print ( '')
  print ( '  Initial direct-link distances:' )
  print ( a )

  for j in range ( 0, n ):
    for i in range ( 0, n ):
      if ( a[i,j] == -1 ):
        a[i,j] = huge

  a = i4mat_shortest_path ( n, a )

  for j in range ( 0, n ):
    for i in range ( 0, n ):
      if ( a[i,j] == huge ):
        a[i,j] = -1

  print ( '' )
  print ( '  In the final shortest distance array, if' )
  print ( '    A(I,J) = -1,' )
  print ( '  this indicates there is NO directed path from' )
  print ( '  node I to node J.' )
  print ( '' )
  print ( '  Final distance matrix:' )
  print ( a )

  return

def r8mat_shortest_path ( n, m ):

#*****************************************************************************80
#
## r8mat_shortest_path() computes the shortest distance between all pairs of points.
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    01 March 2014
#
#  Author:
#
#    John Burkardt
#
#  Reference:
#
#    Robert Floyd,
#    Algorithm 97, Shortest Path,
#    Communications of the ACM,
#    Volume 5, Number 6, June 1962, page 345.
#
#  Input:
#
#    integer N, the number of points.
#
#    real M(N,N).  M(I,J) contains the length of the direct link between 
#    nodes I and J, or Inf if there is no direct link.
#
#  Output:
#
#    real M(N,N).  M(I,J) contains the distance between nodes I and J,
#    that is, the length of the shortest path between them.  If there
#    is no such path, then M(I,J) will remain Inf.
#
  import numpy as np

  for i in range ( 0, n ):
    for j in range ( 0, n ):
      if ( m[j,i] < np.inf ):
        for k in range ( 0, n ):
          if ( m[i,k] < np.inf ):
            s = m[j,i] + m[i,k]
            if ( s < m[j,k] ):
              m[j,k] = s

  return m

def r8mat_shortest_path_test ( ):

#*****************************************************************************80
#
## r8mat_shortest_path_test() tests r8mat_shortest_path().
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    28 January 2016
#
#  Author:
#
#    John Burkardt
#
  import numpy as np

  n = 6

  a = np.array ( [ \
    [  0.0,  2.0,  5.0, -1.0, -1.0, -1.0 ], \
    [ -1.0,  0.0,  7.0,  1.0, -1.0,  8.0 ], \
    [ -1.0, -1.0,  0.0,  4.0, -1.0, -1.0 ], \
    [ -1.0, -1.0, -1.0,  0.0,  3.0, -1.0 ], \
    [ -1.0, -1.0,  2.0, -1.0,  0.0,  3.0 ], \
    [ -1.0,  5.0, -1.0,  2.0,  4.0,  0.0 ] ] )
 
  print ( '' )
  print ( 'r8mat_shortest_path_test():' )
  print ( '  r8mat_shortest_path() uses Floyd\'s algorithm to find the' )
  print ( '  shortest distance between all pairs of nodes' )
  print ( '  in a directed graph, starting from the initial array' )
  print ( '  of direct node-to-node distances.' )

  print ( '' )
  print ( '  In the initial direct distance array, if' )
  print ( '    A(I,J) = Inf,' )
  print ( '  this indicates there is NO directed link from' )
  print ( '  node I to node J.  In that case, the value of' )
  print ( '  of A(I,J) is essentially "infinity".' )
  print ( '' )
  print ( '  Initial direct-link distances:' )
  print ( a )

  for j in range ( 0, n ):
    for i in range ( 0, n ):
      if ( a[i,j] == -1.0 ):
        a[i,j] = np.inf

  a = r8mat_shortest_path ( n, a )

  for j in range ( 0, n ):
    for i in range ( 0, n ):
      if ( a[i,j] == np.inf ):
        a[i,j] = -1.0

  print ( '' )
  print ( '  In the final shortest distance array, if' )
  print ( '    A(I,J) = -1,' )
  print ( '  this indicates there is NO directed path from' )
  print ( '  node I to node J.' )
  print ( '' )
  print ( '  Final distance matrix:' )
  print ( a )

  return

def timestamp ( ):

#*****************************************************************************80
#
## timestamp() prints the date as a timestamp.
#
#  Licensing:
#
#    This code is distributed under the MIT license. 
#
#  Modified:
#
#    06 April 2013
#
#  Author:
#
#    John Burkardt
#
  import time

  t = time.time ( )
  print ( time.ctime ( t ) )

  return None

def toms097_test ( ):

#*****************************************************************************80
#
## toms097_test() tests toms097().
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    28 January 2016
#
#  Author:
#
#    John Burkardt
#
  import platform

  print ( '' )
  print ( 'toms097_test():' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  Test toms097().' )

  i4mat_shortest_path_test ( )
  r8mat_shortest_path_test ( )
#
#  Terminate.
#
  print ( '' )
  print ( 'toms097_test():' )
  print ( '  Normal end of execution.' )
  return

if ( __name__ == '__main__' ):
  timestamp ( )
  toms097_test ( )
  timestamp ( )