As announced in 32169#comment:40, thanks to the help of Loukas Georgiadis [1] for providing an experimental C code, we implement in Cython the algorithm proposed by Gabow [2] for computing the edge connectivity of directed graphs.

[1] Loukas Georgiadis, Dionysios Kefallinos, Luigi Laura, Nikos Parotsidis: An Experimental Study of Algorithms for Computing the Edge Connectivity of a Directed Graph. SIAM Symposium on Algorithm Engineering and Experiments (ALENEX), pp 85-97, 2021.

[2] Harold N. Gabow: A Matroid Approach to Finding Edge Connectivity and Packing Arborescences. Journal of Computer and System Sciences, 50(2):259-273 (1995)

CC: @kliem @DaveWitteMorris @tscrim @enjeck

Component: graph theory

Author: David Coudert

Branch/Commit: 5dcb653

Reviewer: Jonathan Kliem, Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/33839