Crate bevy_internal::utils::petgraph

source ·
Expand description

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 to Graph, 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 weight-like. 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

  • serde-1 - Defaults off. Enables serialization for Graph, StableGraph, GraphMap using serde 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.

Modules

  • adj
    Simple adjacency list.
  • 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
    Graph<N, E, Ty, Ix> is a graph datastructure using an adjacency list representation.
  • graphmap
    GraphMap<N, E, Ty> is a graph datastructure where node values are mapping keys.
  • matrix_graph
    MatrixGraph<N, E, Ty, NullN, NullE, Ix> is a graph datastructure backed by an adjacency matrix.
  • operator
    Operators for creating new graphs from existings ones.
  • prelude
    Commonly used items.
  • stable_graph
    StableGraph keeps indices stable across removals.
  • unionfind
    UnionFind<K> is a disjoint-set data structure.
  • visit
    Graph traits and graph traversals.

Structs

  • Graph
    Graph<N, E, Ty, Ix> is a graph datastructure using an adjacency list representation.

Enums

Traits

  • EdgeType
    A graph’s edge type determines whether it has directed edges or not.
  • IntoWeightedEdge
    Convert an element like (i, j) or (i, j, w) into a triple of source, target, edge weight.