






_a   			=						float('''inf''')





class __lowerCamelCase				:





	"""simple docstring"""






	def __init__(							self ,					UpperCAmelCase					):
							"""simple docstring"""







							_UpperCAmelCase							      =    [0] * n
							_UpperCAmelCase							      =    [0] * n
							_UpperCAmelCase							      =    [0] * n
							_UpperCAmelCase							      =    [[] for _ in range(UpperCAmelCase					)]

	def  UpperCamelCase					(							self ,					UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase=0					):
							"""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  UpperCamelCase					(							self ,					UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase					):
							"""simple docstring"""







							if vertex == sink or not flow:
													return flow

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

	def  UpperCamelCase					(							self ,					UpperCAmelCase ,					UpperCAmelCase					):
							"""simple docstring"""







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

																			_UpperCAmelCase							      =    self.depth_first_search(UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase					)
																			while p:
																									flow += p
																									_UpperCAmelCase							      =    self.depth_first_search(UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase					)

																			if not self.lvl[sink]:
																									break

							return flow



_a   			=						Dinic(10)
_a   			=						0
_a   			=						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))








from __future__ import annotations

import inspect
import unittest

import numpy as np

from transformers import SwinConfig
from transformers.testing_utils import require_tf, require_vision, slow, to_atuple
from transformers.utils import cached_property, is_tf_available, is_vision_available

from ...test_configuration_common import ConfigTester
from ...test_modeling_tf_common import TFModelTesterMixin, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_tf_available():
		import tensorflow as tf

		from transformers.models.swin.modeling_tf_swin import (
		    TF_SWIN_PRETRAINED_MODEL_ARCHIVE_LIST,
		    TFSwinForImageClassification,
		    TFSwinForMaskedImageModeling,
		    TFSwinModel,
		)


if is_vision_available():
		from PIL import Image

		from transformers import AutoImageProcessor





class __lowerCamelCase				:





	"""simple docstring"""






	def __init__(							self ,					UpperCAmelCase ,					UpperCAmelCase=13 ,					UpperCAmelCase=32 ,					UpperCAmelCase=2 ,					UpperCAmelCase=3 ,					UpperCAmelCase=16 ,					UpperCAmelCase=[1, 2, 1] ,					UpperCAmelCase=[2, 2, 4] ,					UpperCAmelCase=2 ,					UpperCAmelCase=2.0 ,					UpperCAmelCase=True ,					UpperCAmelCase=0.0 ,					UpperCAmelCase=0.0 ,					UpperCAmelCase=0.1 ,					UpperCAmelCase="gelu" ,					UpperCAmelCase=False ,					UpperCAmelCase=True ,					UpperCAmelCase=0.02 ,					UpperCAmelCase=1e-5 ,					UpperCAmelCase=True ,					UpperCAmelCase=None ,					UpperCAmelCase=True ,					UpperCAmelCase=10 ,					UpperCAmelCase=8 ,					):
							"""simple docstring"""







							_UpperCAmelCase             =    parent
							_UpperCAmelCase             =    batch_size
							_UpperCAmelCase             =    image_size
							_UpperCAmelCase             =    patch_size
							_UpperCAmelCase             =    num_channels
							_UpperCAmelCase             =    embed_dim
							_UpperCAmelCase             =    depths
							_UpperCAmelCase             =    num_heads
							_UpperCAmelCase             =    window_size
							_UpperCAmelCase             =    mlp_ratio
							_UpperCAmelCase             =    qkv_bias
							_UpperCAmelCase             =    hidden_dropout_prob
							_UpperCAmelCase             =    attention_probs_dropout_prob
							_UpperCAmelCase             =    drop_path_rate
							_UpperCAmelCase             =    hidden_act
							_UpperCAmelCase             =    use_absolute_embeddings
							_UpperCAmelCase             =    patch_norm
							_UpperCAmelCase             =    layer_norm_eps
							_UpperCAmelCase             =    initializer_range
							_UpperCAmelCase             =    is_training
							_UpperCAmelCase             =    scope
							_UpperCAmelCase             =    use_labels
							_UpperCAmelCase             =    type_sequence_label_size
							_UpperCAmelCase             =    encoder_stride

	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							_UpperCAmelCase             =    floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]					)

							_UpperCAmelCase             =    None
							if self.use_labels:
													_UpperCAmelCase             =    ids_tensor([self.batch_size] ,					self.type_sequence_label_size					)

							_UpperCAmelCase             =    self.get_config()

							return config, pixel_values, labels

	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							return SwinConfig(
							    image_size=self.image_size ,					patch_size=self.patch_size ,					num_channels=self.num_channels ,					embed_dim=self.embed_dim ,					depths=self.depths ,					num_heads=self.num_heads ,					window_size=self.window_size ,					mlp_ratio=self.mlp_ratio ,					qkv_bias=self.qkv_bias ,					hidden_dropout_prob=self.hidden_dropout_prob ,					attention_probs_dropout_prob=self.attention_probs_dropout_prob ,					drop_path_rate=self.drop_path_rate ,					hidden_act=self.hidden_act ,					use_absolute_embeddings=self.use_absolute_embeddings ,					path_norm=self.patch_norm ,					layer_norm_eps=self.layer_norm_eps ,					initializer_range=self.initializer_range ,					encoder_stride=self.encoder_stride ,					)

	def  UpperCamelCase					(							self ,					UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase					):
							"""simple docstring"""







							_UpperCAmelCase             =    TFSwinModel(config=UpperCAmelCase					)
							_UpperCAmelCase             =    model(UpperCAmelCase					)

							_UpperCAmelCase             =    ((config.image_size // config.patch_size) ** 2) // (4 ** (len(config.depths					) - 1))
							_UpperCAmelCase             =    int(config.embed_dim * 2 ** (len(config.depths					) - 1)					)

							self.parent.assertEqual(result.last_hidden_state.shape ,					(self.batch_size, expected_seq_len, expected_dim)					)

	def  UpperCamelCase					(							self ,					UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase					):
							"""simple docstring"""







							_UpperCAmelCase             =    TFSwinForMaskedImageModeling(config=UpperCAmelCase					)
							_UpperCAmelCase             =    model(UpperCAmelCase					)
							self.parent.assertEqual(
							    result.logits.shape ,					(self.batch_size, self.num_channels, self.image_size, self.image_size)					)

							# test greyscale images
							_UpperCAmelCase             =    1
							_UpperCAmelCase             =    TFSwinForMaskedImageModeling(UpperCAmelCase					)

							_UpperCAmelCase             =    floats_tensor([self.batch_size, 1, self.image_size, self.image_size]					)
							_UpperCAmelCase             =    model(UpperCAmelCase					)
							self.parent.assertEqual(result.logits.shape ,					(self.batch_size, 1, self.image_size, self.image_size)					)

	def  UpperCamelCase					(							self ,					UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase					):
							"""simple docstring"""







							_UpperCAmelCase             =    self.type_sequence_label_size
							_UpperCAmelCase             =    TFSwinForImageClassification(UpperCAmelCase					)
							_UpperCAmelCase             =    model(UpperCAmelCase ,					labels=UpperCAmelCase					)
							self.parent.assertEqual(result.logits.shape ,					(self.batch_size, self.type_sequence_label_size)					)

							# test greyscale images
							_UpperCAmelCase             =    1
							_UpperCAmelCase             =    TFSwinForImageClassification(UpperCAmelCase					)
							_UpperCAmelCase             =    floats_tensor([self.batch_size, 1, self.image_size, self.image_size]					)
							_UpperCAmelCase             =    model(UpperCAmelCase					)
							self.parent.assertEqual(result.logits.shape ,					(self.batch_size, self.type_sequence_label_size)					)

	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							_UpperCAmelCase             =    self.prepare_config_and_inputs()
							_UpperCAmelCase      ,				_UpperCAmelCase      ,				_UpperCAmelCase             =    config_and_inputs
							_UpperCAmelCase             =    {'pixel_values': pixel_values}
							return config, inputs_dict





@require_tf
class __lowerCamelCase				(   snake_case__  , snake_case__  , unittest.TestCase):





	"""simple docstring"""






	UpperCamelCase__			=   (
	    (
	        TFSwinModel,
	        TFSwinForImageClassification,
	        TFSwinForMaskedImageModeling,
	    )
	    if is_tf_available()
	    else ()
	)
	UpperCamelCase__			=   (
	    {"feature-extraction": TFSwinModel, "image-classification": TFSwinForImageClassification}
	    if is_tf_available()
	    else {}
	)

	UpperCamelCase__			=   False
	UpperCamelCase__			=   False
	UpperCamelCase__			=   False
	UpperCamelCase__			=   False

	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							_UpperCAmelCase             =    TFSwinModelTester(self					)
							_UpperCAmelCase             =    ConfigTester(self ,					config_class=UpperCAmelCase ,					embed_dim=37					)

	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							self.create_and_test_config_common_properties()
							self.config_tester.create_and_test_config_to_json_string()
							self.config_tester.create_and_test_config_to_json_file()
							self.config_tester.create_and_test_config_from_and_save_pretrained()
							self.config_tester.create_and_test_config_with_num_labels()
							self.config_tester.check_config_can_be_init_without_params()
							self.config_tester.check_config_arguments_init()

	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							return

	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							_UpperCAmelCase             =    self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_model(*UpperCAmelCase					)

	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							_UpperCAmelCase             =    self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_for_masked_image_modeling(*UpperCAmelCase					)

	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							_UpperCAmelCase             =    self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_for_image_classification(*UpperCAmelCase					)

	@unittest.skip(reason='Swin does not use inputs_embeds'					)
	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							pass

	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							_UpperCAmelCase      ,				_UpperCAmelCase             =    self.model_tester.prepare_config_and_inputs_for_common()

							for model_class in self.all_model_classes:
													_UpperCAmelCase             =    model_class(UpperCAmelCase					)
													self.assertIsInstance(model.get_input_embeddings() ,					tf.keras.layers.Layer					)
													_UpperCAmelCase             =    model.get_output_embeddings()
													self.assertTrue(x is None or isinstance(UpperCAmelCase ,					tf.keras.layers.Dense					)					)

	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							_UpperCAmelCase      ,				_UpperCAmelCase             =    self.model_tester.prepare_config_and_inputs_for_common()

							for model_class in self.all_model_classes:
													_UpperCAmelCase             =    model_class(UpperCAmelCase					)
													_UpperCAmelCase             =    inspect.signature(model.call					)
													# signature.parameters is an OrderedDict => so arg_names order is deterministic
													_UpperCAmelCase             =    [*signature.parameters.keys()]

													_UpperCAmelCase             =    ['pixel_values']
													self.assertListEqual(arg_names[:1] ,					UpperCAmelCase					)

	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							_UpperCAmelCase      ,				_UpperCAmelCase             =    self.model_tester.prepare_config_and_inputs_for_common()
							_UpperCAmelCase             =    True

							for model_class in self.all_model_classes:
													_UpperCAmelCase             =    True
													_UpperCAmelCase             =    False
													_UpperCAmelCase             =    True
													_UpperCAmelCase             =    model_class(UpperCAmelCase					)
													_UpperCAmelCase             =    model(**self._prepare_for_class(UpperCAmelCase ,					UpperCAmelCase					)					)
													_UpperCAmelCase             =    outputs.attentions
													_UpperCAmelCase             =    len(self.model_tester.depths					)
													self.assertEqual(len(UpperCAmelCase					) ,					UpperCAmelCase					)

													# check that output_attentions also work using config
													del inputs_dict["output_attentions"]
													_UpperCAmelCase             =    True
													_UpperCAmelCase             =    config.window_size**2
													_UpperCAmelCase             =    model_class(UpperCAmelCase					)
													_UpperCAmelCase             =    model(**self._prepare_for_class(UpperCAmelCase ,					UpperCAmelCase					)					)
													_UpperCAmelCase             =    outputs.attentions
													self.assertEqual(len(UpperCAmelCase					) ,					UpperCAmelCase					)

													self.assertListEqual(
													    list(attentions[0].shape[-3:]					) ,					[self.model_tester.num_heads[0], window_size_squared, window_size_squared] ,					)
													_UpperCAmelCase             =    len(UpperCAmelCase					)

													# Check attention is always last and order is fine
													_UpperCAmelCase             =    True
													_UpperCAmelCase             =    True
													_UpperCAmelCase             =    model_class(UpperCAmelCase					)
													_UpperCAmelCase             =    model(**self._prepare_for_class(UpperCAmelCase ,					UpperCAmelCase					)					)

													if hasattr(self.model_tester ,					'num_hidden_states_types'					):
																			_UpperCAmelCase             =    self.model_tester.num_hidden_states_types
													else:
																			# also another +1 for reshaped_hidden_states
																			_UpperCAmelCase             =    2
													self.assertEqual(out_len + added_hidden_states ,					len(UpperCAmelCase					)					)

													_UpperCAmelCase             =    outputs.attentions

													self.assertEqual(len(UpperCAmelCase					) ,					UpperCAmelCase					)

													self.assertListEqual(
													    list(self_attentions[0].shape[-3:]					) ,					[self.model_tester.num_heads[0], window_size_squared, window_size_squared] ,					)

	def  UpperCamelCase					(							self ,					UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase					):
							"""simple docstring"""







							_UpperCAmelCase             =    model_class(UpperCAmelCase					)
							_UpperCAmelCase             =    model(**self._prepare_for_class(UpperCAmelCase ,					UpperCAmelCase					)					)
							_UpperCAmelCase             =    outputs.hidden_states

							_UpperCAmelCase             =    getattr(
							    self.model_tester ,					'expected_num_hidden_layers' ,					len(self.model_tester.depths					) + 1					)
							self.assertEqual(len(UpperCAmelCase					) ,					UpperCAmelCase					)

							# Swin has a different seq_length
							_UpperCAmelCase             =    to_atuple(config.patch_size					)

							_UpperCAmelCase             =    (image_size[1] // patch_size[1]) * (image_size[0] // patch_size[0])

							self.assertListEqual(
							    list(hidden_states[0].shape[-2:]					) ,					[num_patches, self.model_tester.embed_dim] ,					)

							_UpperCAmelCase             =    outputs.reshaped_hidden_states
							self.assertEqual(len(UpperCAmelCase					) ,					UpperCAmelCase					)

							_UpperCAmelCase      ,				_UpperCAmelCase      ,				_UpperCAmelCase      ,				_UpperCAmelCase             =    reshaped_hidden_states[0].shape

							_UpperCAmelCase             =    tf.reshape(reshaped_hidden_states[0] ,					(batch_size, num_channels, height * width)					)
							_UpperCAmelCase             =    tf.transpose(UpperCAmelCase ,					(0, 2, 1)					)

							self.assertListEqual(
							    list(reshaped_hidden_states.shape[-2:]					) ,					[num_patches, self.model_tester.embed_dim] ,					)

	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							_UpperCAmelCase      ,				_UpperCAmelCase             =    self.model_tester.prepare_config_and_inputs_for_common()

							_UpperCAmelCase             =    to_atuple(self.model_tester.image_size					)

							for model_class in self.all_model_classes:
													_UpperCAmelCase             =    True
													self.check_hidden_states_output(UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase					)

													# check that output_hidden_states also work using config
													del inputs_dict["output_hidden_states"]
													_UpperCAmelCase             =    True

													self.check_hidden_states_output(UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase					)

	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							_UpperCAmelCase      ,				_UpperCAmelCase             =    self.model_tester.prepare_config_and_inputs_for_common()
							_UpperCAmelCase             =    3

							_UpperCAmelCase             =    to_atuple(self.model_tester.image_size					)
							_UpperCAmelCase             =    to_atuple(config.patch_size					)

							_UpperCAmelCase             =    image_size[0] + patch_size[0] - (image_size[0] % patch_size[0])
							_UpperCAmelCase             =    image_size[1] + patch_size[1] - (image_size[1] % patch_size[1])

							for model_class in self.all_model_classes:
													_UpperCAmelCase             =    True
													self.check_hidden_states_output(UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase ,					(padded_height, padded_width)					)

													# check that output_hidden_states also work using config
													del inputs_dict["output_hidden_states"]
													_UpperCAmelCase             =    True
													self.check_hidden_states_output(UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase ,					(padded_height, padded_width)					)

	@slow
	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							for model_name in TF_SWIN_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
													_UpperCAmelCase             =    TFSwinModel.from_pretrained(UpperCAmelCase					)
													self.assertIsNotNone(UpperCAmelCase					)





@require_vision
@require_tf
class __lowerCamelCase				(   unittest.TestCase):





	"""simple docstring"""






	@cached_property
	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							return (
							    AutoImageProcessor.from_pretrained('microsoft/swin-tiny-patch4-window7-224'					)
							    if is_vision_available()
							    else None
							)

	@slow
	def  UpperCamelCase					(							self					):
							"""simple docstring"""







							_UpperCAmelCase             =    TFSwinForImageClassification.from_pretrained('microsoft/swin-tiny-patch4-window7-224'					)
							_UpperCAmelCase             =    self.default_image_processor

							_UpperCAmelCase             =    Image.open('./tests/fixtures/tests_samples/COCO/000000039769.png'					)
							_UpperCAmelCase             =    image_processor(images=UpperCAmelCase ,					return_tensors='tf'					)

							# forward pass
							_UpperCAmelCase             =    model(UpperCAmelCase					)

							# verify the logits
							_UpperCAmelCase             =    tf.TensorShape((1, 1000)					)
							self.assertEqual(outputs.logits.shape ,					UpperCAmelCase					)
							_UpperCAmelCase             =    tf.constant([-0.09_48, -0.64_54, -0.09_21]					)
							self.assertTrue(np.allclose(outputs.logits[0, :3] ,					UpperCAmelCase ,					atol=1e-4					)					)
