Internal recursive backtracking algorithm.
434678
def _backtracking(problem, assignment, domains, variable_chooser, values_sorter, inference=True):
    '''
    
    '''
    from simpleai.search.arc import arc_consistency_3
    if len(assignment) == len(problem.variables):
        return assignment

    pending = [v for v in problem.variables
               if v not in assignment]
    variable = variable_chooser(problem, pending, domains)

    values = values_sorter(problem, assignment, variable, domains)

    for value in values:
        new_assignment = deepcopy(assignment)
        new_assignment[variable] = value

        if not _count_conflicts(problem, new_assignment):  # TODO on aima also checks if using fc
            new_domains = deepcopy(domains)
            new_domains[variable] = [value]

            if not inference or arc_consistency_3(new_domains, problem.constraints):
                result = _backtracking(problem,
                                       new_assignment,
                                       new_domains,
                                       variable_chooser,
                                       values_sorter,
                                       inference=inference)
                if result:
                    return result

    return None
777092
function tree(d, i) {
    var nodes = hierarchy.call(this, d, i),
        t = nodes[0],
        wt = wrapTree(t);

    wroot = wt;
    zerothWalk(wt, 0);
    firstWalk(wt);
    secondWalk(wt, 0);
    renormalize(wt);

    return nodes;
  }
676514
private void traverseClassMembers(Node n) {
    for (Node child = n.getFirstChild(); child != null;) {
      Node next = child.getNext(); // see traverseChildren
      if (child.isComputedProp()) {
        curNode = n;
        if (callback.shouldTraverse(this, child, n)) {
          traverseBranch(child.getLastChild(), child);
          curNode = n;
          callback.visit(this, child, n);
        }
      } else {
        traverseBranch(child, n);
      }
      child = next;
    }
  }
404947
def _solve_tsp(dist, niter):
    

    # number of nodes
    N = dist.shape[0]

    # tsp path for quick calculation of cost
    ii = np.arange(N)
    jj = np.hstack((np.arange(1, N), 0))

    # for each node, cache a sorted list of all other nodes in order of
    # increasing distance.
    dsort = [np.argsort(d) for d in dist]
    dsort = [d[d != i] for i, d in enumerate(dsort)]

    # randomly initialize path through graph
    path = np.random.permutation(N)
    idx = np.argsort(path)
    cost = np.sum(dist[path[ii], path[jj]])

    # keep track of objective function over time
    cost_hist = [cost]

    # optimization loop
    node = 0
    itercount = 0
    n = 0

    while n < N and itercount < niter:

        # count iterations
        itercount += 1

        # we'll try breaking the connection i -> j
        i = path[node]
        j = path[(node+1) % N]

        # We are breaking i -> j so we can remove the cost of that connection.
        c = cost - dist[i, j]

        # Search over nodes k that are closer to j than i.
        for k in dsort[j]:

            # Can safely continue if dist[i,j] < dist[k,j] for the remaining k.
            if k == i:
                n += 1
                break

            # Break connection k -> p.
            # Add connection j -> p.
            # Add connection i -> k.
            p = path[(idx[k]+1) % N]
            new_cost = c - dist[k, p] + dist[j, p] + dist[i, k]

            # If this swap improves the cost, implement it and move to next i.
            if new_cost < cost:
                path = reverse_segment(path, idx[j], idx[k])
                idx = np.argsort(path)
                cost = new_cost
                # Restart from the begining of the graph.
                cost_hist.append(cost)
                n = 0
                break

        # move to next node
        node = (node + 1) % N

    return path, cost_hist
