Crate mapgraph

A powerful library for directed adjacency list graphs.

Graph is a complex data structure where relations between nodes may often be cyclic which doesn’t go well with the Rust’s type system. A typical approach to this is to refer to nodes and edges in a graph using node and edge indices (sometimes called IDs or keys) which are mapped to the actual nodes, edges and their weights instead of using references or pointers. Since we’re mapping indices anyway why not make the maps we use generic and allow custom indices?

mapgraph provides the generic Graph type that is based on two maps: one for nodes and one for edges. By using the rich system of traits from the map submodule the Graph type may borrow some capabilities of the maps it’s based on. For example, using a HashMap as a node map for a Graph makes it accept external indices for nodes, effectively making the graph an index for its own nodes.

Library features and examples

Internal node indices

Let’s imagine Alice and Bob are friends and often call each other. Sometimes they order pizza by phone from a place where Luigi works, but they aren’t friends with Luigi, so he never calls them by himself.

Here’s one way to make a graph to represent their relations:

use mapgraph::aliases::SlotMapGraph;

// we create a graph that uses SlotMaps for both nodes and edges
let mut graph = SlotMapGraph::<&'static str, ()>::default();

// next we create a node for each person
let alice_index = graph.add_node("Alice");
let bob_index = graph.add_node("Bob");
let luigi_index = graph.add_node("Luigi");

// let's ensure that the indices return us the right node weights
assert_eq!(graph.node_weight(alice_index).copied(), Some("Alice"));
assert_eq!(graph.node_weight(bob_index).copied(), Some("Bob"));
assert_eq!(graph.node_weight(luigi_index).copied(), Some("Luigi"));

// finally let's connect them
graph.add_edge((), alice_index, bob_index)?;
graph.add_edge((), bob_index, alice_index)?;
graph.add_edge((), bob_index, luigi_index)?;
graph.add_edge((), alice_index, luigi_index)?;

Here SlotMapGraph is just an alias for Graph that uses SlotMaps for both nodes and edges. We don’t use edge weights, so we pass the unit type as the first parameter to Graph::add_edge.

While this may not seem like much just yet, using SlotMaps gives Graph important properties: removing nodes won’t cause unrelated indices to be invalidated and key versioning prevents older indices from pointing to newly added nodes that happen to be stored in place of an older node.

External node indices

Now let’s imagine we are telephone company employees who want to trace phone numbers to people and their relations for data science purposes. The obvious way to do this would be to create a separate index that maps phone numbers to graph indices, but that presents a challenge: the index should be synchronised to the graph. Adding or removing nodes should update the index as well as the graph itself. What if we used the phone numbers as node indices directly?

Here’s how we can do this:

use mapgraph::aliases::HashSlotMapGraph;

// we create a graph that uses a HashMap for nodes and a SlotMap for edges
let mut graph = HashSlotMapGraph::<&'static str, (), _>::default();

// define some constants for simplicity
const ALICE_NUMBER: &'static str = "6661234";
const BOB_NUMBER: &'static str = "5553535";
const LUIGI_NUMBER: &'static str = "1001112";

// next we create a node for each person
graph.try_add_node_at_index(ALICE_NUMBER, "Alice")?;
graph.try_add_node_at_index(BOB_NUMBER, "Bob")?;
graph.try_add_node_at_index(LUIGI_NUMBER, "Luigi")?;

// let's ensure that the indices return us the right node weights
assert_eq!(graph.node_weight(ALICE_NUMBER).copied(), Some("Alice"));
assert_eq!(graph.node_weight(BOB_NUMBER).copied(), Some("Bob"));
assert_eq!(graph.node_weight(LUIGI_NUMBER).copied(), Some("Luigi"));

// finally let's connect them
graph.add_edge((), ALICE_NUMBER, BOB_NUMBER)?;
graph.add_edge((), BOB_NUMBER, ALICE_NUMBER)?;
graph.add_edge((), BOB_NUMBER, LUIGI_NUMBER)?;
graph.add_edge((), ALICE_NUMBER, LUIGI_NUMBER)?;

