text:
"""
Generators for some classic graphs.

The typical graph generator is called as follows:

>>> G=nx.complete_graph(100)

returning the complete graph on n nodes labeled 0, .., 99
as a simple graph. Except for empty_graph, all the generators
in this module return a Graph class (i.e. a simple, undirected graph).

"""
# Authors: Aric Hagberg (hagberg@lanl.gov) and Pieter Swart (swart@lanl.gov)

#    Copyright (C) 2004-2016 by
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    All rights reserved.
#    BSD license.
from __future__ import division

import itertools

import networkx as nx
from networkx.algorithms.bipartite.generators import complete_bipartite_graph
from networkx.utils import accumulate
from networkx.utils import flatten
from networkx.utils import nodes_or_number
from networkx.utils import pairwise

__all__ = ['balanced_tree',
           'barbell_graph',
           'complete_graph',
           'complete_multipartite_graph',
           'circular_ladder_graph',
           'circulant_graph',
           'cycle_graph',
           'dorogovtsev_goltsev_mendes_graph',
           'empty_graph',
           'full_rary_tree',
           'grid_graph',
           'grid_2d_graph',
           'hypercube_graph',
           'ladder_graph',
           'lollipop_graph',
           'null_graph',
           'path_graph',
           'star_graph',
           'trivial_graph',
           'turan_graph',
           'wheel_graph']

#-------------------------------------------------------------------
#   Some Classic Graphs
#-------------------------------------------------------------------

def _tree_edges(n, r):
    # helper function for trees
    # yields edges in rooted tree at 0 with n nodes and branching ratio r
    nodes = iter(range(n))
    parents = [next(nodes)]  # stack of max length r
    while parents:
        source = parents.pop(0)
        for i in range(r):
            try:
                target = next(nodes)
                parents.append(target)
                yield source, target
            except StopIteration:
                break

def full_rary_tree(r, n, create_using=None):
    """Creates a full r-ary tree of n vertices.

    Sometimes called a k-ary, n-ary, or m-ary tree.
    "... all non-leaf vertices have exactly r children and all levels
    are full except for some rightmost position of the bottom level
    (if a leaf at the bottom level is missing, then so are all of the
    leaves to its right." [1]_

    Parameters
    ----------
    r : int
        branching factor of the tree
    n : int
        Number of nodes in the tree
    create_using : Graph, optional (default None)
        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
    -------
    G : networkx Graph
        An r-ary tree with n nodes

    References
    ----------
    .. [1] An introduction to data structures and algorithms,
           James Andrew Storer,  Birkhauser Boston 2001, (page 225).
    """
    G = nx.empty_graph(n, create_using)
    G.add_edges_from(_tree_edges(n, r))
    return G

def balanced_tree(r, h, create_using=None):
    """Return the perfectly balanced `r`-ary tree of height `h`.

    Parameters
    ----------
    r : int
        Branching factor of the tree; each node will have `r`
        children.

    h : int
        Height of the tree.

    create_using : Graph, optional (default None)
        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
    -------
    G : NetworkX graph
        A balanced `r`-ary tree of height `h`.

    Notes
    -----
    This is the rooted tree where all leaves are at distance `h` from
    the root. The root has degree `r` and all other internal nodes
    have degree `r + 1`.

    Node labels are integers, starting from zero.

    A balanced tree is also known as a *complete r-ary tree*.

    """
    # The number of nodes in the balanced tree is `1 + r + ... + r^h`,
    # which is computed by using the closed-form formula for a geometric
    # sum with ratio `r`. In the special case that `r` is 1, the number
    # of nodes is simply `h + 1` (since the tree is actually a path
    # graph).
    if r == 1:
        n = h + 1
    else:
        # This must be an integer if both `r` and `h` are integers. If
        # they are not, we force integer division anyway.
        n = (1 - r ** (h + 1)) // (1 - r)
    return full_rary_tree(r, n, create_using=create_using)

def barbell_graph(m1, m2, create_using=None):
    """Return the Barbell Graph: two complete graphs connected by a path.

    For `m1 > 1` and `m2 >= 0`.

    Two identical complete graphs `K_{m1}` form the left and right bells,
    and are connected by a path `P_{m2}`.

    The `2*m1+m2`  nodes are numbered
        `0, ..., m1-1` for the left barbell,
        `m1, ..., m1+m2-1` for the path,
        and `m1+m2, ..., 2*m1+m2-1` for the right barbell.

    The 3 subgraphs are joined via the edges `(m1-1, m1)` and
    `(m1+m2-1, m1+m2)`. If `m2=0`, this is merely two complete
    graphs joined together.

    This graph is an extremal example in David Aldous
    and Jim Fill's e-text on Random Walks on Graphs.

    """
    if create_using is not None and create_using.is_directed():
        raise nx.NetworkXError("Directed Graph not supported")
    if m1 < 2:
        raise nx.NetworkXError(
            "Invalid graph description, m1 should be >=2")
    if m2 < 0:
        raise nx.NetworkXError(
            "Invalid graph description, m2 should be >=0")

    # left barbell
    G = complete_graph(m1, create_using)
    G.name = "barbell_graph(%d,%d)" % (m1, m2)

    # connecting path
    G.add_nodes_from(range(m1, m1 + m2 - 1))
    if m2 > 1:
        G.add_edges_from(pairwise(range(m1, m1 + m2)))
    # right barbell
    G.add_edges_from((u, v) for u in range(m1 + m2, 2 * m1 + m2)
                     for v in range(u + 1, 2 * m1 + m2))
    # connect it up
    G.add_edge(m1 - 1, m1)
    if m2 > 0:
        G.add_edge(m1 + m2 - 1, m1 + m2)
    return G

