def setUp(self):
        G1 = cnlti(nx.grid_2d_graph(2, 2), first_label=0, ordering="sorted")
        G2 = cnlti(nx.lollipop_graph(3, 3), first_label=4, ordering="sorted")
        G3 = cnlti(nx.house_graph(), first_label=10, ordering="sorted")
        self.G = nx.union(G1, G2)
        self.G = nx.union(self.G, G3)
        self.DG = nx.DiGraph([(1, 2), (1, 3), (2, 3)])
        self.grid = cnlti(nx.grid_2d_graph(4, 4), first_label=1)

        self.gc = []
        G = nx.DiGraph()
        G.add_edges_from([(1, 2), (2, 3), (2, 8), (3, 4), (3, 7), (4, 5),
                          (5, 3), (5, 6), (7, 4), (7, 6), (8, 1), (8, 7)])
        C = [[3, 4, 5, 7], [1, 2, 8], [6]]
        self.gc.append((G, C))

        G = nx.DiGraph()
        G.add_edges_from([(1, 2), (1, 3), (1, 4), (4, 2), (3, 4), (2, 3)])
        C = [[2, 3, 4],[1]]
        self.gc.append((G, C))

        G = nx.DiGraph()
        G.add_edges_from([(1, 2), (2, 3), (3, 2), (2, 1)])
        C = [[1, 2, 3]]
        self.gc.append((G,C))

        # Eppstein's tests
        G = nx.DiGraph({0:[1], 1:[2, 3], 2:[4, 5], 3:[4, 5], 4:[6], 5:[], 6:[]})
        C = [[0], [1], [2],[ 3], [4], [5], [6]]
        self.gc.append((G,C))

        G = nx.DiGraph({0:[1], 1:[2, 3, 4], 2:[0, 3], 3:[4], 4:[3]})
        C = [[0, 1, 2], [3, 4]]
        self.gc.append((G, C))

