Tabs => spaces (where did tabs come from?)

WeightedConfigSampler.py

import networkx as nx
import random
import copy

def isValidPair(G, Gp):
  '''
  This function checks if the weighted, undirected graphs G and Gp
  constitute a valid pair.
  G and Gp constitute a valid pair if, for every vertex u in G and Gp,
  the multiset of weights for u is the same in both graphs.
  This function returns True if (G,Gp) constitutes a valid pair and False
  otherwise.
  '''
  if not G.size() == Gp.size(): return False
	
  for u in G.nodes_iter():
		# assert that G(u) & Gp(v) have the same multiset of edge weights
		weights = sorted([ G[u][v]['weight'] for v in G.neighbors(u) ])
		weightsPrime = sorted([ Gp[u][v]['weight'] for v in Gp.neighbors(u) ])
		for i in xrange(len(weights)):
			if weights[i] != weightsPrime[i]: return False

  return True

def main():
  density = 0.1
  N = 100
  G = nx.gnm_random_graph( N, density * ( N*(N-1) / 2.0 ) )
	
  # Map from each weight to the potential endpoints (with multiplicity) having this weight
  halfEdges = {}

  # randomly weight the edges in the original graph
  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]

  # make a copy of the half edge map (since we'll destroy it)
  heCopy = copy.deepcopy(halfEdges)
  for k,v in heCopy.iteritems():
    # randomize the endpoints
  	random.shuffle(v)

  # our new, random graph
  GRand = nx.Graph()
  keys = heCopy.keys()
  # keep track of the edges in the new graph by their weight
  newEdges = { k : [] for k in keys }

  # while we have edges left to add
  while len(keys) > 0:
    # pick a random weight
  	kind = random.randrange(len(keys))
  	k = keys[kind]
  	endpoints = heCopy[k]
    # if we have nothing left of this weight, then remove the key
    # and move on to the next iteration
  	if len(endpoints) == 0:
  		del keys[kind]
  		continue
  	else:
      # pick one random endpoing
  		uind = random.randrange(len(endpoints))
  		u = endpoints[uind]
  		foundEdge = False
  		while not foundEdge:
        # our options for the other endpoint of this edge
        # it must be different from u and it must not form a duplicate of an existing edge
  			vopts = filter( lambda i: endpoints[i] != u and (not GRand.has_edge(u,endpoints[i])), xrange(len(endpoints)) )
  			if len(vopts) == 0:
          # If we have no options, then we've gotten "stuck" by an earlier decision.
          # To avoid remaining "stuck", we undo previous edges of this weight, inserting
          # their endpoints back into the set of valid endpoints until we can get unstuck
  				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:
          # Otherwise, we found a satisfactory option
  				vind = random.choice( vopts )				
  				v = endpoints[vind]
  				foundEdge = True

    # delete this u & v from the set of endpoints
		del endpoints[uind]
		if vind < uind:
			del endpoints[vind]
		else:
			del endpoints[vind-1]

    # add the edge {u,v} to the graph with the correct weight
		GRand.add_edge(u,v,weight=k)
    # add the edge to our map of new edges
		edge = (u,v) if u < v else (v,u)
		newEdges[k].append(edge)

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

  # print the size of the final graph
  print(GRand.size())
  # assert that the original graph and our new random graph 
  # constitute a "valid" pair.
  assert( isValidPair(G, GRand) )

if __name__ == "__main__":
	main()