#6632: [with patch, needs review] 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: sage-4.1.1
Component: graph theory | Keywords:
Reviewer: | Author:
Merged: |
--------------------------+-------------------------------------------------
Comment(by jason):
Thanks for looking at this!
How about we trade reviews? I'd like to get #6659 reviewed and in 4.1.1
:).
Could you also just initialize p to [None]*G.num_verts()? Then the check
at the bottom becomes {{{p[v] is None}}}.
I'm a little concerned about you taking out the last B.append(S)
statement. Can you comment on it? I don't have Jungnickel handy, so
forgive me if the answer is easy.
I noticed a few other things with this function, but I'll open up another
ticket to address these. For one, it totally ignores the original vertex
labeling in the answer. For example, you can't make sense of the
following output.
{{{
sage: g=graphs.CubeGraph(2)
sage: g.blocks_and_cut_vertices()
([[2, 3, 1, 0]], [])
sage: g
2-Cube: Graph on 4 vertices
sage: g.vertices()
['00', '01', '10', '11']
}}}
Second: there seems to be a serious error (in the old implementation too)
in the case of a star graph. Look at the cut vertices returned here.
{{{
sage: g=graphs.StarGraph(8)
sage: g.blocks_and_cut_vertices() # current implementation
([[1, 0], [2, 0], [3, 0], [4, 0], [5, 0], [6, 0], [7, 0], [8, 0], [0]],
[0, 0, 0, 0, 0, 0, 0])
}}}
Your implementation corrects at least one problem: the last [0] is gone
(probably as an effect of you taking out that last append() statement,
right?):
{{{
sage: g=graphs.StarGraph(8)
sage: g.blocks_and_cut_vertices() # your implementation
([[1, 0], [2, 0], [3, 0], [4, 0], [5, 0], [6, 0], [7, 0], [8, 0]],
[0, 0, 0, 0, 0, 0, 0])
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6632#comment:5>
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
-~----------~----~----~----~------~----~------~--~---
