Struct MinCut 

pub struct MinCut {
    pub source_side: Vec<usize>,
    pub sink_side: Vec<usize>,
    pub cut_edges: Vec<(usize, usize)>,
    pub capacity: f64,
}

The result of a minimum s-t cut computation.

The cut partitions the graph’s nodes into two sets: source_side (nodes reachable from the source in the residual graph) and sink_side (all other nodes). Every edge crossing from source_side to sink_side in the original graph is a cut edge; their capacity sum equals the max flow.

Fields

source_side: Vec<usize>

Nodes reachable from the source in the residual graph after max-flow.

This is the source partition S of the min-cut (S, T).

sink_side: Vec<usize>

Nodes not reachable from the source in the residual graph.

This is the sink partition T of the min-cut (S, T).

cut_edges: Vec<(usize, usize)>

The cut edges: (u, v) pairs where u ∈ source_side, v ∈ sink_side, and there is a forward edge u → v in the original graph.

capacity: f64

Total capacity of all cut edges. Equals the maximum flow value by the Max-Flow Min-Cut theorem.

Trait Implementations

impl Clone for MinCut

fn clone(&self) -> MinCut

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for MinCut

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.