



"""simple docstring"""






class     UpperCAmelCase    :



   def __init__(       self    :	str							,       __lowerCamelCase    :	Optional[int]							,       __lowerCamelCase    :	Dict							,       __lowerCamelCase    :	Union[str, Any]				):



     """simple docstring"""
     _snake_case   	=      None
     _snake_case   	=      None
     _snake_case   	=      graph

     self._normalize_graph(__lowerCamelCase							,       __lowerCamelCase				)
     _snake_case   	=      len(__lowerCamelCase				)
     _snake_case   	=      None



   def    __UpperCAmelCase    (       self    :	Union[str, Any]							,       __lowerCamelCase    :	Tuple							,       __lowerCamelCase    :	str				):



     """simple docstring"""
     if sources is int:
       _snake_case   	=      [sources]
     if sinks is int:
       _snake_case   	=      [sinks]

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

     _snake_case   	=      sources[0]
     _snake_case   	=      sinks[0]

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

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

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



   def    __UpperCAmelCase    (       self    :	Optional[Any]				):



     """simple docstring"""
     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    :	Dict							,       __lowerCamelCase    :	int				):



     """simple docstring"""
     _snake_case   	=      algorithm(self				)



class     UpperCAmelCase    :



   def __init__(       self    :	List[str]							,       __lowerCamelCase    :	Optional[Any]				):



     """simple docstring"""
     _snake_case   	=      flow_network
     _snake_case   	=      flow_network.verticesCount
     _snake_case   	=      flow_network.sourceIndex
     _snake_case   	=      flow_network.sinkIndex
     # it's just a reference, so you shouldn't change
     # it in your algorithms, use deep copy before doing that
     _snake_case   	=      flow_network.graph
     _snake_case   	=      False



   def    __UpperCAmelCase    (       self    :	Optional[Any]				):



     """simple docstring"""
     if not self.executed:
       self._algorithm()
       _snake_case   	=      True





   def    __UpperCAmelCase    (       self    :	List[str]				):



     """simple docstring"""
     pass



class     UpperCAmelCase    (	__SCREAMING_SNAKE_CASE  ):



   def __init__(       self    :	str							,       __lowerCamelCase    :	Optional[int]				):



     """simple docstring"""
     super().__init__(__lowerCamelCase				)
     # use this to save your result
     _snake_case   	=      -1





   def    __UpperCAmelCase    (       self    :	List[Any]				):



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

     return self.maximum_flow



class     UpperCAmelCase    (	__SCREAMING_SNAKE_CASE  ):



   def __init__(       self    :	str							,       __lowerCamelCase    :	Tuple				):



     """simple docstring"""
     super().__init__(__lowerCamelCase				)

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

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



   def    __UpperCAmelCase    (       self    :	str				):



     """simple docstring"""
     _snake_case   	=      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
     _snake_case   	=      [
         i
         for i in range(self.verticies_count				)
         if i != self.source_index and i != self.sink_index
     ]

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

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



   def    __UpperCAmelCase    (       self    :	str							,       __lowerCamelCase    :	Tuple				):



     """simple docstring"""
     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(__lowerCamelCase							,       __lowerCamelCase				)

       self.relabel(__lowerCamelCase				)



   def    __UpperCAmelCase    (       self    :	int							,       __lowerCamelCase    :	Optional[int]							,       __lowerCamelCase    :	Optional[int]				):



     """simple docstring"""
     _snake_case   	=      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    :	Union[str, Any]							,       __lowerCamelCase    :	Dict				):



     """simple docstring"""
     _snake_case   	=      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):
         _snake_case   	=      self.heights[to_index]

     if min_height is not None:
       _snake_case   	=      min_height + 1


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

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

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













import gc
import unittest

import numpy as np
import torch
from transformers import CLIPTextConfig, CLIPTextModel, CLIPTokenizer

from diffusers import AutoencoderKL, DDIMScheduler, LDMTextToImagePipeline, UNetaDConditionModel
from diffusers.utils.testing_utils import (
    enable_full_determinism,
    load_numpy,
    nightly,
    require_torch_gpu,
    slow,
    torch_device,
)

from ..pipeline_params import TEXT_TO_IMAGE_BATCH_PARAMS, TEXT_TO_IMAGE_PARAMS
from ..test_pipelines_common import PipelineTesterMixin


enable_full_determinism()







