# Graphs in Rust: An Introduction to Petgraph

Graphs are ubiquitous in science and technology. As such, many software projects use graphs in one form or another. Here I discuss Petgraph, a general-purpose graph library written in Rust. The main features of Petgraph are illustrated with short code samples.

## About Petgraph

Started in 2014, Petgraph is Rust's most popular graph library. According to crates.io, Petgraph has been downloaded over 2.1 million times. Dozens of projects use it as a dependency.

Other than rustdoc, documentation on Petgraph is thin. There's an especially acute lack of code examples. A notable exception is the two-part series by Timothy Hobbs:

## Overview

Petgraph consists of three main components:

**Data structures.**Includes four graph implementations representing performance and functionality trade-offs.**Traversals.**Breadth- and depth-first traversals are implemented as Rust iterators.**Graph algorithms.**Includes isomorphism and several variants on connected components.

## Hello, Graph

The most broadly-useful graph implementation is `Graph`

, which is backed by an adjacency list. Create a `Graph`

like so:

```
use petgraph::graph::Graph;
fn main() {
let mut graph = Graph::<(), ()>::new(); // directed and unlabeled
graph.extend_with_edges(&[ (0, 1) ]);
assert_eq!(graph.node_count(), 2);
assert_eq!(graph.edge_count(), 1);
}
```

This minimal `Graph`

is unlabeled, meaning that both nodes and edges are of `Unit`

type (`()`

). Labels can be typed as follows.

```
use petgraph::graph::Graph;
fn main() {
let mut graph = Graph::new();
let origin = graph.add_node("Denver");
let destination_1 = graph.add_node("San Diego");
let destination_2 = graph.add_node("New York");
let cost_1 = graph.add_edge(origin, destination_1, 250);
let cost_2 = graph.add_edge(origin, destination_2, 1099);
assert_eq!(graph.node_weight(origin).unwrap(), &"Denver");
assert_eq!(graph[destination_1], "San Diego");
assert_eq!(graph.edge_weight(cost_1).unwrap(), &250);
assert_eq!(graph.edge_weight(cost_2).unwrap(), &1099);
}
```

The bracket notation `graph[handle]`

returns an unwrapped, cloned node weight. It panics given an unknown node reference, which may not be desirable for production work.

The value returned from `add_node`

is of type `NodeIndex`

. It can produce a numerical node index on request:

```
use petgraph::graph::Graph;
fn main() {
let mut graph = Graph::<(),()>::new();
let n0 = graph.add_node(());
let n1 = graph.add_node(());
assert_eq!(n0.index(), 0);
assert_eq!(n1.index(), 1);
}
```

However, this numerical index is not stable with respect to node deletion. If we rely on node indexing to store state external to the `Graph`

, that system will fail the moment a preceding node is removed:

```
use petgraph::graph::Graph;
fn main() {
let mut graph = Graph::<(),()>::new();
let n0 = graph.add_node(());
let n1 = graph.add_node(());
assert_eq!(n0.index(), 0);
assert_eq!(n1.index(), 1);
graph.remove_node(n0);
assert_eq!(n1.index(), 1); // watch out, not updated!
let indexes = graph.node_indices().collect::<Vec<_>>();
assert_eq!(indexes[0].index(), 1); // FAIL!
}
```

`Graph`

is directed by default. An undirected `Graph`

can be created with the `new_undirected`

method, among others:

```
use petgraph::graph::Graph;
fn main() {
let mut graph = Graph::new_undirected();
let origin = graph.add_node("Denver");
let destination_1 = graph.add_node("San Diego");
let destination_2 = graph.add_node("New York");
let cost_1 = graph.add_edge(origin, destination_1, 250);
let cost_2 = graph.add_edge(origin, destination_2, 1099);
assert_eq!(graph.edge_weight(cost_1).unwrap(), &250);
assert_eq!(graph.edge_weight(cost_2).unwrap(), &1099);
}
```

It's often useful to depict a graph. Petgraph supports DOT, a graph language specification used by many visualization tools including Graphviz. An online viewer (Vis.js) is available. DOT is also a useful debugging format on its own.

The example above can be updated to print a DOT representation of the graph.

