#6632: Bug in blocks_and_cut_vertices() of a graph that occurs when vertex 0 is
a
cut vertex
--------------------------+-------------------------------------------------
Reporter: hartke | Owner: rlm
Type: defect | Status: new
Priority: minor | Milestone:
Component: graph theory | Keywords:
Reviewer: | Author:
Merged: |
--------------------------+-------------------------------------------------
There is a bug in the blocks_and_cut_vertices() function for graphs such
that an incorrect result is returned if the vertex 0 is a cut vertex.
{{{
sage: G=Graph()
sage: G.add_vertices(range(5))
sage: G.add_edges([(0,1),(0,2),(1,2),(2,3),(2,4),(3,4)])
sage: print G.blocks_and_cut_vertices()
([[0, 1, 2]], [])
}}}
The bug arises because the algorithm as presented in the referenced book
uses 0 to indicate a vertex not in the graph. However, in Sage, we number
the vertices of a graph starting at 0.
A patch will be attached below.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6632>
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
-~----------~----~----~----~------~----~------~--~---
