


import unittest

from transformers import AlbertConfig, is_torch_available
from transformers.models.auto import get_values
from transformers.testing_utils import require_torch, slow, torch_device

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 (
      MODEL_FOR_PRETRAINING_MAPPING,
      AlbertForMaskedLM,
      AlbertForMultipleChoice,
      AlbertForPreTraining,
      AlbertForQuestionAnswering,
      AlbertForSequenceClassification,
      AlbertForTokenClassification,
      AlbertModel,
  )
  from transformers.models.albert.modeling_albert import ALBERT_PRETRAINED_MODEL_ARCHIVE_LIST







class       lowerCamelCase__   :





     def __init__(self		,     UpperCAmelCase		,     UpperCAmelCase=1_3		,     UpperCAmelCase=7		,     UpperCAmelCase=True		,     UpperCAmelCase=True		,     UpperCAmelCase=True		,     UpperCAmelCase=True		,     UpperCAmelCase=9_9		,     UpperCAmelCase=1_6		,     UpperCAmelCase=3_6		,     UpperCAmelCase=6		,     UpperCAmelCase=6		,     UpperCAmelCase=6		,     UpperCAmelCase=3_7		,     UpperCAmelCase="gelu"		,     UpperCAmelCase=0.1		,     UpperCAmelCase=0.1		,     UpperCAmelCase=5_1_2		,     UpperCAmelCase=1_6		,     UpperCAmelCase=2		,     UpperCAmelCase=0.02		,     UpperCAmelCase=3		,     UpperCAmelCase=4		,     UpperCAmelCase=None		,     )     ->   str:
      _lowercase							      =parent
      _lowercase							      =batch_size
      _lowercase							      =seq_length
      _lowercase							      =is_training
      _lowercase							      =use_input_mask
      _lowercase							      =use_token_type_ids
      _lowercase							      =use_labels
      _lowercase							      =vocab_size
      _lowercase							      =embedding_size
      _lowercase							      =hidden_size
      _lowercase							      =num_hidden_layers
      _lowercase							      =num_hidden_groups
      _lowercase							      =num_attention_heads
      _lowercase							      =intermediate_size
      _lowercase							      =hidden_act
      _lowercase							      =hidden_dropout_prob
      _lowercase							      =attention_probs_dropout_prob
      _lowercase							      =max_position_embeddings
      _lowercase							      =type_vocab_size
      _lowercase							      =type_sequence_label_size
      _lowercase							      =initializer_range
      _lowercase							      =num_labels
      _lowercase							      =num_choices
      _lowercase							      =scope





     def      __A					(self       )     ->   str:
      _lowercase							      =ids_tensor([self.batch_size, self.seq_length]		,     self.vocab_size       )

      _lowercase							      =None
      if self.use_input_mask:
       _lowercase							      =random_attention_mask([self.batch_size, self.seq_length]       )

      _lowercase							      =None
      if self.use_token_type_ids:
       _lowercase							      =ids_tensor([self.batch_size, self.seq_length]		,     self.type_vocab_size       )

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

      _lowercase							      =self.get_config()

      return config, input_ids, token_type_ids, input_mask, sequence_labels, token_labels, choice_labels





     def      __A					(self       )     ->   Optional[Any]:
      return AlbertConfig(
          vocab_size=self.vocab_size		,     hidden_size=self.hidden_size		,     num_hidden_layers=self.num_hidden_layers		,     num_attention_heads=self.num_attention_heads		,     intermediate_size=self.intermediate_size		,     hidden_act=self.hidden_act		,     hidden_dropout_prob=self.hidden_dropout_prob		,     attention_probs_dropout_prob=self.attention_probs_dropout_prob		,     max_position_embeddings=self.max_position_embeddings		,     type_vocab_size=self.type_vocab_size		,     initializer_range=self.initializer_range		,     num_hidden_groups=self.num_hidden_groups		,     )





     def      __A					(self		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase       )     ->   Dict:
      _lowercase							      =AlbertModel(config=__lowerCamelCase       )
      model.to(__lowerCamelCase       )
      model.eval()
      _lowercase							      =model(__lowerCamelCase		,     attention_mask=__lowerCamelCase		,     token_type_ids=__lowerCamelCase       )
      _lowercase							      =model(__lowerCamelCase		,     token_type_ids=__lowerCamelCase       )
      _lowercase							      =model(__lowerCamelCase       )
      self.parent.assertEqual(result.last_hidden_state.shape		,     (self.batch_size, self.seq_length, self.hidden_size)       )
      self.parent.assertEqual(result.pooler_output.shape		,     (self.batch_size, self.hidden_size)       )





     def      __A					(self		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase       )     ->   List[Any]:
      _lowercase							      =AlbertForPreTraining(config=__lowerCamelCase       )
      model.to(__lowerCamelCase       )
      model.eval()
      _lowercase							      =model(
          __lowerCamelCase		,     attention_mask=__lowerCamelCase		,     token_type_ids=__lowerCamelCase		,     labels=__lowerCamelCase		,     sentence_order_label=__lowerCamelCase		,     )
      self.parent.assertEqual(result.prediction_logits.shape		,     (self.batch_size, self.seq_length, self.vocab_size)       )
      self.parent.assertEqual(result.sop_logits.shape		,     (self.batch_size, config.num_labels)       )





     def      __A					(self		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase       )     ->   Dict:
      _lowercase							      =AlbertForMaskedLM(config=__lowerCamelCase       )
      model.to(__lowerCamelCase       )
      model.eval()
      _lowercase							      =model(__lowerCamelCase		,     attention_mask=__lowerCamelCase		,     token_type_ids=__lowerCamelCase		,     labels=__lowerCamelCase       )
      self.parent.assertEqual(result.logits.shape		,     (self.batch_size, self.seq_length, self.vocab_size)       )





     def      __A					(self		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase       )     ->   Dict:
      _lowercase							      =AlbertForQuestionAnswering(config=__lowerCamelCase       )
      model.to(__lowerCamelCase       )
      model.eval()
      _lowercase							      =model(
          __lowerCamelCase		,     attention_mask=__lowerCamelCase		,     token_type_ids=__lowerCamelCase		,     start_positions=__lowerCamelCase		,     end_positions=__lowerCamelCase		,     )
      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      __A					(self		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase       )     ->   int:
      _lowercase							      =self.num_labels
      _lowercase							      =AlbertForSequenceClassification(__lowerCamelCase       )
      model.to(__lowerCamelCase       )
      model.eval()
      _lowercase							      =model(__lowerCamelCase		,     attention_mask=__lowerCamelCase		,     token_type_ids=__lowerCamelCase		,     labels=__lowerCamelCase       )
      self.parent.assertEqual(result.logits.shape		,     (self.batch_size, self.num_labels)       )





     def      __A					(self		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase       )     ->   List[Any]:
      _lowercase							      =self.num_labels
      _lowercase							      =AlbertForTokenClassification(config=__lowerCamelCase       )
      model.to(__lowerCamelCase       )
      model.eval()
      _lowercase							      =model(__lowerCamelCase		,     attention_mask=__lowerCamelCase		,     token_type_ids=__lowerCamelCase		,     labels=__lowerCamelCase       )
      self.parent.assertEqual(result.logits.shape		,     (self.batch_size, self.seq_length, self.num_labels)       )





     def      __A					(self		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase       )     ->   Dict:
      _lowercase							      =self.num_choices
      _lowercase							      =AlbertForMultipleChoice(config=__lowerCamelCase       )
      model.to(__lowerCamelCase       )
      model.eval()
      _lowercase							      =input_ids.unsqueeze(1       ).expand(-1		,     self.num_choices		,     -1       ).contiguous()
      _lowercase							      =token_type_ids.unsqueeze(1       ).expand(-1		,     self.num_choices		,     -1       ).contiguous()
      _lowercase							      =input_mask.unsqueeze(1       ).expand(-1		,     self.num_choices		,     -1       ).contiguous()
      _lowercase							      =model(
          __lowerCamelCase		,     attention_mask=__lowerCamelCase		,     token_type_ids=__lowerCamelCase		,     labels=__lowerCamelCase		,     )
      self.parent.assertEqual(result.logits.shape		,     (self.batch_size, self.num_choices)       )





     def      __A					(self       )     ->   Union[str, Any]:
      _lowercase							      =self.prepare_config_and_inputs()
      (
          _lowercase   
      )							      =config_and_inputs
      _lowercase							      ={"input_ids": input_ids, "token_type_ids": token_type_ids, "attention_mask": input_mask}
      return config, inputs_dict







