





"""simple docstring"""


class   __SCREAMING_SNAKE_CASE     :







  '''simple docstring'''


  def __init__(		self :							Any       , __a :							Any       , __a :							Dict       , __a :							Dict						)		->					List[str]:
        _UpperCamelCase   :						Tuple    =							None
        _UpperCamelCase   :						str    =							None
        _UpperCamelCase   :						List[Any]    =							graph

        self._normalize_graph(__a       , __a						)
        _UpperCamelCase   :						int    =							len(__a						)
        _UpperCamelCase   :						str    =							None

  def  __SCREAMING_SNAKE_CASE					(		self :							Tuple       , __a :							Optional[int]       , __a :							List[Any]						)		->					Any:
        if sources is int:
              _UpperCamelCase   :						List[str]    =							[sources]
        if sinks is int:
              _UpperCamelCase   :						List[Any]    =							[sinks]

        if len(__a						) == 0 or len(__a						) == 0:
              return

        _UpperCamelCase   :						List[str]    =							sources[0]
        _UpperCamelCase   :						int    =							sinks[0]

        # make fake vertex if there are more
        # than one source or sink
        if len(__a						) > 1 or len(__a						) > 1:
              _UpperCamelCase   :						str    =							0
              for i in sources:
                    max_input_flow += sum(self.graph[i]						)

              _UpperCamelCase   :						Union[str, Any]    =							len(self.graph						) + 1
              for room in self.graph:
                    room.insert(0       , 0						)
              self.graph.insert(0       , [0] * size						)
              for i in sources:
                    _UpperCamelCase   :						List[str]    =							max_input_flow
              _UpperCamelCase   :						List[Any]    =							0

              _UpperCamelCase   :						str    =							len(self.graph						) + 1
              for room in self.graph:
                    room.append(0						)
              self.graph.append([0] * size						)
              for i in sinks:
                    _UpperCamelCase   :						Optional[int]    =							max_input_flow
              _UpperCamelCase   :						int    =							size - 1

  def  __SCREAMING_SNAKE_CASE					(		self :							List[Any]						)		->					int:
        if self.maximum_flow_algorithm is None:
              raise Exception("You need to set maximum flow algorithm before."						)
        if self.source_index is None or self.sink_index is None:
              return 0

        self.maximum_flow_algorithm.execute()
        return self.maximum_flow_algorithm.getMaximumFlow()


  def  __SCREAMING_SNAKE_CASE					(		self :							Any       , __a :							Optional[int]						)		->					List[Any]:
        _UpperCamelCase   :						str    =							algorithm(self						)





class   __SCREAMING_SNAKE_CASE     :







  '''simple docstring'''


  def __init__(		self :							List[str]       , __a :							Tuple						)		->					str:
        _UpperCamelCase   :						Union[str, Any]    =							flow_network
        _UpperCamelCase   :						Dict    =							flow_network.verticesCount
        _UpperCamelCase   :						Optional[int]    =							flow_network.sourceIndex
        _UpperCamelCase   :						Dict    =							flow_network.sinkIndex
        # it's just a reference, so you shouldn't change
        # it in your algorithms, use deep copy before doing that
        _UpperCamelCase   :						List[str]    =							flow_network.graph
        _UpperCamelCase   :						str    =							False

  def  __SCREAMING_SNAKE_CASE					(		self :							Optional[Any]						)		->					List[Any]:
        if not self.executed:
              self._algorithm()
              _UpperCamelCase   :						Tuple    =							True


  def  __SCREAMING_SNAKE_CASE					(		self :							int						)		->					Optional[int]:
        pass





class   __SCREAMING_SNAKE_CASE     (    _UpperCamelCase ):







  '''simple docstring'''


  def __init__(		self :							Dict       , __a :							Tuple						)		->					List[Any]:
        super().__init__(__a						)
        # use this to save your result
        _UpperCamelCase   :						Optional[Any]    =							-1


  def  __SCREAMING_SNAKE_CASE					(		self :							Optional[int]						)		->					Optional[int]:
        if not self.executed:
              raise Exception("You should execute algorithm before using its result!"						)

        return self.maximum_flow





