rustworkx-core

https://docs.rs/rustworkx-core/0.17.1/rustworkx_core
Admin
rustworkx-core is a graph algorithm crate built on top of petgraph that provides generic graph...
Tokens:135,614
Snippets:893
Trust Score:9.1
Update:5 months ago
Show doc for...
Tokens:
Raw
### Depth First Search Example with Control Flow

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/traversal/fn.depth_first_search.html

This example demonstrates finding a path from a start node to a goal node using DFS and breaking the search early once the goal is reached. It records predecessors to reconstruct the path.

```rust
use rustworkx_core::petgraph::prelude::*;
use rustworkx_core::petgraph::graph::node_index as n;
use rustworkx_core::petgraph::visit::Control;

use rustworkx_core::traversal::{DfsEvent, depth_first_search};

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)]);
```

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

### Breadth-First Search Example

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/traversal/fn.breadth_first_search.html

Demonstrates finding a path from a start node to a goal node using BFS. It records predecessors and breaks the search once the goal is reached. Requires `Control` to manage the search flow.

```rust
use rustworkx_core::petgraph::prelude::*
use rustworkx_core::petgraph::graph::node_index as n
use rustworkx_core::petgraph::visit::Control

use rustworkx_core::traversal::{BfsEvent, breadth_first_search};

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);
breadth_first_search(&gr, Some(start), |event| {
    if let BfsEvent::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)]);
```

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

### Example Usage of line_graph

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/line_graph/fn.line_graph.html

An example demonstrating how to construct the line graph of an undirected graph and verify the output.

```APIDOC
## Example

```rust
use rustworkx_core::line_graph::line_graph;
use rustworkx_core::petgraph::visit::EdgeRef;
use rustworkx_core::petgraph::Graph;
use hashbrown::HashMap;
use petgraph::graph::{EdgeIndex, NodeIndex};
use petgraph::Undirected;

let input_graph = 
  Graph::<(), (), Undirected>::from_edges(&[(0, 1), (0, 2), (1, 2), (0, 3)]);

let (output_graph, output_edge_map): (
    petgraph::graph::UnGraph<(), ()>,
    HashMap<petgraph::prelude::EdgeIndex, petgraph::prelude::NodeIndex>,
) = line_graph(&input_graph, || (), || ());

let output_edge_list = output_graph
    .edge_references()
    .map(|edge| (edge.source().index(), edge.target().index()))
    .collect::<Vec<(usize, usize)>>();

let expected_edge_list = vec![(3, 1), (3, 0), (1, 0), (2, 0), (2, 1)];
let expected_edge_map: HashMap<EdgeIndex, NodeIndex> = [
    (EdgeIndex::new(0), NodeIndex::new(0)),
    (EdgeIndex::new(1), NodeIndex::new(1)),
    (EdgeIndex::new(2), NodeIndex::new(2)),
    (EdgeIndex::new(3), NodeIndex::new(3)),
]
.into_iter()
.collect();

assert_eq!(output_edge_list, expected_edge_list);
assert_eq!(output_edge_map, expected_edge_map);
```
```

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

### Dijkstra Search Example

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/traversal/fn.dijkstra_search.html

An example demonstrating how to use dijkstra_search to find the shortest path and control the traversal flow.

```APIDOC
use rustworkx_core::petgraph::prelude::*;
use rustworkx_core::petgraph::graph::node_index as n;
use rustworkx_core::petgraph::visit::Control;

use rustworkx_core::traversal::{DijkstraEvent, dijkstra_search};

let gr: Graph<(), ()> = Graph::from_edges(&[
    (0, 1), (0, 2), (0, 3), (0, 4),
    (1, 3),
    (2, 3), (2, 4),
    (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);
dijkstra_search(
    &gr,
    Some(start),
    |edge| -> Result<usize, ()> {
        Ok(1)
    },
    |event| {
        match event {
            DijkstraEvent::Discover(v, _) => {
                if v == goal {
                    return Control::Break(v);
                }
            },
            DijkstraEvent::EdgeRelaxed(u, v, _) => {
                predecessor[v.index()] = u;
            },
            _ => {}
        };

        Control::Continue
    },
).unwrap();

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(4), n(5)]);
```

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

### Lexicographical Topological Sort Example

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/dag_algo/fn.lexicographical_topological_sort.html

Demonstrates how to perform a lexicographical topological sort on a DAG. This example uses a StableDiGraph and a closure to define the sorting key based on node weights. It also shows the usage of the `initial` parameter to start the sort from specific nodes.

