graphs.travelling_salesman_problem

Travelling Salesman Problem (TSP)

Attributes

demo_graph

Exceptions

InvalidGraphError

Custom error for invalid graph inputs.

Functions

euclidean_distance(→ float)

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

travelling_salesman_brute_force(→ tuple[list[str], float])

Solve the Travelling Salesman Problem using brute force.

travelling_salesman_dynamic_programming(...)

Solve the Travelling Salesman Problem using dynamic programming.

validate_graph(→ None)

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

Module Contents

exception graphs.travelling_salesman_problem.InvalidGraphError

Bases: ValueError

Custom error for invalid graph inputs.

graphs.travelling_salesman_problem.euclidean_distance(point1: list[float], point2: list[float]) → float

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

Parameters:

  • point1 – Coordinates of the first point [x, y]

  • point2 – Coordinates of the second point [x, y]

Returns:

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
graphs.travelling_salesman_problem.travelling_salesman_brute_force(graph_points: dict[str, list[float]]) → tuple[list[str], float]

Solve the Travelling Salesman Problem using brute force.

Parameters:

graph_points – A dictionary of nodes and their coordinates {node: [x, y]}

Returns:

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)
graphs.travelling_salesman_problem.travelling_salesman_dynamic_programming(graph_points: dict[str, list[float]]) → tuple[list[str], float]

Solve the Travelling Salesman Problem using dynamic programming.

Parameters:

graph_points – A dictionary of nodes and their coordinates {node: [x, y]}

Returns:

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)
graphs.travelling_salesman_problem.validate_graph(graph_points: dict[str, list[float]]) → None

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

Parameters:

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(
...     {"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])
Traceback (most recent call last):
    ...
InvalidGraphError: Graph must be a dictionary with node names and coordinates

>>> validate_graph(
...     {"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]
graphs.travelling_salesman_problem.demo_graph