Crate rshyper

Expand description

§rshyper

Welcome to the rshyper crate - a Rust package providing a comprehensive framework for creating, manipulating, and analyzing hypergraphs using a myriad of mathematical and algorithmic techniques. The crate is designed to be flexible and modular enabled via heavy feature-gating throughout the framework.

§Background

Before diving in to the technical side of things, let’s start by defining several terms commonly used in the definition and implementation of hypergraphs.

§Terms

edge: a hyperedge is a generalization of an edge in a graph, allowing it to connect any number of vertices.
link: here, a link defines the layout of an edge providing a way to connect vertices together.
node a node is a complete vertex in that it is considered to be weighted.
point: here, a point is a synonym for a vertex, and is used to define the position of a vertex within the hypergraph.
surface: a surface is a synonym for an edge, often used here to describe iterators directly yielding (mutable) references to the “Edge Values” of the hypergraph.
vertex: a vertex is an unweighted node defining a point within the hypergraph.

§Hypergraphs

A hypergraph is an abstraction of a graph that allows edges to connect any number of vertices. This flexible data-strcture is highly mathematical, yet, extremely useful in many applications such as database design, network analysis, combinatorial optimization, modeling topological spaces, and more.

§Definition 1:

Formally, a directed hypergraph is a pair H = (V,E) where V is a set of vertices and E is a set of hyperedges. Each hyperedge e ∈ E is a subset of V that can contain

§Features

hyper_map: enables the HyperMap implementation, a hash-based hypergraph structure
macros: enables the implemented macros for streamlining graph management

§Dependencies

Note: While the alloc and std libraries are feature-gated, they are required for anything useful in this crate; both are enabled by default.

rayon: enables parallel processing capabilities using the rayon crate
serde: enables serialization and deserialization of hypergraphs using the serde crate

§Examples

For more detailed examples, please refer to the examples directory.

§Example 1: Basic Usage

use rshyper::{HyperMap, Weight};

let mut graph = HyperMap::<usize, usize>::undirected();
// add some unweighted vertices
let v0 = graph.add_vertex().expect("failed to add vertex");
let v1 = graph.add_vertex().expect("failed to add vertex");
// add a weighted node
let v2 = graph.add_node(Weight(10)).expect("failed to add node");
// create some edges using those nodes
let e0 = graph.add_link([v0, v1]).expect("failed to add edge");
let e1 = graph.add_link([v1, v2]).expect("failed to add edge");
// create a surface (weighted edge) using the nodes
let e3 = graph.add_edge([v0, v2], Weight(5)).expect("failed to add surface");

Modules§

algo: the algo module focuses on implementing algorithms and operators for hypergraphs
attrs: this module implements the GraphProps trait and provides a concrete implementation with the Attrs struct. These objects are used to define the attributes of a hypergraph such as the type of index used to identify vertices and edges as well as the type of graph (directed or undirected).
edge: this module focuses on the Edge implementation, providing additional types, traits, and representations for edges in a hypergraph.
error: this module implements the Error type for the rshyper crate.
hyper_map: this module contains the HyperMap, a hash-based hypergraph implementation A map-based implementation of a hypergraph providing efficient storage and manipulation of hypernodes and hyperedges.
idx: the idx module provides the IndexBase, a generic index type used to establish a solid foundation for all indices used by the hypergraph. Type aliases, such as EdgeId and VertexId, are provided for convenience, reducing the need to continually specify the index type when working with hypergraphs.
node: this module provides the Node implmenetation alongisde the several traits such as RawNode and RawPoint focused on establishing a common, well-defined interface for weighted and unweighted “points” within a hypergraph.
rel: this module establishes relational traits and implementations for components of a hypergraph.
traits: this module contains various traits used throughout to establish common interfaces and behaviors
types: this module provides various types used throughout the library
weight: this module implements a generic Weight wrapper type for representing the weights of entries within the hypergraph. Additionally, the module provides the Weightless type alias for cases where there is no associated weight.

Macros§

