is_eulerian doesn't handle disconnected graphs properly

[brunellus]

Consider following:

sage: g = DiGraph({0:[1], 1:[0], 2:[]}); g.is_eulerian()
False

is_eulerian sees two components and refuses to label graph as an eulerian one. But the common definition (and the docstring) says that eulerian graph has all its edges coverable by one tour -- that permits disconnected graphs as long as every component but one don't contains any edges.

Apply:

• trac_12108_is_eulerian_fix2.patch

[brunellus]

My first patch. :-)

[ncohen]

Replying to brunellus:

My first patch. :-)

And a good one ! :-)

Just one remark : the connected_components_number actually calls connected components. So instead of computing the number of CC and *then* go over all vertices, what would you think of something like that :

ok = True
for cc in self.connected_components():
    if len(cc) > 1:
        if ok:
           ok = False
        else:
           return False

I feel like it could be faster, but that's really about milliseconds :-)

Nathann

[brunellus]

Thanks for pointing this out. I will send another patch (with a few more tests cases, also) -- is it prefered to create it on top of the first one, or is it better to be replacement?

[ncohen]

Oh, it is better to replace the patch (on bigger patches you can have a lot of modifications to make, soo...). It actually is not hard if you use mercurial queue

 http://wiki.sagemath.org/MercurialQueues

And it will not be a waste if you intend to write other patches ;-)

Nathann

[brunellus]

Thanks very much for the advices.

Graph.eulerian_circuit() suffers from a similar error (it tries to take first vertex at hand and if it is an isolated one, it immidiately fails) -- but I am already rewriting it for #10135, keeping this in mind.

[ncohen]

Oh ! I did not noticed you updated the patch...... It's good to go ! :-)

Nathann

[brunellus]

Thanks!