Opened 11 years ago
Closed 10 years ago
#10135 closed defect (fixed)
eulerian_circuit() of Graph can't handle multiple edges
Reported by: | mvngu | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-5.0 |
Component: | graph theory | Keywords: | |
Cc: | brunellus, jason | Merged in: | sage-5.0.beta2 |
Authors: | Lukáš Lánský | Reviewers: | Nathann Cohen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
This is reported in sage-support.
Attachments (1)
Change History (10)
comment:1 Changed 10 years ago by
Changed 10 years ago by
comment:4 Changed 10 years ago by
- Status changed from new to needs_review
The patch I just sent strives for three advancements in eulerian_circuit():
- It should close this ticket. :-)
- It should run in O(|E|) time.
- It should find eulerian circualiton in disconnected cases like
Graph({0: [], 1: [2], 2: [3], 3: [1], 4: []})
where previous one failed. This is similar to the trac #12108. Notice, that you need to apply the patch I sent to that ticket before testing this code -- if you don't, one of the tests fails because is_eulerian() doesn't work correctly.
During testing I was surprised by way Sage handles multiple loops:
sage: g=Graph({0: [0, 0]}) sage: g.degree(0) 4 sage: g.delete_edge(g.edge_iterator(0).next()) sage: g.degree(0) 0
I think that Sage should either reject multiple loops at the beginning (merge them to one, for example), or handle them as separate. This is surprising behavior. What do you think?
comment:5 Changed 10 years ago by
I started #12135 for the mentioned multiple loops problem.
comment:6 Changed 10 years ago by
Some additional changes to this code were introduced in #12325. I guess it would be efficient to review both tickets together.
comment:7 Changed 10 years ago by
- Reviewers set to Nathann Cohen
- Status changed from needs_review to positive_review
Helloooooo !!
This one's good to go, too ! The reverse() function is actually slower than the copy(), but it makes much more sense to solve this problem directly by modifying the backends than by changing this method. Thank you for this patch ! :-)
Nathann
comment:8 Changed 10 years ago by
comment:9 Changed 10 years ago by
- Merged in set to sage-5.0.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
I see that the function is based on Fleury's algorithm. Would it be plausible if I rewrite it using asymptotically faster Hierholzer's algorithm?