Crate rshyper 

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.