```rust
use std::convert::Infallible;

use rustworkx_core::dag_algo::lexicographical_topological_sort;
use rustworkx_core::petgraph::stable_graph::{StableDiGraph, NodeIndex};

let mut graph: StableDiGraph<u8, ()> = StableDiGraph::new();
let mut nodes: Vec<NodeIndex> = Vec::new();
for weight in 0..9 {
    nodes.push(graph.add_node(weight));
}
let edges = [
        (nodes[0], nodes[1]),
        (nodes[0], nodes[2]),
        (nodes[1], nodes[3]),
        (nodes[2], nodes[4]),
        (nodes[3], nodes[4]),
        (nodes[4], nodes[5]),
        (nodes[5], nodes[6]),
        (nodes[4], nodes[7]),
        (nodes[6], nodes[8]),
        (nodes[7], nodes[8]),
];
for (source, target) in edges {
    graph.add_edge(source, target, ());
}
let sort_fn = |index: NodeIndex| -> Result<String, Infallible> { Ok(graph[index].to_string()) };
let initial = [nodes[6], nodes[7]];
let result = lexicographical_topological_sort(&graph, sort_fn, true, Some(&initial));
let expected = vec![
    nodes[6],
    nodes[5],
    nodes[7],
    nodes[4],
    nodes[2],
    nodes[3],
    nodes[1],
    nodes[0]
];
assert_eq!(result, Ok(expected));

```

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

### Example of contract_nodes_simple

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/graph_ext/contraction/trait.ContractNodesSimpleDirected.html

Demonstrates how to use contract_nodes_simple to merge nodes 'b' and 'c' into a new node 'm'. The example shows how edge weights are combined and how the new node connects to existing nodes. It uses a closure to define the edge weight combination logic.

```rust
use std::convert::Infallible;
use petgraph::prelude::*;
use rustworkx_core::graph_ext::*;

// Performs the following transformation:
//                          ┌─┐
//     ┌─┐                  │a│
//  ┌0─┤a├─1┐               └┬┘
//  │  └─┘  │                1
// ┌▼┐     ┌▼┐              ┌▼┐
// │b│     │c│     ───►     │m│
// └┬┘     └┬┘              └┬┘
//  │  ┌─┐  │                3
//  └2►│d│◄3┘               ┌▼┐
//     └─┘                  │d│
//                          └─┘
let mut dag: StableDiGraph<char, usize> = StableDiGraph::default();
let a = dag.add_node('a');
let b = dag.add_node('b');
let c = dag.add_node('c');
let d = dag.add_node('d');
dag.add_edge(a.clone(), b.clone(), 0);
dag.add_edge(a.clone(), c.clone(), 1);
dag.add_edge(b.clone(), d.clone(), 2);
dag.add_edge(c.clone(), d.clone(), 3);

let m = dag.contract_nodes_simple([b, c], 'm', true, |&e1, &e2| Ok::<_, Infallible>(if e1 > e2 { e1 } else { e2 } )).unwrap();
assert_eq!(dag.edge_weight(dag.find_edge(a.clone(), m.clone()).unwrap()).unwrap(), &1);
assert_eq!(dag.edge_weight(dag.find_edge(m.clone(), d.clone()).unwrap()).unwrap(), &3);
```

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

### path_graph Example

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/generators/fn.path_graph.html

Example usage of the path_graph function to create an undirected graph with 4 nodes and default weights.

```APIDOC
## Example
```rust
use rustworkx_core::petgraph;
use rustworkx_core::generators::path_graph;
use rustworkx_core::petgraph::visit::EdgeRef;

let g: petgraph::graph::UnGraph<(), ()> = path_graph(
    Some(4),
    None,
    || {()},
    || {()},
    false
).unwrap();
assert_eq!(
    vec![(0, 1), (1, 2), (2, 3)],
    g.edge_references()
        .map(|edge| (edge.source().index(), edge.target().index()))
        .collect::<Vec<(usize, usize)>>(),
)
```
```

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

### IndexMap Indexing Example

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/dictmap/type.DictMap.html

Demonstrates accessing IndexMap values using a key. Panics if the key is not present.

```rust
use indexmap::IndexMap;

let mut map = IndexMap::new();
for word in "Lorem ipsum dolor sit amet".split_whitespace() {
    map.insert(word.to_lowercase(), word.to_uppercase());
}
assert_eq!(map["lorem"], "LOREM");
assert_eq!(map["ipsum"], "IPSUM");
```

```rust
use indexmap::IndexMap;

let mut map = IndexMap::new();
map.insert("foo", 1);
println!("{:?}", map["bar"]); // panics!
```

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

### first

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/dictmap/type.DictMap.html

Get the first key-value pair. Computes in O(1) time.

