




"""simple docstring"""

import unittest

from transformers import XLMConfig, is_torch_available
from transformers.testing_utils import require_torch, slow, torch_device

from ...generation.test_utils import GenerationTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
       import torch

       from transformers import (
           XLMForMultipleChoice,
           XLMForQuestionAnswering,
           XLMForQuestionAnsweringSimple,
           XLMForSequenceClassification,
           XLMForTokenClassification,
           XLMModel,
           XLMWithLMHeadModel,
       )
       from transformers.models.xlm.modeling_xlm import XLM_PRETRAINED_MODEL_ARCHIVE_LIST





class 							lowercase_			:



 '''simple docstring'''

 def __init__(					self			:			Dict       ,				_UpperCAmelCase			:			Any       ,				_UpperCAmelCase			:			List[Any]=13       ,				_UpperCAmelCase			:			List[Any]=7       ,				_UpperCAmelCase			:			Dict=True       ,				_UpperCAmelCase			:			Dict=True       ,				_UpperCAmelCase			:			Optional[Any]=True       ,				_UpperCAmelCase			:			str=True       ,				_UpperCAmelCase			:			Any=True       ,				_UpperCAmelCase			:			str=False       ,				_UpperCAmelCase			:			Tuple=False       ,				_UpperCAmelCase			:			Optional[Any]=False       ,				_UpperCAmelCase			:			List[Any]=2       ,				_UpperCAmelCase			:			List[Any]=99       ,				_UpperCAmelCase			:			Optional[Any]=0       ,				_UpperCAmelCase			:			List[str]=32       ,				_UpperCAmelCase			:			List[Any]=5       ,				_UpperCAmelCase			:			str=4       ,				_UpperCAmelCase			:			Dict=0.1       ,				_UpperCAmelCase			:			int=0.1       ,				_UpperCAmelCase			:			List[str]=512       ,				_UpperCAmelCase			:			Optional[Any]=2       ,				_UpperCAmelCase			:			Any=0.02       ,				_UpperCAmelCase			:			Union[str, Any]=2       ,				_UpperCAmelCase			:			Any=4       ,				_UpperCAmelCase			:			List[Any]="last"       ,				_UpperCAmelCase			:			Any=True       ,				_UpperCAmelCase			:			Union[str, Any]=None       ,				_UpperCAmelCase			:			List[str]=0       ,				):
       _A     =  parent
       _A     =  batch_size
       _A     =  seq_length
       _A     =  is_training
       _A     =  use_input_lengths
       _A     =  use_token_type_ids
       _A     =  use_labels
       _A     =  gelu_activation
       _A     =  sinusoidal_embeddings
       _A     =  causal
       _A     =  asm
       _A     =  n_langs
       _A     =  vocab_size
       _A     =  n_special
       _A     =  hidden_size
       _A     =  num_hidden_layers
       _A     =  num_attention_heads
       _A     =  hidden_dropout_prob
       _A     =  attention_probs_dropout_prob
       _A     =  max_position_embeddings
       _A     =  type_sequence_label_size
       _A     =  initializer_range
       _A     =  num_labels
       _A     =  num_choices
       _A     =  summary_type
       _A     =  use_proj
       _A     =  scope
       _A     =  bos_token_id

 def      lowerCAmelCase_				(					self			:			str						):
       _A     =  ids_tensor([self.batch_size, self.seq_length]       ,				self.vocab_size						)
       _A     =  random_attention_mask([self.batch_size, self.seq_length]						)

       _A     =  None
       if self.use_input_lengths:
             _A     =  (
                 ids_tensor([self.batch_size]       ,				vocab_size=2						) + self.seq_length - 2
             )  # small variation of seq_length

       _A     =  None
       if self.use_token_type_ids:
             _A     =  ids_tensor([self.batch_size, self.seq_length]       ,				self.n_langs						)

       _A     =  None
       _A     =  None
       _A     =  None
       if self.use_labels:
             _A     =  ids_tensor([self.batch_size]       ,				self.type_sequence_label_size						)
             _A     =  ids_tensor([self.batch_size, self.seq_length]       ,				self.num_labels						)
             _A     =  ids_tensor([self.batch_size]       ,				2						).float()
             _A     =  ids_tensor([self.batch_size]       ,				self.num_choices						)

       _A     =  self.get_config()

       return (
           config,
           input_ids,
           token_type_ids,
           input_lengths,
           sequence_labels,
           token_labels,
           is_impossible_labels,
           choice_labels,
           input_mask,
       )

 def      lowerCAmelCase_				(					self			:			Tuple						):
       return XLMConfig(
           vocab_size=self.vocab_size       ,				n_special=self.n_special       ,				emb_dim=self.hidden_size       ,				n_layers=self.num_hidden_layers       ,				n_heads=self.num_attention_heads       ,				dropout=self.hidden_dropout_prob       ,				attention_dropout=self.attention_probs_dropout_prob       ,				gelu_activation=self.gelu_activation       ,				sinusoidal_embeddings=self.sinusoidal_embeddings       ,				asm=self.asm       ,				causal=self.causal       ,				n_langs=self.n_langs       ,				max_position_embeddings=self.max_position_embeddings       ,				initializer_range=self.initializer_range       ,				summary_type=self.summary_type       ,				use_proj=self.use_proj       ,				num_labels=self.num_labels       ,				bos_token_id=self.bos_token_id       ,				)

 def      lowerCAmelCase_				(					self			:			Dict       ,				_UpperCAmelCase			:			List[str]       ,				_UpperCAmelCase			:			Any       ,				_UpperCAmelCase			:			Any       ,				_UpperCAmelCase			:			Dict       ,				_UpperCAmelCase			:			Union[str, Any]       ,				_UpperCAmelCase			:			Optional[int]       ,				_UpperCAmelCase			:			Tuple       ,				_UpperCAmelCase			:			List[Any]       ,				_UpperCAmelCase			:			Tuple       ,				):
       _A     =  XLMModel(config=_UpperCAmelCase						)
       model.to(_UpperCAmelCase						)
       model.eval()
       _A     =  model(_UpperCAmelCase       ,				lengths=_UpperCAmelCase       ,				langs=_UpperCAmelCase						)
       _A     =  model(_UpperCAmelCase       ,				langs=_UpperCAmelCase						)
       _A     =  model(_UpperCAmelCase						)
       self.parent.assertEqual(result.last_hidden_state.shape       ,				(self.batch_size, self.seq_length, self.hidden_size)						)

 def      lowerCAmelCase_				(					self			:			Optional[Any]       ,				_UpperCAmelCase			:			Optional[int]       ,				_UpperCAmelCase			:			Optional[int]       ,				_UpperCAmelCase			:			int       ,				_UpperCAmelCase			:			Dict       ,				_UpperCAmelCase			:			str       ,				_UpperCAmelCase			:			Any       ,				_UpperCAmelCase			:			Optional[Any]       ,				_UpperCAmelCase			:			Optional[Any]       ,				_UpperCAmelCase			:			Union[str, Any]       ,				):
       _A     =  XLMWithLMHeadModel(_UpperCAmelCase						)
       model.to(_UpperCAmelCase						)
       model.eval()

       _A     =  model(_UpperCAmelCase       ,				token_type_ids=_UpperCAmelCase       ,				labels=_UpperCAmelCase						)
       self.parent.assertEqual(result.loss.shape       ,				()						)
       self.parent.assertEqual(result.logits.shape       ,				(self.batch_size, self.seq_length, self.vocab_size)						)

 def      lowerCAmelCase_				(					self			:			int       ,				_UpperCAmelCase			:			Union[str, Any]       ,				_UpperCAmelCase			:			Dict       ,				_UpperCAmelCase			:			str       ,				_UpperCAmelCase			:			Dict       ,				_UpperCAmelCase			:			Tuple       ,				_UpperCAmelCase			:			Dict       ,				_UpperCAmelCase			:			str       ,				_UpperCAmelCase			:			Dict       ,				_UpperCAmelCase			:			Union[str, Any]       ,				):
       _A     =  XLMForQuestionAnsweringSimple(_UpperCAmelCase						)
       model.to(_UpperCAmelCase						)
       model.eval()

       _A     =  model(_UpperCAmelCase						)

       _A     =  model(_UpperCAmelCase       ,				start_positions=_UpperCAmelCase       ,				end_positions=_UpperCAmelCase						)
       _A     =  outputs
       self.parent.assertEqual(result.start_logits.shape       ,				(self.batch_size, self.seq_length)						)
       self.parent.assertEqual(result.end_logits.shape       ,				(self.batch_size, self.seq_length)						)

 def      lowerCAmelCase_				(					self			:			Tuple       ,				_UpperCAmelCase			:			str       ,				_UpperCAmelCase			:			str       ,				_UpperCAmelCase			:			Tuple       ,				_UpperCAmelCase			:			Optional[int]       ,				_UpperCAmelCase			:			str       ,				_UpperCAmelCase			:			int       ,				_UpperCAmelCase			:			Union[str, Any]       ,				_UpperCAmelCase			:			Any       ,				_UpperCAmelCase			:			List[str]       ,				):
       _A     =  XLMForQuestionAnswering(_UpperCAmelCase						)
       model.to(_UpperCAmelCase						)
       model.eval()

       _A     =  model(_UpperCAmelCase						)

       _A     =  model(
           _UpperCAmelCase       ,				start_positions=_UpperCAmelCase       ,				end_positions=_UpperCAmelCase       ,				cls_index=_UpperCAmelCase       ,				is_impossible=_UpperCAmelCase       ,				p_mask=_UpperCAmelCase       ,				)

       _A     =  model(
           _UpperCAmelCase       ,				start_positions=_UpperCAmelCase       ,				end_positions=_UpperCAmelCase       ,				cls_index=_UpperCAmelCase       ,				is_impossible=_UpperCAmelCase       ,				)

       ((_A)  ,       )     =  result_with_labels.to_tuple()

       _A     =  model(_UpperCAmelCase       ,				start_positions=_UpperCAmelCase       ,				end_positions=_UpperCAmelCase						)

       ((_A)  ,       )     =  result_with_labels.to_tuple()

       self.parent.assertEqual(result_with_labels.loss.shape       ,				()						)
       self.parent.assertEqual(result.start_top_log_probs.shape       ,				(self.batch_size, model.config.start_n_top)						)
       self.parent.assertEqual(result.start_top_index.shape       ,				(self.batch_size, model.config.start_n_top)						)
       self.parent.assertEqual(
           result.end_top_log_probs.shape       ,				(self.batch_size, model.config.start_n_top * model.config.end_n_top)						)
       self.parent.assertEqual(
           result.end_top_index.shape       ,				(self.batch_size, model.config.start_n_top * model.config.end_n_top)						)
       self.parent.assertEqual(result.cls_logits.shape       ,				(self.batch_size,)						)

 def      lowerCAmelCase_				(					self			:			Union[str, Any]       ,				_UpperCAmelCase			:			str       ,				_UpperCAmelCase			:			str       ,				_UpperCAmelCase			:			int       ,				_UpperCAmelCase			:			Dict       ,				_UpperCAmelCase			:			str       ,				_UpperCAmelCase			:			str       ,				_UpperCAmelCase			:			str       ,				_UpperCAmelCase			:			Tuple       ,				_UpperCAmelCase			:			int       ,				):
       _A     =  XLMForSequenceClassification(_UpperCAmelCase						)
       model.to(_UpperCAmelCase						)
       model.eval()

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

 def      lowerCAmelCase_				(					self			:			str       ,				_UpperCAmelCase			:			str       ,				_UpperCAmelCase			:			str       ,				_UpperCAmelCase			:			List[str]       ,				_UpperCAmelCase			:			List[Any]       ,				_UpperCAmelCase			:			Union[str, Any]       ,				_UpperCAmelCase			:			Optional[Any]       ,				_UpperCAmelCase			:			Optional[Any]       ,				_UpperCAmelCase			:			List[Any]       ,				_UpperCAmelCase			:			Union[str, Any]       ,				):
       _A     =  self.num_labels
       _A     =  XLMForTokenClassification(_UpperCAmelCase						)
       model.to(_UpperCAmelCase						)
       model.eval()

       _A     =  model(_UpperCAmelCase       ,				attention_mask=_UpperCAmelCase       ,				labels=_UpperCAmelCase						)
       self.parent.assertEqual(result.logits.shape       ,				(self.batch_size, self.seq_length, self.num_labels)						)

 def      lowerCAmelCase_				(					self			:			Optional[int]       ,				_UpperCAmelCase			:			Union[str, Any]       ,				_UpperCAmelCase			:			Any       ,				_UpperCAmelCase			:			List[str]       ,				_UpperCAmelCase			:			List[Any]       ,				_UpperCAmelCase			:			List[str]       ,				_UpperCAmelCase			:			str       ,				_UpperCAmelCase			:			Optional[Any]       ,				_UpperCAmelCase			:			List[str]       ,				_UpperCAmelCase			:			Tuple       ,				):
       _A     =  self.num_choices
       _A     =  XLMForMultipleChoice(config=_UpperCAmelCase						)
       model.to(_UpperCAmelCase						)
       model.eval()
       _A     =  input_ids.unsqueeze(1						).expand(-1       ,				self.num_choices       ,				-1						).contiguous()
       _A     =  token_type_ids.unsqueeze(1						).expand(-1       ,				self.num_choices       ,				-1						).contiguous()
       _A     =  input_mask.unsqueeze(1						).expand(-1       ,				self.num_choices       ,				-1						).contiguous()
       _A     =  model(
           _UpperCAmelCase       ,				attention_mask=_UpperCAmelCase       ,				token_type_ids=_UpperCAmelCase       ,				labels=_UpperCAmelCase       ,				)
       self.parent.assertEqual(result.logits.shape       ,				(self.batch_size, self.num_choices)						)



 def      lowerCAmelCase_				(					self			:			List[Any]						):
       _A     =  self.prepare_config_and_inputs()
       (
           (
           _A
       )  ,       (
           _A
       )  ,       (
           _A
       )  ,       (
           _A
       )  ,       (
           _A
       )  ,       (
           _A
       )  ,       (
           _A
       )  ,       (
           _A
       )  ,       (
           _A
       )  ,       
       )     =  config_and_inputs
       _A     =  {'input_ids': input_ids, 'token_type_ids': token_type_ids, 'lengths': input_lengths}
       return config, inputs_dict





