hypergraphx 0.0.5

//! This module is a clone of petgraph. A lot of the docs are still theirs, so I can't guarantee that they are accurate for the
//! new implementation. By 0.1.0, promise.
//!
//! Essentially, this module provides a few traits that represent classes of algorithms, which are auto-implemented for anything
//! implementing the right traits from `traits`.
pub mod astar;
pub mod bellman_ford;
pub mod dijkstra;
pub mod dominators;

// Turns out FAS for hypergraphs is a bit too mathy for me at the moment.
// [https://arxiv.org/pdf/2305.13283](paper)
// pub mod feedback_arc_set;
pub mod floyd_warshall;
pub mod ford_fulkerson;
// pub mod isomorphism;
pub mod k_shortest_path;
// pub mod matching;
// pub mod min_spanning_tree;

pub mod measures;
pub mod traversal;

// use fixedbitset::FixedBitSet;

use hashbrown::HashMap;

use self::{bellman_ford::Paths, dominators::Dominators, measures::*};
use crate::prelude::*;
use std::{cmp::Ordering, fmt::Display, ops::Sub};

// Trait aliases are unstable
// pub trait GraphCost<K> = Fn(usize) -> K;

/// `MinScored<K, T>` holds a score `K` and a scored object `T` in
/// a pair for use with a `BinaryHeap`.
///
/// `MinScored` compares in reverse order by the score, so that we can
/// use `BinaryHeap` as a min-heap to extract the score-value pair with the
/// least score.
///
/// **Note:** `MinScored` implements a total order (`Ord`), so that it is
/// possible to use float types as scores.
#[derive(Copy, Clone, Debug)]
pub struct MinScored<K, T>(pub K, pub T);

impl<K: PartialOrd, T> PartialEq for MinScored<K, T> {
    #[inline]
    fn eq(&self, other: &MinScored<K, T>) -> bool {
        self.cmp(other) == Ordering::Equal
    }
}

impl<K: PartialOrd, T> Eq for MinScored<K, T> {}

impl<K: PartialOrd, T> PartialOrd for MinScored<K, T> {
    #[inline]
    fn partial_cmp(&self, other: &MinScored<K, T>) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl<K: PartialOrd, T> Ord for MinScored<K, T> {
    #[inline]
    fn cmp(&self, other: &MinScored<K, T>) -> Ordering {
        let a = &self.0;
        let b = &other.0;
        if a == b {
            Ordering::Equal
        } else if a < b {
            Ordering::Greater
        } else if a > b {
            Ordering::Less
        } else if a.ne(a) && b.ne(b) {
            // these are the NaN cases
            Ordering::Equal
        } else if a.ne(a) {
            // Order NaN less, so that it is last in the MinScore order
            Ordering::Less
        } else {
            Ordering::Greater
        }
    }
}

/// Trait for shortest path algorithms.
pub trait ShortestPaths<T: GraphType> {
    fn astar<'a, F, H, IsGoal, K>(
        &'a self,
        start: usize,
        is_goal: IsGoal,
        edge_cost: F,
        estimate_cost: H,
    ) -> Option<(K, Vec<usize>)>
    where
        Self: CommonProperties<'a, T, NodeIndex = usize, EdgeIndex = usize>,
        IsGoal: FnMut(usize) -> bool,
        F: Fn(usize) -> K,
        H: FnMut(usize) -> K,
        K: Measure + Copy,
    {
        astar::astar(self, start, is_goal, edge_cost, estimate_cost)
    }

    fn bellman_ford<'a, F, K, E>(
        &'a self,
        start: usize,
        edge_cost: F,
    ) -> Result<Paths<K>, HypergraphErrors>
    where
        Self: CommonProperties<'a, T, NodeIndex = usize, EdgeIndex = usize>,
        F: Fn(usize) -> K,
        K: BoundedMeasure + Copy,
    {
        bellman_ford::bellman_ford::<Self, E, F, K, T>(self, start, edge_cost)
    }

    fn dijkstra<'a, F, K>(
        &'a self,
        start: Self::NodeIndex,
        goal: Option<Self::NodeIndex>,
        edge_cost: F,
    ) -> Result<HashMap<Self::NodeIndex, K>, HypergraphErrors>
    where
        Self: CommonProperties<'a, T>,
        F: Fn(Self::EdgeIndex) -> K,
        K: BoundedMeasure + Copy,
    {
        dijkstra::dijkstra(self, start, goal, edge_cost)
    }

    fn floyd_warshall<'a, F, K>(
        &'a self,
        edge_cost: F,
    ) -> Result<HashMap<(usize, usize), K>, HypergraphErrors>
    where
        Self: CommonProperties<'a, T, NodeIndex = usize>,
        F: Fn(<Self as GraphBasics<'a>>::EdgeIndex) -> K,
        K: BoundedMeasure + Copy + Display,
    {
        floyd_warshall::floyd_warshall(self, edge_cost)
    }

    fn k_shortest_path<'a, F, K>(
        &'a self,
        start: usize,
        goal: Option<usize>,
        k: usize,
        edge_cost: F,
    ) -> HashMap<usize, K>
    where
        Self: CommonProperties<'a, T, NodeIndex = usize>,
        F: Fn(<Self as GraphBasics>::EdgeIndex) -> K,
        K: Measure + Copy,
    {
        k_shortest_path::k_shortest_path(self, start, goal, k, edge_cost)
    }
}

impl<'a, T: GraphType, G> ShortestPaths<T> for G where
    G: CommonProperties<'a, T, NodeIndex = usize, EdgeIndex = usize>
{
}

/// Trait for algorithms where you provide a root and everything goes from there.
/// So far only dominators.
pub trait Rooted {
    fn dominators<'a>(&'a self, root: Self::NodeIndex) -> Dominators<Self::NodeIndex>
    where
        Self: DiGraphProperties<'a, NodeIndex = usize, EdgeIndex = usize>
            + CommonProperties<'a, Directed>,
    {
        dominators::simple_fast(self, root)
    }
}

impl<'a, G> Rooted for G where
    G: CommonProperties<'a, Directed, NodeIndex = usize, EdgeIndex = usize>
        + DiGraphProperties<'a, NodeIndex = usize, EdgeIndex = usize>
{
}

pub trait Flow {
    fn ford_fulkerson<'a, F, K>(
        &'a self,
        source: Self::NodeIndex,
        sink: Self::NodeIndex,
        edge_cost: F,
    ) -> Option<(K, Vec<K>)>
    where
        Self: DiGraphProperties<'a> + CommonProperties<'a, Directed>,
        F: Fn(Self::EdgeIndex) -> K,
        K: PositiveMeasure + Copy + Sub<Output = K>,
    {
        ford_fulkerson::ford_fulkerson(self, source, sink, edge_cost)
    }
}

impl<'a, G> Flow for G where
    G: DiGraphProperties<'a> + CommonProperties<'a, Directed, NodeIndex = usize, EdgeIndex = usize>
{
}