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 )
Currently, there is only a function for finding an eulerian circuit in an undirected graph.
Apply :
Attachments (3)
Change History (11)
Changed 8 years ago by
comment:1 Changed 8 years ago by
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
Changed 8 years ago by
Changed 8 years ago by
comment:3 Changed 8 years ago by
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
- 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
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
- 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:8 Changed 8 years ago by
- Merged in set to sage-5.0.beta3
- Resolution set to fixed
- Status changed from positive_review to closed
Hellooooooooooooooooo !!!
Looks good ! Some comments :
^^;
Only only sees a function removed, and a different one added.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.
Nathann