@require_torch
class 							lowercase_			(	__lowerCAmelCase     ,      __lowerCAmelCase     ,      __lowerCAmelCase     ,      unittest.TestCase				):



 '''simple docstring'''
 UpperCAmelCase       :	List[str]     =      (
     (
         XLMModel,
         XLMWithLMHeadModel,
         XLMForQuestionAnswering,
         XLMForSequenceClassification,
         XLMForQuestionAnsweringSimple,
         XLMForTokenClassification,
         XLMForMultipleChoice,
     )
     if is_torch_available()
     else ()
 )
 UpperCAmelCase       :	List[str]     =      (
     (XLMWithLMHeadModel,) if is_torch_available() else ()
 )  # TODO (PVP): Check other models whether language generation is also applicable
 UpperCAmelCase       :	Optional[int]     =      (
     {
         '''feature-extraction''': XLMModel,
         '''fill-mask''': XLMWithLMHeadModel,
         '''question-answering''': XLMForQuestionAnsweringSimple,
         '''text-classification''': XLMForSequenceClassification,
         '''text-generation''': XLMWithLMHeadModel,
         '''token-classification''': XLMForTokenClassification,
         '''zero-shot''': XLMForSequenceClassification,
     }
     if is_torch_available()
     else {}
 )

 def      lowerCAmelCase_				(					self			:			Union[str, Any]       ,				_UpperCAmelCase			:			Optional[Any]       ,				_UpperCAmelCase			:			List[Any]       ,				_UpperCAmelCase			:			Optional[Any]       ,				_UpperCAmelCase			:			str       ,				_UpperCAmelCase			:			Optional[Any]						):
       if (
           pipeline_test_casse_name == "QAPipelineTests"
           and tokenizer_name is not None
           and not tokenizer_name.endswith('Fast'						)
       ):
             # `QAPipelineTests` fails for a few models when the slower tokenizer are used.
             # (The slower tokenizers were never used for pipeline tests before the pipeline testing rework)
             # TODO: check (and possibly fix) the `QAPipelineTests` with slower tokenizer
             return True

       return False

 def      lowerCAmelCase_				(					self			:			List[Any]       ,				_UpperCAmelCase			:			Tuple       ,				_UpperCAmelCase			:			Optional[int]       ,				_UpperCAmelCase			:			List[Any]=False						):
       _A     =  super()._prepare_for_class(_UpperCAmelCase       ,				_UpperCAmelCase       ,				return_labels=_UpperCAmelCase						)

       if return_labels:
             if model_class.__name__ == "XLMForQuestionAnswering":
                   _A     =  torch.zeros(
                       self.model_tester.batch_size       ,				dtype=torch.long       ,				device=_UpperCAmelCase						)
                   _A     =  torch.zeros(
                       self.model_tester.batch_size       ,				dtype=torch.long       ,				device=_UpperCAmelCase						)

       return inputs_dict

 def      lowerCAmelCase_				(					self			:			Tuple						):
       _A     =  XLMModelTester(self						)
       _A     =  ConfigTester(self       ,				config_class=_UpperCAmelCase       ,				emb_dim=37						)

 def      lowerCAmelCase_				(					self			:			List[Any]						):
       self.config_tester.run_common_tests()

 def      lowerCAmelCase_				(					self			:			List[Any]						):
       _A     =  self.model_tester.prepare_config_and_inputs()
       self.model_tester.create_and_check_xlm_model(*_UpperCAmelCase						)

 def      lowerCAmelCase_				(					self			:			List[str]						):
       _A     =  self.model_tester.prepare_config_and_inputs()
       self.model_tester.create_and_check_xlm_lm_head(*_UpperCAmelCase						)

 def      lowerCAmelCase_				(					self			:			Any						):
       _A     =  self.model_tester.prepare_config_and_inputs()
       self.model_tester.create_and_check_xlm_simple_qa(*_UpperCAmelCase						)

 def      lowerCAmelCase_				(					self			:			Optional[Any]						):
       _A     =  self.model_tester.prepare_config_and_inputs()
       self.model_tester.create_and_check_xlm_qa(*_UpperCAmelCase						)

 def      lowerCAmelCase_				(					self			:			Dict						):
       _A     =  self.model_tester.prepare_config_and_inputs()
       self.model_tester.create_and_check_xlm_sequence_classif(*_UpperCAmelCase						)

 def      lowerCAmelCase_				(					self			:			Optional[Any]						):
       _A     =  self.model_tester.prepare_config_and_inputs()
       self.model_tester.create_and_check_xlm_token_classif(*_UpperCAmelCase						)

 def      lowerCAmelCase_				(					self			:			Dict						):
       _A     =  self.model_tester.prepare_config_and_inputs()
       self.model_tester.create_and_check_xlm_for_multiple_choice(*_UpperCAmelCase						)

 def      lowerCAmelCase_				(					self			:			Dict       ,				_UpperCAmelCase			:			str       ,				_UpperCAmelCase			:			Union[str, Any]       ,				_UpperCAmelCase			:			str       ,				_UpperCAmelCase			:			Optional[int]       ,				_UpperCAmelCase			:			Optional[Any]       ,				_UpperCAmelCase			:			Optional[Any]=False       ,				_UpperCAmelCase			:			int=1						):
       self.assertIsInstance(_UpperCAmelCase       ,				_UpperCAmelCase						)
       self.assertListEqual(
           [isinstance(_UpperCAmelCase       ,				_UpperCAmelCase						) for iter_attentions in attentions]       ,				[True] * len(_UpperCAmelCase						)						)
       self.assertEqual(len(_UpperCAmelCase						)       ,				(max_length - min_length) * num_beam_groups						)

       for idx, iter_attentions in enumerate(_UpperCAmelCase						):
             # adds PAD dummy token
             _A     =  min_length + idx + 1
             _A     =  min_length + idx + 1

             _A     =  (
                 batch_size * num_beam_groups,
                 config.num_attention_heads,
                 tgt_len,
                 src_len,
             )
             # check attn size
             self.assertListEqual(
                 [layer_attention.shape for layer_attention in iter_attentions]       ,				[expected_shape] * len(_UpperCAmelCase						)						)

 def      lowerCAmelCase_				(					self			:			Any       ,				_UpperCAmelCase			:			List[str]       ,				_UpperCAmelCase			:			Any       ,				_UpperCAmelCase			:			Tuple       ,				_UpperCAmelCase			:			List[str]       ,				_UpperCAmelCase			:			int       ,				_UpperCAmelCase			:			List[Any]=False       ,				_UpperCAmelCase			:			Optional[int]=1						):
       self.assertIsInstance(_UpperCAmelCase       ,				_UpperCAmelCase						)
       self.assertListEqual(
           [isinstance(_UpperCAmelCase       ,				_UpperCAmelCase						) for iter_hidden_states in hidden_states]       ,				[True] * len(_UpperCAmelCase						)       ,				)
       self.assertEqual(len(_UpperCAmelCase						)       ,				(max_length - min_length) * num_beam_groups						)

       for idx, iter_hidden_states in enumerate(_UpperCAmelCase						):
             # adds PAD dummy token
             _A     =  min_length + idx + 1
             _A     =  (batch_size * num_beam_groups, seq_len, config.hidden_size)
             # check hidden size
             self.assertListEqual(
                 [layer_hidden_states.shape for layer_hidden_states in iter_hidden_states]       ,				[expected_shape] * len(_UpperCAmelCase						)       ,				)
       pass



 @slow
 def      lowerCAmelCase_				(					self			:			Dict						):
       for model_name in XLM_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
             _A     =  XLMModel.from_pretrained(_UpperCAmelCase						)
             self.assertIsNotNone(_UpperCAmelCase						)





