#8273: Enumeration of cycles in directed graphs
----------------------------+-----------------------------------------------
Reporter: abmasse | Owner: rlm
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.3.4
Component: graph theory | Keywords: cycle, enumeration
Author: abmasse | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
Comment(by abmasse):
Hello, Nathann !
I corrected my patch according to your remarks. I agree with all of them
except the following one
I do not know much about iterators, but...
Well, the values of vertex_iterators are iterators,
so
{{{
for vi in vertex_iterators.values():
cycles.extend(list(vi))
}}}
For two reasons: (1) I want to iterate cycles with increasing length and
what you propose breaks this property. (2) There is no guarantee that
``list(vi)`` will ever terminate, since the number of cycles (when
``simple`` is set to False) may be infinite !
I also added three functions which iterate over paths. Note that the code
is almost the same, but for sake of efficienty, it seems better to me not
to intersect it. The main reason is that when you want to enumerate
unrooted cycles, there is a very fast way to verify that (just check that
the starting vertex of the current path is the smallest in the path).
Therefore, I prefered to separate the two functions.
Thank you for the useful comments !
Also, if you prefer me to break the patch into two smaller ones, just tell
me, I'll do it. I'll upload the patch in a short while.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8273#comment:5>
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.