@require_torch
class       lowerCamelCase__   (       lowercase__   ,							lowercase__   ,							unittest.TestCase):
     SCREAMING_SNAKE_CASE__      			=			(
         (
             AlbertModel,
             AlbertForPreTraining,
             AlbertForMaskedLM,
             AlbertForMultipleChoice,
             AlbertForSequenceClassification,
             AlbertForTokenClassification,
             AlbertForQuestionAnswering,
         )
         if is_torch_available()
         else ()
     )
     SCREAMING_SNAKE_CASE__      			=			(
         {
             '''feature-extraction''': AlbertModel,
             '''fill-mask''': AlbertForMaskedLM,
             '''question-answering''': AlbertForQuestionAnswering,
             '''text-classification''': AlbertForSequenceClassification,
             '''token-classification''': AlbertForTokenClassification,
             '''zero-shot''': AlbertForSequenceClassification,
         }
         if is_torch_available()
         else {}
     )
     SCREAMING_SNAKE_CASE__      			=			True





     def      __A					(self		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase=False       )     ->   Any:
      _lowercase							      =super()._prepare_for_class(__lowerCamelCase		,     __lowerCamelCase		,     return_labels=__lowerCamelCase       )

      if return_labels:
       if model_class in get_values(__lowerCamelCase       ):
        _lowercase							      =torch.zeros(
            (self.model_tester.batch_size, self.model_tester.seq_length)		,     dtype=torch.long		,     device=__lowerCamelCase       )
        _lowercase							      =torch.zeros(
            self.model_tester.batch_size		,     dtype=torch.long		,     device=__lowerCamelCase       )
      return inputs_dict





     def      __A					(self       )     ->   List[str]:
      _lowercase							      =AlbertModelTester(self       )
      _lowercase							      =ConfigTester(self		,     config_class=__lowerCamelCase		,     hidden_size=3_7       )





     def      __A					(self       )     ->   Optional[int]:
      self.config_tester.run_common_tests()





     def      __A					(self       )     ->   Optional[int]:
      _lowercase							      =self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_model(*__lowerCamelCase       )





     def      __A					(self       )     ->   List[Any]:
      _lowercase							      =self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_for_pretraining(*__lowerCamelCase       )





     def      __A					(self       )     ->   Tuple:
      _lowercase							      =self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_for_masked_lm(*__lowerCamelCase       )





     def      __A					(self       )     ->   Any:
      _lowercase							      =self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_for_multiple_choice(*__lowerCamelCase       )





     def      __A					(self       )     ->   List[Any]:
      _lowercase							      =self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_for_question_answering(*__lowerCamelCase       )





     def      __A					(self       )     ->   str:
      _lowercase							      =self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_for_sequence_classification(*__lowerCamelCase       )





     def      __A					(self       )     ->   int:
      _lowercase							      =self.model_tester.prepare_config_and_inputs()
      for type in ["absolute", "relative_key", "relative_key_query"]:
       _lowercase							      =type
       self.model_tester.create_and_check_model(*__lowerCamelCase       )





     @slow
     def      __A					(self       )     ->   List[Any]:



      for model_name in ALBERT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
       _lowercase							      =AlbertModel.from_pretrained(__lowerCamelCase       )
       self.assertIsNotNone(__lowerCamelCase       )







