Add is_induced_subposet

[sagetrac-csar]

Add is_induced_subposet() method to Posets to check if a subposet is an (induced) subposet of another.

CC: @kevindilks @nathanncohen @tscrim

Component: combinatorics

Keywords: posets

Author: Jori Mäntysalo

Branch/Commit: c7db822

Reviewer: Travis Scrimshaw, Nathann Cohen

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

[sagetrac-csar]

Branch: u/csar/ticket/15875

[sagetrac-csar]

comment:2

I'm not positive this works. I think I've stumbled across an example where you have equality of the results of hasse_diagram(), but not of _hasse_diagram.

[sagetrac-csar]

Commit: 7ecc981

[jm58660]

comment:5

You don't have to say Poset(DiGraph({1:[2,3],2:[4],3:[4]})), just Poset({1:[2,3],2:[4],3:[4]}).

See also #16892, it relates to this one. I think that you can look the code of it for you.

[jm58660]

comment:6

How are other "containing"-functions made? For a poset A to be a subposet of B it should be that for every cover relation u, v in A there is u' < v' in B, where u == u' (and v == v'). How to define ==, for example if u is int(42)and u' is Integer(42)?

[jm58660]

comment:8

At least

g1 = DiGraph({13:[14]})
g2 = DiGraph({13r:[14r]})
g1.is_subgraph(g2), g2.is_subgraph(g1)

outputs (True, True). Is there examples of sub* function with different behaviour? If not, then also is_subposet() should be like is_subgraph(). CC to ncohen for this question.

[nathanncohen]

comment:9

Since a long time, graphs have been converting all 'integer' labels into 'int'. That was long before I came. I expect that the reason is that you "pay for labels" when you deal with graphs, and that was probably a way to avoid that.

[jm58660]

comment:10

Replying to @nathanncohen:

Since a long time, graphs have been converting all 'integer' labels into 'int'. That was long before I came. I expect that the reason is that you "pay for labels" when you deal with graphs, and that was probably a way to avoid that.

This was an answer to different question... (on sage-devel). To clarify, here is another example of is_sub*-function:

r1=2.0-1.0
r2=3.0-1.0
i1=1
i2=2
{i1, i2}.issubset({r1, r2})

This also outputs True. Hence it seems that Poset({r1:[r2]}).is_subposet(Poset({i1:[i2]})) should also return True. But I would like someone to confirm this.

[nathanncohen]

comment:11

That would be because Integer(5) == int(5) returns True, then. Would you expect them to be handled any differently by posets?

[jm58660]

comment:12

Replying to @nathanncohen:

That would be because Integer(5) == int(5) returns True, then. Would you expect them to be handled any differently by posets?

Well, no. So, in principle P.is_subposet(Q) can be implemented like set([frozenset(x) for x in P.relations()]).issubset(set([frozenset(x) for x in Q.relations()])). Or course there is better ways to do it in reality.

Is there any graph function already to wrap for this? Something about reachability in digraphs?

[nathanncohen]

comment:13

Is there any graph function already to wrap for this? Something about reachability in digraphs?

Hmmmm... I don't think so. If there was, you could probably expect the Poset (Directed Acyclic Graph) case to be much faster to solve, so it's really Poset code in the end.

Nathann

[jm58660]

comment:14

Would implementing P.is_subposet(Q) as P.hasse_diagram().is_subgraph(Q.hasse_diagram().transitive_closure()) be too slow? I am not sure if I can make faster version by manually calling digraph functions in a loop. But of course it is much faster to get False if some element of P is not an element of Q at all by first checking for that. But will transitive_closure()) eat memory?

[nathanncohen]

comment:15

Replying to @jm58660:

Would implementing P.is_subposet(Q) as P.hasse_diagram().is_subgraph(Q.hasse_diagram().transitive_closure()) be too slow?

"depends". It means a copy of Q's graph even if P is only one vertex. In other cases it will be optimal.

I am not sure if I can make faster version by manually calling digraph functions in a loop. But of course it is much faster to get False if some element of P is not an element of Q at all by first checking for that. But will transitive_closure()) eat memory?

It will eat some memory indeed, but it will be freed then. Ideally, we would need a dense representation for Q's transitive closure and a sparse representation of P. We can iterate over all edges of P, and check every time that it is an edge of Q's transitive closure.

The most costly part of it will probably be the vertex labelling.

Nathann

[jm58660]