```
use petgraph::prelude::Graph;
use petgraph::dot::Dot;
fn main() {
let mut graph = Graph::<&str, u32>::new();
let origin = graph.add_node("Denver");
let destination_1 = graph.add_node("San Diego");
let destination_2 = graph.add_node("New York");
graph.extend_with_edges(&[
(origin, destination_1, 250),
(origin, destination_2, 1099)
]);
println!("{}", Dot::new(&graph));
}
```

The output from this program can be copied into Vis.js:

```
digraph {
0 [label="Denver"]
1 [label="San Diego"]
2 [label="New York"]
0 -> 1 [label="250"]
0 -> 2 [label="1099"]
}
```

This yields the image:

An alternative, JSON-based debug format is available through the optional Serde integration. Activate it by adding the following to your `Cargo.toml`

file:

```
[dependencies]
serde_json = "1.0.45"
[dependencies.petgraph]
version = "0.5.0"
features = ["serde-1"]
```

Then use the `serde_json::to_string_pretty`

function.

```
use petgraph::graph::Graph;
fn main() {
let mut graph = Graph::<&str, u32>::new();
let origin = graph.add_node("Denver");
let destination_1 = graph.add_node("San Diego");
let destination_2 = graph.add_node("New York");
graph.extend_with_edges(&[
(origin, destination_1, 250),
(origin, destination_2, 1099)
]);
println!("{}", serde_json::to_string_pretty(&graph).unwrap());
}
```

This program prints:

```
{
"nodes": [
"Denver",
"San Diego",
"New York"
],
"node_holes": [],
"edge_property": "directed",
"edges": [
[
0,
1,
250
],
[
0,
2,
1099
]
]
}
```

## Graph Implementations

Petgraph supports four graph implementations. Their main difference lies in the data structure backing the graph. This can lead to different memory and time performance depending on the situation. As discussed shortly, however, the APIs of these graphs are not necessarily compatible with all uses.

`Graph`

is backed with an adjacency list. There is no restriction on node or edge type. Nodes and edges are accessed through `NodeIndex`

and `EdgeIndex`

values, respectively. These values in turn allow access to an underlying numerical index. As noted previously, these indexes are not stable under removal operations. `Graph`

enjoys the most support among Petgraph algorithms.

Like `Graph`

, StableGraph is backed with an adjacency list. Unlike `Graph`

, removing nodes or edges from a `StableGraph`

will not invalidate existing indexes.

```
use petgraph::stable_graph::StableGraph;
fn main() {
let mut graph = StableGraph::<(),()>::new();
let n0 = graph.add_node(());
let n1 = graph.add_node(());
assert_eq!(n0.index(), 0);
assert_eq!(n1.index(), 1);
graph.remove_node(n0);
assert_eq!(n1.index(), 1); // not updated
let indexes = graph.node_indices().collect::<Vec<_>>();
assert_eq!(indexes[0].index(), 1); // PASS!
}
```

The counterintuitively-named `GraphMap`

is backed with a Map, using nodes as keys. Nodes must implement `Copy`

, `Eq`

, `Ord`

, and `Hash`

. Node membership tests, a feature missing from `Graph`

but present in `StableGraph`

, execute in constant time.

Unlike the other three graph implementations, `GraphMap`

can work directly with with node and edge labels rather than intermediate handles.

```
use std::hash::Hash;
use petgraph::graphmap::UnGraphMap;
#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
struct City {
population: u32,
cars: u32
}
fn main() {
let mut graph = UnGraphMap::<_, ()>::new();
let bedford_falls = City { population: 1023, cars: 24 };
let tinsel_town = City { population: 102479, cars: 1231441 };
graph.add_node(&bedford_falls);
graph.add_node(&tinsel_town);
graph.add_edge(&bedford_falls, &tinsel_town, ());
assert!(graph.contains_node(&bedford_falls));
assert!(graph.contains_node(&tinsel_town));
assert!(graph.contains_edge(&bedford_falls, &tinsel_town));
assert!(graph.contains_edge(&tinsel_town, &bedford_falls));
}
```

