Petgraph

https://docs.rs/petgraph/latest/
Admin
Petgraph is a Rust graph data structure library providing multiple graph types, comprehensive graph...
Tokens:225,787
Snippets:1,692
Trust Score:9.7
Update:2 months ago
Show doc for...
Tokens:
Raw
### Ford-Fulkerson Example Setup

Source: https://docs.rs/petgraph/latest/src/petgraph/algo/maximum_flow/ford_fulkerson.rs.html

Initial setup for using the Ford-Fulkerson algorithm with a petgraph Graph.

```rust
```rust
use petgraph::Graph;
use petgraph::algo::ford_fulkerson;
// Example from CLRS book
let mut graph = Graph::<u8, u8>::new();
```

--------------------------------

### Compute shortest path with bidirectional_dijkstra

Source: https://docs.rs/petgraph/latest/petgraph/algo/dijkstra/fn.bidirectional_dijkstra.html

Example demonstrating the setup of a directed graph and the calculation of the shortest path cost between two nodes.

```rust
use petgraph::Graph;
use petgraph::algo::bidirectional_dijkstra;
use petgraph::prelude::*;
use hashbrown::HashMap;

let mut graph: Graph<(), (), Directed> = Graph::new();
let a = graph.add_node(());
let b = graph.add_node(());
let c = graph.add_node(());
let d = graph.add_node(());
let e = graph.add_node(());
let f = graph.add_node(());
let g = graph.add_node(());
let h = graph.add_node(());

graph.extend_with_edges(&[
    (a, b),
    (b, c),
    (c, d),
    (d, a),
    (e, f),
    (b, e),
    (f, g),
    (g, h),
    (h, e),
]);
// a ----> b ----> e ----> f
// ^       |       ^       |
// |       v       |       v
// d <---- c       h <---- g

let result = bidirectional_dijkstra(&graph, a, g, |_| 1);
assert_eq!(result, Some(4));
```

--------------------------------

### Compute k-th shortest paths in a graph

Source: https://docs.rs/petgraph/latest/petgraph/algo/k_shortest_path/fn.k_shortest_path.html

Example demonstrating the usage of k_shortest_path to find path costs from a starting node in a directed graph.

```rust
use petgraph::Graph;
use petgraph::algo::k_shortest_path;
use petgraph::prelude::*;
use hashbrown::HashMap;

let mut graph : Graph<(),(),Directed>= Graph::new();
let a = graph.add_node(()); // node with no weight
let b = graph.add_node(());
let c = graph.add_node(());
let d = graph.add_node(());
let e = graph.add_node(());
let f = graph.add_node(());
let g = graph.add_node(());
let h = graph.add_node(());
// z will be in another connected component
let z = graph.add_node(());

graph.extend_with_edges(&[
    (a, b),
    (b, c),
    (c, d),
    (d, a),
    (e, f),
    (b, e),
    (f, g),
    (g, h),
    (h, e)
]);
// a ----> b ----> e ----> f
// ^       |       ^       |
// |       v       |       v
// d <---- c       h <---- g

let expected_res: HashMap<NodeIndex, usize> = [
     (a, 7),
     (b, 4),
     (c, 5),
     (d, 6),
     (e, 5),
     (f, 6),
     (g, 7),
     (h, 8)
    ].iter().cloned().collect();
let res = k_shortest_path(&graph,b,None,2, |_| 1);
assert_eq!(res, expected_res);
// z is not inside res because there is not path from b to z.
```

--------------------------------

### Dijkstra with dynamic goal example

Source: https://docs.rs/petgraph/latest/petgraph/algo/dijkstra/fn.with_dynamic_goal.html

Demonstrates using with_dynamic_goal to find the shortest path to either node d or node f starting from node b.

```rust
use petgraph::Graph;
use petgraph::algo::dijkstra;
use petgraph::prelude::*;
use hashbrown::HashMap;

let mut graph: Graph<(), (), Directed> = Graph::new();
let a = graph.add_node(()); // node with no weight
let b = graph.add_node(());
let c = graph.add_node(());
let d = graph.add_node(());
let e = graph.add_node(());
let f = graph.add_node(());
let g = graph.add_node(());
let h = graph.add_node(());
// z will be in another connected component
let z = graph.add_node(());

graph.extend_with_edges(&[
    (a, b),
    (b, c),
    (c, d),
    (d, a),
    (e, f),
    (b, e),
    (f, g),
    (g, h),
    (h, e),
]);
// a ----> b ----> e ----> f
// ^       |       ^       |
// |       v       |       v
// d <---- c       h <---- g

let expected_res: HashMap<NodeIndex, usize> = [
    (b, 0),
    (c, 1),
    (d, 2),
    (e, 1),
    (f, 2),
].iter().cloned().collect();
let res = dijkstra::with_dynamic_goal(&graph, b, |&node| node == d || node == f, |_| 1);
assert_eq!(res.scores, expected_res);
assert!(res.goal_node == Some(d) || res.goal_node == Some(f));
```

--------------------------------

### DfsPostOrder::new

Source: https://docs.rs/petgraph/latest/petgraph/visit/struct.DfsPostOrder.html

Creates a new DfsPostOrder instance initialized with a starting node.

```APIDOC
## pub fn new<G>(graph: G, start: N) -> Self