```APIDOC
## first

### Description
Get the first key-value pair
Computes in **O(1)** time.

### Method Signature
`pub fn first(&self) -> Option<(&K, &V)>`
```

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

### Example Usage of Token Swapper

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/token_swapper/fn.token_swapper.html

Demonstrates how to use the token_swapper function with a sample graph and mapping. It shows the necessary imports and how to call the function, asserting the expected output length.

```rust
use hashbrown::HashMap;
use rustworkx_core::petgraph;
use rustworkx_core::token_swapper::token_swapper;
use rustworkx_core::petgraph::graph::NodeIndex;

 let g = petgraph::graph::UnGraph::<(), ()>::from_edges(&[(0, 1), (1, 2), (2, 3)]);
 let mapping = HashMap::from([
  (NodeIndex::new(0), NodeIndex::new(0)),
  (NodeIndex::new(1), NodeIndex::new(3)),
  (NodeIndex::new(3), NodeIndex::new(1)),
  (NodeIndex::new(2), NodeIndex::new(2)),
 ]);
 // Do the token swap
 let output = token_swapper(&g, mapping, Some(4), Some(4), Some(50)).expect("Swap mapping failed.");
 assert_eq!(3, output.len());

```

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

### Example usage of k_shortest_path

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/shortest_path/fn.k_shortest_path.html

Demonstrates how to use the k_shortest_path function to find the 2 shortest paths from a given node in an undirected graph. The edge costs are set to a constant value.

```rust
use rustworkx_core::petgraph;
use rustworkx_core::petgraph::graph::NodeIndex;
use rustworkx_core::shortest_path::k_shortest_path;
use hashbrown::HashMap;
use rustworkx_core::Result;

let g = petgraph::graph::UnGraph::<i32, _>::from_edges(&[
    (0, 1), (1, 2), (2, 3), (3, 0), (4, 5), (1, 4), (5, 6), (6, 7), (7, 5)
]);

let res: Result<HashMap<NodeIndex, f64>> = k_shortest_path(
    &g, NodeIndex::new(1), None, 2,
    |e: rustworkx_core::petgraph::graph::EdgeReference<&'static str>| Ok(1.0),
);

let output = res.unwrap();
let expected: HashMap<NodeIndex, f64> = [
    (NodeIndex::new(0), 3.0),
    (NodeIndex::new(1), 2.0),
    (NodeIndex::new(2), 3.0),
    (NodeIndex::new(3), 2.0),
    (NodeIndex::new(4), 3.0),
    (NodeIndex::new(5), 4.0),
    (NodeIndex::new(6), 4.0),
    (NodeIndex::new(7), 4.0),
].iter().cloned().collect();
assert_eq!(expected, output);
```

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

### Example Usage

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/shortest_path/fn.bellman_ford.html

Demonstrates how to use the `bellman_ford` function with a `petgraph::Graph` to find shortest paths, including handling negative edge weights.

```APIDOC
## Example
```rust
use rustworkx_core::petgraph::Graph;
use rustworkx_core::petgraph::prelude::*;
use rustworkx_core::dictmap::DictMap;
use rustworkx_core::shortest_path::bellman_ford;
use rustworkx_core::Result;

let mut graph : Graph<(),i32,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, 1),
    (b, c, 1),
    (c, d, 1),
    (d, a, 1),
    (e, f, -2),
    (b, e, -1),
    (f, g, 5),
    (g, h, 2),
    (h, e, -1)
]);
// a ----> b ----> e ----> f
// ^       |       ^       |
// |       v       |       v
// d <---- c       h <---- g

let expected_res: DictMap<NodeIndex, i32> = [
     (a, 3),
     (b, 0),
     (c, 1),
     (d, 2),
     (e, -1),
     (f, -3),
     (g, 2),
     (h, 4)
    ].iter().cloned().collect();
let res: Result<Option<DictMap<NodeIndex, i32>>> = bellman_ford(
    &graph, b, |x| Ok(*x.weight()), None
);
assert_eq!(res.unwrap().unwrap(), expected_res);
// z is not inside res because there is not path from b to z.
```
```

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

### BFS Successors Traversal

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/traversal/fn.bfs_successors.html

Demonstrates how to use `bfs_successors` to get nodes and their successors in BFS order. The example maps the `NodeId` to its index for easier assertion.

```rust
use rustworkx_core::traversal::bfs_successors;
use rustworkx_core::petgraph::stable_graph::{StableDiGraph, NodeIndex};

let graph: StableDiGraph<(), ()> = StableDiGraph::from_edges(&[
    (0, 1), (1, 2), (1, 3), (2, 4), (3, 4), (4, 5)
]);
let successors: Vec<(usize, Vec<usize>)> = bfs_successors(&graph, NodeIndex::new(3))
    .map(|(x, succ)| (x.index(), succ.iter().map(|y| y.index()).collect()))
    .collect();
assert_eq!(vec![(3_usize, vec![4_usize]), (4, vec![5]), (5, vec![])], successors);
```

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

### Index<RangeFrom<usize>>

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/dictmap/type.DictMap.html

Performs indexing on IndexMap using a range starting from an index.

```APIDOC
## Index<RangeFrom<usize>>

### Description
Performs the indexing (`container[index]`) operation.

### Method
`index( &self, range: RangeFrom<usize>, ) -> &<IndexMap<K, V, S> as Index<RangeFrom<usize>>>::Output`

### Output Type
`Slice<K, V>`
```

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

### Bipartite Edge Coloring Example

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/bipartite_coloring/fn.bipartite_edge_color.html

Demonstrates how to use `bipartite_edge_color` on a `petgraph::Graph`. It checks if the coloring is successful and compares the resulting colors with the expected output.

```rust
use petgraph::graph::Graph;
use petgraph::graph::{EdgeIndex, NodeIndex};
use petgraph::Undirected;
use rustworkx_core::dictmap::*;
use rustworkx_core::bipartite_coloring::bipartite_edge_color;

let edge_list = vec![(0, 1), (1, 2), (2, 3), (3, 0)];
let graph = Graph::<(), (), Undirected>::from_edges(&edge_list);
let colors = bipartite_edge_color(&graph);
assert!(colors.is_ok());
let expected_colors: DictMap<EdgeIndex, usize> = [
    (EdgeIndex::new(0), 0),
    (EdgeIndex::new(1), 1),
    (EdgeIndex::new(2), 0),
    (EdgeIndex::new(3), 1),
]
.into_iter()
.collect();
assert_eq!(colors.unwrap(), expected_colors);
```

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

### Generate a 3x3 grid graph

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/generators/fn.grid_graph.html

This example demonstrates how to create a 3x3 undirected grid graph with no node or edge weights. It then asserts that the generated edges match the expected connections.

```rust
use rustworkx_core::petgraph;
use rustworkx_core::generators::grid_graph;
use rustworkx_core::petgraph::visit::EdgeRef;

let g: petgraph::graph::UnGraph<(), ()> = grid_graph(
    Some(3),
    Some(3),
    None,
    || {()},
    || {()},
    false
).unwrap();
assert_eq!(
    vec![(0, 3), (0, 1), (1, 4), (1, 2), (2, 5),
         (3, 6), (3, 4), (4, 7), (4, 5), (5, 8), (6, 7), (7, 8)],
    g.edge_references()
        .map(|edge| (edge.source().index(), edge.target().index()))
        .collect::<Vec<(usize, usize)>>()
)
```

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

### Greedy Node Coloring Example

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/coloring/fn.greedy_node_color.html

Demonstrates how to use the greedy_node_color function with a petgraph::Graph. This function colors nodes with higher degrees first using a largest-first strategy.

```rust
use petgraph::graph::Graph;
use petgraph::graph::NodeIndex;
use petgraph::Undirected;
use rustworkx_core::dictmap::*
use rustworkx_core::coloring::greedy_node_color;

let g = Graph::<(), (), Undirected>::from_edges(&[(0, 1), (0, 2)]);
let colors = greedy_node_color(&g);
let mut expected_colors = DictMap::new();
expected_colors.insert(NodeIndex::new(0), 0);
expected_colors.insert(NodeIndex::new(1), 1);
expected_colors.insert(NodeIndex::new(2), 1);
assert_eq!(colors, expected_colors);
```

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

### first_entry

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/dictmap/type.DictMap.html

Get the first entry in the map for in-place manipulation. Computes in O(1) time.

```APIDOC
## first_entry

### Description
Get the first entry in the map for in-place manipulation.
Computes in **O(1)** time.

### Method Signature
`pub fn first_entry(&mut self) -> Option<IndexedEntry<'_, K, V>>`
```

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

### Find Connected Components in an Undirected Graph

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/connectivity/fn.connected_components.html

This example demonstrates how to use `connected_components` to find all connected components in an undirected graph. It requires `petgraph` for graph representation and `hashbrown` for `HashSet`.

```rust
use std::iter::FromIterator;
use hashbrown::HashSet;
use petgraph::graph::Graph;
use petgraph::graph::NodeIndex;
use petgraph::{Undirected, Directed};
use petgraph::graph::node_index as ndx;
use rustworkx_core::connectivity::connected_components;

let graph = Graph::<(), (), Undirected>::from_edges(&[
    (0, 1),
    (1, 2),
    (2, 3),
    (3, 0),
    (4, 5),
    (5, 6),
    (6, 7),
    (7, 4),
]);
let components = connected_components(&graph);
let exp1 = HashSet::from_iter([ndx(0), ndx(1), ndx(3), ndx(2)]);
let exp2 = HashSet::from_iter([ndx(7), ndx(5), ndx(4), ndx(6)]);
let expected = vec![exp1, exp2];
assert_eq!(expected, components);
```

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

### Generate a Star Graph

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/generators/fn.star_graph.html

Generates a star graph with a specified number of nodes and default weights. The example verifies the structure of the generated undirected graph.

```rust
use rustworkx_core::petgraph;
use rustworkx_core::generators::star_graph;
use rustworkx_core::petgraph::visit::EdgeRef;

let g: petgraph::graph::UnGraph<(), ()> = star_graph(
    Some(4),
    None,
    || {()},
    || {()},
    false,
    false
).unwrap();
assert_eq!(
    vec![(0, 1), (0, 2), (0, 3)],
    g.edge_references()
        .map(|edge| (edge.source().index(), edge.target().index()))
        .collect::<Vec<(usize, usize)>>(),
)
```

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

### Greedy Edge Coloring Example

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/coloring/fn.greedy_edge_color.html

Demonstrates how to use greedy_edge_color to color the edges of an undirected graph. The function returns a mapping from edge IDs to their assigned color (usize).

```rust
use petgraph::graph::Graph;
use petgraph::graph::EdgeIndex;
use petgraph::Undirected;
use rustworkx_core::dictmap::*
use rustworkx_core::coloring::greedy_edge_color;

let g = Graph::<(), (), Undirected>::from_edges(&[(0, 1), (1, 2), (0, 2), (2, 3)]);
let colors = greedy_edge_color(&g);
let mut expected_colors = DictMap::new();
expected_colors.insert(EdgeIndex::new(0), 2);
expected_colors.insert(EdgeIndex::new(1), 0);
expected_colors.insert(EdgeIndex::new(2), 1);
expected_colors.insert(EdgeIndex::new(3), 2);
assert_eq!(colors, expected_colors);
```

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

### Contract Nodes Example

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/graph_ext/contraction/trait.ContractNodesUndirected.html

Demonstrates how to use `contract_nodes` to merge nodes 'b' and 'c' into a new node 'm'. This operation preserves edges connected to the contracted nodes, redirecting them to the new node.

```rust
use petgraph::prelude::*;
use rustworkx_core::graph_ext::*;

// Performs the following transformation:
//      ┌─┐
//      │a│
//      └┬┘              ┌─┐
//       0               │a│
//      ┌┴┐              └┬┘
//      │b│               0
//      └┬┘              ┌┴┐
//       1      ───►     │m│
//      ┌┴┐              └┬┘
//      │c│               2
//      └┬┘              ┌┴┐
//       2               │d│
//      ┌┴┐              └─┘
//      │d│
//      └─┘
let mut dag: StableUnGraph<char, usize> = StableUnGraph::default();
let a = dag.add_node('a');
let b = dag.add_node('b');
let c = dag.add_node('c');
let d = dag.add_node('d');
dag.add_edge(a.clone(), b.clone(), 0);
dag.add_edge(b.clone(), c.clone(), 1);
dag.add_edge(c.clone(), d.clone(), 2);

let m = dag.contract_nodes([b, c], 'm');
assert_eq!(dag.edge_weight(dag.find_edge(a.clone(), m.clone()).unwrap()).unwrap(), &0);
assert_eq!(dag.edge_weight(dag.find_edge(m.clone(), d.clone()).unwrap()).unwrap(), &2);
```

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

### Bellman-Ford Shortest Path Algorithm

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/shortest_path/fn.bellman_ford.html

Computes the shortest path distances from a start node. Handles negative edge weights but detects negative cycles. Optionally reconstructs the path.

```rust
use rustworkx_core::petgraph::Graph;
use rustworkx_core::petgraph::prelude::*;
use rustworkx_core::dictmap::DictMap;
use rustworkx_core::shortest_path::bellman_ford;
use rustworkx_core::Result;

let mut graph : Graph<(),i32,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, 1),
    (b, c, 1),
    (c, d, 1),
    (d, a, 1),
    (e, f, -2),
    (b, e, -1),
    (f, g, 5),
    (g, h, 2),
    (h, e, -1)
]);
// a ----> b ----> e ----> f
// ^       |       ^       |
// |       v       |       v
// d <---- c       h <---- g

let expected_res: DictMap<NodeIndex, i32> = [
     (a, 3),
     (b, 0),
     (c, 1),
     (d, 2),
     (e, -1),
     (f, -3),
     (g, 2),
     (h, 4)
    ].iter().cloned().collect();
let res: Result<Option<DictMap<NodeIndex, i32>>> = bellman_ford(
    &graph, b, |x| Ok(*x.weight()), None
);
assert_eq!(res.unwrap().unwrap(), expected_res);
// z is not inside res because there is not path from b to z.

```

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

### Generate a Binomial Tree Graph

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/generators/fn.binomial_tree_graph.html

Generates a binomial tree of order 4 with empty node and edge weights. Asserts that the generated edge list matches the expected structure. This example uses an undirected graph.

```rust
use rustworkx_core::petgraph;
use rustworkx_core::generators::binomial_tree_graph;
use rustworkx_core::petgraph::visit::EdgeRef;

let expected_edge_list = vec![
    (0, 1),
    (2, 3),
    (0, 2),
    (4, 5),
    (6, 7),
    (4, 6),
    (0, 4),
    (8, 9),
    (10, 11),
    (8, 10),
    (12, 13),
    (14, 15),
    (12, 14),
    (8, 12),
    (0, 8),
];
let g: petgraph::graph::UnGraph<(), ()> = binomial_tree_graph(
    4,
    None,
    || {()},
    || {()},
    false
).unwrap();
assert_eq!(
    expected_edge_list,
    g.edge_references()
        .map(|edge| (edge.source().index(), edge.target().index()))
        .collect::<Vec<(usize, usize)>>()
)
```

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

### Get Descendants of a Node

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/traversal/fn.descendants.html

Use the `descendants` function to retrieve all nodes reachable from a starting node, including the starting node itself. The result is collected into a vector of node indices for assertion.

```rust
use rustworkx_core::traversal::descendants;
use rustworkx_core::petgraph::stable_graph::{StableDiGraph, NodeIndex};

let graph: StableDiGraph<(), ()> = StableDiGraph::from_edges(&[
    (0, 1), (1, 2), (1, 3), (2, 4), (3, 4), (4, 5)
]);
let descendants: Vec<usize> = descendants(&graph, NodeIndex::new(3)).map(|x| x.index()).collect();
assert_eq!(vec![3_usize, 4, 5], descendants);
```

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

### Get ancestors of a node

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/traversal/fn.ancestors.html

Use this function to find all nodes that lead to the specified node in a directed graph. The output includes the starting node.

```rust
use rustworkx_core::traversal::ancestors;
use rustworkx_core::petgraph::stable_graph::{StableDiGraph, NodeIndex};

let graph: StableDiGraph<(), ()> = StableDiGraph::from_edges(&[
    (0, 1), (1, 2), (1, 3), (2, 4), (3, 4), (4, 5)
]);
let ancestors: Vec<usize> = ancestors(&graph, NodeIndex::new(3)).map(|x| x.index()).collect();
assert_eq!(vec![3_usize, 1, 0], ancestors);
```

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

### Depth First Search with Event Handling

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/traversal/fn.depth_first_search.html

This example demonstrates how to use the `depth_first_search` function to traverse a graph. It shows how to handle `DfsEvent`s, specifically `Discover` and `BackEdge`, and how to stop the search early by returning an `Err` from the event handler.

```APIDOC
## `depth_first_search` Example

### Description
Performs a depth-first search on a graph starting from a given node. It allows a callback function to process events during the traversal, such as discovering nodes or encountering back edges. The search can be controlled by the return value of the callback.

### Function Signature
```rust
pub fn depth_first_search<G, F, R, E>(graph: &G, start_node: Option<G::NodeId>, visitor: F) -> Result<R, E>
where
    G: GraphBase + Visitable + Data + NodeIndexable,
    F: FnMut(DfsEvent<G::NodeId, G::EdgeWeight>) -> Result<R, E>,
    R: ControlFlow,
    E: ControlFlow,
{
    // ... implementation details ...
}
```

### Parameters
* `graph`: The graph to traverse.
* `start_node`: The node to start the traversal from. If `None`, the traversal starts from an arbitrary node.
* `visitor`: A closure that is called for each `DfsEvent` encountered during the traversal. It should return a `Result` to control the flow of the search. Returning `Ok(())` continues the search, while returning `Err(E)` stops the search and returns the error value `E`.

### Events Handled by Visitor
* `DfsEvent::Discover(node, time)`: Called when a node is first discovered.
* `DfsEvent::Finish(node, time)`: Called when all descendants of a node have been visited.
* `DfsEvent::TreeEdge(u, v, weight)`: Called when traversing a tree edge from `u` to `v`.
* `DfsEvent::BackEdge(u, v, weight)`: Called when traversing a back edge from `u` to `v`.
* `DfsEvent::ForwardOrCrossEdge(u, v, weight)`: Called when traversing a forward or cross edge from `u` to `v`.