class 		_A						( UpperCAmelCase_	,				unittest.TestCase ):
  lowercase_						:			Union[str, Any]						=					LDMTextToImagePipeline
  lowercase_						:			Tuple						=					TEXT_TO_IMAGE_PARAMS - {
      '''negative_prompt''',
      '''negative_prompt_embeds''',
      '''cross_attention_kwargs''',
      '''prompt_embeds''',
  }
  lowercase_						:			Optional[Any]						=					PipelineTesterMixin.required_optional_params - {
      '''num_images_per_prompt''',
      '''callback''',
      '''callback_steps''',
  }
  lowercase_						:			Dict						=					TEXT_TO_IMAGE_BATCH_PARAMS
  lowercase_						:			Tuple						=					False

  def    a					(    self						:	Optional[Any]			):
     """simple docstring"""

     torch.manual_seed(0			)
     __UpperCamelCase	:			Any					=					UNetaDConditionModel(
         block_out_channels=(32, 64)   ,				layers_per_block=2   ,				sample_size=32   ,				in_channels=4   ,				out_channels=4   ,				down_block_types=("""DownBlock2D""", """CrossAttnDownBlock2D""")   ,				up_block_types=("""CrossAttnUpBlock2D""", """UpBlock2D""")   ,				cross_attention_dim=32   ,				)
     __UpperCamelCase	:			Union[str, Any]					=					DDIMScheduler(
         beta_start=0.0_0085   ,				beta_end=0.012   ,				beta_schedule="""scaled_linear"""   ,				clip_sample=lowerCamelCase__   ,				set_alpha_to_one=lowerCamelCase__   ,				)
     torch.manual_seed(0			)
     __UpperCamelCase	:			Any					=					AutoencoderKL(
         block_out_channels=(32, 64)   ,				in_channels=3   ,				out_channels=3   ,				down_block_types=("""DownEncoderBlock2D""", """DownEncoderBlock2D""")   ,				up_block_types=("""UpDecoderBlock2D""", """UpDecoderBlock2D""")   ,				latent_channels=4   ,				)
     torch.manual_seed(0			)
     __UpperCamelCase	:			Union[str, Any]					=					CLIPTextConfig(
         bos_token_id=0   ,				eos_token_id=2   ,				hidden_size=32   ,				intermediate_size=37   ,				layer_norm_eps=1e-05   ,				num_attention_heads=4   ,				num_hidden_layers=5   ,				pad_token_id=1   ,				vocab_size=10_00   ,				)
     __UpperCamelCase	:			List[str]					=					CLIPTextModel(lowerCamelCase__			)
     __UpperCamelCase	:			List[str]					=					CLIPTokenizer.from_pretrained("""hf-internal-testing/tiny-random-clip"""			)

     __UpperCamelCase	:			Any					=					{
         """unet""": unet,
         """scheduler""": scheduler,
         """vqvae""": vae,
         """bert""": text_encoder,
         """tokenizer""": tokenizer,
     }
     return components

  def    a					(    self						:	Tuple   ,				lowerCamelCase__						:	str   ,				lowerCamelCase__						:	List[str]=0			):
     """simple docstring"""

     if str(lowerCamelCase__			).startswith("""mps"""			):
        __UpperCamelCase	:			str					=					torch.manual_seed(lowerCamelCase__			)
     else:
        __UpperCamelCase	:			Optional[Any]					=					torch.Generator(device=lowerCamelCase__			).manual_seed(lowerCamelCase__			)
     __UpperCamelCase	:			Tuple					=					{
         """prompt""": """A painting of a squirrel eating a burger""",
         """generator""": generator,
         """num_inference_steps""": 2,
         """guidance_scale""": 6.0,
         """output_type""": """numpy""",
     }
     return inputs

  def    a					(    self						:	Tuple			):
     """simple docstring"""

     __UpperCamelCase	:			Dict					=					"""cpu"""  # ensure determinism for the device-dependent torch.Generator

     __UpperCamelCase	:			List[str]					=					self.get_dummy_components()
     __UpperCamelCase	:			Optional[int]					=					LDMTextToImagePipeline(**lowerCamelCase__			)
     pipe.to(lowerCamelCase__			)
     pipe.set_progress_bar_config(disable=lowerCamelCase__			)

     __UpperCamelCase	:			List[Any]					=					self.get_dummy_inputs(lowerCamelCase__			)
     __UpperCamelCase	:			List[Any]					=					pipe(**lowerCamelCase__			).images
     __UpperCamelCase	:			Tuple					=					image[0, -3:, -3:, -1]

     assert image.shape == (1, 16, 16, 3)
     __UpperCamelCase	:			int					=					np.array([0.6101, 0.6156, 0.5622, 0.4895, 0.6661, 0.3804, 0.5748, 0.6136, 0.5014]			)

     assert np.abs(image_slice.flatten() - expected_slice			).max() < 1e-3







