Skip to content

The behaviour of Bridges (and therefore StrongOrientation) does not match its documentation #862

@wilfwilson

Description

@wilfwilson

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);
fail

So either we want to change either the behaviour, or the documentation, of these functions.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions