
"""simple docstring"""







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 							__magic_name__     :





					def __init__(				self   :							Optional[int]							,						snake_case_   :							Optional[int]							,						snake_case_   :							Union[str, Any]=13							,						snake_case_   :							Optional[int]=7							,						snake_case_   :							List[str]=True							,						snake_case_   :							Union[str, Any]=True							,						snake_case_   :							Tuple=True							,						snake_case_   :							Any=True							,						snake_case_   :							str=99							,						snake_case_   :							int=16							,						snake_case_   :							str=36							,						snake_case_   :							Union[str, Any]=6							,						snake_case_   :							Tuple=6							,						snake_case_   :							List[Any]=6							,						snake_case_   :							int=37							,						snake_case_   :							List[Any]="gelu"							,						snake_case_   :							int=0.1							,						snake_case_   :							Optional[Any]=0.1							,						snake_case_   :							Optional[Any]=512							,						snake_case_   :							Dict=16							,						snake_case_   :							Tuple=2							,						snake_case_   :							List[Any]=0.02							,						snake_case_   :							Union[str, Any]=3							,						snake_case_   :							Any=4							,						snake_case_   :							Optional[Any]=None							,						):
												__snake_case     			=       parent
												__snake_case     			=       batch_size
												__snake_case     			=       seq_length
												__snake_case     			=       is_training
												__snake_case     			=       use_input_mask
												__snake_case     			=       use_token_type_ids
												__snake_case     			=       use_labels
												__snake_case     			=       vocab_size
												__snake_case     			=       embedding_size
												__snake_case     			=       hidden_size
												__snake_case     			=       num_hidden_layers
												__snake_case     			=       num_hidden_groups
												__snake_case     			=       num_attention_heads
												__snake_case     			=       intermediate_size
												__snake_case     			=       hidden_act
												__snake_case     			=       hidden_dropout_prob
												__snake_case     			=       attention_probs_dropout_prob
												__snake_case     			=       max_position_embeddings
												__snake_case     			=       type_vocab_size
												__snake_case     			=       type_sequence_label_size
												__snake_case     			=       initializer_range
												__snake_case     			=       num_labels
												__snake_case     			=       num_choices
												__snake_case     			=       scope





					def 							lowerCAmelCase      (				self   :							Optional[int]    ):
												__snake_case     			=       ids_tensor([self.batch_size, self.seq_length]							,						self.vocab_size    )

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

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

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

												__snake_case     			=       self.get_config()

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





					def 							lowerCAmelCase      (				self   :							str    ):
												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 							lowerCAmelCase      (				self   :							List[Any]							,						snake_case_   :							Any							,						snake_case_   :							List[str]							,						snake_case_   :							str							,						snake_case_   :							Optional[int]							,						snake_case_   :							List[Any]							,						snake_case_   :							Tuple							,						snake_case_   :							int    ):
												__snake_case     			=       AlbertModel(config=snake_case_    )
												model.to(snake_case_    )
												model.eval()
												__snake_case     			=       model(snake_case_							,						attention_mask=snake_case_							,						token_type_ids=snake_case_    )
												__snake_case     			=       model(snake_case_							,						token_type_ids=snake_case_    )
												__snake_case     			=       model(snake_case_    )
												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 							lowerCAmelCase      (				self   :							List[str]							,						snake_case_   :							Any							,						snake_case_   :							List[Any]							,						snake_case_   :							Optional[int]							,						snake_case_   :							Optional[int]							,						snake_case_   :							str							,						snake_case_   :							Optional[Any]							,						snake_case_   :							List[str]    ):
												__snake_case     			=       AlbertForPreTraining(config=snake_case_    )
												model.to(snake_case_    )
												model.eval()
												__snake_case     			=       model(
												    snake_case_							,						attention_mask=snake_case_							,						token_type_ids=snake_case_							,						labels=snake_case_							,						sentence_order_label=snake_case_							,						)
												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 							lowerCAmelCase      (				self   :							Union[str, Any]							,						snake_case_   :							Optional[Any]							,						snake_case_   :							Any							,						snake_case_   :							List[Any]							,						snake_case_   :							List[str]							,						snake_case_   :							List[str]							,						snake_case_   :							Optional[int]							,						snake_case_   :							Union[str, Any]    ):
												__snake_case     			=       AlbertForMaskedLM(config=snake_case_    )
												model.to(snake_case_    )
												model.eval()
												__snake_case     			=       model(snake_case_							,						attention_mask=snake_case_							,						token_type_ids=snake_case_							,						labels=snake_case_    )
												self.parent.assertEqual(result.logits.shape							,						(self.batch_size, self.seq_length, self.vocab_size)    )





					def 							lowerCAmelCase      (				self   :							Optional[Any]							,						snake_case_   :							List[str]							,						snake_case_   :							Dict							,						snake_case_   :							Optional[int]							,						snake_case_   :							str							,						snake_case_   :							Union[str, Any]							,						snake_case_   :							int							,						snake_case_   :							Union[str, Any]    ):
												__snake_case     			=       AlbertForQuestionAnswering(config=snake_case_    )
												model.to(snake_case_    )
												model.eval()
												__snake_case     			=       model(
												    snake_case_							,						attention_mask=snake_case_							,						token_type_ids=snake_case_							,						start_positions=snake_case_							,						end_positions=snake_case_							,						)
												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							,						snake_case_   :							List[Any]							,						snake_case_   :							Any							,						snake_case_   :							List[Any]							,						snake_case_   :							List[Any]							,						snake_case_   :							Optional[Any]							,						snake_case_   :							Tuple							,						snake_case_   :							List[str]    ):
												__snake_case     			=       self.num_labels
												__snake_case     			=       AlbertForSequenceClassification(snake_case_    )
												model.to(snake_case_    )
												model.eval()
												__snake_case     			=       model(snake_case_							,						attention_mask=snake_case_							,						token_type_ids=snake_case_							,						labels=snake_case_    )
												self.parent.assertEqual(result.logits.shape							,						(self.batch_size, self.num_labels)    )





					def 							lowerCAmelCase      (				self   :							int							,						snake_case_   :							Optional[int]							,						snake_case_   :							List[Any]							,						snake_case_   :							Dict							,						snake_case_   :							Optional[int]							,						snake_case_   :							List[str]							,						snake_case_   :							List[Any]							,						snake_case_   :							Any    ):
												__snake_case     			=       self.num_labels
												__snake_case     			=       AlbertForTokenClassification(config=snake_case_    )
												model.to(snake_case_    )
												model.eval()
												__snake_case     			=       model(snake_case_							,						attention_mask=snake_case_							,						token_type_ids=snake_case_							,						labels=snake_case_    )
												self.parent.assertEqual(result.logits.shape							,						(self.batch_size, self.seq_length, self.num_labels)    )





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





					def 							lowerCAmelCase      (				self   :							Optional[int]    ):
												__snake_case     			=       self.prepare_config_and_inputs()
												(
												    (
												    __snake_case
												)			,   (
												    __snake_case
												)			,   (
												    __snake_case
												)			,   (
												    __snake_case
												)			,   (
												    __snake_case
												)			,   (
												    __snake_case
												)			,   (
												    __snake_case
												)			,   
												)     			=       config_and_inputs
												__snake_case     			=       {"input_ids": input_ids, "token_type_ids": token_type_ids, "attention_mask": input_mask}
												return config, inputs_dict







