graphs.ant_colony_optimization_algorithms
=========================================

.. py:module:: graphs.ant_colony_optimization_algorithms

.. autoapi-nested-parse::

   Use an ant colony optimization algorithm to solve the travelling salesman problem (TSP)
   which asks the following question:
   "Given a list of cities and the distances between each pair of cities, what is the
    shortest possible route that visits each city exactly once and returns to the origin
    city?"

   https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms
   https://en.wikipedia.org/wiki/Travelling_salesman_problem

   Author: Clark



Attributes
----------

.. autoapisummary::

   graphs.ant_colony_optimization_algorithms.cities


Functions
---------

.. autoapisummary::

   graphs.ant_colony_optimization_algorithms.city_select
   graphs.ant_colony_optimization_algorithms.distance
   graphs.ant_colony_optimization_algorithms.main
   graphs.ant_colony_optimization_algorithms.pheromone_update


Module Contents
---------------

.. py:function:: city_select(pheromone: list[list[float]], current_city: dict[int, list[int]], unvisited_cities: dict[int, list[int]], alpha: float, beta: float) -> tuple[dict[int, list[int]], dict[int, list[int]]]

   Choose the next city for ants
   >>> city_select(pheromone=[[1.0, 1.0], [1.0, 1.0]], current_city={0: [0, 0]},
   ...             unvisited_cities={1: [2, 2]}, alpha=1.0, beta=5.0)
   ({1: [2, 2]}, {})
   >>> city_select(pheromone=[], current_city={0: [0,0]},
   ...             unvisited_cities={1: [2, 2]}, alpha=1.0, beta=5.0)
   Traceback (most recent call last):
     ...
   IndexError: list index out of range
   >>> city_select(pheromone=[[1.0, 1.0], [1.0, 1.0]], current_city={},
   ...             unvisited_cities={1: [2, 2]}, alpha=1.0, beta=5.0)
   Traceback (most recent call last):
     ...
   StopIteration
   >>> city_select(pheromone=[[1.0, 1.0], [1.0, 1.0]], current_city={0: [0, 0]},
   ...             unvisited_cities={}, alpha=1.0, beta=5.0)
   Traceback (most recent call last):
     ...
   IndexError: list index out of range


.. py:function:: distance(city1: list[int], city2: list[int]) -> float

   Calculate the distance between two coordinate points
   >>> distance([0, 0], [3, 4] )
   5.0
   >>> distance([0, 0], [-3, 4] )
   5.0
   >>> distance([0, 0], [-3, -4] )
   5.0


.. py:function:: main(cities: dict[int, list[int]], ants_num: int, iterations_num: int, pheromone_evaporation: float, alpha: float, beta: float, q: float) -> tuple[list[int], float]

   Ant colony algorithm main function
   >>> main(cities=cities, ants_num=10, iterations_num=20,
   ...      pheromone_evaporation=0.7, alpha=1.0, beta=5.0, q=10)
   ([0, 1, 2, 3, 4, 5, 6, 7, 0], 37.909778143828696)
   >>> main(cities={0: [0, 0], 1: [2, 2]}, ants_num=5, iterations_num=5,
   ...      pheromone_evaporation=0.7, alpha=1.0, beta=5.0, q=10)
   ([0, 1, 0], 5.656854249492381)
   >>> main(cities={0: [0, 0], 1: [2, 2], 4: [4, 4]}, ants_num=5, iterations_num=5,
   ...      pheromone_evaporation=0.7, alpha=1.0, beta=5.0, q=10)
   Traceback (most recent call last):
     ...
   IndexError: list index out of range
   >>> main(cities={}, ants_num=5, iterations_num=5,
   ...      pheromone_evaporation=0.7, alpha=1.0, beta=5.0, q=10)
   Traceback (most recent call last):
     ...
   StopIteration
   >>> main(cities={0: [0, 0], 1: [2, 2]}, ants_num=0, iterations_num=5,
   ...      pheromone_evaporation=0.7, alpha=1.0, beta=5.0, q=10)
   ([], inf)
   >>> main(cities={0: [0, 0], 1: [2, 2]}, ants_num=5, iterations_num=0,
   ...      pheromone_evaporation=0.7, alpha=1.0, beta=5.0, q=10)
   ([], inf)
   >>> main(cities={0: [0, 0], 1: [2, 2]}, ants_num=5, iterations_num=5,
   ...      pheromone_evaporation=1, alpha=1.0, beta=5.0, q=10)
   ([0, 1, 0], 5.656854249492381)
   >>> main(cities={0: [0, 0], 1: [2, 2]}, ants_num=5, iterations_num=5,
   ...      pheromone_evaporation=0, alpha=1.0, beta=5.0, q=10)
   ([0, 1, 0], 5.656854249492381)


.. py:function:: pheromone_update(pheromone: list[list[float]], cities: dict[int, list[int]], pheromone_evaporation: float, ants_route: list[list[int]], q: float, best_path: list[int], best_distance: float) -> tuple[list[list[float]], list[int], float]

   Update pheromones on the route and update the best route
   >>>
   >>> pheromone_update(pheromone=[[1.0, 1.0], [1.0, 1.0]],
   ...                  cities={0: [0,0], 1: [2,2]}, pheromone_evaporation=0.7,
   ...                  ants_route=[[0, 1, 0]], q=10, best_path=[],
   ...                  best_distance=float("inf"))
   ([[0.7, 4.235533905932737], [4.235533905932737, 0.7]], [0, 1, 0], 5.656854249492381)
   >>> pheromone_update(pheromone=[],
   ...                  cities={0: [0,0], 1: [2,2]}, pheromone_evaporation=0.7,
   ...                  ants_route=[[0, 1, 0]], q=10, best_path=[],
   ...                  best_distance=float("inf"))
   Traceback (most recent call last):
     ...
   IndexError: list index out of range
   >>> pheromone_update(pheromone=[[1.0, 1.0], [1.0, 1.0]],
   ...                  cities={}, pheromone_evaporation=0.7,
   ...                  ants_route=[[0, 1, 0]], q=10, best_path=[],
   ...                  best_distance=float("inf"))
   Traceback (most recent call last):
     ...
   KeyError: 0


.. py:data:: cities