Random block graph

edit

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[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 = graphs.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.

Recall that a block graph is a graph in which every biconnected component is a clique.

A simple method to generate a connected block graph with m blocks of size k is to start from a random tree with m edges and then replace each edge by a clique of order k:

def RandomBlockGraph(m, k):
    G = graphs.RandomTree(m+1)
    E = G.edges(labels=0)
    for u,v in E:
        G.add_clique([u,v] + [G.add_vertex() for i in range(k-2)])
    return G

The add_clique method is a recent addition to sagemath. If you don't have it, you can do

def RandomBlockGraph(m, k):
    import itertools
    G = graphs.RandomTree(m+1)
    E = G.edges(labels=0)
    for u,v in E:
        V = [u,v] + [G.add_vertex() for i in range(k-2)]
        for x,y in itertools.combinations(V, 2):
            G.add_edge(x, y)
    return G

A call to G.add_vertex() adds an isolated vertex to the graph. You then add the edges of the clique.

EDIT: The method below starts with a random tree of order m. Then it creates a graph with one k-clique (block) per vertex of the tree. We connect blocks corresponding to end vertices of tree edges. To do so, we select one vertex per block and merge the two selected vertices. We use a disjoint set data structure to keep track of the merge operations and so get a unique identifier per set of merged vertices.

def RandomBlockGraph(m, k):
    import itertools
    import random

    # We start with a random tree of order m
    T = graphs.RandomTree(m)

    # We create a block of size k per vertex of the tree
    B = {u:[(u,i) for i in range(k)] for u in T}

    # For each edge of the tree, we choose 1 vertex in each of the corresponding
    # blocks and we merge them. We use a disjoint set data structure to keep a
    # unique identifier per merged vertices
    DS = DisjointSet([i for u in B for i in B[u]])
    for u,v in T.edges(labels=0):
        DS.union(random.choice(B[u]), random.choice(B[v]))

    # We finally build the block graph
    BG = Graph()
    for u in B:
        for x,y in itertools.combinations(B[u], 2):
            BG.add_edge(DS.find(x), DS.find(y))

    return BG

See trac ticket 22908 for an implementation in Sage. I am adding a confirmed_bug tag (which will become fixed_bug once this will be merged).