def obtain_graph(args):
        """Build a Graph according to command line arguments

        Arguments:
        - `args`: command line options
        """
        if hasattr(args,'gnd') and args.gnd:

            n,d = args.gnd
            if (n*d)%2 == 1:
                raise ValueError("n * d must be even")
            G=networkx.random_regular_graph(d,n)
            return G

        elif hasattr(args,'gnp') and args.gnp:

            n,p = args.gnp
            G=networkx.gnp_random_graph(n,p)

        elif hasattr(args,'gnm') and args.gnm:

            n,m = args.gnm
            G=networkx.gnm_random_graph(n,m)

        elif hasattr(args,'grid') and args.grid:

            G=networkx.grid_graph(args.grid)

        elif hasattr(args,'torus') and args.torus:
            
            G=networkx.grid_graph(args.torus,periodic=True)

        elif hasattr(args,'complete') and args.complete>0:

            G=networkx.complete_graph(args.complete)

        elif args.graphformat:

            G=readGraph(args.input,args.graphformat)
        else:
            raise RuntimeError("Invalid graph specification on command line")

        # Graph modifications
        if hasattr(args,'plantclique') and args.plantclique>1:

            clique=random.sample(G.nodes(),args.plantclique)

            for v,w in combinations(clique,2):
                G.add_edge(v,w)

        # Output the graph is requested
        if hasattr(args,'savegraph') and args.savegraph:
            writeGraph(G,
                       args.savegraph,
                       args.graphformat,
                       graph_type='simple')

        return G

    def test_navigable_small_world(self):
        G = nx.navigable_small_world_graph(5, p=1, q=0)
        gg = nx.grid_2d_graph(5, 5).to_directed()
        assert_true(nx.is_isomorphic(G, gg))

        G = nx.navigable_small_world_graph(5, p=1, q=0, dim=3)
        gg = nx.grid_graph([5, 5, 5]).to_directed()
        assert_true(nx.is_isomorphic(G, gg))

        G = nx.navigable_small_world_graph(5, p=1, q=0, dim=1)
        gg = nx.grid_graph([5]).to_directed()
        assert_true(nx.is_isomorphic(G, gg))

    def obtain_graph(args,suffix=""):
        """Build a Graph according to command line arguments

        Arguments:
        - `args`: command line options
        """
        if getattr(args,'gnd'+suffix) is not None:

            n,d = getattr(args,'gnd'+suffix)
            if (n*d)%2 == 1:
                raise ValueError("n * d must be even")
            G=networkx.random_regular_graph(d,n)

        elif getattr(args,'gnp'+suffix) is not None:

            n,p = getattr(args,'gnp'+suffix)
            G=networkx.gnp_random_graph(n,p)

        elif getattr(args,'gnm'+suffix) is not None:

            n,m = getattr(args,'gnm'+suffix)
            G=networkx.gnm_random_graph(n,m)

        elif getattr(args,'grid'+suffix) is not None:

            G=networkx.grid_graph(getattr(args,'grid'+suffix))

        elif getattr(args,'torus'+suffix) is not None:
            
            G=networkx.grid_graph(getattr(args,'torus'+suffix),periodic=True)

        elif getattr(args,'complete'+suffix) is not None:

            G=networkx.complete_graph(getattr(args,'complete'+suffix))

        elif getattr(args,'empty'+suffix) is not None:

            G=networkx.empty_graph(getattr(args,'empty'+suffix))

        elif getattr(args,'graphformat'+suffix) is not None:

            try:
                print("INFO: reading simple graph {} from '{}'".format(suffix,getattr(args,"input"+suffix).name),
                      file=sys.stderr)
                G=readGraph(getattr(args,'input'+suffix),
                            "simple",
                            getattr(args,'graphformat'+suffix))
            except ValueError,e:
                print("ERROR ON '{}'. {}".format(
                    getattr(args,'input'+suffix).name,e),
                      file=sys.stderr)
                exit(-1)

def anneal_bdst(n=11, depth=10, phases=10, iters=1000):
    """ MCMC/simulated annealing to generate a random bounded-depth spanning tree
    Parameters
    ----------
    n : int, size of grid
    depth : int, optional, target bound on depth

    Returns
    -------
    T : nx.Graph, spanning tree with T.base_graph, possibly with degree bound satisfied
    """

    beta = pm.Uninformative('beta', value=1.)

    G = nx.grid_graph([n, n])
    root = ((n-1)/2, (n-1)/2)
    bdst = BDST(G, root, depth, beta)

    @pm.deterministic
    def max_depth(T=bdst, root=root):
        shortest_path_length = nx.shortest_path_length(T, root)
        T.max_depth = max(shortest_path_length.values())
        return T.max_depth

    mod_mc = pm.MCMC([beta, bdst, max_depth])
    mod_mc.use_step_method(STMetropolis, bdst)
    mod_mc.use_step_method(pm.NoStepper, beta)

    for i in range(phases):
        beta.value = i*5
        mod_mc.sample(iters, thin=max(1, iters/100))
        print('cur depth', max_depth.value)
        print('pct of trace with max_depth <= depth', np.mean(mod_mc.trace(max_depth)[:] <= depth))
    return bdst.value