48608
def _backward_slice_indirect(self, cfgnode, sim_successors, current_function_addr):
        
        # TODO: make this a real indirect jump resolver under the new paradigm

        irsb = sim_successors.artifacts['irsb']  # shorthand

        l.debug("Resolving indirect jump at IRSB %s", irsb)

        # Let's slice backwards from the end of this exit
        next_tmp = irsb.next.tmp
        stmt_id = [i for i, s in enumerate(irsb.statements)
                   if isinstance(s, pyvex.IRStmt.WrTmp) and s.tmp == next_tmp][0]

        cdg = self.project.analyses.CDG(cfg=self, fail_fast=self._fail_fast)
        ddg = self.project.analyses.DDG(cfg=self, start=current_function_addr, call_depth=0, fail_fast=self._fail_fast)

        bc = self.project.analyses.BackwardSlice(self,
                                                 cdg,
                                                 ddg,
                                                 targets=[(cfgnode, stmt_id)],
                                                 same_function=True,
                                                 fail_fast=self._fail_fast)
        taint_graph = bc.taint_graph
        # Find the correct taint
        next_nodes = [cl for cl in taint_graph.nodes() if cl.block_addr == sim_successors.addr]

        if not next_nodes:
            l.error('The target exit is not included in the slice. Something is wrong')
            return []

        next_node = next_nodes[0]

        # Get the weakly-connected subgraph that contains `next_node`
        all_subgraphs = networkx.weakly_connected_component_subgraphs(taint_graph)
        starts = set()
        for subgraph in all_subgraphs:
            if next_node in subgraph:
                # Make sure there is no symbolic read...
                # FIXME: This is an over-approximation. We should try to limit the starts more
                nodes = [n for n in subgraph.nodes() if subgraph.in_degree(n) == 0]
                for n in nodes:
                    starts.add(n.block_addr)

        # Execute the slice
        successing_addresses = set()
        annotated_cfg = bc.annotated_cfg()
        for start in starts:
            l.debug('Start symbolic execution at 0x%x on program slice.', start)
            # Get the state from our CFG
            node = self.get_any_node(start)
            if node is None:
                # Well, we have to live with an empty state
                base_state = self.project.factory.blank_state(addr=start)
            else:
                base_state = node.input_state.copy()
                base_state.set_mode('symbolic')
                base_state.ip = start

                # Clear all initial taints (register values, memory values, etc.)
                initial_nodes = [n for n in bc.taint_graph.nodes() if bc.taint_graph.in_degree(n) == 0]
                for cl in initial_nodes:
                    # Iterate in all actions of this node, and pick corresponding actions
                    cfg_nodes = self.get_all_nodes(cl.block_addr)
                    for n in cfg_nodes:
                        if not n.final_states:
                            continue
                        actions = [ac for ac in n.final_states[0].history.recent_actions
                                   # Normally it's enough to only use the first final state
                                   if ac.bbl_addr == cl.block_addr and
                                   ac.stmt_idx == cl.stmt_idx
                                   ]
                        for ac in actions:
                            if not hasattr(ac, 'action'):
                                continue
                            if ac.action == 'read':
                                if ac.type == 'mem':
                                    unconstrained_value = base_state.solver.Unconstrained('unconstrained',
                                                                                      ac.size.ast * 8)
                                    base_state.memory.store(ac.addr,
                                                            unconstrained_value,
                                                            endness=self.project.arch.memory_endness)
                                elif ac.type == 'reg':
                                    unconstrained_value = base_state.solver.Unconstrained('unconstrained',
                                                                                      ac.size.ast * 8)
                                    base_state.registers.store(ac.offset,
                                                               unconstrained_value,
                                                               endness=self.project.arch.register_endness)

                # Clear the constraints!
                base_state.release_plugin('solver')

            # For speed concerns, we are limiting the timeout for z3 solver to 5 seconds
            base_state.solver._solver.timeout = 5000

            sc = self.project.factory.simulation_manager(base_state)
            sc.use_technique(Slicecutor(annotated_cfg))
            sc.use_technique(LoopSeer(bound=1))
            sc.run()

            if sc.cut or sc.deadended:
                all_deadended_states = sc.cut + sc.deadended
                for s in all_deadended_states:
                    if s.addr == sim_successors.addr:
                        # We want to get its successors
                        succs = s.step()
                        for succ in succs.flat_successors:
                            successing_addresses.add(succ.addr)

            else:
                l.debug("Cannot determine the exit. You need some better ways to recover the exits :-(")

        l.debug('Resolution is done, and we have %d new successors.', len(successing_addresses))

        return list(successing_addresses)
