def grid_2d_graph(m,n,periodic=False,create_using=None):
    """ Return the 2d grid graph of mxn nodes,
        each connected to its nearest neighbors.
        Optional argument periodic=True will connect
        boundary nodes via periodic boundary conditions.
    """
    G=empty_graph(0,create_using)
    row_name, rows = m
    col_name, columns = n
    G.name="grid_2d_graph(%s, %s)"%(row_name, col_name)
    G.add_nodes_from( (i,j) for i in rows for j in columns )
    G.add_edges_from( ((i,j),(pi,j)) for pi,i in pairwise(rows) for j in columns )
    G.add_edges_from( ((i,j),(i,pj)) for i in rows for pj,j in pairwise(columns) )
    if G.is_directed():
        G.add_edges_from( ((pi,j),(i,j)) for pi,i in pairwise(rows) for j in columns )
        G.add_edges_from( ((i,pj),(i,j)) for i in rows for pj,j in pairwise(columns) )
    if periodic:
        if len(columns)>2:
            f = columns[0]
            l = columns[-1]
            G.add_edges_from( ((i,f),(i,l)) for i in rows )
            if G.is_directed():
                G.add_edges_from( ((i,l),(i,f)) for i in rows )
        if len(rows)>2:
            f = rows[0]
            l = rows[-1]
            G.add_edges_from( ((f,j),(l,j)) for j in columns )
            if G.is_directed():
                G.add_edges_from( ((l,j),(f,j)) for j in columns )
        G.name="periodic_grid_2d_graph(%s,%s)"%(m,n)
    return G

def validate_path(G, s, t, soln_len, path):
    assert_equal(path[0], s)
    assert_equal(path[-1], t)
    if not G.is_multigraph():
        computed = sum(G[u][v].get('weight', 1) for u, v in pairwise(path))
        assert_equal(soln_len, computed)
    else:
        computed = sum(min(e.get('weight', 1) for e in G[u][v].values())
                       for u, v in pairwise(path))
        assert_equal(soln_len, computed)

def grid_2d_graph(m, n, periodic=False, create_using=None):
    """Returns the two-dimensional grid graph.

    The grid graph has each node connected to its four nearest neighbors.

    Parameters
    ----------
    m, n : int or iterable container of nodes
        If an integer, nodes are from `range(n)`.
        If a container, elements become the coordinate of the nodes.

    periodic : bool (default: False)
        If this is ``True`` the nodes on the grid boundaries are joined
        to the corresponding nodes on the opposite grid boundaries.

    create_using : NetworkX graph (default: Graph())
        If provided this graph is cleared of nodes and edges and filled
        with the new graph. Usually used to set the type of the graph.

    Returns
    -------
    NetworkX graph
        The (possibly periodic) grid graph of the specified dimensions.

    """
    G = empty_graph(0, create_using)
    row_name, rows = m
    col_name, cols = n
    G.add_nodes_from((i, j) for i in rows for j in cols)
    G.add_edges_from(((i, j), (pi, j))
                     for pi, i in pairwise(rows) for j in cols)
    G.add_edges_from(((i, j), (i, pj))
                     for i in rows for pj, j in pairwise(cols))
    if periodic is True:
        if len(rows) > 2:
            first = rows[0]
            last = rows[-1]
            G.add_edges_from(((first, j), (last, j)) for j in cols)
        if len(cols) > 2:
            first = cols[0]
            last = cols[-1]
            G.add_edges_from(((i, first), (i, last)) for i in rows)
    # both directions for directed
    if G.is_directed():
        G.add_edges_from((v, u) for u, v in G.edges())

    # set name
    G.name = "grid_2d_graph(%s, %s)" % (row_name, col_name)
    if periodic is True:
        G.name = "periodic_" + G.name
    return G

