#29958 closed defect (fixed)

Too many strong articulation points

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.2
Component: graph theory Keywords: articulation points, directed graph
Cc: Merged in:
Authors: David Coudert Reviewers: Jonathan Kliem
Report Upstream: N/A Work issues:
Branch: 07ce116 (Commits, GitHub, GitLab) Commit: 07ce11646908920628c8b17719d0dd6406cc33b3
Dependencies: Stopgaps:

Status badges

Description (last modified by gh-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.

Change History (5)

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:

07ce116trac #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.

comment:4 Changed 17 months ago by dcoudert

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.