How to declare generic types for a function that computes k-shortest-paths using Yen's algorithm and petgraph?

Question

I have implemented Yen's algorithm Wikipedia using petgraph in Rust.

In a main function, the code looks like this:

use std::collections::BinaryHeap;
use std::cmp::Reverse;
use std::collections::HashSet;

use petgraph::{Graph, Undirected};
use petgraph::graph::NodeIndex;
use petgraph::stable_graph::StableUnGraph;
use petgraph::algo::{astar};
use petgraph::visit::NodeRef;

fn main() {
    let mut graph: Graph<String, u32, Undirected> = Graph::new_undirected();
    let c = graph.add_node(String::from("C"));
    let d = graph.add_node(String::from("D"));
    let e = graph.add_node(String::from("E"));
    let f = graph.add_node(String::from("F"));
    let g = graph.add_node(String::from("G"));
    let h = graph.add_node(String::from("H"));
    graph.add_edge(c, d, 3);
    graph.add_edge(c, e, 2);
    graph.add_edge(d, e, 1);
    graph.add_edge(d, f, 4);
    graph.add_edge(e, f, 2);
    graph.add_edge(e, g, 3);
    graph.add_edge(f, g, 2);
    graph.add_edge(f, h, 1);
    graph.add_edge(g, h, 2);

    let start = c;
    let goal = h;

    // start solving Yen's k-shortest-paths
    let (length, path) = match astar(&graph, start, |n| n == goal.unwrap(), |e| *e.weight(), |_| 0) {
        Some(x) => x,
        None => panic!("Testing!"),
    };

    println!("Initial path found\tlength: {}", length);
    for i in 0..(path.len() - 1) {
        println!("\t{:?}({:?}) -> {:?}({:?})", graph.node_weight(path[i].id()).unwrap(), path[i].id(), graph.node_weight(path[i+1].id()).unwrap(), path[i+1].id());
    }
        
    let k = 10;
    let mut ki = 0;
    let mut visited = HashSet::new();

    let mut routes = vec![(length, path)];

    let mut k_routes = BinaryHeap::new();

    for ki in 0..(k - 1) {

        println!("Computing path {}", ki);

        if routes.len() <= ki {
            // We have no more routes to explore
            break;
        }

        let previous = routes[ki].1.clone();

        for i in 0..(previous.len() - 1) {

            let spur_node = previous[i].clone();
            let root_path = &previous[0..i];

            let mut graph_copy = StableUnGraph::<String, u32>::from(graph.clone());

            println!("\tComputing pass {}\tspur: {:?}\troot: {:?}", i, graph.node_weight(spur_node), root_path.iter().map(|n| graph.node_weight(*n).unwrap()));

            for (_, path) in &routes {
                if path.len() > i + 1 && &path[0..i] == root_path {
                    let ei = graph.find_edge_undirected(path[i], path[i + 1]);

                    if ei.is_some() {
                        let edge = ei.unwrap().0;
                        graph_copy.remove_edge(edge);
                        let edge_obj = graph.edge_endpoints(edge);
                        let ns = edge_obj.unwrap();
                        println!("\t\tRemoving edge {:?} from {:?} -> {:?}", edge, graph.node_weight(ns.0).unwrap(), graph.node_weight(ns.1).unwrap());
                    }
                    else {
                        panic!("\t\tProblem finding edge");
                    }
                }
            }

            if let Some((_, spur_path)) =
                astar(&graph_copy, spur_node, |n| n == goal.unwrap(), |e| *e.weight(), |_| 0)
            {
                let nodes: Vec<NodeIndex> = root_path.iter().cloned().chain(spur_path).collect();
                let mut node_names = vec![];
                for ni in 0..nodes.len() {
                    node_names.push(graph.node_weight(nodes[ni]).unwrap());
                }

                // compute root_path length
                let mut path_length = 0;
                for i_rp in 0..(nodes.len() - 1) {
                    let ei = graph.find_edge_undirected(nodes[i_rp], nodes[i_rp + 1]);
                    if ei.is_some() {
                        let ew = graph.edge_weight(ei.unwrap().0);
                        if ew.is_some() {
                            path_length += ew.unwrap();
                        }
                    }
                }

                println!("\t\t\tfound path: {:?} with cost {}", node_names, path_length);
                if !visited.contains(&nodes) {
                    // Mark as visited
                    visited.insert(nodes.clone());
                    // Build a min-heap
                    k_routes.push(Reverse((path_length, nodes)));
                }
            }
            
        }
        if let Some(k_route) = k_routes.pop() {
            println!("\tselected route {:?}", k_route.0);
            routes.push(k_route.0);
        }

    }
}

