Opened 18 months ago
Closed 17 months ago
#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: |
Description (last modified by )
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
comment:2 Changed 18 months ago by
- Branch set to public/graphs/29958_sap
- Commit set to 07ce11646908920628c8b17719d0dd6406cc33b3
- Status changed from new to needs_review
comment:3 Changed 17 months ago by
- 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
Thanks.
comment:5 Changed 17 months ago by
- 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.
This is due to strongly connected components of order 2. In the example digraph, we have:
and in the code we have:
Unfortunately I don't remember why we added this...