#! /usr/bin/env python3
#
def digraph_adj_test ( ):

#*****************************************************************************80
#
## digraph_adj_test() tests digraph_adj().
#
#  Licensing:
#
#    This code is distributed under the MIT license. 
#
#  Modified:
#
#    11 March 2023
#
#  Author:
#
#    John Burkardt
#
  import platform

  print ( '' )
  print ( 'digraph_adj_test():' )
  print ( '  Python version:' + platform.python_version ( ) )
  print ( '  Test digraph_adj().' )

  abc_inc_test ( )
  abcd_inc_test ( )
  five_inc_test ( )
  inc_to_google_test ( )
  inc_to_transition_test ( )
  moler_inc_test ( )
  sauer_inc_test ( )
#
#  Terminate.
#
  print ( '' )
  print ( 'digraph_adj_test():' )
  print ( '  Normal end of execution.' )

  return

def abc_inc ( ):

#*****************************************************************************80
#
## abc_inc() sets up the incidence matrix associated with a network.
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    24 February 2023
#
#  Author:
#
#    John Burkardt
#
#  Output:
#
#    integer A(3,3): a sparse incidence matrix.
#
  import numpy as np

  A = np.array ( [ \
    [ 0, 1, 0 ], \
    [ 0, 0, 1 ], \
    [ 1, 0, 0 ] ] )

  return A

def abc_inc_test ( ):

#*****************************************************************************80
#
## abc_inc_test() tests abc_inc().
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    25 February 2023
#
#  Author:
#
#    John Burkardt
#
  import numpy as np

  print ( '' )
  print ( 'abc_inc_test():' )
  print ( '  Test abc_inc()' )

  A = abc_inc ( )

  print ( '' )
  print ( '  "abc" incidence matrix A:' )
  print ( A )

  return

def abcd_inc ( ):

#*****************************************************************************80
#
## abcd_inc() sets up the incidence matrix associated with a network.
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    24 February 2023
#
#  Author:
#
#    John Burkardt
#
#  Output:
#
#    integer A(4,4): a sparse incidence matrix.
#
  import numpy as np

  A = np.array ( [ \
    [ 0, 1, 0, 0 ], \
    [ 0, 0, 1, 0 ], \
    [ 1, 0, 0, 1 ], \
    [ 1, 0, 0, 0 ] ] )

  return A

def abcd_inc_test ( ):

#*****************************************************************************80
#
## abcd_inc_test() tests abcd_inc().
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    25 February 2023
#
#  Author:
#
#    John Burkardt
#
  import numpy as np

  print ( '' )
  print ( 'abcd_inc_test():' )
  print ( '  Test abcd_inc()' )

  A = abcd_inc ( )

  print ( '' )
  print ( '  "abcd" incidence matrix A:' )
  print ( A )

  return

def five_inc ( ):

#*****************************************************************************80
#
## five_inc() sets up the incidence matrix associated with a network.
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    24 February 2023
#
#  Author:
#
#    John Burkardt
#
#  Output:
#
#    integer A(5,5): a sparse incidence matrix.
#
  import numpy as np

  A = np.array ( [ \
    [ 0, 1, 0, 0, 0 ], \
    [ 0, 0, 0, 0, 1 ], \
    [ 1, 0, 0, 0, 0 ], \
    [ 1, 0, 0, 0, 0 ], \
    [ 1, 0, 0, 0, 0 ] ] )

  return A

def five_inc_test ( ):

#*****************************************************************************80
#
## five_inc_test() tests five_inc().
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    25 February 2023
#
#  Author:
#
#    John Burkardt
#
  import numpy as np

  print ( '' )
  print ( 'five_inc_test():' )
  print ( '  Test five_inc()' )

  A = five_inc ( )

  print ( '' )
  print ( '  "five" incidence matrix A:' )
  print ( A )

  return

def inc_to_google ( A ):

#*****************************************************************************80
#
## inc_to_google() converts an incidence matrix to a Google transition matrix.
#
#  Discussion:
#
#    If the input incidence matrix has a node I with no connectivity,
#    (A(I,1:N) = 0) then we artificially set T(1:N,I)=1/N, so that
#    the transition matrix property of having unit column sums is preserved.
#
#    For nodes with connectivity, we assume that 85 percent of the time
#    we will take a link at random, and 15 percent of the time, we will
#    jump to an arbitrary link.  
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    24 February 2023
#
#  Author:
#
#    John Burkardt
#
#  Input:
#
#    integer A(N,N): the incidence matrix.
#
#  Output:
#
#    real G(N,N): the Google matrix.
#
  import numpy as np

  n = A.shape[0]

  s = np.sum ( A, axis = 1 )

  p = 0.15

  G = np.zeros ( [ n, n ] )

  for i in range ( 0, n ):
    if ( s[i] == 0.0 ):
      G[i,:] = 1.0 / n
    else:
      G[i,:] = ( 1.0 - p ) * A[i,:] / s[i] + p / n

  G = np.transpose ( G )

  return G

def inc_to_google_test ( ):