def graph_example_1():
    G = nx.convert_node_labels_to_integers(nx.grid_graph([5, 5]),
                                           label_attribute='labels')
    rlabels = nx.get_node_attributes(G, 'labels')
    labels = {v: k for k, v in rlabels.items()}

    for nodes in [(labels[(0, 0)], labels[(1, 0)]),
                  (labels[(0, 4)], labels[(1, 4)]),
                  (labels[(3, 0)], labels[(4, 0)]),
                  (labels[(3, 4)], labels[(4, 4)])]:
        new_node = G.order() + 1
        # Petersen graph is triconnected
        P = nx.petersen_graph()
        G = nx.disjoint_union(G, P)
        # Add two edges between the grid and P
        G.add_edge(new_node + 1, nodes[0])
        G.add_edge(new_node, nodes[1])
        # K5 is 4-connected
        K = nx.complete_graph(5)
        G = nx.disjoint_union(G, K)
        # Add three edges between P and K5
        G.add_edge(new_node + 2, new_node + 11)
        G.add_edge(new_node + 3, new_node + 12)
        G.add_edge(new_node + 4, new_node + 13)
        # Add another K5 sharing a node
        G = nx.disjoint_union(G, K)
        nbrs = G[new_node + 10]
        G.remove_node(new_node + 10)
        for nbr in nbrs:
            G.add_edge(new_node + 17, nbr)
        G.add_edge(new_node + 16, new_node + 5)

    G.name = 'Example graph for connectivity'
    return G

    def __init__(self, dim=None, phi=np.pi, periodic=True, phases=None):
        if not dim: dim = [4, 4]
        dim = copy(dim)
        self.dim = copy(dim)
        self.nspins = np.prod(dim)

        self.G = nx.grid_graph(dim, periodic)

        if phases is not None:
            self.phases = phases
        else:
            self.phases = dict()
            binary_disorder = True
            if binary_disorder:
                for edge in self.G.edges():
                    self.phases[edge] = phi * np.random.random_integers(0, 1)
            else:
                for edge in self.G.edges():
                    self.phases[edge] = np.random.uniform(-phi, phi)
        nx.set_edge_attributes(self.G, "phase", self.phases)

        self.indices = dict()
        self.index2node = dict()
        nodes = sorted(self.G.nodes())
        for i, node in enumerate(nodes):
            self.indices[node] = i
            self.index2node[i] = node

        self.num_edges = self.G.number_of_edges()

        self.set_up_neighborlists()

def spanning_1d_chain(length):
    """
    Generate a linear chain with auxiliary nodes for spanning cluster detection

    Parameters
    ----------

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

    Returns
    -------

    networkx.Graph
       A linear chain graph with auxiliary nodes for spanning cluster detection

    See Also
    --------

    sample_states : spanning cluster detection

    """
    ret = nx.grid_graph(dim=[int(length + 2)])

    ret.node[0]['span'] = 0
    ret[0][1]['span'] = 0
    ret.node[length + 1]['span'] = 1
    ret[length][length + 1]['span'] = 1

    return ret

