hypergraph 3.0.0

pub(crate) mod bi_hash_map;
#[doc(hidden)]
pub mod errors;
#[doc(hidden)]
pub mod hyperedges;
mod indexes;
#[doc(hidden)]
pub mod iterator;
mod shared;
#[doc(hidden)]
mod types;
mod utils;
#[doc(hidden)]
pub mod vertices;

use std::{
    fmt::{
        Debug,
        Display,
        Formatter,
        Result,
    },
    hash::Hash,
    ops::Deref,
};

use bi_hash_map::BiHashMap;
use types::{
    AIndexSet,
    ARandomState,
};

// Reexport indexes at this level.
pub use crate::core::indexes::{
    HyperedgeIndex,
    VertexIndex,
};
pub use crate::core::iterator::{
    HypergraphBorrowingIterator,
    HypergraphIterator,
};

/// Shared Trait for the vertices.
/// Must be implemented to use the library.
pub trait VertexTrait: Copy + Debug + Display + Eq + Hash + Send + Sync {}

impl<T> VertexTrait for T where T: Copy + Debug + Display + Eq + Hash + Send + Sync {}

/// Shared Trait for the hyperedges.
/// Must be implemented to use the library.
pub trait HyperedgeTrait: VertexTrait + Into<usize> {}

impl<T> HyperedgeTrait for T where T: VertexTrait + Into<usize> {}

/// A `HyperedgeKey` is a representation of both the vertices and the weight
/// of a hyperedge, used as a key in the hyperedges set.
/// In a non-simple hypergraph, since the same vertices can be shared by
/// different hyperedges, the weight is also included in the key to keep
/// it unique.
#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub(crate) struct HyperedgeKey<HE> {
    vertices: Vec<usize>,
    weight: HE,
}

impl<HE> HyperedgeKey<HE> {
    /// Creates a new `HyperedgeKey` from the given vertices and weight.
    pub(crate) fn new(vertices: Vec<usize>, weight: HE) -> HyperedgeKey<HE> {
        Self { vertices, weight }
    }
}

impl<HE> Deref for HyperedgeKey<HE> {
    type Target = HE;

    fn deref(&self) -> &HE {
        &self.weight
    }
}

/// A directed hypergraph composed of generic vertices and hyperedges.
#[derive(Clone)]
#[cfg_attr(
    feature = "serde",
    derive(serde::Serialize, serde::Deserialize),
    serde(bound(
        serialize = "V: serde::Serialize, HE: serde::Serialize",
        deserialize = "V: serde::Deserialize<'de>, HE: serde::Deserialize<'de> + Eq + std::hash::Hash"
    ))
)]
pub struct Hypergraph<V, HE> {
    /// Vertices are stored as a vec of `(weight, hyperedge-index-set)` pairs.
    /// Position in the vec is the internal index. Weights are not required to
    /// be unique — identity is the stable `VertexIndex`, not the weight.
    vertices: Vec<(V, AIndexSet<usize>)>,

    /// Hyperedges are stored as a set whose unique keys are a combination of
    /// vertices indexes and a weight. Two or more hyperedges can contain
    /// the exact same vertices (non-simple hypergraph).
    hyperedges: AIndexSet<HyperedgeKey<HE>>,

    /// Bi-directional map for hyperedges.
    hyperedges_mapping: BiHashMap<HyperedgeIndex>,

    /// Bi-directional map for vertices.
    vertices_mapping: BiHashMap<VertexIndex>,

    /// Stable index generation counter for hyperedges.
    hyperedges_count: usize,

    /// Stable index generation counter for vertices.
    vertices_count: usize,
}

impl<V, HE> Debug for Hypergraph<V, HE>
where
    V: Debug,
    HE: Debug,
{
    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
        f.debug_struct("Hypergraph")
            .field("vertices", &self.vertices)
            .field("hyperedges", &self.hyperedges)
            .finish_non_exhaustive()
    }
}

impl<V, HE> Display for Hypergraph<V, HE>
where
    V: VertexTrait,
    HE: HyperedgeTrait,
{
    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
        let mut vertices: Vec<(VertexIndex, &V)> = self.vertices_iter().collect();
        vertices.sort_by_key(|(idx, _)| *idx);

        write!(f, "Hypergraph {{ vertices: [")?;
        for (i, (idx, weight)) in vertices.iter().enumerate() {
            if i > 0 {
                write!(f, ", ")?;
            }
            write!(f, "{}: {}", idx.0, weight)?;
        }

        write!(f, "], hyperedges: [")?;
        let mut hyperedges: Vec<(HyperedgeIndex, &HE)> = self.hyperedges_iter().collect();
        hyperedges.sort_by_key(|(idx, _)| *idx);

        for (i, (idx, weight)) in hyperedges.iter().enumerate() {
            if i > 0 {
                write!(f, ", ")?;
            }
            write!(f, "{}: {} [", idx.0, weight)?;
            if let Ok(vertex_indexes) = self.get_hyperedge_vertices(*idx) {
                for (j, v_idx) in vertex_indexes.iter().enumerate() {
                    if j > 0 {
                        write!(f, " → ")?;
                    }
                    if let Ok(v_weight) = self.get_vertex_weight(*v_idx) {
                        write!(f, "{v_weight}")?;
                    }
                }
            }
            write!(f, "]")?;
        }

        write!(f, "] }}")
    }
}

impl<V, HE> Default for Hypergraph<V, HE>
where
    V: VertexTrait,
    HE: HyperedgeTrait,
{
    fn default() -> Self {
        Hypergraph::new()
    }
}

/// Hypergraph implementations.
impl<V, HE> Hypergraph<V, HE>
where
    V: VertexTrait,
    HE: HyperedgeTrait,
{
    /// Returns `true` if the hypergraph contains no vertices.
    ///
    /// Because hyperedges require at least one vertex to exist, an empty vertex
    /// set implies an empty hyperedge set as well.
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.vertices.is_empty()
    }

    /// Clears the hypergraph.
    pub fn clear(&mut self) {
        // Clear the hyperedges and vertices sets while keeping their capacities.
        self.hyperedges.clear();
        self.vertices.clear();

        // Reset the mappings.
        self.hyperedges_mapping = BiHashMap::default();
        self.vertices_mapping = BiHashMap::default();

        // Reset the counters.
        self.hyperedges_count = 0;
        self.vertices_count = 0;
    }

    /// Creates a new hypergraph with no allocation.
    #[must_use]
    pub fn new() -> Self {
        Hypergraph::with_capacity(0, 0)
    }

    /// Creates a new hypergraph with the specified capacity.
    #[must_use]
    pub fn with_capacity(vertices: usize, hyperedges: usize) -> Self {
        Hypergraph {
            hyperedges_count: 0,
            hyperedges_mapping: BiHashMap::default(),
            hyperedges: AIndexSet::with_capacity_and_hasher(hyperedges, ARandomState::default()),
            vertices_count: 0,
            vertices_mapping: BiHashMap::default(),
            vertices: Vec::with_capacity(vertices),
        }
    }
}