Weighted Graph Configuration Model

WeightedConfigSampler.py

import networkx as nx
import random
import copy

def main():
  G = nx.gnm_random_graph( 100, 0.1 * ( 100*100 ) )
	
	# Map from each weight to the potential endpoints having this weight
	halfEdges = {}

	# randomly weight the edges
	for u,v in G.edges_iter():
		w = random.randrange(10)
		G[u][v]['weight'] = w
		if w in halfEdges:
			halfEdges[w].append(v)
			halfEdges[w].append(u)
		else:
			halfEdges[w] = [v,u]

	heCopy = copy.deepcopy(halfEdges)
	for k,v in heCopy.iteritems():
		random.shuffle(v)

	GRand = nx.Graph()
	keys = heCopy.keys()
	newEdges = { k : [] for k in keys }
	while len(keys) > 0:
		kind = random.randrange(len(keys))
		k = keys[kind]
		endpoints = heCopy[k]
		if len(endpoints) == 0:
			del keys[kind]
			continue
		else:
			uind = random.randrange(len(endpoints))
			u = endpoints[uind]
			foundEdge = False
			while not foundEdge:
				vopts = filter( lambda i: endpoints[i] != u and (not GRand.has_edge(u,endpoints[i])), xrange(len(endpoints)) )
				if len(vopts) == 0:
   				    eind = random.randrange(len(newEdges[k]))
   				    w,z = newEdges[k][eind]
   				    del newEdges[k][eind]
   				    GRand.remove_edge(w,z)
   				    endpoints.append(w)
   				    endpoints.append(z)
   				else:
   					vind = random.choice( vopts )				
   					v = endpoints[vind]
   					foundEdge = True

			del endpoints[uind]
			if vind < uind:
				del endpoints[vind]
			else:
				del endpoints[vind-1]

			GRand.add_edge(u,v,weight=k)
			edge = (u,v) if u < v else (v,u)
			newEdges[k].append(edge)

			print(GRand.size(), G.size())

	print(GRand.size())

if __name__ == "__main__":
	main()