We use a HashSlotMapGraph which is just an alias to a Graph like SlotMapGraph from the previous example. The interface for adding nodes to a HashSlotMapGraph is, however, different. The Graph::try_add_node_at_index method that accepts an external node index is used rather than Graph::add_node which provides an index as its return value since HashMap accepts keys provided externally unlike SlotMap which produces its keys internally. The way your map treats indices is encoded by implementing either ExtKeyMap or IntKeyMap trait. See documentation for the map module for more info on map traits and the capabilities they expose.

Ordered node indices

For the last example let’s pretend we also want to find people with particular area codes in their phone numbers:

use mapgraph::aliases::BTreeSlotMapGraph;

// we create a graph that uses a BTreeMap for nodes and a SlotMap for edges
let mut graph = BTreeSlotMapGraph::<&'static str, (), _>::default();

// define some constants for simplicity
const ALICE_NUMBER: &'static str = "6661234";
const BOB_NUMBER: &'static str = "5553535";
const LUIGI_NUMBER: &'static str = "1001112";

// next we create a node for each person
graph.try_add_node_at_index(ALICE_NUMBER, "Alice")?;
graph.try_add_node_at_index(BOB_NUMBER, "Bob")?;
graph.try_add_node_at_index(LUIGI_NUMBER, "Luigi").unwrap();

// we skip adding edges this time and just do a range query
let phones_and_names: Vec<_> = graph.nodes_range("5000000"..="7000000").collect();

// check that the results match our expectations
assert_eq!(
    &phones_and_names,
    &[(BOB_NUMBER, &"Bob"), (ALICE_NUMBER, &"Alice")]
);

Here we use the capabilities of a BTreeMap that are lent to the graph using the OrderedKeyMap trait.

More advanced features

Frozen graphs

This is a nice feature lent from the petgraph crate. FrozenGraph is a Graph with an immutable structure. Having a mutable reference to a FrozenGraph means you can mutate weights, but not add or remove nodes and edges. Graph and FrozenGraph can be freely converted between each other, graph also implements Deref<Target=FrozenGraph>. See docs for FrozenGraph for more info.

Parallel iteration using rayon

When the rayon crate feature is enabled, Graph exposes methods for parallel iteration of nodes and edges in case the underlying maps expose this functionality through the ParIterMap trait.

use mapgraph::aliases::HashSlotMapGraph;
use rayon::iter::ParallelIterator;

let mut graph = HashSlotMapGraph::<i32, i32, &'static str>::default();

// add nodes and edges...

// add 1 to each node weight in parallel
graph
    .par_iter_node_weights_mut()
    .for_each(|(_, weight)| *weight += 1);

In case you need to mutably iterate nodes and edges in parallel or to walk over edges while doing parallel iteration on nodes (or vice versa), a mutable reference to a Graph may be split into a reference to Nodes and a reference to Edges:

use mapgraph::{aliases::HashSlotMapGraph, graph::iter::EdgesWalker};
use rayon::iter::ParallelIterator;

let mut graph = HashSlotMapGraph::<i32, i32, &'static str>::default();

// add nodes and edges...

// split a reference to a graph
let (nodes, edges) = graph.as_nodes_mut_and_edges();

nodes.par_iter_mut().for_each(|(_, node)| {
    // let's sum all the weight of outgoing edges of that node
    let mut outputs_walker = node.walk_outputs();
    let mut sum = 0;
    while let Some((_ei, edge)) = outputs_walker.walk_edges_next(edges) {
        sum += *edge.weight();
    }

    // add that sum to the node's weight
    *node.weight_mut() += sum;
});

Crate 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 alloc crate, in particular BTreeMap and BTreeSet types.
• slotmap - enables integration with the slotmap crate.
• indexmap - enables integration with the indexmap crate.
• algorithms - enables the algo module which provides various algorithms to be run on graphs.
• serde - enables serialization/deserialization using serde. Disabled by default.
• rayon - enables parallel iteration support using rayon. Disabled by default.

Re-exports

• pub use graph::FrozenGraph;
• pub use graph::Graph;
• pub use map::ParIterMap;
  rayon
• 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

• algoalgorithms
  Contains implementations of some algorithms that can be used on Graphs.
• aliasesalloc or slotmap
  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.