>>> adjacency_list = {0: [[1, 1], [3, 3]], ... 1: [[0, 1], [2, 6], [3, 5], [4, 1]], ... 2: [[1, 6], [4, 5], [5, 2]], ... 3: [[0, 3], [1, 5], [4, 1]], ... 4: [[1, 1], [2, 5], [3, 1], [5, 4]], ...
(adjacency_list)
| 73 | |
| 74 | |
| 75 | def prisms_algorithm(adjacency_list): |
| 76 | """ |
| 77 | >>> adjacency_list = {0: [[1, 1], [3, 3]], |
| 78 | ... 1: [[0, 1], [2, 6], [3, 5], [4, 1]], |
| 79 | ... 2: [[1, 6], [4, 5], [5, 2]], |
| 80 | ... 3: [[0, 3], [1, 5], [4, 1]], |
| 81 | ... 4: [[1, 1], [2, 5], [3, 1], [5, 4]], |
| 82 | ... 5: [[2, 2], [4, 4]]} |
| 83 | >>> prisms_algorithm(adjacency_list) |
| 84 | [(0, 1), (1, 4), (4, 3), (4, 5), (5, 2)] |
| 85 | """ |
| 86 | |
| 87 | heap = Heap() |
| 88 | |
| 89 | visited = [0] * len(adjacency_list) |
| 90 | nbr_tv = [-1] * len(adjacency_list) # Neighboring Tree Vertex of selected vertex |
| 91 | # Minimum Distance of explored vertex with neighboring vertex of partial tree |
| 92 | # formed in graph |
| 93 | distance_tv = [] # Heap of Distance of vertices from their neighboring vertex |
| 94 | positions = [] |
| 95 | |
| 96 | for vertex in range(len(adjacency_list)): |
| 97 | distance_tv.append(sys.maxsize) |
| 98 | positions.append(vertex) |
| 99 | heap.node_position.append(vertex) |
| 100 | |
| 101 | tree_edges = [] |
| 102 | visited[0] = 1 |
| 103 | distance_tv[0] = sys.maxsize |
| 104 | for neighbor, distance in adjacency_list[0]: |
| 105 | nbr_tv[neighbor] = 0 |
| 106 | distance_tv[neighbor] = distance |
| 107 | heap.heapify(distance_tv, positions) |
| 108 | |
| 109 | for _ in range(1, len(adjacency_list)): |
| 110 | vertex = heap.delete_minimum(distance_tv, positions) |
| 111 | if visited[vertex] == 0: |
| 112 | tree_edges.append((nbr_tv[vertex], vertex)) |
| 113 | visited[vertex] = 1 |
| 114 | for neighbor, distance in adjacency_list[vertex]: |
| 115 | if ( |
| 116 | visited[neighbor] == 0 |
| 117 | and distance < distance_tv[heap.get_position(neighbor)] |
| 118 | ): |
| 119 | distance_tv[heap.get_position(neighbor)] = distance |
| 120 | heap.bottom_to_top( |
| 121 | distance, heap.get_position(neighbor), distance_tv, positions |
| 122 | ) |
| 123 | nbr_tv[neighbor] = vertex |
| 124 | return tree_edges |
| 125 | |
| 126 | |
| 127 | if __name__ == "__main__": # pragma: no cover |
no test coverage detected