




'''simple docstring'''



UpperCAmelCase_       :  List[Any]      =		float('''inf''')





class     lowerCAmelCase   :


       def __init__(   self    ,  __SCREAMING_SNAKE_CASE  )      ->  Optional[Any]:



            '''simple docstring'''




            __snake_case    					=  [0] * n
            __snake_case    					=  [0] * n
            __snake_case    					=  [0] * n
            __snake_case    					=  [[] for _ in range(SCREAMING_SNAKE_CASE_  )]


       def       lowerCAmelCase      (   self    ,  __SCREAMING_SNAKE_CASE    ,  __SCREAMING_SNAKE_CASE    ,  __SCREAMING_SNAKE_CASE    ,  __SCREAMING_SNAKE_CASE=0  )      ->  List[Any]:



            '''simple docstring'''




            self.adj[a].append([b, len(self.adj[b]  ), c, 0]  )
            self.adj[b].append([a, len(self.adj[a]  ) - 1, rcap, 0]  )


       def       lowerCAmelCase      (   self    ,  __SCREAMING_SNAKE_CASE    ,  __SCREAMING_SNAKE_CASE    ,  __SCREAMING_SNAKE_CASE  )      ->  Dict:



            '''simple docstring'''




            if vertex == sink or not flow:
                 return flow

            for i in range(self.ptr[vertex]    ,  len(self.adj[vertex]  )  ):
                 __snake_case    					=  self.adj[vertex][i]
                 if self.lvl[e[0]] == self.lvl[vertex] + 1:
                      __snake_case    					=  self.depth_first_search(e[0]    ,  SCREAMING_SNAKE_CASE_    ,  min(SCREAMING_SNAKE_CASE_    ,  e[2] - e[3]  )  )
                      if p:
                           self.adj[vertex][i][3] += p
                           self.adj[e[0]][e[1]][3] -= p
                           return p
                 __snake_case    					=  self.ptr[vertex] + 1
            return 0




       def       lowerCAmelCase      (   self    ,  __SCREAMING_SNAKE_CASE    ,  __SCREAMING_SNAKE_CASE  )      ->  str:



            '''simple docstring'''




            __snake_case					,    __snake_case    					=  0, source
            for l in range(31  ):  # noqa: E741  l = 30 maybe faster for random data
                 while True:
                      __snake_case					,    __snake_case    					=  [0] * len(self.q  ), [0] * len(self.q  )
                      __snake_case					,    __snake_case					,    __snake_case    					=  0, 1, 1
                      while qi < qe and not self.lvl[sink]:
                           __snake_case    					=  self.q[qi]
                           qi += 1
                           for e in self.adj[v]:
                                if not self.lvl[e[0]] and (e[2] - e[3]) >> (30 - l):
                                     __snake_case    					=  e[0]
                                     qe += 1
                                     __snake_case    					=  self.lvl[v] + 1

                      __snake_case    					=  self.depth_first_search(SCREAMING_SNAKE_CASE_    ,  SCREAMING_SNAKE_CASE_    ,  SCREAMING_SNAKE_CASE_  )
                      while p:
                           flow += p
                           __snake_case    					=  self.depth_first_search(SCREAMING_SNAKE_CASE_    ,  SCREAMING_SNAKE_CASE_    ,  SCREAMING_SNAKE_CASE_  )

                      if not self.lvl[sink]:
                           break

            return flow

UpperCAmelCase_       :  str      =		Dinic(1_0)
UpperCAmelCase_       :  List[str]      =		0
UpperCAmelCase_       :  Optional[int]      =		9
for vertex in range(1, 5):
     graph.add_edge(source, vertex, 1)
for vertex in range(5, 9):
     graph.add_edge(vertex, sink, 1)
for vertex in range(1, 5):
     graph.add_edge(vertex, vertex + 4, 1)

# Now we can know that is the maximum flow(source -> sink)
print(graph.max_flow(source, sink))












'''simple docstring'''



from typing import Any

import numpy as np







