A very easy-to-use version of GFL solver that just requires the data and
    the edges.
359954
def solve_gfl(data, edges=None, weights=None,
              minlam=0.2, maxlam=1000.0, numlam=30,
              alpha=0.2, inflate=2., converge=1e-6,
              maxsteps=1000000, lam=None, verbose=0,
              missing_val=None, full_path=False,
              loss='normal'):
    ''''''

    #Fix no edge cases
    if edges.shape[0] < 1:
        return data

    #Keep initial edges
    init_edges = edges

    if verbose:
        print('Decomposing graph into trails')

    if loss == 'binomial':
        flat_data = data[0].flatten()
        nonmissing_flat_data = flat_data, data[1].flatten()
    else:
        flat_data = data.flatten()
        nonmissing_flat_data = flat_data

    if edges is None:
        if loss == 'binomial':
            if verbose:
                print('Using default edge set of a grid of same shape as the data: {0}'.format(data[0].shape))
            edges = hypercube_edges(data[0].shape)
        else:
            if verbose:
                print('Using default edge set of a grid of same shape as the data: {0}'.format(data.shape))
            edges = hypercube_edges(data.shape)
        if missing_val is not None:
            if verbose:
                print('Removing all data points whose data value is {0}'.format(missing_val))
            edges = [(e1,e2) for (e1,e2) in edges if flat_data[e1] != missing_val and flat_data[e2] != missing_val]
            if loss == 'binomial':
                nonmissing_flat_data = flat_data[flat_data != missing_val], nonmissing_flat_data[1][flat_data != missing_val]
            else:
                nonmissing_flat_data = flat_data[flat_data != missing_val]


    ########### Setup the graph
    g = Graph()
    g.add_edges_from(edges)
    chains = decompose_graph(g, heuristic='greedy')
    ntrails, trails, breakpoints, edges = chains_to_trails(chains)

    if verbose:
        print('Setting up trail solver')

    ########### Setup the solver
    if loss == 'normal':
        solver = TrailSolver(alpha, inflate, maxsteps, converge)
    elif loss == 'logistic':
        solver = LogisticTrailSolver(alpha, inflate, maxsteps, converge)
    elif loss == 'binomial':
        solver = BinomialTrailSolver(alpha, inflate, maxsteps, converge)
    else:
        raise NotImplementedError('Loss must be normal, logistic, or binomial')

    # Set the data and pre-cache any necessary structures
    solver.set_data(nonmissing_flat_data, edges, ntrails, trails, breakpoints, weights=weights)

    if verbose:
        print('Solving')

    ########### Run the solver
    if lam:
        # Fixed lambda
        beta = solver.solve(lam)
    else:
        # Grid search to find the best lambda
        beta = solver.solution_path(minlam, maxlam, numlam, verbose=max(0, verbose-1))
        if not full_path:
            beta = beta['best']

    ########### Fix disconnected nodes
    mask = np.ones_like(beta)
    mask[init_edges[:,0]] = 0
    mask[init_edges[:,1]] = 0
    beta[mask>0] = data[mask>0]

    return beta
1067737
def solve(self, lam):
        ''''''
        s = weighted_graphtf_logit(self.nnodes, self.trials, self.successes, lam,
                                 self.Dk.shape[0], self.Dk.shape[1], self.Dk.nnz,
                                 self.Dk.row.astype('int32'), self.Dk.col.astype('int32'), self.Dk.data.astype('double'),
                                 self.maxsteps, self.converge,
                                 self.beta, self.u)
        self.steps.append(s)
        return self.beta
1031806
def gru(name, input, state, kernel_r, kernel_u, kernel_c, bias_r, bias_u, bias_c, new_state, number_of_gates = 2):
    ''' 
    '''
    nn = Build(name)
    inputs = nn.concat(input, state)

    u = nn.sigmoid(nn.mad(inputs, kernel_u, bias_u))
    r = nn.sigmoid(nn.mad(inputs, kernel_r, bias_r))
    r_state = nn.mul(r, state)

    c = nn.tanh(nn.mad(kernel=kernel_c, bias=bias_c,
        x=nn.concat(input, r_state)))

    # new_h = u' * state + (1 - u') * c'
    #       = u' * state + c' - u' * c'

    # u' * state + c'
    nn.add(nn.mul(u, state), c)
    # - u' * c'
    nn.sub(nn._, nn.mul(u, c),
        out=new_state)

    return nn.layers;
