Function to check if a poset containt a subposet isomorphic to another poset

[jm58660]

It is, in principle, easy to check if poset A contains a subposet isomorphic to poset B:

def has_isomorphic_subposet(A, B):
    for x in Subsets(A.list()):
        if A.subposet(x).is_isomorphic(B):
            return True
    return False

In reality this is way too slow. Can this be made usefully fast at least in posets of size 5..10?

Depends on #16909

CC: @nathanncohen

Component: combinatorics

Author: Jori Mäntysalo

Branch/Commit: 346ef0e

Reviewer: Nathann Cohen

Issue created by migration from https://trac.sagemath.org/ticket/16892

[jm58660]

comment:1

Seems that this function is easy:

def has_isomorphic_subposet(A, B):
    if A.hasse_diagram().transitive_closure().subgraph_search(B.hasse_diagram().transitive_closure(),induced=True) is None:
        return False
    return True

(Thanks to Nathann Cohen for this.) Needs to test this, and then just add few lines of code + documentation to Sage.

[jm58660]

Branch: u/jmantysalo/function_to_check_if_a_poset_containt_a_subposet_isomorphic_to_another_poset

[jm58660]

New commits:

f13f238

Added a (wrapper) function to posets.

[jm58660]

Commit: f13f238

[nathanncohen]

comment:4

1. The function should only be defined in ONE place. If something forces you to define it twice, complain on sage-devel as it is not normal

2. All questions you asked yourself about this function should be answered in the doc. In particular, you should define what exactly is a "subposet". Ideally, you should define both version and make them both available.

Nathann

[nathanncohen]

comment:5

My first comment is totally wrong, I am sorry. I thought you were defining the function twice, once in posets.py and another time in the categories files. What you are doing is fine. Though Hasse diagrams are graph objects, and so they already have the subgraph_search functions.

Nathann

[jm58660]

comment:6

But if I do self.transitive_closure() instead of DiGraph(self).transitive_closure() I get

NotImplementedError: An immutable graph does not change name

On point 2 you are right.

[nathanncohen]

comment:7

Yoooooooooooooo !

But if I do self.transitive_closure() instead of DiGraph(self).transitive_closure() I get

NotImplementedError: An immutable graph does not change name

That's a bug. There is no reason why computing the transitive closure of a graph requires that graph to be mutable (indeed, the graph itself is not modified: its closure is returned as a completely new graph).

You can fix it by going into src/graph/generic_graph.py, and in function transitive_closure replace copy(self) with self.copy(immutable=False).

Nathann

[jm58660]

comment:8

1. Should I open a new ticket about transitive_closure? And if so, mark it as a dependency to this one? I have no idea about what to check on DiGraph class; hence, if I made a fix and you review it, it will actually be work of only one person. If I have understood correctly, idea is to have always two people looking at code.

2. About dokumentation: I already made an example on N5 containing 4-element diamond lattice. Would this be enought for documentation: "Return True if the poset contains a subposet isomorphic to other. By subposet we mean a poset containing elements with partial order induced by that of self."?

[nathanncohen]

comment:9

Hello !!

1. Should I open a new ticket about transitive_closure? And if so, mark it as a dependency to this one? I have no idea about what to check on DiGraph class; hence, if I made a fix and you review it, it will actually be work of only one person. If I have understood correctly, idea is to have always two people looking at code.

I would fix it in the same ticket given that it's a very small change, but then that's up to you if you do not feel safe fixing this yourself. It is a fairly simple change, needed because we only recently added a support for immutable graphs (graphs that cannot be modified) and so a lot of code written before is not made to handle it. It is exactly the case here, where you have to say explicitly that the copy should NOT be immutable, even if the graph itself was immutable.

If you prefer to leave others double-check it, then indeed you should open another ticket which would be a dependency of this one (only if you need that bug to be fixed in order to implement what you write here).

2. About dokumentation: I already made an example on N5 containing 4-element diamond lattice. Would this be enought for documentation: "Return True if the poset contains a subposet isomorphic to other. By subposet we mean a poset containing elements with partial order induced by that of self."?

"Induced" here seems a little too vague to me. But you could complete it with the code you used before:

"By subposet we mean tha set ``X`` of vertices such that P1.subposet(X).is_isomorphic(P2).

