Opened 6 years ago

Closed 6 years ago

Last modified 6 years ago

#13984 closed enhancement (fixed)

Improve the is_vertex_transitive test

Reported by: azi Owned by: tbd
Priority: major Milestone: sage-5.7
Component: graph theory Keywords:
Cc: azi ncohen Merged in: sage-5.7.beta2
Authors: Nathann Cohen Reviewers: Jernej Azarija
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #13721 Stopgaps:

Description

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.

Attachments (1)

trac_13984.patch (1.6 KB) - added by ncohen 6 years ago.

Download all attachments as: .zip

Change History (16)

comment:1 Changed 6 years ago by azi

  • Component changed from PLEASE CHANGE to graph theory
  • Status changed from new to needs_info
  • Type changed from PLEASE CHANGE to enhancement

comment:2 Changed 6 years ago by ncohen

  • Dependencies set to #13721

comment:3 Changed 6 years ago by ncohen

  • Status changed from needs_info to needs_review

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

comment:4 Changed 6 years ago by 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?

comment:5 Changed 6 years ago by 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

comment:6 Changed 6 years ago by 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!

comment:7 Changed 6 years ago by ncohen

Here it is !

Nathann

comment:8 Changed 6 years ago by 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?

Changed 6 years ago by ncohen

comment:9 Changed 6 years ago by ncohen

Updated !!

Nathann

comment:10 Changed 6 years ago by azi

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

comment:11 Changed 6 years ago by ncohen

Yep, you can ! :-)

Nathann

comment:12 Changed 6 years ago by azi

  • Reviewers set to Jernej Azarija
  • Status changed from needs_review to positive_review

comment:13 Changed 6 years ago by jdemeyer

  • Authors set to Nathann Cohen

comment:14 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.7.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:15 Changed 6 years ago by 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

Note: See TracTickets for help on using tickets.