#19586: Add is_cayley_graph
-------------------------------------+-------------------------------------
Reporter: jaanos | Owner:
Type: enhancement | Status: needs_work
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: | 8685628455d2364bbb1896bf28e18c637bfab50c
u/jaanos/add_is_cayley_graph | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by jaanos):
Hi!
Some quick replies:
> - 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.
Yes, I was a bit worried about that. Anyway, this was intended more as a
demonstration that the method works on non-simple graphs, so maybe it
should be moved to the Examples section. Instead of printing out the
generating set, maybe we should just print its length and the number of
distinct elements, and maybe check that it contains the identity element.
> - about `is_cayley` returning generators: do you think that it is
necessary to
> have this option, or should we let users call `.generators()` on the
group
> object?
Yes, because the generating set of a Cayley graph is not the same as the
set of generators of a group. A trivial example would be a complete graph
- its generating set as a Cayley graph is the whole group, which can of
course be generated by some subset of its elements. For a disconnected
Cayley graph, on the other hand, the generating set will not even generate
the whole group.
This reminds me that I should probably add a further optimization: if a
(simple) graph is connected and dense (say, vertex degree more than half
the order), then it may be more efficient to check for Cayleyness of its
complement (in case it is disconnected it will be more efficient,
otherwise the same).
> - Can this
> {{{
> + t = C[0].is_cayley(return_group=certificate)
> + if certificate:
> + c, CG = t
> }}}
> be replaced by that?
> {{{
> + c, CG = C[0].is_cayley(return_group=certificate)
> + if certificate:
> }}}
> The value `None` may be replaced by `None` uselessly, but that's not a
big
> problem (if I don't get anything wrong)
No, because we are not guaranteed that a tuple will be returned.
> - About {{{return tuple(out)}}} -- there is nothing wrong with this,
though I
> don't think it is necessary to force a 'tuple'. This is no request to
change
> it of course, it is fine as it is if you prefer it this way.
True, but other methods returning multiple data also return tuples, so I
think it should stay (IMO lists should be used when the size of the output
is not predetermined, and its members have the same type).
I agree with the comments that I haven't replied to. I'm a bit busy these
days, so (anyone) feel free to implement these suggestions if you feel
like it.
Janoš
--
Ticket URL: <http://trac.sagemath.org/ticket/19586#comment:63>
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.
