Function for subposet search

[Jori Mantysalo]

Does Sage has a function to check if poset A contains a subposet
isomorphic to subposet B?

If not, is it because there is no good algorithm for it, or because it is
not implemented?

--
Jori Mäntysalo

[Nathann Cohen]

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

 

[Jori Mantysalo]

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

[Nathann Cohen]

Helloooooooooo !!

> 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

[Travis Scrimshaw]

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

[Nathann Cohen]

> +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

[Jori Mantysalo]

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

[Nathann Cohen]

(At the super market)

Doesn't it work better if you also do induced=true for the transitive closure thing too ?

Nathann

--
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+...@googlegroups.com.
To post to this group, send email to sage-...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[Nathann Cohen]

(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

[Jori Mantysalo]

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

[Nathann Cohen]

(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

[Jori Mantysalo]

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 :=) )

[Nathann Cohen]

Yooooooooooo !!!

> 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

[Jori Mantysalo]

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

[Jori Mantysalo]

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