Partitions a graph using Karger's Algorithm. Implemented from pseudocode found here: https://en.wikipedia.org/wiki/Karger%27s_algorithm. This function involves random choices, meaning it will not give consistent outputs. Args: graph: A dictionary containing adacency
(graph: dict[str, list[str]])
| 23 | |
| 24 | |
| 25 | def partition_graph(graph: dict[str, list[str]]) -> set[tuple[str, str]]: |
| 26 | """ |
| 27 | Partitions a graph using Karger's Algorithm. Implemented from |
| 28 | pseudocode found here: |
| 29 | https://en.wikipedia.org/wiki/Karger%27s_algorithm. |
| 30 | This function involves random choices, meaning it will not give |
| 31 | consistent outputs. |
| 32 | |
| 33 | Args: |
| 34 | graph: A dictionary containing adacency lists for the graph. |
| 35 | Nodes must be strings. |
| 36 | |
| 37 | Returns: |
| 38 | The cutset of the cut found by Karger's Algorithm. |
| 39 | |
| 40 | >>> graph = {'0':['1'], '1':['0']} |
| 41 | >>> partition_graph(graph) |
| 42 | {('0', '1')} |
| 43 | """ |
| 44 | # Dict that maps contracted nodes to a list of all the nodes it "contains." |
| 45 | contracted_nodes = {node: {node} for node in graph} |
| 46 | |
| 47 | graph_copy = {node: graph[node][:] for node in graph} |
| 48 | |
| 49 | while len(graph_copy) > 2: |
| 50 | # Choose a random edge. |
| 51 | u = random.choice(list(graph_copy.keys())) |
| 52 | v = random.choice(graph_copy[u]) |
| 53 | |
| 54 | # Contract edge (u, v) to new node uv |
| 55 | uv = u + v |
| 56 | uv_neighbors = list(set(graph_copy[u] + graph_copy[v])) |
| 57 | uv_neighbors.remove(u) |
| 58 | uv_neighbors.remove(v) |
| 59 | graph_copy[uv] = uv_neighbors |
| 60 | for neighbor in uv_neighbors: |
| 61 | graph_copy[neighbor].append(uv) |
| 62 | |
| 63 | contracted_nodes[uv] = set(contracted_nodes[u].union(contracted_nodes[v])) |
| 64 | |
| 65 | # Remove nodes u and v. |
| 66 | del graph_copy[u] |
| 67 | del graph_copy[v] |
| 68 | for neighbor in uv_neighbors: |
| 69 | if u in graph_copy[neighbor]: |
| 70 | graph_copy[neighbor].remove(u) |
| 71 | if v in graph_copy[neighbor]: |
| 72 | graph_copy[neighbor].remove(v) |
| 73 | |
| 74 | # Find cutset. |
| 75 | groups = [contracted_nodes[node] for node in graph_copy] |
| 76 | return { |
| 77 | (node, neighbor) |
| 78 | for node in groups[0] |
| 79 | for neighbor in graph[node] |
| 80 | if neighbor in groups[1] |
| 81 | } |
| 82 |