[−][src]Crate petgraph
petgraph
is a graph data structure library.
Graphs are collections of nodes, and edges between nodes. petgraph
provides several graph types (each differing in the
tradeoffs taken in their internal representation),
algorithms on those graphs, and functionality to
output graphs in
graphviz
format. Both nodes and edges
can have arbitrary associated data, and edges may be either directed or undirected.
Example
use petgraph::graph::{NodeIndex, UnGraph}; use petgraph::algo::{dijkstra, min_spanning_tree}; use petgraph::data::FromElements; use petgraph::dot::{Dot, Config}; // Create an undirected graph with `i32` nodes and edges with `()` associated data. let g = UnGraph::<i32, ()>::from_edges(&[ (1, 2), (2, 3), (3, 4), (1, 4)]); // Find the shortest path from `1` to `4` using `1` as the cost for every edge. let node_map = dijkstra(&g, 1.into(), Some(4.into()), _ 1); assert_eq!(&1i32, node_map.get(&NodeIndex::new(4)).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\""] // 1  2 // 3  4 // 2  3 // }
Graph types
Graph
 An adjacency list graph with arbitrary associated data.StableGraph
 Similar toGraph
, but it keeps indices stable across removals.GraphMap
 An adjacency list graph backed by a hash table. The node identifiers are the keys into the table.MatrixGraph
 An adjacency matrix graph.CSR
 A sparse adjacency matrix graph with arbitrary associated data.
Generic parameters
Each graph type is generic over a handful of parameters. All graphs share 3 common
parameters, N
, E
, and Ty
. This is a broad overview of what those are. Each
type's documentation will have finer detail on these parameters.
N
& E
are called weights in this implementation, and are associated with
nodes and edges respectively. They can generally be of arbitrary type, and don't have to
be what you might conventionally consider weightlike. For example, using &str
for N
will work. Many algorithms that require costs let you provide a cost function that
translates your N
and E
weights into costs appropriate to the algorithm. Some graph
types and choices do impose bounds on N
or E
.
min_spanning_tree
for example requires edge weights that
implement PartialOrd
.
GraphMap
requires node weights that can serve as hash
map keys, since that graph type does not create standalone node indices.
Ty
controls whether edges are Directed
or
Undirected
.
Ix
appears on graph types that use indices. It is exposed so you can control
the size of node and edge indices, and therefore the memory footprint of your graphs.
Allowed values are u8
, u16
, u32
, and usize
, with u32
being the default.
Shorthand types
Each graph type vends a few shorthand type definitions that name some specific
generic choices. For example, DiGraph<_, _>
is shorthand
for Graph<_, _, Directed>
.
UnMatrix<_, _>
is shorthand for
MatrixGraph<_, _, Undirected>
. Each graph type's
module documentation lists the available shorthand types.
Crate features
 serde1 
Defaults off. Enables serialization for
Graph, StableGraph
usingserde 1.0
. May require a more recent version of Rust than petgraph alone.  graphmap 
Defaults on. Enables
GraphMap
.  stable_graph 
Defaults on. Enables
StableGraph
.  matrix_graph 
Defaults on. Enables
MatrixGraph
.
Reexports
pub use crate::graph::Graph; 
pub use crate::Direction::Incoming; 
pub use crate::Direction::Outgoing; 
Modules
algo  Graph algorithms. 
csr  Compressed Sparse Row (CSR) is a sparse adjacency matrix graph. 
data  Graph traits for associated data and graph construction. 
dot  Simple graphviz dot file format output. 
graph 

graphmap 

matrix_graph 

prelude  Commonly used items. 
stable_graph 

unionfind 

visit  Graph traits and graph traversals. 
Enums
Directed  Marker type for a directed graph. 
Direction  Edge direction. 
Undirected  Marker type for an undirected graph. 
Traits
EdgeType  A graph's edge type determines whether it has directed edges or not. 
IntoWeightedEdge  Convert an element like 