digraphs
BiconnectedComponents
I should look into this properly, but just to get something down:
As far as I recall, we can check whether a graph is Biconnected and even k-connected (strongly? weakly?) but we can't necessarily get its biconnected or k-connected components. Is this something we can do, either quickly by a call to an existing function, or with significant new code?
I thought of this because of this.
Pretty sure there's a BiconnectedComponents function, but that might be for bipartite graphs. You can also get ArticulationPoints which if removed from the graph will give you back the thing you're after!
I think it is important to distinguish between which notion of biconnectedness we are talking about, namely whether its vertex-biconnectedness or edge-biconnectedness:
- a digraph is vertex-biconnected if it is connected and remains so after removing any one vertex;
- a digraph is edge-biconnected if it is connected and remains connected after removing any one edge.
In digraphs the IsBiconnectedDigraph function checks if a digraph is vertex-biconnected. To check edge-biconnectedness we have a function IsBridgelessDigraph instead. Note that the linked article is mainly talking about edge-biconnectedness. For more general k-vertex-connectivity we have the old PR #94 which me and Wilf are in the process of necromancing. For edge-connectivity we do not have a function but it should be not too hard to implement via the new max flows functionality (thanks to Rayian and Michael).
With each notion of biconnectedness we have associated a different notion of biconnected component as well:
- a vertex-biconnected component is a maximal set of vertices whose induced subdigraph is vertex-biconnected;
- an edge-biconnected component is a maximal set of vertices whose induced subdigraph is edge-biconnected.
Both of these notions are made in analogy to connected components. There is no BiconnectedComponents function in the digraphs package.
For finding edge-biconnected components in a connected digraph D the following should work:
gap> DigraphConnectedComponents(DigraphRemoveEdges(DigraphImmutableCopyIfMutable(D), Bridges(D)));
A bridge is an edge in a connected digraph whose removal makes a digraph disconnected, the Bridges function computes all bridges. I think we can show that removing all bridges does not create any new ones, hence each connected component of the resulting graph has no bridges and is therefore edge-biconnected. To make it work with disconnected digraphs D we just compute and remove all bridges of each connected component of D. I think computing the bridges is essentially the same dfs-based procedure as getBridges implemented in the linked article, but slightly expanded to also get the articulation points and additional info, see https://github.com/digraphs/Digraphs/blob/1231e19e60f59bdd871980af480daf2fae7a690d/gap/attr.gi#L29
If one wanted to, we could avoid having to explicitly remove the bridges (and therefore allocate memory) if we e.g. modified the existing connected components function to take in an array of "forbidden edges" and then run the dfs as if these edges were missing, but that would require us to modify a C-function and pass more data between C and gap which may not be better overall.
Now, for vertex-biconnected components things are a bit more complicated, namely, as the linked article points out, vertex-biconnected components don't partition the vertices, see the example graph from section Bonus 2 of the linked article:
D := Digraph([[4, 5], [6, 7], [], [2], [2], [3], [3]]);
There are two vertex-biconnected components: the one induced by vertices {1, 2, 4, 5} and the one induced by {2, 3, 6, 7}, but both components contain 2.
The analogue of a bridge for vertex-biconnectedness, that is, a vertex whose removal disconnects a connected graph, is called an articulation point. In the graph D the vertex 2 is the only articulation point. Doing what James suggests - removing all articulation points and taking the connected components would therefore only get you part of the way there, yielding the sets {1, 4, 5} and {3, 6, 7} which both notably do not induce vertex-biconnected digraphs.
I think its the case that any point included in a vertex-biconnected component is neccesarily an articulation point, so we could probably make James suggestion into a method for finding vertex-biconnected components by figuring out how to re-attach the articulation points, but this could get a bit tricky. E.g. adding all articulation points that an incomplete component has an edge going in/out of. But definitely needs some sort of proof to make sure there aren't some edge cases that don't work like this. Maybe a task for a VIP student looking for a more math-focused task?
Additionally, this was all assuming we wanted weak-biconnected components (i.e. assuming each edge can be traversed both ways), there are of course strong analogues to all of these notions (where we are only allowed to go the way an edge is pointing) as Michael points out. I believe we do not have anything implemented for this at all, though I'm not sure of the utility either.
And finding the k-connected components for general k seems like quite a difficult task too. As a minimum for this we probably would need to implement a function for finding the minimum cut, the minimum set of edges needed to disconnect the graph. It seems like Rayian implemented some of this in #584 (the MinimumCuts function), but its commented out for some reason. It might also be possible to get this info from the maximum flow function (there is a correspondence between the size of the minimum cut and the maximum flow, but I'm not sure if it tells us how to effectively find the cut from the flow). But even then its not entirely clear how to translate that into components.
