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
//!# Matt's HyperGraph Library (mhgl)
//!
//! A small library that provides three undirected hypergraph structures:
//! 1.`ConGraph` - a connectivity only option that uses `u32`'s as IDs for
//! nodes and `u64`'s for edge IDs. No data that can be stored within the
//! `ConGraph` structure itself and NodeIDs and EdgeIDs are simple incremented
//! counters started at 0.
//! 2. `HGraph` - An option generic over the types stored in both the nodes and
//! edges. Additionally generic over the size of integers `u8` through `u128`
//! to store NodeIDs and EdgeIDs with `u32` and `u64` as the default for the respective IDs.
//! 3. `KVGraph` - A key-value hypergraph where each node and edge allows you
//! to store simple values modeled after a simple subset of the Polars data
//! types. There are two features for this crate, "uuid" which is necessary to use the
//! `KVGraph` struct as `Uuid`s are used for both node and edge ids and "polars"
//! is necessary if you want to retreive dataframes out of the hypergraph.
//!
//! `ConGraph` and `KVGraph` are essentially wrappers around `HGraph` with
//! slightly tweaked apis for adding and deleting nodes or edges (for example
//! you don't need to provide data for adding nodes to a `ConGraph` but you do
//! for `HGraph`).
//!
//! The common behavior between these three structures is collected in the
//! `HyperGraph` trait, which mostly consists of various ways of collecting
//! "local" information about a node or a set of nodes within the hypergraph.
//! With a `HyperGraph` object you can query for the link of an edge or a set
//! of nodes, the maximal edges that contain a given edge, or the action of
//! boundary up and down operators on an edge or set of nodes. Consistent
//! throughout the trait is the ability to interact with a `HyperGraph` either
//! through edge ids or any type that can be
//! cast `AsRef` into a slice &[NodeID]. Whenever a slice or such is passed the
//! hypergraph will clone the NodeIDs, sort, and make sure no duplicates exist.
//! The only other trait in the crate for now is the `HgNode` trait which is
//! used to mark the types suitable for `HGraph`.
//!
//! ```rust
//! use mhgl::*;
//! let mut cg = ConGraph::new();
//! let nodes = cg.add_nodes(5);
//! let mut edges = Vec::new();
//! for ix in 1..nodes.len() {
//! let edge = cg.add_edge(&nodes[0..=ix]);
//! edges.push(edge);
//! }
//! let maxs_of_edge = cg.maximal_edges(&edges[0]);
//! let maxs_of_nodes = cg.maximal_edges_of_nodes([0, 1, 2]);
//!
//! assert_eq!(maxs_of_edge[0], edges[edges.len() - 1]);
//! assert_eq!(maxs_of_nodes[0], edges[edges.len() - 1]);
//! assert_eq!(cg.boundary_up(&edges[0]), vec![edges[1]]);
//!
//! #[derive(Debug)]
//! struct Foo(u8);
//!
//! #[derive(Debug)]
//! struct Bar(u32);
//!
//! let mut hg = HGraph::<Foo, Bar>::new();
//! let n0 = hg.add_node(Foo(1));
//! let n1 = hg.add_node(Foo(2));
//! let e = hg.add_edge(&[n0, n1], Bar(42)).unwrap();
//! let e_mut = hg.borrow_edge_mut(&e).unwrap();
//! e_mut.0 = 12;
//! let bar = hg.remove_edge(e).unwrap();
//! assert_eq!(bar.0, 12);
//!
//! let mut kvgraph = KVGraph::new();
//! let n0 = kvgraph.add_node_with_label("toronto");
//! let n1 = kvgraph.add_node_with_label("seattle");
//! let edge = kvgraph.add_edge_with_label(&[n0, n1], "AC123").unwrap();
//! kvgraph.insert(&n0, "darkness", 0.6);
//! kvgraph.insert(&n1, "darkness", 0.8);
//! let df = kvgraph.dataframe();
//! println!("{:}", df);
//! ```
//! The last line in the above code will output:
//! ```text
//!┌────────────┬───────────────────────────────────┬───────────────────────────────────┬───────────────────┬──────────┐
//! │ label ┆ id ┆ nodes ┆ labelled_nodes ┆ darkness │
//! │ --- ┆ --- ┆ --- ┆ --- ┆ --- │
//! │ str ┆ str ┆ str ┆ str ┆ f64 │
//! ╞════════════╪═══════════════════════════════════╪═══════════════════════════════════╪═══════════════════╪══════════╡
//! │ toronto ┆ 6347a42e-0bde-4d80-aad3-7e8c59d3… ┆ [6347a42e-0bde-4d80-aad3-7e8c59d… ┆ [toronto] ┆ 0.6 │
//! │ seattle ┆ 032e1a16-ec39-4045-8ebd-381c2b06… ┆ [032e1a16-ec39-4045-8ebd-381c2b0… ┆ [seattle] ┆ 0.8 │
//! │ AC123 ┆ 1b233128-22d2-4158-850d-b4b814d5… ┆ [1b233128-22d2-4158-850d-b4b814d… ┆ [seattle,toronto] ┆ null │
//! └────────────┴───────────────────────────────────┴───────────────────────────────────┴───────────────────┴──────────┘
//! ```
//! Currently data schema is shared between nodes and edges, which is
//! unfortunate.
//!
//!# Algorithms
//! Mostly under construction, currently there is only a simple random walk either using link,
//! boundary_up * boundary_down, and boundary_down * boundary_up to determine the next subset to move to. I plan to
//! port some algorithms, such as the connected components, s_walk, and homology algorithms from `HyperNetX` to this library over time.
//!
//! This library should be considered as an **alpha** version. Here are a few hypergraph libraries I found, the most mature of which is HyperNetX developed by Pacific Northwest National Laboratory (PNNL).
//! # Alternative Hypergraph Libraries
//! - HyperNetX (Python): The most complete hypergraph library with algorithms
//! for homology computations. Based on python and the underlying datastructure
//! seems to be pandas arrays.
//! - HypergraphDB (Java): A database backend for storing and querying data, seems unmaintained but probably was ahead of its time.
//! - Hypergraph (Rust): Appears very limited in scope and not maintained.
pub use ConGraph;
pub use EdgeSet;
pub use HGraph;
pub use HyperGraph;
pub use KVGraph;
pub use HgNode;