### Description
Creates a new DfsPostOrder using the graph's visitor map and initializes the stack with the provided start node.

### Parameters
- **graph** (G) - The graph to traverse, must implement GraphRef and Visitable.
- **start** (N) - The starting node for the traversal.
```

--------------------------------

### Bfs::new

Source: https://docs.rs/petgraph/latest/petgraph/visit/struct.Bfs.html

Creates a new Bfs instance starting from a specified node.

```APIDOC
## Bfs::new<G>(graph: G, start: N) -> Self

### Description
Creates a new Bfs instance, using the graph's visitor map, and initializes the stack with the starting node.

### Parameters
- **graph** (G) - The graph to traverse, must implement GraphRef and Visitable.
- **start** (N) - The starting node ID for the traversal.
```

--------------------------------

### Dfs::new

Source: https://docs.rs/petgraph/latest/petgraph/visit/struct.Dfs.html

Creates a new Dfs instance starting from a specific node.

```APIDOC
## pub fn new<G>(graph: G, start: N) -> Self

### Description
Create a new Dfs, using the graph’s visitor map, and put start in the stack of nodes to visit.
```

--------------------------------

### Compute All-Pairs Shortest Paths with Johnson Algorithm

Source: https://docs.rs/petgraph/latest/petgraph/algo/johnson/fn.johnson.html

Demonstrates calculating shortest paths in a directed graph using the johnson function. The example verifies results against an expected HashMap of distances.

```rust
use petgraph::{prelude::*, Graph, Directed};
use petgraph::algo::johnson;
use std::collections::HashMap;

let mut graph: Graph<(), i32, Directed> = Graph::new();
let a = graph.add_node(());
let b = graph.add_node(());
let c = graph.add_node(());
let d = graph.add_node(());

graph.extend_with_edges(&[
   (a, b, 1),
   (a, c, 4),
   (a, d, 10),
   (b, c, 2),
   (b, d, 2),
   (c, d, 2)
]);

//     ----- b --------
//    |      ^         | 2
//    |    1 |    4    v
//  2 |      a ------> c
//    |   10 |         | 2
//    |      v         v
//     --->  d <-------

let expected_res: HashMap<(NodeIndex, NodeIndex), i32> = [
   ((a, a), 0), ((a, b), 1), ((a, c), 3), ((a, d), 3),
   ((b, b), 0), ((b, c), 2), ((b, d), 2),
   ((c, c), 0), ((c, d), 2),
   ((d, d), 0),
].iter().cloned().collect();


let res = johnson(&graph, |edge| {
    *edge.weight()
}).unwrap();

let nodes = [a, b, c, d];
for node1 in &nodes {
    for node2 in &nodes {
        assert_eq!(res.get(&(*node1, *node2)), expected_res.get(&(*node1, *node2)));
    }
}
```

--------------------------------

### SPFA Usage Example

Source: https://docs.rs/petgraph/latest/petgraph/algo/spfa/fn.spfa.html

Demonstrates calculating shortest paths in a graph with negative edge weights and handling a negative cycle case.

```rust
use petgraph::Graph;
use petgraph::algo::spfa;

let mut g = Graph::new();
let a = g.add_node(()); // node with no weight
let b = g.add_node(());
let c = g.add_node(());
let d = g.add_node(());
let e = g.add_node(());
let f = g.add_node(());
g.extend_with_edges(&[
    (0, 1, 3.0),
    (0, 3, 2.0),
    (1, 2, 1.0),
    (1, 5, 7.0),
    (2, 4, -4.0),
    (3, 4, -1.0),
    (4, 5, 1.0),
]);

// Graph represented with the weight of each edge.
//
//     3       1
// a ----- b ----- c
// | 2     | 7     |
// d       f       | -4
// | -1    | 1     |
// \------ e ------/

let path = spfa(&g, a, |edge| *edge.weight());
assert!(path.is_ok());
let path = path.unwrap();
assert_eq!(path.distances, vec![0.0 ,     3.0,     4.0,    2.0,     0.0,     1.0]);
assert_eq!(path.predecessors, vec![None, Some(a), Some(b), Some(a), Some(c), Some(e)]);


// Negative cycle.
let graph = Graph::<(), f32>::from_edges(&[
    (0, 1, 2.0), (1, 2, 2.0), (2, 0, -10.0)]);

assert!(spfa(&graph, 0.into(), |edge| *edge.weight()).is_err());
```

--------------------------------

### DFS with Control Flow

Source: https://docs.rs/petgraph/latest/petgraph/visit/fn.depth_first_search.html

Example demonstrating how to use Control::Break to stop the search early when a goal node is reached.

```rust
use petgraph::prelude::*;
use petgraph::graph::node_index as n;
use petgraph::visit::depth_first_search;
use petgraph::visit::{DfsEvent, Control};

let gr: Graph<(), ()> = Graph::from_edges(&[
    (0, 1), (0, 2), (0, 3),
    (1, 3),
    (2, 3), (2, 4),
    (4, 0), (4, 5),
]);

// record each predecessor, mapping node → node
let mut predecessor = vec![NodeIndex::end(); gr.node_count()];
let start = n(0);
let goal = n(5);
depth_first_search(&gr, Some(start), |event| {
    if let DfsEvent::TreeEdge(u, v) = event {
        predecessor[v.index()] = u;
        if v == goal {
            return Control::Break(v);
        }
    }
    Control::Continue
});