def 			_UpperCamelCase (_lowerCamelCase							:     np.ndarray	)->   bool:




     '''simple docstring'''





     assert np.shape(_lowerCamelCase	)[0] == np.shape(_lowerCamelCase	)[1]

     # If matrix not symmetric, exit right away.
     if np.allclose(_lowerCamelCase   ,	matrix.T	) is False:
          return False

     # Get eigenvalues and eignevectors for a symmetric matrix.
     __snake_case					,    __snake_case    					=  np.linalg.eigh(_lowerCamelCase	)

     # Check sign of all eigenvalues.
     # np.all returns a value of type np.bool_
     return bool(np.all(eigen_values > 0	)	)







def 			_UpperCamelCase (_lowerCamelCase							:     int	)->   Any:




     '''simple docstring'''





     __snake_case    					=  np.random.randn(_lowerCamelCase   ,	_lowerCamelCase	)
     __snake_case    					=  np.dot(_lowerCamelCase   ,	random_matrix.T	)
     assert _is_matrix_spd(_lowerCamelCase	)
     return spd_matrix







def 			_UpperCamelCase (_lowerCamelCase							:     np.ndarray   ,	_lowerCamelCase							:     np.ndarray   ,	_lowerCamelCase							:     int = 10_00   ,	_lowerCamelCase							:     float = 1E-8   ,	)->   Any:




     '''simple docstring'''





     assert np.shape(_lowerCamelCase	)[0] == np.shape(_lowerCamelCase	)[1]
     assert np.shape(_lowerCamelCase	)[0] == np.shape(_lowerCamelCase	)[0]
     assert _is_matrix_spd(_lowerCamelCase	)

     # Initialize solution guess, residual, search direction.
     __snake_case    					=  np.zeros((np.shape(_lowerCamelCase	)[0], 1)	)
     __snake_case    					=  np.copy(_lowerCamelCase	)
     __snake_case    					=  np.copy(_lowerCamelCase	)

     # Set initial errors in solution guess and residual.
     __snake_case    					=  1E9
     __snake_case    					=  1E9
     __snake_case    					=  1E9

     # Set iteration counter to threshold number of iterations.
     __snake_case    					=  0

     while error > tol:
          # Save this value so we only calculate the matrix-vector product once.
          __snake_case    					=  np.dot(_lowerCamelCase   ,	_lowerCamelCase	)

          # The main algorithm.

          # Update search direction magnitude.
          __snake_case    					=  np.dot(ra.T   ,	_lowerCamelCase	) / np.dot(pa.T   ,	_lowerCamelCase	)
          # Update solution guess.
          __snake_case    					=  xa + alpha * pa
          # Calculate new residual.
          __snake_case    					=  ra - alpha * w
          # Calculate new Krylov subspace scale.
          __snake_case    					=  np.dot(r.T   ,	_lowerCamelCase	) / np.dot(ra.T   ,	_lowerCamelCase	)
          # Calculate new A conjuage search direction.
          __snake_case    					=  r + beta * pa

          # Calculate errors.
          __snake_case    					=  np.linalg.norm(r - ra	)
          __snake_case    					=  np.linalg.norm(x - xa	)
          __snake_case    					=  np.maximum(_lowerCamelCase   ,	_lowerCamelCase	)

          # Update variables.
          __snake_case    					=  np.copy(_lowerCamelCase	)
          __snake_case    					=  np.copy(_lowerCamelCase	)
          __snake_case    					=  np.copy(_lowerCamelCase	)

          # Update number of iterations.
          iterations += 1
          if iterations > max_iterations:
               break

     return x







def 			_UpperCamelCase ()->   None:




     '''simple docstring'''





     __snake_case    					=  3
     __snake_case    					=  _create_spd_matrix(_lowerCamelCase	)
     __snake_case    					=  np.random.randn(_lowerCamelCase   ,	1	)
     __snake_case    					=  np.dot(_lowerCamelCase   ,	_lowerCamelCase	)

     # Numpy solution.
     __snake_case    					=  np.linalg.solve(_lowerCamelCase   ,	_lowerCamelCase	)

     # Our implementation.
     __snake_case    					=  conjugate_gradient(_lowerCamelCase   ,	_lowerCamelCase	)

     # Ensure both solutions are close to x_true (and therefore one another).
     assert np.linalg.norm(x_numpy - x_true	) <= 1E-6
     assert np.linalg.norm(x_conjugate_gradient - x_true	) <= 1E-6


if __name__ == "__main__":
     import doctest

     doctest.testmod()
     test_conjugate_gradient()






