Revision history [back]

Some words on the code posted below:

Since there was no method available for the task, we have to do it with our own devices. I hope i could understand the definitions for the structure, and that the following strategy to construct such a graph with $m$ blocks, each one being a $k$-clique is constructing them all.

First of all, we start with a (connected) tree $t$ with $m$ vertices. We assume that each vertex is connected to at most $k$ other vertices. Then we construct the graph $G$ by the following strategy. For each vertex $v$ in $t$ we consider the $k$-clique graph $G(v)$. We build the direct sum / disjoint union of all these blocks, $$ \bigsqcup_{v\in\text{Vert(t)}} G(v)\ ,$$ and pass to the quotient $$ \bigsqcup_{v\in\text{Vert(t)}} G(v)\ \Big/\ \sim\ ,$$ where the equivalence relation $\sim$ is a choice of an equivence relation, that we describe in the sequel.

For this, let us fix a vertex $v$ in the tree. Let $s(t,v)$ be the set of its "sons" in the tree $t$. We consider a random partition of the corresponding edges $(v,w)$ with $w\in S(t,v)$, and this partition should have at most $k$ parts. We will probabilistically choose to encourage the maximal number of partitions. Then we are identifiying two "representative" vertices $v_1$ in $G(v)$ and $w_1$ in $G(w)$ iff there is an edge $(v,w)$ in the tree $t$, and such that for two edges $(v,w)$ and $(v,w')$ in $t$ we consider the same representative $v_1$, iff the two edges are in the same random partition chosen.

An now the code:

import random
import scipy.stats
from sage.graphs.trees import TreeIterator

def randomTree( numberOfVertices ): 
    treeList = []
    # we count first the trees
    numberOfTrees = sum( 1 for t in TreeIterator( numberOfVertices ) )
    # now we pick up a random tree,
    # by getting a random number in [ 0, 1, ..., numberOfTrees-1 ]
    # and then the tree at that position
    randomCounter = random.choice( range( numberOfTrees ) )
    count = 0
    for t in TreeIterator( numberOfVertices ):
        if count == randomCounter:
            return t
        count += 1

NEW_SYMBOLS = 'abcdefghijklmnopqrstuvwxyz'

def makeBlockGraph( t, k, newSymbols=NEW_SYMBOLS ):
    """From the tree we construct a graph.
    Each vertex of the tree is replaced by a k-clique, these are the blocks of the new graph.
    The blocks are joined with each other by a rule dictated by the edges of the tree.
    The labels for the vertices of the tree should not conflict with the newSymbols.
    """

    vertices    = t.vertices()
    newVertices = []
    freeVertices_DIC = dict( [ (v,k) for v in vertices ] )

    for v in vertices:
        free  = freeVertices_DIC[v] 
        sons  = [ w for w in vertices if (v,w) in t.edges( labels=False ) ]
        nsons = len(sons)
        if not nsons:
            newVertices.extend( [ ( (v,), NEW_SYMBOLS[j] ) for j in range(free) ] )
            continue

        # else
        nrPartitions = -1    # this is an init, we will change it till we get a good number
        while nrPartitions <= 0:
            nrPartitions = min( nsons, free ) - scipy.stats.poisson.rvs( 1 )

        sonsPartition = SetPartitions( sons, nrPartitions ).random_element()

        newVertices.extend( [ ( tuple( [v]+list(part) ), '' )
                              for part in sonsPartition ] )
        newVertices.extend( [ (        (v,)            , NEW_SYMBOLS[j] )
                              for j in range(free - nrPartitions) ] )

        for son in sons:    freeVertices_DIC[son] -= 1

    newEdges = [ ( newVertex1, newVertex2 )
                 for newVertex1 in newVertices
                 for newVertex2 in newVertices
                 if  set( newVertex1[0] ) . intersection( set(newVertex2[0]) ) ]
    return Graph( [newVertices, newEdges] )

# constructing a random m block-graph, each block being a k-clique, based on a random tree t
m = 15
k =  5
t = randomTree( m )

# t . show()
print "...random tree chosen with adjacency matrix"
print t.adjacency_matrix()

G  = makeBlockGraph( t, k )
# GG = Graph( G.adjacency_matrix() )    # same graph, vertices relabelled

P = G.plot( vertex_labels=False
            , vertex_size=15
            , graph_border=False
            , vertex_colors = { 'cornflowerblue' : [ v for v in G.vertices() if v[1] ] }
            , vertex_color = 'red'
            , dist=10 )

P . show()

This one time, i've got the tree with the following matrix:

...random tree chosen with adjacency matrix

[0 1 0 0 0 0 0 0 1 0 0 0 0 1 0]
[1 0 1 0 0 1 0 0 0 0 0 0 0 0 0]
[0 1 0 1 1 0 0 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 1 1 0 0 0 0 0 0 0]
[0 0 0 0 0 1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 1 0 0 0 0 0 0 0 0 0]
[1 0 0 0 0 0 0 0 0 1 0 0 1 0 0]
[0 0 0 0 0 0 0 0 1 0 1 1 0 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 0 0 1 0 0 0 0 0 0]
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
[0 0 0 0 0 0 0 0 0 0 0 0 0 1 0]

... and unfortunately i cannot show here the constructed graph. Its data is:

sage: G
Graph on 61 vertices
sage: G.vertices()

[((0,), 'a'),
 ((0,), 'b'),
 ((0,), 'c'),
 ((0,), 'd'),
 ((0, 8, 1, 13), ''),
 ((1,), 'a'),
 ((1,), 'b'),
 ((1, 2), ''),
 ((1, 5), ''),
 ((2,), 'a'),
 ((2,), 'b'),
 ((2, 3), ''),
 ((2, 4), ''),
 ((3,), 'a'),
 ((3,), 'b'),
 ((3,), 'c'),
 ((3,), 'd'),
 ((4,), 'a'),
 ((4,), 'b'),
 ((4,), 'c'),
 ((4,), 'd'),
 ((5,), 'a'),
 ((5,), 'b'),
 ((5,), 'c'),
 ((5, 6, 7), ''),
 ((6,), 'a'),
 ((6,), 'b'),
 ((6,), 'c'),
 ((6,), 'd'),
 ((7,), 'a'),
 ((7,), 'b'),
 ((7,), 'c'),
 ((7,), 'd'),
 ((8,), 'a'),
 ((8,), 'b'),
 ((8,), 'c'),
 ((8, 9, 12), ''),
 ((9,), 'a'),
 ((9,), 'b'),
 ((9,), 'c'),
 ((9, 10, 11), ''),
 ((10,), 'a'),
 ((10,), 'b'),
 ((10,), 'c'),
 ((10,), 'd'),
 ((11,), 'a'),
 ((11,), 'b'),
 ((11,), 'c'),
 ((11,), 'd'),
 ((12,), 'a'),
 ((12,), 'b'),
 ((12,), 'c'),
 ((12,), 'd'),
 ((13,), 'a'),
 ((13,), 'b'),
 ((13,), 'c'),
 ((13, 14), ''),
 ((14,), 'a'),
 ((14,), 'b'),
 ((14,), 'c'),
 ((14,), 'd')]

and two vertices $v=($ edges , decoration $)$, and $v'=\dots$ are joined iff the first components (edges and edges') share a common block number comming from the initial tree $t$.

I hope, this was wanted.