#19586: Add is_cayley_graph
-------------------------------------+-------------------------------------
Reporter: jaanos | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.10
Component: graph theory | Resolution:
Keywords: Cayley graphs | Merged in:
groups | Reviewers: Nathann Cohen
Authors: Janoš Vidali | Work issues:
Report Upstream: N/A | Commit:
Branch: | 95e34eecb315bcd0fded9c4f02a22b8c85e0ca1f
u/jaanos/add_is_cayley_graph | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by jaanos):
* status: needs_work => needs_review
Old description:
> This ticket adds a method `is_cayley` 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.
>
> A method `has_transitive_subgroup` has also been added to
> `PermutationGroup_generic`. For a given order, it determines whether the
> group has a subgroup of this order, and returns it if requested. If no
> order is given, it is taken to be the order of the group itself (i.e.,
> the method then simply tells whether the group is transitive).
New description:
This ticket adds a method `is_cayley` to `GenericGraph`. This method
checks whether a graph or digraph (which may or may not be connected) is a
Cayley graph. If requested, it also returns a permutation group, a mapping
from vertices to group elements, and a generating set of the Cayley graph.
A method `has_regular_subgroup` has also been added to
`PermutationGroup_generic`. It determines whether the group has a regular
subgroup, and returns it if requested.
--
Comment:
Hi!
I have implemented your suggestions. Some comments:
> - About the doctest {{{sage: S}}}. I am not sure that the output will be
> identital on all platforms: the order of the generators can change on
a
> different architecture, and this would be reported as a broken
doctest. If you
> have reasons to believe that it will work on all platform then it can
stay,
> otherwise the test must be made platform-independent. This can be done
by
> building the graph from the generators for instance. If you do not
believe
> that it is worth checking (e.g. if it is already tested elsewhere)
then you
> can just remove this line, or test something different.
I've moved it to the Examples section and added a `# random` flag. I've
also added this flag to the doctests in `permgroup.py` where the
generators of a group are output.
> - `regular_subgroup` given that the default behaviour is to return a
boolean,
> shouldn't it be named `has_regular_subgroup` instead?
Actually, the default behaviour was to return a group, but I changed it
now. It seems more appropriate this way, since the method will return
''a'' regular subgroup, not ''the'' regular subgroup (if there is one in
the first place). Now, the returned group (if requested) can be thought of
as a certificate. Anyway, `is_cayley` now explicitly specifies the
`return_group` parameter of `has_regular_subgroup` in both cases.
> - {{{c, G, d, S}}} could you give more meaningful names to those
variables? I
> guess that 'G' is alright (even though, in a Graph function...) but
`d` and
> `S` could easily be `graph_to_group_map` and `generators`. Or anything
else
> you might prefer.
OK, I have now changed `map`, `d` and `S` to `compute_map`, `map` and
`genset`, respectively.
> - You do not need `\` at the end of the line when a `[({` is open and
remains to
> be closed.
True, but the `\` in line 20891 of `generic_graph.py` is actually outside
any parentheses.
Janoš
--
Ticket URL: <http://trac.sagemath.org/ticket/19586#comment:68>
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 https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
