Petgraph provides fast, flexible graph data structures and algorithms in Rust. Supporting both directed and undirected graphs with arbitrary node and edge data. It comes with:
-
Multiple Graph Types: Graph, StableGraph, GraphMap, and MatrixGraph to suit various use cases.
-
Algorithms Included & Extensible: For tasks like path-finding, minimum spanning trees, graph isomorphisms, and more - with traits exposed for implementing custom algorithms.
-
Graph Visualization support: Export/import graphs to/from DOT format for visualization with Graphviz.
Supports Rust 1.64 and later. This will only change on major releases.
For more examples, see the documentation on docs.rs.
use petgraph::graph::UnGraph;
use petgraph::algo::{dijkstra, min_spanning_tree};
use petgraph::data::FromElements;
use petgraph::dot::{Dot, Config};
use petgraph::visit::NodeIndexable;
fn main() {
// Create an undirected graph with associated data
// of type `i32` for the nodes and `()` for the edges.
let g = UnGraph::<i32, ()>::from_edges(&[
(0, 1), (1, 2), (2, 3), (0, 3)
]);
// The graph looks like this:
// 0 -- 1
// | |
// 3 -- 2
// Find the shortest path from `0` to `2` using `1` as the cost for every edge.
let node_map = dijkstra(&g, 0.into(), Some(2.into()), |_| 1);
assert_eq!(&2i32, node_map.get(&g.from_index(2)).unwrap());
// Get the minimum spanning tree of the graph as a new graph, and check that
// one edge was trimmed.
let mst = UnGraph::<_, _>::from_elements(min_spanning_tree(&g));
assert_eq!(g.raw_edges().len() - 1, mst.raw_edges().len());
// Output the tree to `graphviz` `DOT` format
println!("{:?}", Dot::with_config(&mst, &[Config::EdgeNoLabel]));
// graph {
// 0 [ label = "0" ]
// 1 [ label = "0" ]
// 2 [ label = "0" ]
// 3 [ label = "0" ]
// 0 -- 1 [ ]
// 2 -- 3 [ ]
// 1 -- 2 [ ]
// }
}petgraph is built with these features enabled by default:
graphmapenableGraphMap.stable_graphenableStableGraph.matrix_graphenableMatrixGraph.
Optionally, the following features can be enabled:
serde-1enable serialization forGraph, StableGraph, GraphMapusing serde 1.0. Requires Rust version as required by serde.rayonenable parallel iterators for the underlying data inGraphMap. Requires Rust version as required by rayon.dot_parserenable parsing graph from DOT/Graphviz strings and files.
First, see if the answer to your question can be found in the API documentation. If the answer is not there, feel free to ask your question on the discussions page. We would be happy to try to answer your question. If you find a bug, or have a feature request, please open an issue.
🦕 Thanks for your help improving the project! We are so happy to have you! We have a contributing guide to help you get started.
The mascot is named "Sir Paul Rustory Graphosaurus" (close friends call him Paul). The logo has been created by the talented Aren.
Dual-licensed to be compatible with the Rust project.
Licensed under the Apache License, Version 2.0 or the MIT license, at your option. This file may not be copied, modified, or distributed except according to those terms.