"""simple docstring"""





import argparse
import copy





def 				a_     (      _lowerCAmelCase  : Optional[int]     ):





       '''simple docstring'''

       lowercase__			:		int       =	{}

       with open(_lowerCAmelCase     ) as f:
              for line in f:
                     if line.split()[0] not in dict_of_neighbours:
                            lowercase__			:		str       =	[]
                            _list.append([line.split()[1], line.split()[2]]     )
                            lowercase__			:		Dict       =	_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__			:		Dict       =	[]
                            _list.append([line.split()[0], line.split()[2]]     )
                            lowercase__			:		Optional[int]       =	_list
                     else:
                            dict_of_neighbours[line.split()[1]].append(
                                [line.split()[0], line.split()[2]]     )

       return dict_of_neighbours





def 				a_     (      _lowerCAmelCase  : List[str]   , _lowerCAmelCase  : Optional[Any]     ):





       '''simple docstring'''

       with open(_lowerCAmelCase     ) as f:
              lowercase__			:		Union[str, Any]       =	f.read(1     )
       lowercase__			:		Union[str, Any]       =	start_node

       lowercase__			:		int       =	[]

       lowercase__			:		int       =	start_node

       lowercase__			:		Optional[Any]       =	0
       while visiting not in first_solution:
              lowercase__			:		str       =	1_0000
              for k in dict_of_neighbours[visiting]:
                     if int(k[1]     ) < int(_lowerCAmelCase     ) and k[0] not in first_solution:
                            lowercase__			:		Any       =	k[1]
                            lowercase__			:		Union[str, Any]       =	k[0]

              first_solution.append(_lowerCAmelCase     )
              lowercase__			:		Dict       =	distance_of_first_solution + int(_lowerCAmelCase     )
              lowercase__			:		Tuple       =	best_node

       first_solution.append(_lowerCAmelCase     )

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

       lowercase__			:		str       =	(
           distance_of_first_solution
           + int(dict_of_neighbours[first_solution[-2]][position][1]     )
           - 1_0000
       )
       return first_solution, distance_of_first_solution





def 				a_     (      _lowerCAmelCase  : Union[str, Any]   , _lowerCAmelCase  : int     ):





       '''simple docstring'''

       lowercase__			:		Optional[int]       =	[]

       for n in solution[1:-1]:
              lowercase__			:		int       =	solution.index(_lowerCAmelCase     )
              for kn in solution[1:-1]:
                     lowercase__			:		List[Any]       =	solution.index(_lowerCAmelCase     )
                     if n == kn:
                            continue

                     lowercase__			:		Optional[Any]       =	copy.deepcopy(_lowerCAmelCase     )
                     lowercase__			:		Tuple       =	kn
                     lowercase__			:		Dict       =	n

                     lowercase__			:		List[str]       =	0

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

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

       lowercase__			:		Dict       =	len(neighborhood_of_solution[0]     ) - 1

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





def 				a_     (      _lowerCAmelCase  : List[Any]   , _lowerCAmelCase  : Union[str, Any]   , _lowerCAmelCase  : List[Any]   , _lowerCAmelCase  : List[str]   , _lowerCAmelCase  : Tuple     ):





       '''simple docstring'''

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

       while count <= iters:
              lowercase__			:		Any       =	find_neighborhood(_lowerCAmelCase   , _lowerCAmelCase     )
              lowercase__			:		Any       =	0
              lowercase__			:		int       =	neighborhood[index_of_best_solution]
              lowercase__			:		List[Any]       =	len(_lowerCAmelCase     ) - 1

              lowercase__			:		List[str]       =	False
              while not found:
                     lowercase__			:		Optional[Any]       =	0
                     while i < len(_lowerCAmelCase     ):
                            if best_solution[i] != solution[i]:
                                   lowercase__			:		Union[str, Any]       =	best_solution[i]
                                   lowercase__			:		Tuple       =	solution[i]
                                   break
                            lowercase__			:		str       =	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__			:		List[str]       =	True
                            lowercase__			:		List[str]       =	best_solution[:-1]
                            lowercase__			:		List[str]       =	neighborhood[index_of_best_solution][best_cost_index]
                            if cost < best_cost:
                                   lowercase__			:		List[Any]       =	cost
                                   lowercase__			:		Tuple       =	solution
                     else:
                            lowercase__			:		Tuple       =	index_of_best_solution + 1
                            lowercase__			:		Any       =	neighborhood[index_of_best_solution]

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

              lowercase__			:		List[Any]       =	count + 1

       return best_solution_ever, best_cost