@require_torch
class       lowerCamelCase__   (       unittest.TestCase):





     @slow
     def      __A					(self       )     ->   Union[str, Any]:
      _lowercase							      =AlbertModel.from_pretrained('''albert-base-v2'''       )
      _lowercase							      =torch.tensor([[0, 3_4_5, 2_3_2, 3_2_8, 7_4_0, 1_4_0, 1_6_9_5, 6_9, 6_0_7_8, 1_5_8_8, 2]]       )
      _lowercase							      =torch.tensor([[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]       )
      with torch.no_grad():
       _lowercase							      =model(__lowerCamelCase		,     attention_mask=__lowerCamelCase       )[0]
      _lowercase							      =torch.Size((1, 1_1, 7_6_8)       )
      self.assertEqual(output.shape		,     __lowerCamelCase       )
      _lowercase							      =torch.tensor(
          [[[-0.6513, 1.5035, -0.2766], [-0.6515, 1.5046, -0.2780], [-0.6512, 1.5049, -0.2784]]]       )

      self.assertTrue(torch.allclose(output[:, 1:4, 1:4]		,     __lowerCamelCase		,     atol=1e-4       )       )





from __future__ import annotations

A      :    Union[str, Any]		=					{
    "A": ["B", "C", "E"],
    "B": ["A", "D", "E"],
    "C": ["A", "F", "G"],
    "D": ["B"],
    "E": ["A", "B", "D"],
    "F": ["C"],
    "G": ["C"],
}







class 			_lowercase :


       """simple docstring"""




       def __init__(   self							:			Tuple					,      __lowerCamelCase							:			dict[str, list[str]]					,      __lowerCamelCase							:			str       ):


             '''simple docstring'''



             lowerCamelCase__		:				Union[str, Any]    =  graph
             # mapping node to its parent in resulting breadth first tree
             lowerCamelCase__		:				dict[str, str | None]    =  {}
             lowerCamelCase__		:				Dict    =  source_vertex





       def 						lowerCAmelCase     (   self							:			Any       ):


             '''simple docstring'''



             lowerCamelCase__		:				int    =  {self.source_vertex}
             lowerCamelCase__		:				Optional[int]    =  None
             lowerCamelCase__		:				Dict    =  [self.source_vertex]  # first in first out queue

             while queue:
                   lowerCamelCase__		:				Optional[int]    =  queue.pop(0       )
                   for adjacent_vertex in self.graph[vertex]:
                         if adjacent_vertex not in visited:
                               visited.add(__lowerCamelCase       )
                               lowerCamelCase__		:				List[str]    =  vertex
                               queue.append(__lowerCamelCase       )





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


             '''simple docstring'''



             if target_vertex == self.source_vertex:
                   return self.source_vertex

             lowerCamelCase__		:				Tuple    =  self.parent.get(__lowerCamelCase       )
             if target_vertex_parent is None:
                   lowerCamelCase__		:				Tuple    =  (
                       f"No path from vertex: {self.source_vertex} to vertex: {target_vertex}"
                   )
                   raise ValueError(__lowerCamelCase       )

             return self.shortest_path(__lowerCamelCase       ) + f"->{target_vertex}"


if __name__ == "__main__":
    A      :    List[str]		=					Graph(graph, "G")
    g.breath_first_search()
    print(g.shortest_path("D"))
    print(g.shortest_path("G"))
    print(g.shortest_path("Foo"))


