


import argparse
import copy






def 					lowerCamelCase_   (	_a	):




		"""simple docstring"""






		lowerCAmelCase__       :      Any   					= {}

		with open(_a	) as f:
				for line in f:
						if line.split()[0] not in dict_of_neighbours:
								lowerCAmelCase__       :      Tuple   					= []
								_list.append([line.split()[1], line.split()[2]]	)
								lowerCAmelCase__       :      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:
								lowerCAmelCase__       :      List[Any]   					= []
								_list.append([line.split()[0], line.split()[2]]	)
								lowerCAmelCase__       :      Dict   					= _list
						else:
								dict_of_neighbours[line.split()[1]].append(
								    [line.split()[0], line.split()[2]]	)

		return dict_of_neighbours






def 					lowerCamelCase_   (	_a     ,       _a	):




		"""simple docstring"""






		with open(_a	) as f:
				lowerCAmelCase__       :      Any   					= f.read(1	)
		lowerCAmelCase__       :      str   					= start_node

		lowerCAmelCase__       :      Any   					= []

		lowerCAmelCase__       :      Any   					= start_node

		lowerCAmelCase__       :      Union[str, Any]   					= 0
		while visiting not in first_solution:
				lowerCAmelCase__       :      Any   					= 10_000
				for k in dict_of_neighbours[visiting]:
						if int(k[1]	) < int(_a	) and k[0] not in first_solution:
								lowerCAmelCase__       :      List[Any]   					= k[1]
								lowerCAmelCase__       :      Optional[int]   					= k[0]

				first_solution.append(_a	)
				lowerCAmelCase__       :      str   					= distance_of_first_solution + int(_a	)
				lowerCAmelCase__       :      Union[str, Any]   					= best_node

		first_solution.append(_a	)

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

		lowerCAmelCase__       :      List[str]   					= (
		    distance_of_first_solution
		    + int(dict_of_neighbours[first_solution[-2]][position][1]	)
		    - 10_000
		)
		return first_solution, distance_of_first_solution






def 					lowerCamelCase_   (	_a     ,       _a	):




		"""simple docstring"""






		lowerCAmelCase__       :      List[str]   					= []

		for n in solution[1:-1]:
				lowerCAmelCase__       :      Dict   					= solution.index(_a	)
				for kn in solution[1:-1]:
						lowerCAmelCase__       :      Tuple   					= solution.index(_a	)
						if n == kn:
								continue

						lowerCAmelCase__       :      str   					= copy.deepcopy(_a	)
						lowerCAmelCase__       :      Dict   					= kn
						lowerCAmelCase__       :      Dict   					= n

						lowerCAmelCase__       :      Any   					= 0

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

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

		lowerCAmelCase__       :      Optional[int]   					= len(neighborhood_of_solution[0]	) - 1

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






def 					lowerCamelCase_   (	_a     ,       _a     ,       _a     ,       _a     ,       _a	):




		"""simple docstring"""






		lowerCAmelCase__       :      int   					= 1
		lowerCAmelCase__       :      str   					= first_solution
		lowerCAmelCase__       :      List[str]   					= []
		lowerCAmelCase__       :      str   					= distance_of_first_solution
		lowerCAmelCase__       :      Dict   					= solution

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

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

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

				lowerCAmelCase__       :      int   					= count + 1

		return best_solution_ever, best_cost






def 					lowerCamelCase_   (	_a=None	):




		"""simple docstring"""






		lowerCAmelCase__       :      Optional[int]   					= generate_neighbours(args.File	)

		lowerCAmelCase__					,     lowerCAmelCase__       :      Optional[Any]   					= generate_first_solution(
		    args.File     ,       _a	)

		lowerCAmelCase__					,     lowerCAmelCase__       :      Tuple   					= tabu_search(
		    _a     ,       _a     ,       _a     ,       args.Iterations     ,       args.Size     ,       )

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


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








