






import argparse
import copy






def     _snake_case    (__lowercase):
   UpperCamelCase_									=     {}

   with open(__lowercase) as f:
      for line in f:
         if line.split()[0] not in dict_of_neighbours:
            UpperCamelCase_									=     []
            _list.append([line.split()[1], line.split()[2]])
            UpperCamelCase_									=     _list
         else:
            dict_of_neighbours[line.split()[0]].append(
                [line.split()[1], line.split()[2]])
         if line.split()[1] not in dict_of_neighbours:
            UpperCamelCase_									=     []
            _list.append([line.split()[0], line.split()[2]])
            UpperCamelCase_									=     _list
         else:
            dict_of_neighbours[line.split()[1]].append(
                [line.split()[0], line.split()[2]])

   return dict_of_neighbours






def     _snake_case    (__lowercase    ,      __lowercase):

   with open(__lowercase) as f:
      UpperCamelCase_									=     f.read(1)
   UpperCamelCase_									=     start_node

   UpperCamelCase_									=     []

   UpperCamelCase_									=     start_node

   UpperCamelCase_									=     0
   while visiting not in first_solution:
      UpperCamelCase_									=     10000
      for k in dict_of_neighbours[visiting]:
         if int(k[1]) < int(__lowercase) and k[0] not in first_solution:
            UpperCamelCase_									=     k[1]
            UpperCamelCase_									=     k[0]

      first_solution.append(__lowercase)
      UpperCamelCase_									=     distance_of_first_solution + int(__lowercase)
      UpperCamelCase_									=     best_node

   first_solution.append(__lowercase)

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

   UpperCamelCase_									=     (
       distance_of_first_solution
       + int(dict_of_neighbours[first_solution[-2]][position][1])
       - 10000
   )
   return first_solution, distance_of_first_solution






def     _snake_case    (__lowercase    ,      __lowercase):
   UpperCamelCase_									=     []

   for n in solution[1:-1]:
      UpperCamelCase_									=     solution.index(__lowercase)
      for kn in solution[1:-1]:
         UpperCamelCase_									=     solution.index(__lowercase)
         if n == kn:
            continue

         UpperCamelCase_									=     copy.deepcopy(__lowercase)
         UpperCamelCase_									=     kn
         UpperCamelCase_									=     n

         UpperCamelCase_									=     0

         for k in _tmp[:-1]:
            UpperCamelCase_									=     _tmp[_tmp.index(__lowercase) + 1]
            for i in dict_of_neighbours[k]:
               if i[0] == next_node:
                  UpperCamelCase_									=     distance + int(i[1])
         _tmp.append(__lowercase)

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

   UpperCamelCase_									=     len(neighborhood_of_solution[0]) - 1

   neighborhood_of_solution.sort(key=lambda __lowercase: x[index_of_last_item_in_the_list])
   return neighborhood_of_solution






def     _snake_case    (__lowercase    ,      __lowercase    ,      __lowercase    ,      __lowercase    ,      __lowercase):
   UpperCamelCase_									=     1
   UpperCamelCase_									=     first_solution
   UpperCamelCase_									=     []
   UpperCamelCase_									=     distance_of_first_solution
   UpperCamelCase_									=     solution

   while count <= iters:
      UpperCamelCase_									=     find_neighborhood(__lowercase    ,      __lowercase)
      UpperCamelCase_									=     0
      UpperCamelCase_									=     neighborhood[index_of_best_solution]
      UpperCamelCase_									=     len(__lowercase) - 1

      UpperCamelCase_									=     False
      while not found:
         UpperCamelCase_									=     0
         while i < len(__lowercase):
            if best_solution[i] != solution[i]:
               UpperCamelCase_									=     best_solution[i]
               UpperCamelCase_									=     solution[i]
               break
            UpperCamelCase_									=     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])
            UpperCamelCase_									=     True
            UpperCamelCase_									=     best_solution[:-1]
            UpperCamelCase_									=     neighborhood[index_of_best_solution][best_cost_index]
            if cost < best_cost:
               UpperCamelCase_									=     cost
               UpperCamelCase_									=     solution
         else:
            UpperCamelCase_									=     index_of_best_solution + 1
            UpperCamelCase_									=     neighborhood[index_of_best_solution]

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

      UpperCamelCase_									=     count + 1

   return best_solution_ever, best_cost






def     _snake_case    (__lowercase=None):
   UpperCamelCase_									=     generate_neighbours(args.File)

   UpperCamelCase_		,      UpperCamelCase_									=     generate_first_solution(
       args.File    ,      __lowercase)

   UpperCamelCase_		,      UpperCamelCase_									=     tabu_search(
       __lowercase    ,      __lowercase    ,      __lowercase    ,      args.Iterations    ,      args.Size    ,      )

   print(f"""Best solution: {best_sol}, with total distance: {best_cost}.""")


