#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: |
----------------------------+-----------------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
Several comments :
* I do not understand the comment "First, we handle the trivial paths if
needed" at line 1519 of digraph.py. What you do just afterwards is
initialize the list of paths, which is nicely done regardless of the value
of "trivial".
* I did not notice it before, but you are maintaining a list of values to
which you append things, while only removing the smallest element. This is
clearly a heap !! By using them (see
http://docs.python.org/library/heapq.html), you could *theoretically*
reduce the complexity of your computations. Well, I think you patch is
fixe as it is now, but if you need your computations to speed up a bit,
this is definitely worth a try !
* Instead, when starting_vertices = None, of setting it to
self.vertices(), you can also set it to just "self". When, later on, you
write "for v in starting_vertices", it will use the iterator over the
vertices from "self", which can be slightly better. Well, you algorithm is
not meant to be used on graphs with a large number of vertices anyway, so
it's not a problem in the present case.
* in all_simple_paths, you both have a "vertex" argument and a "starting
vertex" argument. Besides, in the documentation, you say that vertex is
the starting vertex of the cycle. What I understand is : the cycles you
enumerate will ALL contain "vertex", but the first vertices of each cycle
you will return will belong to starting_vertices. Is this right ? :-)
* line 1706 : I understand your comment as "If cycles are NOT rooted",
which is what your code does and appears more correct. Besides, is
"rooted" is documented in all_cycles_iterator, it is not in
_all_cycles_iterator
* You remove the bad edges in _all_simple_cycles if the correct flag is
set, though you never use it in your own code... As you remove them
manually in all_simple_cycles, perhaps you can just remove this option in
_all_simple_cycles ?
Short of this, your patch is fine... Next update will definitely be a
positive review ! I did not update the patch myself as there were several
questions I did not know how to solve myself, so sorry if some comments
are clearly minor ones... :-)
Have fuuuuuuun !
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8273#comment:7>
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.
