#13289: Determine if a vertex is a cut vertex
---------------------------------+------------------------------------------
Reporter: dcoudert | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.3
Component: graph theory | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: David Coudert | Merged in:
Dependencies: | Stopgaps:
---------------------------------+------------------------------------------
Comment (by sluther):
Replying to [comment:16 dcoudert]:
> I have also changed seen from set to dict. It could be faster to access
a cell of a >dictionary than to test is a elt is in a set.
IIRC they are both implemented as hash maps, which should make the set
faster. I think it has something to do with the fact that the "v in s" has
to catch the KeyError and return False instead of just raising the
exception. That's exactly what happens with your dict here. It doesn't
catch KeyError, but that's fine because it never occurs. Making it faster.
In contrast, if you let it catch the exception aka "seen.get(w, False)",
the dict is a lot slower.
>Furthermore, I avoid testing w!=u by initializing seen[u] to True, so it
will never be considered.
>
Good idea.
Once I checked the manual and ptestlong, I'll give it a positive review.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13289#comment:18>
Sage <http://www.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.