@nodes_or_number(0)
def complete_graph(n, create_using=None):
    """ Return the complete graph `K_n` with n nodes.

    Parameters
    ==========
    n : int or iterable container of nodes
        If n is an integer, nodes are from range(n).
        If n is a container of nodes, those nodes appear in the graph.
    create_using : Graph, optional (default None)
        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.

    Examples
    ========
    >>> G = nx.complete_graph(9)
    >>> len(G)
    9
    >>> G.size()
    36
    >>> G = nx.complete_graph(range(11,14))
    >>> list(G.nodes())
    [11, 12, 13]
    >>> G = nx.complete_graph(4, nx.DiGraph())
    >>> G.is_directed()
    True

    """
    n_name, nodes = n
    G = empty_graph(n_name, create_using)
    G.name = "complete_graph(%s)" % (n_name,)
    if len(nodes) > 1:
        if G.is_directed():
            edges = itertools.permutations(nodes, 2)
        else:
            edges = itertools.combinations(nodes, 2)
        G.add_edges_from(edges)
    return G

def circular_ladder_graph(n, create_using=None):
    """Return the circular ladder graph `CL_n` of length n.

    `CL_n` consists of two concentric n-cycles in which
    each of the n pairs of concentric nodes are joined by an edge.

    Node labels are the integers 0 to n-1

    """
    G = ladder_graph(n, create_using)
    G.name = "circular_ladder_graph(%d)" % n
    G.add_edge(0, n - 1)
    G.add_edge(n, 2 * n - 1)
    return G

def circulant_graph(n, offsets, create_using=None):
    """Generates the circulant graph Ci_n(x_1, x_2, ..., x_m) with n vertices.

    Returns
    -------
    The graph Ci_n(x_1, ..., x_m) consisting of n vertices 0, ..., n-1 such
    that the vertex with label i is connected to the vertices labelled (i + x)
    and (i - x), for all x in x_1 up to x_m, with the indices taken modulo n.

    Parameters
    ----------
    n : integer
        The number of vertices the generated graph is to contain.
    offsets : list of integers
        A list of vertex offsets, x_1 up to x_m, as described above.
    create_using : Graph, optional (default None)
        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.

    Examples
    --------
    Many well-known graph families are subfamilies of the circulant graphs; for
    example, to generate the cycle graph on n points, we connect every vertex to
    every other at offset plus or minus one. For n = 10,

    >>> import networkx
    >>> G = networkx.generators.classic.circulant_graph(10, [1])
    >>> edges = [
    ...     (0, 9), (0, 1), (1, 2), (2, 3), (3, 4),
    ...     (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)]
    ...
    >>> sorted(edges) == sorted(G.edges())
    True

    Similarly, we can generate the complete graph on 5 points with the set of
    offsets [1, 2]:

    >>> G = networkx.generators.classic.circulant_graph(5, [1, 2])
    >>> edges = [
    ...     (0, 1), (0, 2), (0, 3), (0, 4), (1, 2),
    ...     (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
    ...
    >>> sorted(edges) == sorted(G.edges())
    True

    """
    G = empty_graph(n, create_using)
    template = 'circulant_graph(%d, [%s])'
    G.name = template % (n, ', '.join(str(j) for j in offsets))
    for i in range(n):
        for j in offsets:
            G.add_edge(i, (i - j) % n)
            G.add_edge(i, (i + j) % n)
    return G

@nodes_or_number(0)
def cycle_graph(n, create_using=None):
    """Return the cycle graph `C_n` of cyclicly connected nodes.

    `C_n` is a path with its two end-nodes connected.

    Parameters
    ==========
    n : int or iterable container of nodes
        If n is an integer, nodes are from `range(n)`.
        If n is a container of nodes, those nodes appear in the graph.
    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.

    Notes
    =====
    If create_using is directed, the direction is in increasing order.

    """
    n_orig, nodes = n
    G = empty_graph(nodes, create_using)
    G.name = "cycle_graph(%s)" % (n_orig,)
    G.add_edges_from(nx.utils.pairwise(nodes))
    G.add_edge(nodes[-1], nodes[0])
    return G

def dorogovtsev_goltsev_mendes_graph(n, create_using=None):
    """Return the hierarchically constructed Dorogovtsev-Goltsev-Mendes graph.

    n is the generation.
    See: arXiv:/cond-mat/0112143 by Dorogovtsev, Goltsev and Mendes.

    """
    if create_using is not None:
        if create_using.is_directed():
            raise nx.NetworkXError("Directed Graph not supported")
        if create_using.is_multigraph():
            raise nx.NetworkXError("Multigraph not supported")
    G = empty_graph(0, create_using)
    G.name = "Dorogovtsev-Goltsev-Mendes Graph"
    G.add_edge(0, 1)
    if n == 0:
        return G
    new_node = 2         # next node to be added
    for i in range(1, n + 1):  # iterate over number of generations.
        last_generation_edges = list(G.edges())
        number_of_edges_in_last_generation = len(last_generation_edges)
        for j in range(0, number_of_edges_in_last_generation):
            G.add_edge(new_node, last_generation_edges[j][0])
            G.add_edge(new_node, last_generation_edges[j][1])
            new_node += 1
    return G

