Breadth first search
181976
public ImageSource BFS(int startI, int startJ, /*String imageName*/ImageSource originalImage) {
        LinkedList<Vector2i> queue = new LinkedList<>();

        //=============================================================================

        int gapX = 30;
        int gapY = 30;

        MatrixSource letter = new MatrixSource(letterWidth, letterHeight);

        //BufferedImage letter = new BufferedImage(letterWidth, letterHeight, BufferedImage.TYPE_BYTE_BINARY);
        int alpha = originalImage.getA(startI, startJ);
        int white = ColorHelper.getARGB(255, 255, 255, alpha);
        int black = ColorHelper.getARGB(0, 0, 0, alpha);

        for (int j = 0; j < letterHeight; j++) {
            for (int i = 0; i < letterWidth; i++) {
                letter.setRGB(i, j, white);
            }
        }
        //=============================================================================

        int count = 0;
        Vector2i positions = new Vector2i(startI, startJ);
        visited[startI][startJ] = true;
        queue.addLast(positions);

        while (!queue.isEmpty()) {
            Vector2i pos = queue.removeFirst();

            int x = pos.getX();
            int y = pos.getY();
            visited[x][y] = true;

            //set black pixel to letter image===================================
            int posX = startI - x + gapX;
            int posY = startJ - y + gapY;

            count++;

            if(posX>=originalImage.getWidth() || posY>=originalImage.getHeight()) {
                continue;
            } else {
                letter.setRGB(posX, posY, black);
                /*try {
                    letter.setRGB(posX, posY, black);
                } catch (Exception e) {
                    e.printStackTrace();
                    System.out.println("posX " + posX);
                    System.out.println("posY " + posY);
                    System.out.println("letterWidth " + letter.getWidth());
                    System.out.println("letterHeight " + letter.getHeight());
                    throw e;
                }*/
            }

            //==================================================================
            for (int i = x - 1; i <= x + 1; i++) {
                for (int j = y - 1; j <= y + 1; j++) {
                    if (i >= 0 && j >= 0 && i < originalImage.getWidth() && j < originalImage.getHeight()) {
                        if (!visited[i][j]) {
                            int color = originalImage.getGray(i, j);
                            if (color < 10) {
                                visited[i][j] = true;
                                Vector2i tmpPos = new Vector2i(i, j);
                                queue.addLast(tmpPos);
                            }
                        }
                    }
                } //i
            } //j
        }

        System.out.println("count = " + count);
        //save letter===========================================================
        if (count < 3) {
            return letter;
        }
        /*try {
            saveToFile(letter, imageName);
            //
        } catch (IOException ex) {
            ex.printStackTrace();
        }*/

        return letter;
    }
539281
function bfrac(a, b, x, y) {
      var lambda;

      lambda = a - (a + b) * x;
      return brcomp(a, b, x, y) + Math.log(contFrac(
         function(i) { // betas from DiDonato
            var n;

            n = i - 1;
            return i === 0 ? 0
                           : n + n * (b - n) * x / (a + 2 * n - 1) +
                             (a + n) / (a + 2 * n + 1) *
                                (lambda + 1 + n * (1 + y));
         },
         function(i) { // alphas from DiDonato
            var n;

            n = i - 1;
            return i === 1 ? 1
                           : (a + n - 1) * (a + b + n - 1) /
                             (a + 2 * n - 1) / (a + 2 * n - 1) *
                             n * (b - n) * x * x;
         }
      ));
   }
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
1052112
def bfs(graph, start=0):
    
    to_visit = deque()
    dist = [float('inf')] * len(graph)
    prec = [None] * len(graph)
    dist[start] = 0
    to_visit.appendleft(start)
    while to_visit:              # an empty queue is considered False
        node = to_visit.pop()
        for neighbor in graph[node]:
            if dist[neighbor] == float('inf'):
                dist[neighbor] = dist[node] + 1
                prec[neighbor] = node
                to_visit.appendleft(neighbor)
    return dist, prec
