Revision history [back]

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.