hypergraphx 0.0.5

//! Most of the functionality of this library is encapsulated in these traits. A quick overview:
//!
//! GraphBasics: Provides iterators over nodes and edges.
//!
//! Weights: Provides shared and mutable access to node and edge weight.
//!
//! MatrixRepresentation: Adjacency and incidence matrices.
//!
//! GraphProperties: Basic properties of graphs, such as degree, connected components, etc.
//!
//! DiGraphProperties: The directed analogue of GraphProperties.
//!
//! CommonProperties: Trait for functions that apply to both directed and undirected graphs, but with
//!     different implementations.
//!
//! HypergraphProperties: Properties specific to hypergraphs, such as edge order.
//!
//! DirectedHypergraphProperties: Directed analogue of HypergraphProperties.
//!
//! GraphType: A trait over which other traits are generic - when the same set of functions
//!     applies to multiple kinds of graphs and I didn't want to write the same code multiple times.
//!     In general, unless you're implementing a new graph type, you do not need to worry about this
//!     trait.
//!
//! ParallelWeights: Provides parallel iterators over graph weights with rayon.
//!     
//!
//! In principle, none of these traits borrow the graph (or atleast the incidence structure) mutably.
//! All mutation is done though struct methods, because the function signatures vary too much
//! between different graph types. Also, cleaner?

use crate::prelude::*;
use hashbrown::{HashMap, HashSet};
use itertools::Itertools;
use std::{hash::Hash, ops::Deref};

pub mod undirected;
pub use undirected::*;
pub mod directed;
pub use directed::*;
pub mod linalg;
pub use linalg::*;
pub mod common;
pub use common::*;
pub mod weights;
pub use weights::*;
pub mod wrappers;
pub use wrappers::*;