def dag_longest_path_length(G, weight='weight', default_weight=1):
    """Returns the longest path length in a DAG

    Parameters
    ----------
    G : NetworkX DiGraph
        A directed acyclic graph (DAG)

    weight : string, optional
        Edge data key to use for weight

    default_weight : int, optional
        The weight of edges that do not have a weight attribute

    Returns
    -------
    int
        Longest path length

    Raises
    ------
    NetworkXNotImplemented
        If `G` is not directed

    See also
    --------
    dag_longest_path
    """
    path = nx.dag_longest_path(G, weight, default_weight)
    path_length = 0
    for (u, v) in pairwise(path):
        path_length += G[u][v].get(weight, default_weight)

    return path_length

    def test_unorderable_nodes(self):
        """Tests that computing the longest path does not depend on
        nodes being orderable.

        For more information, see issue #1989.

        """
        # TODO In Python 3, instances of the `object` class are
        # unorderable by default, so we wouldn't need to define our own
        # class here, we could just instantiate an instance of the
        # `object` class. However, we still support Python 2; when
        # support for Python 2 is dropped, this test can be simplified
        # by replacing `Unorderable()` by `object()`.
        class Unorderable(object):

            def __le__(self):
                raise NotImplemented

            def __ge__(self):
                raise NotImplemented

        # Create the directed path graph on four nodes, with nodes
        # represented as (unorderable) Python objects.
        nodes = [Unorderable() for n in range(4)]
        G = nx.DiGraph()
        G.add_edges_from(pairwise(nodes))
        path = list(nx.dag_longest_path(G))
        assert_equal(path, nodes)

def add_cycle(G_to_add_to, nodes_for_cycle, **attr):
    """Add a cycle to the Graph G_to_add_to.

    Parameters
    ----------
    G_to_add_to : graph
        A NetworkX graph
    nodes_for_cycle: iterable container
        A container of nodes.  A cycle will be constructed from
        the nodes (in order) and added to the graph.
    attr : keyword arguments, optional (default= no attributes)
        Attributes to add to every edge in cycle.

    See Also
    --------
    add_path, add_star

    Examples
    --------
    >>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
    >>> nx.add_cycle(G, [0, 1, 2, 3])
    >>> nx.add_cycle(G, [10, 11, 12], weight=7)
    """
    nlist = iter(nodes_for_cycle)
    try:
        first_node = next(nlist)
    except StopIteration:
        return
    G_to_add_to.add_node(first_node)
    G_to_add_to.add_edges_from(pairwise(chain((first_node,), nlist), cyclic=True), **attr)

def add_path(G, nodes, **attr):
    """Add a path to the Graph G.

    Parameters
    ----------
    nodes : iterable container
        A container of nodes.  A path will be constructed from
        the nodes (in order) and added to the graph.
    attr : keyword arguments, optional (default= no attributes)
        Attributes to add to every edge in path.

    See Also
    --------
    add_star, add_cycle

    Examples
    --------
    >>> G = nx.Graph()
    >>> nx.add_path(G, [0, 1, 2, 3])
    >>> nx.add_path(G, [10, 11, 12], weight=7)
    """
    nlist = iter(nodes)
    try:
        first_node = next(nlist)
    except StopIteration:
        return
    G.add_node(first_node)
    G.add_edges_from(pairwise(chain((first_node,), nlist)), **attr)

def test_four_clique():
    paths = [
        (11, 12, 13, 14, 11, 13, 14, 12),  # first 4-clique
        (21, 22, 23, 24, 21, 23, 24, 22),  # second 4-clique
        # paths connecting the 4 cliques such that they are
        # 3-connected in G, but not in the subgraph.
        # Case where the nodes bridging them do not have degree less than 3.
        (100, 13),
        (12, 100, 22),
        (13, 200, 23),
        (14, 300, 24),
    ]
    G = nx.Graph(it.chain(*[pairwise(path) for path in paths]))

    # The subgraphs and ccs are different for k=3
    local_ccs = fset(nx.k_edge_components(G, k=3))
    subgraphs = fset(nx.k_edge_subgraphs(G, k=3))
    assert_not_equal(local_ccs, subgraphs)

    # The cliques ares in the same cc
    clique1 = frozenset(paths[0])
    clique2 = frozenset(paths[1])
    assert_in(clique1.union(clique2).union({100}), local_ccs)

    # but different subgraphs
    assert_in(clique1, subgraphs)
    assert_in(clique2, subgraphs)

    assert_equal(G.degree(100), 3)

    _check_edge_connectivity(G)