@nodes_or_number(0)
def empty_graph(n=0, create_using=None):
    """Return the empty graph with n nodes and zero edges.

    Parameters
    ==========
    n : int or iterable container of nodes (default = 0)
        If n is an integer, nodes are from `range(n)`.
        If n is a container of nodes, those nodes appear in the graph.
    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.

    For example:
    >>> G=nx.empty_graph(10)
    >>> G.number_of_nodes()
    10
    >>> G.number_of_edges()
    0
    >>> G=nx.empty_graph("ABC")
    >>> G.number_of_nodes()
    3
    >>> sorted(G)
    ['A', 'B', 'C']

    Notes
    =====
    The variable create_using should point to a "graph"-like object that
    will be cleared (nodes and edges will be removed) and refitted as
    an empty "graph" with nodes specified in n. This capability
    is useful for specifying the class-nature of the resulting empty
    "graph" (i.e. Graph, DiGraph, MyWeirdGraphClass, etc.).

    The variable create_using has two main uses:
    Firstly, the variable create_using can be used to create an
    empty digraph, multigraph, etc.  For example,

    >>> n=10
    >>> G=nx.empty_graph(n, create_using=nx.DiGraph())

    will create an empty digraph on n nodes.

    Secondly, one can pass an existing graph (digraph, multigraph,
    etc.) via create_using. For example, if G is an existing graph
    (resp. digraph, multigraph, etc.), then empty_graph(n, create_using=G)
    will empty G (i.e. delete all nodes and edges using G.clear())
    and then add n nodes and zero edges, and return the modified graph.

    See also create_empty_copy(G).

    """
    if create_using is None:
        # default empty graph is a simple graph
        G = nx.Graph()
    else:
        G = create_using
        G.clear()

    n_name, nodes = n
    G.name = "empty_graph(%s)" % (n_name,)
    G.add_nodes_from(nodes)
    return G

@nodes_or_number([0, 1])
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 grid_graph(dim, periodic=False):
    """ Return the n-dimensional grid graph.

    'dim' is a tuple or list with the size in each dimension or an
    iterable of nodes for each dimension. The dimension of
    the grid_graph is the length of the tuple or list 'dim'.

    E.g. G=grid_graph(dim=[2, 3]) produces a 2x3 grid graph.

    E.g. G=grid_graph(dim=[range(7, 9), range(3, 6)]) produces a 2x3 grid graph.

    If periodic=True then join grid edges with periodic boundary conditions.

    """
    dlabel = "%s" % str(dim)
    if not dim:
        G = empty_graph(0)
        G.name = "grid_graph(%s)" % dlabel
        return G
    if periodic:
        func = cycle_graph
    else:
        func = path_graph

    G = func(dim[0])
    for current_dim in dim[1:]:
        # order matters: copy before it is cleared during the creation of Gnew
        Gold = G.copy()
        Gnew = func(current_dim)
        # explicit: create_using=None
        # This is so that we get a new graph of Gnew's class.
        G = nx.cartesian_product(Gnew, Gold)
    # graph G is done but has labels of the form (1, (2, (3, 1)))
    # so relabel
    H = nx.relabel_nodes(G, flatten)
    H.name = "grid_graph(%s)" % dlabel
    return H

def hypercube_graph(n):
    """Return the n-dimensional hypercube.

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

    """
    dim = n * [2]
    G = grid_graph(dim)
    G.name = "hypercube_graph_(%d)" % n
    return G

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

    This is two rows 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 nx.NetworkXError("Directed Graph not supported")
    G = empty_graph(2 * n, create_using)
    G.name = "ladder_graph_(%d)" % n
    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

@nodes_or_number([0, 1])
def lollipop_graph(m, n, create_using=None):
    """Return the Lollipop Graph; `K_m` connected to `P_n`.

    This is the Barbell Graph without the right barbell.

    Parameters
    ==========
    m, n : int or iterable container of nodes (default = 0)
        If an integer, nodes are from `range(m)` and `range(m,m+n)`.
        If a container, the entries are the coordinate of the node.

        The nodes for m appear in the complete graph `K_m` and the nodes
        for n appear in the path `P_n`
    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.

    Notes
    =====
    The 2 subgraphs are joined via an edge (m-1, m).
    If n=0, this is merely a complete graph.

    (This graph is an extremal example in David Aldous and Jim
    Fill's etext on Random Walks on Graphs.)

    """
    m, m_nodes = m
    n, n_nodes = n
    M = len(m_nodes)
    N = len(n_nodes)
    if isinstance(m, int):
        n_nodes = [len(m_nodes) + i for i in n_nodes]
    if create_using is not None and create_using.is_directed():
        raise nx.NetworkXError("Directed Graph not supported")
    if M < 2:
        raise nx.NetworkXError(
            "Invalid graph description, m should be >=2")
    if N < 0:
        raise nx.NetworkXError(
            "Invalid graph description, n should be >=0")

    # the ball
    G = complete_graph(m_nodes, create_using)
    # the stick
    G.add_nodes_from(n_nodes)
    if N > 1:
        G.add_edges_from(pairwise(n_nodes))
    # connect ball to stick
    if M > 0 and N > 0:
        G.add_edge(m_nodes[-1], n_nodes[0])
    G.name = "lollipop_graph(%s, %s)" % (m, n)
    return G

