Skip to main content

Problem

Struct Problem 

Source
pub struct Problem { /* private fields */ }
Expand description

A validated min-cost-flow instance.

Construct through Problem::builder. Every invariant the solver relies on — endpoints in range, lower ≤ upper, supplies summing to zero — is established here, once, so an invalid instance never exists.

Implementations§

Source§

impl Problem

Source

pub fn builder(node_count: usize) -> ProblemBuilder

Start building a network with node_count nodes, ids 0..node_count, every supply zero.

Source

pub fn node_count(&self) -> usize

Number of nodes.

Source

pub fn arc_count(&self) -> usize

Number of arcs.

Source

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

The arcs, in the order they were added.

Source

pub fn supplies(&self) -> &[Flow] ⓘ

Supply at every node, indexed by node id. Positive is supply, negative is demand; the vector sums to zero.

Source

pub fn supply(&self, node: usize) -> Option<Flow>

Supply at node, or None if the id is out of range.

Source

pub fn objective(&self, flows: &[Flow]) -> Result<Objective, Overflow>

Cost of a candidate flow vector, Σ wₖ·fₖ, widened to Objective.

Says nothing about feasibility or optimality — that is verify’s job. Returns an error only on overflow of the 128-bit accumulator, which needs roughly 10¹⁹ units of flow at maximum cost to reach.

Source

pub fn canonical(&self) -> (Self, Vec<usize>)

A canonical reordering of this instance’s arcs, plus the permutation back to the caller’s order.

Arcs are sorted by (tail, head, cost, lower, upper). Two instances that differ only in the order their arcs were added produce byte-equal canonical forms, which is what makes deterministic mode return the same flow for permuted inputs and not merely the same cost.

The returned vector maps canonical position to original position: original[perm[i]] is the arc at canonical position i.

Source

pub fn memory_estimate(&self) -> u64

Bytes the solver will allocate for this instance, stated up front from the problem size, so a caller can budget memory before committing.

Counts the residual network, the per-node solver state and the feasibility pre-check. It is an upper bound on steady-state usage, not a guarantee about transient allocation inside Vec::with_capacity.

Trait Implementations§

Source§

impl Clone for Problem

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 (const: unstable) · Source§

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

Performs copy-assignment from source. Read more
Source§

impl Debug for Problem

Source§

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

Formats the value using the given formatter. Read more
Source§

impl Eq for Problem

Source§

impl PartialEq for Problem

Source§

fn eq(&self, other: &Self) -> bool

Equality operator ==. Read more
1.0.0 (const: unstable) · Source§

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=. Read more
Source§

impl StructuralPartialEq for Problem

Auto Trait Implementations§

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.