[BUG] edge_connectivity returns wrong result on directed graphs

[Becheler]

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: sagemath/sage#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.

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.