## Expand description

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 `SlotMap`

s 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 `SlotMap`

s 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§

- algo
`algorithms`

Contains implementations of some algorithms that can be used on`Graph`

s. - aliases
`alloc`

or`slotmap`

Contains type aliases of the`Graph`

type that use specific node and edge maps and the maps themselves. - Contains all error types provided by the crate.
- Contains the generic
`Graph`

and`FrozenGraph`

structures. - Contains traits used as an interface between
`Graph`

s and their backing maps.