def make_grid_graph(dim, periodic=True):
    """
    this is a wrapper for nx.grid_graph() which replaces the node definition
    
    grid_graph creates a graph where the nodes are tuples (ix, iy, ...) 
    where ix and iy are the x and y positions of the site.  It would be more useful to
    have the nodes be simple integers that could act as indices for lists and arrays.
    The spatial positions will be returned in a separate dict
    """
    G = nx.grid_graph(dim, periodic=periodic)
    Gnew = nx.Graph()
    spatial = dict()
    node2i = dict()
    

    for i, node in enumerate(G.nodes()):
        Gnew.add_node(i)
        spatial[i] = node
        node2i[node] = i
    
    for edge in G.edges(data=False):
        u = node2i[edge[0]]
        v = node2i[edge[1]]
        Gnew.add_edge(u, v)
    
    return Gnew, spatial

    def setup_space(self):
        """
        Method to setup our space.
        """
        # Initialize a space with a grid network
        self.g = nx.grid_graph(dim=self.size)
        self.g=self.g.to_directed()
        
        # Set Pheromones
        print 'Setting up network'
        capacity_pheromone_list=[self.initial_pheromone]*len(self.capacities[0])*2
        capacity_pheromone_list.extend([self.initial_pheromone]*len(self.capacities[1])*2)
        for e in self.g.edges_iter():
            self.g.add_edge(e[0],e[1],max_capacity=self.edge_capacity)
            self.g.add_edge(e[0],e[1],capacity=0) #initial capacity 
            self.g.add_edge(e[0],e[1],edge_pheromone=[self.initial_pheromone]*2*2) #pheromone per edge
            self.g.add_edge(e[0],e[1],capacity_pheromone=capacity_pheromone_list) #pheromone per capacity
            
        for n in self.g.nodes_iter():
            neighbors_n=self.g.neighbors(n)
            
            branch_pheromone_list=[]
            branch_pheromone_list=[self.initial_pheromone]
            branch_pheromone_list.extend([self.initial_pheromone*.5]*(len(neighbors_n)-1))
            self.g.add_node(n,branch_pheromone=branch_pheromone_list*2*2)

            termination_pheromone_list=[self.initial_termination*0.25,self.initial_termination]*2*2
            self.g.add_node(n,termination_pheromone=termination_pheromone_list)

        # Set layout    
        self.g_layout = nx.spectral_layout(self.g)

def get_graph_from_image(image): 
  grid = nx.grid_graph(dim=list(image.shape[:2])) 

  for u,v,d in grid.edges(data=True):
    d['weight'] = np.abs(image[u] - image[v])*255
 
  return grid 

def generate_grid_graph():
    """Generates k cuts for grid graphs"""
    k = int(input("k for grid graph:"))
    trials = int(input("number of trials:"))
    gridfname = input("output file:")
    gridfname = "hard_instances/" + gridfname
    gridfile = open(gridfname, "wb", 0)
    n = int(input("Number of dimensions: "))
    d = []
    for i in range(0, n):
        tmp = int(input("Size of dimension " + str(i + 1) + ": "))
        d.append(tmp)
    G = nx.grid_graph(dim=d)
    A = nx.adjacency_matrix(G).toarray()
    L = nx.normalized_laplacian_matrix(G).toarray()
    (tmpw, tmpv) = la.eigh(L, eigvals=(0, 1))
    tmp = 2 * math.sqrt(tmpw[1])
    print("cheeger upperbound:" + str(tmp))
    (w, v) = spectral_projection(L, k)
    lambda_k = w[k - 1]
    k_cuts_list = lrtv(A, v, k, lambda_k, trials, gridfile)
    plotname = gridfname + "plot"
    plot(k_cuts_list, plotname)
    tmp_str = "Grid graph of dimension: " + str(d) + "\n"
    tmp_str += "k = " + str(k) + ", "
    tmp_str += "trials = " + str(trials) + "\n\n\n"
    tmp_str = tmp_str.encode("utf-8")
    gridfile.write(tmp_str)
    for i in range(len(k_cuts_list)):
        k_cuts = k_cuts_list[i]
        tmp_str = list(map(str, k_cuts))
        tmp_str = " ".join(tmp_str)
        tmp_str += "\n\n"
        tmp_str = tmp_str.encode("utf-8")
        gridfile.write(tmp_str)

def main(plot=True):
    # make a graph representing a lattice in two dimensions
    dim = [10,10]
    grid_graph = nx.grid_graph(dim, periodic=False)
    A = [(0,0)]
    B = [(dim[0]-1, dim[1]-1)]
    
    # make some random rates for each of the edges
    rates = dict()
    for u, v in grid_graph.edges_iter():
        rates[(u,v)] = np.random.rand()
        rates[(v,u)] = np.random.rand()
        
    
    # set up the graph reduction object
    reducer = GraphReduction(rates, A, B)
    
    
    # make the kmc graph from the rates
    kmc_graph = kmcgraph_from_rates(rates)
    com_prob = reducer.compute_committor_probabilities(kmc_graph.nodes())

    if plot:    
        # put it into matrix form and plot
        P = np.zeros(dim)
        for node, p in com_prob.iteritems():
            x, y = node
            P[x,y] = p
        import matplotlib.pyplot as plt
        
        plt.imshow(P, cmap="BrBG", vmin=0, vmax=1)
        plt.title("probability of a trajectory reaching the lower right corner\n before reaching the upper left")
        plt.colorbar()
        plt.show()

