Случайная прогулка по петграфу - PullRequest
Новая
       26

Случайная прогулка по петграфу

0 голосов
/ 18 октября 2018

Я пытаюсь реализовать случайный обход ориентированного графа с использованием ящика petgraph.

До сих пор я определил структуру RandomWalk, которая реализует черту Walker: 

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 не правильный тип?

1 Ответ

0 голосов
/ 18 октября 2018

Решение достаточно простое, если вы понимаете компилятор.
Rust не предполагает ничего о типе, если вы не укажете его, например, вы не можете добавить два типа T вместе, если только реализация Add черта.Затем вы можете написать T + T.
Ваша проблема очень похожа.

Вы пытаетесь использовать функцию neighbors_directed, которая не реализована для G (которая связана с GraphBase втвой пример).Вместо этого вы должны указать, что G также должен реализовывать черту IntoNeighborsDirected, добавив это в ваш блок impl. 

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

Это сообщит компилятору, что Gреализован метод neighbors_directed, и вы можете использовать его ( детская площадка )

...