Struct FlowGraph

Source

pub struct FlowGraph {
    pub adjacency: Vec<Vec<FlowEdge>>,
}

Expand description

An index-based directed flow network supporting residual graph operations.

Nodes are identified by usize indices 0..n. Call add_edge to add a directed edge; the reverse residual edge is inserted automatically.

§Examples

use graph_flow::FlowGraph;

let mut g = FlowGraph::new(4);
g.add_edge(0, 1, 10.0);
g.add_edge(0, 2, 5.0);
g.add_edge(1, 3, 10.0);
g.add_edge(2, 3, 5.0);

// Node count is what we specified.
assert_eq!(g.node_count(), 4);
// Each add_edge inserts 2 entries (forward + reverse).
assert_eq!(g.adjacency[0].len(), 2);

Fields§

§adjacency: Vec<Vec<FlowEdge>>

Adjacency list: adjacency[u] is the list of edges leaving node u.

Both real (forward) edges and zero-capacity reverse (residual) edges are stored here. Use FlowEdge::residual to check if an edge can carry more flow.

Implementations§

Source §

impl FlowGraph

Source

pub fn new(n: usize) -> Self

Creates a new flow graph with n nodes and no edges.

§Examples

use graph_flow::FlowGraph;

let g = FlowGraph::new(5);
assert_eq!(g.node_count(), 5);

Source

pub fn node_count(&self) -> usize

Returns the number of nodes in the graph.

§Examples

use graph_flow::FlowGraph;

let g = FlowGraph::new(3);
assert_eq!(g.node_count(), 3);

Source

pub fn add_edge(&mut self, u: usize, v: usize, capacity: f64)

Adds a directed edge from u to v with the given capacity, and automatically inserts the corresponding zero-capacity reverse edge from v to u.

The reverse edge index is stored in each FlowEdge::rev field so that augmenting flow along (u→v) can update the residual (v→u) in O(1) using only safe index arithmetic.

§Panics

Panics if u or v is out of bounds (>= node_count()).

§Examples

use graph_flow::FlowGraph;

let mut g = FlowGraph::new(2);
g.add_edge(0, 1, 15.0);

// Forward edge from 0 to 1.
assert_eq!(g.adjacency[0][0].to, 1);
assert_eq!(g.adjacency[0][0].capacity, 15.0);

// Reverse edge from 1 to 0 (zero capacity).
assert_eq!(g.adjacency[1][0].to, 0);
assert_eq!(g.adjacency[1][0].capacity, 0.0);

Source

pub fn push_flow(&mut self, u: usize, edge_idx: usize, amount: f64)

Sends amount of flow along the edge at adjacency[u][edge_idx] and simultaneously updates the corresponding reverse edge.

This is the primitive used by augmenting-path algorithms after identifying the bottleneck capacity of a path.

§Panics

Panics if u or edge_idx is out of bounds.

Source

pub fn reset_flow(&mut self)

Resets all flow values to zero, restoring the graph to its initial state with full capacity on every forward edge.

Useful for running multiple flow algorithms on the same graph without rebuilding it from scratch.

§Examples

use graph_flow::{FlowGraph, ford_fulkerson};

let mut g = FlowGraph::new(2);
g.add_edge(0, 1, 10.0);

let flow = ford_fulkerson(&mut g, 0, 1);
assert_eq!(flow, 10.0);

g.reset_flow();
assert_eq!(g.adjacency[0][0].flow, 0.0);