Opened 8 years ago

Closed 8 years ago

#12325 closed enhancement (fixed)

Eulerian circuits/paths for (di)graphs

Reported by: brunellus Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.0
Component: graph theory Keywords:
Cc: brunellus Merged in: sage-5.0.beta3
Authors: Lukáš Lánský Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #10135 Stopgaps:

Description (last modified by ncohen)

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

Apply :

Attachments (3)

trac_12325_eulerian_paths.patch (8.8 KB) - added by brunellus 8 years ago.
trac_12325_eulerian_move.patch (7.2 KB) - added by brunellus 8 years ago.
trac_12325_eulerian_paths.2.patch (10.0 KB) - added by brunellus 8 years ago.

Download all attachments as: .zip

Change History (11)

Changed 8 years ago by brunellus

comment:1 Changed 8 years ago by brunellus

  • Status changed from new to needs_review

comment:2 Changed 8 years ago 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

Changed 8 years ago by brunellus

Changed 8 years ago by brunellus

comment:3 Changed 8 years ago by brunellus

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áš.

comment:4 Changed 8 years ago by ncohen

  • Description modified (diff)

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

comment:5 Changed 8 years ago by ncohen

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

comment:6 Changed 8 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

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

Nathann

comment:7 Changed 8 years ago by brunellus

  • Authors set to Lukáš Lánský

Thank you for the review. :-)

comment:8 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.0.beta3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.