Csr, is the fourth graph implementation supported by Petgraph. Short for *Compressed Sparse Row* (aka sparse matrix), CSR is an efficient method for representing sparse matrix data such as that used in most graphs. This results in reduced memory requirement with fast edge lookup. There are no restrictions on node or edge type. However, the API for `Csr`

is the most restricted of all the graph types.

```
use petgraph::csr::Csr;
fn main() {
let mut graph = Csr::<_,_>::new(); // directed
let a = graph.add_node("a");
let b = graph.add_node("b");
let _ = graph.add_edge(a, b, ());
assert!(graph.contains_edge(a, b));
assert!(!graph.contains_edge(b, a));
}
```

## Traversal

Three forms of traversal are supported: breadth-first; depth-first; and depth-first post-order. All are implemented as iterators, and all account for edge directionality.

A depth-first traversal can be executed like so:

```
use petgraph::Graph;
use petgraph::visit::Dfs;
fn main() {
let mut graph = Graph::<(),(), petgraph::Undirected>::new_undirected();
// 0(1)(2)3
graph.extend_with_edges(&[
(0, 1), (0, 2), (0, 3)
]);
for start in graph.node_indices() {
let mut dfs = Dfs::new(&graph, start);
print!("[{}] ", start.index());
while let Some(visited) = dfs.next(&graph) {
print!(" {}", visited.index());
}
println!();
}
}
```

producing the output:

```
[0] 0 1 2 3
[1] 1 0 2 3
[2] 2 0 1 3
[3] 3 0 1 2
```

We may want a slightly different order of iteration in which the neighbors of a node are first iterated, then the node itself. Petgraph supports such traversals with `DfsPostOrder`

. This traversal is invoked identically to `Dfs`

:

```
use petgraph::Graph;
use petgraph::visit::DfsPostOrder;
fn main() {
let mut graph = Graph::<(),(), petgraph::Undirected>::new_undirected();
// 0(1)(2)3
graph.extend_with_edges(&[
(0, 1), (0, 2), (0, 3)
]);
for start in graph.node_indices() {
let mut dfs = DfsPostOrder::new(&graph, start);
print!("[{}] ", start.index());
while let Some(visited) = dfs.next(&graph) {
print!(" {}", visited.index());
}
println!();
}
}
```

The effect is to first traverse neighbors, then the node itself:

```
[0] 1 2 3 0
[1] 2 3 0 1
[2] 1 3 0 2
[3] 1 2 0 3
```

Breadth-first traversal is supported with `Bfs`

, which works analogously to `Dfs`

and `DfsPostOrder`

:

```
use petgraph::Graph;
use petgraph::visit::Bfs;
fn main() {
let mut graph = Graph::<(),(), petgraph::Undirected>::new_undirected();
// 0(1)(2)34
graph.extend_with_edges(&[
(0, 1), (0, 2), (0, 3), (3, 4)
]);
for start in graph.node_indices() {
let mut bfs = Bfs::new(&graph, start);
print!("[{}] ", start.index());
while let Some(visited) = bfs.next(&graph) {
print!(" {}", visited.index());
}
println!();
}
}
```

The result is a characteristic breath-first traversal order:

```
[0] 0 3 2 1 4
[1] 1 0 3 2 4
[2] 2 0 3 1 4
[3] 3 4 0 2 1
[4] 4 3 0 2 1
```

## Algorithms

Petgraph supports a number of graph algorithms, as documented in the `algo`

package. A few algorithms will be highlighted here. However, a warning from the documentation should be kept in mind:

It is a goal to gradually migrate the algorithms to be based on graph traits so that they are generally applicable. For now, some of these still require the Graph type.

Isomorphism checks can be used to answer questions about graph equivalence and embedding. For this purpose, Petgraph offers the `is_isomorphic`

function:

```
use petgraph::Graph;
use petgraph::algo;
fn main() {
let mut g1 = Graph::<(),(), petgraph::Undirected>::new_undirected();
let mut g2 = Graph::<(),(), petgraph::Undirected>::new_undirected();
g1.extend_with_edges(&[
(0, 1), (0, 2), (0, 3)
]);
g2.extend_with_edges(&[
(0, 1), (0, 2), (0, 3)
]);
assert_eq!(algo::is_isomorphic(&g1, &g2), true);
g1.extend_with_edges(&[
(3, 4)
]);
assert_eq!(algo::is_isomorphic(&g1, &g2), false);
}
```