def ladder_graph(n, create_using=None):
    """Return the Ladder graph of length n.

    This is two paths of n nodes, with
    each pair connected by a single edge.

    Node labels are the integers 0 to 2*n - 1.

    """
    if create_using is not None and create_using.is_directed():
        raise NetworkXError("Directed Graph not supported")
    G = empty_graph(2 * n, create_using)
    G.add_edges_from(pairwise(range(n)))
    G.add_edges_from(pairwise(range(n, 2 * n)))
    G.add_edges_from((v, v + n) for v in range(n))
    return G

def test_triangles():
    paths = [
        (11, 12, 13, 11),  # first 3-clique
        (21, 22, 23, 21),  # second 3-clique
        (11, 21),  # connected by an edge
    ]
    G = nx.Graph(it.chain(*[pairwise(path) for path in paths]))

    # subgraph and ccs are the same in all cases here
    assert_equal(
        fset(nx.k_edge_components(G, k=1)),
        fset(nx.k_edge_subgraphs(G, k=1))
    )

    assert_equal(
        fset(nx.k_edge_components(G, k=2)),
        fset(nx.k_edge_subgraphs(G, k=2))
    )

    assert_equal(
        fset(nx.k_edge_components(G, k=3)),
        fset(nx.k_edge_subgraphs(G, k=3))
    )

    _check_edge_connectivity(G)

def test_local_subgraph_difference():
    paths = [
        (11, 12, 13, 14, 11, 13, 14, 12),  # first 4-clique
        (21, 22, 23, 24, 21, 23, 24, 22),  # second 4-clique
        # paths connecting each node of the 4 cliques
        (11, 101, 21),
        (12, 102, 22),
        (13, 103, 23),
        (14, 104, 24),
    ]
    G = nx.Graph(it.chain(*[pairwise(path) for path in paths]))
    aux_graph = EdgeComponentAuxGraph.construct(G)

    # Each clique is returned separately in k-edge-subgraphs
    subgraph_ccs = fset(aux_graph.k_edge_subgraphs(3))
    subgraph_target = fset([{101}, {102}, {103}, {104},
                            {21, 22, 23, 24}, {11, 12, 13, 14}])
    assert_equal(subgraph_ccs, subgraph_target)

    # But in k-edge-ccs they are returned together
    # because they are locally 3-edge-connected
    local_ccs = fset(aux_graph.k_edge_components(3))
    local_target = fset([{101}, {102}, {103}, {104},
                         {11, 12, 13, 14, 21, 22, 23, 24}])
    assert_equal(local_ccs, local_target)

    def test_unorderable_nodes(self):
        """Tests that A* accomodates nodes that are not orderable.

        For more information, see issue #554.

        """
        # TODO In Python 3, instances of the `object` class are
        # unorderable by default, so we wouldn't need to define our own
        # class here, we could just instantiate an instance of the
        # `object` class. However, we still support Python 2; when
        # support for Python 2 is dropped, this test can be simplified
        # by replacing `Unorderable()` by `object()`.
        class Unorderable(object):

            def __le__(self):
                raise NotImplemented

            def __ge__(self):
                raise NotImplemented

        # Create the cycle graph on four nodes, with nodes represented
        # as (unorderable) Python objects.
        nodes = [Unorderable() for n in range(4)]
        G = nx.Graph()
        G.add_edges_from(pairwise(nodes, cyclic=True))
        path = nx.astar_path(G, nodes[0], nodes[2])
        assert_equal(len(path), 3)

