Opened 7 years ago

Closed 7 years ago

#14099 closed enhancement (fixed)

Adding Method for testing avoidance in posets

Reported by: chrisjamesberg Owned by: rowland
Priority: minor Milestone: sage-5.11
Component: combinatorics Keywords: posets, days45, days49
Cc: chrisjamesberg, ahmorales, saliola, ncohen, nthiery, hivert Merged in: sage-5.11.rc0
Authors: Eric Rowland, Alejandro Morales Reviewers: Chris Berg
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #14536 Stopgaps:

Description (last modified by ncohen)

This is a test for finite posets to check if they do not have induced posets isomorphic to the union of two disjoint chains. Example 3+1 free, 2+2 free.

Apply:

Attachments (3)

poset_functionality_14099_er.patch (5.8 KB) - added by rowland 7 years ago.
poset_functionality_14099-er.patch (6.3 KB) - added by rowland 7 years ago.
trac_14099-rev.patch (1.3 KB) - added by ncohen 7 years ago.

Download all attachments as: .zip

Change History (48)

comment:1 Changed 7 years ago by ncohen

Could you be interested in running this method on the transitive closure of your poset ?

http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.subgraph_search

Nathann

comment:2 Changed 7 years ago by rowland

  • Cc chrisjamesberg ahmorales added

comment:3 Changed 7 years ago by chrisjamesberg

apply: poset_functionality_14099_er.patch

comment:4 follow-up: Changed 7 years ago by rowland

  • Cc saliola ncohen added

Is the transitive closure + subgraph_search fast enough to make it worthwhile?

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

Is the transitive closure + subgraph_search fast enough to make it worthwhile?

Well... It is sligthly smarter than what you do (it would not enumerate all chains of length 'n' beginning with an element v, if this element v is comparable with an element of the chain of length 'm' you already picked) and it is implemented in Cython.

I'd say that it's definitely worth a try.

Nathann

comment:6 Changed 7 years ago by rowland

apply: poset_functionality_14099_er.patch

comment:7 Changed 7 years ago by rowland

I don't think subgraph_search answers the same question....

Using induced=True results in the poset Poset({0 : [], 1 : [2], 2 : [3]}) which is 3+1 being (3+1)-free:

# g is the transitive closure
sage: g = DiGraph({0 : [], 1 : [2, 3], 2 : [3]})
sage: g.subgraph_search(DiGraph({0 : [1], 1 : [2]}) + DiGraph({0 : []}), induced=True)

Using induced=False results in the poset Poset({0 : [1, 2], 2 : [3]}) which is (3+1)-free containing (3+1):

# g is the transitive closure
sage: g = DiGraph({0 : [1, 2, 3], 2 : [3]})
sage: g.subgraph_search(DiGraph({0 : [1], 1 : [2]}) + DiGraph({0 : []}), induced=False)
Subgraph of (): Digraph on 4 vertices

comment:8 Changed 7 years ago by ncohen

you definitely need to use induced = True, but not on the digraphs. As I said you need to work on their transitive closure :

def test(g,n,m):
    n = 3
    m = 1
    pattern = digraphs.Circuit(n+1); pattern.delete_vertex(n)
    pattern += digraphs.Circuit(m+1); pattern.delete_vertex(n+m-1)
    c = g.transitive_closure().subgraph_search(pattern.transitive_closure(), induced = True)
    if c:
      print "Pattern found with chains", c.connected_components()
    else:
      print "No pattern in this graph"

g = DiGraph({0 : [], 1 : [2, 3], 2 : [3]})
test(g,3,1)

Nathann

comment:9 Changed 7 years ago by rowland

Yes, you are right; it seems to work. It doesn't seem to be any faster for posets on 7 elements, but perhaps it's worth having both options available.

