
"""simple docstring"""
import argparse
import copy





def    _lowerCAmelCase    (     lowerCamelCase__							:							List[str]				)  ->    Optional[Any]:
  _SCREAMING_SNAKE_CASE   :				List[Any]							    = {}

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

  return dict_of_neighbours





def    _lowerCAmelCase    (     lowerCamelCase__							:							Tuple,						lowerCamelCase__							:							str				)  ->    int:

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

  _SCREAMING_SNAKE_CASE   :				Dict							    = []

  _SCREAMING_SNAKE_CASE   :				Dict							    = start_node

  _SCREAMING_SNAKE_CASE   :				Optional[int]							    = 0
  while visiting not in first_solution:
    _SCREAMING_SNAKE_CASE   :				int							    = 1_0_0_0_0
    for k in dict_of_neighbours[visiting]:
      if int(k[1]				) < int(lowerCamelCase__				) and k[0] not in first_solution:
        _SCREAMING_SNAKE_CASE   :				Optional[Any]							    = k[1]
        _SCREAMING_SNAKE_CASE   :				List[Any]							    = k[0]

    first_solution.append(lowerCamelCase__				)
    _SCREAMING_SNAKE_CASE   :				List[Any]							    = distance_of_first_solution + int(lowerCamelCase__				)
    _SCREAMING_SNAKE_CASE   :				Tuple							    = best_node

  first_solution.append(lowerCamelCase__				)

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

  _SCREAMING_SNAKE_CASE   :				Tuple							    = (
      distance_of_first_solution
      + int(dict_of_neighbours[first_solution[-2]][position][1]				)
      - 1_0_0_0_0
  )
  return first_solution, distance_of_first_solution





def    _lowerCAmelCase    (     lowerCamelCase__							:							Any,						lowerCamelCase__							:							List[Any]				)  ->    Tuple:
  _SCREAMING_SNAKE_CASE   :				List[Any]							    = []

  for n in solution[1:-1]:
    _SCREAMING_SNAKE_CASE   :				int							    = solution.index(lowerCamelCase__				)
    for kn in solution[1:-1]:
      _SCREAMING_SNAKE_CASE   :				Optional[Any]							    = solution.index(lowerCamelCase__				)
      if n == kn:
        continue

      _SCREAMING_SNAKE_CASE   :				Tuple							    = copy.deepcopy(lowerCamelCase__				)
      _SCREAMING_SNAKE_CASE   :				int							    = kn
      _SCREAMING_SNAKE_CASE   :				str							    = n

      _SCREAMING_SNAKE_CASE   :				int							    = 0

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

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

  _SCREAMING_SNAKE_CASE   :				Tuple							    = 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    _lowerCAmelCase    (     lowerCamelCase__							:							List[str],						lowerCamelCase__							:							str,						lowerCamelCase__							:							List[str],						lowerCamelCase__							:							str,						lowerCamelCase__							:							Union[str, Any]				)  ->    str:
  _SCREAMING_SNAKE_CASE   :				int							    = 1
  _SCREAMING_SNAKE_CASE   :				Any							    = first_solution
  _SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = []
  _SCREAMING_SNAKE_CASE   :				Optional[Any]							    = distance_of_first_solution
  _SCREAMING_SNAKE_CASE   :				List[Any]							    = solution

  while count <= iters:
    _SCREAMING_SNAKE_CASE   :				Dict							    = find_neighborhood(lowerCamelCase__,						lowerCamelCase__				)
    _SCREAMING_SNAKE_CASE   :				Optional[Any]							    = 0
    _SCREAMING_SNAKE_CASE   :				int							    = neighborhood[index_of_best_solution]
    _SCREAMING_SNAKE_CASE   :				List[str]							    = len(lowerCamelCase__				) - 1

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

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

    _SCREAMING_SNAKE_CASE   :				List[Any]							    = count + 1

  return best_solution_ever, best_cost





