graphs.dijkstra_algorithm

Attributes

graph

Classes

Graph
PriorityQueue

Module Contents

class graphs.dijkstra_algorithm.Graph(num)

add_edge(u, v, w)

Add edge going from node u to v and v to u with weight w: u (w)-> v, v (w) -> u

Examples: >>> graph_test = Graph(1) >>> graph_test.add_edge(1, 2, 1) >>> graph_test.add_edge(2, 3, 2) >>> graph_test.adjList {1: [(2, 1)], 2: [(1, 1), (3, 2)], 3: [(2, 2)]}

dijkstra(src)

Dijkstra algorithm

Examples: >>> graph_test = Graph(3) >>> graph_test.add_edge(0, 1, 2) >>> graph_test.add_edge(1, 2, 2) >>> graph_test.dijkstra(0) Distance from node: 0 Node 0 has distance: 0 Node 1 has distance: 2 Node 2 has distance: 4 >>> graph_test.dist [0, 2, 4]

>>> graph_test = Graph(2)
>>> graph_test.add_edge(0, 1, 2)
>>> graph_test.dijkstra(0)
Distance from node: 0
Node 0 has distance: 0
Node 1 has distance: 2
>>> graph_test.dist
[0, 2]

>>> graph_test = Graph(3)
>>> graph_test.add_edge(0, 1, 2)
>>> graph_test.dijkstra(0)
Distance from node: 0
Node 0 has distance: 0
Node 1 has distance: 2
Node 2 has distance: 0
>>> graph_test.dist
[0, 2, 0]

>>> graph_test = Graph(3)
>>> graph_test.add_edge(0, 1, 2)
>>> graph_test.add_edge(1, 2, 2)
>>> graph_test.add_edge(0, 2, 1)
>>> graph_test.dijkstra(0)
Distance from node: 0
Node 0 has distance: 0
Node 1 has distance: 2
Node 2 has distance: 1
>>> graph_test.dist
[0, 2, 1]

>>> graph_test = Graph(4)
>>> graph_test.add_edge(0, 1, 4)
>>> graph_test.add_edge(1, 2, 2)
>>> graph_test.add_edge(2, 3, 1)
>>> graph_test.add_edge(0, 2, 3)
>>> graph_test.dijkstra(0)
Distance from node: 0
Node 0 has distance: 0
Node 1 has distance: 4
Node 2 has distance: 3
Node 3 has distance: 4
>>> graph_test.dist
[0, 4, 3, 4]

>>> graph_test = Graph(4)
>>> graph_test.add_edge(0, 1, 4)
>>> graph_test.add_edge(1, 2, 2)
>>> graph_test.add_edge(2, 3, 1)
>>> graph_test.add_edge(0, 2, 7)
>>> graph_test.dijkstra(0)
Distance from node: 0
Node 0 has distance: 0
Node 1 has distance: 4
Node 2 has distance: 6
Node 3 has distance: 7
>>> graph_test.dist
[0, 4, 6, 7]

show_distances(src)

Show the distances from src to all other nodes in a graph

Examples: >>> graph_test = Graph(1) >>> graph_test.show_distances(0) Distance from node: 0 Node 0 has distance: 0

show_graph()

Show the graph: u -> v(w)

Examples: >>> graph_test = Graph(1) >>> graph_test.add_edge(1, 2, 1) >>> graph_test.show_graph() 1 -> 2(1) 2 -> 1(1) >>> graph_test.add_edge(2, 3, 2) >>> graph_test.show_graph() 1 -> 2(1) 2 -> 1(1) -> 3(2) 3 -> 2(2)

show_path(src, dest)

Shows the shortest path from src to dest. WARNING: Use it after calling dijkstra.

Examples: >>> graph_test = Graph(4) >>> graph_test.add_edge(0, 1, 1) >>> graph_test.add_edge(1, 2, 2) >>> graph_test.add_edge(2, 3, 3) >>> graph_test.dijkstra(0) Distance from node: 0 Node 0 has distance: 0 Node 1 has distance: 1 Node 2 has distance: 3 Node 3 has distance: 6 >>> graph_test.show_path(0, 3) # doctest: +NORMALIZE_WHITESPACE —-Path to reach 3 from 0—- 0 -> 1 -> 2 -> 3 Total cost of path: 6

adjList

dist

num_nodes

par

class graphs.dijkstra_algorithm.PriorityQueue

decrease_key(tup, new_d)

Decrease the key value for a given tuple, assuming the new_d is at most old_d.