sage: def test1(poset, m, n):
....:     for mchain in poset.chains().elements_of_depth_iterator(m):
....:         for nchain in poset.chains().elements_of_depth_iterator(n):
....:             if all(poset.compare_elements(x, y) is None for x in mchain for y in nchain):
....:                 return False
....:     return True
....: 
sage: %time len([p for p in Posets(7) if test1(p, 3, 1)])
CPU times: user 22.46 s, sys: 0.03 s, total: 22.49 s
Wall time: 22.49 s
639
sage: def test2(poset, m, n):
....:     relations = poset.relations()
....:     g = DiGraph([rel for rel in relations if rel[0] != rel[1]])
....:     g.add_vertices([rel[0] for rel in relations if rel[0] == rel[1]])
....:     mchain = digraphs.Circuit(m+1)
....:     mchain.delete_vertex(m)
....:     nchain = digraphs.Circuit(n+1)
....:     nchain.delete_vertex(n)
....:     return g.transitive_closure().subgraph_search((mchain + nchain).transitive_closure(), induced = True) is None
....: 
sage: %time len([p for p in Posets(7) if test2(p, 3, 1)])
CPU times: user 23.47 s, sys: 0.01 s, total: 23.48 s
Wall time: 23.48 s
639

comment:10 Changed 7 years ago by rowland

  • Keywords days45 added

On the other hand, for larger posets using the graph search does much better:

sage: posets = [Posets.RandomPoset(30, .5) for x in range(10)]
sage: %time len([p for p in posets if test1(p, 3, 1)])
CPU times: user 20.69 s, sys: 0.00 s, total: 20.69 s
Wall time: 20.69 s
6
sage: %time len([p for p in posets if test2(p, 3, 1)])
CPU times: user 0.19 s, sys: 0.00 s, total: 0.19 s
Wall time: 0.19 s
6

comment:11 Changed 7 years ago by chrisjamesberg

  • Authors changed from chrisjamesberg, rowland, ahmorales to Eric rowland, Alejandro Morales

comment:12 Changed 7 years ago by chrisjamesberg

  • Reviewers changed from saliola to Chris Berg

comment:13 Changed 7 years ago by ncohen

I just created ticket #14122 because of this ticket.

With that ticket, the following code

mchain = digraphs.Circuit(m+1)
mchain.delete_vertex(m)
nchain = digraphs.Circuit(n+1)
nchain.delete_vertex(n)
return g.transitive_closure().subgraph_search((mchain + nchain).transitive_closure(), induced = True) is None

can be replaced by

twochains = digraphs.Tournament(n) + digraphs.Tournament(m)
return g.transitive_closure().subgraph_search(twochains, induced = True) is None

Nathann

Changed 7 years ago by rowland

comment:14 Changed 7 years ago by rowland

  • Authors changed from Eric rowland, Alejandro Morales to Eric Rowland, Alejandro Morales
  • Status changed from new to needs_review

comment:15 Changed 7 years ago by ncohen

  • Cc nthiery hivert added

As #14122 just got reviewed, could you rebase your patch on top of it and use the Tournament cnstructor ? :-)

By the way, could your merge your two functions into only one ? It would accept a list as a parameter and run the "real code" if the list has length one, and call itself on each pair of the list when it has a larger length.

Nathann

comment:16 follow-up: Changed 7 years ago by rowland

What is the advantage of merging them into one? The disadvantage is a decrease in clarity.

comment:17 in reply to: ↑ 16 Changed 7 years ago by ncohen

What is the advantage of merging them into one? The disadvantage is a decrease in clarity.

One advantage is that you only have to write documentation and doctests for only one function instead of two, and documentation and doctests are actually the largest part of this patch. Then 50% of the actual code is only there to deal with the input and not actual computations. If you want to improve clarity, you can also dramatically decrease the tests you do at the beginning. Something like that :

def i_take_lists_of_pairs_or_just_a_pair_as_input(u,v=None):
    if v is None:
        return all(i_take_lists_of_pairs_or_just_a_pair_as_input(*x) for x in u)
    u,v = Integer(u), Integer(v)
    if u<0 or v<0:
        raise ValueError("Both elements of a pair must be positive integers") 
    # No I can do some actual computations
    print u,v
    return True

But honestly I think that only one method (taking a pair as input) should exist in Sage. To me the rest is "personal code".

Nathann

comment:18 Changed 7 years ago by ncohen

  • Status changed from needs_review to needs_work

#14122 has been merged into beta1.

Nathann

comment:19 Changed 7 years ago by rowland

  • Status changed from needs_work to needs_review

comment:20 Changed 7 years ago by chapoton

  • Description modified (diff)

instruction for the bot:

Apply poset_functionality_14099-er.patch

comment:21 Changed 7 years ago by chapoton

