'''simple docstring'''

import unittest

from transformers import ElectraConfig, 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, floats_tensor, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
       import torch

       from transformers import (
           MODEL_FOR_PRETRAINING_MAPPING,
           ElectraForCausalLM,
           ElectraForMaskedLM,
           ElectraForMultipleChoice,
           ElectraForPreTraining,
           ElectraForQuestionAnswering,
           ElectraForSequenceClassification,
           ElectraForTokenClassification,
           ElectraModel,
       )
       from transformers.models.electra.modeling_electra import ELECTRA_PRETRAINED_MODEL_ARCHIVE_LIST





class 				lowercase    :


   def __init__( self					:						List[str] ,		__lowerCAmelCase					:						List[Any] ,		__lowerCAmelCase					:						int=13 ,		__lowerCAmelCase					:						List[Any]=7 ,		__lowerCAmelCase					:						List[str]=True ,		__lowerCAmelCase					:						Dict=True ,		__lowerCAmelCase					:						Optional[Any]=True ,		__lowerCAmelCase					:						int=True ,		__lowerCAmelCase					:						List[str]=99 ,		__lowerCAmelCase					:						Optional[int]=32 ,		__lowerCAmelCase					:						str=5 ,		__lowerCAmelCase					:						List[Any]=4 ,		__lowerCAmelCase					:						str=37 ,		__lowerCAmelCase					:						Dict="gelu" ,		__lowerCAmelCase					:						Dict=0.1 ,		__lowerCAmelCase					:						List[Any]=0.1 ,		__lowerCAmelCase					:						Tuple=512 ,		__lowerCAmelCase					:						Dict=16 ,		__lowerCAmelCase					:						List[Any]=2 ,		__lowerCAmelCase					:						str=0.02 ,		__lowerCAmelCase					:						List[Any]=3 ,		__lowerCAmelCase					:						Optional[int]=4 ,		__lowerCAmelCase					:						int=None ,		)   ->       Union[str, Any]:
         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_     			=   hidden_size
         lowercase_     			=   num_hidden_layers
         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 __UpperCAmelCase							( self					:						int)   ->       Optional[int]:
         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_     			=   ids_tensor([self.batch_size, self.seq_length] ,		1)

         lowercase_     			=   self.get_config()

         return (
             config,
             input_ids,
             token_type_ids,
             input_mask,
             sequence_labels,
             token_labels,
             choice_labels,
             fake_token_labels,
         )


   def __UpperCAmelCase							( self					:						List[str])   ->       int:
         return ElectraConfig(
             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 ,		is_decoder=__A ,		initializer_range=self.initializer_range ,		)


   def __UpperCAmelCase							( self					:						Optional[int])   ->       Optional[Any]:
         (
             lowercase_       
         )     			=   self.prepare_config_and_inputs()

         lowercase_     			=   True
         lowercase_     			=   floats_tensor([self.batch_size, self.seq_length, self.hidden_size])
         lowercase_     			=   ids_tensor([self.batch_size, self.seq_length] ,		vocab_size=2)

         return (
             config,
             input_ids,
             token_type_ids,
             input_mask,
             sequence_labels,
             token_labels,
             choice_labels,
             encoder_hidden_states,
             encoder_attention_mask,
         )


   def __UpperCAmelCase							( self					:						str ,		__lowerCAmelCase					:						int ,		__lowerCAmelCase					:						List[Any] ,		__lowerCAmelCase					:						Optional[int] ,		__lowerCAmelCase					:						List[Any] ,		__lowerCAmelCase					:						Tuple ,		__lowerCAmelCase					:						Dict ,		__lowerCAmelCase					:						List[Any] ,		__lowerCAmelCase					:						Tuple ,		)   ->       List[Any]:
         lowercase_     			=   ElectraModel(config=__A)
         model.to(__A)
         model.eval()
         lowercase_     			=   model(__A ,		attention_mask=__A ,		token_type_ids=__A)
         lowercase_     			=   model(__A ,		token_type_ids=__A)
         lowercase_     			=   model(__A)
         self.parent.assertEqual(result.last_hidden_state.shape ,		(self.batch_size, self.seq_length, self.hidden_size))


   def __UpperCAmelCase							( self					:						Optional[Any] ,		__lowerCAmelCase					:						Dict ,		__lowerCAmelCase					:						List[Any] ,		__lowerCAmelCase					:						Tuple ,		__lowerCAmelCase					:						str ,		__lowerCAmelCase					:						Optional[int] ,		__lowerCAmelCase					:						Dict ,		__lowerCAmelCase					:						Optional[int] ,		__lowerCAmelCase					:						int ,		__lowerCAmelCase					:						List[Any] ,		)   ->       List[str]:
         lowercase_     			=   True
         lowercase_     			=   ElectraModel(__A)
         model.to(__A)
         model.eval()
         lowercase_     			=   model(
             __A ,		attention_mask=__A ,		token_type_ids=__A ,		encoder_hidden_states=__A ,		encoder_attention_mask=__A ,		)
         lowercase_     			=   model(
             __A ,		attention_mask=__A ,		token_type_ids=__A ,		encoder_hidden_states=__A ,		)
         lowercase_     			=   model(__A ,		attention_mask=__A ,		token_type_ids=__A)
         self.parent.assertEqual(result.last_hidden_state.shape ,		(self.batch_size, self.seq_length, self.hidden_size))


   def __UpperCAmelCase							( self					:						Tuple ,		__lowerCAmelCase					:						Tuple ,		__lowerCAmelCase					:						Optional[Any] ,		__lowerCAmelCase					:						List[Any] ,		__lowerCAmelCase					:						List[str] ,		__lowerCAmelCase					:						Tuple ,		__lowerCAmelCase					:						Optional[Any] ,		__lowerCAmelCase					:						List[Any] ,		__lowerCAmelCase					:						Any ,		)   ->       str:
         lowercase_     			=   ElectraForMaskedLM(config=__A)
         model.to(__A)
         model.eval()
         lowercase_     			=   model(__A ,		attention_mask=__A ,		token_type_ids=__A ,		labels=__A)
         self.parent.assertEqual(result.logits.shape ,		(self.batch_size, self.seq_length, self.vocab_size))


   def __UpperCAmelCase							( self					:						Tuple ,		__lowerCAmelCase					:						Union[str, Any] ,		__lowerCAmelCase					:						List[Any] ,		__lowerCAmelCase					:						Union[str, Any] ,		__lowerCAmelCase					:						Optional[Any] ,		__lowerCAmelCase					:						Optional[Any] ,		__lowerCAmelCase					:						List[str] ,		__lowerCAmelCase					:						Tuple ,		__lowerCAmelCase					:						Optional[Any] ,		__lowerCAmelCase					:						str ,		)   ->       Optional[Any]:
         lowercase_     			=   ElectraForCausalLM(config=__A)
         model.to(__A)
         model.eval()
         lowercase_     			=   model(__A ,		attention_mask=__A ,		token_type_ids=__A ,		labels=__A)
         self.parent.assertEqual(result.logits.shape ,		(self.batch_size, self.seq_length, self.vocab_size))


   def __UpperCAmelCase							( self					:						Optional[Any] ,		__lowerCAmelCase					:						Any ,		__lowerCAmelCase					:						Dict ,		__lowerCAmelCase					:						Union[str, Any] ,		__lowerCAmelCase					:						Optional[int] ,		__lowerCAmelCase					:						Optional[int] ,		__lowerCAmelCase					:						Optional[Any] ,		__lowerCAmelCase					:						int ,		__lowerCAmelCase					:						Any ,		)   ->       List[Any]:
         lowercase_     			=   self.num_labels
         lowercase_     			=   ElectraForTokenClassification(config=__A)
         model.to(__A)
         model.eval()
         lowercase_     			=   model(__A ,		attention_mask=__A ,		token_type_ids=__A ,		labels=__A)
         self.parent.assertEqual(result.logits.shape ,		(self.batch_size, self.seq_length, self.num_labels))


   def __UpperCAmelCase							( self					:						Tuple ,		__lowerCAmelCase					:						List[str] ,		__lowerCAmelCase					:						Optional[Any] ,		__lowerCAmelCase					:						Dict ,		__lowerCAmelCase					:						Optional[int] ,		__lowerCAmelCase					:						List[Any] ,		__lowerCAmelCase					:						str ,		__lowerCAmelCase					:						List[Any] ,		__lowerCAmelCase					:						int ,		)   ->       List[Any]:
         lowercase_     			=   self.num_labels
         lowercase_     			=   ElectraForPreTraining(config=__A)
         model.to(__A)
         model.eval()
         lowercase_     			=   model(__A ,		attention_mask=__A ,		token_type_ids=__A ,		labels=__A)
         self.parent.assertEqual(result.logits.shape ,		(self.batch_size, self.seq_length))


   def __UpperCAmelCase							( self					:						Dict ,		__lowerCAmelCase					:						Optional[Any] ,		__lowerCAmelCase					:						Union[str, Any] ,		__lowerCAmelCase					:						Union[str, Any] ,		__lowerCAmelCase					:						Tuple ,		__lowerCAmelCase					:						int ,		__lowerCAmelCase					:						List[Any] ,		__lowerCAmelCase					:						Dict ,		__lowerCAmelCase					:						int ,		)   ->       Optional[Any]:
         lowercase_     			=   self.num_labels
         lowercase_     			=   ElectraForSequenceClassification(__A)
         model.to(__A)
         model.eval()
         lowercase_     			=   model(__A ,		attention_mask=__A ,		token_type_ids=__A ,		labels=__A)
         self.parent.assertEqual(result.logits.shape ,		(self.batch_size, self.num_labels))


   def __UpperCAmelCase							( self					:						str ,		__lowerCAmelCase					:						Union[str, Any] ,		__lowerCAmelCase					:						str ,		__lowerCAmelCase					:						str ,		__lowerCAmelCase					:						List[Any] ,		__lowerCAmelCase					:						Optional[int] ,		__lowerCAmelCase					:						Dict ,		__lowerCAmelCase					:						Union[str, Any] ,		__lowerCAmelCase					:						int ,		)   ->       List[Any]:
         lowercase_     			=   ElectraForQuestionAnswering(config=__A)
         model.to(__A)
         model.eval()
         lowercase_     			=   model(
             __A ,		attention_mask=__A ,		token_type_ids=__A ,		start_positions=__A ,		end_positions=__A ,		)
         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 __UpperCAmelCase							( self					:						Optional[Any] ,		__lowerCAmelCase					:						List[str] ,		__lowerCAmelCase					:						Optional[int] ,		__lowerCAmelCase					:						List[Any] ,		__lowerCAmelCase					:						Dict ,		__lowerCAmelCase					:						Any ,		__lowerCAmelCase					:						str ,		__lowerCAmelCase					:						Tuple ,		__lowerCAmelCase					:						Any ,		)   ->       int:
         lowercase_     			=   self.num_choices
         lowercase_     			=   ElectraForMultipleChoice(config=__A)
         model.to(__A)
         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(
             __A ,		attention_mask=__A ,		token_type_ids=__A ,		labels=__A ,		)
         self.parent.assertEqual(result.logits.shape ,		(self.batch_size, self.num_choices))


   def __UpperCAmelCase							( self					:						Dict)   ->       int:
         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 				lowercase    (    a__			,					a__			,					unittest.TestCase			):
   lowerCamelCase_            =(
       (
           ElectraModel,
           ElectraForPreTraining,
           ElectraForMaskedLM,
           ElectraForCausalLM,
           ElectraForMultipleChoice,
           ElectraForTokenClassification,
           ElectraForSequenceClassification,
           ElectraForQuestionAnswering,
       )
       if is_torch_available()
       else ()
   )
   lowerCamelCase_            =(
       {
           'feature-extraction': ElectraModel,
           'fill-mask': ElectraForMaskedLM,
           'question-answering': ElectraForQuestionAnswering,
           'text-classification': ElectraForSequenceClassification,
           'text-generation': ElectraForCausalLM,
           'token-classification': ElectraForTokenClassification,
           'zero-shot': ElectraForSequenceClassification,
       }
       if is_torch_available()
       else {}
   )
   lowerCamelCase_            =True


   def __UpperCAmelCase							( self					:						Union[str, Any] ,		__lowerCAmelCase					:						str ,		__lowerCAmelCase					:						Optional[Any] ,		__lowerCAmelCase					:						Optional[int]=False)   ->       str:
         lowercase_     			=   super()._prepare_for_class(__A ,		__A ,		return_labels=__A)

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


   def __UpperCAmelCase							( self					:						List[Any])   ->       str:
         lowercase_     			=   ElectraModelTester(self)
         lowercase_     			=   ConfigTester(self ,		config_class=__A ,		hidden_size=37)


   def __UpperCAmelCase							( self					:						List[Any])   ->       Optional[Any]:
         self.config_tester.run_common_tests()


   def __UpperCAmelCase							( self					:						List[str])   ->       int:
         lowercase_     			=   self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_electra_model(*__A)


   def __UpperCAmelCase							( self					:						Union[str, Any])   ->       Optional[int]:
         lowercase_     			=   self.model_tester.prepare_config_and_inputs_for_decoder()
         self.model_tester.create_and_check_electra_model_as_decoder(*__A)


   def __UpperCAmelCase							( self					:						Optional[int])   ->       Any:
         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_electra_model(*__A)


   def __UpperCAmelCase							( self					:						Union[str, Any])   ->       Union[str, Any]:
         lowercase_     			=   self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_electra_for_masked_lm(*__A)


   def __UpperCAmelCase							( self					:						Dict)   ->       Dict:
         lowercase_     			=   self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_electra_for_token_classification(*__A)


   def __UpperCAmelCase							( self					:						Any)   ->       List[Any]:
         lowercase_     			=   self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_electra_for_pretraining(*__A)


   def __UpperCAmelCase							( self					:						Any)   ->       Union[str, Any]:
         lowercase_     			=   self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_electra_for_sequence_classification(*__A)


   def __UpperCAmelCase							( self					:						Tuple)   ->       Optional[Any]:
         lowercase_     			=   self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_electra_for_question_answering(*__A)


   def __UpperCAmelCase							( self					:						Tuple)   ->       List[str]:
         lowercase_     			=   self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_electra_for_multiple_choice(*__A)


   @slow
   def __UpperCAmelCase							( self					:						Tuple)   ->       Union[str, Any]:







         for model_name in ELECTRA_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
               lowercase_     			=   ElectraModel.from_pretrained(__A)
               self.assertIsNotNone(__A)


   def __UpperCAmelCase							( self					:						Tuple)   ->       Optional[Any]:
         lowercase_     			=   self.model_tester.prepare_config_and_inputs_for_decoder()
         self.model_tester.create_and_check_electra_for_causal_lm(*__A)