1223849
def walk_recursive(f, data):
    
    results = {}
    if isinstance(data, list):
        return [walk_recursive(f, d) for d in data]
    elif isinstance(data, dict):
        results = funcy.walk_keys(f, data)

        for k, v in data.iteritems():
            if isinstance(v, dict):
                results[f(k)] = walk_recursive(f, v)
            elif isinstance(v, list):
                results[f(k)] = [walk_recursive(f, d) for d in v]
    else:
        return f(data)

    return results
1177059
def find_path(start, goal, neighbors_fnct, reversePath=False, heuristic_cost_estimate_fnct=lambda a, b: Infinite, distance_between_fnct=lambda a, b: 1.0, is_goal_reached_fnct=lambda a, b: a == b):
    """"""
    class FindPath(AStar):

        def heuristic_cost_estimate(self, current, goal):
            return heuristic_cost_estimate_fnct(current, goal)

        def distance_between(self, n1, n2):
            return distance_between_fnct(n1, n2)

        def neighbors(self, node):
            return neighbors_fnct(node)

        def is_goal_reached(self, current, goal):
            return is_goal_reached_fnct(current, goal)
    return FindPath().astar(start, goal, reversePath)
477179
def find_cycles(self):
        """"""

        # Apply the Tarjan's algorithm successively until all functions are visited
        stack = []
        data = {}
        order = 0
        for function in compat_itervalues(self.functions):
            order = self._tarjan(function, order, stack, data)
        cycles = []
        for function in compat_itervalues(self.functions):
            if function.cycle is not None and function.cycle not in cycles:
                cycles.append(function.cycle)
        self.cycles = cycles
        if 0:
            for cycle in cycles:
                sys.stderr.write("Cycle:\n")
                for member in cycle.functions:
                    sys.stderr.write("\tFunction %s\n" % member.name)
1204526
def _elimination_trees(theta, decision_variables):
    
    # auxiliary variables are any variables that are not decision
    auxiliary_variables = set(n for n in theta.linear if n not in decision_variables)

    # get the adjacency of the auxiliary subgraph
    adj = {v: {u for u in theta.adj[v] if u in auxiliary_variables}
           for v in theta.adj if v in auxiliary_variables}

    # get the elimination order that minimizes treewidth
    tw, order = dnx.treewidth_branch_and_bound(adj)

    ancestors = {}
    for n in order:
        ancestors[n] = set(adj[n])

        # now make v simplicial by making its neighborhood a clique, then
        # continue
        neighbors = adj[n]
        for u, v in itertools.combinations(neighbors, 2):
            adj[u].add(v)
            adj[v].add(u)
        for v in neighbors:
            adj[v].discard(n)
        del adj[n]

    roots = {}
    nodes = {v: {} for v in ancestors}
    for vidx in range(len(order) - 1, -1, -1):
        v = order[vidx]

        if ancestors[v]:
            for u in order[vidx + 1:]:
                if u in ancestors[v]:
                    # v is a child of u
                    nodes[u][v] = nodes[v]  # nodes[u][v] = children of v
                    break
        else:
            roots[v] = nodes[v]  # roots[v] = children of v

    return roots, ancestors
921105
private void backpropagate(Layer upper, Layer lower) {
        for (int i = 0; i <= lower.units; i++) {
            double out = lower.output[i];
            double err = 0;
            for (int j = 0; j < upper.units; j++) {
                err += upper.weight[j][i] * upper.error[j];
            }
            if (activationFunction==ActivationFunction.LOGISTIC_SIGMOID) {
                lower.error[i] = out * (1.0 - out) * err;
            }
            else if (activationFunction==ActivationFunction.TANH){
                lower.error[i] = (1-(out*out))*err;
            }
        }
    }
