Ask Your Question
1

Random block graph

asked 2017-04-26 06:35:00 -0600

Deepak Sarma gravatar image

updated 2017-05-03 02:58:45 -0600

tmonteil gravatar image

How can I get a random connected graph with m blocks so that each block is a k-clique (complete graph with k vertices).

edit retag flag offensive close merge delete

Comments

Would this be equivalent to generating a tree at random and replacing each edge by a clique? If so, it shouldn't be hard to implement.

fidbc gravatar imagefidbc ( 2017-04-27 11:38:58 -0600 )edit

Yes, it is.

Deepak Sarma gravatar imageDeepak Sarma ( 2017-04-28 01:21:53 -0600 )edit

3 answers

Sort by ยป oldest newest most voted
0

answered 2017-05-03 02:58:28 -0600

tmonteil gravatar image

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).

edit flag offensive delete link more
0

answered 2017-04-28 04:05:16 -0600

updated 2017-04-29 05:00:36 -0600

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
edit flag offensive delete link more

Comments

'Graph' object has no attribute 'add_clique'

Deepak Sarma gravatar imageDeepak Sarma ( 2017-04-28 04:44:12 -0600 )edit

Many thanks for

graphs.RandomTree

i could not photo-graph the method during a long internet search, thus writing a mess instead in my post...

dan_fulea gravatar imagedan_fulea ( 2017-04-28 13:14:02 -0600 )edit

Using the above, each clique in the resulted random graph gets at most two vertices that also belong to some other clique block, if i get the message right. (The code does not work on my 'SageMath version 7.6, Release Date: 2017-03-25' ... It appears that version 8 is needed.) The vertices in

[G.add_vertex() for i in range(k-2)]

remain unconnected to inserted $k$-clique blocks, excepting the one generated to contain [u,v] . Isn't it?!

dan_fulea gravatar imagedan_fulea ( 2017-04-28 13:22:04 -0600 )edit

You are right, add_clique is a recent addition. I have edited my answer in case you don't have it.

David Coudert gravatar imageDavid Coudert ( 2017-04-29 02:55:19 -0600 )edit

The first proposed method starts building a random tree with m edges and then replaces each edge with a k-clique. It is effectively not sufficient to get all possible random block graphs. I have added a new version that starts with a random tree with m vertices, replaces each vertex by a k-clique and then connect blocks corresponding to tree edges. This way we can get all possible random block graphs.

David Coudert gravatar imageDavid Coudert ( 2017-04-29 03:03:54 -0600 )edit
0

answered 2017-04-27 14:29:45 -0600

dan_fulea gravatar image

updated 2017-04-28 13:32:38 -0600

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.

edit flag offensive delete link more

Comments

Thank you.

Deepak Sarma gravatar imageDeepak Sarma ( 2017-04-28 01:25:08 -0600 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2017-04-26 06:35:00 -0600

Seen: 145 times

Last updated: May 03