`edge_connectivity()` returns wrong result on directed graphs

Start with the boost::edge_connectivity entry point and the flow-graph construction shown in the issue, then run the Compiler Explorer reproducer for directed and bidirectional graphs. Check the existing test tree, which currently appears to lack coverage for this algorithm. Done requires an agreed scope for rejecting directed graphs or supporting them, plus tests that lock in the selected behavior.

User bug description

It has been brought to my attention by David Coudert (maintainer of Sage Math graph that uses Boost Graph) that one ticket got lost long ago when migrating from SVN: https://github.com/sagemath/sage/issues/18753

Basically the edge_connectivity experience is broken for their users:

sage: g = digraphs.Path(3)
sage: g.edge_connectivity(implementation="sage")
0.0
sage: g.edge_connectivity(implementation="boost")  # wrong answer
1
sage: g.add_edge(1, 0)
sage: g.edge_connectivity(implementation="sage")
0.0
sage: g.edge_connectivity(implementation="boost")
0

Implementation

Looking quickly into the implementation, the implementation does not filter out directed graph, treating all as undirected, and unconditionally add reverse edges when consturcting the flow graph. There is reasonable ground to believe it was not clear for the author if the reverse edge should have capacity 0 or 1:

    for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
    {
        u = source(*ei, g), v = target(*ei, g);
        boost::tie(e1, inserted) = add_edge(u, v, flow_g);
        cap[e1] = 1;
        boost::tie(e2, inserted) = add_edge(v, u, flow_g);
        cap[e2] = 1; // not sure about this
        rev_edge[e1] = e2;
        rev_edge[e2] = e1;
    }

The bug seems to be present since early day ~2001 by Jeremy Siek. The file comes with a warning // WARNING: not-yet fully tested! , and unless I'm mistaken there is indeed no test for this algorithm.

Reproducer

See on Compiler Explorer

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/edge_connectivity.hpp>
#include <iostream>
#include <vector>

int main() {
    using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS>;
    G g(3);
    boost::add_edge(0, 1, g);
    boost::add_edge(1, 2, g);

    using E = boost::graph_traits<G>::edge_descriptor;
    std::vector<E> cut;
    auto k = boost::edge_connectivity(g, std::back_inserter(cut));

    std::cout << "0 -> 1 -> 2\n";
    std::cout << "expected: 0\n";
    std::cout << "boost:    " << k << "\n";

    boost::add_edge(1, 0, g);
    cut.clear();
    k = boost::edge_connectivity(g, std::back_inserter(cut));
    std::cout << "\nafter adding 1 -> 0:\n";
    std::cout << "expected: 0\n";
    std::cout << "boost:    " << k << "\n";
}

Program returned: 0
Program stdout
0 -> 1 -> 2
expected: 0
boost:    1

after adding 1 -> 0:
expected: 0
boost:    0

Proposed changes

1. Add a concept restriction to forbid directed graphs
2. Add extensive tests to lock-in functional behavior
3. Think about supporting directed graphs: I am unsure how to do this, and this could require an algorithmic modification.