Repository navigation
edge_connectivity() returns wrong result on directed graphs #454
Description
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.
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
- Add a concept restriction to forbid directed graphs
- Add extensive tests to lock-in functional behavior
- Think about supporting directed graphs: I am unsure how to do this, and this could require an algorithmic modification.
Activity
jeremy-murphy commentedon Feb 8, 2026
Interesting. Could you please add some hyperlinks to the relevant sections of the library? Thanks.
Becheler commentedon Feb 9, 2026
It is here:
graph/include/boost/graph/edge_connectivity.hpp
Lines 105 to 125 in 3131c24
jeremy-murphy commentedon Feb 10, 2026
Am I right that this algorithm is undocumented?
jeremy-murphy commentedon Feb 10, 2026
If Sage have their own implementation of edge connectivity for directed graphs, can we not use it to figure out what ours should do?
Or at least get a reference to the literature that defines this algorithm?
jeremy-murphy commentedon Feb 10, 2026
Harold N. Gabow. A Matroid Approach to Finding Edge Connectivity and Packing Arborescences. Journal of Computer and System Sciences, 50(2):259-273, 1995. doi:10.1006/jcss.1995.1022
Becheler commentedon Feb 10, 2026
In SageMath implemenetations:
[-][BUG] edge_connectivity returns wrong result on directed graphs[/-][+]`edge_connectivity()` returns wrong result on directed graphs[/+]dcoudert commentedon Aug 8, 2026
Clearly, the algorithm in$n-1$ flow problems, but I'm not sure why.
graph/include/boost/graph/edge_connectivity.hppis for undirected graphs only.It solves a max flow problem from a fixed vertex
pto each vertexkand returns the minimum value.pis chosen as a vertex with min degree as the edge connectivity is at most the minimum degree. The algorithm also uses a method to select the next vertexkto consider. It seems that this method enables to solve less thanFor directed graphs, a simple algorithm is to select a vertex$2(n-1)$ flow problems.
pwith minimum in or out degree, and then to solve a max flow problem frompto each vertexkand fromktop. The edge connectivity is then the minimum over all theseIt should not be difficult to implement without all the tricks of the current code.
Gabow's algorithm is faster but way harder to implement. You can have a look at the code in Sagemath https://github.com/sagemath/sage/blob/develop/src/sage/graphs/edge_connectivity.pyx. It is for directed graphs and now supports directed graphs with multiple edges (sagemath/sage#42570).
FYI: the code in Sagemath is for both
edge_connectivityandedge_disjoint_spanning_trees(sagemath/sage#42257).We have other methods for undirected graphs.