def generate_connection_graph(graph_type, params, count):
    lower_type = graph_type.lower()
    if lower_type == 'complete':
        assert (len(params) == 0)
        return networkx.complete_graph(count)
    elif lower_type == 'complete-bipartite':
        assert (len(params) == 2)
        assert (int(params[0]) > 0.0)
        assert (int(params[1]) > 0.0)
        n1 = int(round(count * float(params[0]) / float(params[1])))
        n2 = int(round(count * float(params[1]) / float(params[0])))
        n1 = 1 if n1 < 1 else n1
        n2 = 1 if n2 < 1 else n2
        return networkx.complete_bipartite_graph(n1, n2)
    elif lower_type == 'circular-ladder':
        assert (len(params) == 0)
        return networkx.circular_ladder_graph(count)
    elif lower_type == 'cycle':
        assert (len(params) == 0)
        return networkx.cycle_graph(count)
    elif lower_type == 'periodic-2grid':
        assert (len(params) == 2)
        assert (int(params[0]) > 0.0)
        assert (int(params[1]) > 0.0)
        width = int(round(math.sqrt(count * float(params[0]) / float(params[1]))))
        height = int(round(math.sqrt(count * float(params[1]) / float(params[0]))))
        width = 1 if width < 1 else width
        height = 1 if height < 1 else height
        return networkx.grid_2d_graph(width, height, True)
    elif lower_type == 'nonperiodic-2grid':
        assert (len(params) == 2)
        assert (int(params[0]) > 0.0)
        assert (int(params[1]) > 0.0)
        width = int(round(math.sqrt(count * float(params[0]) / float(params[1]))))
        height = int(round(math.sqrt(count * float(params[1]) / float(params[0]))))
        width = 1 if width < 1 else width
        height = 1 if height < 1 else height
        return networkx.grid_2d_graph(width, height, False)
    elif lower_type == 'hypercube':
        assert (len(params) == 0)
        return networkx.hypercube_graph(int(round(math.log(count, 2))))
    elif lower_type == 'star':
        assert (len(params) == 0)
        return networkx.star_graph(count - 1)
    elif lower_type == 'wheel':
        assert (len(params) == 0)
        return networkx.wheel_graph(count)
    elif lower_type == 'erdos-reyni':
        assert (len(params) == 1)
        return networkx.erdos_renyi_graph(count, float(params[0]))
    elif lower_type == 'watts-strogatz':
        assert (len(params) == 2)
        if int(params[0]) >= count / 2:
            k = int(count / 2 - 1)
        else:
            k = int(params[0])
        return networkx.connected_watts_strogatz_graph(count, k, int(params[1]))
    else:
        print "Unknown graph type {}".format(lower_type)
        assert False

 def setUp(self):
     G1=cnlti(nx.grid_2d_graph(2,2),first_label=0,ordering="sorted")
     G2=cnlti(nx.lollipop_graph(3,3),first_label=4,ordering="sorted")
     G3=cnlti(nx.house_graph(),first_label=10,ordering="sorted")
     self.G=nx.union(G1,G2)
     self.G=nx.union(self.G,G3)
     self.DG=nx.DiGraph([(1,2),(1,3),(2,3)])
     self.grid=cnlti(nx.grid_2d_graph(4,4),first_label=1)

 def test_node_input(self):
     G = nx.grid_2d_graph(4, 2, periodic=True)
     H = nx.grid_2d_graph(range(4), range(2), periodic=True)
     assert_true(nx.is_isomorphic(H, G))
     H = nx.grid_2d_graph("abcd", "ef", periodic=True)
     assert_true(nx.is_isomorphic(H, G))
     G = nx.grid_2d_graph(5, 6)
     H = nx.grid_2d_graph(range(5), range(6))
     assert_edges_equal(H, G)

    def test_periodic(self):
        G = nx.grid_2d_graph(0, 0, periodic=True)
        assert_equal(dict(G.degree()), {})

        for m, n, H in [(2, 2, nx.cycle_graph(4)), (1, 7, nx.cycle_graph(7)),
                        (7, 1, nx.cycle_graph(7)),
                        (2, 5, nx.circular_ladder_graph(5)),
                        (5, 2, nx.circular_ladder_graph(5)),
                        (2, 4, nx.cubical_graph()),
                        (4, 2, nx.cubical_graph())]:
            G = nx.grid_2d_graph(m, n, periodic=True)
            assert_true(nx.could_be_isomorphic(G, H))

    def __init__(self, input, theta=0.3, threshold=0.1):
        self.input = input
        self.shape = self.input.shape
        self.theta = theta
        self.threshold = threshold

        self.visible = nx.grid_2d_graph(self.shape[0], self.shape[1])
        self.hidden = nx.grid_2d_graph(self.shape[0], self.shape[1])

        for n in self.nodes():
            self.visible[n]['value'] = self.input[n[0], n[1]]
            f = lambda: np.array([1.0, 1.0])
            self.hidden[n]['messages'] = defaultdict(f)

def run_with_q(q):
    G = nx.grid_2d_graph(N,N)
#    draw_lattice(G)

    # Generate traits
    traits = {}
    for node in G:
        trait_values = []
        for i in range(F):        
            trait_values.append(random.randint(1,q))
        traits[node] = trait_values

    nx.set_node_attributes(G, 'traits', traits)
    edges = G.edges()
    potential_edges = get_potential_edges(G, edges)
    #print len(potential_edges)
    reached_stationary = False
    while not reached_stationary:
        run_cycle(G,potential_edges)
        if (len(potential_edges) == 0):
            reached_stationary = True
        #else:
            #print('Still %d more potential edges '% (len(potential_edges)))

    result = get_cultural_domains(G)    
    print result
    #print potential_edges
    draw_lattice(G,q)

    return result['percentage']