Examples: >>> priority_queue_test = PriorityQueue() >>> priority_queue_test.array = [(10, ‘A’), (15, ‘B’)] >>> priority_queue_test.cur_size = len(priority_queue_test.array) >>> priority_queue_test.pos = {‘A’: 0, ‘B’: 1} >>> priority_queue_test.decrease_key((10, ‘A’), 5) >>> priority_queue_test.array [(5, ‘A’), (15, ‘B’)]

extract_min()

Removes and returns the min element at top of priority queue.

Examples: >>> priority_queue_test = PriorityQueue() >>> priority_queue_test.array = [(10, ‘A’), (15, ‘B’)] >>> priority_queue_test.cur_size = len(priority_queue_test.array) >>> priority_queue_test.pos = {‘A’: 0, ‘B’: 1} >>> priority_queue_test.insert((5, ‘C’)) >>> priority_queue_test.extract_min() ‘C’ >>> priority_queue_test.array[0] (10, ‘A’)

insert(tup)

Inserts a node into the Priority Queue.

Examples: >>> priority_queue_test = PriorityQueue() >>> priority_queue_test.insert((10, ‘A’)) >>> priority_queue_test.array [(10, ‘A’)] >>> priority_queue_test.insert((15, ‘B’)) >>> priority_queue_test.array [(10, ‘A’), (15, ‘B’)] >>> priority_queue_test.insert((5, ‘C’)) >>> priority_queue_test.array [(5, ‘C’), (10, ‘A’), (15, ‘B’)]

is_empty()

Conditional boolean method to determine if the priority queue is empty or not.

Examples: >>> priority_queue_test = PriorityQueue() >>> priority_queue_test.is_empty() True >>> priority_queue_test.insert((2, ‘A’)) >>> priority_queue_test.is_empty() False

left(i)

Returns the index of left child

Examples: >>> priority_queue_test = PriorityQueue() >>> priority_queue_test.left(0) 1 >>> priority_queue_test.left(1) 3

min_heapify(idx)

Sorts the queue array so that the minimum element is root.

Examples: >>> priority_queue_test = PriorityQueue() >>> priority_queue_test.cur_size = 3 >>> priority_queue_test.pos = {‘A’: 0, ‘B’: 1, ‘C’: 2}

>>> priority_queue_test.array = [(5, 'A'), (10, 'B'), (15, 'C')]
>>> priority_queue_test.min_heapify(0)
>>> priority_queue_test.array
[(5, 'A'), (10, 'B'), (15, 'C')]

>>> priority_queue_test.array = [(10, 'A'), (5, 'B'), (15, 'C')]
>>> priority_queue_test.min_heapify(0)
>>> priority_queue_test.array
[(5, 'B'), (10, 'A'), (15, 'C')]

>>> priority_queue_test.array = [(10, 'A'), (15, 'B'), (5, 'C')]
>>> priority_queue_test.min_heapify(0)
>>> priority_queue_test.array
[(5, 'C'), (15, 'B'), (10, 'A')]

>>> priority_queue_test.array = [(10, 'A'), (5, 'B')]
>>> priority_queue_test.cur_size = len(priority_queue_test.array)
>>> priority_queue_test.pos = {'A': 0, 'B': 1}
>>> priority_queue_test.min_heapify(0)
>>> priority_queue_test.array
[(5, 'B'), (10, 'A')]

par(i)

Returns the index of parent

Examples: >>> priority_queue_test = PriorityQueue() >>> priority_queue_test.par(1) 0 >>> priority_queue_test.par(2) 1 >>> priority_queue_test.par(4) 2

right(i)

Returns the index of right child

Examples: >>> priority_queue_test = PriorityQueue() >>> priority_queue_test.right(0) 2 >>> priority_queue_test.right(1) 4

swap(i, j)

Swaps array elements at indices i and j, update the pos{}

Examples: >>> priority_queue_test = PriorityQueue() >>> priority_queue_test.array = [(10, ‘A’), (15, ‘B’)] >>> priority_queue_test.cur_size = len(priority_queue_test.array) >>> priority_queue_test.pos = {‘A’: 0, ‘B’: 1} >>> priority_queue_test.swap(0, 1) >>> priority_queue_test.array [(15, ‘B’), (10, ‘A’)] >>> priority_queue_test.pos {‘A’: 1, ‘B’: 0}

array = []

cur_size = 0

pos

graphs.dijkstra_algorithm.graph