Opened 11 years ago

Closed 9 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:

Status badges

Description

This is reported in sage-support.

Attachments (1)

trac_10135_eulerian_circuit_rewrite.patch (4.6 KB) - added by brunellus 10 years ago.

Download all attachments as: .zip

Change History (10)

comment:1 Changed 10 years ago by brunellus

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?

comment:2 Changed 10 years ago by brunellus

  • Cc brunellus added

plausible -> meaningful :-)

comment:3 Changed 10 years ago by jason

  • Cc jason added

If you've got a better way to do it, go for it!

Changed 10 years ago by brunellus

comment:4 Changed 10 years ago by brunellus

  • 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 brunellus

I started #12135 for the mentioned multiple loops problem.

comment:6 Changed 9 years ago by brunellus

Some additional changes to this code were introduced in #12325. I guess it would be efficient to review both tickets together.

comment:7 Changed 9 years ago by ncohen

  • 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 9 years ago by brunellus

  • Authors set to Lukáš Lánský

comment:9 Changed 9 years ago by jdemeyer

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