2

我正在研究petgraph库的源代码，但我找不到该类型的Graph::NodeId来源。

我可以看到该函数astar接受一个类型G（可以是 a Graph）。astar期望NodeId在G的命名空间中有一个类型。

pub fn astar<G, F, H, K, IsGoal>(
    graph: G, 
    start: G::NodeId, 
    is_goal: IsGoal, 
    edge_cost: F, 
    estimate_cost: H
) -> Option<(K, Vec<G::NodeId>)> where
    G: IntoEdges + Visitable,
    IsGoal: FnMut(G::NodeId) -> bool,
    G::NodeId: Eq + Hash,
    F: FnMut(G::EdgeRef) -> K,
    H: FnMut(G::NodeId) -> K,
    K: Measure + Copy,

我可以看到它Graph被定义为

pub struct Graph<N, E, Ty = Directed, Ix = DefaultIx> {
    nodes: Vec<Node<N, Ix>>,
    edges: Vec<Edge<E, Ix>>,
    ty: PhantomData<Ty>,
}

但是，我不知道该类型NodeId来自何处。我在源代码中看到它定义的唯一地方是特征实现EdgeRef for EdgeReference

impl<'a, Ix, E> EdgeRef for EdgeReference<'a, E, Ix>
    where Ix: IndexType,
{
    type NodeId = NodeIndex<Ix>;
    type EdgeId = EdgeIndex<Ix>;
    type Weight = E;

    fn source(&self) -> Self::NodeId { self.node[0] }
    fn target(&self) -> Self::NodeId { self.node[1] }
    fn weight(&self) -> &E { self.weight }
    fn id(&self) -> Self::EdgeId { self.index }
}

但我不明白该类型如何进入Graph.

4

1 回答 1

3

astar有一个界限G: IntoEdges + Visitable，其中Visitable定义为

pub trait Visitable: GraphBase { … }

并GraphBase定义为

pub trait GraphBase {
    type EdgeId: Copy + PartialEq;
    type NodeId: Copy + PartialEq;
}

这就是允许astar使用G::NodeId. 基本上你有这个：

struct Graph;

trait GraphBase {
    type Type;
}

trait Visitable: GraphBase {}

impl GraphBase for Graph {
    type Type = u8;
}

impl Visitable for Graph {}

fn foo<G: Visitable>(_: G, _: G::Type) {}

fn main() {
    foo(Graph, 42);
}

（永久链接到操场）

于 2019-12-01T19:51:19.887 回答