class  _a							:




	def __init__( self						:		str		, _SCREAMING_SNAKE_CASE						:		str		, _SCREAMING_SNAKE_CASE						:		Optional[int]		, _SCREAMING_SNAKE_CASE						:		List[Any]		)->	Tuple:
			lowerCAmelCase__       :      List[Any]   					= None
			lowerCAmelCase__       :      int   					= None
			lowerCAmelCase__       :      Union[str, Any]   					= graph

			self._normalize_graph(_SCREAMING_SNAKE_CASE		, _SCREAMING_SNAKE_CASE		)
			lowerCAmelCase__       :      Tuple   					= len(_SCREAMING_SNAKE_CASE		)
			lowerCAmelCase__       :      Optional[int]   					= None




	def 							UpperCAmelCase__( self						:		Union[str, Any]		, _SCREAMING_SNAKE_CASE						:		Optional[Any]		, _SCREAMING_SNAKE_CASE						:		Union[str, Any]		)->	Union[str, Any]:
			if sources is int:
					lowerCAmelCase__       :      List[Any]   					= [sources]
			if sinks is int:
					lowerCAmelCase__       :      Optional[Any]   					= [sinks]

			if len(_SCREAMING_SNAKE_CASE		) == 0 or len(_SCREAMING_SNAKE_CASE		) == 0:
					return

			lowerCAmelCase__       :      Union[str, Any]   					= sources[0]
			lowerCAmelCase__       :      Dict   					= sinks[0]

			# make fake vertex if there are more
			# than one source or sink
			if len(_SCREAMING_SNAKE_CASE		) > 1 or len(_SCREAMING_SNAKE_CASE		) > 1:
					lowerCAmelCase__       :      List[Any]   					= 0
					for i in sources:
							max_input_flow += sum(self.graph[i]		)

					lowerCAmelCase__       :      Any   					= len(self.graph		) + 1
					for room in self.graph:
							room.insert(0		, 0		)
					self.graph.insert(0		, [0] * size		)
					for i in sources:
							lowerCAmelCase__       :      Optional[Any]   					= max_input_flow
					lowerCAmelCase__       :      List[str]   					= 0

					lowerCAmelCase__       :      List[Any]   					= len(self.graph		) + 1
					for room in self.graph:
							room.append(0		)
					self.graph.append([0] * size		)
					for i in sinks:
							lowerCAmelCase__       :      str   					= max_input_flow
					lowerCAmelCase__       :      Tuple   					= size - 1




	def 							UpperCAmelCase__( self						:		Union[str, Any]		)->	Union[str, Any]:
			if self.maximum_flow_algorithm is None:
					raise Exception('''You need to set maximum flow algorithm before.'''		)
			if self.source_index is None or self.sink_index is None:
					return 0

			self.maximum_flow_algorithm.execute()
			return self.maximum_flow_algorithm.getMaximumFlow()




	def 							UpperCAmelCase__( self						:		str		, _SCREAMING_SNAKE_CASE						:		List[Any]		)->	int:
			lowerCAmelCase__       :      int   					= algorithm(self		)





class  _a							:




	def __init__( self						:		Optional[Any]		, _SCREAMING_SNAKE_CASE						:		Tuple		)->	Union[str, Any]:
			lowerCAmelCase__       :      Tuple   					= flow_network
			lowerCAmelCase__       :      Dict   					= flow_network.verticesCount
			lowerCAmelCase__       :      Optional[Any]   					= flow_network.sourceIndex
			lowerCAmelCase__       :      Optional[Any]   					= flow_network.sinkIndex
			# it's just a reference, so you shouldn't change
			# it in your algorithms, use deep copy before doing that
			lowerCAmelCase__       :      str   					= flow_network.graph
			lowerCAmelCase__       :      Optional[int]   					= False




	def 							UpperCAmelCase__( self						:		List[str]		)->	Dict:
			if not self.executed:
					self._algorithm()
					lowerCAmelCase__       :      Any   					= True




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





class  _a							(    _lowercase):




	def __init__( self						:		Any		, _SCREAMING_SNAKE_CASE						:		List[Any]		)->	Union[str, Any]:
			super().__init__(_SCREAMING_SNAKE_CASE		)
			# use this to save your result
			lowerCAmelCase__       :      Dict   					= -1




	def 							UpperCAmelCase__( self						:		Any		)->	Optional[Any]:
			if not self.executed:
					raise Exception('''You should execute algorithm before using its result!'''		)

			return self.maximum_flow





