Dijkstra's algorithm with priority queue

Question

I implemented the Dijkstra algorithm. I'm looking for feedback how to make this more pythonic. I'm also wondering if I should move get_shortest_path method out of the Graph class, this would mean I need to expose the vertex list.

The MutablePriorityQueue is just the code snippet from: https://docs.python.org/3/library/heapq.html#priority-queue-implementation-notes. So I can update the priority of an item in the queue.

import math
from mutable_priority_queue import MutablePriorityQueue
class Graph:
 def __init__(self):
 self._vertices = []
 def add_new_vertex(self, x, y):
 """
 Adds a new vertex to the graph.
 :param x: X position of the vertex.
 :param y: Y position of the vertex.
 :return: The newly added vertex in the graph.
 """
 new_vertex_index = len(self._vertices)
 new_vertex = Vertex(new_vertex_index, x, y)
 self._vertices.append(new_vertex)
 return new_vertex
 def get_vertex(self, i):
 """
 Returns the vertex at the i'th index.
 :param i: The index of the vertex in our vertex list.
 """
 return self._vertices[i]
 @staticmethod
 def _calculate_distance(v0, v1):
 v_x = v0.x - v1.x
 v_y = v0.y - v1.y
 return math.sqrt(v_x * v_x + v_y * v_y)
 @staticmethod
 def _get_path(vertex):
 path = [vertex]
 previous_vertex = vertex.previous
 while previous_vertex is not None:
 path.insert(0, previous_vertex)
 previous_vertex = previous_vertex.previous
 return path
 def get_shortest_path(self, source_vertex_index, destination_vertex_index):
 """
 Calculates the shortest path between source and destination using Dijkstra's algorithm
 :param source_vertex_index: The index of the vertex we start at.
 :param destination_vertex_index: The index of the vertex we want to calculate a path to.
 :return: A collection with the vertices making up the shortest path from source to destination.
 """
 if source_vertex_index > len(self._vertices) - 1:
 raise IndexError('source vertex index is out of range.')
 if destination_vertex_index > len(self._vertices) - 1:
 raise IndexError('destination vertex index is out of range.')
 priority_queue = MutablePriorityQueue()
 visited_vertices = set()
 # The source is 0 distance away from itself.
 source_vertex = self._vertices[source_vertex_index]
 source_vertex.distance = 0
 priority_queue.add_or_update(source_vertex, 0)
 while priority_queue:
 # Find an unvisited vertex that closest to our source vertex.
 # Note: the first loop this will be our source vertex.
 current_vertex = priority_queue.pop()
 if current_vertex.index == destination_vertex_index:
 return Graph._get_path(current_vertex)
 visited_vertices.add(current_vertex)
 # Loop over all the neighbouring vertices of our current vertex
 for neighbour_index in range(current_vertex.degree):
 neighbour_vertex = current_vertex.get_neighbour(neighbour_index)
 # If we already visited this neighbour of the current vertex that means
 # we have already calculated the distance between the two.
 if neighbour_vertex in visited_vertices:
 continue
 # Calculate the total distance from the source to this current vertex
 distance = Graph._calculate_distance(current_vertex, neighbour_vertex)
 tentative_distance = current_vertex.distance + distance
 # If the distance is lower we have found a more direct path (or this neighbour hadn't been visited yet)
 if tentative_distance < neighbour_vertex.distance:
 neighbour_vertex.distance = tentative_distance
 neighbour_vertex.previous = current_vertex
 priority_queue.add_or_update(neighbour_vertex, tentative_distance)
 return Graph._get_path(current_vertex)
class Vertex:
 def __init__(self, index, x, y):
 if not isinstance(index, int):
 raise TypeError('Index needs to be of type integer.')
 if index < 0:
 raise IndexError('Index out of range (-1).')
 self.index = index
 self.x = x
 self.y = y
 self.distance = float("inf")
 self.previous = None
 self._neighbours = []
 self._degree = 0
 @property
 def degree(self):
 """
 :return: The number of edges connected to this vertex.
 """
 return self._degree
 def get_neighbour(self, index):
 """
 :param index: The 0-based index of our neighbour.
 :return: The neighbour vertex at the provided index.
 """
 return self._neighbours[index]
 def create_edge(self, neighbour_vertex):
 """
 Creates and edge between this vertex and the neighbour.
 :param neighbour_vertex: The vertex we create an edge between.
 """
 if neighbour_vertex in self._neighbours:
 return
 self._neighbours.append(neighbour_vertex)
 self._degree += 1
 neighbour_vertex.create_edge(self)

Unit tests:

from unittest import TestCase
from undirected_graph import Graph, Vertex
class TestUndirectedGraph(TestCase):
 def test_negative_vertex_index(self):
 # arrange & act & assert
 self.assertRaises(IndexError, lambda: Vertex(-1, 0, 0))
 def test_add_neighbour_check_degree(self):
 # arrange
 v0 = Vertex(0, 10, 10)
 v1 = Vertex(1, 20, 20)
 # act
 v0.create_edge(v1)
 # assert
 self.assertEqual(1, v0.degree)
 self.assertEqual(1, v1.degree)
 self.assertEqual(v1, v0.get_neighbour(0))
 self.assertEqual(v0, v1.get_neighbour(0))
 def test_add_first_vertex(self):
 # arrange
 graph = Graph()
 # act
 vertex = graph.add_new_vertex(10, 10)
 # assert
 self.assertEqual(0, vertex.index)
 def test_add_two_vertices(self):
 # arrange
 graph = Graph()
 # act
 vertex0 = graph.add_new_vertex(10, 10)
 vertex1 = graph.add_new_vertex(20, 20)
 # assert
 self.assertEqual(0, vertex0.index)
 self.assertEqual(1, vertex1.index)
 def test_distance_empty_graph(self):
 # arrange
 graph = Graph()
 # act & assert
 self.assertRaises(IndexError, lambda: graph.get_shortest_path(0, 0))
 def test_distance_single_vertex(self):
 # arrange
 graph = Graph()
 graph.add_new_vertex(0, 0)
 # act
 path = graph.get_shortest_path(0, 0)
 # assert
 self.assertEqual(len(path), 1)
 self.assertEqual(path[0], graph.get_vertex(0))
 def test_distance_two_vertices(self):
 # arrange
 graph = Graph()
 v0 = graph.add_new_vertex(0, 0)
 v1 = graph.add_new_vertex(10, 0)
 v0.create_edge(v1)
 # act
 path = graph.get_shortest_path(0, 1)
 # assert
 self.assertEqual(len(path), 2)
 self.assertEqual(path[0], graph.get_vertex(0))
 self.assertEqual(path[1], graph.get_vertex(1))

Answer 1

My comments are not necessarily python specific but just questioning some modelling choices.

1. Why does vertex take index as an argument? The array of vertices belongs to the graph, is maintained and manipulated by the graph. The question "what is the index of this vertex" should always be answered by the graph object.

2. In general, the index should be something internal to graph. You don't want to be passing around the index of vertices everywhere, but the vertices themselves.

   path = graph.get_shortest_path(v0, v1)
   

3. As you write bigger programs, keeping track of the index of each vertex at some higher level of abstraction (the thing that creates the graph object) is probably going to be cumbersome. Also, then you can never sort or reorder the list of vertice or remove a vertex from the list because you'll screw up the indexing. You might have a similar problem with the neighbor list in the vector class.

4. You could expose neighbors in the vector class. Makes looping simpler:

   for n in current_vertex.neighbors: