Function longest_path

pub fn longest_path<G, F, T, E>(
    graph: G,
    weight_fn: F,
) -> Result<Option<(Vec<<G as GraphBase>::NodeId>, T)>, E>
where
    G: GraphProp<EdgeType = Directed> + IntoNodeIdentifiers + IntoEdgesDirected + Visitable,
    F: FnMut(G::EdgeRef) -> Result<T, E>,
    T: Num + Zero + PartialOrd + Copy,
    <G as GraphBase>::NodeId: Hash + Eq + PartialOrd,

Calculates the longest path in a directed acyclic graph (DAG).

This function computes the longest path by weight in a given DAG. It will return the longest path along with its total weight, or None if the graph contains cycles which make the longest path computation undefined.

Arguments

• graph: Reference to a directed graph.
• weight_fn - An input callable that will be passed the EdgeRef for each edge in the graph. The callable should return the weight of the edge as Result<T, E>. The weight must be a type that implements Num, Zero, PartialOrd, and Copy.

Type Parameters

• G: Type of the graph. Must be a directed graph.
• F: Type of the weight function.
• T: The type of the edge weight. Must implement Num, Zero, PartialOrd, and Copy.
• E: The type of the error that the weight function can return.

Returns

• None if the graph contains a cycle.
• Some((Vec<NodeId<G>>, T)) representing the longest path as a sequence of nodes and its total weight.
• Err(E) if there is an error computing the weight of any edge.

Example

use petgraph::graph::DiGraph;
use petgraph::Directed;
use rustworkx_core::dag_algo::longest_path;

let mut graph: DiGraph<(), i32> = DiGraph::new();
let n0 = graph.add_node(());
let n1 = graph.add_node(());
let n2 = graph.add_node(());
graph.add_edge(n0, n1, 1);
graph.add_edge(n0, n2, 3);
graph.add_edge(n1, n2, 1);

let weight_fn = |edge: petgraph::graph::EdgeReference<i32>| Ok::<i32, &str>(*edge.weight());
let result = longest_path(&graph, weight_fn).unwrap();
assert_eq!(result, Some((vec![n0, n2], 3)));