hypergraphx 0.0.5

use std::hash::Hash;

use nalgebra::DMatrix;

use super::*;
/// This trait provides a few basic properties of graphs, such as node degree, connected components,
/// and incidence and neighbour relationships.
///
/// It is implemented only for Undirected Graphs.
///
///
/// Any method that accepts an index as an argument returns `Option<_>`, which is `None`
/// when the index is invalid.
pub trait GraphProperties<'a>: GraphBasics<'a> {
    fn incident_edges(
        &'a self,
        node_index: <Self as GraphBasics<'a>>::NodeIndex,
    ) -> Option<HashSet<<Self as GraphBasics<'a>>::EdgeIndex>>;
    fn contained_nodes(
        &'a self,
        edge_index: <Self as GraphBasics<'a>>::EdgeIndex,
    ) -> Option<HashSet<<Self as GraphBasics<'a>>::NodeIndex>>;
    fn neighbours(
        &'a self,
        node_index: <Self as GraphBasics<'a>>::NodeIndex,
    ) -> Option<HashSet<<Self as GraphBasics<'a>>::NodeIndex>>;

    /// While the neighbour count can be made a default method, there are more efficient ways
    /// to *count* the neighbours than to collect them into a set.
    fn neighbour_count(&'a self, node_index: usize) -> Option<usize>;
    fn degree(&'a self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> Option<usize>;
    fn degree_by_order(
        &'a self,
        node_index: <Self as GraphBasics<'a>>::NodeIndex,
        order: usize,
    ) -> Option<usize>;

    /// This function is nice for analysis. For example, it can be used to see if the graph is even,
    /// which determines the existence of an Eulerian tour.
    fn degree_sequence(&'a self) -> Vec<usize> {
        (0..self.node_count())
            .map(|n| self.degree(n.into()).unwrap())
            .collect()
    }

    fn degree_sequence_by_order(&'a self, order: usize) -> Vec<usize> {
        (0..self.node_count())
            .map(|n| self.degree_by_order(n.into(), order).unwrap())
            .collect()
    }

    /// Returns the indices of the nodes in each component.
    fn connected_components(&'a self) -> Vec<Vec<<Self as GraphBasics<'a>>::NodeIndex>>;
    fn is_connected(&'a self) -> bool {
        self.connected_components().len() == 1
    }

    /// Sometimes a subgraph, obtained by restricting the nodes (for example), is not the same type
    /// as the original graph. A subhypergraph induced on a uniform hypergraph need not be uniform.
    /// This is why we have a separate associated type for subgraphs.
    type Subgraph;

    /// Returns the indices of the nodes in the component containing the node at `node_index`.
    fn component(&'a self, node_index: usize) -> Option<Vec<usize>>;

    /// Clones the component of the graph containing the node at `node_index`.
    fn extract_component(&'a self, node_index: usize) -> Option<Self::Subgraph>;

    /// Returns a vec of edges connecting the two nodes `a` and `b`.
    fn edges_connecting(
        &'a self,
        a: <Self as GraphBasics<'a>>::NodeIndex,
        b: <Self as GraphBasics<'a>>::NodeIndex,
    ) -> Option<Vec<<Self as GraphBasics<'a>>::EdgeIndex>> {
        let aset = self.incident_edges(a)?;
        let bset = self.incident_edges(b)?;

        let out = aset.intersection(&bset).map(|e| *e).collect::<Vec<_>>();

        Some(out)
    }
}

/// Statistics.
pub trait Measures<'a, N, E>: GraphProperties<'a> {
    fn degree_distribution(&'a self) -> HashMap<usize, usize> {
        let mut dist = HashMap::new();
        for node_index in 0..self.node_count() {
            let degree = self.degree(node_index.into()).unwrap();
            *dist.entry(degree).or_insert(0) += 1;
        }
        dist
    }
    fn jaccard_similarity(&'a self, a: Self::EdgeIndex, b: Self::EdgeIndex) -> Option<f64> {
        let a_nodes = self.contained_nodes(a)?;
        let b_nodes = self.contained_nodes(b)?;

        let intersection = a_nodes.intersection(&b_nodes).count();
        let union = a_nodes.union(&b_nodes).count();

        Some(if union == 0 {
            0.0
        } else {
            intersection as f64 / union as f64
        })
    }
    fn jaccard_similarity_matrix(&'a self) -> DMatrix<f64> {
        let mut matrix = DMatrix::zeros(self.edge_count(), self.edge_count());
        for (i, j) in (0..self.edge_count()).cartesian_product(0..self.edge_count()) {
            if let Some(sim) = self.jaccard_similarity(i.into(), j.into()) {
                matrix[(i, j)] = sim;
            }
        }
        matrix
    }
}

impl<'a, N, E, T> Measures<'a, N, E> for T
where
    T: GraphProperties<'a>,
    N: 'a + Clone + Eq + Hash,
    E: 'a + Clone + Eq + Hash,
{
}

pub trait EigenMeasures<'a, N, E>: Measures<'a, N, E> {
    fn cec(&'a self) -> Vec<f64>;
    fn zec(&'a self) -> Vec<f64>;
    fn hec(&'a self) -> Vec<f64>;
}

pub trait Centralities<'a, N, E>: Measures<'a, N, E> {
    fn closeness_centrality(&'a self) -> Vec<f64>;
    fn betweenness_centrality(&'a self) -> Vec<f64>;
    fn closeness_centrality_nodes(&'a self) -> Vec<f64>;
    fn betweenness_centrality_nodes(&'a self) -> Vec<f64>;

    fn shgraph_centrality(&'a self) -> Vec<f64>;
}

/// This trait provides properties of hypergraphs, such as edge order, uniformity, and dual graphs.
/// The dual of a hypergraph is a hypergraph where the nodes and edges are swapped.
pub trait HypergraphProperties<'a, N, E>: GraphProperties<'a> + HypergraphBasics<'a> {
    fn order(&'a self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> Option<usize>;
    fn order_sequence(&'a self) -> Vec<usize> {
        (0..self.edge_count())
            .map(|e| self.order(e.into()).unwrap())
            .collect()
    }
    fn rank(&'a self) -> usize {
        (0..self.edge_count())
            .map(|e| self.contained_nodes(e.into()).unwrap().len())
            .max()
            .unwrap_or(0)
    }

    /// Provides an immutable view of the hypergraph as a `Graph`, where each hyperedge is replaced by
    /// {order \choose 2} edges connecting all pairs of nodes in the hyperedge.
    fn graph_view(&'a self) -> Graph<&'a N, &'a E>;

    /// For Simple Hypergraphs, there is at most one such edge.
    /// However, all graph types presented in this library allow multiple edges
    /// to contain the same set of nodes.
    fn edges_containing(
        &'a self,
        a: &[<Self as GraphBasics<'a>>::NodeIndex],
    ) -> Option<Vec<<Self as GraphBasics<'a>>::EdgeIndex>> {
        if a.is_empty() {
            return Some(Vec::new());
        }
        let mut wset = self.incident_edges(a[0])?;
        for &node_index in &a[1..] {
            let eset = self.incident_edges(node_index)?;
            wset.retain(|x| eset.contains(x));
        }
        Some(wset.into_iter().collect())
    }
}