def wheel_graph(n, create_using=None):
    """ Return the wheel graph
    
    The wheel graph consists of a hub node connected to a cycle of (n-1) nodes.

    Parameters
    ==========
    n : int or iterable
        If an integer, node labels are 0 to n with center 0.
        If an iterable of nodes, the center is the first.
    create_using : Graph, optional (default Graph())
        If provided this graph is cleared of nodes and edges and filled
        with the new graph. Usually used to set the type of the graph.
    Node labels are the integers 0 to n - 1.

    """
    n_name, nodes = n
    if n_name == 0:
        G = nx.empty_graph(0, create_using=create_using)
        G.name = "wheel_graph(0)"
        return G
    G = star_graph(nodes, create_using)
    G.name = "wheel_graph(%s)" % (n_name,)
    if len(G) > 2:
        G.add_edges_from(pairwise(nodes[1:]))
        G.add_edge(nodes[-1], nodes[1])
    return G

def test_directed_aux_graph():
    # Graph similar to the one in
    # http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0136264
    a, b, c, d, e, f, g, h, i = 'abcdefghi'
    dipaths = [
        (a, d, b, f, c),
        (a, e, b),
        (a, e, b, c, g, b, a),
        (c, b),
        (f, g, f),
        (h, i)
    ]
    G = nx.DiGraph(it.chain(*[pairwise(path) for path in dipaths]))
    aux_graph = EdgeComponentAuxGraph.construct(G)

    components_1 = fset(aux_graph.k_edge_subgraphs(k=1))
    target_1 = fset([{a, b, c, d, e, f, g}, {h}, {i}])
    assert_equal(target_1, components_1)

    # Check that the directed case for k=1 agrees with SCCs
    alt_1 = fset(nx.strongly_connected_components(G))
    assert_equal(alt_1, components_1)

    components_2 = fset(aux_graph.k_edge_subgraphs(k=2))
    target_2 = fset([{i}, {e}, {d}, {b, c, f, g}, {h}, {a}])
    assert_equal(target_2, components_2)

    components_3 = fset(aux_graph.k_edge_subgraphs(k=3))
    target_3 = fset([{a}, {b}, {c}, {d}, {e}, {f}, {g}, {h}, {i}])
    assert_equal(target_3, components_3)

def test_local_subgraph_difference_directed():
    dipaths = [
        (1, 2, 3, 4, 1),
        (1, 3, 1),
    ]
    G = nx.DiGraph(it.chain(*[pairwise(path) for path in dipaths]))

    assert_equal(
        fset(nx.k_edge_components(G, k=1)),
        fset(nx.k_edge_subgraphs(G, k=1))
    )

    # Unlike undirected graphs, when k=2, for directed graphs there is a case
    # where the k-edge-ccs are not the same as the k-edge-subgraphs.
    # (in directed graphs ccs and subgraphs are the same when k=2)
    assert_not_equal(
        fset(nx.k_edge_components(G, k=2)),
        fset(nx.k_edge_subgraphs(G, k=2))
    )

    assert_equal(
        fset(nx.k_edge_components(G, k=3)),
        fset(nx.k_edge_subgraphs(G, k=3))
    )

    _check_edge_connectivity(G)

 def test_multidigraph_unweighted(self):
     # This is the twice-singly-linked directed cycle graph on six nodes.
     edges = list(pairwise(range(6), cyclic=True))
     G = nx.MultiDiGraph(2 * edges)
     H = nx.DiGraph(G)
     G_cells = nx.voronoi_cells(G, {0, 3})
     H_cells = nx.voronoi_cells(H, {0, 3})
     assert_equal(G_cells, H_cells)

