#12325: Eulerian circuits/paths for (di)graphs
----------------------------+-----------------------------------------------
Reporter: brunellus | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.0
Component: graph theory | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies: #10135
----------------------------+-----------------------------------------------
Comment(by ncohen):
Hellooooooooooooooooo !!!
Looks good ! Some comments :
* The patch does not apply on sage-5.0-beta1 (nothing serious)
* You seem to have moved the function through the file.. Well, if
there is a reason behind could you produce first one patch that moves it,
and another one that changes it ? As such, it is very hard while reading
the patch to see what you changed `^^;` Only only sees a function removed,
and a different one added.
* Perhaps I am making a mistake but it seems in your patch that if
path is True and the graph is undirected you keep no track of the two
vertices with odd degree. One of them should become the start_vertex,
shouldn't it ?
* It is "easy" to test whether the graph is eulerian through the
is_eulerian function, and slightly harder to test whether there exists an
eulerian path because you have to find the two vertices yourself. What
would you think of modifying the is_eulerian function so that it also has
a ``path`` flag, tell you whether your graph admits an eulerian path, and
if necessary (perhaps another flag ?) return the two vertices with odd
degree ? Actually, I did ot understand why you did not write this code
"the lazy way", and by that I mean : first find the two special vertices,
add an edge between them, and test whether the resulting graph is
eulerian. This would avoid the duplication of the "empty components"
count. Actually, with the modification of the is_eulerian function, the
modifications of this patch to the eulerian_cycle function would amount to
a new argument, a call to is_eulerian(path = True, return_missing_edge =
True), and run the same old algorithm with one of the two vertices given
by is_eulerian.
* If I did not say anything stupid in my former remark, could you add
a doctest of an undirected graph which has a eulerian path and the
function's output ?
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12325#comment:2>
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.
