Repository navigation
The behaviour of Bridges (and therefore StrongOrientation) does not match its documentation #862
Description
As reported by @saffronmciver in #737 (comment), there is a problem with Bridges.
The manual says:
‣ Bridges( D ) ─────────────────────────────────────────────────────────────────────────── attribute
Returns: A (possibly empty) list of edges.
A connected digraph is 2-edge-connected if it is still connected (in the sense of IsConnectedDigraph
(6.6-3)) when any edge is removed. If the digraph D is not 2-edge-connected but is connected, then
any edge [u, v] of D whose removal makes the resulting digraph disconnected is called a bridge.
Bridges returns a list of the bridges of D, if any, and, in particular, returns the empty list if D
is not connected.
But Digraphs behaves in the following way in this example:
gap> d := Digraph([[2], [1]]);
<immutable digraph with 2 vertices, 2 edges>
gap> Bridges(d);
[ [ 1, 2 ] ]According to the documentation, this is not a bridge since removing the edge [1, 2] still leaves the edge [2, 1] connecting the two vertices of the digraph!
As @saffronmciver points out, this also means that StrongOrientation is broken, since according to its manual entry, this same digraph d should admit a strong orientation, but it returns fail:
gap> StrongOrientation(d);
failSo either we want to change either the behaviour, or the documentation, of these functions.
Activity
saffronmciver commentedon Oct 1, 2025
After talking to @reiniscirpons, I think the intention was that when
[1, 2]is returned, this is interpreted as both[1, 2]and[2, 1]being removed. I guess the assumption is that each edge[u, v]is considered to be[v, u]and[u, v]since the graph is forced to be symmetric.But the documentation doesn't really reflect this since it is implying that a returned edge alone being removed causes the graph to be disconnected.
One option would be having both edges in the return list but that doesn't really make sense since the idea is that the combination of those edges is the bridge, and the symmetric edge created might not have been in the original graph.
wilfwilson commentedon Oct 1, 2025
Sounds like the documentation probably just needs to be corrected and clarified, then.