Opened 5 years ago

Closed 5 years ago

#16892 closed enhancement (fixed)

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

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-6.4
Component: combinatorics Keywords:
Cc: ncohen Merged in:
Authors: Jori Mäntysalo Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: 346ef0e (Commits) Commit: 346ef0e676727cd287f58b978ac1a9e4d82a09e9
Dependencies: #16909 Stopgaps:

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?

Change History (44)

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

  • Commit set to f13f2385d2b79adad5dae8282162d776bb8114bd
  • Status changed from new to needs_review

New commits:

f13f238Added 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: 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: 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: 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: 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?

Yepyep, you can ask !

Nathann

comment:15 follow-up: 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: 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: 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: 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: 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: Changed 5 years ago by jmantysalo

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

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

  • Commit changed from f13f2385d2b79adad5dae8282162d776bb8114bd to 160d8a5cdd251d13619e1291542cdd35a3f57ba2

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

160d8a5Added two simple wrapper functions.

comment:27 follow-up: 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:

d4c0285Version 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:

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

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

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:

f1d0174Moved 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:

ad47132trac #16909: transitive_closure() and mutable graphs
346ef0eMerge 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: 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

comment:42 Changed 5 years ago by ncohen

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