let mut next = goal;
let mut path = vec![next];
while next != start {
    let pred = predecessor[next.index()];
    path.push(pred);
    next = pred;
}
path.reverse();
assert_eq!(&path, &[n(0), n(2), n(4), n(5)]);
```

--------------------------------

### Find paths to multiple targets using all_simple_paths_multi

Source: https://docs.rs/petgraph/latest/petgraph/algo/simple_paths/fn.all_simple_paths_multi.html

Demonstrates finding all simple paths from a starting node to a set of target nodes in a directed graph.

```rust
use petgraph::{algo, prelude::*};
use hashbrown::HashSet;
use std::collections::hash_map::RandomState;

let mut graph = DiGraph::<&str, i32>::new();

let a = graph.add_node("a");
let b = graph.add_node("b");
let c = graph.add_node("c");
let d = graph.add_node("d");
graph.extend_with_edges(&[(a, b, 1), (b, c, 1), (b, d, 1)]);

// Find paths from "a" to either "c" or "d".
let targets = HashSet::from_iter([c, d]);
let mut paths = algo::all_simple_paths_multi::<Vec<_>, _, RandomState>(&graph, a, &targets, 0, None)
    .collect::<Vec<_>>();

paths.sort_by_key(|p| p.clone());
let expected_paths = vec![
    vec![a, b, c],
    vec![a, b, d],
];

assert_eq!(paths, expected_paths);
```

--------------------------------

### Bfs Traversal Example

Source: https://docs.rs/petgraph/latest/petgraph/visit/struct.Bfs.html

Demonstrates performing a BFS traversal while maintaining mutable access to the graph.

```rust
use petgraph::Graph;
use petgraph::visit::Bfs;

let mut graph = Graph::<_,()>::new();
let a = graph.add_node(0);

let mut bfs = Bfs::new(&graph, a);
while let Some(nx) = bfs.next(&graph) {
    // we can access `graph` mutably here still
    graph[nx] += 1;
}

assert_eq!(graph[a], 1);
```

--------------------------------

### Basic Graph Implementation in Main

Source: https://docs.rs/petgraph/latest/src/petgraph/lib.rs.html

A minimal example of creating an undirected graph within a Rust main function.

```text
use petgraph::graph::UnGraph;

