Improve the is_vertex_transitive test

[azi]

As it turned out from the discussion in the TRAC ticket 13721, the is_vertex_transitive method can be optimized and simplified substantially.

This TRAC ticket aims at achieving that.

[ncohen]

partition an new_partition are both partitions of the vertex set, and new_partition is necessarily more refined (i.e. each set of new_partition is a subset of some set of partition). Hence, they are equal if and only if they have same length !

Nathann

[azi]

I can fix the code if someone explain to me what exactly should this partition thing be doing in the first place. I suspect what it wants to verify is if a given partition is a system of imprimitivity?

[ncohen]

Helloooooo !!

Well, I just uploaded a code that replaces the block of 4 lines by the equality test. The point is that partition is necessarily blocks of imprimitivity of the automorphism group, for this argument says that Sage should only consider automorphisms that respect the partition given (i.e. only those such that an element from a set inside of partition stay in the same set). And as new_partition is necessarily a refinment of new_partition, the two are equal if and only if their lengths are the same.

Nathann

[azi]

Indeed, this makes sense! Also could you add a quick regularity check inside?

The degrees of every element of the same partition should coincide!

[ncohen]

Here it is !

Nathann

[azi]

Looks good!

My only two questions are

1. Can we expect a partition cell to be empty
2. What happens if we call this thing on the empty graph?

[ncohen]

Updated !!

Nathann

[azi]

The patch looks fine to me. Shall I mark it as positively reviewed?

[ncohen]

Yep, you can ! :-)

Nathann

[ncohen]

(oh, and by the way I sent an email to Robert Miller, who originally wrote that code, and agreed with the shortcut that this patch implements) :-)

Nathann