def square_lattice_model(D=3, N_side=4):

    lattice_dimensions = []
    for _ in range(D):
        lattice_dimensions.append(N_side)
   
    G = nx.grid_graph(lattice_dimensions)
    edges = G.edges()
    G.remove_edges_from(edges)
    G = G.to_directed()

    bottom_corner = []
    top_corner = []
    for _ in range(D):
        bottom_corner.append(0)
        top_corner.append(N_side-1)
        
    extremes = [bottom_corner, top_corner]
    for j in range(len(extremes)):
        extremes[j] = tuple(extremes[j])

    for node_a in G.nodes():
        for node_b in G.nodes():
            if lattice_check(node_a, node_b, D):
                G.add_edge(node_a, node_b)

    return [G,extremes]

 def generateLattice(self):
     edgeCounter = 0
     maxEdges = self.__dimension * 2 * (self.__size ** self.__dimension)
     
     # A grid graph forming the lattices
     dimGrid = []
     for i in range(self.__dimension):
         dimGrid.append(self.__size)
     G = nx.grid_graph(dimGrid)
     print 'Gridgraph constructed! size = ' + str(self.__size) 
     
     # use a classic Bi-directional graph
     print 'start adding a Stairway to Heaven '
     oldcounter = 0
     for e in G.edges_iter():
         edgeCounter+=1
         ec = edgeCounter/1000
         if ec > oldcounter:
             print '.';
             oldcounter += ec
         self.__GD.add_node(e[0], consumed=False, counter=0)
         self.__GD.add_node(e[1], consumed=False, counter=0)
         if self.__GD.has_edge(e[0], e[1]) == False:
             self.__GD.add_edge(e[0], e[1], vdir=np.array(e[0]) - np.array(e[1]),SA= False,New=True)
             
         if self.__GD.has_edge(e[1], e[0]) == False:
             self.__GD.add_edge(e[1], e[0], vdir=np.array(e[1]) - np.array(e[0]),SA=False,New=True)
     print 'clearing original graph!'
     G.clear()    

def GridGraph(dim_list):
    """
    Returns an n-dimensional grid graph.

    INPUT:


    -  ``dim_list`` - a list of integers representing the
       number of nodes to extend in each dimension.


    PLOTTING: When plotting, this graph will use the default
    spring-layout algorithm, unless a position dictionary is
    specified.

    EXAMPLES::

        sage: G = graphs.GridGraph([2,3,4])
        sage: G.show()  # long time

    ::

        sage: C = graphs.CubeGraph(4)
        sage: G = graphs.GridGraph([2,2,2,2])
        sage: C.show()  # long time
        sage: G.show()  # long time
    """
    import networkx
    dim = [int(a) for a in dim_list]
    G = networkx.grid_graph(dim)
    return graph.Graph(G, name="Grid Graph for %s"%dim)

def torrents_and_ferraro_graph():
    G = nx.convert_node_labels_to_integers(nx.grid_graph([5, 5]),
                                           label_attribute='labels')
    rlabels = nx.get_node_attributes(G, 'labels')
    labels = {v: k for k, v in rlabels.items()}

    for nodes in [(labels[(0, 4)], labels[(1, 4)]),
                  (labels[(3, 4)], labels[(4, 4)])]:
        new_node = G.order() + 1
        # Petersen graph is triconnected
        P = nx.petersen_graph()
        G = nx.disjoint_union(G, P)
        # Add two edges between the grid and P
        G.add_edge(new_node + 1, nodes[0])
        G.add_edge(new_node, nodes[1])
        # K5 is 4-connected
        K = nx.complete_graph(5)
        G = nx.disjoint_union(G, K)
        # Add three edges between P and K5
        G.add_edge(new_node + 2, new_node + 11)
        G.add_edge(new_node + 3, new_node + 12)
        G.add_edge(new_node + 4, new_node + 13)
        # Add another K5 sharing a node
        G = nx.disjoint_union(G, K)
        nbrs = G[new_node + 10]
        G.remove_node(new_node + 10)
        for nbr in nbrs:
            G.add_edge(new_node + 17, nbr)
        # Commenting this makes the graph not biconnected !!
        # This stupid mistake make one reviewer very angry :P
        G.add_edge(new_node + 16, new_node + 8)

    for nodes in [(labels[(0, 0)], labels[(1, 0)]),
                  (labels[(3, 0)], labels[(4, 0)])]:
        new_node = G.order() + 1
        # Petersen graph is triconnected
        P = nx.petersen_graph()
        G = nx.disjoint_union(G, P)
        # Add two edges between the grid and P
        G.add_edge(new_node + 1, nodes[0])
        G.add_edge(new_node, nodes[1])
        # K5 is 4-connected
        K = nx.complete_graph(5)
        G = nx.disjoint_union(G, K)
        # Add three edges between P and K5
        G.add_edge(new_node + 2, new_node + 11)
        G.add_edge(new_node + 3, new_node + 12)
        G.add_edge(new_node + 4, new_node + 13)
        # Add another K5 sharing two nodes
        G = nx.disjoint_union(G, K)
        nbrs = G[new_node + 10]
        G.remove_node(new_node + 10)
        for nbr in nbrs:
            G.add_edge(new_node + 17, nbr)
        nbrs2 = G[new_node + 9]
        G.remove_node(new_node + 9)
        for nbr in nbrs2:
            G.add_edge(new_node + 18, nbr)
    return G