fn main() {
    let g = UnGraph::<(), ()>::from_edges(&[(0, 1), (1, 2), (2, 3), (0, 3)]);
```

--------------------------------

### Compute All-Pairs Shortest Paths

Source: https://docs.rs/petgraph/latest/src/petgraph/algo/floyd_warshall.rs.html

Example demonstrating the use of floyd_warshall_path to calculate shortest paths and distances in a directed graph.

```rust
use petgraph::{prelude::*, Graph, Directed};
use petgraph::algo::floyd_warshall::floyd_warshall_path;
use std::collections::HashMap;

let mut graph: Graph<(), (), Directed> = Graph::new();
let a = graph.add_node(());
let b = graph.add_node(());
let c = graph.add_node(());
let d = graph.add_node(());

graph.extend_with_edges(&[
   (a, b),
   (a, c),
   (a, d),
   (b, c),
   (b, d),
   (c, d)
]);

let weight_map: HashMap<(NodeIndex, NodeIndex), i32> = [
   ((a, a), 0), ((a, b), 1), ((a, c), 4), ((a, d), 10),
   ((b, b), 0), ((b, c), 2), ((b, d), 2),
   ((c, c), 0), ((c, d), 2)
].iter().cloned().collect();
//     ----- b --------
//    |      ^         |
//    |    1 |    4    v
//  2 |      a ------> c
//    |   10 |         | 2
//    |      v         v
//     --->  d <------- 

let inf = std::i32::MAX;
let expected_res: HashMap<(NodeIndex, NodeIndex), i32> = [
   ((a, a), 0), ((a, b), 1), ((a, c), 3), ((a, d), 3),
   ((b, a), inf), ((b, b), 0), ((b, c), 2), ((b, d), 2),
   ((c, a), inf), ((c, b), inf), ((c, c), 0), ((c, d), 2),
   ((d, a), inf), ((d, b), inf), ((d, c), inf), ((d, d), 0),
].iter().cloned().collect();


let (res, prev) = floyd_warshall_path(&graph, |edge| {
    if let Some(weight) = weight_map.get(&(edge.source(), edge.target())) {
        *weight
    } else {
        inf
    }
}).unwrap();

assert_eq!(prev[0][2], Some(1));

let nodes = [a, b, c, d];
for node1 in &nodes {
    for node2 in &nodes {
        assert_eq!(res.get(&(*node1, *node2)).unwrap(), expected_res.get(&(*node1, *node2)).unwrap());
    }
}
```

--------------------------------

### Test Multi-Target Paths Inline

Source: https://docs.rs/petgraph/latest/src/petgraph/algo/simple_paths.rs.html

Example of finding paths to multiple targets in an undirected graph.

```rust
    #[test]
    fn test_multi_target_paths_inline() {
        let graph = UnGraph::<i32, ()>::from_edges([(0, 1), (1, 2), (2, 3)]);
        let targets = HashSet::from_iter([2.into(), 3.into()]);
        let paths: HashSet<Vec<_>> =
            all_simple_paths_multi::<_, _, RandomState>(&graph, 0.into(), &targets, 0, None)
                .map(|v: Vec<_>| v.into_iter().map(|i| i.index()).collect())
                .collect();
        let expected: HashSet<Vec<_>> = HashSet::from_iter([vec![0, 1, 2], vec![0, 1, 2, 3]]);
        assert_eq!(paths, expected);
    }
```

--------------------------------

### Compute shortest paths with dijkstra in Rust

Source: https://docs.rs/petgraph/latest/petgraph/algo/dijkstra/fn.dijkstra.html

Demonstrates calculating shortest path costs from a starting node in a directed graph using a constant edge cost.

```rust
use petgraph::Graph;
use petgraph::algo::dijkstra;
use petgraph::prelude::*;
use hashbrown::HashMap;

let mut graph: Graph<(), (), Directed> = Graph::new();
let a = graph.add_node(()); // node with no weight
let b = graph.add_node(());
let c = graph.add_node(());
let d = graph.add_node(());
let e = graph.add_node(());
let f = graph.add_node(());
let g = graph.add_node(());
let h = graph.add_node(());
// z will be in another connected component
let z = graph.add_node(());

graph.extend_with_edges(&[
    (a, b),
    (b, c),
    (c, d),
    (d, a),
    (e, f),
    (b, e),
    (f, g),
    (g, h),
    (h, e),
]);
// a ----> b ----> e ----> f
// ^       |       ^       |
// |       v       |       v
// d <---- c       h <---- g

let expected_res: HashMap<NodeIndex, usize> = [
    (a, 3),
    (b, 0),
    (c, 1),
    (d, 2),
    (e, 1),
    (f, 2),
    (g, 3),
    (h, 4),
].iter().cloned().collect();
let res = dijkstra(&graph, b, None, |_| 1);
assert_eq!(res, expected_res);
// z is not inside res because there is not path from b to z.
```

--------------------------------

### DFS with Result Control Flow

Source: https://docs.rs/petgraph/latest/petgraph/visit/fn.depth_first_search.html

Example showing how to use Result to terminate the search when a specific event, such as a back edge, is encountered.

```rust
use petgraph::graph::node_index as n;
use petgraph::prelude::*;
use petgraph::visit::depth_first_search;
use petgraph::visit::{DfsEvent, Time};

let gr: Graph<(), ()> = Graph::from_edges(&[(0, 1), (1, 2), (1, 1), (2, 1)]);
let start = n(0);
let mut back_edges = 0;
let mut discover_time = 0;
// Stop the search, the first time a BackEdge is encountered.
let result = depth_first_search(&gr, Some(start), |event| {
    match event {
        // In the cases where Ok(()) is returned,
        // Result falls back to the implementation of Control on the value ().
        // In the case of (), this is to always return Control::Continue.
        // continuing the search.
        DfsEvent::Discover(_, Time(t)) => {
            discover_time = t;
            Ok(())
        }
        DfsEvent::BackEdge(_, _) => {
            back_edges += 1;
            // the implementation of ControlFlow for Result,
            // treats this Err value as Continue::Break
            Err(event)
        }
        _ => Ok(()),
    }
});

// Even though the graph has more than one cycle,
// The number of back_edges visited by the search should always be 1.
assert_eq!(back_edges, 1);
println!("discover time:{:?}", discover_time);
println!("number of backedges encountered: {}", back_edges);
println!("back edge: {:?}", result);
```

--------------------------------

### Compute Steiner Tree

Source: https://docs.rs/petgraph/latest/petgraph/algo/steiner_tree/fn.steiner_tree.html

Example demonstrating the usage of the steiner_tree function to find a Steiner tree for a set of terminals in an undirected graph.

```rust
use petgraph::Graph;
use petgraph::algo::steiner_tree::steiner_tree;
use petgraph::graph::UnGraph;
let mut graph = UnGraph::<(), i32>::default();
let a = graph.add_node(());
let b = graph.add_node(());
let c = graph.add_node(());
let d = graph.add_node(());
let e = graph.add_node(());
let f = graph.add_node(());
graph.extend_with_edges([
    (a, b, 7),
    (a, f, 6),
    (b, c, 1),
    (b, f, 5),
    (c, d, 1),
    (c, e, 3),
    (d, e, 1),
    (d, f, 4),
    (e, f, 10),
]);
let terminals = vec![a, c, e, f];
let tree = steiner_tree(&graph, &terminals);
assert_eq!(tree.edge_weights().sum::<i32>(), 12);
```

--------------------------------

### Initialize a new Rust project

Source: https://docs.rs/petgraph/latest/index.html

Commands to create a new directory and initialize a Rust project.

```bash
cargo new petgraph_example
cd petgraph_example
```

--------------------------------

### Build a directed graph

Source: https://docs.rs/petgraph/latest/petgraph/graph/struct.Graph.html

Demonstrates creating a new Graph instance and populating it with nodes and edges.

```rust
use petgraph::Graph;

let mut deps = Graph::<&str, &str>::new();
let pg = deps.add_node("petgraph");
let fb = deps.add_node("fixedbitset");
let qc = deps.add_node("quickcheck");
let rand = deps.add_node("rand");
let libc = deps.add_node("libc");
deps.extend_with_edges(&[
    (pg, fb), (pg, qc),
    (qc, rand), (rand, libc), (qc, libc),
]);
```

--------------------------------

### Initialize Petgraph Project

Source: https://docs.rs/petgraph/latest/petgraph

Commands to create a new Rust project and add the petgraph dependency.

```bash
cargo new petgraph_example
cd petgraph_example
```

```bash
cargo add petgraph
```

--------------------------------

### depth_first_search<G, I, F, C>(graph: G, starts: I, visitor: F) -> C

Source: https://docs.rs/petgraph/latest/petgraph/visit/fn.depth_first_search.html

Performs a depth-first search on the provided graph starting from the specified nodes. The visitor closure is invoked for each DfsEvent, and the return value controls the search flow.

```APIDOC
## Function: depth_first_search

### Description
Performs a recursive depth-first search on a graph. The search starts from nodes provided in the `starts` iterator and triggers the `visitor` closure for various events (discovery, finish, edge classification). The search can be controlled using the `ControlFlow` trait.

### Signature
`pub fn depth_first_search<G, I, F, C>(graph: G, starts: I, visitor: F) -> C`

### Parameters
- **graph** (G) - The graph to traverse. Must implement `IntoNeighbors` and `Visitable`.
- **starts** (I) - An iterator of starting node IDs.
- **visitor** (F) - A closure that takes a `DfsEvent` and returns a value implementing `ControlFlow`.

### Return Value
- **C** - The value returned by the visitor closure, which determines the final state or result of the search (e.g., `Control::Continue`, `Control::Break`, or `Result`).
```

--------------------------------

### neighbors

Source: https://docs.rs/petgraph/latest/petgraph/graph/type.DiGraph.html

Return an iterator of all nodes with an edge starting from a given node.

```APIDOC
## pub fn neighbors(&self, a: NodeIndex<Ix>) -> Neighbors<'_, E, Ix>

### Description
Return an iterator of all nodes with an edge starting from `a`. Produces an empty iterator if the node doesn’t exist.
```

--------------------------------

### Retrieve neighbors of a node

Source: https://docs.rs/petgraph/latest/src/petgraph/graph_impl/stable_graph/mod.rs.html

Returns an iterator of all nodes with an edge starting from the specified node.

```rust
pub fn neighbors(&self, a: NodeIndex<Ix>) -> Neighbors<'_, E, Ix> {
    self.neighbors_directed(a, Outgoing)
}
```

--------------------------------

### has_path_connecting

Source: https://docs.rs/petgraph/latest/petgraph/algo/fn.has_path_connecting.html

Checks if there exists a path starting at 'from' and reaching 'to' in the provided graph.

```APIDOC
## Function: has_path_connecting

