Crate rshyper_hmap

A map-based implementation of a hypergraph providing efficient storage and manipulation of hypernodes and hyperedges.

Overview

This implementation focuses on providing a flexible and efficient representation of a hypergraph. The HyperMap is parameterized by the following types:

• N: the type of weight associated with a hypernode
• E: the type of weight associated with a hyperedge
• A: the attributes of the graph are implementors of the [GraphProps] trait
  • A::Kind: the kind of hypergraph, either Directed or Undirected
  • A::Ix: the type of indices used by the instance; bounded by the [RawIndex trait
• S: the type of [BuildHasher] used for the underling stores

This is done to maximize compatibility and flexibility, allowing users to define their own hypergraphs with custom node and edge types, as well as different index types and hashers.

Backend

The underlying storage mechanics are based on the hashbrown crate, which is a Rust implementation of Google’s SwissTable algorithm. This is largely done to benfit from the additional feature set natively available within the crate versus the standard HashMap implementation. That being said, it is important to note that for any applications where security it a concerin it is highly recommended to use the RandomState as the default hasher in lieu of the [DefaultHashBuilder] from foldhash as it fails to prevent against attacks such as Hash-DoS. See the hashbrown for more information on the security implications of using a custom hasher.

Features

The HyperMap supports various features to enhance its functionality:

• algo: enables the algorithmic operators from the rshyper_algo crate
• 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_core::Weight;
use rshyper_hmap::HyperMap;
// initialize a ne, undirected hypergraph
let mut graph = HyperMap::<i32, i32>::undirected();
// insert some nodes with and without weights
let v0 = graph.add_vertex().expect("failed to add vertex");
let v1 = graph.add_node(Weight(42)).expect("failed to add the node");
let v2 = graph.add_node(Weight(100)).expect("failed to add the node");
// insert an edge between the two nodes
let e0 = graph.add_edge([v0, v1, v2], Weight(100)).expect("failed to add edge");
// verify the size of the graph; (number of edges)
assert_eq!(graph.size(), 1);
// verify the order of the graph; (number of nodes)
assert_eq!(graph.order(), 3);

Modules

iter

this module defines various iterators for the HyperMap

Structs

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.

Type Aliases

DiHyperMap

a type alias for a directed HyperMap

EdgeEntry

a type alias for a Entry that whose key is an EdgeId and value is a [HashSurface]

EdgeMap

a type alias for a HashMap that maps EdgeId to a [HashFacet]

NodeEntry

a type alias for a Entry that whose key is a VertexId and value is a Node

NodeMap

a type alias for a HashMap that maps VertexId to a Node

UnHyperMap

a type alias for an undirected HyperMap