802115
def solve(ctx, length, height, silent, profile, **pieces):
    
    # Check that at least one piece is provided.
    if not sum(pieces.values()):
        context = click.get_current_context()
        raise BadParameter('No piece provided.', ctx=context, param_hint=[
            '--{}'.format(label) for label in PIECE_LABELS])

    # Setup the optionnal profiler.
    profiler = BProfile('solver-profile.png', enabled=profile)

    solver = SolverContext(length, height, **pieces)
    logger.info(repr(solver))

    logger.info('Searching positions...')
    with profiler:
        start = time.time()
        for result in solver.solve():
            if not silent:
                click.echo(u'{}'.format(result))
        processing_time = time.time() - start

    logger.info('{} results found in {:.2f} seconds.'.format(
        solver.result_counter, processing_time))

    if profile:
        logger.info('Execution profile saved at {}'.format(
            profiler.output_path))
914207
def nalu(x, depth, epsilon=1e-30, name=None, reuse=None):
  """"""
  with tf.variable_scope(name, default_name="nalu", values=[x], reuse=reuse):
    x_shape = shape_list(x)
    x_flat = tf.reshape(x, [-1, x_shape[-1]])
    gw = tf.get_variable("w", [x_shape[-1], depth])
    g = tf.nn.sigmoid(tf.matmul(x_flat, gw))
    g = tf.reshape(g, x_shape[:-1] + [depth])
    a = nac(x, depth, name="nac_lin")
    log_x = tf.log(tf.abs(x) + epsilon)
    m = nac(log_x, depth, name="nac_log")
    return g * a + (1 - g) * tf.exp(m)