1177206
def _walk_breadth(
        self,
        fs,  # type: FS
        path,  # type: Text
        namespaces=None,  # type: Optional[Collection[Text]]
    ):
        # type: (...) -> Iterator[Tuple[Text, Optional[Info]]]
        
        queue = deque([path])
        push = queue.appendleft
        pop = queue.pop

        _combine = combine
        _scan = self._scan
        _calculate_depth = self._calculate_depth
        _check_open_dir = self._check_open_dir
        _check_scan_dir = self._check_scan_dir
        _check_file = self.check_file

        depth = _calculate_depth(path)

        while queue:
            dir_path = pop()
            for info in _scan(fs, dir_path, namespaces=namespaces):
                if info.is_dir:
                    _depth = _calculate_depth(dir_path) - depth + 1
                    if _check_open_dir(fs, dir_path, info):
                        yield dir_path, info  # Opened a directory
                        if _check_scan_dir(fs, dir_path, info, _depth):
                            push(_combine(dir_path, info.name))
                else:
                    if _check_file(fs, info):
                        yield dir_path, info  # Found a file
            yield dir_path, None
609852
function bfsOrder(root) {
    var inqueue = [root], outqueue = [];
    root._bfs_parent = null;
    while (inqueue.length > 0) {
      var elem = inqueue.shift();
      outqueue.push(elem);
      var children = elem.childNodes;
      var liParent = null;
      for (var i=0 ; i<children.length; i++) {
        if (children[i].nodeType == 1) {// element node
          if (children[i].tagName === 'LI') {
            liParent = children[i];
          } else if ((children[i].tagName === 'UL' || children[i].tagName === 'OL') && liParent) {
            liParent.appendChild(children[i]);
            i--;
            continue;
          } 
          children[i]._bfs_parent = elem;
          inqueue.push(children[i]);
        }
      }
    }
    outqueue.shift();
    return outqueue;
  }
1355420
function closeness(graph, oriented) {
  var Q = [];
  // list of predecessors on shortest paths from source
  // distance from source
  var dist = Object.create(null);

  var currentNode;
  var centrality = Object.create(null);

  graph.forEachNode(setCentralityToZero);
  graph.forEachNode(calculateCentrality);

  return centrality;

  function setCentralityToZero(node) {
    centrality[node.id] = 0;
  }

  function calculateCentrality(node) {
    currentNode = node.id;
    singleSourceShortestPath(currentNode);
    accumulate();
  }

  function accumulate() {
    // Add all distances for node to array, excluding -1s
    var distances = Object.keys(dist).map(function(key) {return dist[key]}).filter(function(val){return val !== -1});
    // Set number of reachable nodes
    var reachableNodesTotal = distances.length;
    // Compute sum of all distances for node
    var totalDistance = distances.reduce(function(a,b) { return a + b });
    if (totalDistance > 0) {
      centrality[currentNode] = ((reachableNodesTotal - 1) / totalDistance); 
    } else {
      centrality[currentNode] = 0;
    }
  }

  function singleSourceShortestPath(source) {
    graph.forEachNode(initNode);
    dist[source] = 0;
    Q.push(source);

    while (Q.length) {
      var v = Q.shift();
      graph.forEachLinkedNode(v, processNode, oriented);
    }

    function initNode(node) {
      var nodeId = node.id;
      dist[nodeId] = -1;
    }

    function processNode(otherNode) {
      var w = otherNode.id
      if (dist[w] === -1) {
        // Node w is found for the first time
        dist[w] = dist[v] + 1;
        Q.push(w);
      }
    }
  }
}
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();
}
584827
def find_minimum_spanning_forest_as_subgraphs(graph):
    """"""
    forest = find_minimum_spanning_forest(graph)
    list_of_subgraphs = [get_subgraph_from_edge_list(graph, edge_list) for edge_list in forest]

    return list_of_subgraphs
