Digraphs Add `VertexConnectivity`

Edit: ( @reiniscirpons ): the current implementation seems have some bug and it fails on DigraphFromGraph6String("HoStIv{") (this is Graph 33668 on house of graphs). The expected output is 4, currently the method gives 3. My hunch is that the bug may be in the Edmonds-Karp method. It seems PR #584 implements a max-flow method, so once this is merged, we may be able to fix this PR as well.

Hopefully within the next 7 years we will be able to merge this PR!

Original comment: This pull request adds an attribute called VertexConnectivity which for a graph G = (V, E) computes the least cardinality |S| of a subset S of V, such that G - S is either disconnected, is trivial, or has no vertices. Documentation and tests are included.

Nov 01 '17 14:11 ffloresbrito

@james-d-mitchell Did @ffloresbrito address your changes? Is @ffloresbrito still involved in any GAP-related activity?

Feb 01 '19 09:02 wilfwilson

@james-d-mitchell I have squashed and rebased this PR on the latest master branch, and fixed the CI errors, and pushed. Assuming that @ffloresbrito is no longer involved with this, we can now decide how to proceed with this PR (or whether just to just close it).

On the whole, I'd say it's better to have a slow implementation than no implementation - it could always be a student project to improve or rewrite it. But that assumes that this implementation is correct, and it's been long enough that I don't remember if it is. So I'll review it again sometime.

Mar 03 '21 16:03 wilfwilson

Stale pull request message

Jan 07 '22 01:01 github-actions[bot]