#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!
> > 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).
>
> The .density() and .complement() method raise exceptions on non-simple
graphs. I think that it is better to not care about this, unless you
really need those cases and the speedup is obvious.
That's why I said simple (and I hadn't thought out the implications of
non-simple graphs). But yes, the denser the graph, the greater the
probability that such a speedup will be achieved, and the greater
potential of speedup in this case. In the case of multiple edges, this
potential is smaller (the current method will be faster in general due to
the potentially smaller automorphism group), and I agree that we should
not even care about the cases when speedup is actually possible (e.g. when
all multiedges appear with the same multiplicity).
> > No, because we are not guaranteed that a tuple will be returned.
>
> Weird. I thought you said in the doctest that a tuple will always be
returned, whether the graph is a cayley graph or not, and that the
additional values would be set to `None` if necessary.
A tuple will be returned whenever some form of certificate is requested,
regardless of whether the graph is Cayley or not. What is being
differentiated here is whether the group has been requested in the first
place. Although if you prefer, a call to `is_cayley` could be made in each
branch of the `if` statement.
Janoš
--
Ticket URL: <http://trac.sagemath.org/ticket/19586#comment:65>
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.