if __name__ == "__main__":
 snake_case__      :	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())













import inspect
import unittest

from transformers import ViTMSNConfig
from transformers.testing_utils import require_torch, require_vision, slow, torch_device
from transformers.utils import cached_property, is_torch_available, is_vision_available

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 torch import nn

 from transformers import ViTMSNForImageClassification, ViTMSNModel
 from transformers.models.vit_msn.modeling_vit_msn import VIT_MSN_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
 from PIL import Image

 from transformers import ViTImageProcessor


class 						_a       :






  """simple docstring"""





  def __init__(     self		,		_UpperCAmelCase		,		_UpperCAmelCase=13		,		_UpperCAmelCase=30		,		_UpperCAmelCase=2		,		_UpperCAmelCase=3		,		_UpperCAmelCase=True		,		_UpperCAmelCase=True		,		_UpperCAmelCase=32		,		_UpperCAmelCase=5		,		_UpperCAmelCase=4		,		_UpperCAmelCase=37		,		_UpperCAmelCase="gelu"		,		_UpperCAmelCase=0.1		,		_UpperCAmelCase=0.1		,		_UpperCAmelCase=10		,		_UpperCAmelCase=0.0_2		,		_UpperCAmelCase=None		,		)			-> Optional[Any]:
     UpperCamelCase_									=     parent
     UpperCamelCase_									=     batch_size
     UpperCamelCase_									=     image_size
     UpperCamelCase_									=     patch_size
     UpperCamelCase_									=     num_channels
     UpperCamelCase_									=     is_training
     UpperCamelCase_									=     use_labels
     UpperCamelCase_									=     hidden_size
     UpperCamelCase_									=     num_hidden_layers
     UpperCamelCase_									=     num_attention_heads
     UpperCamelCase_									=     intermediate_size
     UpperCamelCase_									=     hidden_act
     UpperCamelCase_									=     hidden_dropout_prob
     UpperCamelCase_									=     attention_probs_dropout_prob
     UpperCamelCase_									=     type_sequence_label_size
     UpperCamelCase_									=     initializer_range
     UpperCamelCase_									=     scope

     # in ViT MSN, the seq length equals the number of patches + 1 (we add 1 for the [CLS] token)
     UpperCamelCase_									=     (image_size // patch_size) ** 2
     UpperCamelCase_									=     num_patches + 1




  def    _UpperCAmelCase     (     self )			-> Tuple:
     UpperCamelCase_									=     floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size] )

     UpperCamelCase_									=     None
     if self.use_labels:
        UpperCamelCase_									=     ids_tensor([self.batch_size]		,		self.type_sequence_label_size )

     UpperCamelCase_									=     self.get_config()

     return config, pixel_values, labels




  def    _UpperCAmelCase     (     self )			-> int:
     return ViTMSNConfig(
         image_size=self.image_size		,		patch_size=self.patch_size		,		num_channels=self.num_channels		,		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		,		initializer_range=self.initializer_range		,		)




  def    _UpperCAmelCase     (     self		,		_UpperCAmelCase		,		_UpperCAmelCase		,		_UpperCAmelCase )			-> Any:
     UpperCamelCase_									=     ViTMSNModel(config=_UpperCAmelCase )
     model.to(_UpperCAmelCase )
     model.eval()
     UpperCamelCase_									=     model(_UpperCAmelCase )
     self.parent.assertEqual(result.last_hidden_state.shape		,		(self.batch_size, self.seq_length, self.hidden_size) )




  def    _UpperCAmelCase     (     self		,		_UpperCAmelCase		,		_UpperCAmelCase		,		_UpperCAmelCase )			-> str:
     UpperCamelCase_									=     self.type_sequence_label_size
     UpperCamelCase_									=     ViTMSNForImageClassification(_UpperCAmelCase )
     model.to(_UpperCAmelCase )
     model.eval()
     UpperCamelCase_									=     model(_UpperCAmelCase		,		labels=_UpperCAmelCase )
     print('Pixel and labels shape: {pixel_values.shape}, {labels.shape}' )
     print('Labels: {labels}' )
     self.parent.assertEqual(result.logits.shape		,		(self.batch_size, self.type_sequence_label_size) )

     # test greyscale images
     UpperCamelCase_									=     1
     UpperCamelCase_									=     ViTMSNForImageClassification(_UpperCAmelCase )
     model.to(_UpperCAmelCase )
     model.eval()

     UpperCamelCase_									=     floats_tensor([self.batch_size, 1, self.image_size, self.image_size] )
     UpperCamelCase_									=     model(_UpperCAmelCase )
     self.parent.assertEqual(result.logits.shape		,		(self.batch_size, self.type_sequence_label_size) )




  def    _UpperCAmelCase     (     self )			-> Dict:
     UpperCamelCase_									=     self.prepare_config_and_inputs()
     UpperCamelCase_		,      UpperCamelCase_		,      UpperCamelCase_									=     config_and_inputs
     UpperCamelCase_									=     {'pixel_values': pixel_values}
     return config, inputs_dict