Now, I want to put this algorithm within a function that I can call from my code. I made an initial attempt with the signature like this:

pub fn yen_k_shortest_paths<G, E, Ty, Ix, F, K>(
    graph: Graph<String, u32, Undirected>,
    start: NodeIndex<u32>,
    goal: NodeIndex<u32>,
    mut edge_cost: F,
    k: usize,
) -> Result<Vec<(u32, Vec<NodeIndex<u32>>)>, Box<dyn std::error::Error>>
where
    G: IntoEdges + Visitable,
    Ty: EdgeType,
    Ix: IndexType,
    E: Default + Debug + std::ops::Add,
    F: FnMut(G::EdgeRef) -> K,
    K: Measure + Copy,
{
    // implementation here
}

However, when I try to call the function with:

let paths = yen::yen_k_shortest_paths(graph, start, goal, |e: EdgeReference<u32>| *e.weight(), 5);

the compiler complains: type annotations needed cannot satisfy <_ as IntoEdgeReferences>::EdgeRef == petgraph::graph::EdgeReference<'_, u32>`

I already tried several alternatives without success. Do you have any suggestion on how to fix this issue?

Answer 1

The issue with the yen_k_shortest_paths() function signature as written is the generic type parameters aren't used correctly. As an example, consider the first declared type parameter on yen_k_shortest_paths(): G, which is intended to represent the graph type. Declaring G like this means that the code that calls yen_k_shortest_paths() gets to pick the graph type G. But the graph argument is declared with the concrete type Graph<String, u32, Undirected>—the caller has no choice. This contradiction is the problem with G. Similar reasoning applies to the other type parameters, except F and K. There are two ways to fix this kind of issue:

1. Keep the graph argument as Graph<String, u32, Undirected> and remove the G type parameter.
2. Change the graph argument to take a G.

Approach #1 is simpler but your function won't be as general. Approach #2 can involve needing to add extra bounds and some code changes in the function in order for the code to compile.

In this case, the simplest approach doesn't need any type parameters at all:

fn yen_k_shortest_paths(
    graph: &Graph<String, u32, Undirected>,
    start: NodeIndex<u32>,
    goal: NodeIndex<u32>,
    edge_cost: fn(EdgeReference<u32>) -> u32,
    k: usize,
) -> Vec<(u32, Vec<NodeIndex<u32>>)> {...}

Here's the full code, which can be run:

use std::cmp::Reverse;
use std::collections::BinaryHeap;
use std::collections::HashSet;

use petgraph::algo::astar;
use petgraph::graph::{EdgeReference, NodeIndex};
use petgraph::stable_graph::StableUnGraph;
use petgraph::visit::NodeRef;
use petgraph::{Graph, Undirected};

fn main() {
    let mut graph: Graph<String, u32, Undirected> = Graph::new_undirected();
    let c = graph.add_node(String::from("C"));
    let d = graph.add_node(String::from("D"));
    let e = graph.add_node(String::from("E"));
    let f = graph.add_node(String::from("F"));
    let g = graph.add_node(String::from("G"));
    let h = graph.add_node(String::from("H"));
    graph.add_edge(c, d, 3);
    graph.add_edge(c, e, 2);
    graph.add_edge(d, e, 1);
    graph.add_edge(d, f, 4);
    graph.add_edge(e, f, 2);
    graph.add_edge(e, g, 3);
    graph.add_edge(f, g, 2);
    graph.add_edge(f, h, 1);
    graph.add_edge(g, h, 2);

    let start = c;
    let goal = h;
    let edge_cost = |e: EdgeReference<u32>| *e.weight();
    let k = 10;

    let _paths = yen_k_shortest_paths(&graph, start, goal, edge_cost, k);
}

