hypergraphx 0.0.5

use super::*;
/// This trait provides properties of directed graphs, such as in and out edges, strongly and
/// weakly connected components, and directed incidence and neighbour relationships.
///
/// It is implemented only for Directed Graphs.
///
/// Any method that accepts an index as an argument returns `Option<_>`, which is `None`
/// when the index is invalid.
pub trait DiGraphProperties<'a>: GraphBasics<'a> {
    fn in_edges(
        &'a self,
        node_index: <Self as GraphBasics<'a>>::NodeIndex,
    ) -> Option<HashSet<<Self as GraphBasics<'a>>::EdgeIndex>>;
    fn in_edge_count(&'a self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> Option<usize>;
    fn out_edges(
        &'a self,
        node_index: <Self as GraphBasics<'a>>::NodeIndex,
    ) -> Option<HashSet<<Self as GraphBasics<'a>>::EdgeIndex>>;
    fn out_edge_count(&'a self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> Option<usize>;
    fn in_neighbours(
        &'a self,
        node_index: <Self as GraphBasics<'a>>::NodeIndex,
    ) -> Option<HashSet<<Self as GraphBasics<'a>>::NodeIndex>>;
    fn out_neighbours(
        &'a self,
        node_index: <Self as GraphBasics<'a>>::NodeIndex,
    ) -> Option<HashSet<<Self as GraphBasics<'a>>::NodeIndex>>;

    fn in_neighbour_count(
        &'a self,
        node_index: <Self as GraphBasics<'a>>::NodeIndex,
    ) -> Option<usize>;
    fn out_neighbour_count(
        &'a self,
        node_index: <Self as GraphBasics<'a>>::NodeIndex,
    ) -> Option<usize>;

    /// Uses Tarjan's SCC algorithm.
    fn strongly_connected_components(&'a self) -> Vec<Vec<usize>>;
    fn is_strongly_connected(&'a self) -> bool {
        self.strongly_connected_components().len() == 1
    }
    /// Returns the indices of the nodes in the strong component containing the node at `node_index`.
    fn strong_component(
        &'a self,
        node_index: <Self as GraphBasics<'a>>::NodeIndex,
    ) -> Option<Vec<usize>>;
    /// Clones the strong component of the graph containing the node at `node_index`.
    fn extract_strong_component(
        &'a self,
        node_index: <Self as GraphBasics<'a>>::NodeIndex,
    ) -> Option<Self::Subgraph>;

    /// Returns a directed acyclic graph (DAG) of the strongly connected components.
    /// Relatively fast, as there's no looping beyond the SCC algorithm itself and adding all the edges.
    fn condense(&'a self) -> DiGraph<(), ()>;

    /// Don't use this unless you really have to.
    ///
    /// So the nice thing about Tarjan's algorithm, which is the current implementation of SCC in the graphs provided,
    /// is that no extra computation is needed to create a DAG of the strongly connected components. You lose this advantage
    /// with this method because it requires enumerating each edge crossing strong components, which is *O(|E|)* , i.e. slow.
    fn condense_with<F1, F2, N, E>(&'a self, node_collate: F1, edge_collate: F2) -> DiGraph<N, E>
    where
        F1: Fn(&[<Self as GraphBasics<'_>>::NodeRef]) -> N,
        F2: Fn(&[<Self as GraphBasics<'_>>::EdgeRef]) -> E,
        N: Clone + Eq + Hash,
        E: Clone + Eq + Hash,
    {
        let sccs = self.strongly_connected_components();
        let mut dag = DiGraph::new();
        dag.add_nodes(sccs.iter().map(|c| {
            node_collate(
                c.iter()
                    .map(|i| self.node((*i).into()).unwrap())
                    .collect::<Vec<_>>()
                    .as_slice(),
            )
        }));
        for ((u_index, u), (v_index, v)) in sccs.iter().enumerate().tuple_combinations() {
            let mut fwd = HashSet::new();
            let mut rev = HashSet::new();
            u.iter().cartesian_product(v.iter()).for_each(|(i, j)| {
                let (f, r) = self.edges_connecting((*i).into(), (*j).into()).unwrap();
                fwd.extend(f);
                rev.extend(r);
            });
            if !fwd.is_empty() {
                dag.add_edge(
                    edge_collate(
                        &self
                            .edge_iter(fwd.into_iter())
                            .filter_map(|x| x)
                            .collect::<Vec<_>>(),
                    ),
                    [u_index],
                    [v_index],
                )
                .unwrap();
            }
            if !rev.is_empty() {
                dag.add_edge(
                    edge_collate(
                        &self
                            .edge_iter(rev.into_iter())
                            .filter_map(|x| x)
                            .collect::<Vec<_>>(),
                    ),
                    [v_index],
                    [u_index],
                )
                .unwrap();
            }
        }

        dag
    }

    /// Pretends the graph is undirected and finds components.
    fn weakly_connected_components(&'a self) -> Vec<Vec<usize>>;
    fn is_weakly_connected(&'a self) -> bool {
        self.weakly_connected_components().len() == 1
    }
    /// Returns the indices of the nodes in the weak component containing the node at `node_index`.
    fn weak_component(
        &'a self,
        node_index: <Self as GraphBasics<'a>>::NodeIndex,
    ) -> Option<Vec<usize>>;
    fn extract_weak_component(
        &'a self,
        node_index: <Self as GraphBasics<'a>>::NodeIndex,
    ) -> Option<Self::Subgraph>;

    fn in_degree(&'a self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> Option<usize>;
    fn out_degree(&'a self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> Option<usize>;
    /// Nice for analysis.
    fn in_degree_sequence(&'a self) -> Vec<usize> {
        (0..self.node_count())
            .map(|n| self.in_edge_count(n.into()).unwrap())
            .collect()
    }
    /// Nice for analysis.
    fn out_degree_sequence(&'a self) -> Vec<usize> {
        (0..self.node_count())
            .map(|n| self.out_edge_count(n.into()).unwrap())
            .collect()
    }

    type Subgraph;

    fn source(
        &'a self,
        edge_index: <Self as GraphBasics<'a>>::EdgeIndex,
    ) -> Option<HashSet<<Self as GraphBasics<'a>>::NodeIndex>>;
    fn target(
        &'a self,
        edge_index: <Self as GraphBasics<'a>>::EdgeIndex,
    ) -> Option<HashSet<<Self as GraphBasics<'a>>::NodeIndex>>;

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

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

        let aset = self.in_edges(a)?;
        let bset = self.out_edges(b)?;

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

        Some(out)
    }

    // fn disorient<N, E>(&'a self) -> UndirectedHypergraph<N, E> {
    //     let mut h = UndirectedHypergraph::new();
    //     h.add_nodes(self.nodes().map(|n| n.clone()));
    //     // for (i, e) in self.edges().enumerate() {
    //     //     let mut nodes = self.source(i).into_iter().chain(self.target(i)).collect::<Vec<_>>();
    //     //     if nodes.len() < 2 {
    //     //         continue;
    //     //     }
    //     //     h.add_edge(nodes[0].clone(), nodes[1].clone());
    //     // }
    //     h.add_edges((0..self.edge_count()).map(|i| UndirectedEdge {
    //         weight: self.edge_weight(i.into()).cloned(),
    //         nodes: self.source(i.into()).iter().chain(self.target(i.into()).iter()).cloned().collect()
    //     }));
    //     h
    // }
}

/// This trait provides properties of directed hypergraphs, such as in and out orders, uniformity,
/// and dual graphs.
pub trait DirectedHypergraphProperties<'a, N, E>:
    DiGraphProperties<'a> + HypergraphBasics<'a>
{
    fn in_order(&'a self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> Option<usize>;
    fn out_order(&'a self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> Option<usize>;
    fn in_order_sequence(&'a self) -> Vec<usize> {
        (0..self.edge_count())
            .map(|e| self.in_order(e.into()).unwrap())
            .collect()
    }
    fn out_order_sequence(&'a self) -> Vec<usize> {
        (0..self.edge_count())
            .map(|e| self.out_order(e.into()).unwrap())
            .collect()
    }
    fn in_rank(&'a self) -> usize {
        (0..self.edge_count())
            .map(|e| self.in_order(e.into()).unwrap())
            .max()
            .unwrap_or(0)
    }
    fn out_rank(&'a self) -> usize {
        (0..self.edge_count())
            .map(|e| self.out_order(e.into()).unwrap())
            .max()
            .unwrap_or(0)
    }
    /// Provides an immutable view of the directed hypergraph as a `DiGraph`, where each hyperedge is replaced by
    /// {in_order * out_order} edges connecting all source nodes to all target nodes in the hyperedge.
    fn digraph_view(&'a self) -> DiGraph<&'a N, &'a E>;
    /// Returns a vec of edges mapping the given sets of nodes.
    /// For Simple Directed Hypergraphs, there is at most one such edge.
    ///
    fn edges_mapping(
        &'a self,
        a: &[<Self as GraphBasics<'a>>::NodeIndex],
        b: &[<Self as GraphBasics<'a>>::NodeIndex],
    ) -> Option<Vec<<Self as GraphBasics<'a>>::EdgeIndex>> {
        if a.is_empty() || b.is_empty() {
            return Some(Vec::new());
        }
        let mut wset = self.out_edges(a[0])?;
        for &node_index in &a[1..] {
            let eset = self.out_edges(node_index)?;
            wset.retain(|x| eset.contains(x));
        }
        for &node_index in b {
            let eset = self.in_edges(node_index)?;
            wset.retain(|x| eset.contains(x));
        }
        Some(wset.into_iter().collect())
    }
}