Ask Your Question
2

Eulerian Cycle of a Digraph

asked 2011-01-06 13:43:08 -0600

Eviatar Bach gravatar image

Hello,

Is there a function to do an Eulerian cycle of a digraph? eulerian_cycle works on undirected graphs, but not on digraphs. Basically I'm looking for an equivalent to Mathematica's EulerianCycle. Does this exist?

Thanks in advance.

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
2

answered 2011-01-06 15:48:35 -0600

kcrisman gravatar image

Are you sure about eulerian_cycle? I think it's eulerian_circuit in Sage (?). But it does seem to only work for undirected graphs...

I would say this is a start.

sage: D = DiGraph('IRAaDCIIOWEOKcPWAo')
sage: D.is_eulerian()
True

In fact, the code basically finds the circuit, but doesn't keep it like eulerian_circuit does. So it could be modified to keep it, just like eulerian_circuit.

However, things get bad when we convert, because it doesn't keep double edges... hmmm...

sage: E = D.to_undirected()
sage: E.eulerian_circuit()
False

Anyway, this could probably be implemented pretty easily. I highly suggest you post about this on sage-devel, and/or file a ticket at trac.sagemath.org if one doesn't already exist for this.

edit flag offensive delete link more

Comments

Thank you! I will take a look.

Eviatar Bach gravatar imageEviatar Bach ( 2011-01-07 16:43:59 -0600 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2011-01-06 13:43:08 -0600

Seen: 231 times

Last updated: Jan 06 '11