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:  sage6.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
comment:2 Changed 5 years ago by
 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
 Commit set to f13f2385d2b79adad5dae8282162d776bb8114bd
 Status changed from new to needs_review
New commits:
f13f238  Added a (wrapper) function to posets.

comment:4 Changed 5 years ago by
 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 sagedevel 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
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 followup: ↓ 7 Changed 5 years ago by
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
Yoooooooooooooo !
But if I do
self.transitive_closure()
instead ofDiGraph(self).transitive_closure()
I getNotImplementedError: 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 followup: ↓ 9 Changed 5 years ago by
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 4element 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
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 onDiGraph
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 doublecheck 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 4element 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 oneline description of what it does. Then you can describe better the behaviour of the function.
Nathann
comment:10 Changed 5 years ago by
 Dependencies set to 16909
comment:11 followup: ↓ 12 Changed 5 years ago by
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
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 followup: ↓ 14 Changed 5 years ago by
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 sagedevel list?
comment:14 in reply to: ↑ 13 Changed 5 years ago by
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.pyshows that there are 14 functions that are just wrappers to underlying hasse_diagram function. Should this be discussed on sagedevel list?
Yepyep, you can ask !
Nathann
comment:15 followup: ↓ 16 Changed 5 years ago by
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
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 followup: ↓ 18 Changed 5 years ago by
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.pyhasse_diagram.py style, because I'm not sure about rationale behind it. If unsure, do as others...
comment:18 in reply to: ↑ 17 Changed 5 years ago by
Yo !
Ah, it is that easy to convert this to iterator. Points to python!
Now there is
antichains_iterator()
andantichains()
on posets, and also for examplelower_covers_iterator()
but notclosed_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.pyhasse_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 followup: ↓ 20 Changed 5 years ago by
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
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
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 followup: ↓ 23 Changed 5 years ago by
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 ; followup: ↓ 24 Changed 5 years ago by
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 onlyisomorphic_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 ; followup: ↓ 25 Changed 5 years ago by
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 onlyisomorphic_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
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
 Commit changed from f13f2385d2b79adad5dae8282162d776bb8114bd to 160d8a5cdd251d13619e1291542cdd35a3f57ba2
Branch pushed to git repo; I updated commit sha1. New commits:
160d8a5  Added two simple wrapper functions.

comment:27 followup: ↓ 28 Changed 5 years ago by
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
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
 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
 Dependencies changed from 16909 to #16909
comment:31 Changed 5 years ago by
 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
 Status changed from needs_work to needs_review
comment:33 Changed 5 years ago by
 Milestone changed from sagewishlist to sage6.4
comment:34 Changed 5 years ago by
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 oneline 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
 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
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
 Status changed from needs_review to needs_work
comment:38 Changed 5 years ago by
 Commit changed from f1d01742d3b0900e221b60d5e5392b386924621e to 346ef0e676727cd287f58b978ac1a9e4d82a09e9
comment:39 followup: ↓ 40 Changed 5 years ago by
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
 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
 Reviewers set to Nathann Cohen
 Status changed from needs_review to positive_review
comment:42 Changed 5 years ago by
(name again)
comment:43 Changed 5 years ago by
comment:44 Changed 5 years ago by
 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
Seems that this function is easy:
(Thanks to Nathann Cohen for this.) Needs to test this, and then just add few lines of code + documentation to Sage.