Opened 5 years ago

Closed 5 years ago

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

Reported by: Owned by: jmantysalo major sage-6.4 combinatorics ncohen Jori Mäntysalo Nathann Cohen N/A 346ef0e (Commits) 346ef0e676727cd287f58b978ac1a9e4d82a09e9 #16909

### Description

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?

### comment:1 Changed 5 years ago by jmantysalo

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.

### comment:2 Changed 5 years ago by jmantysalo

• Branch set to u/jmantysalo/function_to_check_if_a_poset_containt_a_subposet_isomorphic_to_another_poset

### comment:3 Changed 5 years ago by jmantysalo

• Status changed from new to needs_review

New commits:

 ​f13f238 `Added a (wrapper) function to posets.`

### comment:4 Changed 5 years ago by ncohen

• Status changed from needs_review to needs_work

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

### comment:5 Changed 5 years ago by ncohen

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

### comment:6 follow-up: ↓ 7 Changed 5 years ago by jmantysalo

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.

### comment:7 in reply to: ↑ 6 Changed 5 years ago by ncohen

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

### comment:8 follow-up: ↓ 9 Changed 5 years ago by jmantysalo

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."?

### comment:9 in reply to: ↑ 8 Changed 5 years ago by ncohen

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

### comment:10 Changed 5 years ago by jmantysalo

• Dependencies set to 16909

### comment:11 follow-up: ↓ 12 Changed 5 years ago by jmantysalo

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?

### comment:12 in reply to: ↑ 11 Changed 5 years ago by ncohen

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

### comment:13 follow-up: ↓ 14 Changed 5 years ago by jmantysalo

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?

### comment:14 in reply to: ↑ 13 Changed 5 years ago by ncohen

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?

Nathann

### comment:15 follow-up: ↓ 16 Changed 5 years ago by jmantysalo

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)]
```

### comment:16 in reply to: ↑ 15 Changed 5 years ago by ncohen

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

### comment:17 follow-up: ↓ 18 Changed 5 years ago by jmantysalo

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

Last edited 5 years ago by jmantysalo (previous) (diff)

### comment:18 in reply to: ↑ 17 Changed 5 years ago by ncohen

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

### comment:19 follow-up: ↓ 20 Changed 5 years ago by jmantysalo

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.

### comment:20 in reply to: ↑ 19 Changed 5 years ago by ncohen

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

### comment:21 Changed 5 years ago by jmantysalo

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.

### comment:22 follow-up: ↓ 23 Changed 5 years ago by jmantysalo

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`.

### comment:23 in reply to: ↑ 22 ; follow-up: ↓ 24 Changed 5 years ago by ncohen

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`.

It is not because you have no use for this information that you should filter them out before giving them to the users, especially when you spent time to compute them. At the very least you could add an option to remove them.

Nathann

### comment:24 in reply to: ↑ 23 ; follow-up: ↓ 25 Changed 5 years ago by jmantysalo

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`.

It is not because you have no use for this information that you should filter them out before giving them to the users, especially when you spent time to compute them. At the very least you could add an option to remove them.

I don't get it. If I leave duplicates, then user will have REAL duplicates, that have no difference at all. Function called `isomorphic_subposets` should return posets.

### comment:25 in reply to: ↑ 24 Changed 5 years ago by ncohen

Hello !

I don't get it. If I leave duplicates, then user will have REAL duplicates, that have no difference at all. Function called `isomorphic_subposets` should return posets.

I believe that it is criminal in this case to build the whole list before returning anything. To me, if you believe that this is uncompatible with the name of the function, I think that the function's name should be changed, and not the other way around.

If you try to find a chain of length 20 in a chain of length 40, the code just won't run.

Nathann

### comment:26 Changed 5 years ago by git

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

 ​160d8a5 `Added two simple wrapper functions.`

### comment:27 follow-up: ↓ 28 Changed 5 years ago by jmantysalo

I committed a version where `hasse_diagram.py` is not modified at all.

Is every possible object that can be an element of a poset comparable? If so, maybe is there some way to remove duplicates by order: Remove subset 0,2,1 and let 0,1,2 be? But this must be think more.

If it is not possible, should there be function giving also duplicates, with warning section saying something about that?

### comment:28 in reply to: ↑ 27 Changed 5 years ago by ncohen

Hello !

Is every possible object that can be an element of a poset comparable? If so, maybe is there some way to remove duplicates by order: Remove subset 0,2,1 and let 0,1,2 be? But this must be think more.

No, you cannot assume that. The points of a poset may be sets themselves, and their order with respect to `<=` is not a total order.

If it is not possible, should there be function giving also duplicates, with warning section saying something about that?

This is the way it is done in `Graph.subgraph_search_iterator`.

Nathann

### comment:29 Changed 5 years ago by git

• Commit changed from 160d8a5cdd251d13619e1291542cdd35a3f57ba2 to d4c0285a8090837f9fe3e416c77f96628a3ede58

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

 ​d4c0285 `Version with both isomorphic_subposets() and isomorphic_subposets_iterator().`

### comment:30 Changed 5 years ago by jmantysalo

• Dependencies changed from 16909 to #16909

### comment:31 Changed 5 years ago by git

• Commit changed from d4c0285a8090837f9fe3e416c77f96628a3ede58 to 87b585264681072a670c5b3e1da6cf5d5c9782ad

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

 ​87b5852 `Better documentation.`

### comment:32 Changed 5 years ago by jmantysalo

• Status changed from needs_work to needs_review

### comment:33 Changed 5 years ago by jmantysalo

• Milestone changed from sage-wishlist to sage-6.4

### comment:34 Changed 5 years ago by ncohen

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' ?

Thanks,

Nathann

### comment:35 Changed 5 years ago by git

• Commit changed from 87b585264681072a670c5b3e1da6cf5d5c9782ad to f1d01742d3b0900e221b60d5e5392b386924621e

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

 ​f1d0174 `Moved import statement to function; corrections to docs.`

### comment:36 Changed 5 years ago by ncohen

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

### comment:37 Changed 5 years ago by ncohen

• Status changed from needs_review to needs_work

### comment:38 Changed 5 years ago by git

• Commit changed from f1d01742d3b0900e221b60d5e5392b386924621e to 346ef0e676727cd287f58b978ac1a9e4d82a09e9

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`

### comment:39 follow-up: ↓ 40 Changed 5 years ago by jmantysalo

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

### comment:40 in reply to: ↑ 39 Changed 5 years ago by ncohen

• Status changed from needs_work to needs_review

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

### comment:41 Changed 5 years ago by ncohen

• Reviewers set to Nathann Cohen
• Status changed from needs_review to positive_review

(name again)

### comment:43 Changed 5 years ago by jmantysalo

• Authors set to Jori Mäntysalo

### comment:44 Changed 5 years ago by vbraun

• Branch changed from u/jmantysalo/function_to_check_if_a_poset_containt_a_subposet_isomorphic_to_another_poset to 346ef0e676727cd287f58b978ac1a9e4d82a09e9
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.