@require_torch
class 				lowercase    (    unittest.TestCase			):


   @slow
   def __UpperCAmelCase							( self					:						Dict)   ->       Optional[Any]:
         lowercase_     			=   ElectraModel.from_pretrained("google/electra-small-discriminator")
         lowercase_     			=   torch.tensor([[0, 345, 232, 328, 740, 140, 1695, 69, 6078, 1588, 2]])
         lowercase_     			=   torch.tensor([[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]])
         lowercase_     			=   model(__A ,		attention_mask=__A)[0]
         lowercase_     			=   torch.Size((1, 11, 256))
         self.assertEqual(output.shape ,		__A)
         lowercase_     			=   torch.tensor(
             [[[0.4471, 0.6821, -0.3265], [0.4627, 0.5255, -0.3668], [0.4532, 0.3313, -0.4344]]])

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










'''simple docstring'''




import math
import sys





class _snake_case :
							"""simple docstring"""





							def __init__( self						)  ->int:



											"""simple docstring"""







											__lowerCamelCase		:   int           =       0
											__lowerCamelCase		:   str           =       []
											__lowerCamelCase		:   int           =       {}  # To store the pos of node in array







							def 		__SCREAMING_SNAKE_CASE( self						)  ->Union[str, Any]:



											"""simple docstring"""







											return self.cur_size == 0







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A						)  ->Union[str, Any]:



											"""simple docstring"""







											__lowerCamelCase		:   Any           =       self.left(__A						)
											__lowerCamelCase		:   Any           =       self.right(__A						)
											if lc < self.cur_size and self.array(__A						)[0] < self.array(__A						)[0]:
															__lowerCamelCase		:   Dict           =       lc
											else:
															__lowerCamelCase		:   List[Any]           =       idx
											if rc < self.cur_size and self.array(__A						)[0] < self.array(__A						)[0]:
															__lowerCamelCase		:   List[str]           =       rc
											if smallest != idx:
															self.swap(__A      ,					__A						)
															self.min_heapify(__A						)







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A						)  ->str:



											"""simple docstring"""







											__lowerCamelCase		:   Optional[Any]           =       self.cur_size
											self.cur_size += 1
											self.array.append((sys.maxsize, tup[1])						)
											self.decrease_key((sys.maxsize, tup[1])      ,					tup[0]						)







							def 		__SCREAMING_SNAKE_CASE( self						)  ->int:



											"""simple docstring"""







											__lowerCamelCase		:   Tuple           =       self.array[0][1]
											__lowerCamelCase		:   str           =       self.array[self.cur_size - 1]
											self.cur_size -= 1
											self.min_heapify(1						)
											del self.pos[min_node]
											return min_node







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A						)  ->int:



											"""simple docstring"""







											return 2 * i + 1







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A						)  ->Optional[Any]:



											"""simple docstring"""







											return 2 * i + 2







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A						)  ->Tuple:



											"""simple docstring"""







											return math.floor(i / 2						)







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A      ,					__A						)  ->List[Any]:



											"""simple docstring"""







											__lowerCamelCase		:   Union[str, Any]           =       j
											__lowerCamelCase		:   str           =       i
											__lowerCamelCase		:   Dict           =       self.array[i]
											__lowerCamelCase		:   Union[str, Any]           =       self.array[j]
											__lowerCamelCase		:   str           =       temp







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A      ,					__A						)  ->Optional[Any]:



											"""simple docstring"""







											__lowerCamelCase		:   str           =       self.pos[tup[1]]
											# assuming the new_d is atmost old_d
											__lowerCamelCase		:   Union[str, Any]           =       (new_d, tup[1])
											while idx > 0 and self.array[self.par(__A						)][0] > self.array[idx][0]:
															self.swap(__A      ,					self.par(__A						)						)
															__lowerCamelCase		:   List[Any]           =       self.par(__A						)