fn yen_k_shortest_paths(
    graph: &Graph<String, u32, Undirected>,
    start: NodeIndex<u32>,
    goal: NodeIndex<u32>,
    edge_cost: fn(EdgeReference<u32>) -> u32,
    k: usize,
) -> Vec<(u32, Vec<NodeIndex<u32>>)> {
    let (length, path) = match astar(graph, start, |n| n == goal, edge_cost, |_| 0) {
        Some(x) => x,
        None => panic!("Testing!"),
    };

    println!("Initial path found\tlength: {}", length);
    for i in 0..(path.len() - 1) {
        println!(
            "\t{:?}({:?}) -> {:?}({:?})",
            graph.node_weight(path[i].id()).unwrap(),
            path[i].id(),
            graph.node_weight(path[i + 1].id()).unwrap(),
            path[i + 1].id()
        );
    }

    let mut visited = HashSet::new();

    let mut routes = vec![(length, path)];

    let mut k_routes = BinaryHeap::new();

    for ki in 0..(k - 1) {
        println!("Computing path {}", ki);

        if routes.len() <= ki {
            // We have no more routes to explore
            break;
        }

        let previous = routes[ki].1.clone();

        for i in 0..(previous.len() - 1) {
            let spur_node = previous[i];
            let root_path = &previous[0..i];

            let mut graph_copy = StableUnGraph::from(graph.clone());

            println!(
                "\tComputing pass {}\tspur: {:?}\troot: {:?}",
                i,
                graph.node_weight(spur_node),
                root_path
                    .iter()
                    .map(|n| graph.node_weight(*n).unwrap())
                    .collect::<Vec<_>>()
            );

            for (_, path) in &routes {
                if path.len() > i + 1 && &path[0..i] == root_path {
                    let ei = graph.find_edge_undirected(path[i], path[i + 1]);

                    if let Some(ei) = ei {
                        let edge = ei.0;
                        graph_copy.remove_edge(edge);
                        let edge_obj = graph.edge_endpoints(edge);
                        let ns = edge_obj.unwrap();
                        println!(
                            "\t\tRemoving edge {:?} from {:?} -> {:?}",
                            edge,
                            graph.node_weight(ns.0).unwrap(),
                            graph.node_weight(ns.1).unwrap()
                        );
                    } else {
                        panic!("\t\tProblem finding edge");
                    }
                }
            }

            if let Some((_, spur_path)) = astar(
                &graph_copy,
                spur_node,
                |n| n == goal,
                |e| *e.weight(),
                |_| 0,
            ) {
                let nodes: Vec<NodeIndex> = root_path.iter().cloned().chain(spur_path).collect();
                let mut node_names = vec![];
                for &node in &nodes {
                    node_names.push(graph.node_weight(node).unwrap());
                }

                // compute root_path length
                let mut path_length = 0;
                for i_rp in 0..(nodes.len() - 1) {
                    let ei = graph.find_edge_undirected(nodes[i_rp], nodes[i_rp + 1]);
                    if let Some(ei) = ei {
                        let ew = graph.edge_weight(ei.0);
                        if let Some(&ew) = ew {
                            path_length += ew;
                        }
                    }
                }

                println!(
                    "\t\t\tfound path: {:?} with cost {}",
                    node_names, path_length
                );
                if !visited.contains(&nodes) {
                    // Mark as visited
                    visited.insert(nodes.clone());
                    // Build a min-heap
                    k_routes.push(Reverse((path_length, nodes)));
                }
            }
        }
        if let Some(k_route) = k_routes.pop() {
            println!("\tselected route {:?}", k_route.0);
            routes.push(k_route.0);
        }
    }

    routes
}

As another example of a possible function signature, this one is generic over the node type N and the edge cost function F:

fn yen_k_shortest_paths<'a, N, F>(
    graph: &'a Graph<N, u32, Undirected>,
    start: NodeIndex<u32>,
    goal: NodeIndex<u32>,
    edge_cost: F,
    k: usize,
) -> Vec<(u32, Vec<NodeIndex<u32>>)>
where
    &'a Graph<N, u32, Undirected>:
        GraphBase<NodeId = NodeIndex<u32>> + IntoEdgeReferences<EdgeRef = EdgeReference<'a, u32>>,
    N: Debug + Clone,
    F: FnMut(EdgeReference<u32>) -> u32,
{...}

As you can see, these bounds can get pretty complicated. Figuring them out involved reading the error messages the compiler emitted, as well as reading the docs for the involved types/traits. (Although, I think in this case the complicated bound &'a Graph<N, u32, Undirected>: GraphBase<NodeId = NodeIndex<u32>> + IntoEdgeReferences<EdgeRef = EdgeReference<'a, u32>> should be inferred, but currently isn't due to a complier bug/limitation)