846585
def _create_solver(self):
        
        """
        # http://www.mcs.anl.gov/petsc/petsc-current/docs/manualpages/KSP/KSPType.html#KSPType
        iterative_solvers = ['richardson', 'chebyshev', 'cg', 'groppcg',
                             'pipecg', 'pipecgrr', 'cgne', 'nash', 'stcg',
                             'gltr', 'fcg', 'pipefcg', 'gmres', 'pipefgmres',
                             'fgmres', 'lgmres', 'dgmres', 'pgmres', 'tcqmr',
                             'bcgs', 'ibcgs', 'fbcgs', 'fbcgsr', 'bcgsl',
                             'pipebcgs', 'cgs', 'tfqmr', 'cr', 'pipecr',
                             'lsqr', 'preonly', 'qcg', 'bicg', 'minres',
                             'symmlq', 'lcd', 'python', 'gcr', 'pipegcr',
                             'tsirm', 'cgls', 'fetidp']

        # http://www.mcs.anl.gov/petsc/petsc-current/docs/manualpages/PC/PCType.html#PCType
        preconditioners = ['none', 'jacobi', 'sor', 'lu', 'shell', 'bjacobi',
                           'mg', 'eisenstat', 'ilu', 'icc', 'asm', 'gasm',
                           'ksp', 'composite', 'redundant', 'spai', 'nn',
                           'cholesky', 'pbjacobi', 'mat', 'hypre', 'parms',
                           'fieldsplit', 'tfs', 'ml', 'galerkin', 'exotic',
                           'cp', 'bfbt', 'lsc', 'python', 'pfmg', 'syspfmg',
                           'redistribute', 'svd', 'gamg', 'sacusp',
                           'sacusppoly', 'bicgstabcusp', 'ainvcusp',
                           'chowiluviennacl', 'rowscalingviennacl',
                           'saviennacl', 'bddc', 'kaczmarz', 'telescope']

        lu_direct_solvers = ['mumps', 'superlu_dist', 'umfpack', 'klu']

        cholesky_direct_solvers = ['mumps', 'cholmod']

        solver = self.settings['type']
        preconditioner = self.settings['preconditioner']

        if solver not in (iterative_solvers +
                          lu_direct_solvers +
                          cholesky_direct_solvers):
            solver = 'cg'
            print('Warning: ' + self.settings['type'] +
                  ' not availabe, ' + solver + ' used instead.')

        if preconditioner not in preconditioners:
            preconditioner = 'jacobi'
            print('Warning: ' + self.settings['preconditioner'] +
                  ' not availabe, ' + preconditioner + ' used instead.')

        if solver in lu_direct_solvers:
            self.ksp = PETSc.KSP()
            self.ksp.create(PETSc.COMM_WORLD)
            self.ksp.getPC().setType('lu')
            self.ksp.getPC().setFactorSolverPackage(solver)
            self.ksp.setType('preonly')

        elif solver in cholesky_direct_solvers:
            self.ksp = PETSc.KSP()
            self.ksp.create(PETSc.COMM_WORLD)
            self.ksp.getPC().setType('cholesky')
            self.ksp.getPC().setFactorSolverPackage(solver)
            self.ksp.setType('preonly')

        elif solver in iterative_solvers:
            self.ksp = PETSc.KSP()
            self.ksp.create(PETSc.COMM_WORLD)
            self.ksp.getPC().setType(preconditioner)
            self.ksp.setType(solver)

        self.ksp.setTolerances(self.settings['atol'], self.settings['rtol'],
                               self.settings['maxiter'])
383279
def graph_simplify(G):
    
    spurs = []
    path_nodes = []
    for k, d in G.degree().iteritems():
        if d == 1:
            spurs.append(k)
        elif d == 2:
            path_nodes.append(k)

    logging.debug("Remove {0} spurs.".format(len(spurs)))
    G.remove_nodes_from(spurs)

    SG = G.subgraph(path_nodes)
    cc = nx.connected_components(SG)
    for c in cc:
        if len(c) == 1:
            continue
        c = set(c)
        neighbors = set()
        for x in c:
            neighbors |= set(G.neighbors(x))
        neighbors -= c
        newtag = list(c)[0] + "*"
        for n in neighbors:
            G.add_edge(newtag, n)
        G.remove_nodes_from(c)
    logging.debug("Contract {0} path nodes into {1} nodes.".\
                    format(len(path_nodes), len(cc)))
782191
def _NTU_from_P_solver(P1, R1, NTU_min, NTU_max, function, **kwargs):
    '''
    '''
    P1_max = _NTU_from_P_objective(NTU_max, R1, 0, function, **kwargs)
    P1_min = _NTU_from_P_objective(NTU_min, R1, 0, function, **kwargs)
    if P1 > P1_max:
        raise ValueError('No solution possible gives such a high P1; maximum P1=%f at NTU1=%f' %(P1_max, NTU_max))
    if P1 < P1_min:
        raise ValueError('No solution possible gives such a low P1; minimum P1=%f at NTU1=%f' %(P1_min, NTU_min))
    # Construct the function as a lambda expression as solvers don't support kwargs
    to_solve = lambda NTU1: _NTU_from_P_objective(NTU1, R1, P1, function, **kwargs)
    return ridder(to_solve, NTU_min, NTU_max)
746468
def euler_tour_dfs(G, source=None):
    
    if source is None:
        # produce edges for all components
        nodes = G
    else:
        # produce edges for components with source
        nodes = [source]
    yielder = []
    visited = set()
    for start in nodes:
        if start in visited:
            continue
        visited.add(start)
        stack = [(start, iter(G[start]))]
        while stack:
            parent, children = stack[-1]
            try:
                child = next(children)
                if child not in visited:
                    # yielder += [[parent, child]]
                    yielder += [parent]
                    visited.add(child)
                    stack.append((child, iter(G[child])))
            except StopIteration:
                if stack:
                    last = stack[-1]
                    yielder += [last[0]]
                stack.pop()
    return yielder
805476
def gf_poly_mul_simple(p, q): # simple equivalent way of multiplying two polynomials without precomputation, but thus it's slower
    ''''''
    # Pre-allocate the result array
    r = bytearray(len(p) + len(q) - 1)
    # Compute the polynomial multiplication (just like the outer product of two vectors, we multiply each coefficients of p with all coefficients of q)
    for j in xrange(len(q)):
        for i in xrange(len(p)):
            r[i + j] ^= gf_mul(p[i], q[j]) # equivalent to: r[i + j] = gf_add(r[i+j], gf_mul(p[i], q[j])) -- you can see it's your usual polynomial multiplication
    return r
1071560
def tsp_gurobi(edges):
    
    from gurobipy import Model, GRB, quicksum

    edges = populate_edge_weights(edges)
    incoming, outgoing, nodes = node_to_edge(edges)
    idx = dict((n, i) for i, n in enumerate(nodes))
    nedges = len(edges)
    n = len(nodes)

    m = Model()

    def step(x): return "u_{0}".format(x)
    # Create variables
    vars = {}
    for i, (a, b, w) in enumerate(edges):
        vars[i] = m.addVar(obj=w, vtype=GRB.BINARY, name=str(i))
    for u in nodes[1:]:
        u = step(u)
        vars[u] = m.addVar(obj=0, vtype=GRB.INTEGER, name=u)
    m.update()

    # Bounds for step variables
    for u in nodes[1:]:
        u = step(u)
        vars[u].lb = 1
        vars[u].ub = n - 1

    # Add degree constraint
    for v in nodes:
        incoming_edges = incoming[v]
        outgoing_edges = outgoing[v]
        m.addConstr(quicksum(vars[x] for x in incoming_edges) == 1)
        m.addConstr(quicksum(vars[x] for x in outgoing_edges) == 1)

    # Subtour elimination
    edge_store = dict(((idx[a], idx[b]), i)
                      for i, (a, b, w) in enumerate(edges))

    # Given a list of edges, finds the shortest subtour
    def subtour(s_edges):
        visited = [False] * n
        cycles = []
        lengths = []
        selected = [[] for i in range(n)]
        for x, y in s_edges:
            selected[x].append(y)
        while True:
            current = visited.index(False)
            thiscycle = [current]
            while True:
                visited[current] = True
                neighbors = [x for x in selected[current] if not visited[x]]
                if len(neighbors) == 0:
                    break
                current = neighbors[0]
                thiscycle.append(current)
            cycles.append(thiscycle)
            lengths.append(len(thiscycle))
            if sum(lengths) == n:
                break
        return cycles[lengths.index(min(lengths))]

    def subtourelim(model, where):
        if where != GRB.callback.MIPSOL:
            return
        selected = []
        # make a list of edges selected in the solution
        sol = model.cbGetSolution([model._vars[i] for i in range(nedges)])
        selected = [edges[i] for i, x in enumerate(sol) if x > .5]
        selected = [(idx[a], idx[b]) for a, b, w in selected]
        # find the shortest cycle in the selected edge list
        tour = subtour(selected)
        if len(tour) == n:
            return
        # add a subtour elimination constraint
        c = tour
        incident = [edge_store[a, b] for a, b in pairwise(c + [c[0]])]
        model.cbLazy(quicksum(model._vars[x]
                              for x in incident) <= len(tour) - 1)

    m.update()

    m._vars = vars
    m.params.LazyConstraints = 1
    m.optimize(subtourelim)

    selected = [v.varName for v in m.getVars() if v.x > .5]
    selected = [int(x) for x in selected if x[:2] != "u_"]
    results = sorted(x for i, x in enumerate(edges) if i in selected) \
        if selected else None
    return results
1207028
def gf_poly_eval(poly, x):
    ''''''
    y = poly[0]
    for i in xrange(1, len(poly)):
        y = gf_mul(y, x) ^ poly[i]
    return y
378501
def _solve(self, x0, A, l, u, xmin, xmax):
        
        # Indexes of constrained lines.
        il = [i for i,ln in enumerate(self._ln) if 0.0 < ln.rate_a < 1e10]
        nl2 = len(il)

        neqnln = 2 * self._nb # no. of non-linear equality constraints
        niqnln = 2 * len(il)  # no. of lines with constraints

        user_data = {"A": A, "neqnln": neqnln, "niqnln": niqnln}

        self._f(x0)
        Jdata = self._dg(x0, False, user_data)
#        Hdata = self._h(x0, ones(neqnln + niqnln), None, False, user_data)

        lmbda = {"eqnonlin": ones(neqnln),
                 "ineqnonlin": ones(niqnln)}
        H = tril(self._hessfcn(x0, lmbda), format="coo")
        self._Hrow, self._Hcol = H.row, H.col

        n = len(x0) # the number of variables
        xl = xmin
        xu = xmax
        gl = r_[zeros(2 * self._nb), -Inf * ones(2 * nl2), l]
        gu = r_[zeros(2 * self._nb),       zeros(2 * nl2), u]
        m = len(gl) # the number of constraints
        nnzj = len(Jdata) # the number of nonzeros in Jacobian matrix
        nnzh = 0#len(H.data) # the number of non-zeros in Hessian matrix

        f_fcn, df_fcn, g_fcn, dg_fcn, h_fcn = \
            self._f, self._df, self._g, self._dg, self._h

        nlp = pyipopt.create(n, xl, xu, m, gl, gu, nnzj, nnzh,
                             f_fcn, df_fcn, g_fcn, dg_fcn)#, h_fcn)

#        print dir(nlp)
#        nlp.str_option("print_options_documentation", "yes")
#        nlp.int_option("max_iter", 10)

#        x, zl, zu, obj = nlp.solve(x0)
        success = nlp.solve(x0, user_data)
        nlp.close()
1032013
def _expandGLQ(self, zeros, lmax, lmax_calc):
        """"""
        if self.normalization == '4pi':
            norm = 1
        elif self.normalization == 'schmidt':
            norm = 2
        elif self.normalization == 'unnorm':
            norm = 3
        elif self.normalization == 'ortho':
            norm = 4
        else:
            raise ValueError(
                "Normalization must be '4pi', 'ortho', 'schmidt', or " +
                "'unnorm'. Input value was {:s}"
                .format(repr(self.normalization)))

        if zeros is None:
            zeros, weights = _shtools.SHGLQ(self.lmax)

        data = _shtools.MakeGridGLQC(self.coeffs, zeros, norm=norm,
                                     csphase=self.csphase, lmax=lmax,
                                     lmax_calc=lmax_calc)
        gridout = SHGrid.from_array(data, grid='GLQ', copy=False)
        return gridout
32165
def xstep(self):
        """

        self.YU[:] = self.Y - self.U
        YUf = sl.rfftn(self.YU, None, self.cri.axisN)
        YUf0 = self.block_sep0(YUf)
        YUf1 = self.block_sep1(YUf)

        b = self.rho * np.sum(np.conj(self.GDf) * YUf1, axis=-1)
        if self.cri.Cd > 1:
            b = np.sum(b, axis=self.cri.axisC, keepdims=True)
        b += self.DSf + self.rho*YUf0

        # Concatenate multiple GDf components on axisC. For
        # single-channel signals, and multi-channel signals with a
        # single-channel dictionary, we end up with sl.solvemdbi_ism
        # solving a linear system of rank dimN+1 (corresponding to the
        # dictionary and a gradient operator per spatial dimension) plus
        # an identity. For multi-channel signals with a multi-channel
        # dictionary, we end up with sl.solvemdbi_ism solving a linear
        # system of rank C.d (dimN+1) (corresponding to the dictionary
        # and a gradient operator per spatial dimension for each
        # channel) plus an identity.

        # The structure of the linear system to be solved depends on the
        # number of channels in the signal and dictionary. Both branches are
        # the same in the single-channel signal case (the choice of handling
        # it via the 'else' branch is somewhat arbitrary).
        if self.cri.C > 1 and self.cri.Cd == 1:
            # Concatenate multiple GDf components on the final axis
            # of GDf (that indexes the number of gradient operators). For
            # multi-channel signals with a single-channel dictionary,
            # sl.solvemdbi_ism has to solve a linear system of rank dimN+1
            # (corresponding to the dictionary and a gradient operator per
            # spatial dimension)
            DfGDf = np.concatenate(
                [self.Df[..., np.newaxis],] +
                [np.sqrt(self.rho)*self.GDf[..., k, np.newaxis] for k
                 in range(self.GDf.shape[-1])], axis=-1)
            self.Xf[:] = sl.solvemdbi_ism(DfGDf, self.rho, b[..., np.newaxis],
                                          self.cri.axisM, -1)[..., 0]
        else:
            # Concatenate multiple GDf components on axisC. For multi-channel
            # signals with a multi-channel dictionary, sl.solvemdbi_ism has
            # to solve a linear system of rank C.d (dimN+1) (corresponding to
            # the dictionary and a gradient operator per spatial dimension
            # for each channel) plus an identity.
            DfGDf = np.concatenate(
                [self.Df,] + [np.sqrt(self.rho)*self.GDf[..., k] for k
                              in range(self.GDf.shape[-1])],
                axis=self.cri.axisC)
            self.Xf[:] = sl.solvemdbi_ism(DfGDf, self.rho, b, self.cri.axisM,
                                          self.cri.axisC)

        self.X = sl.irfftn(self.Xf, self.cri.Nv, self.cri.axisN)

        if self.opt['LinSolveCheck']:
            if self.cri.C > 1 and self.cri.Cd == 1:
                Dop = lambda x: sl.inner(DfGDf, x[..., np.newaxis],
                                         axis=self.cri.axisM)
                DHop = lambda x: sl.inner(np.conj(DfGDf), x, axis=-1)
                ax = DHop(Dop(self.Xf))[..., 0] + self.rho*self.Xf
            else:
                Dop = lambda x: sl.inner(DfGDf, x, axis=self.cri.axisM)
                DHop = lambda x: sl.inner(np.conj(DfGDf), x,
                                          axis=self.cri.axisC)
                ax = DHop(Dop(self.Xf)) + self.rho*self.Xf
            self.xrrs = sl.rrs(ax, b)
        else:
            self.xrrs = None