def grid_2d(dim):
    """Creates a 2d grid of dimension dim"""
    graph = nx.grid_2d_graph(dim, dim)

    for node in graph:
        graph.node[node]["asn"] = 1
        graph.node[node]["x"] = node[0] * 150
        graph.node[node]["y"] = node[1] * 150
        graph.node[node]["device_type"] = "router"
        graph.node[node]["platform"] = "cisco"
        graph.node[node]["syntax"] = "ios_xr"
        graph.node[node]["host"] = "internal"
        graph.node[node]["ibgp_role"] = "Peer"

    mapping = {node: "%s_%s" % (node[0], node[1]) for node in graph}
    # Networkx wipes data if remap with same labels
    nx.relabel_nodes(graph, mapping, copy=False)
    for src, dst in graph.edges():
        graph[src][dst]["type"] = "physical"
        # add global index for sorting

    SETTINGS["General"]["deploy"] = True
    SETTINGS["Deploy Hosts"]["internal"] = {"cisco": {"deploy": True}}

    return graph

    def test_others(self):
        (P, D) = nx.bellman_ford(self.XG, 's')
        assert_equal(P['v'], 'u')
        assert_equal(D['v'], 9)
        (P, D) = nx.goldberg_radzik(self.XG, 's')
        assert_equal(P['v'], 'u')
        assert_equal(D['v'], 9)

        G = nx.path_graph(4)
        assert_equal(nx.bellman_ford(G, 0),
                     ({0: None, 1: 0, 2: 1, 3: 2}, {0: 0, 1: 1, 2: 2, 3: 3}))
        assert_equal(nx.goldberg_radzik(G, 0),
                     ({0: None, 1: 0, 2: 1, 3: 2}, {0: 0, 1: 1, 2: 2, 3: 3}))
        assert_equal(nx.bellman_ford(G, 3),
                     ({0: 1, 1: 2, 2: 3, 3: None}, {0: 3, 1: 2, 2: 1, 3: 0}))
        assert_equal(nx.goldberg_radzik(G, 3),
                     ({0: 1, 1: 2, 2: 3, 3: None}, {0: 3, 1: 2, 2: 1, 3: 0}))

        G = nx.grid_2d_graph(2, 2)
        pred, dist = nx.bellman_ford(G, (0, 0))
        assert_equal(sorted(pred.items()),
                     [((0, 0), None), ((0, 1), (0, 0)),
                      ((1, 0), (0, 0)), ((1, 1), (0, 1))])
        assert_equal(sorted(dist.items()),
                     [((0, 0), 0), ((0, 1), 1), ((1, 0), 1), ((1, 1), 2)])
        pred, dist = nx.goldberg_radzik(G, (0, 0))
        assert_equal(sorted(pred.items()),
                     [((0, 0), None), ((0, 1), (0, 0)),
                      ((1, 0), (0, 0)), ((1, 1), (0, 1))])
        assert_equal(sorted(dist.items()),
                     [((0, 0), 0), ((0, 1), 1), ((1, 0), 1), ((1, 1), 2)])

def simulate():
  data = get_data()

  adjacency = data["adjacency"]
  t = 10
  t_f = 100
  t = np.linspace(0, t, num=t_f).astype(np.float32)

  # a = 0.
  # b = 100.
  # r = np.array([
  #     [a, 0.],
  #     [a+2.,0.],
  # ])
  # v = np.array([
  #     [0.,10.],
  #     [0., -10.],
  # ])
  #
  # w = np.array([
  #   [0,1],
  #   [1,0]
  # ]).astype(np.float32)

  n = 5
  G = nx.grid_2d_graph(n,n)
  N = 25
  w = nx.to_numpy_matrix(G)*10
  r = np.random.rand(N,3)
  d = r.shape[-1]
  v = r*0.
  k=1.
  return sim_particles(t,r,v,w)

def ex_1():
    '''Example 1 of the paper.

    A 2-by-20 grid with reflecting boundary condition and an obstacle in the
    middle.
    '''
    N = 20
    G = nx.grid_2d_graph(N,N)

    n_middle = (N/2, N/2)

    # Add reflecting boundary condition
    for i,j in G:
        if i == 0 or i == N-1 or j == 0 or j == N-1:
            G.add_edge((i,j), (i,j))
    
    # Remove edges of the node at the middle
    # (keep one edge, to simplify the bookiping
    for u,v in sorted(G.edges(n_middle))[:-1]:
        G.add_edge(v,v) # Add self loop
        G.remove_edge(u, v)

    T, _ = get_T(G)
    savemat('vf_ex1', {'T':T}, oned_as='column')
    return G

