The 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.
By Hasse quiver, do you mean Hasse diagram?
If so, then you may use the
DiGraphmethods on the diagram to check the out-degree and the in-degree. See for exampleout_degreeandin_degree.@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?
This 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.
Depending 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.
First, isn't
is_connectedredundant once you know thatp.has_top()is true? Second, it would probably be faster to construct all posets withn-2elements and then adjoin a new top and bottom. Finally, do you need all of them at once? Note thatposets = (p for p in Posets(5) ...)is much faster than the same with square brackets, and you can dofor p in posets: ...just as well in either case.