广度优先遍历 Breadth-First-Search
559224
function breadthFirstSearch(obj, handler) {
  var childrenKey = arguments.length > 2 && arguments[2] !== undefined ? arguments[2] : 'children';
  var reverse = arguments[3];

  var rootChildren = hp.isArray(obj) ? obj : [obj];
  //
  var stack = rootChildren.map(function (v, i) {
    return { item: v, index: i };
  });
  if (reverse) {
    stack.reverse();
  }

  var _loop = function _loop() {
    var _stack$shift = stack.shift(),
        item = _stack$shift.item,
        index = _stack$shift.index,
        parent = _stack$shift.parent;

    var r = handler(item, index, parent);
    if (r === false) {
      // stop
      return {
        v: void 0
      };
    } else if (r === 'skip children') {
      return 'continue';
    } else if (r === 'skip siblings') {
      stack = stack.filter(function (v) {
        return v.parent !== parent;
      });
    }
    if (item.children) {
      var _stack;

      var children = item.children;
      if (reverse) {
        children = children.slice();
        children.reverse();
      }
      var pushStack = children.map(function (v, i) {
        return { item: v, index: i, parent: item };
      });
      (_stack = stack).push.apply(_stack, _toConsumableArray(pushStack));
    }
  };

  while (stack.length) {
    var _ret = _loop();

    switch (_ret) {
      case 'continue':
        continue;

      default:
        if ((typeof _ret === 'undefined' ? 'undefined' : _typeof(_ret)) === "object") return _ret.v;
    }
  }
}
274370
private void bfs(int[] membership, int cluster, int id) {
        int n = merge.length + 1;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(cluster);

        for (Integer i = queue.poll(); i != null; i = queue.poll()) {
            if (i < n) {
                membership[i] = id;
                continue;
            }

            i -= n;

            int m1 = merge[i][0];

            if (m1 >= n) {
                queue.offer(m1);
            } else {
                membership[m1] = id;
            }

            int m2 = merge[i][1];

            if (m2 >= n) {
                queue.offer(m2);
            } else {
                membership[m2] = id;
            }
        }
    }
989325
def B(u, v, dfs_data):
    """Bu(v) = {wx | w is in S*(v)}"""
    if a(v, dfs_data) != u:
        return None

    return list(set([edge_id for w in S_star(v, dfs_data) for edge_id in dfs_data['graph'].get_node(w)['edges']]))
858547
def breadth_first_vertex_order(vertices_resources, nets):
    
    # Special case: no vertices, just stop immediately
    if len(vertices_resources) == 0:
        return

    # Enumerate the set of nets attached to each vertex
    vertex_neighbours = defaultdict(set)
    for net in nets:
        # Note: Iterating over a Net object produces the set of vertices
        # involved in the net.
        vertex_neighbours[net.source].update(net)
        for sink in net.sinks:
            vertex_neighbours[sink].update(net)

    # Perform a breadth-first iteration over the vertices.
    unplaced_vertices = set(vertices_resources)
    vertex_queue = deque()
    while vertex_queue or unplaced_vertices:
        if not vertex_queue:
            vertex_queue.append(unplaced_vertices.pop())
        vertex = vertex_queue.popleft()

        yield vertex

        vertex_queue.extend(v for v in vertex_neighbours[vertex]
                            if v in unplaced_vertices)
        unplaced_vertices.difference_update(vertex_neighbours[vertex])
578084
public static <S, I, T, D> boolean breadthFirst(TransitionSystem<S, ? super I, T> ts,
                                                    int limit,
                                                    Collection<? extends I> inputs,
                                                    TSTraversalVisitor<S, I, T, D> vis) {
        Deque<BFSRecord<S, D>> bfsQueue = new ArrayDeque<>();

        // setting the following to false means that the traversal had to be aborted
        // due to reaching the limit
        boolean complete = true;
        int stateCount = 0;

        Holder<D> dataHolder = new Holder<>();

        for (S initS : ts.getInitialStates()) {
            dataHolder.value = null;
            TSTraversalAction act = vis.processInitial(initS, dataHolder);
            switch (act) {
                case ABORT_TRAVERSAL:
                    return complete;
                case EXPLORE:
                    if (stateCount != limit) {
                        bfsQueue.offer(new BFSRecord<>(initS, dataHolder.value));
                        stateCount++;
                    } else {
                        complete = false;
                    }
                    break;
                default: // case ABORT_INPUT: case ABORT_STATE: case IGNORE:
            }
        }

        while (!bfsQueue.isEmpty()) {
            BFSRecord<S, D> current = bfsQueue.poll();

            S state = current.state;
            D data = current.data;

            if (!vis.startExploration(state, data)) {
                continue;
            }

            inputs_loop:
            for (I input : inputs) {
                Collection<T> transitions = ts.getTransitions(state, input);

                for (T trans : transitions) {
                    S succ = ts.getSuccessor(trans);

                    dataHolder.value = null;
                    TSTraversalAction act = vis.processTransition(state, data, input, trans, succ, dataHolder);

                    switch (act) {
                        case ABORT_INPUT:
                            continue inputs_loop;
                        case ABORT_STATE:
                            break inputs_loop;
                        case ABORT_TRAVERSAL:
                            return complete;
                        case EXPLORE:
                            if (stateCount != limit) {
                                bfsQueue.offer(new BFSRecord<>(succ, dataHolder.value));
                                stateCount++;
                            } else {
                                complete = false;
                            }
                            break;
                        case IGNORE:
                            break;
                        default:
                            throw new IllegalStateException("Unknown action " + act);
                    }
                }
            }
        }

        return complete;
    }
