Cuts

karger_cut_cost(g, cut)

Find the number of crossing edges in a cut of graph g where the cut is represented by the integer array, cut.

karger_cut_edges(g, cut)

Find the crossing edges in a cut of graph g where the cut is represented by the integer array, cut.

karger_min_cut(g)

Perform Karger Minimum Cut to find the minimum cut of graph g with some probability of success. A cut is a partition of vertices(g) into two non-empty sets. The size of a cut is the number of edges crossing the two non-empty sets.

Implementation Notes

The cut is represented by an integer array. If cut[v] == 1 then v is in the first non-empty set. If cut[v] == 2 then v is in the second non-empty set. cut[1] = 1.

If |V| < 2 then cut[v] = 0 for all v.

Performance

Runtime: O(|E|) Memory: O(|E|)

normalized_cut(g, thres, distmx=weights(g), [num_cuts=10]);

Perform recursive two-way normalized graph-cut on a graph, partitioning the vertices into disjoint sets. Return a vector that contains the set index for each vertex.

It is important to identify a good threshold for your application. A bisection search over the range (0,1) will help determine a good value of thres.

Keyword Arguments

• thres: Subgraphs aren't split if best normalized cut is above this threshold
• num_cuts: Number of cuts performed to determine optimal cut

References

"Normalized Cuts and Image Segmentation" - Jianbo Shi and Jitendra Malik