ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 03 May 2017 02:58:28 -0500Random block graphhttp://ask.sagemath.org/question/37433/random-block-graph/ How can I get a random connected graph with m blocks so that each block is a k-clique (complete graph with k vertices). Wed, 26 Apr 2017 06:35:00 -0500http://ask.sagemath.org/question/37433/random-block-graph/Comment by Deepak Sarma for <p>How can I get a random connected graph with m blocks so that each block is a k-clique (complete graph with k vertices). </p>
http://ask.sagemath.org/question/37433/random-block-graph/?comment=37447#post-id-37447Yes, it is.Fri, 28 Apr 2017 01:21:53 -0500http://ask.sagemath.org/question/37433/random-block-graph/?comment=37447#post-id-37447Comment by fidbc for <p>How can I get a random connected graph with m blocks so that each block is a k-clique (complete graph with k vertices). </p>
http://ask.sagemath.org/question/37433/random-block-graph/?comment=37440#post-id-37440Would 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.Thu, 27 Apr 2017 11:38:58 -0500http://ask.sagemath.org/question/37433/random-block-graph/?comment=37440#post-id-37440Answer by tmonteil for <p>How can I get a random connected graph with m blocks so that each block is a k-clique (complete graph with k vertices). </p>
http://ask.sagemath.org/question/37433/random-block-graph/?answer=37496#post-id-37496See [trac ticket 22908](https://trac.sagemath.org/ticket/22908) for an implementation in Sage. I am adding a `confirmed_bug` tag (which will become `fixed_bug` once this will be merged).Wed, 03 May 2017 02:58:28 -0500http://ask.sagemath.org/question/37433/random-block-graph/?answer=37496#post-id-37496Answer by David Coudert for <p>How can I get a random connected graph with m blocks so that each block is a k-clique (complete graph with k vertices). </p>
http://ask.sagemath.org/question/37433/random-block-graph/?answer=37450#post-id-37450Recall 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 BGFri, 28 Apr 2017 04:05:16 -0500http://ask.sagemath.org/question/37433/random-block-graph/?answer=37450#post-id-37450Comment by David Coudert for <p>Recall that a block graph is a graph in which every biconnected component is a clique.</p>
<p>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:</p>
<pre><code>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
</code></pre>
<p>The <code>add_clique</code> method is a recent addition to sagemath. If you don't have it, you can do</p>
<pre><code>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
</code></pre>
<p>A call to <code>G.add_vertex()</code> adds an isolated vertex to the graph. You then add the edges of the clique.</p>
<p><em>EDIT</em>: 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. </p>
<pre><code>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
</code></pre>
http://ask.sagemath.org/question/37433/random-block-graph/?comment=37464#post-id-37464The 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.Sat, 29 Apr 2017 03:03:54 -0500http://ask.sagemath.org/question/37433/random-block-graph/?comment=37464#post-id-37464Comment by David Coudert for <p>Recall that a block graph is a graph in which every biconnected component is a clique.</p>
<p>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:</p>
<pre><code>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
</code></pre>
<p>The <code>add_clique</code> method is a recent addition to sagemath. If you don't have it, you can do</p>
<pre><code>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
</code></pre>
<p>A call to <code>G.add_vertex()</code> adds an isolated vertex to the graph. You then add the edges of the clique.</p>
<p><em>EDIT</em>: 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. </p>
<pre><code>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
</code></pre>
http://ask.sagemath.org/question/37433/random-block-graph/?comment=37463#post-id-37463You are right, `add_clique` is a recent addition. I have edited my answer in case you don't have it.Sat, 29 Apr 2017 02:55:19 -0500http://ask.sagemath.org/question/37433/random-block-graph/?comment=37463#post-id-37463Comment by dan_fulea for <p>Recall that a block graph is a graph in which every biconnected component is a clique.</p>
<p>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:</p>
<pre><code>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
</code></pre>
<p>The <code>add_clique</code> method is a recent addition to sagemath. If you don't have it, you can do</p>
<pre><code>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
</code></pre>
<p>A call to <code>G.add_vertex()</code> adds an isolated vertex to the graph. You then add the edges of the clique.</p>
<p><em>EDIT</em>: 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. </p>
<pre><code>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
</code></pre>
http://ask.sagemath.org/question/37433/random-block-graph/?comment=37455#post-id-37455Using 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?!Fri, 28 Apr 2017 13:22:04 -0500http://ask.sagemath.org/question/37433/random-block-graph/?comment=37455#post-id-37455Comment by dan_fulea for <p>Recall that a block graph is a graph in which every biconnected component is a clique.</p>
<p>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:</p>
<pre><code>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
</code></pre>
<p>The <code>add_clique</code> method is a recent addition to sagemath. If you don't have it, you can do</p>
<pre><code>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
</code></pre>
<p>A call to <code>G.add_vertex()</code> adds an isolated vertex to the graph. You then add the edges of the clique.</p>
<p><em>EDIT</em>: 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. </p>
<pre><code>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
</code></pre>
http://ask.sagemath.org/question/37433/random-block-graph/?comment=37454#post-id-37454Many thanks for
graphs.RandomTree
i could not photo-graph the method during a long internet search, thus writing a mess instead in my post...Fri, 28 Apr 2017 13:14:02 -0500http://ask.sagemath.org/question/37433/random-block-graph/?comment=37454#post-id-37454Comment by Deepak Sarma for <p>Recall that a block graph is a graph in which every biconnected component is a clique.</p>
<p>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:</p>
<pre><code>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
</code></pre>
<p>The <code>add_clique</code> method is a recent addition to sagemath. If you don't have it, you can do</p>
<pre><code>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
</code></pre>
<p>A call to <code>G.add_vertex()</code> adds an isolated vertex to the graph. You then add the edges of the clique.</p>
<p><em>EDIT</em>: 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. </p>
<pre><code>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
</code></pre>
http://ask.sagemath.org/question/37433/random-block-graph/?comment=37452#post-id-37452'Graph' object has no attribute 'add_clique'Fri, 28 Apr 2017 04:44:12 -0500http://ask.sagemath.org/question/37433/random-block-graph/?comment=37452#post-id-37452Answer by dan_fulea for <p>How can I get a random connected graph with m blocks so that each block is a k-clique (complete graph with k vertices). </p>
http://ask.sagemath.org/question/37433/random-block-graph/?answer=37443#post-id-37443Some 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.Thu, 27 Apr 2017 14:29:45 -0500http://ask.sagemath.org/question/37433/random-block-graph/?answer=37443#post-id-37443Comment by Deepak Sarma for <p>Some words on the code posted below:</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>An now the code:</p>
<p><em>* LATER EDIT *</em> Since there is a random tree generator (@David Coudert, thanks!) some longer passages were commented.</p>
<pre><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 = 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()
</code></pre>
<p>This one time, i've got the tree with the following matrix:</p>
<p>...random <strong>tree</strong> chosen with adjacency matrix</p>
<pre><code>[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]
</code></pre>
<p>... and unfortunately i cannot show here the <strong>constructed graph</strong>. Its data is:</p>
<pre><code>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')]
</code></pre>
<p>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$.</p>
<p>I hope, this was wanted.</p>
http://ask.sagemath.org/question/37433/random-block-graph/?comment=37448#post-id-37448Thank you.Fri, 28 Apr 2017 01:25:08 -0500http://ask.sagemath.org/question/37433/random-block-graph/?comment=37448#post-id-37448Answer by fidbc for <p>How can I get a random connected graph with m blocks so that each block is a k-clique (complete graph with k vertices). </p>
http://ask.sagemath.org/question/37433/random-block-graph/?answer=37439#post-id-37439Would 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.Thu, 27 Apr 2017 11:38:36 -0500http://ask.sagemath.org/question/37433/random-block-graph/?answer=37439#post-id-37439