# Cuts

*Graphs.jl* implements several algorithms for graph cuts.

## Index

## Full docs

`Graphs.karger_cut_cost`

— Method`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`

.

`Graphs.karger_cut_edges`

— Method`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`

.

`Graphs.karger_min_cut`

— Method`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|)

`Graphs.normalized_cut`

— Method`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