921897
private static int binarySearch(int[] a, int start, int end, int key) {
        int lo = start, hi = end-1; // search range is [lo,hi]

        // invariant lo<=hi
        while (lo <= hi) {
            int pivot = (lo + hi)/2;
            int v = a[pivot];

            if (v < key)        // needs to search upper half
                lo = pivot+1;
            else if (v > key)   // needs to search lower half
                hi = pivot-1;
            else    // eureka!
                return pivot;
        }
        return -(lo + 1); // insertion point
    }
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
1311672
private void findBestWithFirst(DatanodeDescriptor first,
      List<DatanodeDescriptor> listOfNodes, DatanodeDescriptor[] result) {
    for (int in2 = 0; in2 < listOfNodes.size(); in2++) {
      DatanodeDescriptor n2 = listOfNodes.get(in2);
      if (!first.equals(n2)) {
        if (result[1] == null && inWindow(first, n2)) {
          result[0] = first;
          result[1] = n2;
        }

        for (int in3 = in2 + 1; in3 < listOfNodes.size(); in3++) {
          DatanodeDescriptor n3 = listOfNodes.get(in3);
          if (!first.equals(n3)
              && inWindow(first, n3, n2)) {
            result[0] = first;
            result[1] = n2;
            result[2] = n3;
            return;
          }
        }
      }
    }
  }
189080
function walkNodesBreadthFirstHelper(ast, f) {
  let childAst = [];
  (ast || []).forEach(node => {
    f(node);
    childAst = childAst.concat(getChildren(node));
  });
  if (childAst.length > 0) {
    walkNodesBreadthFirstHelper(childAst, f);
  }
}
1219944
def run_bfs(m, w, trace=False, steps=1000):
    """"""
    from .machines import Store, Configuration, Transition

    agenda = collections.deque()
    chart = {}

    # Initial configuration
    config = list(m.start_config)
    w = Store(w)
    config[m.input] = w
    config = Configuration(config)

    chart[config] = 0
    agenda.append(config)
    run = graphs.Graph()
    run.attrs['rankdir'] = 'LR'
    run.add_node(config, {'start': True})

    while len(agenda) > 0:
        tconfig = agenda.popleft()

        if trace: print("trigger: {}".format(tconfig))

        for aconfig in m.accept_configs:
            if aconfig.match(tconfig):
                run.add_node(tconfig, {'accept': True})

        if chart[tconfig] == steps:
            if trace: print("maximum number of steps reached")
            run.add_node(tconfig, {'incomplete': True})
            continue

        for rule in m.transitions:
            if trace: print("rule: {}".format(rule))
            if rule.match(tconfig):
                nconfig = rule.apply(tconfig)

                if nconfig in chart:
                    assert chart[nconfig] <= chart[tconfig]+1
                    if trace: print("merge: {}".format(nconfig))
                else:
                    chart[nconfig] = chart[tconfig]+1
                    if trace: print("add: {}".format(nconfig))
                    agenda.append(nconfig)
                run.add_edge(tconfig, nconfig)

    # If input tape is one-way, then rank all nodes by input position
    if m.oneway:
        for q in run.nodes:
            ql = list(q)
            run.nodes[q]['rank'] = ql.pop(m.input)
            run.nodes[q]['label'] = Configuration(ql)
        for i in range(len(w)+1):
            r = 'rank{}'.format(i)
            run.add_node(r, {'rank' : Store(w[i:]), 'style' : 'invisible'})
            if i > 0:
                run.add_edge(rprev, r, {'color': 'white', 'label' : w[i-1]})
            rprev = r

    return run
398726
private Set<Integer> getSuccessors(Graph g, Integer vertex) {
        if (g instanceof DirectedGraph) {
            DirectedGraph<?> dg = (DirectedGraph)g;
            return dg.successors(vertex);
        }
        else
            return Collections.<Integer>emptySet();
    }
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;
    }
713431
def astar(problem, graph_search=False, viewer=None):
    '''
    
    '''
    return _search(problem,
                   BoundedPriorityQueue(),
                   graph_search=graph_search,
                   node_factory=SearchNodeStarOrdered,
                   graph_replace_when_better=True,
                   viewer=viewer)