使用 petgraph 随机游走

Question

我正在尝试使用 petgraph 板条箱在有向图上实现随机游走。

到目前为止，我已经定义了一个实现 Walker 特征的 RandomWalk 结构：

extern crate petgraph; // 0.4.13
use petgraph::visit::{GraphBase, Walker};
use petgraph::Direction;

pub struct RandomWalk<G> 
    where G: GraphBase
{
   next: G::NodeId, 
}

impl<G> Walker<G> for RandomWalk<G>
    where G: GraphBase
{
   type Item = G::NodeId; 

   fn walk_next(&mut self, graph: G) -> Option<Self::Item> {
       // Even this deterministic walk does not work:
       graph.neighbors_directed(self.next, Direction::Incoming).next()
   }
}

但是，我收到错误消息：

error[E0599]: no method named `neighbors_directed` found for type `G` in the current scope
  --> src/lib.rs:50:11
   |
50 |     graph.neighbors_directed(self.next, Direction::Incoming).next()
   |           ^^^^^^^^^^^^^^^^^^
   |
   = note: the method `neighbors_directed` exists but the following trait bounds were not satisfied:
           `&G : petgraph::visit::IntoNeighborsDirected`
   = help: items from traits can only be used if the trait is implemented and in scope
   = note: the following trait defines an item `neighbors_directed`, perhaps you need to implement it:
           candidate #1: `petgraph::visit::IntoNeighborsDirected`

我不太明白 petgraph API 是如何工作的，GraphBase 不是正确的类型吗？

Answer 1

如果你了解编译器，解决方案就很清楚了。
Rust 不会假设任何类型，除非你指定它，例如你不能将两种类型 T 加在一起，除非实现 Add 特性。然后你可以写T + T.
你的问题很相似。

您正在尝试使用未针对 G 实现的函数 neighbors_directed（在您的示例中绑定到 GraphBase）。相反，您必须指定 G 还必须通过将特征添加到您的 impl 块来实现特征 IntoNeighborsDirected。

impl<G> Walker<G> for RandomWalk<G> where G: GraphBase + IntoNeighborsDirected

这将告诉编译器，G 实现了方法 neighbors_directed，您可以使用它 (playground)

使用 petgraph 随机游走

Random walk using petgraph

graph-algorithm

rust

petgraph