#*****************************************************************************80
#
## inc_to_google_test() tests inc_to_google().
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    25 February 2023
#
#  Author:
#
#    John Burkardt
#
  import numpy as np

  print ( '' )
  print ( 'inc_to_google_test():' )
  print ( '  Test inc_to_google()' )

  A = np.array ( [ \
    [ 0, 1, 0, 0 ], \
    [ 0, 0, 1, 0 ], \
    [ 1, 0, 0, 1 ], \
    [ 1, 0, 0, 0 ] ] )

  print ( '' )
  print ( '  Incidence matrix A:' )
  print ( A )

  G = inc_to_google ( A )

  print ( '' )
  print ( '  Google transition matrix G:' )
  print ( G )

  return

def inc_to_transition ( A ):

#*****************************************************************************80
#
## inc_to_transition() converts an incidence matrix to a transition matrix.
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    25 February 2023
#
#  Author:
#
#    John Burkardt
#
#  Input:
#
#    integer A(N,N), the incidence matrix.
#
#  Output:
#
#    real T(N,N): the transition matrix.
#
  import numpy as np
#
#  Get the number of variables.
#
  n = A.shape[0]
#
#  Get the row sums.
#
  s = np.sum ( A, axis = 1 )
#
#  Allocate T.
#
  T = np.zeros ( [ n, n ] )
#
#  Normalize each row so it sums to 1.
#
  for i in range ( 0, n ):
    if ( s[i] != 0.0 ):
      T[i,:] = A[i,:] / s[i]
    else:
      T[i,i] = 1.0
#
#  Transpose the matrix.
#
  T = np.transpose ( T )

  return T

def inc_to_transition_test ( ):

#*****************************************************************************80
#
## inc_to_transition_test() tests inc_to_transition().
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    25 February 2023
#
#  Author:
#
#    John Burkardt
#
  import numpy as np

  print ( '' )
  print ( 'inc_to_transition_test():' )
  print ( '  Test inc_to_transition()' )

  A = np.array ( [ \
    [ 0, 1, 0, 0 ], \
    [ 0, 0, 1, 0 ], \
    [ 1, 0, 0, 1 ], \
    [ 1, 0, 0, 0 ] ] )

  print ( '' )
  print ( '  Incidence matrix A:' )
  print ( A )

  T = inc_to_transition ( A )

  print ( '' )
  print ( '  Transition matrix T:' )
  print ( T )

  return

def moler_inc ( ):

#*****************************************************************************80
#
## moler_inc() returns the incidence matrix for Moler's example 3.
#
#  Discussion:
#
#    This matrix appears on page 5 of the reference.
#
#    We added a self-link for node 5, which otherwise has no outlinks.
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    24 February 2023
#
#  Author:
#
#    John Burkardt
#
#  Reference:
#
#    Cleve Moler,
#    Experiments with Matlab,
#    Chapter 7: Google PageRank,
#    https://www.mathworks.com/moler/exm/chapters/pagerank.pdf
#
#  Output:
#
#    integer A(6,6), the incidence matrix.
#
  import numpy as np

  A = np.zeros ( [ 6, 6 ] )

  A = np.array ( [ \
    [ 0, 1, 0, 0, 0, 1 ], \
    [ 0, 0, 1, 1, 0, 0 ], \
    [ 0, 0, 0, 1, 1, 1 ], \
    [ 1, 0, 0, 0, 0, 0 ], \
    [ 0, 0, 0, 0, 1, 0 ], \
    [ 1, 0, 0, 0, 0, 0 ] ] )

  return A

def moler_inc_test ( ):

#*****************************************************************************80
#
## moler_inc_test() tests moler_inc().
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    25 February 2023
#
#  Author:
#
#    John Burkardt
#
  import numpy as np

  print ( '' )
  print ( 'moler_inc_test():' )
  print ( '  Test moler_inc()' )

  A = moler_inc ( )

  print ( '' )
  print ( '  Moler incidence matrix A:' )
  print ( A )

  return

def sauer_inc ( ):

#*****************************************************************************80
#
## sauer_inc() sets up the incidence matrix associated with a network.
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    24 February 2023
#
#  Author:
#
#    John Burkardt
#
#  Reference:
#
#    Timothy Sauer,
#    "How search engines rate page quality",
#    Numerical Analysis,
#    Pearson, 2006.
#    ISBN: 0-321-2698-9,
#    LC: QA297.S348
#
#  Output:
#
#    real A(15,15): a sparse incidence matrix.
#
  import numpy as np

  A = np.array ( [ \
    [ 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ], \
    [ 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 ], \
    [ 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0 ], \
    [ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 ], \
    [ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 ], \
    [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 ], \
    [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 ], \
    [ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 ], \
    [ 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0 ], \
    [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 ], \
    [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ], \
    [ 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0 ], \
    [ 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0 ], \
    [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1 ], \
    [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0 ] ] )

  return A

def sauer_inc_test ( ):

#*****************************************************************************80
#
## sauer_inc_test() tests sauer_inc().
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    25 February 2023
#
#  Author:
#
#    John Burkardt
#
  import numpy as np

  print ( '' )
  print ( 'sauer_inc_test():' )
  print ( '  Test sauer_inc()' )

  A = sauer_inc ( )

  print ( '' )
  print ( '  Sauer incidence matrix A:' )
  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

if ( __name__ == "__main__" ):
  timestamp ( )
  digraph_adj_test ( )
  timestamp ( )