Re: [sage-devel] Re: Function for subposet search
(At the super market) Doesn't it work better if you also do induced=true for the transitive closure thing too ? Nathann On Wednesday, August 27, 2014, Jori Mantysalo jori.mantys...@uta.fi wrote: On Fri, 22 Aug 2014, Nathann Cohen wrote: Does Sage has a function to check if poset A contains a subposet isomorphic to subposet B? Not... exactly. There is no Poset method that does that, but there is a DiGraph method that does that. But then, it depends on what you call a subposet of a poset. It seems that neither definition is not what I was thinking. In principle the function I want could be done with something like def has_isomorphic_subposet(A, B): for x in Subsets(A.list()): if A.subposet(x).is_isomorphic(B): return True return False which is of course extremely slow. In this definition i.e. lattice N_5 contains 4-element diamond lattice. -- Jori Mäntysalo -- You received this message because you are subscribed to a topic in the Google Groups sage-devel group. To unsubscribe from this topic, visit https://groups.google.com/d/ topic/sage-devel/0kqw7HPV088/unsubscribe. To unsubscribe from this group and all its topics, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Function for subposet search
(sitting in the living room) Yes, you do need this induced=True otherwise the chain contains all other (smaller) posets :-P Sorry 'bout that. And it should be much faster than the listing from your trac ticket (which you can close if your problem is solved, or recycle into a ticket to implement the feature) Nathann On 28 August 2014 10:22, Nathann Cohen nathann.co...@gmail.com wrote: (At the super market) Doesn't it work better if you also do induced=true for the transitive closure thing too ? Nathann On Wednesday, August 27, 2014, Jori Mantysalo jori.mantys...@uta.fi wrote: On Fri, 22 Aug 2014, Nathann Cohen wrote: Does Sage has a function to check if poset A contains a subposet isomorphic to subposet B? Not... exactly. There is no Poset method that does that, but there is a DiGraph method that does that. But then, it depends on what you call a subposet of a poset. It seems that neither definition is not what I was thinking. In principle the function I want could be done with something like def has_isomorphic_subposet(A, B): for x in Subsets(A.list()): if A.subposet(x).is_isomorphic(B): return True return False which is of course extremely slow. In this definition i.e. lattice N_5 contains 4-element diamond lattice. -- Jori Mäntysalo -- You received this message because you are subscribed to a topic in the Google Groups sage-devel group. To unsubscribe from this topic, visit https://groups.google.com/d/topic/sage-devel/0kqw7HPV088/unsubscribe. To unsubscribe from this group and all its topics, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Function for subposet search
On Thu, 28 Aug 2014, Nathann Cohen wrote: Yes, you do need this induced=True otherwise the chain contains all other (smaller) posets :-P But def has_isomorphic_subposet(A, B): for x in Subsets(A.list(), k=B.cardinality()): if A.subposet(x).is_isomorphic(B): return True return False def has_isomorphic_subposet2(A, B): if A.hasse_diagram().subgraph_search(B.hasse_diagram(),induced=True) is None: return False return True Diamond=Poset( ([1,2,3,4], [[1,2],[1,3],[2,4],[3,4]]) ) N5=Poset( ([1,2,3,4,5], [[1,2],[1,3],[3,4],[2,5],[4,5]]) ) print has_isomorphic_subposet(N5, Diamond) print has_isomorphic_subposet2(N5, Diamond) outputs True False And it should be much faster than the listing from your trac ticket (which you can close if your problem is solved, or recycle into a ticket to implement the feature) If there is an easy solution for this, I can make a function to finite posets class. Hence I'm not going to close ticket yet. -- Jori Mäntysalo -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Function for subposet search
(In the forest) With the transitive closure ! The transitive closure AND induced= true. Append .transitive_closure() after each call to hasse_digram and it should work ! Nathann On Thursday, August 28, 2014, Jori Mantysalo jori.mantys...@uta.fi wrote: On Thu, 28 Aug 2014, Nathann Cohen wrote: Yes, you do need this induced=True otherwise the chain contains all other (smaller) posets :-P But def has_isomorphic_subposet(A, B): for x in Subsets(A.list(), k=B.cardinality()): if A.subposet(x).is_isomorphic(B): return True return False def has_isomorphic_subposet2(A, B): if A.hasse_diagram().subgraph_search(B.hasse_diagram(),induced=True) is None: return False return True Diamond=Poset( ([1,2,3,4], [[1,2],[1,3],[2,4],[3,4]]) ) N5=Poset( ([1,2,3,4,5], [[1,2],[1,3],[3,4],[2,5],[4,5]]) ) print has_isomorphic_subposet(N5, Diamond) print has_isomorphic_subposet2(N5, Diamond) outputs True False And it should be much faster than the listing from your trac ticket (which you can close if your problem is solved, or recycle into a ticket to implement the feature) If there is an easy solution for this, I can make a function to finite posets class. Hence I'm not going to close ticket yet. -- Jori Mäntysalo -- You received this message because you are subscribed to a topic in the Google Groups sage-devel group. To unsubscribe from this topic, visit https://groups.google.com/d/ topic/sage-devel/0kqw7HPV088/unsubscribe. To unsubscribe from this group and all its topics, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Function for subposet search
On Thu, 28 Aug 2014, Nathann Cohen wrote: (In the forest) With the transitive closure ! The transitive closure AND induced= true. Now it seems to work! I'll continue testing, and add a function to sage. Is it pine forest? In any case, have a nice walk. -- Jori Mäntysalo (mänty=pine, salo=forest :=) ) -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Function for subposet search
Yooo !!! Now it seems to work! I'll continue testing, and add a function to sage. It is meant to be equivalent, so it would be a bad news if they did not give the same answer :-P Is it pine forest? In any case, have a nice walk. Not a pine forest, but a good forest indeed. It had trees and everything, and I found good places for my hammock :-P Nathann -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Function for subposet search
On Thu, 28 Aug 2014, Nathann Cohen wrote: Now it seems to work! I'll continue testing, and add a function to sage. It is meant to be equivalent, so it would be a bad news if they did not give the same answer :-P As a side note of testing: Docs for is_modular() reference to the wikipedia article saying Every non-modular lattice contains a copy of N5 as a sublattice. However LatticePoset(Poset( ([0,1,2,3,4,5], [[0, 1], [0, 3], [1, 2], [1, 4], [2, 5], [3, 4], [4, 5]]) )).is_modular() returns True. Is this an error on Sage, or have I understood something wrong? -- Jori Mäntysalo -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Function for subposet search
On Thu, 28 Aug 2014, Jori Mantysalo wrote: As a side note of testing: Docs for is_modular() reference to the wikipedia Uh, forget. If poset is also lattice and has subposet that is also lattice, still subposet might not be sublattice. -- Jori Mäntysalo -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Function for subposet search
On Fri, 22 Aug 2014, Nathann Cohen wrote: Does Sage has a function to check if poset A contains a subposet isomorphic to subposet B? Not... exactly. There is no Poset method that does that, but there is a DiGraph method that does that. But then, it depends on what you call a subposet of a poset. It seems that neither definition is not what I was thinking. In principle the function I want could be done with something like def has_isomorphic_subposet(A, B): for x in Subsets(A.list()): if A.subposet(x).is_isomorphic(B): return True return False which is of course extremely slow. In this definition i.e. lattice N_5 contains 4-element diamond lattice. -- Jori Mäntysalo -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Function for subposet search
On Fri, 22 Aug 2014, Nathann Cohen wrote: Does Sage has a function to check if poset A contains a subposet isomorphic to subposet B? Not... exactly. There is no Poset method that does that, but there is a DiGraph method that does that. But then, it depends on what you call a subposet of a poset. Case 1: You say that a poset B is a subposet of a poset A if there is a set of points in A that induce a poset isomorphic to B. In this case, you want to ensure that the transitive closure of A contains the transitive closure of B and your problem is solved by I mean this one. A.hasse_diagram().transitive_closure().subgraph_search(B.hasse_diagram().tr ansitive_closure()) Seems to work, thanks. If you need this feature, however (and as you wrote to sage-devel, not to sage-support :-P) it would be cool if you could write a ticket to implement all this at poset-level. It would just call the digraph routines, but it needs to be documented and interfaced properly. OK. First question is name of the function. I would say A.has_subposet(), but should it be A.has_isomorphic_subposet() or even B.is_subposet()? Next, short description. There are three different style used for True/False -functions: - Returns True if the poset has a unique minimal element. - Returns True if the poset is totally ordered, and False otherwise. - Returns whether f is an EL labelling of self (Last one also misses a dot.) Is there some style manual? And after that I should see logic behind posets.py vs. hasse_diagram.py at .../combinat/posets/. Source for last one says This should not be called directly, use Poset instead; all type checking happens there. However, I think that there is nothing to check for? Maybe I'll start with .is_lattice(); now there are is_meet_semilattice() and is_join_semilattice() but not ready function to check for poset being lattice. (And there is, besides is_top() and is_bottom(), also is_bounded().) -- Jori Mäntysalo -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Function for subposet search
Helloo !! OK. First question is name of the function. I would say A.has_subposet(), but should it be A.has_isomorphic_subposet() or even B.is_subposet()? HMmmm.. Well, do you only want to answer whether there is a copy of B in A, or also give that copy to the user ? When I picked a name for subgraph_search, I added the _search to make sure the users understands that there is a search going on, and that we do not just check that the vertices of B are also vertices of A, and that the relations in B induce the same relations in A. There is a search going on, and I wanted the users to be aware of that. Your has_isomorphic_subposet does exactly that, and I actually prefer your name. The thing is : do you want to give the isomorphic copy to the user or not ? Having this copy may be very useful ! Note that I often use the (controversed) syntax A.has_isomorphic_subposet(B,certificate=True) which would return either (False, None) or (True, copy_of_B_in_A) When certificate=False, the function is plain boolean. That's up to you ! Next, short description. There are three different style used for True/False -functions: - Returns True if the poset has a unique minimal element. - Returns True if the poset is totally ordered, and False otherwise. - Returns whether f is an EL labelling of self (Last one also misses a dot.) Is there some style manual? I do not know if there is a prefered style. And after that I should see logic behind posets.py vs. hasse_diagram.py at .../combinat/posets/. Source for last one says This should not be called directly, use Poset instead; all type checking happens there. However, I think that there is nothing to check for? Maybe I'll start with .is_lattice(); now there are is_meet_semilattice() and is_join_semilattice() but not ready function to check for poset being lattice. (And there is, besides is_top() and is_bottom(), also is_bounded().) As I told you in answer to your private message, there are many things to fix/change in Poset. With this in mind, feel free to change things when it just not look right -- it probably isn't. Nathann -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Function for subposet search
Hey, OK. First question is name of the function. I would say A.has_subposet(), but should it be A.has_isomorphic_subposet() or even B.is_subposet()? +1 to doing this; that way it becomes easier (more natural) to check for things like 2+2 freeness. My first thought is for B.is_subposet(A). Next, short description. There are three different style used for True/False -functions: - Returns True if the poset has a unique minimal element. - Returns True if the poset is totally ordered, and False otherwise. - Returns whether f is an EL labelling of self (Last one also misses a dot.) Is there some style manual? I'd take the middle one (but starting with Return) . I forget the link off-hand, but there is a place in the Sage doc about this. Best, Travis -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Function for subposet search
+1 to doing this; that way it becomes easier (more natural) to check for things like 2+2 freeness. My first thought is for B.is_subposet(A). In Graph there is a G.is_subgraph(H) that just checks that the edges of H are edges of G (and that points of H are point of G). This function is of course much faster. To avoid such a misunderstanding I really think that is_isomorphic_subposet clears any doubt. Or we can also change the graph side if you prefer it like that, I do not mind myself. Nathann -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