### Description
Check if there exists a path starting at `from` and reaching `to`. If `from` and `to` are equal, this function returns true.

### Signature
`pub fn has_path_connecting<G>(g: G, from: G::NodeId, to: G::NodeId, space: Option<&mut DfsSpace<G::NodeId, G::Map>>) -> bool`

### Arguments
- **g** (G: IntoNeighbors + Visitable) - The input graph.
- **from** (G::NodeId) - The starting node of the desired path.
- **to** (G::NodeId) - The target node of the desired path.
- **space** (Option<&mut DfsSpace<G::NodeId, G::Map>>) - Optional workspace for graph traversal to avoid re-allocation.

### Returns
- **bool** - Returns `true` if a path exists or nodes are equal, otherwise `false`.

### Complexity
- **Time**: O(|V| + |E|)
- **Space**: O(|V|) or O(1) if `space` is provided.
```

--------------------------------

### Compute a Minimum Spanning Tree with Prim's Algorithm

Source: https://docs.rs/petgraph/latest/petgraph/algo/min_spanning_tree/fn.min_spanning_tree_prim.html

Demonstrates how to use min_spanning_tree_prim to generate a minimum spanning tree from an undirected graph and verify the result.

```rust
use petgraph::Graph;
use petgraph::algo::min_spanning_tree_prim;
use petgraph::data::FromElements;
use petgraph::graph::UnGraph;

let mut g = Graph::new_undirected();
let a = g.add_node(());
let b = g.add_node(());
let c = g.add_node(());
let d = g.add_node(());
let e = g.add_node(());
let f = g.add_node(());
g.extend_with_edges(&[
    (0, 1, 2.0),
    (0, 3, 4.0),
    (1, 2, 1.0),
    (1, 5, 7.0),
    (2, 4, 5.0),
    (4, 5, 1.0),
    (3, 4, 1.0),
]);

// The graph looks like this:
//     2       1
// a ----- b ----- c
// | 4     | 7     |
// d       f       | 5
// | 1     | 1     |
// \------ e ------/

let mst = UnGraph::<_, _>::from_elements(min_spanning_tree_prim(&g));
assert_eq!(g.node_count(), mst.node_count());
assert_eq!(mst.node_count() - 1, mst.edge_count());

// The resulting minimum spanning tree looks like this:
//     2       1
// a ----- b ----- c
// | 4
// d       f
// | 1     | 1
// \------ e

