petgraph

petgraph is a powerful and versatile graph data structure library for Rust. It provides a robust and idiomatic way to represent various types of graphs (collections of nodes/vertices and edges/connections) and offers a rich set of algorithms to operate on them.

Key Features:

1. Diverse Graph Types: petgraph supports different graph representations, including:
* `Graph<N, E, Ty, Ix>`: A generic graph where `N` is the node weight type, `E` is the edge weight type, `Ty` specifies the graph kind (directed or undirected), and `Ix` is the index type (usually `u32` or `u16`).
* `DiGraph<N, E>`: A shorthand for a directed graph.
* `UnGraph<N, E>`: A shorthand for an undirected graph.
* `StableGraph`: A variant that guarantees `NodeIndex` and `EdgeIndex` stability even after removals, which is useful when external references to indices are maintained.

2. Node and Edge Weights: Both nodes and edges can carry arbitrary data (weights), making it highly flexible for various applications like representing distances, costs, attributes, etc.

3. Comprehensive Algorithms: petgraph includes implementations of many standard graph algorithms, such as:
* Traversal: Breadth-First Search (BFS), Depth-First Search (DFS).
* Shortest Path: Dijkstra's algorithm, A* search, Bellman-Ford.
* Connectivity: Strongly Connected Components (SCC), Weakly Connected Components (WCC).
* Topological Sort: For directed acyclic graphs (DAGs).
* Minimum Spanning Tree: Kruskal's algorithm, Prim's algorithm.
* Cycle detection, reachability, etc.

4. Efficient Indexing: Nodes and edges are referenced by `NodeIndex` and `EdgeIndex` types, which are lightweight wrappers around integers, providing efficient access.

5. Ergonomic API: The library provides a clean and easy-to-use API for adding/removing nodes and edges, querying graph properties, and running algorithms.

6. `no_std` Support: With reduced features, `petgraph` can also be used in `no_std` environments, making it suitable for embedded systems or operating system kernels.

Use Cases:

`petgraph` is ideal for any application requiring graph data structures, including:
* Network routing: Finding optimal paths.
* Social networks: Analyzing connections and relationships.
* Dependency resolution: Package managers, build systems.
* Pathfinding in games: AI navigation.
* Compiler design: Control flow graphs.
* Geographic information systems (GIS): Representing roads and locations.

In essence, `petgraph` is the de-facto standard for graph manipulation in the Rust ecosystem, offering both performance and a rich feature set.

Example Code

```rust
// Cargo.toml
// [dependencies]
// petgraph = "0.6"

use petgraph::graph::{DiGraph, NodeIndex};
use petgraph::algo::dijkstra;
use std::collections::HashMap;

fn main() {
    // 1. Create a directed graph with node weights (city names) and edge weights (distances).
    // DiGraph<N, E> where N is node weight type, E is edge weight type.
    let mut graph = DiGraph::<&str, u32>::new();

    // 2. Add nodes (cities) and store their NodeIndex to use them for adding edges.
    let paris = graph.add_node("Paris");
    let london = graph.add_node("London");
    let berlin = graph.add_node("Berlin");
    let rome = graph.add_node("Rome");
    let madrid = graph.add_node("Madrid");
    let amsterdam = graph.add_node("Amsterdam");

    // 3. Add edges (roads) with their respective distances (weights).
    // The order of arguments for add_edge is (source_node, target_node, edge_weight).
    graph.add_edge(paris, london, 450);
    graph.add_edge(london, paris, 450); // Assuming roads are bidirectional for simplicity here
    graph.add_edge(paris, berlin, 1050);
    graph.add_edge(berlin, rome, 1200);
    graph.add_edge(london, madrid, 1250);
    graph.add_edge(madrid, rome, 1600);
    graph.add_edge(paris, rome, 1100);
    graph.add_edge(london, amsterdam, 350);
    graph.add_edge(amsterdam, berlin, 650);

    println!("Graph created with {} nodes and {} edges.", graph.node_count(), graph.edge_count());

    // 4. Find the shortest path from Paris to all other reachable nodes using Dijkstra's algorithm.
    // dijkstra takes: graph, start_node, optional_goal_node, edge_cost_fn.
    // Here, None means calculate paths to all reachable nodes.
    // The closure |e| *e.weight() extracts the edge weight (distance) for cost calculation.
    let shortest_paths: HashMap<NodeIndex, u32> = dijkstra(&graph, paris, None, |e| *e.weight());

    println!("\nShortest paths from Paris:");
    for (node_idx, distance) in shortest_paths.iter() {
        // Use graph[node_idx] to access the node's weight (city name).
        if let Some(city_name) = graph.node_weight(*node_idx) {
            println!("  To {}: {} km", city_name, distance);
        }
    }

    // Example: Querying a specific shortest distance
    if let Some(dist_to_rome) = shortest_paths.get(&rome) {
        println!("\nSpecific shortest distance from Paris to Rome: {} km", dist_to_rome);
    } else {
        println!("\nRome is not reachable from Paris (or no path found).");
    }

    // Example: Iterate and print all nodes and their weights
    println!("\nAll nodes in the graph:");
    for node_idx in graph.node_indices() {
        println!("  Node {:?}: {}", node_idx, graph[node_idx]);
    }

    // Example: Iterate and print all edges, their endpoints, and weights
    println!("\nAll edges in the graph:");
    for edge_idx in graph.edge_indices() {
        let (source_idx, target_idx) = graph.edge_endpoints(edge_idx).unwrap();
        println!(
            "  Edge {:?} from {} ({:?}) to {} ({:?}): {} km",
            edge_idx,
            graph[source_idx],
            source_idx,
            graph[target_idx],
            target_idx,
            graph[edge_idx] // Access edge weight
        );
    }
}
```

Example Code

Related Topics