Eulerian Cycle of a Digraph

i like this post (click again to cancel)
2
i dont like this post (click again to cancel)

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.

asked Jan 06 '11

Eviatar Bach gravatar image Eviatar Bach
474 2 10 26
i like this answer (click again to cancel)
2
i dont like this answer (click again to cancel) Eviatar Bach has selected this answer as correct

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.

link

posted Jan 06 '11

kcrisman gravatar image kcrisman
6639 13 66 150
Thank you! I will take a look. Eviatar Bach (Jan 07 '11)

Your answer

Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!
[hide preview]

Question tools

Tags:

Stats:

Asked: Jan 06 '11

Seen: 130 times

Last updated: Jan 06 '11

powered by ASKBOT version 0.7.22
Copyright Sage, 2010. Some rights reserved under creative commons license.