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.