def null_graph(create_using=None):
    """Return the Null graph with no nodes or edges.

    See empty_graph for the use of create_using.

    """
    G = empty_graph(0, create_using)
    G.name = "null_graph()"
    return G

@nodes_or_number(0)
def path_graph(n, create_using=None):
    """Return the Path graph `P_n` of linearly connected 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.

    """
    n_name, nodes = n
    G = empty_graph(nodes, create_using)
    G.name = "path_graph(%s)" % (n_name,)
    G.add_edges_from(nx.utils.pairwise(nodes))
    return G

@nodes_or_number(0)
def star_graph(n, create_using=None):
    """ Return the star graph

    The star graph consists of one center node connected to n outer 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.

    Notes
    =====
    The graph has n+1 nodes for integer n.
    So star_graph(3) is the same as star_graph(range(4)).
    """
    n_name, nodes = n
    if isinstance(n_name, int):
        nodes = nodes + [n_name]  # there should be n+1 nodes
    first = nodes[0]
    G = empty_graph(nodes, create_using)
    if G.is_directed():
        raise nx.NetworkXError("Directed Graph not supported")
    G.add_edges_from((first, v) for v in nodes[1:])
    G.name = "star_graph(%s)" % (n_name,)
    return G

def trivial_graph(create_using=None):
    """ Return the Trivial graph with one node (with label 0) and no edges.

    """
    G = empty_graph(1, create_using)
    G.name = "trivial_graph()"
    return G

