rs-graph 0.20.1

/*
 * Copyright (c) 2021 Frank Fischer <frank-fischer@shadow-soft.de>
 *
 * This program is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
 */

use crate::num::traits::{Bounded, FromPrimitive, Num, NumAssign, NumCast, Signed};
use crate::traits::{GraphSize, GraphType, IndexDigraph, IndexGraph};
use crate::vec::EdgeVec;

pub mod simplex;
pub use simplex::NetworkSimplex;

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum SolutionState {
    /// Unknown state, the problem has not been solved, yet
    Unknown,
    /// The problem has been solved to optimality
    Optimal,
    /// The problem is infeasible
    Infeasible,
    /// The problem is unbounded
    Unbounded,
}

pub trait MinCostFlow<'a> {
    type Graph: IndexDigraph<'a> + 'a;

    type Flow;

    fn new(g: &'a Self::Graph) -> Self;

    fn as_graph(&self) -> &'a Self::Graph;

    fn balance(&self, u: <Self::Graph as GraphType<'a>>::Node) -> Self::Flow;

    fn set_balance(&mut self, u: <Self::Graph as GraphType<'a>>::Node, balance: Self::Flow);

    fn set_balances<F>(&mut self, balance: F)
    where
        F: Fn(<Self::Graph as GraphType<'a>>::Node) -> Self::Flow,
    {
        for uid in 0..self.as_graph().num_nodes() {
            let u = self.as_graph().id2node(uid);
            self.set_balance(u, (balance)(u));
        }
    }

    fn lower(&self, e: <Self::Graph as GraphType<'a>>::Edge) -> Self::Flow;

    fn set_lower(&mut self, e: <Self::Graph as GraphType<'a>>::Edge, lb: Self::Flow);

    fn set_lowers<F>(&mut self, lower: F)
    where
        F: Fn(<Self::Graph as GraphType<'a>>::Edge) -> Self::Flow,
    {
        for eid in 0..self.as_graph().num_edges() {
            let e = self.as_graph().id2edge(eid);
            self.set_lower(e, (lower)(e));
        }
    }

    fn upper(&self, e: <Self::Graph as GraphType<'a>>::Edge) -> Self::Flow;

    fn set_upper(&mut self, e: <Self::Graph as GraphType<'a>>::Edge, ub: Self::Flow);

    fn set_uppers<F>(&mut self, upper: F)
    where
        F: Fn(<Self::Graph as GraphType<'a>>::Edge) -> Self::Flow,
    {
        for eid in 0..self.as_graph().num_edges() {
            let e = self.as_graph().id2edge(eid);
            self.set_upper(e, (upper)(e));
        }
    }

    fn cost(&self, e: <Self::Graph as GraphType<'a>>::Edge) -> Self::Flow;

    fn set_cost(&mut self, e: <Self::Graph as GraphType<'a>>::Edge, cost: Self::Flow);

    fn set_costs<F>(&mut self, cost: F)
    where
        F: Fn(<Self::Graph as GraphType<'a>>::Edge) -> Self::Flow,
    {
        for eid in 0..self.as_graph().num_edges() {
            let e = self.as_graph().id2edge(eid);
            self.set_cost(e, (cost)(e));
        }
    }

    /// Return the value of the latest computed flow value.
    fn value(&self) -> Self::Flow;

    /// The flow of an Edge.
    fn flow(&self, a: <Self::Graph as GraphType<'a>>::Edge) -> Self::Flow;

    /// The flow as vector.
    fn flow_vec(&self) -> EdgeVec<'a, &'a Self::Graph, Self::Flow> {
        EdgeVec::new_with(self.as_graph(), |e| self.flow(e))
    }

    /// Solve the maxflow problem.
    ///
    /// The method solves the max flow problem from the source nodes
    /// `src` to the sink node `snk` with the given `upper` bounds on
    /// the edges.
    fn solve(&mut self) -> SolutionState;

    /// Return the current solution state.
    fn solution_state(&self) -> SolutionState;
}

/// Solve a min-cost-flow problem with a network simplex algorithm.
///
/// The function returns the objective value and the optimal flow.
pub fn network_simplex<'a, G, F, Bs, Ls, Us, Cs>(
    g: &'a G,
    balances: Bs,
    lower: Ls,
    upper: Us,
    costs: Cs,
) -> Option<(F, EdgeVec<'a, &'a G, F>)>
where
    G: IndexDigraph<'a>,
    F: Num + NumAssign + NumCast + FromPrimitive + Ord + Signed + Bounded + Copy,
    Bs: Fn(G::Node) -> F,
    Ls: Fn(G::Edge) -> F,
    Us: Fn(G::Edge) -> F,
    Cs: Fn(G::Edge) -> F,
{
    let mut spx = simplex::NetworkSimplex::new(g);
    spx.set_balances(balances);
    spx.set_lowers(lower);
    spx.set_uppers(upper);
    spx.set_costs(costs);
    if spx.solve() == SolutionState::Optimal {
        Some((spx.value(), spx.flow_vec()))
    } else {
        None
    }
}