hyperedge: The hyperedge macro streamlines the definition of hyperedges in a hypergraph.
hypergraph: the [hypergraph] macro works to aide the in the creation of hypergraphs by allowing users to define nodes and edges in a hypergraph in a more declarative way.
hypernode: the [hypernode] macro streamlines the process of inserting nodes into a hypergraph.

Structs§

Attrs: Attrs is a generic implementation of the GraphProps trait, enabling the definition of hypergraphs with different index types and graph kinds (i.e., Directed or Undirected).
Directed: A marker type representing a directed graph type
Edge: The Edge implementation essentially wraps the Link type with a Weight
EdgeIndex: A kind of index for edges in a graph
HyperMap: The HyperMap is a map-based implementation of a hypergraph that provides a flexible and efficient way to store and manipulate hypergraphs. It is designed to be generic over the types of nodes N, edges E, attributes A, and the hasher S used for hashing the nodes and edges. This design allows for a wide range of applications, from simple hypergraphs to more complex structures with custom attributes and hashing strategies.
IndexBase: A generic IndexBase implementation used to represent various kinds of indices
IndexFrame: The IndexFrame stores the current edge and vertex indices in a hypergraph, allowing for efficient traversal and manipulation of the hypergraph structure. Here, when we say current we mean the next indices used to create a new edge or vertex, respectively. It is designed to be used in conjunction with hypergraph operations that require knowledge of the current position within the hypergraph, such as adding or removing edges and vertices, or iterating over the hypergraph’s elements. The cursor is generic over the index type T, which must implement the RawIndex trait. This allows for flexibility in the choice of index representation, enabling the use of different types of indices (e.g., Udx or some custom index types) while maintaining the same interface for the cursor.
IndexKindIter: An iterator over the variants of IndexKind
IsWeighted
Link: Here, a Link essentially defines the layout of an edge within a hypergraph. The implementation is generic over the type of domain it contains, which can be a set of vertices or any other structure that implements the Domain trait.
ModeIter: An iterator over the variants of Mode
Node: The Node implementation generically associates a VertexId with a Weight.
UnWeighted
Undirected: A marker type representing an undirected graph type
VertexIndex: A kind of index for vertices in a graph
Weight: The Weight type is a wrapper around a generic type T that provides additional functionality for working with weights in a graph context.

Enums§

Error: The error type for this crate
Grid: the Grid enumerate the possible variations of indicies that can be used within the scope of a hypergraph. This entity is useful for enabling “compoite” collections of indicies for iteration, traversal, etc.
IndexKind: Auto-generated discriminant enum variants
Mode: Mode enumerates the possible graph variants enabling dynamic dispatch features.

Traits§