@slow
@require_torch_gpu
class 		_A						( unittest.TestCase ):

  def    a					(    self						:	Any			):
     """simple docstring"""

     super().tearDown()
     gc.collect()
     torch.cuda.empty_cache()

  def    a					(    self						:	Dict   ,				lowerCamelCase__						:	List[Any]   ,				lowerCamelCase__						:	Tuple=torch.floataa   ,				lowerCamelCase__						:	List[Any]=0			):
     """simple docstring"""

     __UpperCamelCase	:			Union[str, Any]					=					torch.manual_seed(lowerCamelCase__			)
     __UpperCamelCase	:			Tuple					=					np.random.RandomState(lowerCamelCase__			).standard_normal((1, 4, 32, 32)			)
     __UpperCamelCase	:			Any					=					torch.from_numpy(lowerCamelCase__			).to(device=lowerCamelCase__   ,				dtype=lowerCamelCase__			)
     __UpperCamelCase	:			Optional[int]					=					{
         """prompt""": """A painting of a squirrel eating a burger""",
         """latents""": latents,
         """generator""": generator,
         """num_inference_steps""": 3,
         """guidance_scale""": 6.0,
         """output_type""": """numpy""",
     }
     return inputs

  def    a					(    self						:	Optional[int]			):
     """simple docstring"""

     __UpperCamelCase	:			Any					=					LDMTextToImagePipeline.from_pretrained("""CompVis/ldm-text2im-large-256"""			).to(lowerCamelCase__			)
     pipe.set_progress_bar_config(disable=lowerCamelCase__			)

     __UpperCamelCase	:			Any					=					self.get_inputs(lowerCamelCase__			)
     __UpperCamelCase	:			Tuple					=					pipe(**lowerCamelCase__			).images
     __UpperCamelCase	:			Optional[int]					=					image[0, -3:, -3:, -1].flatten()

     assert image.shape == (1, 2_56, 2_56, 3)
     __UpperCamelCase	:			Optional[Any]					=					np.array([0.5_1825, 0.5_2850, 0.5_2543, 0.5_4258, 0.5_2304, 0.5_2569, 0.5_4363, 0.5_5276, 0.5_6878]			)
     __UpperCamelCase	:			Union[str, Any]					=					np.abs(expected_slice - image_slice			).max()
     assert max_diff < 1e-3







@nightly
@require_torch_gpu
class 		_A						( unittest.TestCase ):

  def    a					(    self						:	Optional[Any]			):
     """simple docstring"""

     super().tearDown()
     gc.collect()
     torch.cuda.empty_cache()

  def    a					(    self						:	Tuple   ,				lowerCamelCase__						:	str   ,				lowerCamelCase__						:	Union[str, Any]=torch.floataa   ,				lowerCamelCase__						:	Tuple=0			):
     """simple docstring"""

     __UpperCamelCase	:			Union[str, Any]					=					torch.manual_seed(lowerCamelCase__			)
     __UpperCamelCase	:			Optional[Any]					=					np.random.RandomState(lowerCamelCase__			).standard_normal((1, 4, 32, 32)			)
     __UpperCamelCase	:			List[Any]					=					torch.from_numpy(lowerCamelCase__			).to(device=lowerCamelCase__   ,				dtype=lowerCamelCase__			)
     __UpperCamelCase	:			Union[str, Any]					=					{
         """prompt""": """A painting of a squirrel eating a burger""",
         """latents""": latents,
         """generator""": generator,
         """num_inference_steps""": 50,
         """guidance_scale""": 6.0,
         """output_type""": """numpy""",
     }
     return inputs

  def    a					(    self						:	Tuple			):
     """simple docstring"""

     __UpperCamelCase	:			Tuple					=					LDMTextToImagePipeline.from_pretrained("""CompVis/ldm-text2im-large-256"""			).to(lowerCamelCase__			)
     pipe.set_progress_bar_config(disable=lowerCamelCase__			)

     __UpperCamelCase	:			Dict					=					self.get_inputs(lowerCamelCase__			)
     __UpperCamelCase	:			List[Any]					=					pipe(**lowerCamelCase__			).images[0]

     __UpperCamelCase	:			Optional[Any]					=					load_numpy(
         """https://huggingface.co/datasets/diffusers/test-arrays/resolve/main/ldm_text2img/ldm_large_256_ddim.npy"""			)
     __UpperCamelCase	:			int					=					np.abs(expected_image - image			).max()
     assert max_diff < 1e-3



