code: 
  
  
  
  
  
  '''simple docstring'''
  
  
  
  
  
  
  
  import collections
  import inspect
  import unittest
  
  from transformers import NatConfig
  from transformers.testing_utils import require_natten, require_torch, require_vision, slow, torch_device
  from transformers.utils import cached_property, is_torch_available, is_vision_available
  
  from ...test_backbone_common import BackboneTesterMixin
  from ...test_configuration_common import ConfigTester
  from ...test_modeling_common import ModelTesterMixin, _config_zero_init, floats_tensor, ids_tensor
  from ...test_pipeline_mixin import PipelineTesterMixin
  
  
  if is_torch_available():
   import torch
   from torch import nn
  
   from transformers import NatBackbone, NatForImageClassification, NatModel
   from transformers.models.nat.modeling_nat import NAT_PRETRAINED_MODEL_ARCHIVE_LIST
  
  if is_vision_available():
   from PIL import Image
  
   from transformers import AutoImageProcessor
  
  
  
  
  
  class 					_UpperCAmelCase							:
    def __init__(						self,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE=13,__SCREAMING_SNAKE_CASE=64,__SCREAMING_SNAKE_CASE=4,__SCREAMING_SNAKE_CASE=3,__SCREAMING_SNAKE_CASE=16,__SCREAMING_SNAKE_CASE=[1, 2, 1],__SCREAMING_SNAKE_CASE=[2, 4, 8],__SCREAMING_SNAKE_CASE=3,__SCREAMING_SNAKE_CASE=2.0,__SCREAMING_SNAKE_CASE=True,__SCREAMING_SNAKE_CASE=0.0,__SCREAMING_SNAKE_CASE=0.0,__SCREAMING_SNAKE_CASE=0.1,__SCREAMING_SNAKE_CASE="gelu",__SCREAMING_SNAKE_CASE=True,__SCREAMING_SNAKE_CASE=0.02,__SCREAMING_SNAKE_CASE=1e-5,__SCREAMING_SNAKE_CASE=True,__SCREAMING_SNAKE_CASE=None,__SCREAMING_SNAKE_CASE=True,__SCREAMING_SNAKE_CASE=10,__SCREAMING_SNAKE_CASE=["stage1", "stage2"],__SCREAMING_SNAKE_CASE=[1, 2],):
  
  
  
       '''simple docstring'''
  
       __lowerCAmelCase      		=       parent
       __lowerCAmelCase      		=       batch_size
       __lowerCAmelCase      		=       image_size
       __lowerCAmelCase      		=       patch_size
       __lowerCAmelCase      		=       num_channels
       __lowerCAmelCase      		=       embed_dim
       __lowerCAmelCase      		=       depths
       __lowerCAmelCase      		=       num_heads
       __lowerCAmelCase      		=       kernel_size
       __lowerCAmelCase      		=       mlp_ratio
       __lowerCAmelCase      		=       qkv_bias
       __lowerCAmelCase      		=       hidden_dropout_prob
       __lowerCAmelCase      		=       attention_probs_dropout_prob
       __lowerCAmelCase      		=       drop_path_rate
       __lowerCAmelCase      		=       hidden_act
       __lowerCAmelCase      		=       patch_norm
       __lowerCAmelCase      		=       layer_norm_eps
       __lowerCAmelCase      		=       initializer_range
       __lowerCAmelCase      		=       is_training
       __lowerCAmelCase      		=       scope
       __lowerCAmelCase      		=       use_labels
       __lowerCAmelCase      		=       num_labels
       __lowerCAmelCase      		=       out_features
       __lowerCAmelCase      		=       out_indices
    def 						lowerCamelCase__    (						self    ):
  
  
  
       '''simple docstring'''
  
       __lowerCAmelCase      		=       floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]    )
  
       __lowerCAmelCase      		=       None
       if self.use_labels:
          __lowerCAmelCase      		=       ids_tensor([self.batch_size],self.num_labels    )
  
       __lowerCAmelCase      		=       self.get_config()
  
       return config, pixel_values, labels
    def 						lowerCamelCase__    (						self    ):
  
  
  
       '''simple docstring'''
  
       return NatConfig(
           num_labels=self.num_labels,image_size=self.image_size,patch_size=self.patch_size,num_channels=self.num_channels,embed_dim=self.embed_dim,depths=self.depths,num_heads=self.num_heads,kernel_size=self.kernel_size,mlp_ratio=self.mlp_ratio,qkv_bias=self.qkv_bias,hidden_dropout_prob=self.hidden_dropout_prob,attention_probs_dropout_prob=self.attention_probs_dropout_prob,drop_path_rate=self.drop_path_rate,hidden_act=self.hidden_act,patch_norm=self.patch_norm,layer_norm_eps=self.layer_norm_eps,initializer_range=self.initializer_range,out_features=self.out_features,out_indices=self.out_indices,)
    def 						lowerCamelCase__    (						self,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE    ):
  
  
  
       '''simple docstring'''
  
       __lowerCAmelCase      		=       NatModel(config=__SCREAMING_SNAKE_CASE    )
       model.to(__SCREAMING_SNAKE_CASE    )
       model.eval()
       __lowerCAmelCase      		=       model(__SCREAMING_SNAKE_CASE    )
  
       __lowerCAmelCase      		=       __lowerCAmelCase      		=       (config.image_size // config.patch_size) // (2 ** (len(config.depths    ) - 1))
       __lowerCAmelCase      		=       int(config.embed_dim * 2 ** (len(config.depths    ) - 1)    )
  
       self.parent.assertEqual(
           result.last_hidden_state.shape,(self.batch_size, expected_height, expected_width, expected_dim)    )
    def 						lowerCamelCase__    (						self,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE    ):
  
  
  
       '''simple docstring'''
  
       __lowerCAmelCase      		=       NatForImageClassification(__SCREAMING_SNAKE_CASE    )
       model.to(__SCREAMING_SNAKE_CASE    )
       model.eval()
       __lowerCAmelCase      		=       model(__SCREAMING_SNAKE_CASE,labels=__SCREAMING_SNAKE_CASE    )
       self.parent.assertEqual(result.logits.shape,(self.batch_size, self.num_labels)    )
  
       # test greyscale images
       __lowerCAmelCase      		=       1
       __lowerCAmelCase      		=       NatForImageClassification(__SCREAMING_SNAKE_CASE    )
       model.to(__SCREAMING_SNAKE_CASE    )
       model.eval()
  
       __lowerCAmelCase      		=       floats_tensor([self.batch_size, 1, self.image_size, self.image_size]    )
       __lowerCAmelCase      		=       model(__SCREAMING_SNAKE_CASE    )
       self.parent.assertEqual(result.logits.shape,(self.batch_size, self.num_labels)    )
    def 						lowerCamelCase__    (						self,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE    ):
  
  
  
       '''simple docstring'''
  
       __lowerCAmelCase      		=       NatBackbone(config=__SCREAMING_SNAKE_CASE    )
       model.to(__SCREAMING_SNAKE_CASE    )
       model.eval()
       __lowerCAmelCase      		=       model(__SCREAMING_SNAKE_CASE    )
  
       # verify hidden states
       self.parent.assertEqual(len(result.feature_maps    ),len(config.out_features    )    )
       self.parent.assertListEqual(list(result.feature_maps[0].shape    ),[self.batch_size, model.channels[0], 16, 16]    )
  
       # verify channels
       self.parent.assertEqual(len(model.channels    ),len(config.out_features    )    )
  
       # verify backbone works with out_features=None
       __lowerCAmelCase      		=       None
       __lowerCAmelCase      		=       NatBackbone(config=__SCREAMING_SNAKE_CASE    )
       model.to(__SCREAMING_SNAKE_CASE    )
       model.eval()
       __lowerCAmelCase      		=       model(__SCREAMING_SNAKE_CASE    )
  
       # verify feature maps
       self.parent.assertEqual(len(result.feature_maps    ),1    )
       self.parent.assertListEqual(list(result.feature_maps[0].shape    ),[self.batch_size, model.channels[-1], 4, 4]    )
  
       # verify channels
       self.parent.assertEqual(len(model.channels    ),1    )
  
  
  
  
  
  
  
    def 						lowerCamelCase__    (						self    ):
  
  
  
       '''simple docstring'''
  
       __lowerCAmelCase      		=       self.prepare_config_and_inputs()
       __lowerCAmelCase		, __lowerCAmelCase		, __lowerCAmelCase      		=       config_and_inputs
       __lowerCAmelCase      		=       {"""pixel_values""": pixel_values}
       return config, inputs_dict
  
  
  
  
  
  @require_natten
  @require_torch
  class 					_UpperCAmelCase							(		snake_case_			,      snake_case_			,      unittest.TestCase     ):
    a     :     Any     						=(
        (
            NatModel,
            NatForImageClassification,
            NatBackbone,
        )
        if is_torch_available()
        else ()
    )
    a     :     Optional[int]     						=(
        {"""feature-extraction""": NatModel, """image-classification""": NatForImageClassification}
        if is_torch_available()
        else {}
    )
    a     :     str     						=False
  
    a     :     List[str]     						=False
    a     :     int     						=False
    a     :     str     						=False
    a     :     Tuple     						=False
    def 						lowerCamelCase__    (						self    ):
  
  
  
       '''simple docstring'''
  
       __lowerCAmelCase      		=       NatModelTester(self    )
       __lowerCAmelCase      		=       ConfigTester(self,config_class=__SCREAMING_SNAKE_CASE,embed_dim=37    )
    def 						lowerCamelCase__    (						self    ):
  
  
  
       '''simple docstring'''
  
       self.create_and_test_config_common_properties()
       self.config_tester.create_and_test_config_to_json_string()
       self.config_tester.create_and_test_config_to_json_file()
       self.config_tester.create_and_test_config_from_and_save_pretrained()
       self.config_tester.create_and_test_config_with_num_labels()
       self.config_tester.check_config_can_be_init_without_params()
       self.config_tester.check_config_arguments_init()
    def 						lowerCamelCase__    (						self    ):
  
  
  
       '''simple docstring'''
  
       return
    def 						lowerCamelCase__    (						self    ):
  
  
  
       '''simple docstring'''
  
       __lowerCAmelCase      		=       self.model_tester.prepare_config_and_inputs()
       self.model_tester.create_and_check_model(*__SCREAMING_SNAKE_CASE    )
    def 						lowerCamelCase__    (						self    ):
  
  
  
       '''simple docstring'''
  
       __lowerCAmelCase      		=       self.model_tester.prepare_config_and_inputs()
       self.model_tester.create_and_check_for_image_classification(*__SCREAMING_SNAKE_CASE    )
    def 						lowerCamelCase__    (						self    ):
  
  
  
       '''simple docstring'''
  
       __lowerCAmelCase      		=       self.model_tester.prepare_config_and_inputs()
       self.model_tester.create_and_check_backbone(*__SCREAMING_SNAKE_CASE    )
    @unittest.skip(reason="""Nat does not use inputs_embeds"""    )
    def 						lowerCamelCase__    (						self    ):
  
  
  
       '''simple docstring'''
  
       pass
    @unittest.skip(reason="""Nat does not use feedforward chunking"""    )
    def 						lowerCamelCase__    (						self    ):
  
  
  
       '''simple docstring'''
  
       pass
    def 						lowerCamelCase__    (						self    ):
  
  
  
       '''simple docstring'''
  
       __lowerCAmelCase		, __lowerCAmelCase      		=       self.model_tester.prepare_config_and_inputs_for_common()
  
       for model_class in self.all_model_classes:
          __lowerCAmelCase      		=       model_class(__SCREAMING_SNAKE_CASE    )
          self.assertIsInstance(model.get_input_embeddings(),(nn.Module)    )
          __lowerCAmelCase      		=       model.get_output_embeddings()
          self.assertTrue(x is None or isinstance(__SCREAMING_SNAKE_CASE,nn.Linear    )    )
    def 						lowerCamelCase__    (						self    ):
  
  
  
       '''simple docstring'''
  
       __lowerCAmelCase		, __lowerCAmelCase      		=       self.model_tester.prepare_config_and_inputs_for_common()
  
       for model_class in self.all_model_classes:
          __lowerCAmelCase      		=       model_class(__SCREAMING_SNAKE_CASE    )
          __lowerCAmelCase      		=       inspect.signature(model.forward    )
          # signature.parameters is an OrderedDict => so arg_names order is deterministic
          __lowerCAmelCase      		=       [*signature.parameters.keys()]
  
          __lowerCAmelCase      		=       ["""pixel_values"""]
          self.assertListEqual(arg_names[:1],__SCREAMING_SNAKE_CASE    )
    def 						lowerCamelCase__    (						self    ):
  
  
  
       '''simple docstring'''
  
       self.skipTest("""Nat's attention operation is handled entirely by NATTEN."""    )
    def 						lowerCamelCase__    (						self,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE    ):
  
  
  
       '''simple docstring'''
  
       __lowerCAmelCase      		=       model_class(__SCREAMING_SNAKE_CASE    )
       model.to(__SCREAMING_SNAKE_CASE    )
       model.eval()
  
       with torch.no_grad():
          __lowerCAmelCase      		=       model(**self._prepare_for_class(__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE    )    )
  
       __lowerCAmelCase      		=       outputs.hidden_states
  
       __lowerCAmelCase      		=       getattr(
           self.model_tester,"""expected_num_hidden_layers""",len(self.model_tester.depths    ) + 1    )
       self.assertEqual(len(__SCREAMING_SNAKE_CASE    ),__SCREAMING_SNAKE_CASE    )
  
       # Nat has a different seq_length
       __lowerCAmelCase      		=       (
           config.patch_size
           if isinstance(config.patch_size,collections.abc.Iterable    )
           else (config.patch_size, config.patch_size)
       )
  
       __lowerCAmelCase      		=       image_size[0] // patch_size[0]
       __lowerCAmelCase      		=       image_size[1] // patch_size[1]
  
       self.assertListEqual(
           list(hidden_states[0].shape[-3:]    ),[height, width, self.model_tester.embed_dim],)
  
       if model_class.__name__ != "NatBackbone":
          __lowerCAmelCase      		=       outputs.reshaped_hidden_states
          self.assertEqual(len(__SCREAMING_SNAKE_CASE    ),__SCREAMING_SNAKE_CASE    )
  
          __lowerCAmelCase		, __lowerCAmelCase		, __lowerCAmelCase		, __lowerCAmelCase      		=       reshaped_hidden_states[0].shape
          __lowerCAmelCase      		=       (
              reshaped_hidden_states[0].view(__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE    ).permute(0,2,3,1    )
          )
          self.assertListEqual(
              list(reshaped_hidden_states.shape[-3:]    ),[height, width, self.model_tester.embed_dim],)
    def 						lowerCamelCase__    (						self    ):
  
  
  
       '''simple docstring'''
  
       __lowerCAmelCase		, __lowerCAmelCase      		=       self.model_tester.prepare_config_and_inputs_for_common()
  
       __lowerCAmelCase      		=       (
           self.model_tester.image_size
           if isinstance(self.model_tester.image_size,collections.abc.Iterable    )
           else (self.model_tester.image_size, self.model_tester.image_size)
       )
  
       for model_class in self.all_model_classes:
          __lowerCAmelCase      		=       True
          self.check_hidden_states_output(__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE    )
  
          # check that output_hidden_states also work using config
          del inputs_dict["output_hidden_states"]
          __lowerCAmelCase      		=       True
  
          self.check_hidden_states_output(__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE    )
    @slow
    def 						lowerCamelCase__    (						self    ):
  
  
  
       '''simple docstring'''
  
       for model_name in NAT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
          __lowerCAmelCase      		=       NatModel.from_pretrained(__SCREAMING_SNAKE_CASE    )
          self.assertIsNotNone(__SCREAMING_SNAKE_CASE    )
  
  
  
  
  
  
  
    def 						lowerCamelCase__    (						self    ):
  
  
  
       '''simple docstring'''
  
       __lowerCAmelCase		, __lowerCAmelCase      		=       self.model_tester.prepare_config_and_inputs_for_common()
  
       __lowerCAmelCase      		=       _config_zero_init(__SCREAMING_SNAKE_CASE    )
       for model_class in self.all_model_classes:
          __lowerCAmelCase      		=       model_class(config=__SCREAMING_SNAKE_CASE    )
          for name, param in model.named_parameters():
             if "embeddings" not in name and param.requires_grad:
                self.assertIn(
                    ((param.data.mean() * 1e9).round() / 1e9).item(),[0.0, 1.0],msg=f'Parameter {name} of model {model_class} seems not properly initialized',)
  
  
  
  
  
  @require_natten
  @require_vision
  @require_torch
  class 					_UpperCAmelCase							(		unittest.TestCase     ):
    @cached_property
    def 						lowerCamelCase__    (						self    ):
  
  
  
       '''simple docstring'''
  
       return AutoImageProcessor.from_pretrained("""shi-labs/nat-mini-in1k-224"""    ) if is_vision_available() else None
  
  
  
  
  
  
  
    @slow
    def 						lowerCamelCase__    (						self    ):
  
  
  
       '''simple docstring'''
  
       __lowerCAmelCase      		=       NatForImageClassification.from_pretrained("""shi-labs/nat-mini-in1k-224"""    ).to(__SCREAMING_SNAKE_CASE    )
       __lowerCAmelCase      		=       self.default_image_processor
  
       __lowerCAmelCase      		=       Image.open("""./tests/fixtures/tests_samples/COCO/000000039769.png"""    )
       __lowerCAmelCase      		=       image_processor(images=__SCREAMING_SNAKE_CASE,return_tensors="""pt"""    ).to(__SCREAMING_SNAKE_CASE    )
  
       # forward pass
       with torch.no_grad():
          __lowerCAmelCase      		=       model(**__SCREAMING_SNAKE_CASE    )
  
       # verify the logits
       __lowerCAmelCase      		=       torch.Size((1, 10_00)    )
       self.assertEqual(outputs.logits.shape,__SCREAMING_SNAKE_CASE    )
       __lowerCAmelCase      		=       torch.tensor([0.3805, -0.8676, -0.3912]    ).to(__SCREAMING_SNAKE_CASE    )
       self.assertTrue(torch.allclose(outputs.logits[0, :3],__SCREAMING_SNAKE_CASE,atol=1e-4    )    )
  
  
  
  
  
  @require_torch
  @require_natten
  class 					_UpperCAmelCase							(		unittest.TestCase			,      snake_case_     ):
    a     :     Any     						=(NatBackbone,) if is_torch_available() else ()
    a     :     Dict     						=NatConfig
    def 						lowerCamelCase__    (						self    ):
  
  
  
       '''simple docstring'''
  
       __lowerCAmelCase      		=       NatModelTester(self    )
  
  
style_context: 
  
  
  
  
  
  '''simple docstring'''
  
  
  
  
  
  
  
  import math
  import sys
  
  
  
  
  
  class 					_UpperCAmelCase							:
  		def __init__(						self    ):
  
  
  
  					'''simple docstring'''
  
  					__lowerCAmelCase      		=       0
  					__lowerCAmelCase      		=       []
  					__lowerCAmelCase      		=       {}  # To store the pos of node in array
  		def 						lowerCamelCase__    (						self    ):
  
  
  
  					'''simple docstring'''
  
  					return self.cur_size == 0
  		def 						lowerCamelCase__    (						self,__SCREAMING_SNAKE_CASE    ):
  
  
  
  					'''simple docstring'''
  
  					__lowerCAmelCase      		=       self.left(__SCREAMING_SNAKE_CASE    )
  					__lowerCAmelCase      		=       self.right(__SCREAMING_SNAKE_CASE    )
  					if lc < self.cur_size and self.array(__SCREAMING_SNAKE_CASE    )[0] < self.array(__SCREAMING_SNAKE_CASE    )[0]:
  								__lowerCAmelCase      		=       lc
  					else:
  								__lowerCAmelCase      		=       idx
  					if rc < self.cur_size and self.array(__SCREAMING_SNAKE_CASE    )[0] < self.array(__SCREAMING_SNAKE_CASE    )[0]:
  								__lowerCAmelCase      		=       rc
  					if smallest != idx:
  								self.swap(__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE    )
  								self.min_heapify(__SCREAMING_SNAKE_CASE    )
  		def 						lowerCamelCase__    (						self,__SCREAMING_SNAKE_CASE    ):
  
  
  
  					'''simple docstring'''
  
  					__lowerCAmelCase      		=       self.cur_size
  					self.cur_size += 1
  					self.array.append((sys.maxsize, tup[1])    )
  					self.decrease_key((sys.maxsize, tup[1]),tup[0]    )
  		def 						lowerCamelCase__    (						self    ):
  
  
  
  					'''simple docstring'''
  
  					__lowerCAmelCase      		=       self.array[0][1]
  					__lowerCAmelCase      		=       self.array[self.cur_size - 1]
  					self.cur_size -= 1
  					self.min_heapify(1    )
  					del self.pos[min_node]
  					return min_node
  		def 						lowerCamelCase__    (						self,__SCREAMING_SNAKE_CASE    ):
  
  
  
  					'''simple docstring'''
  
  					return 2 * i + 1
  		def 						lowerCamelCase__    (						self,__SCREAMING_SNAKE_CASE    ):
  
  
  
  					'''simple docstring'''
  
  					return 2 * i + 2
  		def 						lowerCamelCase__    (						self,__SCREAMING_SNAKE_CASE    ):
  
  
  
  					'''simple docstring'''
  
  					return math.floor(i / 2    )
  		def 						lowerCamelCase__    (						self,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE    ):
  
  
  
  					'''simple docstring'''
  
  					__lowerCAmelCase      		=       j
  					__lowerCAmelCase      		=       i
  					__lowerCAmelCase      		=       self.array[i]
  					__lowerCAmelCase      		=       self.array[j]
  					__lowerCAmelCase      		=       temp
  
  
  
  
  
  
  
  		def 						lowerCamelCase__    (						self,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE    ):
  
  
  
  					'''simple docstring'''
  
  					__lowerCAmelCase      		=       self.pos[tup[1]]
  					# assuming the new_d is atmost old_d
  					__lowerCAmelCase      		=       (new_d, tup[1])
  					while idx > 0 and self.array[self.par(__SCREAMING_SNAKE_CASE    )][0] > self.array[idx][0]:
  								self.swap(__SCREAMING_SNAKE_CASE,self.par(__SCREAMING_SNAKE_CASE    )    )
  								__lowerCAmelCase      		=       self.par(__SCREAMING_SNAKE_CASE    )
  
  
  
  
  
  class 					_UpperCAmelCase							:
  		def __init__(						self,__SCREAMING_SNAKE_CASE    ):
  
  
  
  					'''simple docstring'''
  
  					__lowerCAmelCase      		=       {}  # To store graph: u -> (v,w)
  					__lowerCAmelCase      		=       num  # Number of nodes in graph
  					# To store the distance from source vertex
  					__lowerCAmelCase      		=       [0] * self.num_nodes
  					__lowerCAmelCase      		=       [-1] * self.num_nodes  # To store the path
  		def 						lowerCamelCase__    (						self,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE    ):
  
  
  
  					'''simple docstring'''
  
  					if u in self.adjList:
  								self.adjList[u].append((v, w)    )
  					else:
  								__lowerCAmelCase      		=       [(v, w)]
  
  					# Assuming undirected graph
  					if v in self.adjList:
  								self.adjList[v].append((u, w)    )
  					else:
  								__lowerCAmelCase      		=       [(u, w)]
  		def 						lowerCamelCase__    (						self    ):
  
  
  
  					'''simple docstring'''
  
  					for u in self.adjList:
  								print(__SCREAMING_SNAKE_CASE,"""->""",""" -> """.join(str(f'{v}({w})'    ) for v, w in self.adjList[u]    )    )
  		def 						lowerCamelCase__    (						self,__SCREAMING_SNAKE_CASE    ):
  
  
  
  					'''simple docstring'''
  
  					__lowerCAmelCase      		=       [-1] * self.num_nodes
  					# src is the source node
  					__lowerCAmelCase      		=       0
  					__lowerCAmelCase      		=       PriorityQueue()
  					q.insert((0, src)    )  # (dist from src, node)
  					for u in self.adjList:
  								if u != src:
  											__lowerCAmelCase      		=       sys.maxsize  # Infinity
  											__lowerCAmelCase      		=       -1
  
  					while not q.is_empty():
  								__lowerCAmelCase      		=       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      		=       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),__SCREAMING_SNAKE_CASE    )
  														__lowerCAmelCase      		=       new_dist
  														__lowerCAmelCase      		=       u
  
          # Show the shortest distances from src
  					self.show_distances(__SCREAMING_SNAKE_CASE    )
  		def 						lowerCamelCase__    (						self,__SCREAMING_SNAKE_CASE    ):
  
  
  
  					'''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 						lowerCamelCase__    (						self,__SCREAMING_SNAKE_CASE,__SCREAMING_SNAKE_CASE    ):
  
  
  
  					'''simple docstring'''
  
  					__lowerCAmelCase      		=       []
  					__lowerCAmelCase      		=       0
  					__lowerCAmelCase      		=       dest
  					# Backtracking from dest to src
  					while self.par[temp] != -1:
  								path.append(__SCREAMING_SNAKE_CASE    )
  								if temp != src:
  											for v, w in self.adjList[temp]:
  														if v == self.par[temp]:
  																	cost += w
  																	break
  								__lowerCAmelCase      		=       self.par[temp]
  					path.append(__SCREAMING_SNAKE_CASE    )
  					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: """,__SCREAMING_SNAKE_CASE    )
  
  
  if __name__ == "__main__":
  	_a      :				str											=					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, 1_1)
  	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, 1_4)
  	graph.add_edge(4, 5, 1_0)
  	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
  
  