#14099: Adding Method for testing avoidance in posets
------------------------------------------------------+---------------------
Reporter: chrisjamesberg | Owner: rowland
Type: enhancement | Status: new
Priority: minor | Milestone: sage-5.7
Component: combinatorics | Resolution:
Keywords: posets | Work issues:
Report Upstream: N/A | Reviewers: saliola
Authors: chrisjamesberg, rowland, ahmorales | Merged in:
Dependencies: | Stopgaps:
------------------------------------------------------+---------------------
Comment (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
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14099#comment:9>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
