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 -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
