ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 28 Sep 2017 17:05:49 -0500Finding posets of a certain form 2https://ask.sagemath.org/question/38967/finding-posets-of-a-certain-form-2/I try to obtain the connected posets with n elements having a top and bottom such that in the Hasse quiver, in every point there start at most two arrows and at every point there end at most two arrows (thus for example all distributive lattices are of this form).
Is there a quick command to obtain this as a list?
What condition does one has to add in
posets = [ p for p in Posets(n) if p.is_connected() and p.has_top() and p.has_bottom()]
Actually a quick method would be cool which works up to n=10 or 11. (filtering things out of the set of all posets, seems to be very slow in SAGE)Sun, 24 Sep 2017 13:58:05 -0500https://ask.sagemath.org/question/38967/finding-posets-of-a-certain-form-2/Comment by John Palmieri for <p>I try to obtain the connected posets with n elements having a top and bottom such that in the Hasse quiver, in every point there start at most two arrows and at every point there end at most two arrows (thus for example all distributive lattices are of this form).
Is there a quick command to obtain this as a list?
What condition does one has to add in</p>
<pre><code>posets = [ p for p in Posets(n) if p.is_connected() and p.has_top() and p.has_bottom()]
</code></pre>
<p>Actually a quick method would be cool which works up to n=10 or 11. (filtering things out of the set of all posets, seems to be very slow in SAGE)</p>
https://ask.sagemath.org/question/38967/finding-posets-of-a-certain-form-2/?comment=38997#post-id-38997First, isn't `is_connected` redundant once you know that `p.has_top()` is true? Second, it would probably be faster to construct all posets with `n-2` elements and then adjoin a new top and bottom. Finally, do you need all of them at once? Note that `posets = (p for p in Posets(5) ...)` is much faster than the same with square brackets, and you can do `for p in posets: ...` just as well in either case.Thu, 28 Sep 2017 17:05:49 -0500https://ask.sagemath.org/question/38967/finding-posets-of-a-certain-form-2/?comment=38997#post-id-38997Comment by fidbc for <p>I try to obtain the connected posets with n elements having a top and bottom such that in the Hasse quiver, in every point there start at most two arrows and at every point there end at most two arrows (thus for example all distributive lattices are of this form).
Is there a quick command to obtain this as a list?
What condition does one has to add in</p>
<pre><code>posets = [ p for p in Posets(n) if p.is_connected() and p.has_top() and p.has_bottom()]
</code></pre>
<p>Actually a quick method would be cool which works up to n=10 or 11. (filtering things out of the set of all posets, seems to be very slow in SAGE)</p>
https://ask.sagemath.org/question/38967/finding-posets-of-a-certain-form-2/?comment=38973#post-id-38973Depending on what you are planning to do with these posets, it might be worth filtering them up to a certain size and store the output. So that you can just go back and read from the stored list. However, if you are interested in say, counting them, then maybe generating them will be the way to go.Sun, 24 Sep 2017 16:34:55 -0500https://ask.sagemath.org/question/38967/finding-posets-of-a-certain-form-2/?comment=38973#post-id-38973Comment by fidbc for <p>I try to obtain the connected posets with n elements having a top and bottom such that in the Hasse quiver, in every point there start at most two arrows and at every point there end at most two arrows (thus for example all distributive lattices are of this form).
Is there a quick command to obtain this as a list?
What condition does one has to add in</p>
<pre><code>posets = [ p for p in Posets(n) if p.is_connected() and p.has_top() and p.has_bottom()]
</code></pre>
<p>Actually a quick method would be cool which works up to n=10 or 11. (filtering things out of the set of all posets, seems to be very slow in SAGE)</p>
https://ask.sagemath.org/question/38967/finding-posets-of-a-certain-form-2/?comment=38972#post-id-38972This looks like a very particular set of posets. Maybe you'll need to generate them manually if you do not want to filter from the list of all posets.Sun, 24 Sep 2017 16:31:52 -0500https://ask.sagemath.org/question/38967/finding-posets-of-a-certain-form-2/?comment=38972#post-id-38972Comment by sagequstions for <p>I try to obtain the connected posets with n elements having a top and bottom such that in the Hasse quiver, in every point there start at most two arrows and at every point there end at most two arrows (thus for example all distributive lattices are of this form).
Is there a quick command to obtain this as a list?
What condition does one has to add in</p>
<pre><code>posets = [ p for p in Posets(n) if p.is_connected() and p.has_top() and p.has_bottom()]
</code></pre>
<p>Actually a quick method would be cool which works up to n=10 or 11. (filtering things out of the set of all posets, seems to be very slow in SAGE)</p>
https://ask.sagemath.org/question/38967/finding-posets-of-a-certain-form-2/?comment=38970#post-id-38970@fidbc Yes I mean the Hasse diagram. Thank I will look at it. But it is also important that the code is quick, so maybe filtering is not the quickest thing to do?Sun, 24 Sep 2017 16:15:59 -0500https://ask.sagemath.org/question/38967/finding-posets-of-a-certain-form-2/?comment=38970#post-id-38970Comment by fidbc for <p>I try to obtain the connected posets with n elements having a top and bottom such that in the Hasse quiver, in every point there start at most two arrows and at every point there end at most two arrows (thus for example all distributive lattices are of this form).
Is there a quick command to obtain this as a list?
What condition does one has to add in</p>
<pre><code>posets = [ p for p in Posets(n) if p.is_connected() and p.has_top() and p.has_bottom()]
</code></pre>
<p>Actually a quick method would be cool which works up to n=10 or 11. (filtering things out of the set of all posets, seems to be very slow in SAGE)</p>
https://ask.sagemath.org/question/38967/finding-posets-of-a-certain-form-2/?comment=38969#post-id-38969By Hasse quiver, do you mean Hasse diagram?
If so, then you may use the `DiGraph` methods on the diagram to check the out-degree and the in-degree. See for example [`out_degree`](http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/digraph.html#sage.graphs.digraph.DiGraph.out_degree) and [`in_degree`](http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/digraph.html#sage.graphs.digraph.DiGraph.in_degree).Sun, 24 Sep 2017 16:09:02 -0500https://ask.sagemath.org/question/38967/finding-posets-of-a-certain-form-2/?comment=38969#post-id-38969Answer by dan_fulea for <p>I try to obtain the connected posets with n elements having a top and bottom such that in the Hasse quiver, in every point there start at most two arrows and at every point there end at most two arrows (thus for example all distributive lattices are of this form).
Is there a quick command to obtain this as a list?
What condition does one has to add in</p>
<pre><code>posets = [ p for p in Posets(n) if p.is_connected() and p.has_top() and p.has_bottom()]
</code></pre>
<p>Actually a quick method would be cool which works up to n=10 or 11. (filtering things out of the set of all posets, seems to be very slow in SAGE)</p>
https://ask.sagemath.org/question/38967/finding-posets-of-a-certain-form-2/?answer=38991#post-id-38991The following code collects the directed graphs associated to Hasse diagrams for the specified posets.
I hope the recursion works as needed. However, the code does not perform well up to 10 or 11 vertices...
class MyDiGraph( DiGraph ):
"""class extending DiGraph
"""
def __init__( self, *args, **kargs ):
super( MyDiGraph, self ).__init__( *args, **kargs )
self.open_valence_dic = {}
def add_top_joins( self, n, jList ):
"""
add the vertex n and an edge j -> n for each j in jList
also set the open valence 2 for the new vertex n
"""
self . add_vertex( n )
for j in jList:
self . add_edges( [ (j,n) ] )
self . open_valence_dic[j] -= 1
self . open_valence_dic[n] = 2
def is_valid_final_hasse_diagram( self ):
n = max( self.vertices() )
A = matrix.identity( ZZ, n ) + self.adjacency_matrix()
An = A^n
if min( list( An.row(0) ) + list( An.column(n-1) ) ) > 0:
return True
return False
import copy
def compute_MyDiGraph_List( level=1, verbose=False ):
"""recursively comute all MyDiGraph instances up to isomorphism.
"""
if level not in ZZ or level < 0:
return []
n = 0
while n < level:
n += 1
if verbose:
print "LEVEL", n
if n == 1:
D = MyDiGraph( { 1: [] }
, weighted=False
, format='dict_of_lists' )
D.open_valence_dic[1] = 2
newList = [ D, ]
else:
oldList = newList[:]
newList = [] # and we append
for oldD in oldList:
open_vertices = [ j
for j in oldD.vertices()
if oldD.open_valence_dic[j] > 0 ]
for j in open_vertices:
D = copy.deepcopy( oldD )
D . add_top_joins( n, [j,] )
newList.append( D )
for k in open_vertices:
if k <= j:
continue
DD = copy.deepcopy( D )
DD . add_top_joins( n, [k,] )
newList.append( DD )
if verbose:
print "\t%s new digraphs" % len( newList )
isoList = []
for D in newList:
ok = True
for iD in isoList:
if D.is_isomorphic( iD ):
ok = False
break
if ok:
isoList.append(D)
newList = isoList[:]
if verbose:
print "\t%s new digraphs up to isomorphism\n" % len( newList )
return [ D
for D in newList
if D.is_valid_final_hasse_diagram() ]
digraphs = compute_MyDiGraph_List( level=8, verbose=True )
print len(digraphs)
The above runs in verbose mode and shows information about the collected data:
LEVEL 1
1 new digraphs
1 new digraphs up to isomorphism
LEVEL 2
1 new digraphs
1 new digraphs up to isomorphism
LEVEL 3
3 new digraphs
3 new digraphs up to isomorphism
LEVEL 4
12 new digraphs
9 new digraphs up to isomorphism
LEVEL 5
52 new digraphs
36 new digraphs up to isomorphism
LEVEL 6
265 new digraphs
169 new digraphs up to isomorphism
LEVEL 7
1527 new digraphs
922 new digraphs up to isomorphism
LEVEL 8
9946 new digraphs
5696 new digraphs up to isomorphism
2143
Some comments on the last data for the last level. The code collected first 9946 digraphs on 8 vertices, that would be possibly relevant for the next step. Among them, after a time consuming process, there are only 5696 such digraphs up to isomorphism. The recursion constructs digraphs such that each new top node $n$ is connected with at least one node among $1,2,\dots,(n-1)$. So this insures the existence of a path to the minimal vertex $1$. But there be no path to the new top, $n$. Among the $5696$ digraphs there are $2143$ digraphs, such that each vertex lies at at least one path from $1$ to $n=8$.
After the design was established and the results are now here, one can draw conclusions and make things better. Perhaps the deep copy operations are time consuming. A better strategy would be now to work with upper diagonal zero-one-matrices next time, at least as long we are generating the new generation of matrices. Only the check for isomorphisms must be maybe done in the digraph world. For instance it should be simpler to store and extend the data
sage: D = digraphs[99]
sage: D.adjacency_matrix()
[0 1 1 0 0 0 0 0]
[0 0 0 1 1 0 0 0]
[0 0 0 0 0 1 1 0]
[0 0 0 0 1 0 0 0]
[0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 1]
[0 0 0 0 0 0 0 0]
than doing this with the corresponding digraph. The condition
if min( list( An.row(0) ) + list( An.column(n-1) ) ) > 0:
return True
is very pessimistic. In fact it is a slow condition, the first row has by construction only elements $\ge 1$, so i think we can write simpler `if min( list( An.column(n-1) ) ) > 0:` and possibly there is no need to use the matrix `A`, since the dictionary of valencies still open for higher levels to come has the information. But i am in time troubles, have to stop here.Thu, 28 Sep 2017 03:49:28 -0500https://ask.sagemath.org/question/38967/finding-posets-of-a-certain-form-2/?answer=38991#post-id-38991