I really think that it would be best to implement both features at once (possibly with an optional 'induced' boolean parameter in the function you add). And it would also be nice to give the user a way to obtain the copy of P2 in P1, as they will probably want this as a certificate.

Whatever you do, the beginning of the doc of each function should be a one-line description of what it does. Then you can describe better the behaviour of the function.

Nathann

[jm58660]

Dependencies: 16909

[jm58660]

comment:11

1. As this is not urgent change, I made another ticket (16909). Of course I could also do this without another one, adding note like "After transitive_closure() is fixed, change..."

2. Yes, that is actually better phrasing.

Can 'induced' be later added with default value to True?

One more question: What is the meaning of having same documentation and examples copied to both posets.py and hasse_diagram.py? For example has_bottom() and actually most of functions?

[nathanncohen]

comment:12

Hello !

1. As this is not urgent change, I made another ticket (16909). Of course I could also do this without another one, adding note like "After transitive_closure() is fixed, change..."

I just wrote a commit and added Travis and Simon in cc. The patch is very short, so it may not take very long before it is reviewed !

Can 'induced' be later added with default value to True?

I believe that False (i.e. the transitive closure version) should be the default behaviour, I think that it is the most common definition of 'subposet'.

One more question: What is the meaning of having same documentation and examples copied to both posets.py and hasse_diagram.py? For example has_bottom() and actually most of functions?

Why exacty do you want to add a method to HasseDiagram, given that they are digraphs and that they already inherit the subgraph_search method which does exactly the same (and even a bit more as it returns the graph) ?

Nathann

[jm58660]

comment:13

As for default behaviour, I asked few mathematicians what they guess the function would do if they only know it's name.

In any case, it must be documented. Now when I think more: "having subgraph" is quite different from "having subposet", and "having sublattice" is stille one more thing.

About posets.py vs. hasse_diagram.py: Actually I don't know. Saying

fgrep 'return self._hasse_diagram.' combinat/posets/posets.py

shows that there are 14 functions that are just wrappers to underlying hasse_diagram -function. Should this be discussed on sage-devel -list?

[nathanncohen]

comment:14

Hello !

As for default behaviour, I asked few mathematicians what they guess the function would do if they only know it's name.

The current default behaviour is good, but it is what I would call "not induced". The "induced" version would be the one in which you do not have the call to transitive_closure: that's why I said that the default value of "induced" in .has_isomorphic_subposet should be false. But perhaps nobody cares about this second version.

About posets.py vs. hasse_diagram.py: Actually I don't know. Saying

fgrep 'return self._hasse_diagram.' combinat/posets/posets.py

shows that there are 14 functions that are just wrappers to underlying hasse_diagram -function. Should this be discussed on sage-devel -list?

Yepyep, you can ask !

Nathann

[jm58660]

comment:15

OK, so we have same view on default behaviour. Good. And so it is possible to make this function first and expand it later.

But I'll also check if I can make a function to get subposets. This seems to work:

def isomorphic_subposets(A, B):
    return [A.subposet(x) for x in A.hasse_diagram().transitive_closure().subgraph_search_iterator(B.hasse_diagram().transitive_closure(), induced=True)]

[nathanncohen]

comment:16

This seems to work:

def isomorphic_subposets(A, B):
    return [A.subposet(x) for x in A.hasse_diagram().transitive_closure().subgraph_search_iterator(B.hasse_diagram().transitive_closure(), induced=True)]

It does work "on the paper", but by doing this you first build the whole list of copies, then return it. And it could take a long time, in particular if the user is only looking for some specific copy. By replacing the [] with (), you turn it into a Python interator, and the list is not totally built first but only when the users wants to read more and more values.

Example:

sage: e=[x for x in NN if is_prime(x)] # will never stop

But

sage: e=(x for x in NN if is_prime(x))
sage: for p in e:
....:     print p
....:     if p>10:
....:         break
....:     
2
3
5
7
11

Nathann

[jm58660]

comment:17

Ah, it is that easy to convert this to iterator. Points to python!

Now there is antichains_iterator() and antichains() on posets, and also for example lower_covers_iterator() but not closed_interval_iterator(). Of course there might be technical reason for that.

But anyways, I can make isomorphic_subposets_iterator(other) and isomorphic_subposets(other).

