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 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 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 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)
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
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’)]
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’)
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’)]
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
Returns the index of left child
Examples: >>> priority_queue_test = PriorityQueue() >>> priority_queue_test.left(0) 1 >>> priority_queue_test.left(1) 3
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')]
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
Returns the index of right child
Examples: >>> priority_queue_test = PriorityQueue() >>> priority_queue_test.right(0) 2 >>> priority_queue_test.right(1) 4
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}