-
Notifications
You must be signed in to change notification settings - Fork 61
Open
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.
Metadata
Metadata
Assignees
Labels
No labels