scirs2_graph::algorithms::flow

Function push_relabel_max_flow

Source 
pub fn push_relabel_max_flow<N, E, Ix>(
    graph: &DiGraph<N, E, Ix>,
    source: &N,
    sink: &N,
) -> Result<f64>
where
    N: Node + Clone + Hash + Eq,
    E: EdgeWeight + Into<f64> + Clone,
    Ix: IndexType,
Expand description

Push-relabel algorithm for maximum flow

Implements the push-relabel algorithm for finding maximum flow. This algorithm has time complexity O(V³) and works well for dense graphs.

§Arguments

  • graph - The directed graph representing the flow network
  • source - The source node
  • sink - The sink node

§Returns

  • The maximum flow value from source to sink