def build_grid(n, m, l=1):
    """
    See Random planar graphs and the London street network
    by A.P. Masuccia, D. Smith, A. Crooks, and M. Batty
    for further information.
    """
    result = networkx.grid_2d_graph(n, n)
    for a in result.nodes():
        result.node[a]['pos'] = (l * a[0], l * a[1])
    for e in result.edges():
        result.edge[e[0]][e[1]]['weight'] = l
    for i in range(m):
        e = choice(result.edges())
        sigma = result.edge[e[0]][e[1]]['weight']
        apos = (
            (result.node[e[0]]['pos'][0] + result.node[e[1]]['pos'][0]) / 2,
            (result.node[e[0]]['pos'][1] + result.node[e[1]]['pos'][1]) / 2
        )
        a = result.number_of_nodes()
        bpos = (
            apos[0] + (result.node[e[0]]['pos'][1] - result.node[e[1]]['pos'][1]) / 3,
            apos[1] + (result.node[e[0]]['pos'][0] - result.node[e[1]]['pos'][0]) / 3
        )
        result.add_node(a, pos=apos)
        result.add_node(a + 1, pos=bpos)
        result.add_edge(a, a + 1, weight=sigma / 3)
        result.add_edge(e[0], a, weight=sigma / 2)
        result.add_edge(e[1], a, weight=sigma / 2)
        result.remove_edge(e[0], e[1])
    return result

def spanning_2d_grid(length):
    """
    Generate a square lattice with auxiliary nodes for spanning detection

    Parameters
    ----------

    length : int
       Number of nodes in one dimension, excluding the auxiliary nodes.

    Returns
    -------

    networkx.Graph
       A square lattice graph with auxiliary nodes for spanning cluster
       detection

    See Also
    --------

    sample_states : spanning cluster detection

    """
    ret = nx.grid_2d_graph(length + 2, length)

    for i in range(length):
        # side 0
        ret.node[(0, i)]['span'] = 0
        ret[(0, i)][(1, i)]['span'] = 0

        # side 1
        ret.node[(length + 1, i)]['span'] = 1
        ret[(length + 1, i)][(length, i)]['span'] = 1

    return ret

 def makeCCGraph_grid2d(self):
     """Make 2D grid Capacity Constrained Graph"""
     if (self.seed != None):
         random.seed(self.seed)
     self.G = nx.grid_2d_graph(self.graph_shape[0],self.graph_shape[1])
     self.makeCCNodes()
     self.makeCCEdges()

def topologyInit(N, choice, Beta):
	'''Initializes a grid with N nodes distributed evenly on the map. The 
	map-file is files/Grid.xyz.
	The procedure evaluates the best possible coarsness to fit the desired
	number of nodes. Generates the full grid, associates height and position
	to the nodes and removes the node from the grid if it has 0 height. It then
	associates a weight with every link proportinal to 1+|Delta H|^(-40/13)
	Finally the resulting grid is out'''
	

	FRACTION=0.2796296296296296
	M=mapInfo("files/Grid.xyz")
	coarsnes = int(((float(N)/FRACTION)/(WIDTH*HEIGHT))**(0.5))
	print "Coarsness is : " + str(coarsnes)
	G = nx.grid_2d_graph(WIDTH*coarsnes, HEIGHT*coarsnes, True)
	listOfNodes = G.nodes()
	totalNum = len(listOfNodes)
	

	listOfPositions = M.getAll3dPos(G, coarsnes)
	listofGPS=[[element[0],element[1]] for element in listOfPositions]
	listOfHeights=[element[2] for element in listOfPositions]
	for i,x in enumerate(sorted(sorted(listOfNodes, key=itemgetter(0)), key=itemgetter(1), reverse=True)):
		G.node[x]['position']=listofGPS[i]
		G.node[x]['height']=listOfHeights[i]
	nodeColor=[]
	listOfNodes=[x for x in listOfNodes if float(G.node[x]['height']) == 0]
	G.remove_nodes_from(listOfNodes)
	print "The actual number of agents in this simulation will be " + str(len(G.nodes()))
	

	if choice == WEIGHTED:
		for edge in G.edges():
			G[edge[0]][edge[1]]['weight'] =  2.7**(-Beta*abs(G.node[edge[0]]['height'] - G.node[edge[1]]['height']))
			if DEBUG:
		   		print G[edge[0]][edge[1]]['weight']
			#print str(edge) + "\t" + str(G[edge[0]][edge[1]]['weight']) + str(G.node[edge[0]]['height']) + "\t" + str(G.node[edge[1]]['height'])
	else:
		for edge in G.edges():
			G[edge[0]][edge[1]]['weight']=1
	print "the number of edges in this simulation will be " + str(len(G.edges()))
	
	
	for x in G.nodes():
		nodeColor.append(int(G.node[x]['height']))
	#target = open("node_height", "w")
	#for x in range(len(nodeColor)):
	#	target.write(str(x)+"\t"+str(nodeColor[x])+"\n")
	if SHOW == 1:
		fig=plt.figure()
		elarge=[(u,v) for (u,v,d) in G.edges(data=True) if d['weight'] >=0.05]
		esmall=[(u,v) for (u,v,d) in G.edges(data=True) if d['weight'] <0.05]
		nx.draw_networkx_edges(G, pos={i:i for i in G.nodes()}, edgelist=elarge, width=2)
		nx.draw_networkx_edges(G, pos={i:i for i in G.nodes()}, edgelist=esmall, width=2, alpha=0.5,edge_color='b',style='dashed')
		nx.draw_networkx_nodes(G, pos={i:i for i in G.nodes()}, node_color=nodeColor, node_cmap=plt.cm.summer, node_size=20)
		plt.xlabel('X_grid identifier')
		plt.ylabel('Y_grid identifier')
		plt.title('The grid\nGenerated on the basis of given DEM')
		plt.show() # display
	return G

    def get_graph(self):
        lattice_coord_num = 4
        side_length = 0

        # The lattice size should be a perfect square, ideally, and is sqrt(population size)
        l = m.sqrt(self.simconfig.popsize)
        # get the fractional part of the result, because sqrt always returns a float, even if the number is technically an integer
        # so we have to test the fractional part, not check python types
        frac, integral = m.modf(l)
        if frac == 0.0:
            log.debug("Lattice model:  popsize %s, lattice will be %s by %s", self.simconfig.popsize, l, l)
            side_length = int(l)
        else:
            log.error("Lattice model: population size %s is not a perfect square", self.simconfig.popsize)
            exit(1)

        if self.simconfig.periodic == 1:
            p = True
            log.debug("periodic boundary condition selected")
        else:
            p = False

        model = nx.grid_2d_graph(side_length, side_length, periodic=p)
        # now convert the resulting graph to have simple nodenames to use as keys
        # We need to retain the original nodenames, because they're tuples which represent the position
        # of the node in the lattice.  So we first store them as attribution 'pos' and then convert
        for nodename in model.nodes():
            model.node[nodename]['pos'] = nodename

        g = nx.convert_node_labels_to_integers(model)
        return g

    def test_large(self):
        try:
            import networkx as nx
        except ImportError:
            return

        try:
            GraphSet.converters['to_graph'] = nx.Graph
            GraphSet.converters['to_edges'] = nx.Graph.edges

            g = nx.grid_2d_graph(8, 8)
            v00, v01, v10 = (0,0), (0,1), (1,0)

            GraphSet.set_universe(g)
            self.assertEqual(len(GraphSet.universe().edges()), 112)
#            self.assertEqual(GraphSet.universe().edges()[:2], [(v00, v01), (v00, v10)])

            gs = GraphSet({});
            gs -= GraphSet([nx.Graph([(v00, v01)]),
                            nx.Graph([(v00, v01), (v00, v10)])])
            self.assertEqual(gs.len(), 5192296858534827628530496329220094)

            i = 0
            for g in gs:
                if i > 100: break
                i += 1

            paths = GraphSet.paths((0, 0), (7, 7))
            self.assertEqual(len(paths), 789360053252)
        except:
            raise
        finally:
            GraphSet.converters['to_graph'] = lambda edges: edges
            GraphSet.converters['to_edges'] = lambda graph: graph

