graphs.karger

An implementation of Karger’s Algorithm for partitioning a graph.

Attributes

TEST_GRAPH

Functions

partition_graph(→ set[tuple[str, str]])

Partitions a graph using Karger's Algorithm. Implemented from

Module Contents

graphs.karger.partition_graph(graph: dict[str, list[str]]) → set[tuple[str, str]]

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 lists for the graph.

Nodes must be strings.

Returns:

The cutset of the cut found by Karger’s Algorithm.

>>> graph = {'0':['1'], '1':['0']}
>>> partition_graph(graph)
{('0', '1')}

graphs.karger.TEST_GRAPH