994365
function graph(g) {
    init(g);

    var xs = [upperLeft(g), upperRight(g), lowerRight(g), lowerLeft(g)];

    g.nodes().forEach(function(u) {
      var xArray = [];
      for (var i = 0; i < xs.length; ++i) {
        xArray.push(xs[i][u]);
      }
      xArray.sort();
      g.node(u).x = (xArray[1] + xArray[2]) / 2;
    });
  }
218625
private int findFirst(CharSequence input, int beginIndex, int rewindIndex) {
        int first = -1;
        boolean atomBoundary = true;
        for (int i = beginIndex; i >= rewindIndex; i--) {
            char c = input.charAt(i);
            if (localAtomAllowed(c)) {
                first = i;
                atomBoundary = false;
            } else if (c == '.') {
                if (atomBoundary) {
                    break;
                }
                atomBoundary = true;
            } else {
                break;
            }
        }
        return first;
    }
834107
def bfd(items, targets, **kwargs):
    
    sizes = zip(items, weight(items, **kwargs))
    sizes = sorted(sizes, key=operator.itemgetter(1), reverse=True)
    items = map(operator.itemgetter(0), sizes)
    return bf(items, targets, **kwargs)
435820
function tightTree(t, g) {
  function dfs(v) {
    _.forEach(g.nodeEdges(v), function(e) {
      var edgeV = e.v,
        w = (v === edgeV) ? e.w : edgeV;
      if (!t.hasNode(w) && !slack(g, e)) {
        t.setNode(w, {});
        t.setEdge(v, w, {});
        dfs(w);
      }
    });
  }

  _.forEach(t.nodes(), dfs);
  return t.nodeCount();
}
276392
private void initNShortPath(Graph inGraph, int nValueKind)
    {
        graph = inGraph;
        N = nValueKind;

        // 获取顶点的数目
        vertexCount = inGraph.vertexes.length;

        fromArray = new CQueue[vertexCount - 1][];  // 不包含起点
        weightArray = new double[vertexCount - 1][];

        //每个节点的最小堆
        for (int i = 0; i < vertexCount - 1; i++)
        {
            fromArray[i] = new CQueue[nValueKind];
            weightArray[i] = new double[nValueKind];

            for (int j = 0; j < nValueKind; j++)
                fromArray[i][j] = new CQueue();
        }
    }
1296648
function inxsearch(b, g, r) {
    var a, p, dist;

    var bestd = 1000; // biggest possible dist is 256*3
    var best = -1;

    var i = netindex[g]; // index on g
    var j = i - 1; // start at netindex[g] and work outwards

    while ((i < netsize) || (j >= 0)) {
      if (i < netsize) {
        p = network[i];
        dist = p[1] - g; // inx key
        if (dist >= bestd) i = netsize; // stop iter
        else {
          i++;
          if (dist < 0) dist = -dist;
          a = p[0] - b; if (a < 0) a = -a;
          dist += a;
          if (dist < bestd) {
            a = p[2] - r; if (a < 0) a = -a;
            dist += a;
            if (dist < bestd) {
              bestd = dist;
              best = p[3];
            }
          }
        }
      }
      if (j >= 0) {
        p = network[j];
        dist = g - p[1]; // inx key - reverse dif
        if (dist >= bestd) j = -1; // stop iter
        else {
          j--;
          if (dist < 0) dist = -dist;
          a = p[0] - b; if (a < 0) a = -a;
          dist += a;
          if (dist < bestd) {
            a = p[2] - r; if (a < 0) a = -a;
            dist += a;
            if (dist < bestd) {
              bestd = dist;
              best = p[3];
            }
          }
        }
      }
    }

    return best;
  }
