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 ) . intersection( set(newVertex2) ) ]
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"

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 ] }
, 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.

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:

* LATER EDIT * Since there is a random tree generator (@David Coudert, thanks!) some longer passages were commented.

# 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 ) . intersection( set(newVertex2) ) ]
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 = graphs.RandomTree( m )

# t . show()
print "...random tree chosen with 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 ] }
, 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.