#13721: Additional tests for graph symmetries and an improvement of
is_vertex_transitive
----------------------------------+-----------------------------------------
Reporter: azi | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-5.6
Component: graph theory | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Jernej Azarija | Merged in:
Dependencies: | Stopgaps:
----------------------------------+-----------------------------------------
Comment (by ncohen):
Hellooooooo Jernej !
First, thank you ver much for these patches ! I love to have fun with the
graphs' automorphism groups these days -- though I really am a beginner --
and it is nice to see Sage improve on that side :-)
I have many questions, though :
* Why do you insist on returnin the group ? It feels like it is a very
complicated object that shouldn't be built unless necessary :-)
I do agree that the current implementation seems QUITE wasteful when
just checking that a graph is indeed vertex_transitive. But I do not
really get what the four lines after ``new_partition = ...`` actually do.
Isn't it totally equivalent to check that the two partitions are equal up
to reordering ? Something like that should do the trick, as (if I make no
mistake) the partition can only be more refined than the one given as an
input) : ``sorted(map(len,partition)) == sorted(map(len,new_partition))``
And I expect that this plugged with the current code, should be faster
than calling GAP :-)
* You write is_edge_transitive by copying the graph twice. Wouldn't it
work to just build the automorphism group, and then ask GAP to give you
the order or the Orbit of *only one edge* with the permutation group acts
on it ? I think that this can be done (and probably faster), but I am a
beginner with GAP so perhaps you are right.
* Not sure if this can also be done on is_arc_transitive, because we are
not talking of sets anymore, but of ordered pairs.
* ``return self.is_edge_transitive() and self.is_vertex_transitive() and
not self.is_arc_transitive()`` this line makes Sage compute the
automorphism group 3 times, but I have no idea how bad it is. Perhaps not
worth the trouble.
* ``is_symmetric`` I share Tom's advice on aliases `^^;`. His wording is
actually very nice : "I love the amount of stuff we can do with graphs...
but I hate the length of the list." `:-P`
* There are some problems with the documentation and doctests : the way it
is written (the "::" are not placed where they should) many doctests do
not appear correctly on the HTML documentation.
* The way it is written, the function is_edge_transitive is a member of
DiGraph objects. When in doubt, the behaviour of the method should be made
clear in the documentation. Or else we can move it to Graph.py `:-)`
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13721#comment:6>
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.