class _snake_case :
							"""simple docstring"""





							def __init__( self      ,					__A						)  ->Any:



											"""simple docstring"""







											__lowerCamelCase		:   Dict           =       {}  # To store graph: u -> (v,w)
											__lowerCamelCase		:   Optional[Any]           =       num  # Number of nodes in graph
											# To store the distance from source vertex
											__lowerCamelCase		:   Dict           =       [0] * self.num_nodes
											__lowerCamelCase		:   List[str]           =       [-1] * self.num_nodes  # To store the path







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A      ,					__A      ,					__A						)  ->Optional[Any]:



											"""simple docstring"""







											if u in self.adjList:
															self.adjList[u].append((v, w)						)
											else:
															__lowerCamelCase		:   Dict           =       [(v, w)]

											# Assuming undirected graph
											if v in self.adjList:
															self.adjList[v].append((u, w)						)
											else:
															__lowerCamelCase		:   List[Any]           =       [(u, w)]







							def 		__SCREAMING_SNAKE_CASE( self						)  ->Tuple:



											"""simple docstring"""







											for u in self.adjList:
															print(__A      ,					"->"      ,					" -> ".join(str(f'{v}({w})'						) for v, w in self.adjList[u]						)						)







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A						)  ->int:



											"""simple docstring"""







											__lowerCamelCase		:   List[str]           =       [-1] * self.num_nodes
											# src is the source node
											__lowerCamelCase		:   str           =       0
											__lowerCamelCase		:   int           =       PriorityQueue()
											q.insert((0, src)						)  # (dist from src, node)
											for u in self.adjList:
															if u != src:
																			__lowerCamelCase		:   List[Any]           =       sys.maxsize  # Infinity
																			__lowerCamelCase		:   Dict           =       -1

											while not q.is_empty():
															__lowerCamelCase		:   int           =       q.extract_min()  # Returns node with the min dist from source
															# Update the distance of all the neighbours of u and
															# if their prev dist was INFINITY then push them in Q
															for v, w in self.adjList[u]:
																			__lowerCamelCase		:   str           =       self.dist[u] + w
																			if self.dist[v] > new_dist:
																							if self.dist[v] == sys.maxsize:
																											q.insert((new_dist, v)						)
																							else:
																											q.decrease_key((self.dist[v], v)      ,					__A						)
																							__lowerCamelCase		:   str           =       new_dist
																							__lowerCamelCase		:   Tuple           =       u

        # Show the shortest distances from src
											self.show_distances(__A						)







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A						)  ->int:



											"""simple docstring"""







											print(f'Distance from node: {src}'						)
											for u in range(self.num_nodes						):
															print(f'Node {u} has distance: {self.dist[u]}'						)







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A      ,					__A						)  ->Optional[int]:



											"""simple docstring"""







											__lowerCamelCase		:   List[Any]           =       []
											__lowerCamelCase		:   Tuple           =       0
											__lowerCamelCase		:   List[str]           =       dest
											# Backtracking from dest to src
											while self.par[temp] != -1:
															path.append(__A						)
															if temp != src:
																			for v, w in self.adjList[temp]:
																							if v == self.par[temp]:
																											cost += w
																											break
															__lowerCamelCase		:   int           =       self.par[temp]
											path.append(__A						)
											path.reverse()

											print(f'----Path to reach {dest} from {src}----'						)
											for u in path:
															print(f'{u}'      ,					end=" "						)
															if u != dest:
																			print("-> "      ,					end=""						)

											print("\nTotal cost of path: "      ,					__A						)