1122369
def bfs_search_tree_from (v)
      require 'laser/third_party/rgl/adjacency'
      bfs  = bfs_iterator(v)
      tree = DirectedAdjacencyGraph.new
      bfs.set_tree_edge_event_handler { |from, to|
        tree.add_edge(from, to)
      }
      bfs.set_to_end				# does the search
      tree
    end
613094
private void calculate(Graph inGraph, int nValueKind)
    {
        initNShortPath(inGraph, nValueKind);

        QueueElement tmpElement;
        CQueue queWork = new CQueue();
        double eWeight;

        for (int nCurNode = 1; nCurNode < vertexCount; ++nCurNode)
        {
            // 将所有到当前结点（nCurNode)可能到达的边根据eWeight排序并压入队列
            enQueueCurNodeEdges(queWork, nCurNode);

            // 初始化当前结点所有边的eWeight值
            for (int i = 0; i < N; ++i)
                weightArray[nCurNode - 1][i] = Double.MAX_VALUE;

            // 将queWork中的内容装入fromArray
            tmpElement = queWork.deQueue();
            if (tmpElement != null)
            {
                for (int i = 0; i < N; ++i)
                {
                    eWeight = tmpElement.weight;
                    weightArray[nCurNode - 1][i] = eWeight;
                    do
                    {
                        fromArray[nCurNode - 1][i].enQueue(new QueueElement(tmpElement.from, tmpElement.index, 0));
                        tmpElement = queWork.deQueue();
                        if (tmpElement == null)
                        {
                            i = N;
                            break;
                        }
                    } while (tmpElement.weight == eWeight);
                }
            }
        }
    }
581925
def bfs(self, graph, start):
        
        newstatediag = {}

        # maintain a queue of paths
        queue = []
        visited = []
        # push the first path into the queue
        queue.append(start)
        while queue:
            # get the first path from the queue
            state = queue.pop(0)
            # get the last node from the path
            # visited
            visited.append(state.id)
            # enumerate all adjacent nodes, construct a new path and push it
            # into the queue
            for key in state.trans:
                if state.trans[key] != []:
                    if key not in visited:
                        for nextstate in graph:
                            if graph[nextstate].id == key:
                                queue.append(graph[nextstate])
                                break
        i = 0
        for state in graph:
            if graph[state].id in visited:
                newstatediag[i] = graph[state]
                i = i + 1

        return newstatediag
1284515
def BFS_Tree(G, start):
    
    if start not in G.vertices:
        raise GraphInsertError("Vertex %s doesn't exist." % (start,))
    pred = BFS(G, start)
    T = digraph.DiGraph()
    queue = Queue()
    queue.put(start)
    while queue.qsize() > 0:
        current = queue.get()
        for element in pred:
            if pred[element] == current:
                T.add_edge(current, element)
                queue.put(element)
    return T
778486
def bpp(s,B):
    
    n = len(s)
    U = len(FFD(s,B)) # upper bound of the number of bins
    model = Model("bpp")
    # setParam("MIPFocus",1)
    x,y = {},{}
    for i in range(n):
        for j in range(U):
            x[i,j] = model.addVar(vtype="B", name="x(%s,%s)"%(i,j))
    for j in range(U):
        y[j] = model.addVar(vtype="B", name="y(%s)"%j)

    # assignment constraints
    for i in range(n):
        model.addCons(quicksum(x[i,j] for j in range(U)) == 1, "Assign(%s)"%i)

    # bin capacity constraints
    for j in range(U):
        model.addCons(quicksum(s[i]*x[i,j] for i in range(n)) <= B*y[j], "Capac(%s)"%j)

    # tighten assignment constraints
    for j in range(U):
        for i in range(n):
            model.addCons(x[i,j] <= y[j], "Strong(%s,%s)"%(i,j))

    # tie breaking constraints
    for j in range(U-1):
        model.addCons(y[j] >= y[j+1],"TieBrk(%s)"%j)

    # SOS constraints
    for i in range(n):
        model.addConsSOS1([x[i,j] for j in range(U)])

    model.setObjective(quicksum(y[j] for j in range(U)), "minimize")
    model.data = x,y

    return model
902679
def _binary_search(f, xmin, xmax, eps=1e-9):
    """"""
    middle = (xmax + xmin) / 2.
    while xmax - xmin > eps:
        assert xmin < xmax
        middle = (xmax + xmin) / 2.
        if f(xmax):
            return xmax
        if not f(xmin):
            return xmin
        if f(middle):
            xmin = middle
        else:
            xmax = middle
    return middle