hypergraph 3.0.0

Hypergraph is data structure library to create a directed hypergraph in which an hyperedge can join any number of vertices.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

use ahash::{
    AHashMap,
    AHashSet,
};

use crate::{
    HyperedgeIndex,
    HyperedgeTrait,
    Hypergraph,
    VertexIndex,
    VertexTrait,
    errors::HypergraphError,
};

impl<V, HE> Hypergraph<V, HE>
where
    V: VertexTrait,
    HE: HyperedgeTrait,
{
    /// Returns the induced subgraph for the given vertex set.
    ///
    /// The subgraph contains exactly the specified vertices (deduplicated and
    /// validated) and every hyperedge from the original graph whose vertices are
    /// all within that set. Vertex stable indexes are reassigned from `0` in
    /// sorted order; hyperedge stable indexes are similarly reassigned in
    /// original insertion order.
    ///
    /// Returns [`HypergraphError::VertexIndexNotFound`] for any invalid index.
    pub fn subgraph(
        &self,
        vertices: &[VertexIndex],
    ) -> Result<Hypergraph<V, HE>, HypergraphError<V, HE>> {
        // Deduplicate and sort for a deterministic, stable output order.
        let mut sorted: Vec<VertexIndex> = vertices.to_vec();
        sorted.sort();
        sorted.dedup();

        let vertex_set: AHashSet<VertexIndex> = sorted.iter().copied().collect();

        let mut sub = Hypergraph::new();
        let mut old_to_new: AHashMap<VertexIndex, VertexIndex> = AHashMap::new();

        for &old_idx in &sorted {
            let weight = self.get_vertex_weight(old_idx)?;
            let new_idx = sub.add_vertex(*weight)?;
            old_to_new.insert(old_idx, new_idx);
        }

        // Include hyperedges whose entire vertex set falls within the subgraph.
        let mut hyperedges: Vec<(HyperedgeIndex, &HE)> = self.hyperedges_iter().collect();
        hyperedges.sort_by_key(|(idx, _)| *idx);

        for (he_idx, _) in hyperedges {
            let he_vertices = self.get_hyperedge_vertices(he_idx)?;
            if he_vertices.iter().all(|v| vertex_set.contains(v)) {
                let new_vertices: Vec<VertexIndex> =
                    he_vertices.iter().map(|v| old_to_new[v]).collect();
                let he_weight = self.get_hyperedge_weight(he_idx)?;
                sub.add_hyperedge(new_vertices, *he_weight)?;
            }
        }

        Ok(sub)
    }
}