hypergraph/lib.rs
1//! Hypergraph is data structure library to generate directed [hypergraphs](https://en.wikipedia.org/wiki/Hypergraph).
2//!
3//! > A hypergraph is a generalization of a graph in which a hyperedge can join any number of vertices.
4//!
5//! ## Features
6//!
7//! This library enables you to:
8//!
9//! - represent **non-simple** hypergraphs with two or more hyperedges - with different weights - containing the exact same set of vertices
10//! - represent **self-loops** - i.e., hyperedges containing vertices directed to themselves one or more times
11//! - represent **unaries** - i.e., hyperedges containing a unique vertex
12//!
13//! Additional features:
14//!
15//! - Safe Rust implementation
16//! - Proper error handling
17//! - Stable indexes assigned for each hyperedge and each vertex
18//!
19//! ## Example
20//!
21//! Please notice that the hyperedges and the vertices must implement the
22//! [`HyperedgeTrait`](crate::HyperedgeTrait) and the [`VertexTrait`](crate::VertexTrait) respectively.
23//!
24//! ```
25//! use hypergraph::{HyperedgeIndex, Hypergraph, VertexIndex};
26//! use std::fmt::{Display, Formatter, Result};
27//!
28//! // Create a new struct to represent a person.
29//! #[derive(Debug, Copy, Clone, Hash, Eq, PartialEq)]
30//! pub struct Person<'a> {
31//! name: &'a str,
32//! }
33//!
34//! impl<'a> Person<'a> {
35//! pub fn new(name: &'a str) -> Self {
36//! Self { name }
37//! }
38//! }
39//!
40//! impl<'a> Display for Person<'a> {
41//! fn fmt(&self, f: &mut Formatter<'_>) -> Result {
42//! write!(f, "{}", self)
43//! }
44//! }
45//!
46//! // Create a new struct to represent a relation.
47//! #[derive(Debug, Copy, Clone, Hash, Eq, PartialEq)]
48//! pub struct Relation<'a> {
49//! cost: usize,
50//! name: &'a str,
51//! }
52//!
53//! impl<'a> Relation<'a> {
54//! pub fn new(name: &'a str, cost: usize) -> Self {
55//! Self { cost, name }
56//! }
57//! }
58//!
59//! impl<'a> Display for Relation<'a> {
60//! fn fmt(&self, f: &mut Formatter<'_>) -> Result {
61//! write!(f, "{}", self)
62//! }
63//! }
64//!
65//! impl<'a> Into<usize> for Relation<'a> {
66//! fn into(self) -> usize {
67//! self.cost
68//! }
69//! }
70//!
71//! fn main() -> std::result::Result<(), Box<dyn std::error::Error>> {
72//! let mut graph = Hypergraph::<Person, Relation>::new();
73//!
74//! // Create some folks.
75//! let ava_person = Person::new("Ava");
76//! let bianca_person = Person::new("Bianca");
77//! let charles_person = Person::new("Charles");
78//! let daena_person = Person::new("Daena");
79//! let ewan_person = Person::new("Ewan");
80//! let faarooq_person = Person::new("Faarooq");
81//! let ghanda_person = Person::new("Ghanda");
82//!
83//! // Add those to the graph as vertices.
84//! let ava = graph.add_vertex(ava_person)?;
85//! let bianca = graph.add_vertex(bianca_person)?;
86//! let charles = graph.add_vertex(charles_person)?;
87//! let daena = graph.add_vertex(daena_person)?;
88//! let ewan = graph.add_vertex(ewan_person)?;
89//! let faarooq = graph.add_vertex(faarooq_person)?;
90//! let ghanda = graph.add_vertex(ghanda_person)?;
91//!
92//! // Each vertex gets a unique index by insertion order.
93//! assert_eq!(ava, VertexIndex(0));
94//! assert_eq!(ghanda, VertexIndex(6));
95//!
96//! // Get the weight of a vertex.
97//! assert_eq!(graph.get_vertex_weight(VertexIndex(0)), Ok(&ava_person));
98//!
99//! // The hypergraph has seven vertices.
100//! assert_eq!(graph.count_vertices(), 7);
101//!
102//! // Create some relations.
103//! let cat_video = Relation::new("share a viral video with a cat", 1);
104//! let dog_video = Relation::new("share a viral video with a dog", 1);
105//! let beaver_video = Relation::new("share a viral video with a beaver", 1);
106//! let playing_online = Relation::new("play online", 1);
107//! let passing_ball = Relation::new("pass the ball", 1);
108//!
109//! // Add those to the graph as hyperedges.
110//! let first_relation = graph.add_hyperedge(vec![faarooq, ava, ghanda], cat_video)?;
111//! let second_relation = graph.add_hyperedge(vec![faarooq, ava, ghanda], dog_video)?;
112//! let third_relation = graph.add_hyperedge(vec![ewan, ava, bianca], beaver_video)?;
113//! let fourth_relation = graph.add_hyperedge(vec![daena], playing_online)?;
114//! let fifth_relation = graph.add_hyperedge(vec![ewan, charles, bianca, bianca, ewan], passing_ball)?;
115//!
116//! // Each hyperedge gets a unique index by insertion order.
117//! assert_eq!(first_relation, HyperedgeIndex(0));
118//! assert_eq!(fifth_relation, HyperedgeIndex(4));
119//!
120//! // Get the weight of a hyperedge.
121//! assert_eq!(graph.get_hyperedge_weight(HyperedgeIndex(0)), Ok(&cat_video));
122//!
123//! // Get the vertices of a hyperedge.
124//! assert_eq!(graph.get_hyperedge_vertices(HyperedgeIndex(0)), Ok(vec![faarooq, ava, ghanda]));
125//!
126//! // The hypergraph has 5 hyperedges.
127//! assert_eq!(graph.count_hyperedges(), 5);
128//!
129//! // Get the hyperedges of a vertex.
130//! assert_eq!(graph.get_vertex_hyperedges(VertexIndex(0)), Ok(vec![first_relation, second_relation, third_relation]));
131//! assert_eq!(graph.get_full_vertex_hyperedges(VertexIndex(0)), Ok(vec![vec![faarooq, ava, ghanda], vec![faarooq, ava, ghanda], vec![ewan, ava, bianca]]));
132//!
133//! // Get the intersection of some hyperedges.
134//! assert_eq!(graph.get_hyperedges_intersections(vec![second_relation, third_relation]), Ok(vec![ava]));
135//!
136//! // Find a hyperedge containing a connection between two vertices.
137//! assert_eq!(graph.get_hyperedges_connecting(bianca, bianca), Ok(vec![fifth_relation]));
138//!
139//! // Get the adjacent vertices from a vertex.
140//! assert_eq!(graph.get_adjacent_vertices_from(VertexIndex(0)), Ok(vec![bianca, ghanda]));
141//!
142//! // Get the adjacent vertices to a vertex.
143//! assert_eq!(graph.get_adjacent_vertices_to(VertexIndex(0)), Ok(vec![ewan, faarooq]));
144//!
145//! // Find the shortest paths between some vertices.
146//! assert_eq!(graph.get_dijkstra_connections(faarooq, bianca), Ok(vec![(faarooq, None), (ava, Some(first_relation)), (bianca, Some(third_relation))]));
147//!
148//! // Update the weight of a vertex.
149//! graph.update_vertex_weight(ava, Person::new("Avā"))?;
150//!
151//! // Update the weight of a hyperedge.
152//! graph.update_hyperedge_weight(third_relation, Relation::new("share a viral video with a capybara", 1))?;
153//!
154//! // Update the vertices of a hyperedge.
155//! graph.update_hyperedge_vertices(third_relation, vec![ewan, ava, daena])?;
156//!
157//! // Remove a hyperedge.
158//! graph.remove_hyperedge(first_relation)?;
159//!
160//! // Remove a vertex.
161//! graph.remove_vertex(ewan)?;
162//!
163//! // Reverse a hyperedge.
164//! graph.reverse_hyperedge(fifth_relation)?;
165//!
166//! // Get the in-degree of a vertex.
167//! assert_eq!(graph.get_vertex_degree_in(ava), Ok(1));
168//!
169//! // Get the out-degree of a vertex.
170//! assert_eq!(graph.get_vertex_degree_out(ghanda), Ok(0));
171//!
172//! // Contract a hyperedge's vertices.
173//! graph.contract_hyperedge_vertices(fifth_relation, vec![bianca, charles], bianca)?;
174//!
175//! // Join some hyperedges.
176//! graph.join_hyperedges(&[fifth_relation, third_relation]);
177//!
178//! // Clear the hyperedges.
179//! graph.clear_hyperedges()?;
180//!
181//! // Clear the whole hypergraph.
182//! graph.clear();
183//!
184//! Ok(())
185//! }
186//! ```
187
188#[doc(hidden)]
189pub mod core;
190
191// Reexport of the public API.
192#[doc(inline)]
193pub use crate::core::*;