I am trying to implement a random walk on a directed graph using the petgraph
crate.
So far, I have defined a RandomWalk
struct which implements the Walker
trait:
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()
}
}
However, I get the error:
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`
I don't really understand how the petgraph
API works, is GraphBase
not the correct type?
The solution is quiet clear, if you understand the compiler.
Rust does not assume anything about the type, unless you specify it, e.g. you can't add two types T
together, unless the implement the Add
trait. Then you can write T + T
.
Your problem is very similar.
You are trying to use the function neighbors_directed
which is not implemented for G
(which is bound to GraphBase
in your example). Instead you have to specify that G
also must implement the trait IntoNeighborsDirected
by adding that to your impl block.
impl<G> Walker<G> for RandomWalk<G> where G: GraphBase + IntoNeighborsDirected
This will tell the compiler, that G
has the method neighbors_directed
implemented and you can use it (playground)