Crate mapgraph

This crate provides the Graph type, a generic implementation of a directed graph using an adjacency list representation that can also be used as an arbitrary map.

Typically, graphs aren’t used as maps which makes fast map data structures that produce their keys internally a good fit. That is how the Graph type from the petgraph crate works: it uses vectors to store nodes and edges and indices in these vectors to refer to them. This approach is really efficient since vector accesses are really fast, but I’ve found it is sometimes not flexible enough.

mapgraph extends this approach and replaces the vectors with arbitrary maps. By choosing maps you can customize some aspects of how exactly the Graph type behaves. For example, using a SlotMap as either a node or an edge map gives you stable versioned keys produced by the Graph internally. Using a HashMap, on the other hand, gives you arbitrary hashable keys you provide yourself.

use mapgraph::aliases::{HashSlotMapGraph, SlotMapGraph};

// Using a graph with a SlotMap backing its nodes. The node's index is produced internally.
let mut first_graph = SlotMapGraph::<String, ()>::default();
let node_index = first_graph.add_node("foo".to_string());
assert_eq!(first_graph.node_weight(node_index).unwrap(), "foo");

// Using a graph with a HashMap backing its nodes. The node's index is supplied externally.
let mut second_graph = HashSlotMapGraph::<&str, (), &str>::default();
second_graph.try_add_node_at_index("foo", "bar").unwrap();
assert_eq!(second_graph.node_weight("foo").unwrap(), &"bar");

Representation

The graph represents nodes and edges as map entries and uses map keys to refer to them. Each node stores indices of the first outgoing and incoming edges and each edge stores indices of next outgoing and incoming edges thus forming two linked lists of edges.

Using custom maps

The maps may expose their features to the Graph type through a system of traits to make the graph act as a map.

The Map trait is the base trait that provides the common operations supported by all maps. This does not include insertion.

The IntKeyMap and ExtKeyMap traits provide the insertion capabilities for maps that produce keys internally or support external keys.

The OrderedKeyMap trait provides range iteration capabilities for maps that support that (e.g. BTreeMap).

See documentation for traits in the map module for more information.

Features

• std - provides implementations of std::error::Error on error types, enables the std feature on the slotmap crate if the slotmap feature is enabled.
• alloc - enables support for the BTreeMap type.
• hashmap - enables support for the HashMap type, requires std.
• slotmap - enables support for the SlotMap type.
• algorithms - provides the algo module.
• serde - enables serialization/deserialization using serde. Disabled by default.

Re-exports

pub use graph::FrozenGraph;

pub use graph::Graph;

pub use map::ExtKeyMap;

pub use map::IntKeyMap;

pub use map::KeySet;

pub use map::Map;

pub use map::MapWithCapacity;

pub use map::OrderedKeyMap;

Modules

algo

Contains implementations of some algorithms that can be used on Graphs.

aliases

Contains type aliases of the Graph type that use specific node and edge maps.

btreemap

Provides an implementation of Map for BTreeMap, necessary iterator types and useful type aliases for using BTreeMap as a node map for a Graph.

error

Contains all error types provided by the crate.

graph

Contains the generic Graph and FrozenGraph structures.

hashmap

Provides an implementation of Map for HashMap, KeySet for HashSet, necessary iterator types and useful type aliases for using HashMap as a node map for a Graph.

map

Contains traits used to provide Graphs with backing maps.

slotmap

Provides implementations of the map traits for SlotMap, HopSlotMap, DenseSlotMap and SecondaryMap and useful type aliases.