#6807: bug in blocks_and_cut_vertices() of a graph where a cut vertex can be
listed more than once
--------------------------+-------------------------------------------------
Reporter: hartke | Owner: rlm
Type: defect | Status: new
Priority: major | Milestone:
Component: graph theory | Keywords:
Reviewer: | Author: Stephen Hartke
Merged: |
--------------------------+-------------------------------------------------
There is another bug in blocks_and_cut_vertices() where cut vertices can
appear more than once in the returned list of cut vertices. Jason Grout
pointed out this problem in ticket
[http://trac.sagemath.org/sage_trac/ticket/6632#comment:5 #6632].
{{{
sage: graphs.StarGraph(3).blocks_and_cut_vertices()
([[1, 0], [2, 0], [3, 0]], [0, 0, 0])
}}}
The problem occurs because the list C of cut vertices should be treated as
a set, not a list: membership should be tested before adding a vertex to
the list.
Following a suggestion of Jason's, I also changed the initialization of
the parent array to None.
Patch will be attached below.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6807>
Sage <http://sagemath.org/>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
