





class 			__UpperCamelCase    :





     def __init__(     self				,							_UpperCamelCase				,							_UpperCamelCase				,							_UpperCamelCase					):
        _UpperCAmelCase           =   None
        _UpperCAmelCase           =   None
        _UpperCAmelCase           =   graph

        self._normalize_graph(_UpperCamelCase				,							_UpperCamelCase					)
        _UpperCAmelCase           =   len(_UpperCamelCase					)
        _UpperCAmelCase           =   None





     def 		UpperCamelCase(     self				,							_UpperCamelCase				,							_UpperCamelCase					):
        if sources is int:
           _UpperCAmelCase           =   [sources]
        if sinks is int:
           _UpperCAmelCase           =   [sinks]

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

        _UpperCAmelCase           =   sources[0]
        _UpperCAmelCase           =   sinks[0]

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

           _UpperCAmelCase           =   len(self.graph					) + 1
           for room in self.graph:
              room.insert(0				,							0					)
           self.graph.insert(0				,							[0] * size					)
           for i in sources:
              _UpperCAmelCase           =   max_input_flow
           _UpperCAmelCase           =   0

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





     def 		UpperCamelCase(     self					):
        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 		UpperCamelCase(     self				,							_UpperCamelCase					):
        _UpperCAmelCase           =   algorithm(self					)




class 			__UpperCamelCase    :





     def __init__(     self				,							_UpperCamelCase					):
        _UpperCAmelCase           =   flow_network
        _UpperCAmelCase           =   flow_network.verticesCount
        _UpperCAmelCase           =   flow_network.sourceIndex
        _UpperCAmelCase           =   flow_network.sinkIndex
        # it's just a reference, so you shouldn't change
        # it in your algorithms, use deep copy before doing that
        _UpperCAmelCase           =   flow_network.graph
        _UpperCAmelCase           =   False





     def 		UpperCamelCase(     self					):
        if not self.executed:
           self._algorithm()
           _UpperCAmelCase           =   True





     def 		UpperCamelCase(     self					):
        pass




class 			__UpperCamelCase    (							A__    ):





     def __init__(     self				,							_UpperCamelCase					):
        super().__init__(_UpperCamelCase					)
        # use this to save your result
        _UpperCAmelCase           =   -1





     def 		UpperCamelCase(     self					):
        if not self.executed:
           raise Exception('''You should execute algorithm before using its result!'''					)

        return self.maximum_flow




class 			__UpperCamelCase    (							A__    ):





     def __init__(     self				,							_UpperCamelCase					):
        super().__init__(_UpperCamelCase					)

        _UpperCAmelCase           =   [[0] * self.verticies_count for i in range(self.verticies_count					)]

        _UpperCAmelCase           =   [0] * self.verticies_count
        _UpperCAmelCase           =   [0] * self.verticies_count





     def 		UpperCamelCase(     self					):
        _UpperCAmelCase           =   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           =   [
            i
            for i in range(self.verticies_count					)
            if i != self.source_index and i != self.sink_index
        ]

        # move through list
        _UpperCAmelCase           =   0
        while i < len(_UpperCamelCase					):
           _UpperCAmelCase           =   vertices_list[i]
           _UpperCAmelCase           =   self.heights[vertex_index]
           self.process_vertex(_UpperCamelCase					)
           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(_UpperCamelCase					)					)
              _UpperCAmelCase           =   0
           else:
              i += 1

        _UpperCAmelCase           =   sum(self.preflow[self.source_index]					)





     def 		UpperCamelCase(     self				,							_UpperCamelCase					):
        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(_UpperCamelCase				,							_UpperCamelCase					)

           self.relabel(_UpperCamelCase					)





     def 		UpperCamelCase(     self				,							_UpperCamelCase				,							_UpperCamelCase					):
        _UpperCAmelCase           =   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 		UpperCamelCase(     self				,							_UpperCamelCase					):
        _UpperCAmelCase           =   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           =   self.heights[to_index]

        if min_height is not None:
           _UpperCAmelCase           =   min_height + 1


if __name__ == "__main__":
   UpperCAmelCase_           =	[0]
   UpperCAmelCase_           =	[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],
   # ]
   UpperCAmelCase_           =	[[0, 7, 0, 0], [0, 0, 6, 0], [0, 0, 0, 8], [9, 0, 0, 0]]

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

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






import numpy as np
def      A__       (    SCREAMING_SNAKE_CASE_   :      np.ndarray				,	SCREAMING_SNAKE_CASE_   :      float						)  ->  np.ndarray:






   """simple docstring"""







   return np.where(vector > 0				,	SCREAMING_SNAKE_CASE_				,	(alpha * (np.exp(SCREAMING_SNAKE_CASE_						) - 1))						)


if __name__ == "__main__":
   import doctest

   doctest.testmod()