Find the maximum saving which can be achieved by removing redundant edges whilst ensuring that the network remains connected. >>> solution("test_network.txt") 150
(filename: str = "p107_network.txt")
| 93 | |
| 94 | |
| 95 | def solution(filename: str = "p107_network.txt") -> int: |
| 96 | """ |
| 97 | Find the maximum saving which can be achieved by removing redundant edges |
| 98 | whilst ensuring that the network remains connected. |
| 99 | >>> solution("test_network.txt") |
| 100 | 150 |
| 101 | """ |
| 102 | script_dir: str = os.path.abspath(os.path.dirname(__file__)) |
| 103 | network_file: str = os.path.join(script_dir, filename) |
| 104 | edges: dict[EdgeT, int] = {} |
| 105 | data: list[str] |
| 106 | edge1: int |
| 107 | edge2: int |
| 108 | |
| 109 | with open(network_file) as f: |
| 110 | data = f.read().strip().split("\n") |
| 111 | |
| 112 | adjaceny_matrix = [line.split(",") for line in data] |
| 113 | |
| 114 | for edge1 in range(1, len(adjaceny_matrix)): |
| 115 | for edge2 in range(edge1): |
| 116 | if adjaceny_matrix[edge1][edge2] != "-": |
| 117 | edges[(edge2, edge1)] = int(adjaceny_matrix[edge1][edge2]) |
| 118 | |
| 119 | graph: Graph = Graph(set(range(len(adjaceny_matrix))), edges) |
| 120 | |
| 121 | subgraph: Graph = graph.prims_algorithm() |
| 122 | |
| 123 | initial_total: int = sum(graph.edges.values()) |
| 124 | optimal_total: int = sum(subgraph.edges.values()) |
| 125 | |
| 126 | return initial_total - optimal_total |
| 127 | |
| 128 | |
| 129 | if __name__ == "__main__": |
no test coverage detected