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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

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::{AIndexMap, AIndexSet, ARandomState};

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

/// 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)]
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.
pub struct Hypergraph<V, HE> {
    /// Vertices are stored as a map whose unique keys are the weights
    /// and the values are a set of the hyperedges indexes which include
    /// the current vertex.
    vertices: AIndexMap<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: Eq + Hash + 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> 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,
{
    /// 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.
    pub fn new() -> Self {
        Hypergraph::with_capacity(0, 0)
    }

    /// Creates a new hypergraph with the specified capacity.
    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: AIndexMap::with_capacity_and_hasher(vertices, ARandomState::default()),
        }
    }
}