Revision history [back]

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

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

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

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.

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