#13721: Additional tests for graph symmetries and an improvement of
is_vertex_transitive
----------------------------+-----------------------------------------------
Reporter: azi | Owner: jason, ncohen, rlm
Type: enhancement | Status: new
Priority: major | Milestone: sage-5.6
Component: graph theory | Keywords:
Work issues: | Report Upstream: N/A
Reviewers: | Authors: Jernej Azarija
Merged in: | Dependencies:
Stopgaps: |
----------------------------+-----------------------------------------------
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 [https://groups.google.com/forum/?fromgroups=#!topic
/sage-devel/b-wsvun9L7g 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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13721>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
