Closed 6bdad4c1-1e26-4f2f-a442-a01a2292c181 closed 11 years ago
There is a small problem with cached functions right now... -_-
Nathann
this looks weird:
def orbit(self, point, onsets = False, ontuples = False):
What about
def orbit(self, point, action = "onpoints"):
(or "OnPoints"
?) which is the default,
and then sort out the cases action = "onsets"
, etc. ?
Totally right...
Just updated it ! And the function only takes tuples as arguments now. I so hate it when design decisions have to be changed for technical issues -_-
.
Nathann
Attachment: trac_14291.patch.gz
There are more useful permutation group actions, see http://www.gap-system.org/Manuals/doc/ref/chap41.html
Namely, OnPairs, OnSetsSets, OnSetsDisjointSets, OnSetsTuples, OnTuplesSets, OnTuplesTuples
all should work just fine.
One has to canonize the representative to start with, for some of them, see here. E.g.
Orbit(SymmetricGroup(5),Set([[2,4],[1,3]]),OnSetsSets);
is OK, but
Orbit(SymmetricGroup(5),[[2,4],[1,3]],OnSetsSets);
gives an error.
Less sure about OnIndeterminates
.
There is also a support for user-defined actions, but this would mean either specifying a piece of GAP code, or providing a callback, which seems to be too crazy to implement.
Helloooooooo !!
There are more useful permutation group actions, see http://www.gap-system.org/Manuals/doc/ref/chap41.html
Yepyep, I saw them but I really only need OnTuples
and OnSets
myself, and as I do not really see how I could use the others I do not think that it would be wise to expose them myself. Soooo unless you want to write that additional patch yourslf, ... :-)
Nathann
Description changed:
---
+++
@@ -1,3 +1,7 @@
A small patch to let us compute the orbits of sets and tuples by exposing it from GAP.
-Nathann
+And a reviewer patch adding more stuff.
+
+Apply
+1. [attachment: trac_14291.patch](https://github.com/sagemath/sage-prod/files/10657404/trac_14291.patch.gz)
+2. [attachment: 14291_reviewer.patch](https://github.com/sagemath/sage-prod/files/10657405/14291_reviewer.patch.gz)
Replying to @nathanncohen:
Helloooooooo !!
There are more useful permutation group actions, see http://www.gap-system.org/Manuals/doc/ref/chap41.html
Yepyep, I saw them but I really only need
OnTuples
andOnSets
myself, and as I do not really see how I could use the others I do not think that it would be wise to expose them myself. Soooo unless you want to write that additional patch yourslf, ...:-)
OK, needs your review now :-P
OK, needs your review now
:-P
Cool :-P
Well, for a start sage -coverage
will not like the documentation of supported_actions
at all. Why do you want to create a function just to list them ? Why don't you just include in the methods, or make it a variable in the module ? (anyway you still have to split cases in orbits
in order to know what to return).
Would it be possible to add a link toward GAP's documentation where all those actions are defined ?
Nathann
Attachment: 14291_reviewer.patch.gz
Replying to @nathanncohen:
OK, needs your review now
:-P
Cool
:-P
Well, for a start
sage -coverage
will not like the documentation ofsupported_actions
at all. Why do you want to create a function just to list them ? Why don't you just include in the methods, or make it a variable in the module ? (anyway you still have to split cases inorbits
in order to know what to return).
made it a variable...
Would it be possible to add a link toward GAP's documentation where all those actions are defined ?
added...
Attachment: trac_14291-rev2.patch.gz
Description changed:
---
+++
@@ -5,3 +5,4 @@
Apply
1. [attachment: trac_14291.patch](https://github.com/sagemath/sage-prod/files/10657404/trac_14291.patch.gz)
2. [attachment: 14291_reviewer.patch](https://github.com/sagemath/sage-prod/files/10657405/14291_reviewer.patch.gz)
+1. [attachment: trac_14291-rev2.patch](https://github.com/sagemath/sage-prod/files/10657406/trac_14291-rev2.patch.gz)
Some small modifications to the documentation. Besides this :
1) What would you think of making supported_actions
a variable of the module itself ? And what of making it a hidden variable ?
2) What would you think of sorting the input when it represents a set ?.. GAP's error message when it is fed with an unsorted list is not that clear :
Error, OnSets: <set> must be a set (not a list (plain,cyc,nsort,imm))
I will do that if you agree with it.
Nathann
Replying to @nathanncohen:
Some small modifications to the documentation. Besides this :
1) What would you think of making
supported_actions
a variable of the module itself ? And what of making it a hidden variable ?
The current setup allows it to be extended by the user. One can install via gap.eval()
a GAP function, say, "OnBlah"
, and then use it. You can't do this with a module variable.
2) What would you think of sorting the input when it represents a set ?.. GAP's error message when it is fed with an unsorted list is not that clear :
Error, OnSets: <set> must be a set (not a list (plain,cyc,nsort,imm))
I will do that if you agree with it.
sure this can be done as you prefer. However, there is a more serious issue with self.action
:
sage: G = PermutationGroup([ [('c','d')], [('a','c')] ])
sage: xx=G.orbit(('a','c'),"OnPairs")
sage: G.action(xx,"OnPairs")
---------------------------------------------------------------------------
RuntimeError Traceback (most recent call last)
<ipython-input-4-540be1338037> in <module>()
----> 1 G.action(xx,"OnPairs")
...
Indeed, _domain_to_gap[x]
needs to be applied onto such orbits. I am thinking that one should have recursive function version of
_domain_to_gap[x]
and of _domain_from_gap[x]
to deal with things like sets, sets of sets, etc in one go rather
than call them explicitly.
One can also (or instead) attach such a pair of functions to each action in supported_actions
to do this rewriting.
The current setup allows it to be extended by the user. One can install via
gap.eval()
a GAP function, say,"OnBlah"
, and then use it. You can't do this with a module variable.
Well, if a action is being used that is not already in the source code, then there is no way for Sage to guess how to translate the result before returning it, is there ?
Otherwise we could just get rid of this list, cross our fingers when GAP is fed with something we ha not thought of, as it would raise an Exception in the worst case ?..
sure this can be done as you prefer. However, there is a more serious issue with
self.action
:
Arg. Right :-/
Indeed,
_domain_to_gap[x]
needs to be applied onto such orbits. I am thinking that one should have recursive function version of_domain_to_gap[x]
and of_domain_from_gap[x]
to deal with things like sets, sets of sets, etc in one go rather than call them explicitly.One can also (or instead) attach such a pair of functions to each action in
supported_actions
to do this rewriting.
Hmmmm... I don't like it very much to be honest... In these situations I think that a bit of code duplication is better than a weird generic way to handle it.
Nathann
I just added a new patch (to be applied on top of the rest) that solves these issues. Please have a look if you like it. (It still needs to be cleaned a bit, and more tests ought to be added). It doesn't use the supported_actions
list.
HMmmmmmmmmm :-/
I'm sorry to say this because I like that code, but I just fixed doctests in homology/simplicial_complex where an automorphism group is defined over the elements of a simplicial complex... And I am afraid that you will find both 'a', 'b', and ['a','b'] as elements of the domain :-/
Nathann
Replying to @nathanncohen:
HMmmmmmmmmm
:-/
I'm sorry to say this because I like that code, but I just fixed doctests in homology/simplicial_complex where an automorphism group is defined over the elements of a simplicial complex... And I am afraid that you will find both 'a', 'b', and ['a','b'] as elements of the domain
:-/
Well, this is trivial to fix, just swap the actions in try/except
blocks in dom_to_gap
internal functions.
By the way, why would one keep several actions in case of simplicial complexes, on letters and on pairs, etc? This is akin to keeping actions on vertices and edges in case of automorphisms of (simple) graphs, right? Was that a poor design in the first place? Besides, this seems to be inefficient to keep permutations in dictionaries.
Nathann
Attachment: ducktype_design.patch.gz
OK, updated as I mentioned in my previous comment, with more examples added.
Helloooooooooooooo !!!
Well, this does not solve the problem either Dima. In case of doubt between an element (a,b,c) and the list of elements (a,b,c) it will return the ELEMENT (a,b,c), but it it computes the orbit of a which happens to be (a,b,c) then returning an ELEMENT (a,b,c) instead of the list (a,b,c) is a mistake too :-/
Nathann
Replying to @nathanncohen:
Helloooooooooooooo !!!
Well, this does not solve the problem either Dima. In case of doubt between an element (a,b,c) and the list of elements (a,b,c) it will return the ELEMENT (a,b,c), but it it computes the orbit of a which happens to be (a,b,c) then returning an ELEMENT (a,b,c) instead of the list (a,b,c) is a mistake too
:-/
This does not seem to present a problem, as the action of the group is the same (trivial).
But the real problem is with tuples vs sets. E.g. if your domain has tuples, it will not be possible to compute the action on subsets.
Can't you typify the domain elements somehow, so that they are recognised as atoms without this kind of problem? (Or mangle them by some other means...)
Can't you typify the domain elements somehow, so that they are recognised as atoms without this kind of problem? (Or mangle them by some other means...)
Hmmmmmmmmm.... I have no idea how, an I would hate to have to use the Parent/Element stuff to do that :-P
Well, I guess the best is to do as you first did and to split according to the value of action
.
By the way, I noticed in the code source of Graph.is_edge_transitive
a trick we could use there :
"OrbitLength("+str(A._gap_())+",Set(" + str(e) + "),OnSets);"
If we wrap the lists with a Set, then GAP itself reorders them and there is nothing to fear when giving sets at Sage level :-)
Nathann
Replying to @nathanncohen:
Can't you typify the domain elements somehow, so that they are recognised as atoms without this kind of problem? (Or mangle them by some other means...)
Hmmmmmmmmm.... I have no idea how, an I would hate to have to use the Parent/Element stuff to do that
:-P
Well, I guess the best is to do as you first did and to split according to the value of
action
.
this is too ugly, uglier than using a class, or whatever. Actually, I think it is simply wrong to let groups act on some totally unstructured arbitrary sh*t, and this is exactly what happens right now with allowing arbitrary domain elements, for which any relation to the original domain is lost.
Say, if the domain of a group is {1,2,3,4,{1,2},{2,3}}, the very notion of the orbit of {1,2} is becoming ambiguous, as in a sane world {1,2} is a subset of {1,2,3,4}, and not a random label.
Dima
Yoooooooooooo !
this is too ugly, uglier than using a class, or whatever. Actually, I think it is simply wrong to let groups act on some totally unstructured arbitrary sh*t, and this is exactly what happens right now with allowing arbitrary domain elements, for which any relation to the original domain is lost.
Ahahaha. Deal. Do I remove all support for labels on edges and vertices from graphs ? I am sooooooooooo eager to :-P
Say, if the domain of a group is {1,2,3,4,{1,2},{2,3}}, the very notion of the orbit of {1,2} is becoming ambiguous, as in a sane world {1,2} is a subset of {1,2,3,4}, and not a random label.
Well, in Sage however it is not ambiguous :
g.orbit(Set([1,2]),action="OnPoints")
g.orbit(Set([1,2]),action="OnSets")
Nathann
Replying to @nathanncohen:
Yoooooooooooo !
this is too ugly, uglier than using a class, or whatever. Actually, I think it is simply wrong to let groups act on some totally unstructured arbitrary sh*t, and this is exactly what happens right now with allowing arbitrary domain elements, for which any relation to the original domain is lost.
Ahahaha. Deal. Do I remove all support for labels on edges and vertices from graphs ? I am sooooooooooo eager to
:-P
I don't think this is relevant. Here we have an example of a group acting on triples, and this is a kind of "primitive" action, all the other actions originate from it.
Anyhow, there is a hack which might fix all our sorrows: namely, add an extra level of () to the "most primitive" elements of the
domain. I.e. if instead of {1,2,3,4,{1,2},{2,3}} there was a domain {{1},{2},{3},{4},{1,2},{2,3}}
then the ambiguity does not arise, for {1,2} and {{1},{2}}
are different things now.
Dima
Say, if the domain of a group is {1,2,3,4,{1,2},{2,3}}, the very notion of the orbit of {1,2} is becoming ambiguous, as in a sane world {1,2} is a subset of {1,2,3,4}, and not a random label.
Well, in Sage however it is not ambiguous :
g.orbit(Set([1,2]),action="OnPoints") g.orbit(Set([1,2]),action="OnSets")
Nathann
I don't think this is relevant. Here we have an example of a group acting on triples, and this is a kind of "primitive" action, all the other actions originate from it.
Anyhow, there is a hack which might fix all our sorrows: namely, add an extra level of () to the "most primitive" elements of the domain. I.e. if instead of {1,2,3,4,{1,2},{2,3}} there was a domain
{{1},{2},{3},{4},{1,2},{2,3}}
then the ambiguity does not arise, for {1,2} and{{1},{2}}
are different things now.
Come on Dima. Let's just rewrite the method as it was previously... If the action is on points we know what to do, if it is on something else we also know what to do, case by case.
It's not worth adding another layer just for that ...
Nathann
Replying to @nathanncohen:
I don't think this is relevant. Here we have an example of a group acting on triples, and this is a kind of "primitive" action, all the other actions originate from it.
Anyhow, there is a hack which might fix all our sorrows: namely, add an extra level of () to the "most primitive" elements of the domain. I.e. if instead of {1,2,3,4,{1,2},{2,3}} there was a domain
{{1},{2},{3},{4},{1,2},{2,3}}
then the ambiguity does not arise, for {1,2} and{{1},{2}}
are different things now.Come on Dima. Let's just rewrite the method as it was previously... If the action is on points we know what to do, if it is on something else we also know what to do, case by case.
It's not worth adding another layer just for that ...
it's for the general sanity of the setup. Let me post on sage-devel asking opinions, as I do think that this is a fundamental semantic problem of the design.
Needless to say, if I am declared insane there, then I would happily review whatever patch you would be willing to put here :)
Dima
Nathann
Needless to say, if I am declared insane there, then I would happily review whatever patch you would be willing to put here :)
It is very kind of you but my patch for this ticket has been written for a while already. It has been delayed because you wanted to add more than I needed :-P
Nathann
Replying to @nathanncohen:
Needless to say, if I am declared insane there, then I would happily review whatever patch you would be willing to put here :)
It is very kind of you but my patch for this ticket has been written for a while already. It has been delayed because you wanted to add more than I needed
:-P
The curiosity of the reviewer is sacred, don't you think so? :-)
Besides, it's easy to backport the patch here directly into the smallgraphs patch it came from, and put this ticket on hold.
Dima
Nathann
The curiosity of the reviewer is sacred, don't you think so? :-)
It is.
Besides, it's easy to backport the patch here directly into the smallgraphs patch it came from, and put this ticket on hold.
Oh, you are worried about #14283 ? I really don't need it, I write this kind of patches when I spent too much time thinking and cannot do anything useful anymore with my head. So I try to build a graph. But if it is not merged in the next ten months I do not mind at all. It is written somewhere, it is reviewed, my part has been done :-)
But still, I would love this patch to be available in Sage. And #14319 even more :-)
Nathann
@cached_method
must not return lists, but only immutable things
sage: S3.orbit(3)
[3, 1, 2]
sage: type(_)
list
Just return a tuple.
It would be nice if orbit were smarter about the action type and make the output a set/tuple if necessary. For example, desirable behaviour would be
sage: S3.orbit(3) # in domain, use OnPoints
(1, 2, 3)
sage: S3.orbit((1,2)) # not in domain, a tuple, use OnTuples
((1, 2), (2, 3), (2, 1), (3, 1), (1, 3), (3, 2))
sage: S3.orbit({1,2}) # not in domain, a set, use OnSets
({1, 2}, {2, 3}, {1, 3})
Replying to @vbraun:
@cached_method
must not return lists, but only immutable things
OK, this should be easy.
- It would be nice if orbit were smarter about the action type and make the output a set/tuple if necessary.
sure, this is also easy with the design I advocate (duck-typing). Given that the other ticket author is not happy with it, there are options (in no particular order):
I proceed with my design, and include a workaround that does the rewriting of the domain ("boxing" things up), before doing the orbit and action computation. (Which is not very efficient, as it essentially involves recreating group domain and its GAP counterparts)
We convince the other author that I am right, and drop the workaround.
Somebody (not me) designs a G-set type/class framework to handle the issue.
You convince me that I am wrong, and it's perfectly kosher to have domains like plain tuples (1,2,{1,2},...), and creating intransitive actions is more work than just appending permutations.
- We convince the other author that I am right, and drop the workaround.
Come on Dima, you do understand that on some instances your patch could return bad answers, do you ?
What's the problem with gessing the "depth" of input/output according to the value of action
?
Nathann
Replying to @nathanncohen:
- We convince the other author that I am right, and drop the workaround.
Come on Dima, you do understand that on some instances your patch could return bad answers, do you ?
On wrong instances, yes. On instances like (1,2,{1,2},...), which make no sense, because they lead to horrible bugs. Here is how.
Take, say, directed 3-cycle, and label its vertices, in the cyclic order, 1, 2, (1,2). So you get G=Z_3, the automorphism group of this digraph, acting on the domain V=(1,2,(1,2)). Next, ask for the orbit of the arc (1,2) of the digraph under G. OK, fine, it is A=((1,2),(2,(1,2)),((1,2),1). Now, note that the intersection of V and A equals {(1,2)}. The intersection of two distinct orbits of a group is not empty...
Would Évariste Galois raise from his grave and chase the designer of this? :–)
Edit. Or implement the action on tuples of tuples, and ask for the orbit of ((1,2),(1,2)).
What's the problem with gessing the "depth" of input/output according to the value of
action
?
this won't fix the bug above.
Dima
Nathann
Take, say, directed 3-cycle, and label its vertices, in the cyclic order, 1, 2, (1,2). So you get G=Z_3, the automorphism group of this digraph, acting on the domain V=(1,2,(1,2)). Next, ask for the orbit of the arc (1,2) of the digraph under G. OK, fine, it is A=((1,2),(2,(1,2)),((1,2),1). Now, note that the intersection of V and A equals {(1,2)}. The intersection of two distinct orbits of a group is not empty...
Ahahaahah. Yeah, it looks like you need to guess somewhere that the element (1,2) is not equal to the set containing the two elements 1 and 2 :-)
Would Évariste Galois raise from his grave and chase the designer of this? :–)
If he does I will help !
What's the problem with gessing the "depth" of input/output according to the value of
action
?this won't fix the bug above.
That's true. But the two problems are totally unrelated, though ! In the current state of things, guessing the value of action as Volker said and translating input/output according to what is what we can do best. Then you will have to hand your beloved groups over to the combinat guys who will make a hell out of it, and I hope that everything I need from groups will be written before they make this impossible to use with their parent/element framework.
Nathann
Replying to @nathanncohen: [...]
Ahahaahah. Yeah, it looks like you need to guess somewhere that the element (1,2) is not equal to the set containing the two elements 1 and 2
:-)
easy, as I said: just replace domain elements 1 and 2 by (1) and (2), and everything all of a sudden works. The alternative is to give yourself over to the category theory and practice...
Would Évariste Galois raise from his grave and chase the designer of this? :–)
If he does I will help !
I won't bet on this, for he might get hold of more powerful weapon than he used during that unfortunate duel, you know :–)
What's the problem with gessing the "depth" of input/output according to the value of
action
?this won't fix the bug above.
That's true. But the two problems are totally unrelated, though !
of course they are related, as the code in question works fine on the sane inputs, and there is nothing to fix then.
easy, as I said: just replace domain elements 1 and 2 by (1) and (2), and everything all of a sudden works. The alternative is to give yourself over to the category theory and practice...
Yeah but it's the same problem then. My vertices are not the elements of the automorphism group. That's a problem.
Nathann
Replying to @nathanncohen:
easy, as I said: just replace domain elements 1 and 2 by (1) and (2), and everything all of a sudden works. The alternative is to give yourself over to the category theory and practice...
Yeah but it's the same problem then. My vertices are not the elements of the automorphism group. That's a problem.
sorry, I don't understand. I never suggested labeling anything by group elements.
Nathann
You can also solve your problem above by saying that the intersection of an orbit of a vertex and the orbit of an edge is empty. And you can guess that because you computed the first with action="OnPoints"
and the second with action="OnSets"
.
Nathann
sorry, I don't understand. I never suggested labeling anything by group elements.
Then how do you apply your problem to this patch ? How do we solve this ? I claim that there is nothing wrong going on for as long as there is an "action" argument somewhere which defines how output and input are to be interpreted.
Nathann
Here's a new patch for what this ticket initially addressed, after the looooooong discussion on sage-devel [1]. #14283 and (more importantly) #14319 depend on this ticket !
Nathann
[1] https://groups.google.com/d/topic/sage-devel/LRZULwy5KYI/discussion
Description changed:
---
+++
@@ -2,7 +2,10 @@
And a reviewer patch adding more stuff.
-Apply
+Apply :
+1. [attachment: trac_14291-v2.patch](https://github.com/sagemath/sage-prod/files/10657408/trac_14291-v2.patch.gz)
+
+Do *NOT* apply the former implementation:
1. [attachment: trac_14291.patch](https://github.com/sagemath/sage-prod/files/10657404/trac_14291.patch.gz)
2. [attachment: 14291_reviewer.patch](https://github.com/sagemath/sage-prod/files/10657405/14291_reviewer.patch.gz)
1. [attachment: trac_14291-rev2.patch](https://github.com/sagemath/sage-prod/files/10657406/trac_14291-rev2.patch.gz)
Apply trac_14291-v2.patch
Attachment: trac_14291-v2.patch.gz
Can we make orbit
return a tuple intstead of a list? As I mentioned before, @cached_method
s must not return mutable containers.
Changed author from Nathann Cohen to Nathann Cohen, Volker Braun
Reviewer: Volker Braun
Description changed:
---
+++
@@ -1,11 +1,6 @@
A small patch to let us compute the orbits of sets and tuples by exposing it from GAP.
-
-And a reviewer patch adding more stuff.
Apply :
1. [attachment: trac_14291-v2.patch](https://github.com/sagemath/sage-prod/files/10657408/trac_14291-v2.patch.gz)
+2. [attachment: trac_14291_reviewer.patch](https://github.com/sagemath/sage-prod/files/10657410/trac_14291_reviewer.patch.gz)
-Do *NOT* apply the former implementation:
-1. [attachment: trac_14291.patch](https://github.com/sagemath/sage-prod/files/10657404/trac_14291.patch.gz)
-2. [attachment: 14291_reviewer.patch](https://github.com/sagemath/sage-prod/files/10657405/14291_reviewer.patch.gz)
-1. [attachment: trac_14291-rev2.patch](https://github.com/sagemath/sage-prod/files/10657406/trac_14291-rev2.patch.gz)
I've cleaned up some stuff and beautified the output containers (as we talked about before):
sage: S3 = groups.permutation.Symmetric(3)
sage: S3.orbit((1,2), action = "OnSets")
({1, 2}, {2, 3}, {1, 3})
sage: S3.orbit((1,2), action = "OnTuples")
((1, 2), (2, 3), (2, 1), (3, 1), (1, 3), (3, 2))
I'm fine with everything else, so if you agree with the reviewer patch feel free to set it to positive review.
For the patchbot: Apply trac_14291-v2.patch, trac_14291_reviewer.patch
Helloooooooooooooooo !!!
There is a "permutatino" somewhere. Could you also replace x = sorted(x)
with `x.sort()
?
This being said, your patch does not apply on my version of Sage... But I still use beta1, perhaps that's the reason why.
Nathann
A small patch to let us compute the orbits of sets and tuples by exposing it from GAP.
Apply :
CC: @dimpase
Component: group theory
Author: Nathann Cohen, Volker Braun
Reviewer: Volker Braun
Merged: sage-5.10.beta0
Issue created by migration from https://trac.sagemath.org/ticket/14291