### Return Value
* `Ok(R)`: If the traversal completes without the visitor returning an `Err`. `R` is the value returned by the visitor when it signals to continue the search.
* `Err(E)`: If the visitor returns an `Err` to stop the search. `E` is the value returned by the visitor.

### Example Usage
```rust
use rustworkx_core::petgraph::graph::node_index as n;
use rustworkx_core::petgraph::prelude::*
use rustworkx_core::petgraph::visit::Time;
use rustworkx_core::traversal::{DfsEvent, depth_first_search};

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;

#[derive(Debug)]
struct BackEdgeFound {
    source: NodeIndex,
    target: NodeIndex,
}

// Stop the search, the first time a BackEdge is encountered.
let result = depth_first_search(&gr, Some(start), |event| {
    match event {
        DfsEvent::Discover(_, Time(t)) => {
            discover_time = t;
            Ok(())
        }
        DfsEvent::BackEdge(u, v, _) => {
            back_edges += 1;
            Err(BackEdgeFound {source: u, target: v})
        }
        _ => Ok(()),
    }
});

assert_eq!(back_edges, 1);
println!("discover time:{:?}", discover_time);
println!("number of backedges encountered: {}", back_edges);
println!("back edge: ({:?})", result.unwrap_err());
```
```

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

### distance_matrix

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/shortest_path/index.html

Get the distance matrix for a graph.

```APIDOC
## Function: distance_matrix

### Description
Get the distance matrix for a graph.

### Parameters
(No specific parameters documented in the source)
```

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

### get

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/dictmap/type.DictMap.html

Retrieves a reference to the value associated with a given key.

```APIDOC
## get<K, V, S, Q>

### Description
Returns a reference to the value stored for `key`, if it is present, else `None`. Computes in **O(1)** time (average).

### Method
`get`

### Parameters
- `key`: A reference to a value that can be hashed and is equivalent to the map's keys.

### Response
- `Option<&V>`: An `Option` containing a reference to the value if the key is found, otherwise `None`.
```

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

### last

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/dictmap/type.DictMap.html

Get the last key-value pair. Computes in O(1) time.

```APIDOC
## last

### Description
Get the last key-value pair
Computes in **O(1)** time.

### Method Signature
`pub fn last(&self) -> Option<(&K, &V)>`
```

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

### Greedy Node Coloring with Preset Colors Example

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/coloring/fn.greedy_node_color_with_preset_colors.html

Demonstrates how to use `greedy_node_color_with_preset_colors` to color a graph, assigning a preset color to a specific node and letting the algorithm determine colors for others. The `preset_color_fn` defines which nodes have preset colors and what those colors are.

```rust
use petgraph::graph::Graph;
use petgraph::graph::NodeIndex;
use petgraph::Undirected;
use rustworkx_core::dictmap::*
use std::convert::Infallible;
use rustworkx_core::coloring::greedy_node_color_with_preset_colors;

let preset_color_fn = |node_idx: NodeIndex| -> Result<Option<usize>, Infallible> {
    if node_idx.index() == 0 {
        Ok(Some(1))
    } else {
        Ok(None)
    }
};

let g = Graph::<(), (), Undirected>::from_edges(&[(0, 1), (0, 2)]);
let colors = greedy_node_color_with_preset_colors(&g, preset_color_fn).unwrap();
let mut expected_colors = DictMap::new();
expected_colors.insert(NodeIndex::new(0), 1);
expected_colors.insert(NodeIndex::new(1), 0);
expected_colors.insert(NodeIndex::new(2), 0);
assert_eq!(colors, expected_colors);
```

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

### Get DictMap Hasher

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/dictmap/type.DictMap.html

Returns a reference to the hash builder used by the DictMap.

```rust
pub fn hasher(&self) -> &S
```

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

### Find Simple Cycles in a Directed Graph

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/connectivity/fn.johnson_simple_cycles.html

This example demonstrates how to find all simple cycles in a directed graph using `johnson_simple_cycles`. It includes pre-processing to handle self-cycles by collecting them separately and removing the corresponding edges from the graph before calling the function. The resulting cycles are sorted for consistent comparison.

```rust
use rustworkx_core::petgraph::prelude::*;
use rustworkx_core::connectivity::johnson_simple_cycles;

let mut graph = DiGraph::<(), ()>::new();
graph.extend_with_edges([(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)]);

