Struct ParametricMaxFlow 

pub struct ParametricMaxFlow { /* private fields */ }

A parametric s-t flow network with affine, GGT-monotone arc capacities.

Implementations

impl ParametricMaxFlow

pub fn new(n: usize, source: usize, sink: usize) -> GraphalgResult<Self>

Create an empty parametric network on n nodes with the given source/sink.

pub fn num_nodes(&self) -> usize

Number of nodes.

pub fn source(&self) -> usize

Source node.

pub fn sink(&self) -> usize

Sink node.

pub fn arcs(&self) -> &[ParametricArc]

Arcs of the network.

pub fn add_arc( &mut self, from: usize, to: usize, base: f64, slope: f64, ) -> GraphalgResult<()>

Add a parametric arc from -> to with capacity base + slope * lambda.

Enforces the GGT monotone structure (see module docs) and rejects out-of-range endpoints and non-finite coefficients.

pub fn from_linear_capacities( n: usize, source: usize, sink: usize, from: &[usize], to: &[usize], base: &[f64], slope: &[f64], ) -> GraphalgResult<Self>

Build a parametric network from parallel coefficient slices.

All slices must share the same length, otherwise a GraphalgError::DimensionMismatch is returned. Each tuple position i describes arc from[i] -> to[i] with capacity base[i] + slope[i] * lambda.

pub fn solve_at(&self, lambda: f64) -> GraphalgResult<ParametricSolution>

Solve the maximum flow at a single lambda, returning the flow value and the minimal source side of the minimum cut (sorted ascending).

pub fn solve_grid( &self, lambdas: &[f64], ) -> GraphalgResult<Vec<ParametricSolution>>

Solve the whole family over the provided lambda grid.

Each entry is an exact independent single-parameter max-flow solve. When the grid is non-decreasing the returned source_sets are nested.

pub fn find_breakpoints( &self, lambda_min: f64, lambda_max: f64, ) -> GraphalgResult<Vec<ParametricBreakpoint>>

Locate every lambda in [lambda_min, lambda_max] at which the minimal minimum-cut source side changes, via Gallo-Grigoriadis-Tarjan slicing.

Returns the breakpoints sorted by ascending lambda. Each breakpoint carries the source side optimal immediately above it. Assumes the affine capacities stay non-negative across the interval (the standard GGT regime); otherwise the breakpoint geometry uses the un-clamped lines.

Trait Implementations

impl Clone for ParametricMaxFlow

fn clone(&self) -> ParametricMaxFlow

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for ParametricMaxFlow

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

Formats the value using the given formatter.