It can be useful to perform isomorphism checks using customized node and edge equivalence conditions. This is available by passing closures to `is_isomorphic_matching`

.

```
use petgraph::Graph;
use petgraph::algo;
#[derive(Default)] // required by Graph
struct Node {
value: u8
}
fn main() {
let mut g1 = Graph::<_,(), petgraph::Undirected>::new_undirected();
let mut g2 = Graph::<_,(), petgraph::Undirected>::new_undirected();
let n0 = g1.add_node(Node { value: 43 });
let n1 = g1.add_node(Node { value: 44 });
g1.extend_with_edges(&[ (n0, n1, ()) ]);
let n2 = g2.add_node(Node { value: 2 });
let n3 = g2.add_node(Node { value: 10 });
g2.extend_with_edges(&[ (n2, n3, ()) ]);
let test_nodes = |a: &Node, b: &Node| a.value > 42 && b.value > 42;
let test_edges = |_: &(), _: &()| true;
assert!(algo::is_isomorphic_matching(&g1, &g1, test_nodes, test_edges));
assert!(!algo::is_isomorphic_matching(&g1, &g2, test_nodes, test_edges));
}
```

Here, the closure `test_nodes`

passed to `is_isomorphic_matching`

fails unless both nodes being compared have `value`

properties greater than 42. The test succeeds for the `g1`

to `g1`

comparison, but fails when comparing `g1`

to `g2`

because only one node complies the the `value`

requirement.

Both `is_isomorphic`

and `is_isomorphic_matching`

functions require a `Graph`

implementation.

Dijkstra's algorithm is a well-known procedure for finding the shortest paths between nodes. The function `dijkstra`

can be used as follows:

```
use petgraph::Graph;
use petgraph::algo;
fn main() {
let mut graph = Graph::<(),()>::new();
graph.extend_with_edges(&[
(0, 1), (0, 2), (0, 3), (3, 4)
]);
for start in graph.node_indices() {
println!("--- {:?} ---", start.index());
println!("{:?}", algo::dijkstra(&graph, start, None, |_| 1));
}
}
```

The program prints the following output representing the cost of visiting each node along the shortest path from a fixed starting node:

```
--- 0 ---
{NodeIndex(3): 1, NodeIndex(0): 0, NodeIndex(1): 1, NodeIndex(2): 1, NodeIndex(4): 2}
--- 1 ---
{NodeIndex(1): 0}
--- 2 ---
{NodeIndex(2): 0}
--- 3 ---
{NodeIndex(3): 0, NodeIndex(4): 1}
--- 4 ---
{NodeIndex(4): 0}
```

In addition to `is_isomorphic`

, `is_isomorphic_matching`

, and `dijkstra`

, the following algorithms are also available:

**all_simple_paths**Returns an iterator over all paths from a given node.**astar**Complements`dijkstra`

with heuristics to guide traversal through the graph.**bellman_ford**Complements`dijkstra`

by supporting negative edge weights.**condensation**Condenses every strongly connected component into a single node.**connected_components**Returns the number of connected components.**has_path_connecting**Returns true if two nodes are reachable through some path.**is_cyclic_directed**Returns true if a graph contains at least one cycle in the directed sense.**is_cyclic_undirected**Returns true if a graph contains at least one cycle.**kosaraju_scc**Returns a vector of strongly connected components using Kosaraju's algorithm.**min_spanning_tree**Returns a tree for each connected component.**tarjan_scc**Returns a vector of strongly connected components using Tarjan's algorithm.**toposort**Returns a Vector of nodes in topological order.

## Conclusion

Petgraph supports many of the capabilities needed in projects using graphs. There are four graph implementations, breadth- and depth-first traversal, and 14 graph algorithms. The use of iterators for traversals offers great flexibility and power. Unfortunately, the graph implementations lack a common interface, and some algorithms are incompatible with certain graph implementations. Provided that the algorithms of interest are available for the required graph implementation, Petgraph may be a good choice.