// Handle self cycles
let self_cycles_vec: Vec<NodeIndex> = graph
    .node_indices()
    .filter(|n| graph.neighbors(*n).any(|x| x == *n))
    .collect();
for node in &self_cycles_vec {
    while let Some(edge_index) = graph.find_edge(*node, *node) {
        graph.remove_edge(edge_index);
    }
}
let self_cycles = if self_cycles_vec.is_empty() {
           None
} else {
    Some(self_cycles_vec)
};

let mut cycles_iter = johnson_simple_cycles(&graph, self_cycles);

let mut cycles = Vec::new();
while let Some(mut cycle) = cycles_iter.next(&graph) {
    cycle.sort();
    cycles.push(cycle);
}

let expected = vec![
    vec![NodeIndex::new(0)],
    vec![NodeIndex::new(2)],
    vec![NodeIndex::new(0), NodeIndex::new(1), NodeIndex::new(2)],
    vec![NodeIndex::new(0), NodeIndex::new(2)],
    vec![NodeIndex::new(1), NodeIndex::new(2)],
];

assert_eq!(expected.len(), cycles.len());
for cycle in cycles {
    assert!(expected.contains(&cycle));
}

```

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

### last_entry

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/dictmap/type.DictMap.html

Get the last entry in the map for in-place manipulation. Computes in O(1) time.

```APIDOC
## last_entry

### Description
Get the last entry in the map for in-place manipulation.
Computes in **O(1)** time.

### Method Signature
`pub fn last_entry(&mut self) -> Option<IndexedEntry<'_, K, V>>`
```

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

### new

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/dictmap/type.DictMap.html

Creates a new, empty DictMap.

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

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

### last_mut

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/dictmap/type.DictMap.html

Get the last key-value pair, with mutable access to the value. Computes in O(1) time.

```APIDOC
## last_mut

### Description
Get the last key-value pair, with mutable access to the value
Computes in **O(1)** time.

### Method Signature
`pub fn last_mut(&mut self) -> Option<(&K, &mut V)>`
```

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

### first_mut

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/dictmap/type.DictMap.html

Get the first key-value pair, with mutable access to the value. Computes in O(1) time.

```APIDOC
## first_mut

### Description
Get the first key-value pair, with mutable access to the value
Computes in **O(1)** time.

### Method Signature
`pub fn first_mut(&mut self) -> Option<(&K, &mut V)>`
```

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

### Default Implementation

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/dictmap/type.DictMap.html

Provides a default empty IndexMap.

```APIDOC
## Default Implementation

### Description
Return an empty `IndexMap`.

### Method
`default() -> IndexMap<K, V, S>`
```

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

### Implement Any trait

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/err/enum.ContractError.html

Implements the Any trait for generic types, providing a way to get the TypeId of a value.

```rust
impl<T> Any for T
    fn type_id(&self) -> TypeId
```

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

### A* Shortest Path Algorithm

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/shortest_path/fn.astar.html

Computes the shortest path from a start node to a goal node using the A* algorithm. The goal is defined by a callback function. Edge costs must be non-negative. The estimate_cost function should be admissible (never overestimate) for optimal results. The graph must implement Visitable and IntoEdges traits.

```rust
use rustworkx_core::petgraph::graph::NodeIndex;
use rustworkx_core::petgraph::Graph;
use rustworkx_core::shortest_path::astar;
use rustworkx_core::Result;

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 res: Result<Option<(u64, Vec<NodeIndex>)>> = astar(
    &g, a, |finish| Ok(finish == f), |e| Ok(*e.weight()), |_| Ok(0)
);
let path = res.unwrap();
assert_eq!(path, Some((6, vec![a, d, e, f])));

```

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

### IndexMap Mutable Indexing by RangeFrom<usize>

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/dictmap/type.DictMap.html

Performs the mutable indexing operation for a range starting from a usize.

```APIDOC
## IndexMap Mutable Indexing by RangeFrom<usize>

### Description
Performs the mutable indexing (`container[index]`) operation for a range starting from a usize.

### Method
`index_mut(&mut self, range: RangeFrom<usize>) -> &mut <IndexMap<K, V, S> as Index<RangeFrom<usize>>>::Output`

### Parameters
- **range** (RangeFrom<usize>) - The range of indices starting from the specified usize.
```

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

### Create DictMap with Capacity and Hasher

Source: https://docs.rs/rustworkx-core/0.17.1/rustworkx_core/dictmap/type.DictMap.html

Creates a new DictMap with a specified initial capacity and a given hash builder. This operation computes in O(n) time.

```rust
pub fn with_capacity_and_hasher(n: usize, hash_builder: S) -> IndexMap<K, V, S>
```
Tokens:
Raw