if __name__ == "__main__":
				__lowercase	:   Optional[Any]   		=					Graph(9)
				graph.add_edge(0, 1, 4)
				graph.add_edge(0, 7, 8)
				graph.add_edge(1, 2, 8)
				graph.add_edge(1, 7, 11)
				graph.add_edge(2, 3, 7)
				graph.add_edge(2, 8, 2)
				graph.add_edge(2, 5, 4)
				graph.add_edge(3, 4, 9)
				graph.add_edge(3, 5, 14)
				graph.add_edge(4, 5, 10)
				graph.add_edge(5, 6, 2)
				graph.add_edge(6, 7, 1)
				graph.add_edge(6, 8, 6)
				graph.add_edge(7, 8, 7)
				graph.show_graph()
				graph.dijkstra(0)
				graph.show_path(0, 4)

# OUTPUT
# 0 -> 1(4) -> 7(8)
# 1 -> 0(4) -> 2(8) -> 7(11)
# 7 -> 0(8) -> 1(11) -> 6(1) -> 8(7)
# 2 -> 1(8) -> 3(7) -> 8(2) -> 5(4)
# 3 -> 2(7) -> 4(9) -> 5(14)
# 8 -> 2(2) -> 6(6) -> 7(7)
# 5 -> 2(4) -> 3(14) -> 4(10) -> 6(2)
# 4 -> 3(9) -> 5(10)
# 6 -> 5(2) -> 7(1) -> 8(6)
# Distance from node: 0
# Node 0 has distance: 0
# Node 1 has distance: 4
# Node 2 has distance: 12
# Node 3 has distance: 19
# Node 4 has distance: 21
# Node 5 has distance: 11
# Node 6 has distance: 9
# Node 7 has distance: 8
# Node 8 has distance: 14
# ----Path to reach 4 from 0----
# 0 -> 7 -> 6 -> 5 -> 4
# Total cost of path:  21