@require_torch
class 						_a       (  UpperCAmelCase__						,       UpperCAmelCase__						,       unittest.TestCase    ):






  """simple docstring"""





  A_						=   (ViTMSNModel, ViTMSNForImageClassification) if is_torch_available() else ()
  A_						=   (
      {"""feature-extraction""": ViTMSNModel, """image-classification""": ViTMSNForImageClassification}
      if is_torch_available()
      else {}
  )

  A_						=   False
  A_						=   False
  A_						=   False
  A_						=   False




  def    _UpperCAmelCase     (     self )			-> Dict:
     UpperCamelCase_									=     ViTMSNModelTester(self )
     UpperCamelCase_									=     ConfigTester(self		,		config_class=_UpperCAmelCase		,		has_text_modality=_UpperCAmelCase		,		hidden_size=37 )




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




  @unittest.skip(reason='ViTMSN does not use inputs_embeds' )
  def    _UpperCAmelCase     (     self )			-> Optional[Any]:
     pass




  def    _UpperCAmelCase     (     self )			-> List[str]:
     UpperCamelCase_		,      UpperCamelCase_									=     self.model_tester.prepare_config_and_inputs_for_common()

     for model_class in self.all_model_classes:
        UpperCamelCase_									=     model_class(_UpperCAmelCase )
        self.assertIsInstance(model.get_input_embeddings()		,		(nn.Module) )
        UpperCamelCase_									=     model.get_output_embeddings()
        self.assertTrue(x is None or isinstance(_UpperCAmelCase		,		nn.Linear ) )




  def    _UpperCAmelCase     (     self )			-> List[str]:
     UpperCamelCase_		,      UpperCamelCase_									=     self.model_tester.prepare_config_and_inputs_for_common()

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

        UpperCamelCase_									=     ['pixel_values']
        self.assertListEqual(arg_names[:1]		,		_UpperCAmelCase )




  def    _UpperCAmelCase     (     self )			-> Any:
     UpperCamelCase_									=     self.model_tester.prepare_config_and_inputs()
     self.model_tester.create_and_check_model(*_UpperCAmelCase )




  def    _UpperCAmelCase     (     self )			-> List[Any]:
     UpperCamelCase_									=     self.model_tester.prepare_config_and_inputs()
     self.model_tester.create_and_check_for_image_classification(*_UpperCAmelCase )




  @slow
  def    _UpperCAmelCase     (     self )			-> Dict:
     for model_name in VIT_MSN_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
        UpperCamelCase_									=     ViTMSNModel.from_pretrained(_UpperCAmelCase )
        self.assertIsNotNone(_UpperCAmelCase )






def     _snake_case    ():
   UpperCamelCase_									=     Image.open('./tests/fixtures/tests_samples/COCO/000000039769.png')
   return image


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






  """simple docstring"""





  @cached_property
  def    _UpperCAmelCase     (     self )			-> Union[str, Any]:
     return ViTImageProcessor.from_pretrained('facebook/vit-msn-small' ) if is_vision_available() else None




  @slow
  def    _UpperCAmelCase     (     self )			-> List[str]:
     torch.manual_seed(2 )
     UpperCamelCase_									=     ViTMSNForImageClassification.from_pretrained('facebook/vit-msn-small' ).to(_UpperCAmelCase )

     UpperCamelCase_									=     self.default_image_processor
     UpperCamelCase_									=     prepare_img()
     UpperCamelCase_									=     image_processor(images=_UpperCAmelCase		,		return_tensors='pt' ).to(_UpperCAmelCase )

     # forward pass
     with torch.no_grad():
        UpperCamelCase_									=     model(**_UpperCAmelCase )

     # verify the logits
     UpperCamelCase_									=     torch.Size((1, 1000) )
     self.assertEqual(outputs.logits.shape		,		_UpperCAmelCase )

     UpperCamelCase_									=     torch.tensor([-0.0_8_0_3, -0.4_4_5_4, -0.2_3_7_5] ).to(_UpperCAmelCase )

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





