Too many strong articulation points
Closed this issue · 10 comments
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
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...
Branch: public/graphs/29958_sap
Author: David Coudert
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.
Reviewer: Jonathan Kliem
Description changed:
---
+++
@@ -31,3 +31,5 @@
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.Thanks.
Changed branch from public/graphs/29958_sap to 07ce116