def grid_2d(dim):
    import networkx as nx
    graph = nx.grid_2d_graph(dim, dim)

    for n in graph:
        graph.node[n]['asn'] = 1
        graph.node[n]['x'] = n[0] * 150
        graph.node[n]['y'] = n[1] * 150
        graph.node[n]['device_type'] = 'router'
        graph.node[n]['platform'] = 'cisco'
        graph.node[n]['syntax'] = 'ios_xr'
        graph.node[n]['host'] = 'internal'
        graph.node[n]['ibgp_level'] = 0

    mapping = {n: "%s_%s" % (n[0], n[1]) for n in graph}
    nx.relabel_nodes(graph, mapping, copy=False) # Networkx wipes data if remap with same labels
    for index, (src, dst) in enumerate(graph.edges()):
        graph[src][dst]['type'] = "physical"
        graph[src][dst]['edge_id'] = "%s_%s_%s" % (index, src, dst) # add global index for sorting

    SETTINGS['General']['deploy'] = True
    SETTINGS['Deploy Hosts']['internal'] = {
        'cisco': {
        'deploy': True,
        },
    }

    return graph

def generate_graph(type = 'PL', n = 100, seed = 1.0, parameter = 2.1):
    if type == 'ER':
        G = nx.erdos_renyi_graph(n, p=parameter, seed=seed, directed=True)
        G = nx.DiGraph(G)
        G.remove_edges_from(G.selfloop_edges())
    elif type == 'PL':
        z = nx.utils.create_degree_sequence(n, nx.utils.powerlaw_sequence, exponent = parameter)
        while not nx.is_valid_degree_sequence(z):
            z = nx.utils.create_degree_sequence(n, nx.utils.powerlaw_sequence, exponent = parameter)
        G = nx.configuration_model(z)
        G = nx.DiGraph(G)
        G.remove_edges_from(G.selfloop_edges())
    elif type == 'BA':
        G = nx.barabasi_albert_graph(n, 3, seed=None)
        G = nx.DiGraph(G)
    elif type == 'grid':
        G = nx.grid_2d_graph(int(np.ceil(np.sqrt(n))), int(np.ceil(np.sqrt(n))))
        G = nx.DiGraph(G)
    elif type in ['facebook', 'enron', 'twitter', 'students', 'tumblr', 'facebookBig']:
        #print 'start reading'
        #_, G, _, _ = readRealGraph(os.path.join("..","..","Data", type+".txt"))
        _, G, _, _ = readRealGraph(os.path.join("..","Data", type+".txt"))
        print 'size of graph', G.number_of_nodes()
        #Gcc = sorted(nx.connected_component_subgraphs(G.to_undirected()), key = len, reverse=True)
        #print Gcc[0].number_of_nodes()
        #print 'num of connected components', len(sorted(nx.connected_component_subgraphs(G.to_undirected()), key = len, reverse=True))
        #exit()
        if G.number_of_nodes() > n:
            G = getSubgraph(G, n)
        #G = getSubgraphSimulation(G, n, infP = 0.3)
    #nx.draw(G)
    #plt.show()
    return G

    def test_dijkstra_predecessor(self):
        G = nx.path_graph(4)
        assert_equal(
            nx.dijkstra_predecessor_and_distance(G, 0), ({0: [], 1: [0], 2: [1], 3: [2]}, {0: 0, 1: 1, 2: 2, 3: 3})
        )
        G = nx.grid_2d_graph(2, 2)
        pred, dist = nx.dijkstra_predecessor_and_distance(G, (0, 0))
        assert_equal(
            sorted(pred.items()), [((0, 0), []), ((0, 1), [(0, 0)]), ((1, 0), [(0, 0)]), ((1, 1), [(0, 1), (1, 0)])]
        )
        assert_equal(sorted(dist.items()), [((0, 0), 0), ((0, 1), 1), ((1, 0), 1), ((1, 1), 2)])

        XG = nx.DiGraph()
        XG.add_weighted_edges_from(
            [
                ("s", "u", 10),
                ("s", "x", 5),
                ("u", "v", 1),
                ("u", "x", 2),
                ("v", "y", 1),
                ("x", "u", 3),
                ("x", "v", 5),
                ("x", "y", 2),
                ("y", "s", 7),
                ("y", "v", 6),
            ]
        )
        (P, D) = nx.dijkstra_predecessor_and_distance(XG, "s")
        assert_equal(P["v"], ["u"])
        assert_equal(D["v"], 9)