@require_torch
class 							__magic_name__     (		lowercase__      ,		lowercase__      ,		unittest.TestCase   ):
					_SCREAMING_SNAKE_CASE       :					Optional[Any]     							=   (
					    (
					        AlbertModel,
					        AlbertForPreTraining,
					        AlbertForMaskedLM,
					        AlbertForMultipleChoice,
					        AlbertForSequenceClassification,
					        AlbertForTokenClassification,
					        AlbertForQuestionAnswering,
					    )
					    if is_torch_available()
					    else ()
					)
					_SCREAMING_SNAKE_CASE       :					str     							=   (
					    {
					        '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       :					Dict     							=   True





					def 							lowerCAmelCase      (				self   :							Tuple							,						snake_case_   :							Any							,						snake_case_   :							Union[str, Any]							,						snake_case_   :							List[Any]=False    ):
												__snake_case     			=       super()._prepare_for_class(snake_case_							,						snake_case_							,						return_labels=snake_case_    )

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





					def 							lowerCAmelCase      (				self   :							List[Any]    ):
												__snake_case     			=       AlbertModelTester(self    )
												__snake_case     			=       ConfigTester(self							,						config_class=snake_case_							,						hidden_size=37    )





					def 							lowerCAmelCase      (				self   :							str    ):
												self.config_tester.run_common_tests()





					def 							lowerCAmelCase      (				self   :							Any    ):
												__snake_case     			=       self.model_tester.prepare_config_and_inputs()
												self.model_tester.create_and_check_model(*snake_case_    )





					def 							lowerCAmelCase      (				self   :							int    ):
												__snake_case     			=       self.model_tester.prepare_config_and_inputs()
												self.model_tester.create_and_check_for_pretraining(*snake_case_    )





					def 							lowerCAmelCase      (				self   :							Union[str, Any]    ):
												__snake_case     			=       self.model_tester.prepare_config_and_inputs()
												self.model_tester.create_and_check_for_masked_lm(*snake_case_    )





					def 							lowerCAmelCase      (				self   :							List[Any]    ):
												__snake_case     			=       self.model_tester.prepare_config_and_inputs()
												self.model_tester.create_and_check_for_multiple_choice(*snake_case_    )





					def 							lowerCAmelCase      (				self   :							Optional[int]    ):
												__snake_case     			=       self.model_tester.prepare_config_and_inputs()
												self.model_tester.create_and_check_for_question_answering(*snake_case_    )





					def 							lowerCAmelCase      (				self   :							Optional[int]    ):
												__snake_case     			=       self.model_tester.prepare_config_and_inputs()
												self.model_tester.create_and_check_for_sequence_classification(*snake_case_    )





					def 							lowerCAmelCase      (				self   :							Union[str, Any]    ):
												__snake_case     			=       self.model_tester.prepare_config_and_inputs()
												for type in ["absolute", "relative_key", "relative_key_query"]:
																			__snake_case     			=       type
																			self.model_tester.create_and_check_model(*snake_case_    )





					@slow
					def 							lowerCAmelCase      (				self   :							str    ):
												for model_name in ALBERT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
																			__snake_case     			=       AlbertModel.from_pretrained(snake_case_    )
																			self.assertIsNotNone(snake_case_    )







@require_torch
class 							__magic_name__     (		unittest.TestCase   ):





					@slow
					def 							lowerCAmelCase      (				self   :							Tuple    ):
												__snake_case     			=       AlbertModel.from_pretrained("albert-base-v2"    )
												__snake_case     			=       torch.tensor([[0, 345, 232, 328, 740, 140, 1695, 69, 6078, 1588, 2]]    )
												__snake_case     			=       torch.tensor([[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]    )
												with torch.no_grad():
																			__snake_case     			=       model(snake_case_							,						attention_mask=snake_case_    )[0]
												__snake_case     			=       torch.Size((1, 11, 768)    )
												self.assertEqual(output.shape							,						snake_case_    )
												__snake_case     			=       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]							,						snake_case_							,						atol=1e-4    )    )


