如何为计算k-最短路径的函数使用Yen算法和花瓣图声明泛型类型？

Question

我在Rust中使用维基百科实现了Yen的算法petgraph。

在main函数中，代码如下所示：

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);
        }

    }
}

现在，我想把这个算法放在我可以从代码中调用的函数中。我第一次尝试用这样的签名：

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
}

但是，当我尝试用以下方法调用该函数时：

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

编译器抱怨：type annotations needed cannot satisfy <_ as IntoEdgeReferences>::EdgeRef ==花瓣：：IntoEdgeReferences>：：EdgeRef==：：EdgeReference<‘_，u32>`

我已经尝试了几种选择，但都没有成功。你对如何解决这个问题有什么建议吗？

Answer 1

编写的yen_k_shortest_paths()函数签名的问题是泛型类型参数没有正确使用。例如，考虑yen_k_shortest_paths()：G上第一个声明的类型参数，该参数用于表示图形类型。像这样声明G意味着调用yen_k_shortest_paths()的代码可以选择图形类型G。但是graph参数是用具体类型声明的，Graph<String, u32, Undirected>-the调用方别无选择。这种矛盾是G的问题所在。类似的推理也适用于其他类型的参数，但F和K除外。有两种方法可以解决这类问题：

1. 将图形参数保持为Graph<String, u32, Undirected>，并删除G类型参数。
2. 将图参数更改为接受G。

方法1比较简单，但是您的功能并不是一般的。方法2可能需要在函数中添加额外的边界和一些代码更改，以便代码进行编译。

在这种情况下，最简单的方法根本不需要任何类型参数：

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>>)> {...}

下面是可以运行的完整代码：

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
}

作为可能的函数签名的另一个例子，这个签名在节点类型N和边缘代价函数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,
{...}

正如你所看到的，这些界限会变得非常复杂。理解它们需要读取编译器发出的错误消息，以及读取所涉及的类型/特征的文档。(虽然，在本例中，我认为应该推断复杂的绑定&'a Graph<N, u32, Undirected>: GraphBase<NodeId = NodeIndex<u32>> + IntoEdgeReferences<EdgeRef = EdgeReference<'a, u32>>，但目前并不是因为一个更复杂的bug/限制)。