#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 !
Don't say sorry, your comments are very welcome and are clearly pertinent
!
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".
Done. It was an old comment I forgot to delete.
* 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 !
Done. I noticed it while writing the code, but I was too lazy to do it. It
turned out to be very simple, so I'm glad you mentionned it.
* 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.
Done. Thanks for the information !
* 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
? :-)
There is no argument vertex in `all_simple_paths`, unless I'm mistaken. I
guess you mean `_all_cycles_iterator_vertex` ? But your understanding is
correct. It seems odd to have the arguments `vertex` and
`starting_vertices`: the reason I do that is that I need to know what are
the allowed initial vertices so that I return only one cycle among
`[0,1,0]` and `[1,0,1]` when `rooted=False`. An efficient and simple way
to control equivalent rooted cycles is to return the one with smallest
starting vertex.
* 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
Done. You are right. The meaning of `rooted` is now documented 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 ?
The reason I put this flag is that I want the function
`_all_simple_cycles_iterator_vertex` not to cycle infinitely if one uses
it directly. So, yes, I don't use it directly in my code, but this allows
me to remove the warning about infinite cycle there was before.
I'll upload a patch in a short while.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8273#comment:8>
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.
