Eulerian circuits/paths for (di)graphs

[sagetrac-brunellus]

Currently, there is only a function for finding an eulerian circuit in an undirected graph.

Apply :

• attachment: trac_12325_eulerian_move.patch
• attachment: trac_12325_eulerian_paths.2.patch

Depends on #10135

CC: @sagetrac-brunellus

Component: graph theory

Author: Lukáš Lánský

Reviewer: Nathann Cohen

Merged: sage-5.0.beta3

Issue created by migration from https://trac.sagemath.org/ticket/12325

[sagetrac-brunellus]

Attachment: trac_12325_eulerian_paths.patch.gz

[nathanncohen]

comment:2

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

[sagetrac-brunellus]

Attachment: trac_12325_eulerian_move.patch.gz

[sagetrac-brunellus]

Attachment: trac_12325_eulerian_paths.2.patch.gz

[sagetrac-brunellus]

comment:3

Hi, thanks for the remarks very much.

I tried to rewrite the fix -- you are certainly right that the eulerianess-checking code should be in the is_eulerian function. I am a big fan of "the lazy way" :-), but in this case it makes almost no difference, because there are no changes in the algorithm needed for allowing the path computation -- the only important step is setting the start_vertex variable. And thanks for the advice about two patches -- it definitelly makes sense.

Lukáš.

[nathanncohen]

comment:4

Hellooooooooooooo !!!

Great ! Thank you very much for these two patches, it is much easier to read. And you also factored things like many (g.degree(u)-g.degree(v)) :-)

Well, I see nothing wrong with this patch, it passes all tests and does it job. Could you rebase the first of your two patches over sage-4.5-beta1 though ? It still does not apply.

Nathann

[nathanncohen]

comment:5

Argggggg !! It's totally my fault ! I had not seen the patch depended on #10135. There's nothing left to do with this patch :-)

Nathann

[nathanncohen]

Reviewer: Nathann Cohen

[nathanncohen]

comment:6

This one is also good to go, and now its dependency has been reviewed !

Nathann

[sagetrac-brunellus]

Author: Lukáš Lánský

[sagetrac-brunellus]

comment:7

Thank you for the review. :-)

[jdemeyer]

Merged: sage-5.0.beta3