@require_torch
class 							lowercase_			(	unittest.TestCase				):



 '''simple docstring'''

 @slow
 def      lowerCAmelCase_				(					self			:			str						):
       _A     =  XLMWithLMHeadModel.from_pretrained('xlm-mlm-en-2048'						)
       model.to(_UpperCAmelCase						)
       _A     =  torch.tensor([[14, 447]]       ,				dtype=torch.long       ,				device=_UpperCAmelCase						)  # the president
       _A     =  [
           14,
           447,
           14,
           447,
           14,
           447,
           14,
           447,
           14,
           447,
           14,
           447,
           14,
           447,
           14,
           447,
           14,
           447,
           14,
           447,
       ]  # the president the president the president the president the president the president the president the president the president the president
       # TODO(PVP): this and other input_ids I tried for generation give pretty bad results. Not sure why. Model might just not be made for auto-regressive inference
       _A     =  model.generate(_UpperCAmelCase       ,				do_sample=_UpperCAmelCase						)
       self.assertListEqual(output_ids[0].cpu().numpy().tolist()       ,				_UpperCAmelCase						)







"""simple docstring"""

class 							lowercase_			:



 '''simple docstring'''

 def __init__(					self			:			List[Any]       ,				_UpperCAmelCase			:			Optional[Any]       ,				_UpperCAmelCase			:			int       ,				_UpperCAmelCase			:			int						):
       _A     =  None
       _A     =  None
       _A     =  graph

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

 def      lowerCAmelCase_				(					self			:			Optional[Any]       ,				_UpperCAmelCase			:			Union[str, Any]       ,				_UpperCAmelCase			:			Dict						):
       if sources is int:
             _A     =  [sources]
       if sinks is int:
             _A     =  [sinks]

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

       _A     =  sources[0]
       _A     =  sinks[0]

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

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

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

 def      lowerCAmelCase_				(					self			:			Optional[Any]						):
       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      lowerCAmelCase_				(					self			:			List[str]       ,				_UpperCAmelCase			:			Union[str, Any]						):
       _A     =  algorithm(self						)





