graphs.travelling_salesman_problem
==================================

.. py:module:: graphs.travelling_salesman_problem

.. autoapi-nested-parse::

   Travelling Salesman Problem (TSP)



Attributes
----------

.. autoapisummary::

   graphs.travelling_salesman_problem.demo_graph


Exceptions
----------

.. autoapisummary::

   graphs.travelling_salesman_problem.InvalidGraphError


Functions
---------

.. autoapisummary::

   graphs.travelling_salesman_problem.euclidean_distance
   graphs.travelling_salesman_problem.travelling_salesman_brute_force
   graphs.travelling_salesman_problem.travelling_salesman_dynamic_programming
   graphs.travelling_salesman_problem.validate_graph


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

.. py:exception:: InvalidGraphError

   Bases: :py:obj:`ValueError`


   Custom error for invalid graph inputs.


.. py:function:: euclidean_distance(point1: list[float], point2: list[float]) -> float

   Calculate the Euclidean distance between two points in 2D space.

   :param point1: Coordinates of the first point [x, y]
   :param point2: Coordinates of the second point [x, y]
   :return: The Euclidean distance between the two points

   >>> euclidean_distance([0, 0], [3, 4])
   5.0
   >>> euclidean_distance([1, 1], [1, 1])
   0.0
   >>> euclidean_distance([1, 1], ['a', 1])
   Traceback (most recent call last):
       ...
   ValueError: Invalid input: Points must be numerical coordinates


.. py:function:: travelling_salesman_brute_force(graph_points: dict[str, list[float]]) -> tuple[list[str], float]

   Solve the Travelling Salesman Problem using brute force.

   :param graph_points: A dictionary of nodes and their coordinates {node: [x, y]}
   :return: The shortest path and its total distance

   >>> graph = {"A": [10, 20], "B": [30, 21], "C": [15, 35]}
   >>> travelling_salesman_brute_force(graph)
   (['A', 'B', 'C', 'A'], 56.35465722402588)


.. py:function:: travelling_salesman_dynamic_programming(graph_points: dict[str, list[float]]) -> tuple[list[str], float]

   Solve the Travelling Salesman Problem using dynamic programming.

   :param graph_points: A dictionary of nodes and their coordinates {node: [x, y]}
   :return: The shortest path and its total distance

   >>> graph = {"A": [10, 20], "B": [30, 21], "C": [15, 35]}
   >>> travelling_salesman_dynamic_programming(graph)
   (['A', 'C', 'B', 'A'], 56.35465722402587)


.. py:function:: validate_graph(graph_points: dict[str, list[float]]) -> None

   Validate the input graph to ensure it has valid nodes and coordinates.

   :param graph_points: A dictionary where the keys are node names,
                        and values are 2D coordinates as [x, y]
   :raises InvalidGraphError: If the graph points are not valid

   >>> validate_graph({"A": [10, 20], "B": [30, 21], "C": [15, 35]})  # Valid graph
   >>> validate_graph(  # doctest: +IGNORE_EXCEPTION_DETAIL
   ...     {"A": [10, 20], "B": [30, "invalid"], "C": [15, 35]}
   ... )
   Traceback (most recent call last):
       ...
   InvalidGraphError: Each node must have a valid 2D coordinate [x, y]

   >>> validate_graph([10, 20])  # doctest: +IGNORE_EXCEPTION_DETAIL
   Traceback (most recent call last):
       ...
   InvalidGraphError: Graph must be a dictionary with node names and coordinates

   >>> validate_graph(  # doctest: +IGNORE_EXCEPTION_DETAIL
   ...     {"A": [10, 20], "B": [30, 21], "C": [15]}
   ... )  # Missing coordinate
   Traceback (most recent call last):
       ...
   InvalidGraphError: Each node must have a valid 2D coordinate [x, y]


.. py:data:: demo_graph