def grid_2d_graph(m, n, periodic=False, create_using=None):
    """Returns the two-dimensional grid graph.

    The grid graph has each node connected to its four nearest neighbors.

    Parameters
    ----------
    m, n : int or iterable container of nodes
        If an integer, nodes are from `range(n)`.
        If a container, elements become the coordinate of the nodes.

    periodic : bool (default: False)
        If this is ``True`` the nodes on the grid boundaries are joined
        to the corresponding nodes on the opposite grid boundaries.

    create_using : NetworkX graph constructor, optional (default=nx.Graph)
        Graph type to create. If graph instance, then cleared before populated.

    Returns
    -------
    NetworkX graph
        The (possibly periodic) grid graph of the specified dimensions.

    """
    G = empty_graph(0, create_using)
    row_name, rows = m
    col_name, cols = n
    G.add_nodes_from((i, j) for i in rows for j in cols)
    G.add_edges_from(((i, j), (pi, j))
                     for pi, i in pairwise(rows) for j in cols)
    G.add_edges_from(((i, j), (i, pj))
                     for i in rows for pj, j in pairwise(cols))
    if periodic is True:
        if len(rows) > 2:
            first = rows[0]
            last = rows[-1]
            G.add_edges_from(((first, j), (last, j)) for j in cols)
        if len(cols) > 2:
            first = cols[0]
            last = cols[-1]
            G.add_edges_from(((i, first), (i, last)) for i in rows)
    # both directions for directed
    if G.is_directed():
        G.add_edges_from((v, u) for u, v in G.edges())
    return G

def grid_2d_graph(m, n, periodic=False, create_using=None):
    """ Return the 2d grid graph of mxn nodes
    
    The grid graph has each node connected to its four nearest neighbors.

    Parameters
    ==========
    m, n : int or iterable container of nodes (default = 0)
        If an integer, nodes are from `range(n)`.
        If a container, those become the coordinate of the node.
    periodic : bool (default = False)
        If True will connect boundary nodes in periodic fashion.
    create_using : Graph, optional (default Graph())
        If provided this graph is cleared of nodes and edges and filled
        with the new graph. Usually used to set the type of the graph.
    """
    G = empty_graph(0, create_using)
    row_name, rows = m
    col_name, columns = n
    G.name = "grid_2d_graph(%s, %s)" % (row_name, col_name)
    G.add_nodes_from((i, j) for i in rows for j in columns)
    G.add_edges_from(((i, j), (pi, j))
                     for pi, i in pairwise(rows) for j in columns)
    G.add_edges_from(((i, j), (i, pj))
                     for i in rows for pj, j in pairwise(columns))
    if G.is_directed():
        G.add_edges_from(((pi, j), (i, j))
                         for pi, i in pairwise(rows) for j in columns)
        G.add_edges_from(((i, pj), (i, j))
                         for i in rows for pj, j in pairwise(columns))
    if periodic:
        if len(columns) > 2:
            f = columns[0]
            l = columns[-1]
            G.add_edges_from(((i, f), (i, l)) for i in rows)
            if G.is_directed():
                G.add_edges_from(((i, l), (i, f)) for i in rows)
        if len(rows) > 2:
            f = rows[0]
            l = rows[-1]
            G.add_edges_from(((f, j), (l, j)) for j in columns)
            if G.is_directed():
                G.add_edges_from(((l, j), (f, j)) for j in columns)
        G.name = "periodic_grid_2d_graph(%s,%s)" % (m, n)
    return G

def _path_to_cycle(path):
    """
    Removes the edges from path that occur even number of times.
    Returns a set of edges
    """
    edges = set()
    for edge in pairwise(path):
        # Toggle whether to keep the current edge.
        edges ^= {edge}
    return edges

def are_edge_disjoint_paths(G, paths):
    if not paths:
        return False
    for path in paths:
        assert_true(is_path(G, path))
    paths_edges = [list(pairwise(p)) for p in paths]
    num_of_edges = sum(len(e) for e in paths_edges)
    num_unique_edges = len(set.union(*[set(es) for es in paths_edges]))
    if num_of_edges == num_unique_edges:
        return True
    return False