class 							lowercase_			:



 '''simple docstring'''

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

 def      lowerCAmelCase_				(					self			:			Optional[Any]						):
       if not self.executed:
             self._algorithm()
             _A     =  True



 def      lowerCAmelCase_				(					self			:			int						):
       pass





class 							lowercase_			(	__lowerCAmelCase				):



 '''simple docstring'''

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



 def      lowerCAmelCase_				(					self			:			Optional[Any]						):
       if not self.executed:
             raise Exception('You should execute algorithm before using its result!'						)

       return self.maximum_flow





class 							lowercase_			(	__lowerCAmelCase				):



 '''simple docstring'''

 def __init__(					self			:			Dict       ,				_UpperCAmelCase			:			List[Any]						):
       super().__init__(_UpperCAmelCase						)

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

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

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

       # move through list
       _A     =  0
       while i < len(_UpperCAmelCase						):
             _A     =  vertices_list[i]
             _A     =  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						)						)
                   _A     =  0
             else:
                   i += 1

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

 def      lowerCAmelCase_				(					self			:			int       ,				_UpperCAmelCase			:			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(_UpperCAmelCase       ,				_UpperCAmelCase						)

             self.relabel(_UpperCAmelCase						)

 def      lowerCAmelCase_				(					self			:			Dict       ,				_UpperCAmelCase			:			Tuple       ,				_UpperCAmelCase			:			Tuple						):
       _A     =  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      lowerCAmelCase_				(					self			:			Union[str, Any]       ,				_UpperCAmelCase			:			int						):
       _A     =  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):
                   _A     =  self.heights[to_index]

       if min_height is not None:
             _A     =  min_height + 1


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

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

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

