#19586: Add is_cayley_graph
-------------------------------------+-------------------------------------
Reporter: jaanos | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.10
Component: graph theory | Resolution:
Keywords: Cayley graphs | Merged in:
groups | Reviewers:
Authors: Janoš Vidali | Work issues:
Report Upstream: N/A | Commit:
Branch: | fbff6b8e22c419beef4a5d991c00d5c512a933f9
u/jaanos/add_is_cayley_graph | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by {'newvalue': u'Jano\u0161 Vidali', 'oldvalue': ''}):
* author: => Janoš Vidali
* cc: ncohen (added)
* component: PLEASE CHANGE => graph theory
* keywords: => Cayley graphs groups
* commit: => fbff6b8e22c419beef4a5d991c00d5c512a933f9
* type: PLEASE CHANGE => enhancement
Old description:
New description:
This ticket adds a method `is_cayley_graph` to `GenericGraph`. This method
checks whether a graph or digraph (which may or may not be connected) is a
Cayley graph. If a certificate is requested, it also returns a permutation
group and a generator set which generate this graph.
--
Comment:
I should point out some questions and issues I have with this before it
goes into review.
* Should the method be called `is_cayley_graph`, or just `is_cayley`?
* The current implementation is slow, mainly due to the slow GAP interface
and the unneeded work done by `conjugacy_classes_subgroups`. Ticket #19585
already improves this, but it would be even better to do something like
this:
{{{
#!python
gap = A._gap_().parent()
C = gap.new("""
First(ConjugacyClassesSubgroups(%s),
x -> Order(Representative(x)) = %d
and IsTransitive(Representative(x), [1..%d]));
""" % (A._gap_().name(), n, n))
c = (gap.eval('%s = fail' % C.name()) != 'true')
if c and certificate:
G = A.subgroup(gap_group=C.Representative())
}}}
Now, I guess that maybe this doesn't really belong in `generic_graph.py`.
But maybe we could have a method in `PermutationGroup_generic` which
checks for the existence of such a group (and have it returned if
requested)?
* I should probably check whether the function works correctly with graphs
with loops and multigraphs (my instinct says yes for the former and no for
the latter).
* Can we have Unicode characters in the docstrings? If I spell my name
properly, Sage compiles, but the documentation doesn't. I guess I could
add `# -*- coding: utf-8 -*-` to the top of the file (haven't tested it),
but I don't know if we want to do it:)
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=9fc982474fb5a2f7161ca0242040ce624a774ec2
9fc9824]||{{{Initial documentation for is_cayley_graph()}}}||
||[http://git.sagemath.org/sage.git/commit/?id=86c766f6f4f10eced30037916de8ffc75fd5dc35
86c766f]||{{{Implement is_cayley_graph for connected graphs}}}||
||[http://git.sagemath.org/sage.git/commit/?id=60142d0e8e2b0308ecc67637c7ea3bcd30b68792
60142d0]||{{{Add tests for is_cayley_graph}}}||
||[http://git.sagemath.org/sage.git/commit/?id=0f925f635ade0e6b9e9f2ad469aa2e5f11e11d12
0f925f6]||{{{Implement is_cayley_graph for disconnected graphs}}}||
||[http://git.sagemath.org/sage.git/commit/?id=fbff6b8e22c419beef4a5d991c00d5c512a933f9
fbff6b8]||{{{Add note regarding optional packages}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/19586#comment:2>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