let mut edge_weight_vec = mst.edge_weights().cloned().collect::<Vec<_>>();
edge_weight_vec.sort_by(|a, b| a.partial_cmp(b).unwrap());
assert_eq!(edge_weight_vec , vec![1.0, 1.0, 1.0, 2.0, 4.0]);
```

--------------------------------

### is_bipartite_undirected

Source: https://docs.rs/petgraph/latest/petgraph/algo/fn.is_bipartite_undirected.html

Checks if the subgraph reachable from a start node is bipartite using a 2-coloring BFS algorithm.

```APIDOC
## Function: is_bipartite_undirected

### Description
Returns true if the subgraph reachable from the start node is bipartite. A graph is bipartite if its nodes can be divided into two disjoint and independent sets U and V such that every edge connects a node in U to one in V.

### Signature
`pub fn is_bipartite_undirected<G, N, VM>(g: G, start: N) -> bool`

### Arguments
- **g** (G) - The input graph. Must implement GraphRef, Visitable, and IntoNeighbors.
- **start** (N) - The starting node for the traversal.

### Returns
- **bool** - Returns true if the subgraph accessible from the start node is bipartite, false otherwise.

### Complexity
- **Time Complexity**: O(|V| + |E|)
- **Auxiliary Space**: O(|V|)

*Note: The algorithm treats the input graph as undirected and only checks the subgraph reachable from the start node.*
```

--------------------------------

### Generate Dot output with configuration

Source: https://docs.rs/petgraph/latest/src/petgraph/dot/mod.rs.html

Demonstrates how to create a Dot wrapper for a graph and print it using specific configuration options like EdgeNoLabel.

```rust
use petgraph::Graph;
use petgraph::dot::{Dot, Config};

let mut graph = Graph::<_, ()>::new();
graph.add_node("A");
graph.add_node("B");
graph.add_node("C");
graph.add_node("D");
graph.extend_with_edges(&[
    (0, 1), (0, 2), (0, 3),
    (1, 2), (1, 3),
    (2, 3),
]);

println!("{:?}", Dot::with_config(&graph, &[Config::EdgeNoLabel]));

// In this case the output looks like this:
//
// digraph {
//     0 [label="\"A\""]
//     1 [label="\"B\""]
//     2 [label="\"C\""]
//     3 [label="\"D\""]
//     0 -> 1 [ ]
//     0 -> 2 [ ]
//     0 -> 3 [ ]
//     1 -> 2 [ ]
//     1 -> 3 [ ]
//     2 -> 3 [ ]
// }
```

--------------------------------

### NeighborsDirected Iterator Implementation

Source: https://docs.rs/petgraph/latest/src/petgraph/graphmap.rs.html

Iterator for directed neighbor traversal, filtering by specific direction or start node.

```rust
impl<N, Ty> Iterator for NeighborsDirected<'_, N, Ty>
where
    N: NodeTrait,
    Ty: EdgeType,
{
    type Item = N;
    fn next(&mut self) -> Option<N> {
        if Ty::is_directed() {
            let self_dir = self.dir;
            let start_node = self.start_node;
            (&mut self.iter)
                .filter_map(move |&(n, dir)| {
                    if dir == self_dir || n == start_node {
                        Some(n)
                    } else {
                        None
                    }
                })
                .next()
        } else {
            self.iter.next().map(|&(n, _)| n)
        }
    }
    fn size_hint(&self) -> (usize, Option<usize>) {
        let (lower, upper) = self.iter.size_hint();
        if Ty::is_directed() {
            (0, upper)
        } else {
            (lower, upper)
        }
    }
}
```

--------------------------------

### Graph Construction

Source: https://docs.rs/petgraph/latest/petgraph/graph/struct.Graph.html

Methods for initializing new graph instances.

```APIDOC
## new()

### Description
Create a new Graph with directed edges.

## new_undirected()

### Description
Create a new Graph with undirected edges.

## with_capacity(nodes: usize, edges: usize)

### Description
Create a new Graph with estimated capacity.
```

--------------------------------

### Convert container to vector for debugging

Source: https://docs.rs/petgraph/latest/src/petgraph/algo/feedback_arc_set.rs.html

Iterates through the container starting from the current node to collect indices into a vector.

```rust
/// For debug purposes
fn to_vec(&self, container: &mut Container) -> Vec<Ix> {
    let mut ixs = Vec::new();

    let mut node_ix = self.start;

    while let Some(n_ix) = node_ix {
        ixs.push(n_ix);

        node_ix = container[n_ix].pos_mut().next;
    }

    ixs
}
}
```

--------------------------------

### Topo::with_initials

Source: https://docs.rs/petgraph/latest/petgraph/visit/struct.Topo.html

Creates a new Topo traversal instance starting from a specific set of initial nodes.

```APIDOC
## pub fn with_initials<G, I>(graph: G, initials: I) -> Self

### Description
Creates a new `Topo` instance with a provided set of initial nodes. Note that nodes with incoming edges are ignored.

### Parameters
- **graph** (G) - Required - The graph to traverse.
- **initials** (I) - Required - An iterator of node identifiers to start the traversal from.
```

--------------------------------

### Compute shortest path with A*

Source: https://docs.rs/petgraph/latest/petgraph/algo/astar/fn.astar.html

Demonstrates finding the shortest path in a graph using astar with a custom edge cost closure and a trivial heuristic.

```rust
use petgraph::Graph;
use petgraph::algo::astar;

