


'''simple docstring'''


import inspect
import unittest
import warnings
from math import ceil, floor

from transformers import LevitConfig
from transformers.file_utils import cached_property, is_torch_available, is_vision_available
from transformers.models.auto import get_values
from transformers.testing_utils import require_torch, require_vision, slow, torch_device

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
						import torch

						from transformers import (
						    MODEL_FOR_IMAGE_CLASSIFICATION_MAPPING,
						    MODEL_MAPPING,
						    LevitForImageClassification,
						    LevitForImageClassificationWithTeacher,
						    LevitModel,
						)
						from transformers.models.levit.modeling_levit import LEVIT_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
						from PIL import Image

						from transformers import LevitImageProcessor






class 		lowerCAmelCase__	(	lowerCamelCase_		):




			def 							lowerCAmelCase__			(						self     :   Optional[Any]       )      ->Any:



					'''simple docstring'''







					_UpperCAmelCase						:				int	    =					self.config_class(**self.inputs_dict       )
					self.parent.assertTrue(hasattr(__SCREAMING_SNAKE_CASE		,     "hidden_sizes"       )       )
					self.parent.assertTrue(hasattr(__SCREAMING_SNAKE_CASE		,     "num_attention_heads"       )       )






class 		lowerCAmelCase__	:




			def __init__(						self     :   int		,     lowerCamelCase__     :   str		,     lowerCamelCase__     :   str=13		,     lowerCamelCase__     :   List[Any]=64		,     lowerCamelCase__     :   Any=3		,     lowerCamelCase__     :   Optional[int]=3		,     lowerCamelCase__     :   str=2		,     lowerCamelCase__     :   Any=1		,     lowerCamelCase__     :   Tuple=16		,     lowerCamelCase__     :   Optional[int]=[1_28, 2_56, 3_84]		,     lowerCamelCase__     :   Union[str, Any]=[4, 6, 8]		,     lowerCamelCase__     :   Optional[int]=[2, 3, 4]		,     lowerCamelCase__     :   Union[str, Any]=[16, 16, 16]		,     lowerCamelCase__     :   Union[str, Any]=0		,     lowerCamelCase__     :   Optional[int]=[2, 2, 2]		,     lowerCamelCase__     :   Tuple=[2, 2, 2]		,     lowerCamelCase__     :   Optional[int]=0.0_2		,     lowerCamelCase__     :   Optional[Any]=True		,     lowerCamelCase__     :   Any=True		,     lowerCamelCase__     :   Tuple=2		,     )      ->str:



					'''simple docstring'''







					_UpperCAmelCase						:				Dict	    =					parent
					_UpperCAmelCase						:				int	    =					batch_size
					_UpperCAmelCase						:				List[Any]	    =					image_size
					_UpperCAmelCase						:				int	    =					num_channels
					_UpperCAmelCase						:				Union[str, Any]	    =					kernel_size
					_UpperCAmelCase						:				int	    =					stride
					_UpperCAmelCase						:				Optional[int]	    =					padding
					_UpperCAmelCase						:				List[Any]	    =					hidden_sizes
					_UpperCAmelCase						:				Any	    =					num_attention_heads
					_UpperCAmelCase						:				Tuple	    =					depths
					_UpperCAmelCase						:				int	    =					key_dim
					_UpperCAmelCase						:				Optional[Any]	    =					drop_path_rate
					_UpperCAmelCase						:				Optional[Any]	    =					patch_size
					_UpperCAmelCase						:				Any	    =					attention_ratio
					_UpperCAmelCase						:				Union[str, Any]	    =					mlp_ratio
					_UpperCAmelCase						:				Optional[int]	    =					initializer_range
					_UpperCAmelCase						:				Union[str, Any]	    =					[
					    ['''Subsample''', key_dim[0], hidden_sizes[0] // key_dim[0], 4, 2, 2],
					    ['''Subsample''', key_dim[0], hidden_sizes[1] // key_dim[0], 4, 2, 2],
					]
					_UpperCAmelCase						:				Union[str, Any]	    =					is_training
					_UpperCAmelCase						:				Optional[int]	    =					use_labels
					_UpperCAmelCase						:				int	    =					num_labels
					_UpperCAmelCase						:				List[Any]	    =					initializer_range




			def 							lowerCAmelCase__			(						self     :   List[Any]       )      ->List[Any]:



					'''simple docstring'''







					_UpperCAmelCase						:				Optional[Any]	    =					floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]       )

					_UpperCAmelCase						:				Dict	    =					None
					if self.use_labels:
							_UpperCAmelCase						:				Tuple	    =					ids_tensor([self.batch_size]		,     self.num_labels       )

					_UpperCAmelCase						:				str	    =					self.get_config()
					return config, pixel_values, labels




			def 							lowerCAmelCase__			(						self     :   Optional[int]       )      ->Dict:



					'''simple docstring'''







					return LevitConfig(
					    image_size=self.image_size		,     num_channels=self.num_channels		,     kernel_size=self.kernel_size		,     stride=self.stride		,     padding=self.padding		,     patch_size=self.patch_size		,     hidden_sizes=self.hidden_sizes		,     num_attention_heads=self.num_attention_heads		,     depths=self.depths		,     key_dim=self.key_dim		,     drop_path_rate=self.drop_path_rate		,     mlp_ratio=self.mlp_ratio		,     attention_ratio=self.attention_ratio		,     initializer_range=self.initializer_range		,     down_ops=self.down_ops		,     )




			def 							lowerCAmelCase__			(						self     :   Optional[Any]		,     lowerCamelCase__     :   List[str]		,     lowerCamelCase__     :   Dict		,     lowerCamelCase__     :   Union[str, Any]       )      ->Optional[Any]:



					'''simple docstring'''







					_UpperCAmelCase						:				Dict	    =					LevitModel(config=__SCREAMING_SNAKE_CASE       )
					model.to(__SCREAMING_SNAKE_CASE       )
					model.eval()
					_UpperCAmelCase						:				List[Any]	    =					model(__SCREAMING_SNAKE_CASE       )
					_UpperCAmelCase						:				Union[str, Any]	    =					(self.image_size, self.image_size)
					_UpperCAmelCase						:				Any	    =					image_size[0], image_size[1]
					for _ in range(4       ):
							_UpperCAmelCase						:				int	    =					floor(((height + 2 * self.padding - self.kernel_size) / self.stride) + 1       )
							_UpperCAmelCase						:				Any	    =					floor(((width + 2 * self.padding - self.kernel_size) / self.stride) + 1       )
					self.parent.assertEqual(
					    result.last_hidden_state.shape		,     (self.batch_size, ceil(height / 4       ) * ceil(width / 4       ), self.hidden_sizes[-1])		,     )




			def 							lowerCAmelCase__			(						self     :   Any		,     lowerCamelCase__     :   List[str]		,     lowerCamelCase__     :   Optional[int]		,     lowerCamelCase__     :   Optional[Any]       )      ->Union[str, Any]:



					'''simple docstring'''







					_UpperCAmelCase						:				int	    =					self.num_labels
					_UpperCAmelCase						:				Dict	    =					LevitForImageClassification(__SCREAMING_SNAKE_CASE       )
					model.to(__SCREAMING_SNAKE_CASE       )
					model.eval()
					_UpperCAmelCase						:				Optional[int]	    =					model(__SCREAMING_SNAKE_CASE		,     labels=__SCREAMING_SNAKE_CASE       )
					self.parent.assertEqual(result.logits.shape		,     (self.batch_size, self.num_labels)       )






			def 							lowerCAmelCase__			(						self     :   Any       )      ->List[str]:



					'''simple docstring'''







					_UpperCAmelCase						:				Dict	    =					self.prepare_config_and_inputs()
					_UpperCAmelCase						:				List[Any]	    =					config_and_inputs
					_UpperCAmelCase						:				List[Any]	    =					{'''pixel_values''': pixel_values}
					return config, inputs_dict