def turan_graph(n, r):
    r""" Return the Turan Graph

    The Turan Graph is a complete multipartite graph on `n` vertices
    with `r` disjoint subsets. It is the graph with the edges for any graph with
    `n` vertices and `r` disjoint subsets.

    Given `n` and `r`, we generate a complete multipartite graph with
    :math:`r-(n \mod r)` partitions of size :math:`n/r`, rounded down, and
    :math:`n \mod r` partitions of size :math:`n/r+1`, rounded down.

    Parameters
    ==========
    n : int
        The number of vertices.
    r : int
        The number of partitions.
        Must be less than or equal to n.

    Notes
    =====
    Must satisfy :math:`1 <= r <= n`.
    The graph has :math:`(r-1)(n^2)/(2r)` edges, rounded down.
    """

    if not 1 <= r <= n:
        raise nx.NetworkXError("Must satisfy 1 <= r <= n")

    partitions = [n//r]*(r-(n%r))+[n//r+1]*(n%r)
    G = complete_multipartite_graph(*partitions)
    G.name = "turan_graph({},{})".format(n, r)
    return G

@nodes_or_number(0)
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 complete_multipartite_graph(*subset_sizes):
    """Returns the complete multipartite graph with the specified subset sizes.

    Parameters
    ----------
    subset_sizes : tuple of integers or tuple of node iterables
       The arguments can either all be integer number of nodes or they
       can all be iterables of nodes. If integers, they represent the
       number of vertices in each subset of the multipartite graph.
       If iterables, each is used to create the nodes for that subset.
       The length of subset_sizes is the number of subsets.

    Returns
    -------
    G : NetworkX Graph
       Returns the complete multipartite graph with the specified subsets.

       For each node, the node attribute 'subset' is an integer
       indicating which subset contains the node.

    Examples
    --------
    Creating a complete tripartite graph, with subsets of one, two, and three
    vertices, respectively.

        >>> import networkx as nx
        >>> G = nx.complete_multipartite_graph(1, 2, 3)
        >>> [G.node[u]['subset'] for u in G]
        [0, 1, 1, 2, 2, 2]
        >>> list(G.edges(0))
        [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)]
        >>> list(G.edges(2))
        [(2, 0), (2, 3), (2, 4), (2, 5)]
        >>> list(G.edges(4))
        [(4, 0), (4, 1), (4, 2)]

        >>> G = nx.complete_multipartite_graph('a', 'bc', 'def')
        >>> [G.node[u]['subset'] for u in sorted(G)]
        [0, 1, 1, 2, 2, 2]

    Notes
    -----
    This function generalizes several other graph generator functions.

    - If no subset sizes are given, this returns the null graph.
    - If a single subset size `n` is given, this returns the empty graph on
      `n` nodes.
    - If two subset sizes `m` and `n` are given, this returns the complete
      bipartite graph on `m + n` nodes.
    - If subset sizes `1` and `n` are given, this returns the star graph on
      `n + 1` nodes.

    See also
    --------
    complete_bipartite_graph
    """
    # The complete multipartite graph is an undirected simple graph.
    G = nx.Graph()
    G.name = 'complete_multiparite_graph{}'.format(subset_sizes)

    if len(subset_sizes) == 0:
        return G

    # set up subsets of nodes
    try:
        extents = pairwise(accumulate((0,) + subset_sizes))
        subsets = [range(start, end) for start, end in extents]
    except TypeError:
        subsets = subset_sizes

    # add nodes with subset attribute
    # while checking that ints are not mixed with iterables
    try:
        for (i, subset) in enumerate(subsets):
            G.add_nodes_from(subset, subset=i)
    except TypeError:
        raise nx.NetworkXError("Arguments must be all ints or all iterables")

    # Across subsets, all vertices should be adjacent.
    # We can use itertools.combinations() because undirected.
    for subset1, subset2 in itertools.combinations(subsets, 2):
        G.add_edges_from(itertools.product(subset1, subset2))
    return G


text:
require File.dirname(__FILE__) + '/../../spec_helper.rb'
module Spec
  module Distributed
    describe ExampleValueHolder do
      include OptionsHelper
      attr_reader :example, :holder
      before do
        @example_group = mock('example_group')
        @example = mock("example")
        @example.should_receive(:class).twice.and_return(@example_group)
        @example.should_receive(:description).twice.and_return("description")

        @example_group.should_receive(:object_id).and_return(7654321)
        @example_group.should_receive(:description_options).and_return({:example_group_object_id => 7654321})
        @example_group.should_receive(:examples).and_return([@example])

        @rspec_options = mock("rspec_options")
        @rspec_options.should_receive(:example_groups).and_return([@example_group])

        @holder = ExampleValueHolder.new(@example)
      end

      it "should return the example" do
        with_rspec_options(@rspec_options) do
          holder.value.should equal(example)
        end
      end
    end

    describe ExampleValueHolder, "with a before(:all) example" do
      include OptionsHelper
      attr_reader :example, :holder
      before do
        @example_group = mock('example_group')
        @example = mock("example")

        @example_group.should_receive(:object_id).and_return(7654321)
        @example_group.should_receive(:description_options).and_return({:example_group_object_id => 7654321})

        @rspec_options = mock("rspec_options")
        @rspec_options.should_receive(:example_groups).and_return([@example_group])

        @before_all_example = mock("before all example")
        @before_all_example.should_receive(:description).and_return("before(:all)")
        @before_all_example.should_receive(:class).and_return(@example_group)
        @holder = ExampleValueHolder.new(@before_all_example)
      end

      it "should return the example" do
        new_example = mock("new example")
        @example_group.should_receive(:new).with("before(:all)").and_return(new_example)

        with_rspec_options(@rspec_options) do
          holder.value.should equal(new_example)
        end
      end
    end

  end
end

redpajama_set_name: RedPajamaGithub


text:
package org.apereo.cas.config;

import org.apereo.cas.configuration.CasConfigurationProperties;
import org.apereo.cas.configuration.model.support.redis.RedisTicketRegistryProperties;
import org.apereo.cas.ticket.registry.RedisTicketRegistry;
import org.apereo.cas.ticket.registry.TicketRedisTemplate;
import org.apereo.cas.ticket.registry.TicketRegistry;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.context.properties.EnableConfigurationProperties;
import org.springframework.cloud.context.config.annotation.RefreshScope;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.data.redis.connection.RedisConnectionFactory;
import org.springframework.data.redis.connection.jedis.JedisConnectionFactory;
import redis.clients.jedis.JedisPoolConfig;

/**
 * This is {@link RedisTicketRegistryConfiguration}.
 *
 * @author serv
 * @since 5.0.0
 */
@Configuration("redisTicketRegistryConfiguration")
@EnableConfigurationProperties(CasConfigurationProperties.class)
public class RedisTicketRegistryConfiguration {

    @Autowired
    private CasConfigurationProperties casProperties;

    private RedisTicketRegistryProperties redisProperties() {
        return casProperties.getTicket().getRegistry().getRedis();
    }

    @Bean
    @RefreshScope
    public RedisConnectionFactory redisConnectionFactory() {
        final JedisPoolConfig poolConfig = this.redisProperties().getPool() != null
                ? jedisPoolConfig() : new JedisPoolConfig();

        final JedisConnectionFactory factory = new JedisConnectionFactory(poolConfig);
        factory.setHostName(this.redisProperties().getHost());
        factory.setPort(this.redisProperties().getPort());
        if (this.redisProperties().getPassword() != null) {
            factory.setPassword(this.redisProperties().getPassword());
        }
        factory.setDatabase(this.redisProperties().getDatabase());
        if (this.redisProperties().getTimeout() > 0) {
            factory.setTimeout(this.redisProperties().getTimeout());
        }
        return factory;
    }

    private JedisPoolConfig jedisPoolConfig() {
        final JedisPoolConfig config = new JedisPoolConfig();
        final RedisTicketRegistryProperties.Pool props = this.redisProperties().getPool();
        config.setMaxTotal(props.getMaxActive());
        config.setMaxIdle(props.getMaxIdle());
        config.setMinIdle(props.getMinIdle());
        config.setMaxWaitMillis(props.getMaxWait());
        return config;
    }

    @Bean
    @RefreshScope
    public TicketRedisTemplate ticketRedisTemplate() {
        return new TicketRedisTemplate(redisConnectionFactory());
    }

    @Bean(name = {"redisTicketRegistry", "ticketRegistry"})
    @RefreshScope
    public TicketRegistry redisTicketRegistry() {
        return new RedisTicketRegistry(ticketRedisTemplate());
    }
}


text:
{-# LANGUAGE CPP #-}
module GHCJS.DOM.HTMLMenuElement (
#if (defined(ghcjs_HOST_OS) && defined(USE_JAVASCRIPTFFI)) || !defined(USE_WEBKIT)
  module GHCJS.DOM.JSFFI.Generated.HTMLMenuElement
#else
  module Graphics.UI.Gtk.WebKit.DOM.HTMLMenuElement
#endif
  ) where
#if (defined(ghcjs_HOST_OS) && defined(USE_JAVASCRIPTFFI)) || !defined(USE_WEBKIT)
import GHCJS.DOM.JSFFI.Generated.HTMLMenuElement
#else
import Graphics.UI.Gtk.WebKit.DOM.HTMLMenuElement
#endif


text:
@interface BrokenMachineParticle : BreakableWallRockParticle

@end


text:
==================
Distributed Cuckoo
==================

As mentioned in :doc:`submit`, Cuckoo provides a REST API for Distributed
Cuckoo usage. Distributed Cuckoo allows one to setup a single REST API
point to which samples and URLs can be submitted which will then, in turn, be
submitted to one of the configured Cuckoo nodes.

A typical setup thus includes a machine on which Distributed Cuckoo is run
and one or more machines running an instance of the Cuckoo daemon and the
:doc:`Cuckoo REST API <api>`.

A few notes:

* Using Distributed Cuckoo only makes sense when running at least two
  cuckoo nodes.
* Distributed Cuckoo can be run on a machine that also runs a Cuckoo
  daemon and REST API, however, make sure it has enough disk space if the
  intention is to submit a lot of samples.

Starting the Distributed REST API
=================================

The Distributed REST API has the following command line options::

    $ cuckoo distributed server --help
    Usage: cuckoo distributed server [OPTIONS]

    Options:
      -H, --host TEXT     Host to bind the Distributed Cuckoo server on
      -p, --port INTEGER  Port to bind the Distributed Cuckoo server on
      --uwsgi             Dump uWSGI configuration
      --nginx             Dump nginx configuration
      --help              Show this message and exit.

As may be derived from the help output, starting Distributed Cuckoo may be as
simple as running ``cuckoo distributed server``.

The various configuration options are described in the configuration file, but
following we have more in-depth descriptions as well. More advanced usage
naturally includes deployment using ``uWSGI`` and ``nginx``.

Distributed Cuckoo Configuration
================================

Report Formats
--------------

The reporting formats denote which reports you'd like to retrieve later on.
Note that all task-related data will be removed from the Cuckoo nodes once the
related reports have been fetched so that the machines are not running out of
disk space. This does, however, force you to specify all the report formats
that you're interested in, because otherwise that information will be lost.

Reporting formats include, but are not limited to and may also include your
own reporting formats, ``report.json``, ``report.html``, etc.

Samples Directory
-----------------

The samples directory denotes the directory where the submitted samples will
be stored temporarily, until the associated task has been deleted.

Reports Directory
-----------------

Much like the ``Samples Directory`` the Reports Directory defines the
directory where reports will be stored until they're fetched and deleted from
the Distributed REST API.

RESTful resources
=================

Following are all RESTful resources. Also make sure to check out the
:ref:`quick-usage` section which documents the most commonly used commands.

+-----------------------------------+---------------------------------------------------------------+
| Resource                          | Description                                                   |
+===================================+===============================================================+
| ``GET`` :ref:`node_root_get`      | Get a list of all enabled Cuckoo nodes.                       |
+-----------------------------------+---------------------------------------------------------------+
| ``POST`` :ref:`node_root_post`    | Register a new Cuckoo node.                                   |
+-----------------------------------+---------------------------------------------------------------+
| ``GET`` :ref:`node_get`           | Get basic information about a node.                           |
+-----------------------------------+---------------------------------------------------------------+
| ``PUT`` :ref:`node_put`           | Update basic information of a node.                           |
+-----------------------------------+---------------------------------------------------------------+
| ``POST`` :ref:`node_refresh`      | Refresh a Cuckoo nodes metadata.                              |
+-----------------------------------+---------------------------------------------------------------+
| ``DELETE`` :ref:`node_delete`     | Disable (not completely remove!) a node.                      |
+-----------------------------------+---------------------------------------------------------------+
| ``GET`` :ref:`task_root_get`      | Get a list of all (or a part) of the tasks in the database.   |
+-----------------------------------+---------------------------------------------------------------+
| ``POST`` :ref:`task_root_post`    | Create a new analysis task.                                   |
+-----------------------------------+---------------------------------------------------------------+
| ``GET`` :ref:`task_get`           | Get basic information about a task.                           |
+-----------------------------------+---------------------------------------------------------------+
| ``DELETE`` :ref:`task_delete`     | Delete all associated information of a task.                  |
+-----------------------------------+---------------------------------------------------------------+
| ``GET`` :ref:`report_get`         | Fetch an analysis report.                                     |
+-----------------------------------+---------------------------------------------------------------+
| ``GET`` :ref:`pcap_get`           | Fetches the PCAP of an analysis.                              |
+-----------------------------------+---------------------------------------------------------------+

.. _node_root_get:

GET /api/node
-------------

Returns all enabled nodes. For each node the information includes the
associated name, its API URL, and machines::

    $ curl http://localhost:9003/api/node
    {
        "success": true,
        "nodes": {
            "localhost": {
                "machines": [
                    {
                        "name": "cuckoo1",
                        "platform": "windows",
                        "tags": []
                    }
                ],
                "name": "localhost",
                "url": "http://localhost:8090/"
            }
        }
    }

.. _node_root_post:

POST /api/node
--------------

Register a new Cuckoo node by providing the name and the URL::

    $ curl http://localhost:9003/api/node -F name=localhost \
        -F url=http://localhost:8090/
    {
        "success": true
    }

.. _node_get:

GET /api/node/<name>
--------------------

Get basic information about a particular Cuckoo node::

    $ curl http://localhost:9003/api/node/localhost
    {
        "success": true,
        "nodes": [
            {
                "name": "localhost",
                "url": "http://localhost:8090/"
                "machines": [
                    {
                        "name": "cuckoo1",
                        "platform": "windows",
                        "tags": []
                    }
                ]
            }
        ]
    }

.. _node_put:

PUT /api/node/<name>
--------------------

Update basic information of a Cuckoo node::

    $ curl -XPUT http://localhost:9003/api/node/localhost -F name=newhost \
        -F url=http://1.2.3.4:8090/
    {
        "success": true
    }

.. _node_refresh:

POST /api/node/<name>/refresh
-----------------------------

Refreshes metadata associated by a Cuckoo node, in particular, its machines::

    $ curl -XPOST http://localhost:9003/api/node/localhost/refresh
    {
        "success": true,
        "machines": [
            {
                "name": "cuckoo1",
                "platform": "windows",
                "tags": []
            },
            {
                "name": "cuckoo2",
                "platform": "windows",
                "tags": []
            }
        ]
    }

.. _node_delete:

DELETE /api/node/<name>
-----------------------

Disable a Cuckoo node, therefore not having it process any new tasks, but
keeping its history in the Distributed Cuckoo database::

    $ curl -XDELETE http://localhost:9003/api/node/localhost
    {
        "success": true
    }

.. _task_root_get:

GET /api/task
-------------

Get a list of all tasks in the database. In order to limit the amount of
results, there's an ``offset``, ``limit``, ``finished``, and ``owner`` field
available::

    $ curl http://localhost:9003/api/task?limit=1
    {
        "success": true,
        "tasks": {
            "1": {
                "clock": null,
                "custom": null,
                "owner": "",
                "enforce_timeout": null,
                "machine": null,
                "memory": null,
                "options": null,
                "package": null,
                "path": "/tmp/dist-samples/tmphal8mS",
                "platform": "windows",
                "priority": 1,
                "tags": null,
                "task_id": 1,
                "timeout": null
            }
        }
    }

.. _task_root_post:

POST /api/task
--------------

Submit a new file or URL to be analyzed::

    $ curl http://localhost:9003/api/task -F file=@sample.exe
    {
        "success": true,
        "task_id": 2
    }

.. _task_get:

GET /api/task/<id>
------------------

Get basic information about a particular task::

    $ curl http://localhost:9003/api/task/2
    {
        "success": true,
        "tasks": {
            "2": {
                "id": 2,
                "clock": null,
                "custom": null,
                "owner": "",
                "enforce_timeout": null,
                "machine": null,
                "memory": null,
                "options": null,
                "package": null,
                "path": "/tmp/tmpPwUeXm",
                "platform": "windows",
                "priority": 1,
                "tags": null,
                "timeout": null,
                "task_id": 1,
                "node_id": 2,
                "finished": false
            }
        }
    }

.. _task_delete:

DELETE /api/task/<id>
---------------------

Delete all associated data of a task, namely the binary, the PCAP, and the
reports::

    $ curl -XDELETE http://localhost:9003/api/task/2
    {
        "success": true
    }

.. _report_get:

GET /api/report/<id>/<format>
-----------------------------

Fetch a report for the given task in the specified format::

    # Defaults to the JSON report.
    $ curl http://localhost:9003/api/report/2
    ...

.. _pcap_get:

GET /api/pcap/<id>
------------------

Fetches the PCAP for the given task::

   $ curl http://localhost:9003/api/pcap/2
   ...

Proposed setup
==============

The following description depicts a Distributed Cuckoo setup with two Cuckoo
machines, **cuckoo0** and **cuckoo1**. In this setup the first machine,
cuckoo0, also hosts the Distributed Cuckoo REST API.

Configuration settings
----------------------

Our setup will require a couple of updates with regards to the configuration
files.

conf/cuckoo.conf
^^^^^^^^^^^^^^^^

Update ``process_results`` to ``off`` as we will be running our own results
processing script (for performance reasons).

Update ``tmppath`` to something that holds enough storage to store a few
hundred binaries. On some servers or setups ``/tmp`` may have a limited amount
of space and thus this wouldn't suffice.

Update ``connection`` to use something *not* sqlite3. Preferably PostgreSQL or
MySQL. SQLite3 doesn't support multi-threaded applications and as such is not
a good choice for systems such as Cuckoo (as-is).

You should create a database specifically for the distributed cuckoo setup. Do
not be tempted to use any existing cuckoo database in order to avoid update
problems with the DB scripts. In the configuration use the new database name.
The remaining configuration such as usernames, servers, etc can be the same as
for your cuckoo install. Don't forget to use one DB per node and one for the
machine running Distributed Cuckoo (the "management machine" or "controller").

conf/processing.conf
^^^^^^^^^^^^^^^^^^^^

You may want to disable some processing modules, such as ``virustotal``.

conf/reporting.conf
^^^^^^^^^^^^^^^^^^^

Depending on which report(s) are required for integration with your system it
might make sense to only make those report(s) that you're going to use. Thus
disabling the other ones.

conf/virtualbox.conf
^^^^^^^^^^^^^^^^^^^^

Assuming ``VirtualBox`` is the Virtual Machine manager of choice, the ``mode``
will have to be changed to ``headless`` or you will have some restless nights
(this is the default nowadays).

Setup Cuckoo
------------

On each machine you will have to run the Cuckoo Daemon, the Cuckoo API, and
one or more Cuckoo Process instances. For more information on setting that up,
please refer to :doc:`Starting Cuckoo <start>`.

Setup Distributed Cuckoo
------------------------

On the Distributed Cuckoo machine you'll have to setup the Distributed Cuckoo
REST API and the Distributed Cuckoo Worker.

As stated earlier, Distributed Cuckoo REST API may be started by running
``cuckoo distributed server`` or by deploying it properly with ``uWSGI`` and
``nginx``.

The Distributed Cuckoo Worker may be started by running ``supervisorctl start
distributed`` in the ``CWD`` (make sure to start ``supervisord`` first as per
:ref:`cuckoo_background`). This will automatically start the Worker with the
correct configuration and arguments, etc.

Register Cuckoo nodes
---------------------

As outlined in :ref:`quick-usage` the Cuckoo nodes have to be registered with
the Distributed Cuckoo REST API::

    $ curl http://localhost:9003/api/node -F name=cuckoo0 -F url=http://localhost:8090/
    $ curl http://localhost:9003/api/node -F name=cuckoo1 -F url=http://1.2.3.4:8090/

Having registered the Cuckoo nodes all that's left to do now is to submit
tasks and fetch reports once finished. Documentation on these commands can be
found in the :ref:`quick-usage` section. In case your Cuckoo node is not on
``localhost``, replace ``localhost`` with the IP address of the node where
the Cuckoo REST API is running.

If you want to experiment with load balancing between the nodes you may want
to try using a lower value for the ``threshold`` parameter in the
``$CWD/distributed/settings.py`` file as the default value is ``500`` (meaning
tasks are assigned to Cuckoo nodes in batches of 500).

.. _quick-usage:

Quick usage
===========

For practical usage the following few commands will be most interesting.

Register a Cuckoo node, in this case a Cuckoo API running on the same machine
in this case::

    $ curl http://localhost:9003/api/node -F name=localhost -F ip=127.0.0.1

Disable a Cuckoo node::

    $ curl -XDELETE http://localhost:9003/api/node/localhost

Submit a new analysis task without any special requirements (e.g., using
Cuckoo ``tags``, a particular machine, etc)::

    $ curl http://localhost:9003/api/task -F file=@/path/to/sample.exe

Get the report of a task has been finished (if it hasn't finished you'll get
an error with code 420). Following example will default to the ``JSON``
report::

    $ curl http://localhost:9003/api/report/1

If a Cuckoo node gets stuck and needs a reset, the following steps could be
performed to restart it cleanly. Note that this requires usage of our
SaltStack configuration and some manual SQL commands (and preferably the
Distributed Cuckoo Worker is temporary disabled, i.e.,
``supervisorctl stop distributed``)::

    $ psql -c "UPDATE task SET status = 'pending' WHERE status = 'processing' AND node_id = 123"
    $ salt cuckoo1 state.apply cuckoo.clean
    $ salt cuckoo1 state.apply cuckoo.start

If the entire Cuckoo cluster was somehow locked up, i.e., all tasks have been
'assigned', are 'processing', or have the 'finished' status while none of the
Cuckoo nodes are currently working on said analyses (e.g., due to numerous
resets etc), then the following steps may be used to reset the entire state::

    $ supervisorctl -c ~/.cuckoo/supervisord.conf stop distributed
    $ salt '*' state.apply cuckoo.stop
    $ salt '*' state.apply cuckoo.clean
    $ psql -c "UPDATE task SET status = 'pending', node_id = null WHERE status IN ('assigned', 'processing', 'finished')"
    $ salt '*' state.apply cuckoo.start
    $ supervisorctl -c ~/.cuckoo/supervisord.conf start distributed

If a Cuckoo node has a number of tasks that failed to process, therefore
locking up the Cuckoo node altogether, then upgrading the Cuckoo instances
with a bugfixed version and re-processing all analyses may do the trick::

    $ salt cuckoo1 state.apply cuckoo.update  # Upgrade Cuckoo.
    # To make sure there are failed analyses in the first place.
    $ salt cuckoo1 cmd.run "sudo -u cuckoo psql -c \"SELECT * FROM tasks WHERE status = 'failed_processing'\"
    # Reset each analyses to be re-processed.
    $ salt cuckoo1 cmd.run "sudo -u cuckoo psql -c \"UPDATE tasks SET status = 'completed', processing = null WHERE status = 'failed_processing'\""

In order to upgrade the Distributed Cuckoo master, one may want to perform the
following steps::

    $ /etc/init.d/uwsgi stop
    $ supervisorctl -c ~/.cuckoo/supervisord.conf stop distributed
    $ pip uninstall -y cuckoo
    $ pip install cuckoo==2.0.0         # Specify your version here.
    $ pip install Cuckoo-2.0.0.tar.gz   # Or use a locally archived build.
    $ cuckoo distributed migrate
    $ supervisorctl -c ~/.cuckoo/supervisord.conf start distributed
    $ /etc/init.d/uwsgi start
    $ /etc/init.d/nginx restart

In order to test your entire Cuckoo cluster, i.e., every machine on every
Cuckoo node, one may take the ``stuff/distributed/cluster-test.py`` script as
an example. As-is it allows one to check for an active internet connection in
each and every configured machine in the cluster. This script may be used to
identify machines that are incorrect or have been corrupted in one way or
another. Example usage may look as follows::

    # Assuming Distributed Cuckoo listens on localhost and that you want to
    # run the 'internet' script (see also the source of cluster-test.py).
    $ python stuff/distributed/cluster-test.py localhost -s internet