class  _a							(    _lowercase):




	def __init__( self						:		Any		, _SCREAMING_SNAKE_CASE						:		List[str]		)->	List[str]:
			super().__init__(_SCREAMING_SNAKE_CASE		)

			lowerCAmelCase__       :      Any   					= [[0] * self.verticies_count for i in range(self.verticies_count		)]

			lowerCAmelCase__       :      Optional[Any]   					= [0] * self.verticies_count
			lowerCAmelCase__       :      str   					= [0] * self.verticies_count




	def 							UpperCAmelCase__( self						:		Any		)->	List[Any]:
			lowerCAmelCase__       :      Optional[Any]   					= self.verticies_count

			# push some substance to graph
			for nextvertex_index, bandwidth in enumerate(self.graph[self.source_index]		):
					self.preflow[self.source_index][nextvertex_index] += bandwidth
					self.preflow[nextvertex_index][self.source_index] -= bandwidth
					self.excesses[nextvertex_index] += bandwidth

			# Relabel-to-front selection rule
			lowerCAmelCase__       :      Any   					= [
			    i
			    for i in range(self.verticies_count		)
			    if i != self.source_index and i != self.sink_index
			]

			# move through list
			lowerCAmelCase__       :      str   					= 0
			while i < len(_SCREAMING_SNAKE_CASE		):
					lowerCAmelCase__       :      Union[str, Any]   					= vertices_list[i]
					lowerCAmelCase__       :      Any   					= self.heights[vertex_index]
					self.process_vertex(_SCREAMING_SNAKE_CASE		)
					if self.heights[vertex_index] > previous_height:
							# if it was relabeled, swap elements
							# and start from 0 index
							vertices_list.insert(0		, vertices_list.pop(_SCREAMING_SNAKE_CASE		)		)
							lowerCAmelCase__       :      Optional[Any]   					= 0
					else:
							i += 1

			lowerCAmelCase__       :      Optional[Any]   					= sum(self.preflow[self.source_index]		)




	def 							UpperCAmelCase__( self						:		List[str]		, _SCREAMING_SNAKE_CASE						:		Optional[Any]		)->	Optional[int]:
			while self.excesses[vertex_index] > 0:
					for neighbour_index in range(self.verticies_count		):
							# if it's neighbour and current vertex is higher
							if (
							    self.graph[vertex_index][neighbour_index]
							    - self.preflow[vertex_index][neighbour_index]
							    > 0
							    and self.heights[vertex_index] > self.heights[neighbour_index]
							):
									self.push(_SCREAMING_SNAKE_CASE		, _SCREAMING_SNAKE_CASE		)

					self.relabel(_SCREAMING_SNAKE_CASE		)




	def 							UpperCAmelCase__( self						:		int		, _SCREAMING_SNAKE_CASE						:		Optional[Any]		, _SCREAMING_SNAKE_CASE						:		Union[str, Any]		)->	Union[str, Any]:
			lowerCAmelCase__       :      Union[str, Any]   					= min(
			    self.excesses[from_index]		, self.graph[from_index][to_index] - self.preflow[from_index][to_index]		, )
			self.preflow[from_index][to_index] += preflow_delta
			self.preflow[to_index][from_index] -= preflow_delta
			self.excesses[from_index] -= preflow_delta
			self.excesses[to_index] += preflow_delta




	def 							UpperCAmelCase__( self						:		Optional[int]		, _SCREAMING_SNAKE_CASE						:		Any		)->	Optional[int]:
			lowerCAmelCase__       :      Optional[int]   					= None
			for to_index in range(self.verticies_count		):
					if (
					    self.graph[vertex_index][to_index]
					    - self.preflow[vertex_index][to_index]
					    > 0
					) and (min_height is None or self.heights[to_index] < min_height):
							lowerCAmelCase__       :      List[Any]   					= self.heights[to_index]

			if min_height is not None:
					lowerCAmelCase__       :      Optional[Any]   					= min_height + 1


if __name__ == "__main__":
		lowerCamelCase						=		[0]
		lowerCamelCase						=		[3]
		# graph = [
		#     [0, 0, 4, 6, 0, 0],
		#     [0, 0, 5, 2, 0, 0],
		#     [0, 0, 0, 0, 4, 4],
		#     [0, 0, 0, 0, 6, 6],
		#     [0, 0, 0, 0, 0, 0],
		#     [0, 0, 0, 0, 0, 0],
		# ]
		lowerCamelCase						=		[[0, 7, 0, 0], [0, 0, 6, 0], [0, 0, 0, 8], [9, 0, 0, 0]]

		# prepare our network
		lowerCamelCase						=		FlowNetwork(graph, entrances, exits)
		# set algorithm
		flow_network.set_maximum_flow_algorithm(PushRelabelExecutor)
		# and calculate
		lowerCamelCase						=		flow_network.find_maximum_flow()

		print(f'''maximum flow is {maximum_flow}''')




