Ticket #13721 (closed enhancement: fixed)
Additional tests for graph symmetries
|Reported by:||azi||Owned by:||jason, ncohen, rlm|
|Cc:||rbeezer, ncohen||Work issues:|
|Report Upstream:||N/A||Reviewers:||Nathann Cohen, Tom Boothby|
|Authors:||Jernej Azarija||Merged in:||sage-5.7.beta1|
Description (last modified by ncohen) (diff)
The following ticket aims at enhancing the is_vertex_transitive method and introducing new symmetry tests for graphs namely if a graph is edge-transitive, arc-transitive, half-transitive and semi-symmetric.
I am still struggling to digest all sage development conventions so it might well be that the code is not yet in the proper format. I apologize for the inconvenience and hope someone can correct this.
Following are some comments related to the patch.
- is_vertex_transitive. This function has been changed so that it uses GAP to test transitivity. In addition a quick check for regularity has been added. The change was tested using the following function
def f(n): for i in xrange(1,n+1): c = 0 for el in graphs.nauty_geng(str(n)): if el.is_vertex_transitive(): c+=1 print i,c
and the results are
%timeit f(10) 5 loops, best of 3: 567 s per loop
for the old function and
%timeit f(10) 5 loops, best of 3: 222 s per loop
for the improvement.
- is_edge_transitive. This new function tests if a graph is edge-transitive. The main idea of the this test was suggested by Tom Boothby, see this sage-devel post.
- is_arc_transitive. Similar to the edge-transitive case. I believe there is a more efficient way to test for arc-transitivity but for now I suppose this one is good enough.
- is_half_transitive. This function tests if a graph is vertex and edge-transitive but not arc-transitive. As a speedup it uses the fact that a half-transitive graph is Eulerian (see Lemma 3.2.2 in the book Algebraic graph theory by Godsil and Royle.)
- is_semi_symmetric. Tests if a graph is regular, edge-transitive but not vertex-transitive. Again we use the fact that such graphs are always bipartite (Lemma 3.2.1 in Godsil & Royle) to speed up the test.
comment:35 Changed 4 months ago by ncohen
- Summary changed from Additional tests for graph symmetries and an improvement of is_vertex_transitive to Additional tests for graph symmetries
comment:38 Changed 4 months ago by boothby
- Reviewers changed from Nathann Cohen to Nathann Cohen, Tom Boothby