1135882
def solve_sdr(prob, *args, **kwargs):
    

    # lifted variables and semidefinite constraint
    X = cvx.Semidef(prob.n + 1)

    W = prob.f0.homogeneous_form()
    rel_obj = cvx.Minimize(cvx.sum_entries(cvx.mul_elemwise(W, X)))
    rel_constr = [X[-1, -1] == 1]

    for f in prob.fs:
        W = f.homogeneous_form()
        lhs = cvx.sum_entries(cvx.mul_elemwise(W, X))
        if f.relop == '==':
            rel_constr.append(lhs == 0)
        else:
            rel_constr.append(lhs <= 0)

    rel_prob = cvx.Problem(rel_obj, rel_constr)
    rel_prob.solve(*args, **kwargs)

    if rel_prob.status not in [cvx.OPTIMAL, cvx.OPTIMAL_INACCURATE]:
        raise Exception("Relaxation problem status: %s" % rel_prob.status)

    return X.value, rel_prob.value
357621
function makeAcyclic(g) {
    var onStack = {};
    var visited = {};

    function dfs(u) {
      if (u in visited) {
        return;
      }
      visited[u] = true;
      onStack[u] = true;
      g.successors(u).forEach(function(v) {
        if (v in onStack) {
          g.addEdge(v, u);
          g.removeEdge(u, v);
        } else {
          dfs(v);
        }
      });
      delete onStack[u];
    }

    g.nodes().forEach(function(u) {
      dfs(u);
    });
  }