/// The root trait for all graphs and hypergraphs.
/// Provides functions to iterate over nodes and edges, and count them.
///
/// Note: We have the associated types `NodeRef` and `EdgeRef`, which are references to
/// nodes and edges respectively. This allows complex graph types, like `Multiplex`, to use
/// enums with variants holding references to different types of edges or nodes.
///
/// Typical graphs and hypergraphs use `usize` for node and edge indices. However,
/// the associated types `NodeIndex` and `EdgeIndex` allow for more complex graph types to use
/// different of indices.
/// For example, `Multiplex` uses `MultiplexIndex(Option<usize>, usize)`. This allows trait methods to
/// return sets of/iterators over edges from a specific layer (`Some` variant) or over all layers (`None` variant).
///
/// However, the `NodeIndex` and `EdgeIndex` types must implement `From<usize>` and `Into<usize>`, so that the methods
/// accepting indices as arguments can be used while iterating over the nodes and/or edges.
///
pub trait GraphBasics<'a> {
    type NodeRef: Eq + Hash + Copy;
    type EdgeRef: Eq + Hash + Copy;

    type NodeIndex: Copy + Eq + Hash + From<usize> + Into<usize>;
    type EdgeIndex: Copy + Eq + Hash + From<usize> + Into<usize>;

    fn nodes(&'a self) -> impl Iterator<Item = Self::NodeRef>;
    fn node_count(&'a self) -> usize;

    fn edges(&'a self) -> impl Iterator<Item = Self::EdgeRef>;
    fn edge_count(&'a self) -> usize;

    fn is_directed(&self) -> bool;
    fn node(&'a self, node_index: Self::NodeIndex) -> Option<Self::NodeRef>;
    fn edge(&'a self, edge_index: Self::EdgeIndex) -> Option<Self::EdgeRef>;
    fn node_iter(
        &'a self,
        node_index: impl Iterator<Item = Self::NodeIndex>,
    ) -> impl Iterator<Item = Option<Self::NodeRef>>;
    fn edge_iter(
        &'a self,
        edge_index: impl Iterator<Item = Self::EdgeIndex>,
    ) -> impl Iterator<Item = Option<Self::EdgeRef>>;
}

#[macro_export]
macro_rules! impl_graph_basics {
    ($graph:ty, $node:ty, $edge:ty, $dir:literal $(, <$($gens:tt),*>)? $(, |$(const $cgens:ident: $ity:ty),*|)? ) => {
        // use rayon::prelude::*;
        impl<'a, N, E$(, $($gens),*)?$(, $(const $cgens: $ity),*)?> GraphBasics<'a>
            for $graph
            where N: 'a + Clone + Eq + Hash,
                  E: 'a + Clone + Eq + Hash,
        {
            type NodeRef = $node;
            type EdgeRef = $edge;
            type EdgeIndex = usize;
            type NodeIndex = usize;

            fn nodes(&'a self) -> impl Iterator<Item = Self::NodeRef> {
                self.nodes.iter()
            }

            fn edges(&'a self) -> impl Iterator<Item = Self::EdgeRef> {
                self.edges.iter()
            }
            fn node_count(&'a self) -> usize {
                self.nodes.len()
            }

            fn edge_count(&'a self) -> usize {
                self.edges.len()
            }
            fn is_directed(&self) -> bool {
                $dir
            }
            fn node(&'a self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> Option<<Self as GraphBasics<'a>>::NodeRef> {
                self.nodes.get(node_index)
            }
            fn edge(&'a self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> Option<<Self as GraphBasics<'a>>::EdgeRef> {
                self.edges.get(edge_index)
            }
            fn node_iter(&'a self, node_index: impl Iterator<Item = <Self as GraphBasics<'a>>::NodeIndex>) -> impl Iterator<Item = Option<<Self as GraphBasics<'a>>::NodeRef>> {
                node_index.map(|i| self.node(i))
            }
            fn edge_iter(&'a self, edge_index: impl Iterator<Item = <Self as GraphBasics<'a>>::EdgeIndex>) -> impl Iterator<Item = Option<<Self as GraphBasics<'a>>::EdgeRef>> {
                edge_index.map(|i| self.edge(i))
            }
        }
    };
}

#[macro_export]
macro_rules! impl_graph_basics_wrapper {
    (
        $graph:ty,
        $inner_g:ty,
        $dir:literal,
        $(, <$($gens:tt),*>)?
        $(, |$(const $cgens:ident: $ity:ty),*|)?
    ) => {
        impl<'a, N, E$(, $($gens),*)?$(, $(const $cgens: $ity),*)?> GraphBasics<'a>
            for $graph
            where N: 'a + Clone + Eq + Hash,
                  E: 'a + Clone + Eq + Hash,
        {
            type NodeRef = <$inner_g as GraphBasics<'a>>::NodeRef;
            type EdgeRef = <$inner_g as GraphBasics<'a>>::EdgeRef;
            type EdgeIndex = <$inner_g as GraphBasics<'a>>::EdgeIndex;
            type NodeIndex = <$inner_g as GraphBasics<'a>>::NodeIndex;

            fn nodes(&'a self) -> impl Iterator<Item = Self::NodeRef> {
                self.inner.nodes.iter()
            }

            fn edges(&'a self) -> impl Iterator<Item = Self::EdgeRef> {
                self.inner.edges.iter()
            }
            fn node_count(&'a self) -> usize {
                self.inner.nodes.len()
            }

            fn edge_count(&'a self) -> usize {
                self.inner.edges.len()
            }
            fn is_directed(&self) -> bool {
                $dir
            }
            fn node(&'a self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> Option<<Self as GraphBasics<'a>>::NodeRef> {
                self.inner.nodes.get(node_index)
            }
            fn edge(&'a self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> Option<<Self as GraphBasics<'a>>::EdgeRef> {
                self.inner.edges.get(edge_index)
            }
            fn node_iter(&'a self, node_index: impl Iterator<Item = <Self as GraphBasics<'a>>::NodeIndex>) -> impl Iterator<Item = Option<<Self as GraphBasics<'a>>::NodeRef>> {
                node_index.map(|i| self.inner.node(i))
            }
            fn edge_iter(&'a self, edge_index: impl Iterator<Item = <Self as GraphBasics<'a>>::EdgeIndex>) -> impl Iterator<Item = Option<<Self as GraphBasics<'a>>::EdgeRef>> {
                edge_index.map(|i| self.inner.edge(i))
            }
        }

        impl<'a, N: 'a, E: 'a$(, $($gens),*)?$(, $(const $cgens: $ity),*)?> GraphWrapper<'a> for $graph
            where   $inner_g: GraphBasics<'a>,
                    N: 'a + Clone + Eq + Hash,
                    E: 'a + Clone + Eq + Hash,{
            type Inner = $inner_g;

            fn into_inner(&'a self) -> &'a Self::Inner {
                &self.inner
            }
        }
    };
    (
        $graph:ty,
        $inner_g:ty,
        $dir:literal,
        reduce E = $edge_weight:tt
        $(, <$($gens:tt),*>)?
        $(, |$(const $cgens:ident: $ity:ty),*|)?
    ) => {
        impl<'a, N$(, $($gens),*)?$(, $(const $cgens: $ity),*)?> GraphBasics<'a>
            for $graph
            where N: 'a + Clone + Eq + Hash,
        {
            type NodeRef = <$inner_g as GraphBasics<'a>>::NodeRef;
            type EdgeRef = <$inner_g as GraphBasics<'a>>::EdgeRef;
            type EdgeIndex = <$inner_g as GraphBasics<'a>>::EdgeIndex;
            type NodeIndex = <$inner_g as GraphBasics<'a>>::NodeIndex;

            fn nodes(&'a self) -> impl Iterator<Item = Self::NodeRef> {
                self.inner.nodes.iter()
            }

            fn edges(&'a self) -> impl Iterator<Item = Self::EdgeRef> {
                self.inner.edges.iter()
            }
            fn node_count(&'a self) -> usize {
                self.inner.nodes.len()
            }

            fn edge_count(&'a self) -> usize {
                self.inner.edges.len()
            }
            fn is_directed(&self) -> bool {
                $dir
            }
            fn node(&'a self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> Option<<Self as GraphBasics<'a>>::NodeRef> {
                self.inner.nodes.get(node_index)
            }
            fn edge(&'a self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> Option<<Self as GraphBasics<'a>>::EdgeRef> {
                self.inner.edges.get(edge_index)
            }
            fn node_iter(&'a self, node_index: impl Iterator<Item = <Self as GraphBasics<'a>>::NodeIndex>) -> impl Iterator<Item = Option<<Self as GraphBasics<'a>>::NodeRef>> {
                node_index.map(|i| self.inner.node(i))
            }
            fn edge_iter(&'a self, edge_index: impl Iterator<Item = <Self as GraphBasics<'a>>::EdgeIndex>) -> impl Iterator<Item = Option<<Self as GraphBasics<'a>>::EdgeRef>> {
                edge_index.map(|i| self.inner.edge(i))
            }
        }

        impl<'a, N: 'a$(, $($gens),*)?$(, $(const $cgens: $ity),*)?> GraphWrapper<'a> for $graph
            where   $inner_g: GraphBasics<'a>,
                    N: 'a + Clone + Eq + Hash,{
            type Inner = $inner_g;

            fn into_inner(&'a self) -> &'a Self::Inner {
                &self.inner
            }
        }
    };
    (
        $graph:ty,
        $inner_g:ty,
        $dir:literal,
        reduce N = $node_weight:tt
        $(, <$($gens:tt),*>)?
        $(, |$(const $cgens:ident: $ity:ty),*|)?
    ) => {
        impl<'a, E$(, $($gens),*)?$(, $(const $cgens: $ity),*)?> GraphBasics<'a>
            for $graph
            where E: 'a + Clone + Eq + Hash,
        {
            type NodeRef = <$inner_g as GraphBasics<'a>>::NodeRef;
            type EdgeRef = <$inner_g as GraphBasics<'a>>::EdgeRef;
            type EdgeIndex = <$inner_g as GraphBasics<'a>>::EdgeIndex;
            type NodeIndex = <$inner_g as GraphBasics<'a>>::NodeIndex;

            fn nodes(&'a self) -> impl Iterator<Item = Self::NodeRef> {
                self.inner.nodes.iter()
            }

            fn edges(&'a self) -> impl Iterator<Item = Self::EdgeRef> {
                self.inner.edges.iter()
            }
            fn node_count(&'a self) -> usize {
                self.inner.nodes.len()
            }

            fn edge_count(&'a self) -> usize {
                self.inner.edges.len()
            }
            fn is_directed(&self) -> bool {
                $dir
            }
            fn node(&'a self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> Option<<Self as GraphBasics<'a>>::NodeRef> {
                self.inner.nodes.get(node_index)
            }
            fn edge(&'a self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> Option<<Self as GraphBasics<'a>>::EdgeRef> {
                self.inner.edges.get(edge_index)
            }
            fn node_iter(&'a self, node_index: impl Iterator<Item = <Self as GraphBasics<'a>>::NodeIndex>) -> impl Iterator<Item = Option<<Self as GraphBasics<'a>>::NodeRef>> {
                node_index.map(|i| self.inner.node(i))
            }
            fn edge_iter(&'a self, edge_index: impl Iterator<Item = <Self as GraphBasics<'a>>::EdgeIndex>) -> impl Iterator<Item = Option<<Self as GraphBasics<'a>>::EdgeRef>> {
                edge_index.map(|i| self.inner.edge(i))
            }
        }

        impl<'a, E: 'a$(, $($gens),*)?$(, $(const $cgens: $ity),*)?> GraphWrapper<'a> for $graph
            where   $inner_g: GraphBasics<'a>,
                    E: 'a + Clone + Eq + Hash,{
            type Inner = $inner_g;

            fn into_inner(&'a self) -> &'a Self::Inner {
                &self.inner
            }
        }
    };
    (
        $graph:ty,
        $inner_g:ty,
        $dir:literal
        $(, <$($gens:tt),*>)?
        $(, |$(const $cgens:ident: $ity:ty),*|)?
    ) => {
        impl<'a, N, E$(, $($gens),*)?$(, $(const $cgens: $ity),*)?> GraphBasics<'a>
            for $graph
            where N: 'a + Clone + Eq + Hash,
                  E: 'a + Clone + Eq + Hash,
        {
            type NodeRef = <$inner_g as GraphBasics<'a>>::NodeRef;
            type EdgeRef = <$inner_g as GraphBasics<'a>>::EdgeRef;
            type EdgeIndex = <$inner_g as GraphBasics<'a>>::EdgeIndex;
            type NodeIndex = <$inner_g as GraphBasics<'a>>::NodeIndex;

            fn nodes(&'a self) -> impl Iterator<Item = Self::NodeRef> {
                self.inner.nodes.iter()
            }

            fn edges(&'a self) -> impl Iterator<Item = Self::EdgeRef> {
                self.inner.edges.iter()
            }
            fn node_count(&'a self) -> usize {
                self.inner.nodes.len()
            }

            fn edge_count(&'a self) -> usize {
                self.inner.edges.len()
            }
            fn is_directed(&self) -> bool {
                $dir
            }
            fn node(&'a self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> Option<<Self as GraphBasics<'a>>::NodeRef> {
                self.inner.nodes.get(node_index)
            }
            fn edge(&'a self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> Option<<Self as GraphBasics<'a>>::EdgeRef> {
                self.inner.edges.get(edge_index)
            }
            fn node_iter(&'a self, node_index: impl Iterator<Item = <Self as GraphBasics<'a>>::NodeIndex>) -> impl Iterator<Item = Option<<Self as GraphBasics<'a>>::NodeRef>> {
                node_index.map(|i| self.inner.node(i))
            }
            fn edge_iter(&'a self, edge_index: impl Iterator<Item = <Self as GraphBasics<'a>>::EdgeIndex>) -> impl Iterator<Item = Option<<Self as GraphBasics<'a>>::EdgeRef>> {
                edge_index.map(|i| self.inner.edge(i))
            }
        }

        impl<'a, N: 'a, E: 'a$(, $($gens),*)?$(, $(const $cgens: $ity),*)?> GraphWrapper<'a> for $graph
            where   $inner_g: GraphBasics<'a>,
                    N: 'a + Clone + Eq + Hash,
                    E: 'a + Clone + Eq + Hash,{
            type Inner = $inner_g;

            fn into_inner(&'a self) -> &'a Self::Inner {
                &self.inner
            }
        }
    };
}

impl<'a, T, U> GraphBasics<'a> for U
where
    T: GraphBasics<'a> + 'a,
    U: Deref<Target = T>,
{
    type NodeRef = T::NodeRef;

    type EdgeRef = T::EdgeRef;

    type NodeIndex = T::NodeIndex;

    type EdgeIndex = T::EdgeIndex;

    fn nodes(&'a self) -> impl Iterator<Item = Self::NodeRef> {
        (**self).nodes()
    }

    fn node_count(&'a self) -> usize {
        (**self).node_count()
    }

    fn edges(&'a self) -> impl Iterator<Item = Self::EdgeRef> {
        (**self).edges()
    }

    fn edge_count(&'a self) -> usize {
        (**self).edge_count()
    }

    fn is_directed(&self) -> bool {
        (**self).is_directed()
    }

    fn node(&'a self, node_index: Self::NodeIndex) -> Option<Self::NodeRef> {
        (**self).node(node_index)
    }

    fn edge(&'a self, edge_index: Self::EdgeIndex) -> Option<Self::EdgeRef> {
        (**self).edge(edge_index)
    }

    fn node_iter(
        &'a self,
        node_index: impl Iterator<Item = Self::NodeIndex>,
    ) -> impl Iterator<Item = Option<Self::NodeRef>> {
        node_index.map(|i| (**self).node(i))
    }

    fn edge_iter(
        &'a self,
        edge_index: impl Iterator<Item = Self::EdgeIndex>,
    ) -> impl Iterator<Item = Option<Self::EdgeRef>> {
        edge_index.map(|i| (**self).edge(i))
    }
}

#[cfg(feature = "temporal")]
pub trait TemporalProperties<'a>: GraphBasics<'a> {
    type Inner: GraphBasics<'a>;
    fn step(&mut self) {
        *self.get_time_mut() += 1;
    }
    fn get_time(&self) -> usize;
    /// Use this method to jump forward and backward, maybe for snapshots,
    /// maybe to test whether stuff behaves the way you want it to.
    fn get_time_mut(&mut self) -> &mut usize;

    fn snapshot(&'a self) -> &'a Self::Inner;

    fn temporal_behaviour(
        &self,
        edge_index: <Self as GraphBasics<'a>>::EdgeIndex,
    ) -> Option<TemporalBehaviour>;
}

pub trait HypergraphBasics<'a>: GraphBasics<'a> {
    /// Returns none if the hypergraph is not uniform, or the size of the hyperedges if it is.
    /// A hypergraph is uniform if all hyperedges have the same number of nodes.
    /// For example, a hypergraph with hyperedges of size 3 is 3-uniform.
    fn uniform(&'a self) -> bool;

    /// Much like subgraphs, the dual of a hypergraph is not necessarily the same type as the original
    /// hypergraph. For example, the dual of a uniform hypergraph is not necessarily uniform.
    type DualType;
    fn dual(&'a self) -> Self::DualType;
}

/// Still a stub.
///
pub trait Generate<N, E, T: GraphType> {
    /// Make your own parser inside this function.
    fn from_file<P: AsRef<std::path::Path>>(path: P) -> Self;
    /// Unweighted Hypergraphs only.
    fn random_hypergraph(node_count: usize, edges_by_size: HashMap<usize, usize>) -> Self;
    fn random_weighted_hypergraph(
        node_count: usize,
        edges_by_size: HashMap<usize, usize>,
        node_weight_sampler: impl Fn() -> N,
        edge_weight_sampler: impl Fn() -> E,
    ) -> Self;
}

/// Stub.
pub trait StatisticalFilters {}

/// Stub.
pub trait Dynamics {}