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 - enables support for the HashMap type, provides implementations of std::error::Error on error types, enables the std feature on the slotmap crate if the slotmap feature is enabled. Requires the alloc feature.
• alloc - enables support for the BTreeMap type.
• 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 and the maps themselves.
• error
  Contains all error types provided by the crate.
• graph
  Contains the generic Graph and FrozenGraph structures.
• map
  Contains traits used as an interface between Graphs and their backing maps.