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 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
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:
(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
(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 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: 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
(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 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 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
(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 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 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
> +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.
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
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
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.
[sage-devel] Re: Function for subposet search
Hello ! 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 A.hasse_diagram().transitive_closure().subgraph_search(B.hasse_diagram().transitive_closure()) Case 2: You say that a poset B is a subposet of a poset A if the hasse dagram of B is a subgraph of the hasse diagram of A. In this case you can do: A.hasse_diagram().subgraph_search(B.hasse_diagram(),induced=True) Thus: both situations can be solved with digraph search though I would expect it to be slightly suboptimal. I do not know by how far. 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. Note that the DiGraph.subgraph_search* methods can do more: - DiGraph.subgraph_search gives you a copy of a digraph B in a digraph A (an induced copy if you ask for it - DiGraph.subgraph_search_count counts the number of copies - DiGraph.subgraph_search_iterator iterates over all *labelled* copies (there are 5! occurrences of the complete graph K5 in K5) If not, is it because there is no good algorithm for it, or because it is > not implemented? > I wouldn't say that the algorithm for subgraph search is "good" (you have to enumerate a lot of things that will turn out to be useless for some reason), but well... The current implementation is somehow well-made (in Cython and everything) and one can spend time to add 1000 ways to reduce the search space if needed... It is a hard problem, and it shows in the amount of enumeration it requires :-) 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.
