#8273: Enumeration of cycles in directed graphs
----------------------------+-----------------------------------------------
Reporter: abmasse | Owner: rlm
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.3.3
Component: graph theory | Keywords: cycle, enumeration
Author: abmasse | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
Changes (by abmasse):
* status: needs_review => needs_work
* type: defect => enhancement
Comment:
Nathann Cohen wrote:
Hello !!!
I just took a quick look at your patch :
- Don't you think it may still be interesting to first check whether
the given is/is not in any cycle ? It just amounts to check the
strongly connected component containing this vertex is a singleton. I
wrote is_strongly_connected in c_graph.pyx, so it is in Cython and
very efficient... strongly_connected_component_containing_vertex is
still to be written, but it should take at most 6 lines, which are a
pure copy of is_strongly_connected :-)
Of course if this function is recursive, it is totallty different as
it may mean many different calls :-)
- I see you wrote many comments in the code, which is nice, but some
loops are not commented at all... Do you think the algorithm can be
easily understood reading it ? :-)
1530 if len(sccs) == 0: raise StopIteration
This condition shouldn't ever happen, as the list of strongly
connected components is a list of list.. In the "worst" case, the
returned list has a singleton per item :
[ [0], [1], .... ], and in this case len(sccs) == self.order()
Thank you for your comments ! I will indeed add some comments in the code
so that everyone can understand what it does. As for the first comment, I
think it is better not to compute the strongly connected components in the
private function `_cycles_iterator_vertex(...)` since it will be computed
for every starting vertices (i.e. it will be quadratic in the worst case).
As for the remark for trivial cycles, it is a good remark: I think I will
add another parameter to choose if one wants to include trivial cycles or
not. What do you think?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8273#comment:3>
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.