E: I think I'll do it in posets.py-hasse_diagram.py -style, because I'm not sure about rationale behind it. If unsure, do as others...

[nathanncohen]

comment:18

Yo !

Ah, it is that easy to convert this to iterator. Points to python!

Now there is antichains_iterator() and antichains() on posets, and also for example lower_covers_iterator() but not closed_interval_iterator(). Of course there might be technical reason for that.

Personally I'd vote for turning them all into iterators and having only one function of each kind.

E: I think I'll do it in posets.py-hasse_diagram.py -style, because I'm not sure about rationale behind it. If unsure, do as others...

Come oooooooon. If nobody knows why it is done like that, just do as you think best ! Don't follow others who followed others themselves.

Nathann

[jm58660]

comment:19

Actually the function isomorphic_subposets I proposed gives double answers. Try with

N5 = Posets.PentagonPoset()
D = Poset({1:[2,3], 2:[4], 3:[4]})
for x in isomorphic_subposets(N5, D): print x.cover_relations()

Searching for a reason to this...

What comes to iterators: They are of course needed when handling large data. But for quite simple tests it is easier to work with plain list, sets etc.

[nathanncohen]

comment:20

Hello !

N5 = Posets.PentagonPoset()
D = Poset({1:[2,3], 2:[4], 3:[4]})
for x in isomorphic_subposets(N5, D): print x.cover_relations()

Searching for a reason to this...

Could it be because there are multiple ways to send D into N5 ?

What comes to iterators: They are of course needed when handling large data. But for quite simple tests it is easier to work with plain list, sets etc.

True. But you can build a set from an iterator if you like, while if the function returns a lot of objects you are forced to store them all whatever you use case is.

Nathann

[jm58660]

comment:21

There are 2 ways to insert D into N5. Or of course 4, if you think it somewhat unnaturally. In same way you got 2 hits with

X=Poset({0:[], 1:[]})
isomorphic_subposets(X, X)

But this doesn't sound right to me.

[jm58660]

comment:22

There is of course ways to remove duplikates from a list. However, I guess it is not possible (in reality) with iterators. Hence we must abandon isomorphic_subposets_iterator and left only isomorphic_subposets.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

d4c0285

Version with both isomorphic_subposets() and isomorphic_subposets_iterator().

[sagetrac-git]

Changed commit from 160d8a5 to d4c0285

[jm58660]

Changed dependencies from 16909 to #16909

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

87b5852

Better documentation.

[sagetrac-git]

Changed commit from d4c0285 to 87b5852

[nathanncohen]

comment:34

Hello !

A few other remarks:

• Could you only import uniq where you need it and not in the module's head ?

• The first line of doc in isomorphic_subposets_iterator is still right after the """

• The one-line descriptions that you added to the index at the top of the file are not correct (as far as I can tell, english is not my language):

"Return an iterator over the subposets isomorphic to other poset" -> to another poset ? Or 'to a given poset' ?

• Could you add an 'INPUT' section to your functions ?

Thanks,

Nathann

[sagetrac-git]

Changed commit from 87b5852 to f1d0174

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

f1d0174

Moved import statement to function; corrections to docs.

[nathanncohen]

comment:36

Hello !

This branch is good to go I guess, but it does not pass tests by itself. Could you merge this branch with the branch at #16909 ?

Nathann

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ad47132	trac #16909: transitive_closure() and mutable graphs
346ef0e	Merge branch 't/16909/public/16909' into t/16892/function_to_check_if_a_poset_containt_a_subposet_isomorphic_to_another_poset

[sagetrac-git]

Changed commit from f1d0174 to 346ef0e

[jm58660]

comment:39

Now there is commit that has both patches merged. Should I or ncohen now close #16909 as merged?

[nathanncohen]

comment:40

Now there is commit that has both patches merged. Should I or ncohen now close #16909 as merged?

Nononono: only the release manager should close the tickets, when he merges the commits into the next release. What you did was the right thing, nothing more is needed.

Nathann

[nathanncohen]

Reviewer: Nathann Cohen

[nathanncohen]

comment:42

(name again)

[jm58660]

Author: Jori Mäntysalo

[vbraun]

Changed branch from u/jmantysalo/function_to_check_if_a_poset_containt_a_subposet_isomorphic_to_another_poset to 346ef0e