def creaRed(Nodos,TipoNodos):
    global g,numNodos, numTipoNodos
    numNodos=Nodos
    numTipoNodos=TipoNodos
    g=nx.grid_graph(dim=[numNodos,numNodos], periodic=True)
    for i in g.nodes_iter():
        g.node[i]['tipo']=rd.choice(range(numTipoNodos))
    return g

 def __init__(self, n):
     """ Create a new cubic lattice with given linear dimension.
     Final number of nodes will be n**3.
     """
     self.G = nx.grid_graph([n, n, n])
     self.G = nx.convert_node_labels_to_integers(self.G, label_attribute="pos")
     self._find_cycle_basis()
     self._find_cycle_dual()

    def test_grid_graph(self):
        """grid_graph([n,m]) is a connected simple graph with the
        following properties:
        number_of_nodes = n*m
        degree_histogram = [0,0,4,2*(n+m)-8,(n-2)*(m-2)]
        """
        for n, m in [(3, 5), (5, 3), (4, 5), (5, 4)]:
            dim = [n, m]
            g = nx.grid_graph(dim)
            assert_equal(len(g), n*m)
            assert_equal(nx.degree_histogram(g), [0, 0, 4, 2 * (n + m) - 8,
                                                  (n - 2) * (m - 2)])

        for n, m in [(1, 5), (5, 1)]:
            dim = [n, m]
            g = nx.grid_graph(dim)
            assert_equal(len(g), n*m)
            assert_true(nx.is_isomorphic(g, nx.path_graph(5)))

def anneal_w_graphics(n=11, depth=10):
    """ Make an animation of the BDST chain walking on an nxn grid and play it
    """
    ni = 5
    nj = 100
    nk = 5

    beta = mc.Uninformative('beta', value=1.)

    G = nx.grid_graph([n, n])
    G.orig_pos = dict([[v, v] for v in G.nodes_iter()])
    G.pos = dict([[v, v] for v in G.nodes_iter()])

    root = (5,5)
    bdst = BDST(G, root, depth, beta)

    mod_mc = mc.MCMC([beta, bdst])
    mod_mc.use_step_method(STMetropolis, bdst)
    mod_mc.use_step_method(mc.NoStepper, beta)

    for i in range(ni):
        beta.value = i*5
        for j in range(nj):
            mod_mc.sample(1)
            T = bdst.value
            
            for k in range(nk):
                if random.random() < .95:
                    delta_pos = nx.spring_layout(T, pos=G.pos, fixed=[root], iterations=1)
                else:
                    delta_pos = G.orig_pos
                eps=.01
                my_avg = lambda x, y: (x[0]*(1.-eps) + y[0]*eps, x[1]*(1.-eps)+y[1]*eps)
                for v in G.pos:
                    G.pos[v] = my_avg(G.pos[v], delta_pos[v])
                views.plot_graph_and_tree(G, T, time=1.*k/nk)
                str = ''
                str += ' beta: %.1f\n' % beta.value
                str += ' cur depth: %d (target: %d)\n' % (T.depth, depth)
                sm = mod_mc.step_method_dict[bdst][0]
                str += ' accepted: %d of %d\n' % (sm.accepted, sm.accepted + sm.rejected)
                plt.figtext(0, 0, str)
                plt.figtext(1, 0, 'healthyalgorithms.wordpress.com \n', ha='right')
                plt.axis([-1, n, -1, n])
                plt.axis('off')
                plt.subplots_adjust(0, 0, 1, 1)
                plt.savefig('bdst%06d.png' % (i*nj*nk + j*nk + k))
            print 'accepted:', mod_mc.step_method_dict[bdst][0].accepted

    import subprocess
    subprocess.call('mencoder mf://bdst*.png -mf w=800:h=600 -ovc x264 -of avi -o bdst_G_%d_d_%d.avi' % (n, depth), shell=True)
    subprocess.call('mplayer -loop 0 bdst_G_%d_d_%d.avi' % (n, depth), shell=True)
    subprocess.call('rm bdst*.png')

    return bdst.value