def 				a_     (      _lowerCAmelCase  : Tuple=None     ):





       '''simple docstring'''

       lowercase__			:		Tuple       =	generate_neighbours(args.File     )

       lowercase__    ,      lowercase__			:		Optional[int]       =	generate_first_solution(
           args.File   , _lowerCAmelCase     )

       lowercase__    ,      lowercase__			:		Optional[int]       =	tabu_search(
           _lowerCAmelCase   , _lowerCAmelCase   , _lowerCAmelCase   , args.Iterations   , args.Size   , )

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


if __name__ == "__main__":
       _UpperCamelCase   :						Optional[int]      =    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())




'''simple docstring'''



import unittest

from transformers import (
    MODEL_FOR_OBJECT_DETECTION_MAPPING,
    AutoFeatureExtractor,
    AutoModelForObjectDetection,
    ObjectDetectionPipeline,
    is_vision_available,
    pipeline,
)
from transformers.testing_utils import (
    is_pipeline_test,
    nested_simplify,
    require_pytesseract,
    require_tf,
    require_timm,
    require_torch,
    require_vision,
    slow,
)

from .test_pipelines_common import ANY


if is_vision_available():
  from PIL import Image
else:







  class 						lowerCAmelCase__   :



   """simple docstring"""



   @staticmethod
   def       UpperCAmelCase__		(		*__SCREAMING_SNAKE_CASE					:       Tuple					,							**__SCREAMING_SNAKE_CASE					:       Union[str, Any]			)  -> List[str]:


        """simple docstring"""




        pass







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



 """simple docstring"""



 lowerCAmelCase__  					=      MODEL_FOR_OBJECT_DETECTION_MAPPING
 def       UpperCAmelCase__		(		self					:       List[Any]					,							__SCREAMING_SNAKE_CASE					:       Any					,							__SCREAMING_SNAKE_CASE					:       int					,							__SCREAMING_SNAKE_CASE					:       Tuple			)  -> str:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE     =      ObjectDetectionPipeline(model=__SCREAMING_SNAKE_CASE					,							image_processor=__SCREAMING_SNAKE_CASE			)
      return object_detector, ["./tests/fixtures/tests_samples/COCO/000000039769.png"]
 def       UpperCAmelCase__		(		self					:       Optional[int]					,							__SCREAMING_SNAKE_CASE					:       Dict					,							__SCREAMING_SNAKE_CASE					:       List[Any]			)  -> Optional[int]:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE     =      object_detector("""./tests/fixtures/tests_samples/COCO/000000039769.png"""					,							threshold=0.0			)

      self.assertGreater(len(__SCREAMING_SNAKE_CASE			)					,							0			)
      for detected_object in outputs:
           self.assertEqual(
               __SCREAMING_SNAKE_CASE					,							{
                   """score""": ANY(__SCREAMING_SNAKE_CASE			),
                   """label""": ANY(__SCREAMING_SNAKE_CASE			),
                   """box""": {"""xmin""": ANY(__SCREAMING_SNAKE_CASE			), """ymin""": ANY(__SCREAMING_SNAKE_CASE			), """xmax""": ANY(__SCREAMING_SNAKE_CASE			), """ymax""": ANY(__SCREAMING_SNAKE_CASE			)},
               }					,							)

      import datasets

      __SCREAMING_SNAKE_CASE     =      datasets.load_dataset("""hf-internal-testing/fixtures_image_utils"""					,							"""image"""					,							split="""test"""			)

      __SCREAMING_SNAKE_CASE     =      [
          Image.open("""./tests/fixtures/tests_samples/COCO/000000039769.png"""			),
          """http://images.cocodataset.org/val2017/000000039769.jpg""",
          # RGBA
          dataset[0]["""file"""],
          # LA
          dataset[1]["""file"""],
          # L
          dataset[2]["""file"""],
      ]
      __SCREAMING_SNAKE_CASE     =      object_detector(__SCREAMING_SNAKE_CASE					,							threshold=0.0			)

      self.assertEqual(len(__SCREAMING_SNAKE_CASE			)					,							len(__SCREAMING_SNAKE_CASE			)			)
      for outputs in batch_outputs:
           self.assertGreater(len(__SCREAMING_SNAKE_CASE			)					,							0			)
           for detected_object in outputs:
                self.assertEqual(
                    __SCREAMING_SNAKE_CASE					,							{
                        """score""": ANY(__SCREAMING_SNAKE_CASE			),
                        """label""": ANY(__SCREAMING_SNAKE_CASE			),
                        """box""": {"""xmin""": ANY(__SCREAMING_SNAKE_CASE			), """ymin""": ANY(__SCREAMING_SNAKE_CASE			), """xmax""": ANY(__SCREAMING_SNAKE_CASE			), """ymax""": ANY(__SCREAMING_SNAKE_CASE			)},
                    }					,							)
 @require_tf
 @unittest.skip("""Object detection not implemented in TF"""			)
 def       UpperCAmelCase__		(		self					:       Union[str, Any]			)  -> str:


      """simple docstring"""




      pass
 @require_torch
 def       UpperCAmelCase__		(		self					:       str			)  -> Optional[Any]:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE     =      """hf-internal-testing/tiny-detr-mobilenetsv3"""

      __SCREAMING_SNAKE_CASE     =      AutoModelForObjectDetection.from_pretrained(__SCREAMING_SNAKE_CASE			)
      __SCREAMING_SNAKE_CASE     =      AutoFeatureExtractor.from_pretrained(__SCREAMING_SNAKE_CASE			)
      __SCREAMING_SNAKE_CASE     =      ObjectDetectionPipeline(model=__SCREAMING_SNAKE_CASE					,							feature_extractor=__SCREAMING_SNAKE_CASE			)

      __SCREAMING_SNAKE_CASE     =      object_detector("""http://images.cocodataset.org/val2017/000000039769.jpg"""					,							threshold=0.0			)

      self.assertEqual(
          nested_simplify(__SCREAMING_SNAKE_CASE					,							decimals=4			)					,							[
              {"""score""": 0.3376, """label""": """LABEL_0""", """box""": {"""xmin""": 159, """ymin""": 120, """xmax""": 480, """ymax""": 359}},
              {"""score""": 0.3376, """label""": """LABEL_0""", """box""": {"""xmin""": 159, """ymin""": 120, """xmax""": 480, """ymax""": 359}},
          ]					,							)

      __SCREAMING_SNAKE_CASE     =      object_detector(
          [
              """http://images.cocodataset.org/val2017/000000039769.jpg""",
              """http://images.cocodataset.org/val2017/000000039769.jpg""",
          ]					,							threshold=0.0					,							)

      self.assertEqual(
          nested_simplify(__SCREAMING_SNAKE_CASE					,							decimals=4			)					,							[
              [
                  {"""score""": 0.3376, """label""": """LABEL_0""", """box""": {"""xmin""": 159, """ymin""": 120, """xmax""": 480, """ymax""": 359}},
                  {"""score""": 0.3376, """label""": """LABEL_0""", """box""": {"""xmin""": 159, """ymin""": 120, """xmax""": 480, """ymax""": 359}},
              ],
              [
                  {"""score""": 0.3376, """label""": """LABEL_0""", """box""": {"""xmin""": 159, """ymin""": 120, """xmax""": 480, """ymax""": 359}},
                  {"""score""": 0.3376, """label""": """LABEL_0""", """box""": {"""xmin""": 159, """ymin""": 120, """xmax""": 480, """ymax""": 359}},
              ],
          ]					,							)
 @require_torch
 @slow
 def       UpperCAmelCase__		(		self					:       Optional[int]			)  -> Any:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE     =      """facebook/detr-resnet-50"""

      __SCREAMING_SNAKE_CASE     =      AutoModelForObjectDetection.from_pretrained(__SCREAMING_SNAKE_CASE			)
      __SCREAMING_SNAKE_CASE     =      AutoFeatureExtractor.from_pretrained(__SCREAMING_SNAKE_CASE			)
      __SCREAMING_SNAKE_CASE     =      ObjectDetectionPipeline(model=__SCREAMING_SNAKE_CASE					,							feature_extractor=__SCREAMING_SNAKE_CASE			)

      __SCREAMING_SNAKE_CASE     =      object_detector("""http://images.cocodataset.org/val2017/000000039769.jpg"""			)
      self.assertEqual(
          nested_simplify(__SCREAMING_SNAKE_CASE					,							decimals=4			)					,							[
              {"""score""": 0.9982, """label""": """remote""", """box""": {"""xmin""": 40, """ymin""": 70, """xmax""": 175, """ymax""": 117}},
              {"""score""": 0.9960, """label""": """remote""", """box""": {"""xmin""": 333, """ymin""": 72, """xmax""": 368, """ymax""": 187}},
              {"""score""": 0.9955, """label""": """couch""", """box""": {"""xmin""": 0, """ymin""": 1, """xmax""": 639, """ymax""": 473}},
              {"""score""": 0.9988, """label""": """cat""", """box""": {"""xmin""": 13, """ymin""": 52, """xmax""": 314, """ymax""": 470}},
              {"""score""": 0.9987, """label""": """cat""", """box""": {"""xmin""": 345, """ymin""": 23, """xmax""": 640, """ymax""": 368}},
          ]					,							)

      __SCREAMING_SNAKE_CASE     =      object_detector(
          [
              """http://images.cocodataset.org/val2017/000000039769.jpg""",
              """http://images.cocodataset.org/val2017/000000039769.jpg""",
          ]			)
      self.assertEqual(
          nested_simplify(__SCREAMING_SNAKE_CASE					,							decimals=4			)					,							[
              [
                  {"""score""": 0.9982, """label""": """remote""", """box""": {"""xmin""": 40, """ymin""": 70, """xmax""": 175, """ymax""": 117}},
                  {"""score""": 0.9960, """label""": """remote""", """box""": {"""xmin""": 333, """ymin""": 72, """xmax""": 368, """ymax""": 187}},
                  {"""score""": 0.9955, """label""": """couch""", """box""": {"""xmin""": 0, """ymin""": 1, """xmax""": 639, """ymax""": 473}},
                  {"""score""": 0.9988, """label""": """cat""", """box""": {"""xmin""": 13, """ymin""": 52, """xmax""": 314, """ymax""": 470}},
                  {"""score""": 0.9987, """label""": """cat""", """box""": {"""xmin""": 345, """ymin""": 23, """xmax""": 640, """ymax""": 368}},
              ],
              [
                  {"""score""": 0.9982, """label""": """remote""", """box""": {"""xmin""": 40, """ymin""": 70, """xmax""": 175, """ymax""": 117}},
                  {"""score""": 0.9960, """label""": """remote""", """box""": {"""xmin""": 333, """ymin""": 72, """xmax""": 368, """ymax""": 187}},
                  {"""score""": 0.9955, """label""": """couch""", """box""": {"""xmin""": 0, """ymin""": 1, """xmax""": 639, """ymax""": 473}},
                  {"""score""": 0.9988, """label""": """cat""", """box""": {"""xmin""": 13, """ymin""": 52, """xmax""": 314, """ymax""": 470}},
                  {"""score""": 0.9987, """label""": """cat""", """box""": {"""xmin""": 345, """ymin""": 23, """xmax""": 640, """ymax""": 368}},
              ],
          ]					,							)
 @require_torch
 @slow
 def       UpperCAmelCase__		(		self					:       List[Any]			)  -> Dict:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE     =      """facebook/detr-resnet-50"""

      __SCREAMING_SNAKE_CASE     =      pipeline("""object-detection"""					,							model=__SCREAMING_SNAKE_CASE			)

      __SCREAMING_SNAKE_CASE     =      object_detector("""http://images.cocodataset.org/val2017/000000039769.jpg"""			)
      self.assertEqual(
          nested_simplify(__SCREAMING_SNAKE_CASE					,							decimals=4			)					,							[
              {"""score""": 0.9982, """label""": """remote""", """box""": {"""xmin""": 40, """ymin""": 70, """xmax""": 175, """ymax""": 117}},
              {"""score""": 0.9960, """label""": """remote""", """box""": {"""xmin""": 333, """ymin""": 72, """xmax""": 368, """ymax""": 187}},
              {"""score""": 0.9955, """label""": """couch""", """box""": {"""xmin""": 0, """ymin""": 1, """xmax""": 639, """ymax""": 473}},
              {"""score""": 0.9988, """label""": """cat""", """box""": {"""xmin""": 13, """ymin""": 52, """xmax""": 314, """ymax""": 470}},
              {"""score""": 0.9987, """label""": """cat""", """box""": {"""xmin""": 345, """ymin""": 23, """xmax""": 640, """ymax""": 368}},
          ]					,							)

      __SCREAMING_SNAKE_CASE     =      object_detector(
          [
              """http://images.cocodataset.org/val2017/000000039769.jpg""",
              """http://images.cocodataset.org/val2017/000000039769.jpg""",
          ]			)
      self.assertEqual(
          nested_simplify(__SCREAMING_SNAKE_CASE					,							decimals=4			)					,							[
              [
                  {"""score""": 0.9982, """label""": """remote""", """box""": {"""xmin""": 40, """ymin""": 70, """xmax""": 175, """ymax""": 117}},
                  {"""score""": 0.9960, """label""": """remote""", """box""": {"""xmin""": 333, """ymin""": 72, """xmax""": 368, """ymax""": 187}},
                  {"""score""": 0.9955, """label""": """couch""", """box""": {"""xmin""": 0, """ymin""": 1, """xmax""": 639, """ymax""": 473}},
                  {"""score""": 0.9988, """label""": """cat""", """box""": {"""xmin""": 13, """ymin""": 52, """xmax""": 314, """ymax""": 470}},
                  {"""score""": 0.9987, """label""": """cat""", """box""": {"""xmin""": 345, """ymin""": 23, """xmax""": 640, """ymax""": 368}},
              ],
              [
                  {"""score""": 0.9982, """label""": """remote""", """box""": {"""xmin""": 40, """ymin""": 70, """xmax""": 175, """ymax""": 117}},
                  {"""score""": 0.9960, """label""": """remote""", """box""": {"""xmin""": 333, """ymin""": 72, """xmax""": 368, """ymax""": 187}},
                  {"""score""": 0.9955, """label""": """couch""", """box""": {"""xmin""": 0, """ymin""": 1, """xmax""": 639, """ymax""": 473}},
                  {"""score""": 0.9988, """label""": """cat""", """box""": {"""xmin""": 13, """ymin""": 52, """xmax""": 314, """ymax""": 470}},
                  {"""score""": 0.9987, """label""": """cat""", """box""": {"""xmin""": 345, """ymin""": 23, """xmax""": 640, """ymax""": 368}},
              ],
          ]					,							)
 @require_torch
 @slow
 def       UpperCAmelCase__		(		self					:       Dict			)  -> Optional[Any]:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE     =      0.9985
      __SCREAMING_SNAKE_CASE     =      """facebook/detr-resnet-50"""

      __SCREAMING_SNAKE_CASE     =      pipeline("""object-detection"""					,							model=__SCREAMING_SNAKE_CASE			)

      __SCREAMING_SNAKE_CASE     =      object_detector("""http://images.cocodataset.org/val2017/000000039769.jpg"""					,							threshold=__SCREAMING_SNAKE_CASE			)
      self.assertEqual(
          nested_simplify(__SCREAMING_SNAKE_CASE					,							decimals=4			)					,							[
              {"""score""": 0.9988, """label""": """cat""", """box""": {"""xmin""": 13, """ymin""": 52, """xmax""": 314, """ymax""": 470}},
              {"""score""": 0.9987, """label""": """cat""", """box""": {"""xmin""": 345, """ymin""": 23, """xmax""": 640, """ymax""": 368}},
          ]					,							)


 @require_torch
 @require_pytesseract
 @slow
 def       UpperCAmelCase__		(		self					:       int			)  -> Optional[Any]:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE     =      """Narsil/layoutlmv3-finetuned-funsd"""
      __SCREAMING_SNAKE_CASE     =      0.9993

      __SCREAMING_SNAKE_CASE     =      pipeline("""object-detection"""					,							model=__SCREAMING_SNAKE_CASE					,							threshold=__SCREAMING_SNAKE_CASE			)

      __SCREAMING_SNAKE_CASE     =      object_detector(
          """https://huggingface.co/spaces/impira/docquery/resolve/2359223c1837a7587402bda0f2643382a6eefeab/invoice.png"""			)
      self.assertEqual(
          nested_simplify(__SCREAMING_SNAKE_CASE					,							decimals=4			)					,							[
              {"""score""": 0.9993, """label""": """I-ANSWER""", """box""": {"""xmin""": 294, """ymin""": 254, """xmax""": 343, """ymax""": 264}},
              {"""score""": 0.9993, """label""": """I-ANSWER""", """box""": {"""xmin""": 294, """ymin""": 254, """xmax""": 343, """ymax""": 264}},
          ]					,							)






