# Too many strong articulation points

Reported by: Owned by: gh-kliem major sage-9.2 graph theory articulation points, directed graph David Coudert Jonathan Kliem N/A 07ce116 07ce11646908920628c8b17719d0dd6406cc33b3

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.

### comment:1 Changed 18 months ago by dcoudert

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...

### comment:2 Changed 18 months ago by dcoudert

• Authors set to David Coudert
• Branch set to public/graphs/29958_sap
• Commit set to 07ce11646908920628c8b17719d0dd6406cc33b3
• Status changed from new to needs_review

a possible fix.

New commits:

 ​07ce116 `trac #29958: fix`

### comment:3 Changed 17 months ago by gh-kliem

• Description modified (diff)
• Reviewers set to Jonathan Kliem
• Status changed from needs_review to positive_review

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.

Thanks.

### comment:5 Changed 17 months ago by vbraun

• Branch changed from public/graphs/29958_sap to 07ce11646908920628c8b17719d0dd6406cc33b3
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.