mapVF2.py

'''
@author Michael J Bommarito II
@date Mar 20, 2010

mjbommar@cluster1:~$ time python -O mapVF2.py 1
Undirected graph (|V| = 50, |E| = 294)
[240, 564, 4248, 97392, 137788, 560468, 6871224, 164328, 4528, 284, 50]

real    0m4.000s
user    0m3.960s
sys     0m0.020s

mjbommar@cluster1:~$ time python -O mapVF2.py 4
Undirected graph (|V| = 50, |E| = 294)
[360, 2004, 7724, 72252, 139200, 588368, 5887272, 149586, 4708, 310, 50]

real    0m3.264s
user    0m4.040s
sys     0m0.020s

mjbommar@cluster1:~$ time python -O mapVF2.py 8
Undirected graph (|V| = 50, |E| = 294)
[0, 156, 1064, 11124, 47622, 395660, 4747824, 113580, 3648, 290, 50]

real    0m2.538s
user    0m3.030s
sys     0m0.050s
'''

import igraph
import multiprocessing
import sys

def countVF2(arg):
	'''
	Count the subisomorphisms of s in g.
	'''
	g, s = arg
	return g.count_subisomorphisms_vf2(s)

if __name__ == "__main__":
	
	N = 50		# Number of nodes
	p = 0.1		# E-R Probablity
	k = 3		# B-A edge
	tau = 5		# maximum subgraph |V| 
	poolSize = int(sys.argv[1]) 	# Number of threads in the pool
	
	#g = igraph.Graph.Erdos_Renyi(N, p)
	g = igraph.Graph.Barabasi(N, k)
	print g
	
	'''
	Create the subgraph set.
	'''
	subgraphs = [igraph.Graph.Full(tau)]
	while subgraphs[-1].vcount() > 1:
		edgelist = subgraphs[-1].get_edgelist()
		edgelist.pop()
		subgraphs.append(igraph.Graph(edgelist))
	
	'''
	Now create the pool and use it to 
	count the number of subgraph isomorphisms.
	'''
	pool = multiprocessing.Pool(poolSize)
	objectList = [(g,s) for s in subgraphs]
	subgraphCount = pool.map(countVF2, objectList)
	
	print subgraphCount