let mut g = Graph::new();
let a = g.add_node((0., 0.));
let b = g.add_node((2., 0.));
let c = g.add_node((1., 1.));
let d = g.add_node((0., 2.));
let e = g.add_node((3., 3.));
let f = g.add_node((4., 2.));
g.extend_with_edges(&[
    (a, b, 2),
    (a, d, 4),
    (b, c, 1),
    (b, f, 7),
    (c, e, 5),
    (e, f, 1),
    (d, e, 1),
]);

// Graph represented with the weight of each edge
// Edges with '*' are part of the optimal path.
//
//     2       1
// a ----- b ----- c
// | 4*    | 7     |
// d       f       | 5
// | 1*    | 1*    |
// \------ e ------/

let path = astar(&g, a, |finish| finish == f, |e| *e.weight(), |_| 0);
assert_eq!(path, Some((6, vec![a, d, e, f])));
```

--------------------------------

### Create an undirected graph

Source: https://docs.rs/petgraph/latest/index.html

Example code to define an undirected graph using UnGraph and print its structure.

```rust
use petgraph::graph::UnGraph;

fn main() {
    let g = UnGraph::<(), ()>::from_edges(&[(0, 1), (1, 2), (2, 3), (0, 3)]);

    println!("Graph: {:?}", g);
}
```

--------------------------------

### edges

Source: https://docs.rs/petgraph/latest/petgraph/graphmap/type.DiGraphMap.html

Returns an iterator of target nodes with an edge starting from the specified node, paired with their respective edge weights.

```APIDOC
## pub fn edges(&self, a: N) -> Edges<'_, N, E, Ty, S>

### Description
Return an iterator of target nodes with an edge starting from `a`, paired with their respective edge weights. For directed graphs, this returns outgoing edges; for undirected, it returns all edges connected to `a`.
```

--------------------------------

### new

Source: https://docs.rs/petgraph/latest/petgraph/graphmap/struct.GraphMap.html

Creates a new, empty GraphMap instance.

```APIDOC
## pub fn new() -> Self

### Description
Creates a new empty GraphMap instance.
```

--------------------------------

### Compute a Minimum Spanning Tree with Rust

Source: https://docs.rs/petgraph/latest/petgraph/algo/min_spanning_tree/fn.min_spanning_tree.html

Demonstrates how to construct an undirected graph, compute its minimum spanning tree using min_spanning_tree, and verify the result using from_elements.

```rust
use petgraph::Graph;
use petgraph::algo::min_spanning_tree;
use petgraph::data::FromElements;
use petgraph::graph::UnGraph;

let mut g = Graph::new_undirected();
let a = g.add_node(());
let b = g.add_node(());
let c = g.add_node(());
let d = g.add_node(());
let e = g.add_node(());
let f = g.add_node(());
g.extend_with_edges(&[
    (0, 1, 2.0),
    (0, 3, 4.0),
    (1, 2, 1.0),
    (1, 5, 7.0),
    (2, 4, 5.0),
    (4, 5, 1.0),
    (3, 4, 1.0),
]);

// The graph looks like this:
//     2       1
// a ----- b ----- c
// | 4     | 7     |
// d       f       |
// | 1     | 1     |
// \------ e ------/

let mst = UnGraph::<_, _>::from_elements(min_spanning_tree(&g));
assert_eq!(g.node_count(), mst.node_count());
assert_eq!(mst.node_count() - 1, mst.edge_count());

// The resulting minimum spanning tree looks like this:
//     2       1
// a ----- b ----- c
// | 4             
// d       f       
// | 1     | 1       
// \------ e

let mut edge_weight_vec = mst.edge_weights().cloned().collect::<Vec<_>>();
edge_weight_vec.sort_by(|a, b| a.partial_cmp(b).unwrap());
assert_eq!(edge_weight_vec , vec![1.0, 1.0, 1.0, 2.0, 4.0]);
```

--------------------------------

### Perform DFS Traversal

Source: https://docs.rs/petgraph/latest/petgraph/visit/struct.Dfs.html

Example of using Dfs to traverse a graph while maintaining mutable access to the graph instance.

```rust
use petgraph::Graph;
use petgraph::visit::Dfs;

let mut graph = Graph::<_,()>::new();
let a = graph.add_node(0);

let mut dfs = Dfs::new(&graph, a);
while let Some(nx) = dfs.next(&graph) {
    // we can access `graph` mutably here still
    graph[nx] += 1;
}