"""simple docstring"""







from __future__ import annotations

_SCREAMING_SNAKE_CASE	       =      {
    """A""": ["""B""", """C""", """E"""],
    """B""": ["""A""", """D""", """E"""],
    """C""": ["""A""", """F""", """G"""],
    """D""": ["""B"""],
    """E""": ["""A""", """B""", """D"""],
    """F""": ["""C"""],
    """G""": ["""C"""],
}







class 							__magic_name__     :





					def __init__(				self   :							Any							,						snake_case_   :							dict[str, list[str]]							,						snake_case_   :							str    ):
												__snake_case     			=       graph
												# mapping node to its parent in resulting breadth first tree
												__snake_case     			=       {}
												__snake_case     			=       source_vertex





					def 							lowerCAmelCase      (				self   :							Union[str, Any]    ):
												__snake_case     			=       {self.source_vertex}
												__snake_case     			=       None
												__snake_case     			=       [self.source_vertex]  # first in first out queue

												while queue:
																			__snake_case     			=       queue.pop(0    )
																			for adjacent_vertex in self.graph[vertex]:
																										if adjacent_vertex not in visited:
																																	visited.add(snake_case_    )
																																	__snake_case     			=       vertex
																																	queue.append(snake_case_    )





					def 							lowerCAmelCase      (				self   :							Dict							,						snake_case_   :							str    ):
												if target_vertex == self.source_vertex:
																			return self.source_vertex

												__snake_case     			=       self.parent.get(snake_case_    )
												if target_vertex_parent is None:
																			__snake_case     			=       (
																			    F'''No path from vertex: {self.source_vertex} to vertex: {target_vertex}'''
																			)
																			raise ValueError(snake_case_    )

												return self.shortest_path(snake_case_    ) + F'''->{target_vertex}'''


if __name__ == "__main__":
		_SCREAMING_SNAKE_CASE	       =      Graph(graph, """G""")
		g.breath_first_search()
		print(g.shortest_path("""D"""))
		print(g.shortest_path("""G"""))
		print(g.shortest_path("""Foo"""))