@require_torch
class 		lowerCAmelCase__	(	lowerCamelCase_			,				lowerCamelCase_			,				unittest.TestCase		):
			lowerCAmelCase       :		Union[str, Any]				      =   (
			    (LevitModel, LevitForImageClassification, LevitForImageClassificationWithTeacher)
			    if is_torch_available()
			    else ()
			)
			lowerCAmelCase       :		int				      =   (
			    {
			        "feature-extraction": LevitModel,
			        "image-classification": (LevitForImageClassification, LevitForImageClassificationWithTeacher),
			    }
			    if is_torch_available()
			    else {}
			)

			lowerCAmelCase       :		Optional[int]				      =   False
			lowerCAmelCase       :		Any				      =   False
			lowerCAmelCase       :		List[str]				      =   False
			lowerCAmelCase       :		Union[str, Any]				      =   False
			lowerCAmelCase       :		Any				      =   False




			def 							lowerCAmelCase__			(						self     :   Any       )      ->Optional[int]:



					'''simple docstring'''







					_UpperCAmelCase						:				Union[str, Any]	    =					LevitModelTester(self       )
					_UpperCAmelCase						:				Any	    =					ConfigTester(self		,     config_class=__SCREAMING_SNAKE_CASE		,     has_text_modality=__SCREAMING_SNAKE_CASE		,     hidden_size=37       )




			def 							lowerCAmelCase__			(						self     :   Optional[Any]       )      ->Tuple:



					'''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     :   Tuple       )      ->int:



					'''simple docstring'''







					return




			@unittest.skip(reason="Levit does not use inputs_embeds"       )
			def 							lowerCAmelCase__			(						self     :   Tuple       )      ->List[Any]:



					'''simple docstring'''







					pass




			@unittest.skip(reason="Levit does not support input and output embeddings"       )
			def 							lowerCAmelCase__			(						self     :   Optional[int]       )      ->Optional[Any]:



					'''simple docstring'''







					pass




			@unittest.skip(reason="Levit does not output attentions"       )
			def 							lowerCAmelCase__			(						self     :   Optional[Any]       )      ->str:



					'''simple docstring'''







					pass




			def 							lowerCAmelCase__			(						self     :   str       )      ->Tuple:



					'''simple docstring'''







					_UpperCAmelCase						:				Optional[int]	    =					self.model_tester.prepare_config_and_inputs_for_common()

					for model_class in self.all_model_classes:
							_UpperCAmelCase						:				List[str]	    =					model_class(__SCREAMING_SNAKE_CASE       )
							_UpperCAmelCase						:				Any	    =					inspect.signature(model.forward       )
							# signature.parameters is an OrderedDict => so arg_names order is deterministic
							_UpperCAmelCase						:				Any	    =					[*signature.parameters.keys()]

							_UpperCAmelCase						:				Optional[int]	    =					['''pixel_values''']
							self.assertListEqual(arg_names[:1]		,     __SCREAMING_SNAKE_CASE       )




			def 							lowerCAmelCase__			(						self     :   int       )      ->str:



					'''simple docstring'''







					def check_hidden_states_output(lowerCamelCase__     :   Tuple		,     lowerCamelCase__     :   str		,     lowerCamelCase__     :   Dict       ):
							_UpperCAmelCase						:				str	    =					model_class(__SCREAMING_SNAKE_CASE       )
							model.to(__SCREAMING_SNAKE_CASE       )
							model.eval()

							with torch.no_grad():
									_UpperCAmelCase						:				List[Any]	    =					model(**self._prepare_for_class(__SCREAMING_SNAKE_CASE		,     __SCREAMING_SNAKE_CASE       )       )

							_UpperCAmelCase						:				Optional[Any]	    =					outputs.hidden_states

							_UpperCAmelCase						:				Any	    =					len(self.model_tester.depths       ) + 1
							self.assertEqual(len(__SCREAMING_SNAKE_CASE       )		,     __SCREAMING_SNAKE_CASE       )

							_UpperCAmelCase						:				int	    =					(self.model_tester.image_size, self.model_tester.image_size)
							_UpperCAmelCase						:				List[Any]	    =					image_size[0], image_size[1]
							for _ in range(4       ):
									_UpperCAmelCase						:				Optional[int]	    =					floor(
									    (
									        (height + 2 * self.model_tester.padding - self.model_tester.kernel_size)
									        / self.model_tester.stride
									    )
									    + 1       )
									_UpperCAmelCase						:				List[str]	    =					floor(
									    (
									        (width + 2 * self.model_tester.padding - self.model_tester.kernel_size)
									        / self.model_tester.stride
									    )
									    + 1       )
							# verify the first hidden states (first block)
							self.assertListEqual(
							    list(hidden_states[0].shape[-2:]       )		,     [
							        height * width,
							        self.model_tester.hidden_sizes[0],
							    ]		,     )

					_UpperCAmelCase						:				Tuple	    =					self.model_tester.prepare_config_and_inputs_for_common()

					for model_class in self.all_model_classes:
							_UpperCAmelCase						:				List[str]	    =					True
							check_hidden_states_output(__SCREAMING_SNAKE_CASE		,     __SCREAMING_SNAKE_CASE		,     __SCREAMING_SNAKE_CASE       )

							# check that output_hidden_states also work using config
							del inputs_dict["output_hidden_states"]
							_UpperCAmelCase						:				Optional[int]	    =					True

							check_hidden_states_output(__SCREAMING_SNAKE_CASE		,     __SCREAMING_SNAKE_CASE		,     __SCREAMING_SNAKE_CASE       )




			@unittest.skip("Will be fixed soon by reducing the size of the model used for common tests."       )
			def 							lowerCAmelCase__			(						self     :   List[Any]       )      ->Any:



					'''simple docstring'''







					pass




			def 							lowerCAmelCase__			(						self     :   Optional[int]		,     lowerCamelCase__     :   Any		,     lowerCamelCase__     :   Optional[int]		,     lowerCamelCase__     :   str=False       )      ->int:



					'''simple docstring'''







					_UpperCAmelCase						:				Optional[int]	    =					super()._prepare_for_class(__SCREAMING_SNAKE_CASE		,     __SCREAMING_SNAKE_CASE		,     return_labels=__SCREAMING_SNAKE_CASE       )

					if return_labels:
							if model_class.__name__ == "LevitForImageClassificationWithTeacher":
									del inputs_dict["labels"]

					return inputs_dict




			def 							lowerCAmelCase__			(						self     :   int       )      ->List[Any]:



					'''simple docstring'''







					_UpperCAmelCase						:				Optional[int]	    =					self.model_tester.prepare_config_and_inputs()
					self.model_tester.create_and_check_model(*__SCREAMING_SNAKE_CASE       )




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



					'''simple docstring'''







					_UpperCAmelCase						:				Tuple	    =					self.model_tester.prepare_config_and_inputs()
					self.model_tester.create_and_check_for_image_classification(*__SCREAMING_SNAKE_CASE       )




			def 							lowerCAmelCase__			(						self     :   List[str]       )      ->Optional[Any]:



					'''simple docstring'''







					if not self.model_tester.is_training:
							return

					_UpperCAmelCase						:				str	    =					self.model_tester.prepare_config_and_inputs_for_common()
					_UpperCAmelCase						:				Dict	    =					True

					for model_class in self.all_model_classes:
							# LevitForImageClassificationWithTeacher supports inference-only
							if (
							    model_class in get_values(__SCREAMING_SNAKE_CASE       )
							    or model_class.__name__ == "LevitForImageClassificationWithTeacher"
							):
									continue
							_UpperCAmelCase						:				str	    =					model_class(__SCREAMING_SNAKE_CASE       )
							model.to(__SCREAMING_SNAKE_CASE       )
							model.train()
							_UpperCAmelCase						:				List[str]	    =					self._prepare_for_class(__SCREAMING_SNAKE_CASE		,     __SCREAMING_SNAKE_CASE		,     return_labels=__SCREAMING_SNAKE_CASE       )
							_UpperCAmelCase						:				Optional[Any]	    =					model(**__SCREAMING_SNAKE_CASE       ).loss
							loss.backward()




			def 							lowerCAmelCase__			(						self     :   List[Any]       )      ->Optional[int]:



					'''simple docstring'''







					_UpperCAmelCase						:				Optional[int]	    =					self.model_tester.prepare_config_and_inputs_for_common()
					if not self.model_tester.is_training:
							return

					_UpperCAmelCase						:				Union[str, Any]	    =					False
					_UpperCAmelCase						:				int	    =					True

					for model_class in self.all_model_classes:
							if model_class in get_values(__SCREAMING_SNAKE_CASE       ) or not model_class.supports_gradient_checkpointing:
									continue
							# LevitForImageClassificationWithTeacher supports inference-only
							if model_class.__name__ == "LevitForImageClassificationWithTeacher":
									continue
							_UpperCAmelCase						:				Optional[Any]	    =					model_class(__SCREAMING_SNAKE_CASE       )
							model.gradient_checkpointing_enable()
							model.to(__SCREAMING_SNAKE_CASE       )
							model.train()
							_UpperCAmelCase						:				int	    =					self._prepare_for_class(__SCREAMING_SNAKE_CASE		,     __SCREAMING_SNAKE_CASE		,     return_labels=__SCREAMING_SNAKE_CASE       )
							_UpperCAmelCase						:				Dict	    =					model(**__SCREAMING_SNAKE_CASE       ).loss
							loss.backward()




			def 							lowerCAmelCase__			(						self     :   List[str]       )      ->Dict:



					'''simple docstring'''







					_UpperCAmelCase						:				List[Any]	    =					self.model_tester.prepare_config_and_inputs_for_common()

					_UpperCAmelCase						:				Union[str, Any]	    =					[
					    {'''title''': '''multi_label_classification''', '''num_labels''': 2, '''dtype''': torch.float},
					    {'''title''': '''single_label_classification''', '''num_labels''': 1, '''dtype''': torch.long},
					    {'''title''': '''regression''', '''num_labels''': 1, '''dtype''': torch.float},
					]

					for model_class in self.all_model_classes:
							if (
							    model_class
							    not in [
							        *get_values(__SCREAMING_SNAKE_CASE       ),
							    ]
							    or model_class.__name__ == "LevitForImageClassificationWithTeacher"
							):
									continue

							for problem_type in problem_types:
									with self.subTest(msg=F"""Testing {model_class} with {problem_type['title']}"""       ):
											_UpperCAmelCase						:				Any	    =					problem_type['''title''']
											_UpperCAmelCase						:				List[Any]	    =					problem_type['''num_labels''']

											_UpperCAmelCase						:				List[Any]	    =					model_class(__SCREAMING_SNAKE_CASE       )
											model.to(__SCREAMING_SNAKE_CASE       )
											model.train()

											_UpperCAmelCase						:				Any	    =					self._prepare_for_class(__SCREAMING_SNAKE_CASE		,     __SCREAMING_SNAKE_CASE		,     return_labels=__SCREAMING_SNAKE_CASE       )

											if problem_type["num_labels"] > 1:
													_UpperCAmelCase						:				str	    =					inputs['''labels'''].unsqueeze(1       ).repeat(1		,     problem_type["num_labels"]       )

											_UpperCAmelCase						:				Optional[Any]	    =					inputs['''labels'''].to(problem_type["dtype"]       )

											# This tests that we do not trigger the warning form PyTorch "Using a target size that is different
											# to the input size. This will likely lead to incorrect results due to broadcasting. Please ensure
											# they have the same size." which is a symptom something in wrong for the regression problem.
											# See https://github.com/huggingface/transformers/issues/11780
											with warnings.catch_warnings(record=__SCREAMING_SNAKE_CASE       ) as warning_list:
													_UpperCAmelCase						:				List[Any]	    =					model(**__SCREAMING_SNAKE_CASE       ).loss
											for w in warning_list:
													if "Using a target size that is different to the input size" in str(w.message       ):
															raise ValueError(
															    F"""Something is going wrong in the regression problem: intercepted {w.message}"""       )

											loss.backward()






			@slow
			def 							lowerCAmelCase__			(						self     :   Any       )      ->Tuple:



					'''simple docstring'''







					for model_name in LEVIT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
							_UpperCAmelCase						:				List[Any]	    =					LevitModel.from_pretrained(__SCREAMING_SNAKE_CASE       )
							self.assertIsNotNone(__SCREAMING_SNAKE_CASE       )






def        __lowerCAmelCase       ():
		_UpperCAmelCase						:				Any	    =					Image.open("./tests/fixtures/tests_samples/COCO/000000039769.png"      )
		return image






@require_torch
@require_vision
class 		lowerCAmelCase__	(	unittest.TestCase		):




			@cached_property
			def 							lowerCAmelCase__			(						self     :   str       )      ->Optional[Any]:



					'''simple docstring'''







					return LevitImageProcessor.from_pretrained(LEVIT_PRETRAINED_MODEL_ARCHIVE_LIST[0]       )






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



					'''simple docstring'''







					_UpperCAmelCase						:				List[Any]	    =					LevitForImageClassificationWithTeacher.from_pretrained(LEVIT_PRETRAINED_MODEL_ARCHIVE_LIST[0]       ).to(
					    __SCREAMING_SNAKE_CASE       )

					_UpperCAmelCase						:				str	    =					self.default_image_processor
					_UpperCAmelCase						:				Dict	    =					prepare_img()
					_UpperCAmelCase						:				List[Any]	    =					image_processor(images=__SCREAMING_SNAKE_CASE		,     return_tensors="pt"       ).to(__SCREAMING_SNAKE_CASE       )

					# forward pass
					with torch.no_grad():
							_UpperCAmelCase						:				List[Any]	    =					model(**__SCREAMING_SNAKE_CASE       )

					# verify the logits
					_UpperCAmelCase						:				Tuple	    =					torch.Size((1, 10_00)       )
					self.assertEqual(outputs.logits.shape		,     __SCREAMING_SNAKE_CASE       )

					_UpperCAmelCase						:				Any	    =					torch.tensor([1.0_4_4_8, -0.3_7_4_5, -1.8_3_1_7]       ).to(__SCREAMING_SNAKE_CASE       )

					self.assertTrue(torch.allclose(outputs.logits[0, :3]		,     __SCREAMING_SNAKE_CASE		,     atol=1E-4       )       )





'''simple docstring'''







import argparse
import copy
def 					snake_case_		(				__SCREAMING_SNAKE_CASE					: Optional[int]							):



						"""simple docstring"""





						lowercase_	:     List[Any]													=       {}

						with open(__SCREAMING_SNAKE_CASE							) as f:
												for line in f:
																		if line.split()[0] not in dict_of_neighbours:
																								lowercase_	:     Union[str, Any]													=       []
																								_list.append([line.split()[1], line.split()[2]]							)
																								lowercase_	:     str													=       _list
																		else:
																								dict_of_neighbours[line.split()[0]].append(
																								    [line.split()[1], line.split()[2]]							)
																		if line.split()[1] not in dict_of_neighbours:
																								lowercase_	:     Optional[int]													=       []
																								_list.append([line.split()[0], line.split()[2]]							)
																								lowercase_	:     Dict													=       _list
																		else:
																								dict_of_neighbours[line.split()[1]].append(
																								    [line.split()[0], line.split()[2]]							)

						return dict_of_neighbours
def 					snake_case_		(				__SCREAMING_SNAKE_CASE					: str      ,      __SCREAMING_SNAKE_CASE					: Tuple							):



						"""simple docstring"""





						with open(__SCREAMING_SNAKE_CASE							) as f:
												lowercase_	:     List[str]													=       f.read(1							)
						lowercase_	:     Optional[int]													=       start_node

						lowercase_	:     Any													=       []

						lowercase_	:     List[str]													=       start_node

						lowercase_	:     Optional[Any]													=       0
						while visiting not in first_solution:
												lowercase_	:     Any													=       10000
												for k in dict_of_neighbours[visiting]:
																		if int(k[1]							) < int(__SCREAMING_SNAKE_CASE							) and k[0] not in first_solution:
																								lowercase_	:     List[Any]													=       k[1]
																								lowercase_	:     List[Any]													=       k[0]

												first_solution.append(__SCREAMING_SNAKE_CASE							)
												lowercase_	:     Optional[Any]													=       distance_of_first_solution + int(__SCREAMING_SNAKE_CASE							)
												lowercase_	:     int													=       best_node

						first_solution.append(__SCREAMING_SNAKE_CASE							)

						lowercase_	:     Tuple													=       0
						for k in dict_of_neighbours[first_solution[-2]]:
												if k[0] == start_node:
																		break
												position += 1

						lowercase_	:     Optional[Any]													=       (
						    distance_of_first_solution
						    + int(dict_of_neighbours[first_solution[-2]][position][1]							)
						    - 10000
						)
						return first_solution, distance_of_first_solution
def 					snake_case_		(				__SCREAMING_SNAKE_CASE					: Optional[Any]      ,      __SCREAMING_SNAKE_CASE					: Union[str, Any]							):



						"""simple docstring"""





						lowercase_	:     Tuple													=       []

						for n in solution[1:-1]:
												lowercase_	:     List[str]													=       solution.index(__SCREAMING_SNAKE_CASE							)
												for kn in solution[1:-1]:
																		lowercase_	:     Any													=       solution.index(__SCREAMING_SNAKE_CASE							)
																		if n == kn:
																								continue

																		lowercase_	:     Dict													=       copy.deepcopy(__SCREAMING_SNAKE_CASE							)
																		lowercase_	:     Dict													=       kn
																		lowercase_	:     List[Any]													=       n

																		lowercase_	:     str													=       0

																		for k in _tmp[:-1]:
																								lowercase_	:     Tuple													=       _tmp[_tmp.index(__SCREAMING_SNAKE_CASE							) + 1]
																								for i in dict_of_neighbours[k]:
																														if i[0] == next_node:
																																				lowercase_	:     Optional[Any]													=       distance + int(i[1]							)
																		_tmp.append(__SCREAMING_SNAKE_CASE							)

																		if _tmp not in neighborhood_of_solution:
																								neighborhood_of_solution.append(_tmp							)

						lowercase_	:     Union[str, Any]													=       len(neighborhood_of_solution[0]							) - 1

						neighborhood_of_solution.sort(key=lambda __SCREAMING_SNAKE_CASE							: x[index_of_last_item_in_the_list]							)
						return neighborhood_of_solution
def 					snake_case_		(				__SCREAMING_SNAKE_CASE					: Tuple      ,      __SCREAMING_SNAKE_CASE					: List[Any]      ,      __SCREAMING_SNAKE_CASE					: Optional[int]      ,      __SCREAMING_SNAKE_CASE					: Optional[int]      ,      __SCREAMING_SNAKE_CASE					: Optional[Any]							):



						"""simple docstring"""





						lowercase_	:     Optional[int]													=       1
						lowercase_	:     List[str]													=       first_solution
						lowercase_	:     Dict													=       []
						lowercase_	:     List[str]													=       distance_of_first_solution
						lowercase_	:     Optional[Any]													=       solution

						while count <= iters:
												lowercase_	:     int													=       find_neighborhood(__SCREAMING_SNAKE_CASE      ,      __SCREAMING_SNAKE_CASE							)
												lowercase_	:     Any													=       0
												lowercase_	:     Dict													=       neighborhood[index_of_best_solution]
												lowercase_	:     Optional[Any]													=       len(__SCREAMING_SNAKE_CASE							) - 1

												lowercase_	:     Tuple													=       False
												while not found:
																		lowercase_	:     Optional[int]													=       0
																		while i < len(__SCREAMING_SNAKE_CASE							):
																								if best_solution[i] != solution[i]:
																														lowercase_	:     Tuple													=       best_solution[i]
																														lowercase_	:     Optional[int]													=       solution[i]
																														break
																								lowercase_	:     int													=       i + 1

																		if [first_exchange_node, second_exchange_node] not in tabu_list and [
																		    second_exchange_node,
																		    first_exchange_node,
																		] not in tabu_list:
																								tabu_list.append([first_exchange_node, second_exchange_node]							)
																								lowercase_	:     Tuple													=       True
																								lowercase_	:     Optional[int]													=       best_solution[:-1]
																								lowercase_	:     Optional[Any]													=       neighborhood[index_of_best_solution][best_cost_index]
																								if cost < best_cost:
																														lowercase_	:     Optional[Any]													=       cost
																														lowercase_	:     int													=       solution
																		else:
																								lowercase_	:     Any													=       index_of_best_solution + 1
																								lowercase_	:     Any													=       neighborhood[index_of_best_solution]

												if len(__SCREAMING_SNAKE_CASE							) >= size:
																		tabu_list.pop(0							)

												lowercase_	:     List[Any]													=       count + 1

						return best_solution_ever, best_cost
def 					snake_case_		(				__SCREAMING_SNAKE_CASE					: List[str]=None							):



						"""simple docstring"""





						lowercase_	:     Any													=       generate_neighbours(args.File							)

						lowercase_						, lowercase_	:     Union[str, Any]													=       generate_first_solution(
						    args.File      ,      __SCREAMING_SNAKE_CASE							)

						lowercase_						, lowercase_	:     Optional[int]													=       tabu_search(
						    __SCREAMING_SNAKE_CASE      ,      __SCREAMING_SNAKE_CASE      ,      __SCREAMING_SNAKE_CASE      ,      args.Iterations      ,      args.Size      ,      )

						print(F'''Best solution: {best_sol}, with total distance: {best_cost}.'''							)


if __name__ == "__main__":
							_lowercase :  Any    							=       argparse.ArgumentParser(description="Tabu Search")
							parser.add_argument(
							    "-f",
							    "--File",
							    type=str,
							    help="Path to the file containing the data",
							    required=True,
							)
							parser.add_argument(
							    "-i",
							    "--Iterations",
							    type=int,
							    help="How many iterations the algorithm should perform",
							    required=True,
							)
							parser.add_argument(
							    "-s", "--Size", type=int, help="Size of the tabu list", required=True
							)

							# Pass the arguments to main method
							main(parser.parse_args())