AddStep: AddStep is a trait that defines a method to add a step to the current value, replacing
Apply: The Apply trait defines a generic, transformative operation that can be applied to an object of type Rhs.
AsWeight: a trait for converting a type into a valid Weight
BinaryDomain: The BinaryDomain trait extends the RawDomain trait to provide specific methods for binary edges, which are edges that connect exactly two vertices.
Combine: Combine defines a common interface for merging two edges in a hypergraph.
Concat: Concat defines an interface for concatenating two entities into another
Contains: Contains defines a common interface for types able to verify if they contain a given key or index; the trait strives to emulate the behavior of the contains method found in standard collections such as HashSet or BTreeSet.
Domain: An Domain is a trait is a specialization of the RawDomain trait that represents a store for edges, which are collections of vertices. It is used to define the behavior
GraphIndex: This trait is used to define various kinds of indices that are used to compose graphical structures.
GraphProps: The GraphProps trait abstracts several generic types used to define a hyper graph into a single entity.
GraphType: GraphType is a marker trait for graph types.
HashIndex: The HashIndex trait extends the [StdIndex] trait to include additional operations and behaviours commonly expected from indices in a hypergraph.
HyperGraph: The HyperGraph trait directly extends the RawHyperGraph trait to provide additional utilities and constructors for implementors while establishing a more robust interface for hypergraphs. This trait is designed to abstract the basic behaviour of hypergraphs, enabling the generalization of implements algorithms and operators.
HyperGraphIter: The HyperGraphIter trait combines the HyperGraphIterNode and HyperGraphIterEdge traits to provide a unified interface for iterating over both nodes
HyperGraphIterEdge: The HyperGraphIterEdge trait extends the HyperGraph trait to provide iterators over the edges in the hypergraph.
HyperGraphIterNode: The HyperGraphIterNode trait extends the HyperGraph trait to provide iterators over the nodes in the hypergraph.
HyperIndex: The HyperIndex trait extends the NumIndex to define contraints for the standard index type for the crate; implementors must also implement following traits:
Indexed: Indexed describes a common interface for all types which are aware of some associated index. The trait is generic over a type T which implements the RawIndex trait, allowing for flexibility in the type of index used while ensuring that the index type is compatible with the hypergraph’s indexing system.
IntoEdgeId: a trait for converting a type into a valid EdgeId
IntoNodeId: a trait for converting a type into a valid VertexId
IntoWeight: a trait for converting a type into a valid Weight
IterDomain: The IterDomain trait defines the base interface for creating an interator over a domain of vertices.
Merge: Merge defines a common interface for merging two entities into another
NumIndex: The NumIndex trait extends the RawIndex trait to include additional operations and behaviours expected from numerical indices in a hypergraph.
RawDomain: RawDomain is a trait that defines the behavior of a store that holds the vertices associated with a hyperedge or hyperfacet. It is used to abstract over different implementations of edge storage, such as arrays, vectors, or sets.
RawHyperGraph: RawHyperGraph is a trait that defines the basic operations for a hypergraph data structure.
RawIndex: a simple trait for denoting types compatible with to be used as indices in a hypergraph. note: the trait is sealed to prevent external implementations.
RawLayout: RawLayout establishes a common interface for hyperedge representations.
StdGraph: The StdGraph is used to denotes instances in-which the hypergraph contains binary edges meaning that each edge is composed of exactly two vertices.
StepSelf: StepSelf is a trait establishing a common interface for entities that may be progressed, producing some Output as a result. The trait is typically used to define generators for indices within the hypergraph.
StepWith: StepWith is a trait defining an interface that can be best described as a more flexible take method, however, instead of leaving the default value in place of the previous one, it allows for a generator function to be provided.
Transform: A trait denoting objects capable of being transformed by another object.
TransformInplace: The TransformInplace generically describes objects capable of being transformed in-place by another object.
Weighted: Weighted is used to define common behaviours for types that have an associated weight.

Type Aliases§

DiHyperMap: a type alias for a directed HyperMap
EdgeId: a type alias for an [Index] whose kind is EdgeIndex
IndexArray: a type alias for a fixed sized array of IndexBase
IndexSet: a type alias for a HashSet of IndexBase that is generic over the index type I, the kind K, and the hash builder S
IndexSlice: a type alias for a slice of IndexBase
IndexSliceMut: a type alias for a mutable slice of IndexBase
IndexSliceRef: a type alias for a reference to a slice of IndexBase
Result: A type alias for a Result with the crate-specific error type Error
Udx: a type alias for a usize used to define the default index type throughout the crate.
UnHyperMap: a type alias for an undirected HyperMap
VertexArray: a type alias for a fixed sized array of VertexId
VertexBSet: a type alias for a VertexId stored in a BTreeSet
VertexDeque: a type alias for a VertexId stored in a VecDeque
VertexId: a type alias for an [Index] whose kind is VertexIndex
VertexSet: a type alias for a HashSet of VertexId that is generic over the index type I
VertexSlice: a type alias for a slice of VertexId
VertexSliceMut: a type alias for a mutable slice of VertexId
VertexSliceRef: a type alias for a reference to a slice of VertexId
VertexVec: a type alias for a Vec of VertexId that is generic over the index type Ix
Weightless: An Weightless types is a type alias for a Weight that uses the [UnWeight] marker type to indicate that it has no weight.

Crate rshyperCopy item path