class   __SCREAMING_SNAKE_CASE     (    _UpperCamelCase ):







  '''simple docstring'''


  def __init__(		self :							int       , __a :							Any						)		->					str:
        super().__init__(__a						)

        _UpperCamelCase   :						Tuple    =							[[0] * self.verticies_count for i in range(self.verticies_count						)]

        _UpperCamelCase   :						str    =							[0] * self.verticies_count
        _UpperCamelCase   :						Union[str, Any]    =							[0] * self.verticies_count

  def  __SCREAMING_SNAKE_CASE					(		self :							Union[str, Any]						)		->					List[str]:
        _UpperCamelCase   :						List[Any]    =							self.verticies_count

        # push some substance to graph
        for nextvertex_index, bandwidth in enumerate(self.graph[self.source_index]						):
              self.preflow[self.source_index][nextvertex_index] += bandwidth
              self.preflow[nextvertex_index][self.source_index] -= bandwidth
              self.excesses[nextvertex_index] += bandwidth

        # Relabel-to-front selection rule
        _UpperCamelCase   :						int    =							[
            i
            for i in range(self.verticies_count						)
            if i != self.source_index and i != self.sink_index
        ]

        # move through list
        _UpperCamelCase   :						Tuple    =							0
        while i < len(__a						):
              _UpperCamelCase   :						Optional[Any]    =							vertices_list[i]
              _UpperCamelCase   :						Union[str, Any]    =							self.heights[vertex_index]
              self.process_vertex(__a						)
              if self.heights[vertex_index] > previous_height:
                    # if it was relabeled, swap elements
                    # and start from 0 index
                    vertices_list.insert(0       , vertices_list.pop(__a						)						)
                    _UpperCamelCase   :						Optional[int]    =							0
              else:
                    i += 1

        _UpperCamelCase   :						int    =							sum(self.preflow[self.source_index]						)

  def  __SCREAMING_SNAKE_CASE					(		self :							Union[str, Any]       , __a :							Union[str, Any]						)		->					Union[str, Any]:
        while self.excesses[vertex_index] > 0:
              for neighbour_index in range(self.verticies_count						):
                    # if it's neighbour and current vertex is higher
                    if (
                        self.graph[vertex_index][neighbour_index]
                        - self.preflow[vertex_index][neighbour_index]
                        > 0
                        and self.heights[vertex_index] > self.heights[neighbour_index]
                    ):
                          self.push(__a       , __a						)

              self.relabel(__a						)

  def  __SCREAMING_SNAKE_CASE					(		self :							Dict       , __a :							Any       , __a :							str						)		->					Optional[int]:
        _UpperCamelCase   :						str    =							min(
            self.excesses[from_index]       , self.graph[from_index][to_index] - self.preflow[from_index][to_index]       , )
        self.preflow[from_index][to_index] += preflow_delta
        self.preflow[to_index][from_index] -= preflow_delta
        self.excesses[from_index] -= preflow_delta
        self.excesses[to_index] += preflow_delta


  def  __SCREAMING_SNAKE_CASE					(		self :							Union[str, Any]       , __a :							int						)		->					Union[str, Any]:
        _UpperCamelCase   :						Union[str, Any]    =							None
        for to_index in range(self.verticies_count						):
              if (
                  self.graph[vertex_index][to_index]
                  - self.preflow[vertex_index][to_index]
                  > 0
              ) and (min_height is None or self.heights[to_index] < min_height):
                    _UpperCamelCase   :						Optional[Any]    =							self.heights[to_index]

        if min_height is not None:
              _UpperCamelCase   :						int    =							min_height + 1


if __name__ == "__main__":
  lowerCamelCase__						= [0]
  lowerCamelCase__						= [3]
  # graph = [
  #     [0, 0, 4, 6, 0, 0],
  #     [0, 0, 5, 2, 0, 0],
  #     [0, 0, 0, 0, 4, 4],
  #     [0, 0, 0, 0, 6, 6],
  #     [0, 0, 0, 0, 0, 0],
  #     [0, 0, 0, 0, 0, 0],
  # ]
  lowerCamelCase__						= [[0, 7, 0, 0], [0, 0, 6, 0], [0, 0, 0, 8], [9, 0, 0, 0]]

  # prepare our network
  lowerCamelCase__						= FlowNetwork(graph, entrances, exits)
  # set algorithm
  flow_network.set_maximum_flow_algorithm(PushRelabelExecutor)
  # and calculate
  lowerCamelCase__						= flow_network.find_maximum_flow()

  print(f"""maximum flow is {maximum_flow}""")







"""simple docstring"""


from collections.abc import Callable

import numpy as np




def        lowercase__     (       lowercase_		,lowercase_		,lowercase_		,lowercase_		,lowercase_      )       ->		np.ndarray:




      """simple docstring"""

      _UpperCamelCase   :						List[str]    =							int(np.ceil((x_end - xa) / step_size      )      )
      _UpperCamelCase   :						Tuple    =							np.zeros((n + 1,)      )
      _UpperCamelCase   :						List[str]    =							ya
      _UpperCamelCase   :						List[Any]    =							xa

      for k in range(lowercase_      ):
            _UpperCamelCase   :						List[str]    =							y[k] + step_size * ode_func(lowercase_		,y[k]      )
            x += step_size

      return y


if __name__ == "__main__":
  import doctest

  doctest.testmod()
