#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)
Change History (16)
comment:1 Changed 8 years ago by
- 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 8 years ago by
- Dependencies set to #13721
comment:3 Changed 8 years ago by
- Status changed from needs_info to needs_review
comment:4 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
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 8 years ago by
Here it is !
Nathann
comment:8 Changed 8 years ago by
Looks good!
My only two questions are
- Can we expect a partition cell to be empty
- What happens if we call this thing on the empty graph?
Changed 8 years ago by
comment:9 Changed 8 years ago by
Updated !!
Nathann
comment:10 Changed 8 years ago by
The patch looks fine to me. Shall I mark it as positively reviewed?
comment:11 Changed 8 years ago by
Yep, you can ! :-)
Nathann
comment:12 Changed 8 years ago by
- Reviewers set to Jernej Azarija
- Status changed from needs_review to positive_review
comment:13 Changed 8 years ago by
comment:14 Changed 8 years ago by
- Merged in set to sage-5.7.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
comment:15 Changed 8 years ago by
(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
partition
annew_partition
are both partitions of the vertex set, and new_partition is necessarily more refined (i.e. each set ofnew_partition
is a subset of some set ofpartition
). Hence, they are equal if and only if they have same length !Nathann