def    _lowerCAmelCase    (     lowerCamelCase__							:							List[Any]=None				)  ->    Dict:
  _SCREAMING_SNAKE_CASE   :				Any							    = generate_neighbours(args.File				)

  _SCREAMING_SNAKE_CASE    ,		_SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = generate_first_solution(
      args.File,						lowerCamelCase__				)

  _SCREAMING_SNAKE_CASE    ,		_SCREAMING_SNAKE_CASE   :				Tuple							    = tabu_search(
      lowerCamelCase__,						lowerCamelCase__,						lowerCamelCase__,						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())





"""simple docstring"""
def    _lowerCAmelCase    (     lowerCamelCase__							:							str,						lowerCamelCase__							:							str				)  ->    Union[str, Any]:
  print("\nThe shortest path matrix using Floyd Warshall algorithm\n"				)
  for i in range(lowerCamelCase__				):
    for j in range(lowerCamelCase__				):
      if dist[i][j] != float("inf"				):
        print(int(dist[i][j]				),						end="\t"				)
      else:
        print("INF",						end="\t"				)
    print()





def    _lowerCAmelCase    (     lowerCamelCase__							:							Dict,						lowerCamelCase__							:							Any				)  ->    List[str]:
  _SCREAMING_SNAKE_CASE   :				List[Any]							    = [[float("inf"				) for _ in range(lowerCamelCase__				)] for _ in range(lowerCamelCase__				)]

  for i in range(lowerCamelCase__				):
    for j in range(lowerCamelCase__				):
      _SCREAMING_SNAKE_CASE   :				List[Any]							    = graph[i][j]

      # check vertex k against all other vertices (i, j)
  for k in range(lowerCamelCase__				):
    # looping through rows of graph array
    for i in range(lowerCamelCase__				):
      # looping through columns of graph array
      for j in range(lowerCamelCase__				):
        if (
            dist[i][k] != float("inf"				)
            and dist[k][j] != float("inf"				)
            and dist[i][k] + dist[k][j] < dist[i][j]
        ):
          _SCREAMING_SNAKE_CASE   :				List[Any]							    = dist[i][k] + dist[k][j]

  _print_dist(lowerCamelCase__,						lowerCamelCase__				)
  return dist, v


if __name__ == "__main__":
      lowercase_       :						Tuple     					=	int(input('''Enter number of vertices: '''))
      lowercase_       :						List[Any]     					=	int(input('''Enter number of edges: '''))

      lowercase_       :						Optional[Any]     					=	[[float('''inf''') for i in range(v)] for j in range(v)]

      for i in range(v):
            lowercase_       :						Tuple     					=	0.0

            # src and dst are indices that must be within the array size graph[e][v]
            # failure to follow this will result in an error
      for i in range(e):
            print('''\nEdge ''', i + 1)
            lowercase_       :						str     					=	int(input('''Enter source:'''))
            lowercase_       :						Optional[Any]     					=	int(input('''Enter destination:'''))
            lowercase_       :						Union[str, Any]     					=	float(input('''Enter weight:'''))
            lowercase_       :						str     					=	weight

      floyd_warshall(graph, v)

      # Example Input
      # Enter number of vertices: 3
      # Enter number of edges: 2

      # # generated graph from vertex and edge inputs
      # [[inf, inf, inf], [inf, inf, inf], [inf, inf, inf]]
      # [[0.0, inf, inf], [inf, 0.0, inf], [inf, inf, 0.0]]

      # specify source, destination and weight for edge #1
      # Edge  1
      # Enter source:1
      # Enter destination:2
      # Enter weight:2

      # specify source, destination and weight for edge #2
      # Edge  2
      # Enter source:2
      # Enter destination:1
      # Enter weight:1

      # # Expected Output from the vertice, edge and src, dst, weight inputs!!
      # 0		INF	INF
      # INF	0	2
      # INF	1	0



