How to do reverse shortest paths on AdjMatrix?

[Pr0methean]

On an AdjMatrix<_,_,Directed,DefaultId>, what's the best way to find the shortest paths from all vertices to a destination vertex? petgraph has a Reverse wrapper, but unlike gryf it's not flexible enough (the vertex-attribute type has to implement Copy, which mine doesn't).

[pnevyk]

There is an adapter gryf::adapt::Transpose which should be more or less equivalent to petgraph's Reversed adapter. It can be used like this:

let reversed = gryf::adapt::Transpose::new(graph);

// Work with reversed as a standard graph.

It's currently hidden in the documentation, because I am not certain about some details of how adapters should work and what API they should have. But it's used internally here. Maybe I should expose the existing adapters and hide only the API where I am not sure.

[Pr0methean]

Or you could always put it behind an "experimental-api" feature flag.

[pnevyk]

Or you could always put it behind an "experimental-api" feature flag.

Yeah. Although the library readme states that "This library is experimental", so in a way all API is sort of experimental now.

Let me know if the Transpose adapter resolved your problem so we can close the issue or continue finding ways to solve it.

[Pr0methean]

So far, so good.

Also, it would be nice if there were an easier way to remove the vertex.attr borrows from ShortestPaths output, so I can go back to mutating the graph while using the outputs; the way I'm currently doing it is

            let reverse_graph = Transpose::new(&divisibility_graph);
            let reverse_shortest_paths = ShortestPaths::on(&reverse_graph)
                        .edge_weight_fn(|edge| if *edge == NotFactor { 1usize } else { 0usize })
                        .run(factor_vid)
                        .unwrap();
            let divisors_of_factor: BTreeSet<_> = divisibility_graph.vertices_by_id()
                .filter(|v| reverse_shortest_paths.dist(v) == Some(&0))
                .collect();

[pnevyk]

it would be nice if there were an easier way to remove the vertex.attr borrows from ShortestPaths output, so I can go back to mutating the graph while using the outputs

Ah, that's a UX issue that I wouldn't think of, because it happens only when using adapters. I created #107 to address that, but not sure when I get to it.

In your particular case, you might do this:

// Move the graph to the adapter so there is no borrow
let reverse_graph = Transpose::new(divisibility_graph);
let reverse_shortest_paths = ShortestPaths::on(&reverse_graph)
    .edge_weight_fn(|edge| if *edge { 1usize } else { 0usize })
    .run(v0)
    .unwrap();
// Get back the original graph
let mut divisibility_graph = reverse_graph.into_inner();
divisibility_graph.add_vertex(...);
let divisors_of_factor: BTreeSet<_> = graph
    .vertices_by_id()
    .filter(|v| reverse_shortest_paths.dist(v) == Some(&0))
    .collect();

unless something else prevents you from doing that. But this is definitely a workaround, not a solution.