hypergraph 4.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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

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

impl<V, HE> IntoIterator for Hypergraph<V, HE>
where
    V: VertexTrait,
    HE: HyperedgeTrait,
{
    type Item = (HE, Vec<V>);
    type IntoIter = HypergraphIterator<V, HE>;

    fn into_iter(self) -> Self::IntoIter {
        HypergraphIterator {
            hypergraph: self,
            index: 0,
        }
    }
}

impl<'a, V, HE> IntoIterator for &'a Hypergraph<V, HE>
where
    V: VertexTrait,
    HE: HyperedgeTrait,
{
    type Item = (&'a HE, Vec<&'a V>);
    type IntoIter = HypergraphBorrowingIterator<'a, V, HE>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<V, HE> Hypergraph<V, HE>
where
    V: VertexTrait,
    HE: HyperedgeTrait,
{
    /// Returns a borrowing iterator over the hyperedges as `(&HE, Vec<&V>)` tuples.
    #[must_use]
    pub fn iter(&self) -> HypergraphBorrowingIterator<'_, V, HE> {
        HypergraphBorrowingIterator {
            hypergraph: self,
            index: 0,
        }
    }

    /// Returns an iterator over all vertices as `(VertexIndex, &V)` pairs, in insertion order.
    #[must_use = "the iterator is lazy and must be consumed"]
    pub fn vertices_iter(&self) -> impl Iterator<Item = (VertexIndex, &V)> + '_ {
        self.vertices
            .iter()
            .map(|(&idx, (weight, _))| (idx, weight))
    }

    /// Returns an iterator over all hyperedges as `(HyperedgeIndex, &HE)` pairs, in insertion order.
    #[must_use = "the iterator is lazy and must be consumed"]
    pub fn hyperedges_iter(&self) -> impl Iterator<Item = (HyperedgeIndex, &HE)> + '_ {
        self.hyperedges
            .iter()
            .map(|(&idx, (_, weight))| (idx, weight))
    }
}

/// A consuming iterator over a [`Hypergraph`].
#[derive(Debug)]
pub struct HypergraphIterator<V, HE>
where
    V: VertexTrait,
    HE: HyperedgeTrait,
{
    hypergraph: Hypergraph<V, HE>,
    index: usize,
}

impl<V, HE> Iterator for HypergraphIterator<V, HE>
where
    V: VertexTrait,
    HE: HyperedgeTrait,
{
    type Item = (HE, Vec<V>);

    fn next(&mut self) -> Option<Self::Item> {
        let (_, (vertices, weight)) = self.hypergraph.hyperedges.get_index(self.index)?;
        self.index += 1;

        let vertex_weights: Option<Vec<V>> = vertices
            .iter()
            .map(|v_idx| self.hypergraph.vertices.get(v_idx).map(|(w, _)| *w))
            .collect();

        vertex_weights.map(|vw| (*weight, vw))
    }
}

/// A borrowing iterator over a [`Hypergraph`].
#[derive(Debug)]
pub struct HypergraphBorrowingIterator<'s, V, HE>
where
    V: VertexTrait,
    HE: HyperedgeTrait,
{
    hypergraph: &'s Hypergraph<V, HE>,
    index: usize,
}

impl<'s, V, HE> Iterator for HypergraphBorrowingIterator<'s, V, HE>
where
    V: VertexTrait,
    HE: HyperedgeTrait,
{
    type Item = (&'s HE, Vec<&'s V>);

    fn next(&mut self) -> Option<Self::Item> {
        let (_, (vertices, weight)) = self.hypergraph.hyperedges.get_index(self.index)?;
        self.index += 1;

        let vertex_weights: Option<Vec<&'s V>> = vertices
            .iter()
            .map(|v_idx| self.hypergraph.vertices.get(v_idx).map(|(w, _)| w))
            .collect();

        vertex_weights.map(|vw| (weight, vw))
    }
}