160598
def Recurrent(step_model):
    """"""
    ops = step_model.ops

    def recurrent_fwd(seqs, drop=0.0):
        lengths = [len(X) for X in seqs]
        X, size_at_t, unpad = ops.square_sequences(seqs)
        Y = ops.allocate((X.shape[0], X.shape[1], step_model.nO))
        cell_drop = ops.get_dropout_mask((len(seqs), step_model.nO), 0.0)
        hidden_drop = ops.get_dropout_mask((len(seqs), step_model.nO), 0.0)
        out_drop = ops.get_dropout_mask((len(seqs), step_model.nO), 0.0)
        backprops = [None] * max(lengths)
        state = step_model.weights.get_initial_state(len(seqs))
        for t in range(max(lengths)):
            state = list(state)
            size = size_at_t[t]
            Xt = X[t, :size]
            state[0] = state[0][:size]
            state[1] = state[1][:size]
            if cell_drop is not None:
                state[0] *= cell_drop
            if hidden_drop is not None:
                state[1] *= hidden_drop
            inputs = (state, Xt)
            (state, Y[t, :size]), backprops[t] = step_model.begin_update(inputs)
            if out_drop is not None:
                Y[t, :size] *= out_drop
        outputs = unpad(Y)

        def recurrent_bwd(d_outputs, sgd=None):
            dY, size_at_t, unpad = step_model.ops.square_sequences(d_outputs)
            d_state = [
                step_model.ops.allocate((dY.shape[1], step_model.nO)),
                step_model.ops.allocate((dY.shape[1], step_model.nO)),
            ]
            updates = {}

            def gather_updates(weights, gradient, key=None):
                updates[key] = (weights, gradient)

            dX = step_model.ops.allocate(
                (dY.shape[0], dY.shape[1], step_model.weights.nI)
            )
            for t in range(max(lengths) - 1, -1, -1):
                if out_drop is not None:
                    dY[t] *= out_drop
                d_state_t, dXt = backprops[t]((d_state, dY[t]), sgd=gather_updates)
                d_state[0][: d_state_t[0].shape[0]] = d_state_t[0]
                d_state[1][: d_state_t[1].shape[0]] = d_state_t[1]
                dX[t, : dXt.shape[0]] = dXt
                if cell_drop is not None:
                    d_state[0] *= cell_drop
                if hidden_drop is not None:
                    d_state[1] *= hidden_drop
            d_cell, d_hidden = d_state
            step_model.weights.d_initial_cells += d_cell.sum(axis=0)
            step_model.weights.d_initial_hiddens += d_hidden.sum(axis=0)
            if sgd is not None:
                for key, (weights, gradient) in updates.items():
                    sgd(weights, gradient, key=key)
            return unpad(dX)

        return outputs, recurrent_bwd

    model = wrap(recurrent_fwd, step_model)
    model.nO = step_model.nO
    return model
235785
def backtrack(self, source):
        """"""
        key = self.get_tok(source)
        s = self[key]()
        meta = s.metadata['original_source']
        cls = meta['cls']
        args = meta['args']
        kwargs = meta['kwargs']
        cls = import_name(cls)
        sout = cls(*args, **kwargs)
        sout.metadata = s.metadata['original_metadata']
        sout.name = s.metadata['original_name']
        return sout
443632
private int calculatePositionViaBreakingForwards(int numOfBreaks, BreakIterator breakIterator, int position) {
        breakIterator.following(position);
        for (int i = 1; i < numOfBreaks; i++) {
            breakIterator.next(numOfBreaks);
        }
        return breakIterator.current();
    }
1119343
def backtrack(self, decision_level):  # type: (int) -> None
        
        self._backtracking = True

        packages = set()
        while self._assignments[-1].decision_level > decision_level:
            removed = self._assignments.pop(-1)
            packages.add(removed.dependency.name)
            if removed.is_decision():
                del self._decisions[removed.dependency.name]

        # Re-compute _positive and _negative for the packages that were removed.
        for package in packages:
            if package in self._positive:
                del self._positive[package]

            if package in self._negative:
                del self._negative[package]

        for assignment in self._assignments:
            if assignment.dependency.name in packages:
                self._register(assignment)