assert_eq!(graph[a], 1);
```

--------------------------------

### Traverse Future Cone

Source: https://docs.rs/petgraph/latest/src/petgraph/acyclic.rs.html

Traverses the graph starting from a node to find reachable nodes within a specific topological range.

```rust
    fn future_cone(
        &self,
        start: G::NodeId,
        min_position: TopologicalPosition,
        max_position: TopologicalPosition,
        res: &mut BTreeMap<TopologicalPosition, G::NodeId>,
    ) -> Result<(), Cycle<G::NodeId>>
    where
        G::NodeId: IndexType,
    {
        dfs(
            &self.graph,
            start,
            &self.order_map,
            |order| {
                debug_assert!(order >= min_position, "invalid topological order");
                match order.cmp(&max_position) {
                    Ordering::Less => Ok(true),           // node within [min_node, max_node]
                    Ordering::Equal => Err(Cycle(start)), // cycle!
                    Ordering::Greater => Ok(false),       // node beyond [min_node, max_node]
                }
            },
            res,
        )
```

--------------------------------

### Check Bipartiteness of an Undirected Graph

Source: https://docs.rs/petgraph/latest/src/petgraph/algo/mod.rs.html

Determines if a graph is bipartite starting from a specific node using a 2-coloring BFS approach.

```rust
pub fn is_bipartite_undirected<G, N, VM>(g: G, start: N) -> bool
where
    G: GraphRef + Visitable<NodeId = N, Map = VM> + IntoNeighbors<NodeId = N>,
    N: Copy + PartialEq + core::fmt::Debug,
    VM: VisitMap<N>,
{
    let mut red = g.visit_map();
    red.visit(start);
    let mut blue = g.visit_map();

    let mut stack = ::alloc::collections::VecDeque::new();
    stack.push_front(start);

    while let Some(node) = stack.pop_front() {
        let is_red = red.is_visited(&node);
        let is_blue = blue.is_visited(&node);

        assert!(is_red ^ is_blue);

        for neighbour in g.neighbors(node) {
            let is_neigbour_red = red.is_visited(&neighbour);
            let is_neigbour_blue = blue.is_visited(&neighbour);

            if (is_red && is_neigbour_red) || (is_blue && is_neigbour_blue) {
                return false;
            }

            if !is_neigbour_red && !is_neigbour_blue {
                //hasn't been visited yet

                match (is_red, is_blue) {
                    (true, false) => {
                        blue.visit(neighbour);
                    }
                    (false, true) => {
                        red.visit(neighbour);
                    }
                    (_, _) => {
                        panic!("Invariant doesn't hold");
                    }
                }

                stack.push_back(neighbour);
            }
        }
    }

    true
}
```

--------------------------------

### Dot::with_config

Source: https://docs.rs/petgraph/latest/petgraph/dot/struct.Dot.html

Creates a new Dot formatting wrapper with custom configuration options.

```APIDOC
### pub fn with_config(graph: G, config: &'a [Config]) -> Self

Creates a `Dot` formatting wrapper with custom configuration.
```

--------------------------------

### Construct and analyze an undirected graph

Source: https://docs.rs/petgraph/latest/index.html

Demonstrates creating an undirected graph, calculating shortest paths with Dijkstra, finding a minimum spanning tree, and exporting to Graphviz DOT format.

```rust
use petgraph::graph::UnGraph;
use petgraph::algo::{dijkstra, min_spanning_tree};
use petgraph::data::FromElements;
use petgraph::dot::{Dot, Config};
use petgraph::visit::NodeIndexable;

// 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 [ ]
// }
```

--------------------------------

### TarjanScc::new

Source: https://docs.rs/petgraph/latest/petgraph/algo/scc/tarjan_scc/struct.TarjanScc.html

Creates a new instance of TarjanScc.

```APIDOC
## pub fn new() -> Self

### Description
Creates a new `TarjanScc` instance to be used for computing strongly connected components.
```

--------------------------------

### Initialize GraphMap

Source: https://docs.rs/petgraph/latest/src/petgraph/graphmap.rs.html

Methods for creating new GraphMap instances with optional capacity and hasher configurations.

```rust
pub fn new() -> Self
    where
        S: Default,
    {
        Self::default()
    }
```

```rust
pub fn with_capacity(nodes: usize, edges: usize) -> Self
    where
        S: Default,
    {
        Self {
            nodes: IndexMap::with_capacity_and_hasher(nodes, S::default()),
            edges: IndexMap::with_capacity_and_hasher(edges, S::default()),
            ty: PhantomData,
        }
    }
```

```rust
pub fn with_capacity_and_hasher(nodes: usize, edges: usize, hasher: S) -> Self
    where
        S: Clone,
    {
        Self {
            nodes: IndexMap::with_capacity_and_hasher(nodes, hasher.clone()),
            edges: IndexMap::with_capacity_and_hasher(edges, hasher),
            ty: PhantomData,
        }
    }
```

--------------------------------

### Initialize MatrixGraph

Source: https://docs.rs/petgraph/latest/src/petgraph/matrix_graph.rs.html

Methods for creating a new MatrixGraph with specific capacity and hasher requirements.

```rust
pub fn with_capacity(node_capacity: usize) -> Self
where
    S: Default,
{
    Self::with_capacity_and_hasher(node_capacity, Default::default())
}

pub fn with_capacity_and_hasher(node_capacity: usize, hasher: S) -> Self {
    let mut m = Self {
        node_adjacencies: vec![],
        node_capacity: 0,
        nodes: IdStorage::with_capacity_and_hasher(node_capacity, hasher),
        nb_edges: 0,
        ty: PhantomData,
        ix: PhantomData,
    };

    debug_assert!(node_capacity <= <Ix as IndexType>::max().index());
    if node_capacity > 0 {
        m.extend_capacity_for_node(NodeIndex::new(node_capacity - 1), true);
    }

    m
}
```
Tokens:
Raw