Description:

When running Ford Fulkerson on StableGraphs which have had edges deleted (or have gaps in the edge indices for some other reason), the Ford Fulkerson algorithm panics in some cases (or computes wrong results in others).

This is likely because Ford Fulkerson assumes edge indices in the range of 0 to m-1 where m is the number of edges in the graph. This is the case for Non-StableGraphs, but not for StableGraphs.

Example

The following example should work fine and compute a flow of 1 but panics instead:

main.rs:

use petgraph::algo::ford_fulkerson;
use petgraph::prelude::*;

fn main() {
    ford_fulkerson_gaps_in_edge_index_test();
}

fn ford_fulkerson_gaps_in_edge_index_test() {
    let mut g: StableGraph<(), u32, Directed> = StableDiGraph::new();

    let a = g.add_node(());
    let b = g.add_node(());
    let c = g.add_node(());
    let d = g.add_node(());

    let ac = g.add_edge(a, c, 1);
    let ab = g.add_edge(a, b, 1);
    let bc = g.add_edge(b, c, 1);
    let cd = g.add_edge(c, d, 1);
    
    // Current state of graph:
    // a --1-- b --1-- c --1-- d
    // |               |
    // - -- -- 1 -- -- -

    println!("Edges before removing bc: {:?}", g.edge_indices().collect::<Vec<_>>());
    // Output: Edges before removing bc: [EdgeIndex(0), EdgeIndex(1), EdgeIndex(2), EdgeIndex(3)]
    g.remove_edge(bc);
    println!("Edges after removing bc: {:?}", g.edge_indices().collect::<Vec<_>>());
    // Output: Edges after removing bc: [EdgeIndex(0), EdgeIndex(1), EdgeIndex(3)]

    // Current state of graph:
    // a --1-- b       c --1-- d
    // |               |       
    // - -- -- 1 -- -- -
    
    println!("Graph: {:?}", g);
    // Output: Graph: StableGraph { Ty: "Directed", node_count: 4, edge_count: 3, edges: (0, 2), (0, 1), (1, 3), edge weights: {0: 1, 1: 1, 3: 1}, free_node: NodeIndex(4294967295), free_edge: EdgeIndex(2) 
    
    let flow = ford_fulkerson(&g, a, d);
    // thread 'main' panicked at src/algo/ford_fulkerson.rs:75:72:
    // index out of bounds: the len is 3 but the index is 3
    println!("Flow: {:?}", flow);
}

The output of the respective print statements and the panic messages are noted in comments in the code above.

Environment to reproduce

The only dependency needed to reproduce is petgraph 0.8.1. This was tested both on nightly and default 1.87. The exact code in a repo to clone can also be found here.

Possible reason

At the start of the main ford_fulkerson function, an empty vec flows is created with a size of network.edge_count():

let mut flows = vec![N::EdgeWeight::zero(); network.edge_count()];

This vector is indexed in the following with edge_index which is itself retrieved via EdgeIndexable::to_index(&network, edge.id()); in line 75 of ford_fulkerson.rs which is part of the has_augmented_path method:

let edge_index: usize = EdgeIndexable::to_index(&network, edge.id());

This is not a problem if the edge indices are in the range of 0 to m-1 where m is the edge count, but in StableGraphs this is not guaranteed.

Possible fix

A fix could be to only restrict the algorithm to Non-StableGraphs. But I don't like this option, as the everything else from the algorithm (seems to) work fine with all types of graphs. Hence, another solution should be found.

An intuitive approach might be using a HashMap to map the edge indices from the original graph to the entries of the vector. However, since Petgraph wants to support no-std, this is not possible. Instead a alloc::collections::BTreeMap could be used, at a performance cost however. At last, of course, one could also use the HashMap from hashbrown, is this desirable?

Another approach might be using vector with possible 'empty slots'. That is, allocate a vector of size network.edge_bound() (edge_bound() is a method from the visit::EdgeIndexable trait) and then leave the empty entries unused. This should result in the same runtime/behaviour as currently for Non-StableGraphs and result in a possibly slightly higher memory usage for StableGraphs.

Since I don't see the downsides of using the hashbrown::HashMap, I would suggest this solution? I would be willing and able to implement any of the above (or possibly another), if desired.

Other

For one, this problem might also appear/be present with other algorithms, I have not checked that yet.

I found this bug while looking at pull request #606. At the start of the algorithm, the OP allocates a vector of node indices in the same manner, however using a HashMap and thus not complying with the no-std bound. Hence, I was wondering how other algorithms like Ford Fulkerson solve this problem, which is when I noticed that something seemed off.
Thus, this is also interesting for future reference.