1280850
private void search(int v, long prev, long curr) {

        state[v] = curr; // store the state before we visited v
        curr = setBit(curr, v); // include v in our current state (state[v] is unmodified)
        visited |= curr; // mark v as visited (or being visited)

        // neighbors of v
        for (int w : g[v]) {

            // w has been visited or is partially visited further up stack
            if (visited(w)) {

                // if w is in our prev state we have a cycle of size >2.
                // we don't check out current state as this will always
                // include w - they are adjacent
                if (isBitSet(prev, w)) {
                    numCycles++;

                    // xor the state when we last visited 'w' with our current
                    // state. this set is all the vertices we visited since then
                    // and are all in a cycle
                    add(state[w] ^ curr);
                }
            } else {
                // recursively call for the unvisited neighbor w
                search(w, state[v], curr);
            }
        }
    }
668030
@Override
    public void backward() {
        Tensor depAdj = depIn.getOutputAdj();
        int n = depAdj.getDims()[1];
        for (int v=0; v<yAdj.varBeliefs.length; v++) {
            if (yAdj.varBeliefs[v] != null) {
                Var var = y.varBeliefs[v].getVars().get(0);
                if (var instanceof LinkVar) {
                    LinkVar link = (LinkVar) var;
                    int p = link.getParent();
                    int c = link.getChild();
                    int pp = EdgeScores.getTensorParent(p, c);
                    assert p < n && c < n;
                    
                    // Add the adjoint of b(e_{p,c} = True).
                    depAdj.add(yAdj.varBeliefs[v].getValue(LinkVar.TRUE), pp, c);
                    // Add the adjoint of b(e_{p,c} = False)
                    depAdj.subtract(yAdj.varBeliefs[v].getValue(LinkVar.FALSE), pp, c);
                }
            }
        }
    }
765481
def solve_scalarization(n,c,t):
    

    model = base_model(n,c,t)   # base model for minimizing cost or time
    x,u,C,T = model.data

    def explore(C1,T1,C2,T2,front):
        """explore: recursively try to find new non-dominated solutions with a scaled objective
        Parameters:
            - C1,T1: cost and time of leftmost point
            - C1,T1: cost and time of rightmost point
            - front: current set of non-dominated solutions
        Returns the updated front
        """
        alpha = float(C1 - C2)/(T2 - T1)
        # print("%s,%s -- %s,%s  (%s)..." % (C1,T1,C2,T2,alpha)
        init = list(front)
        model.setObjective(quicksum((c[i,j] + alpha*t[i,j])*x[i,j] for (i,j) in x), "minimize")
        optimize(model,front)
        front = pareto_front(front)
        # print("... added %s points" % (len(front)-len(init))
        if front == init:
            # print("no points added, returning"
            return front

        CM = model.getVal(C)
        TM = model.getVal(T)
        # print("will explore %s,%s -- %s,%s and %s,%s -- %s,%s" % (C1,T1,CM,TM,CM,TM,C2,T2)
        if TM > T1:
            front = explore(C1,T1,CM,TM,front)
        if T2 > TM:
            front = explore(CM,TM,C2,T2,front)
        return front


    # store the set of solutions for plotting
    cand = []       # to store the set of solutions for plotting
    model.setObjective(T, "minimize")

    stat = optimize(model,cand)
    if stat != "optimal":
        return []
    C1 = model.getVal(C)
    T1 = model.getVal(T)

    # change the objective function to minimize the travel cost
    model.setObjective(C, "minimize")

    stat = optimize(model,cand)
    if stat != "optimal":
        return []
    C2 = model.getVal(C)
    T2 = model.getVal(T)

    front = pareto_front(cand)
    return explore(C1,T1,C2,T2,front)