I also think that only the method taking a pair of numbers should go into sage.

You can now use the TransitiveTournament? method, it works for n=1.

comment:22 Changed 7 years ago by chapoton

  • Dependencies set to #14536

comment:23 Changed 7 years ago by rowland

This is now rebased on #14536.

Awaiting review.

comment:24 Changed 7 years ago by rowland

  • Keywords days49 added

comment:25 Changed 7 years ago by ncohen

  • Status changed from needs_review to needs_work

Helloooooooooooooooooooooo !!

  • Could you add your new method to the index of methods at the top of the file ? This way we have a nice list of everything that the posets can do http://www.sagemath.org/doc/reference/combinat/sage/combinat/posets/posets.html
  • Could you rewrite your reference so that Sphinx understands it ? You have an example there :
    sage: Graph.average_distance??
    
  • Why do you build the digraph from the relations, instead of using the Hasse Diagram ? I thought that this is how it was done in an earlier version of the patch O_o

Nathann

comment:26 Changed 7 years ago by rowland

  • Status changed from needs_work to needs_review

I have no idea what Sphinx is.

comment:27 Changed 7 years ago by ncohen

  • Status changed from needs_review to needs_work

It is the piece of code that generates the html documentation of Sage.

sage -b && sage -docbuild reference/combinat html

Nathann

comment:28 Changed 7 years ago by rowland

  • Status changed from needs_work to needs_review

comment:29 Changed 7 years ago by chrisjamesberg

  • Status changed from needs_review to positive_review

comment:30 Changed 7 years ago by ncohen

  • Status changed from positive_review to needs_work

O_o

Nathann

comment:31 Changed 7 years ago by ncohen

Could you please rewrite the reference to [Stanley, Enumerative Combinatorics Volume 1, 2nd edition] in the usual Sphinx format, or explain why you think that it is a bad idea ?

Nathann

comment:32 Changed 7 years ago by rowland

  • Status changed from needs_work to needs_review

Anything else?

comment:33 Changed 7 years ago by ncohen

O_O

comment:34 Changed 7 years ago by ncohen

Okayyyyyyyyyyyyyyyyyyyyyyyy I see ......

comment:35 Changed 7 years ago by rowland

  • Status changed from needs_review to positive_review

comment:36 Changed 7 years ago by ncohen

No way.

comment:37 Changed 7 years ago by ncohen

I am currently writing an additional patch for this bibliographical reference.

I will upload it shortly.

Nathann

comment:38 Changed 7 years ago by ncohen

  • Status changed from positive_review to needs_work

comment:39 Changed 7 years ago by ncohen

  • Description modified (diff)
  • Status changed from needs_work to needs_review

Here is a patch that rewrites the reference to Stanley's book as we usually do in Sphinx, and as it is done in Graph.average_distance?? and other functions.

I don't know why you set the ticket to positive_review twice even though the guy who was doing the review (=me) never said that he agreed with it. I don't get why Chris set it to positive review while there was a comment which had not been fixed either. Anyway, I think that this small trac_14099-rev.patch patch has to be added to this ticket too, unless you can explain why you prefer it to be left out.

Nathann

comment:40 Changed 7 years ago by rowland

I set the ticket to positive review, once, after I asked if there was anything else and you said "Okayyyyyyyyyyyyyyyyyyyyyyyy I see ......" which I took to mean that everything was okay.

Chris set it to positive review after I addressed your latest comment, which was not specific at all. I improved the typesetting of the variables. Apparently this was not what you had in mind, but you hadn't said that.

You need to be more clear in your communication with people who are learning how to contribute. At this point I am tired of making point modifications every time you think something should be changed, so please just finish the patch up yourself as you want it.

comment:41 Changed 7 years ago by chrisjamesberg

  • Status changed from needs_review to positive_review

comment:42 Changed 7 years ago by jdemeyer

The patches need proper commit messages (use hg qrefresh -e for that).

Changed 7 years ago by rowland

comment:43 Changed 7 years ago by jdemeyer

  • Status changed from positive_review to needs_work

The reviewer patch needs a proper commit message, use hg qrefresh -e for this.

Changed 7 years ago by ncohen

comment:44 Changed 7 years ago by ncohen

  • Status changed from needs_work to positive_review

comment:45 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.11.rc0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.