CODEWITHSUNDEEP
rustpetgraph
curiousdannii
curiousdannii

Reputation: 2010

How do you perform a filtered search with Rust's petgraph?

Rust's Petgraph library has a bunch of filter 'adaptors', but I haven't been able to find any examples or tutorials for how to use them. Some (but not all) have constructors, such as EdgeFiltered.from_fn() which takes a graph and a function, but it's not clear how you'd then use it with the search methods like Dfs or astar as they don't have filter parameters.

So how do you use these filters? For example, if I had a graph with integer edge weights how would you:

  1. Perform a depth first search but excluding edges with a negative weight,
  2. Perform an astar search excluding edges with a negative weight?

Upvotes: 2

Views: 1083

Answers (1)

sebpuetz
sebpuetz

Reputation: 2618

The adapters implement GraphBase, you can just wrap your graph in them and pass the adapter struct to e.g. Dfs:

use petgraph::Graph;
use petgraph::visit::Dfs;
use petgraph::visit::EdgeFiltered;

fn main() {
    let mut graph = Graph::<(), i64>::new();
    let a = graph.add_node(());
    let b = graph.add_node(());
    let e = graph.add_edge(a, b, -1);
    let filtered = EdgeFiltered::from_fn(&graph, |edge_ref| *edge_ref.weight() > 0 );
    let dfs = Dfs::new(&filtered, a);
}

Playground Link

Upvotes: 3

Related Questions