Changed branch from u/csar/ticket/15875 to u/jmantysalo/is_subposet

[jm58660]

comment:17

Done this as an oneline-wrapper. I think that faster versions are easier to do when we already have a docstring and maybe see how this will be used.

This is intentionally left out from index of functions, as I am still waiting for #18534 to get accepted (or rejected).

---

New commits:

29ab8f2

Added a function is_subposet().

[jm58660]

Changed commit from 7ecc981 to 29ab8f2

[jm58660]

Author: Jori Mäntysalo

[jm58660]

Changed keywords from none to posets

[jm58660]

comment:60

Does not work:

P = Poset({1:[2]})
Q1 = Poset({1:[]})
Q2 = LatticePoset({1:[]})
Q1.is_induced_subposet(P), Q2.is_induced_subposet(P)

outputs (True, False).

[sagetrac-git]

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

28a3cc3

Merge branch 't/15875/is_subposet' into ind_subposet. Correction of

[sagetrac-git]

Changed commit from 9119980 to 28a3cc3

[jm58660]

comment:62

Resolved a conflict, made to work with lattices also. Should be OK now.

[nathanncohen]

comment:63

Hello Jori,

I do not understand the point of the line if not hasattr(other, 'hasse_diagram'):. Given that you call subposet and .hasse_diagram on other anyway your code will raise an exception whenever those methods are not available.

Nathann

[sagetrac-git]

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

fb6299e

Removed a test for having attribute _hasse_diagram.

[sagetrac-git]

Changed commit from 28a3cc3 to fb6299e

[jm58660]

comment:65

Replying to @nathanncohen:

I do not understand the point of the line if not hasattr(other, 'hasse_diagram'):. Given that you call subposet and .hasse_diagram on other anyway your code will raise an exception whenever those methods are not available.

As you wish, changed that.

Now P.is_induced_subposet('junk') will say AttributeError: 'str' object has no attribute '_is_facade'. A slightly confusing to a user, but should not be that hard to track the error.

(Quite many Sage functions give strange errors from wrong input... At least this won't be first one.)

[nathanncohen]

comment:66

Hello Jori,

As you seem to care about this message, I pused a commit at public/15875 that will raise a slightly more meaningful error message when the input is bad. Add it if you like it, ignore it if you do not.

The probability of users giving this function bad input would be much lower if the function you add had an 'INPUT' section explaining what exactly it expects.

Nathann

[sagetrac-git]

Changed commit from fb6299e to 4228920

[sagetrac-git]

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

4228920

Better error reporting.

[jm58660]

comment:68

Replying to @nathanncohen:

As you seem to care about this message, I pused a commit at public/15875 that will raise a slightly more meaningful error message when the input is bad. Add it if you like it, ignore it if you do not.

Thanks. Added that.

The probability of users giving this function bad input would be much lower if the function you add had an 'INPUT' section explaining what exactly it expects.

Hmm... Maybe I should go through functions and add INPUT sections.

This patch contains a non-relating line that corrects an indentation bug in dilworth_decomposition(). OK to add here?

[nathanncohen]

comment:69

Yo,

Hmm... Maybe I should go through functions and add INPUT sections.

Could you add one at least in this function that you add here?

This patch contains a non-relating line that corrects an indentation bug in dilworth_decomposition(). OK to add here?

No prob.

About the commit: [please do not change anything as it is not important], but notice that instead of adding my commit on your branch (with cherry-pick, for instance) you apparently applied the changes manually (or did something else that I cannot guess), which has as a side-effect that you became the committer+author of my changes.

Please don't change anything as it is not important, I am just giving you a side-effect of the procedure you followed to use my commit.

Nathann

[sagetrac-git]

Changed commit from 4228920 to c7db822

[sagetrac-git]

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

c7db822

Added an INPUT section to docstring.

[jm58660]

comment:71

Replying to @nathanncohen:

Hmm... Maybe I should go through functions and add INPUT sections.

Could you add one at least in this function that you add here?

Done.

About the commit: [please do not change anything as it is not important], but notice that instead of adding my commit on your branch (with cherry-pick, for instance) you apparently applied the changes manually (or did something else that I cannot guess), which has as a side-effect that you became the committer+author of my changes.

True. I'll try to remember that in the future.

[nathanncohen]

comment:72

Thanks,

Nathann

[vbraun]

Changed branch from u/jmantysalo/is_subposet to c7db822