Too many strong articulation points

[kliem]

This is a doctest from src/sage/graphs/connectivity.pyx with a different random seed:

sage: set_random_seed(151058820726654196682836430928254760259)
sage: from sage.graphs.connectivity import strong_articulation_points
sage: def sap_naive(G):
....:     nscc = len(G.strongly_connected_components())
....:     S = []
....:     for u in G:
....:         H = copy(G)
....:         H.delete_vertex(u)
....:         if len(H.strongly_connected_components()) > nscc:
....:             S.append(u)
....:     return S
....: 
sage: D = digraphs.RandomDirectedGNP(20, 0.1)
sage: X = sap_naive(D)
sage: SAP = strong_articulation_points(D)
sage: set(X) == set(SAP)
False

An indeed the vertex 10 is in SAP, but it appears not to be a strong articulation point:

sage: SAP
[17, 4, 1, 18, 2, 7, 10]
sage: len(D.strongly_connected_components())
13
sage: D.delete_vertex(10)
sage: len(D.strongly_connected_components())
13

Before this ticket, all vertices in strongly connected components of size 2 where returned as strong articulation points. But a graph with 2 vertices always has zero articulation points.

Component: graph theory

Keywords: articulation points, directed graph

Author: David Coudert

Branch/Commit: 07ce116

Reviewer: Jonathan Kliem

Issue created by migration from https://trac.sagemath.org/ticket/29958

[dcoudert]

comment:1

This is due to strongly connected components of order 2. In the example digraph, we have:

sage: D.dig6_string()
'SA?GA??_??a???@?@OH_?@?I??b??G?AgGGCO??AC????a?????A@????AOCOQ?d??I?'
sage: D.strongly_connected_components()
[[14],
 [12],
 [3],
 [0, 4, 11, 15, 17],
 [16],
 [1, 2, 18],
 [7, 10],
 [8],
 [5],
 [6],
 [9],
 [13],
 [19]]

and in the code we have:

        if n == 2:
            SAP.extend(g.vertex_iterator())
            continue

Unfortunately I don't remember why we added this...

[dcoudert]

Commit: 07ce116

[dcoudert]

comment:2

a possible fix.

---

New commits:

07ce116

trac #29958: fix

[dcoudert]

Branch: public/graphs/29958_sap

[dcoudert]

Author: David Coudert

[kliem]

comment:3

LGTM.

I didn't look into the algorithm. But I can certainly confirm that a graph with 2 vertices does not have strong articulation points.

[kliem]

Reviewer: Jonathan Kliem

[dcoudert]

comment:4

Thanks.

[vbraun]

Changed branch from public/graphs/29958_sap to 07ce116