#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):
Helloooooooooo !!
> 1. I am not sure if this can be done without computing the automorphism
of the group.
Well, I guess that it cannot, but it can be done without dealing manually
in Sage with an automorphism group that is internally built by the
automorphism_group function (possibly Nauty), even when return_group is
set to False. From what I understand of the algorithm, the partition that
is returned consists in the orbits of the graphs's vertices. Hence in our
case, the graph is transitive if and only if the partition returned has
only one element in it (--> the whole vertex set). When the partition
given as an input is *NOT* this trivial partition, the algorithm considers
that vertices from differents sets of the partition are of a different
"kind" (or color, or type, or whatever) and returns the orbits of the
graphs respecting the vertices' kind/color/type/whatever. The small patch
I attach replaces a nasty loop by a unique line, and your example of code
returns the same answers for the values I was able to compute, and all
tests pass on all files of the graph/ folder `:-)`
> What exactly do you mean by refined partition ?
By "refined", I mean that each set of the new partition is a subset of one
set of the former partition.
> 2. I agree. Though I am not sure how to get the orbit for an action that
acts on edges (not on vertices.) I am not sure this is possible. Can
someone verify this?
Well. I am no GAP expert but I used to use it with a guy who knew much
better what he did with it, and I can still understand the code's meaning.
What I have is the following : if G is a GAP Group acting on a set (of
vertices), then you can compute the orbit of a pair of edges like that :
{{{
gap('Orbit(G,[1,6],OnSets)')
}}}
And it looks like there is another keyword for ordered sets : OnTuples.
There is even one made especially for pairs : OnPairs.
So I guess that gap('Orbit(G,my_edge,OnSets)') would do the trick for
edge-transitivity, and gap('Orbit(G,my_edge,OnPairs)') for arc-
transitivity `:-)`
> 3. That is a good point! This could be solved by having an optional
argument that supplies the automorphism group to the named functions!
>
> 4. Hahaha agree about the wording - I am waiting for the right time to
tell it to someone IRL :-)
>
> 5.
> 6. This should most likely be moved to Graph.py
+1
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13721#comment:8>
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.
