Given a graph, nodes to explore and an optinal root, do a breadth-first
    search in order to return the tree.
354547
def qbe_tree(graph, nodes, root=None):
    
    if root:
        start = root
    else:
        index = random.randint(0, len(nodes) - 1)
        start = nodes[index]
    # A queue to BFS instead DFS
    to_visit = deque()
    cnodes = copy(nodes)
    visited = set()
    # Format is (parent, parent_edge, neighbor, neighbor_field)
    to_visit.append((None, None, start, None))
    tree = {}
    while len(to_visit) != 0 and nodes:
        parent, parent_edge, v, v_edge = to_visit.pop()
        # Prune
        if v in nodes:
            nodes.remove(v)
        node = graph[v]
        if v not in visited and len(node) > 1:
            visited.add(v)
            # Preorder process
            if all((parent, parent_edge, v, v_edge)):
                if parent not in tree:
                    tree[parent] = []
                if (parent_edge, v, v_edge) not in tree[parent]:
                    tree[parent].append((parent_edge, v, v_edge))
                if v not in tree:
                    tree[v] = []
                if (v_edge, parent, parent_edge) not in tree[v]:
                    tree[v].append((v_edge, parent, parent_edge))
            # Iteration
            for node_edge, neighbor, neighbor_edge in node:
                value = (v, node_edge, neighbor, neighbor_edge)
                to_visit.append(value)
    remove_leafs(tree, cnodes)
    return tree, (len(nodes) == 0)
976778
private RedBlackTreeNode<Key, Value> min(RedBlackTreeNode<Key, Value> x) {
	// assert x != null;
	if (x.getLeft() == null)
	    return x;
	else
	    return min(x.getLeft());
    }
768061
function forwardSearch() {
      cameFrom = open1Set.pop();
      if (cameFrom.closed) {
        return;
      }

      cameFrom.closed = true;

      if (cameFrom.f1 < lMin && (cameFrom.g1 + f2 - heuristic(from, cameFrom.node)) < lMin) {
        graph.forEachLinkedNode(cameFrom.node.id, forwardVisitor);
      }

      if (open1Set.length > 0) {
        // this will be used in reverse search
        f1 = open1Set.peek().f1;
      } 
    }
289714
public static <N, E, D> boolean traverse(TraversalOrder order,
                                             IndefiniteGraph<N, E> graph,
                                             int limit,
                                             N initialNode,
                                             GraphTraversalVisitor<N, E, D> vis) {
        return traverse(order, graph, limit, Collections.singleton(initialNode), vis);
    }
115968
def _build_first_tree(self):
        """"""
        # Prim's algorithm
        neg_tau = -1.0 * abs(self.tau_matrix)
        X = {0}

        while len(X) != self.n_nodes:
            adj_set = set()
            for x in X:
                for k in range(self.n_nodes):
                    if k not in X and k != x:
                        adj_set.add((x, k))

            # find edge with maximum
            edge = sorted(adj_set, key=lambda e: neg_tau[e[0]][e[1]])[0]
            name, theta = Bivariate.select_copula(self.u_matrix[:, (edge[0], edge[1])])

            left, right = sorted([edge[0], edge[1]])
            new_edge = Edge(len(X) - 1, left, right, name, theta)
            new_edge.tau = self.tau_matrix[edge[0], edge[1]]
            self.edges.append(new_edge)
            X.add(edge[1])
225740
def dfs_tree(graph, start=0):
    
    to_visit = [start]
    prec = [None] * len(graph)
    while to_visit:              # an empty queue equals False
        node = to_visit.pop()
        for neighbor in graph[node]:
            if prec[neighbor] is None:
                prec[neighbor] = node
                to_visit.append(neighbor)
    return prec
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;
    }
  }
}
58338
def iter_breadth_first(self, root=None):
        
        if root == None:
            root = self
        yield root
        last = root 
        for node in self.iter_breadth_first(root):
            if isinstance(node, DictCell):
                # recurse
                for subpart in node:
                    yield subpart
                    last = subpart
            if last == node:
                return
877297
public static <V, E extends DirectedEdge<V>> void traverse(Graph<V, E> graph, DFSVisitor<V, E> visitor) {
        MultiSourceDFS.traverse(graph, graph.getVertices(), visitor);
    }
450684
def depth_first_spanning_tree(start_node)
      raise ArgumentError unless vertices.include?(start_node)
      tree = DirectedAdjacencyGraph.new
      visited = Set.new
      build_dfst(tree, start_node, visited)
      tree
    end
355768
private void postTraversalProcessing() {
		int nc1 = treeSize;
		info[KR] = new int[leafCount];
		info[RKR] = new int[leafCount];

		int lc = leafCount;
		int i = 0;

		// compute left-most leaf descendants
		// go along the left-most path, remember each node and assign to it the path's
		// leaf
		// compute right-most leaf descendants (in reversed postorder)
		for (i = 0; i < treeSize; i++) {
			if (paths[LEFT][i] == -1) {
				info[POST2_LLD][i] = i;
			} else {
				info[POST2_LLD][i] = info[POST2_LLD][paths[LEFT][i]];
			}
			if (paths[RIGHT][i] == -1) {
				info[RPOST2_RLD][treeSize - 1 - info[POST2_PRE][i]] =
						(treeSize - 1 - info[POST2_PRE][i]);
			} else {
				info[RPOST2_RLD][treeSize - 1 - info[POST2_PRE][i]] =
						info[RPOST2_RLD][treeSize - 1
								- info[POST2_PRE][paths[RIGHT][i]]];
			}
		}

		// compute key root nodes
		// compute reversed key root nodes (in revrsed postorder)
		boolean[] visited = new boolean[nc1];
		boolean[] visitedR = new boolean[nc1];
		Arrays.fill(visited, false);
		int k = lc - 1;
		int kR = lc - 1;
		for (i = nc1 - 1; i >= 0; i--) {
			if (!visited[info[POST2_LLD][i]]) {
				info[KR][k] = i;
				visited[info[POST2_LLD][i]] = true;
				k--;
			}
			if (!visitedR[info[RPOST2_RLD][i]]) {
				info[RKR][kR] = i;
				visitedR[info[RPOST2_RLD][i]] = true;
				kR--;
			}
		}

		// compute minimal key roots for every subtree
		// compute minimal reversed key roots for every subtree (in reversed postorder)
		int parent = -1;
		int parentR = -1;
		for (i = 0; i < leafCount; i++) {
			parent = info[KR][i];
			while (parent > -1 && info[POST2_MIN_KR][parent] == -1) {
				info[POST2_MIN_KR][parent] = i;
				parent = info[POST2_PARENT][parent];
			}
			parentR = info[RKR][i];
			while (parentR > -1 && info[RPOST2_MIN_RKR][parentR] == -1) {
				info[RPOST2_MIN_RKR][parentR] = i;
				parentR =
						info[POST2_PARENT][info[RPOST2_POST][parentR]]; // get parent's postorder
				if (parentR > -1) {
					parentR = treeSize - 1 - info[POST2_PRE][parentR]; // if parent exists get its
					// rev. postorder
				}
			}
		}
	}
1315246
def reroot_graph(G: nx.DiGraph, node: str) -> nx.DiGraph:
    """"""
    G = G.copy()
    for n, successors in list(nx.bfs_successors(G, source=node)):
        for s in successors:
            G.add_edge(s, n, **G.edges[n, s])
            G.remove_edge(n, s)
    return G
661208
function glb(tree, node, key, comp, low) {
    if (node === tree.z) {
        return low;
    }
    else if (comp(key, node.key) >= 0) {
        // The node key is a valid lower bound, but may not be the greatest.
        // Take the right link in search of larger keys.
        return maxNode(node, glb(tree, node.r, key, comp, low), comp);
    }
    else {
        // Take the left link in search of smaller keys.
        return glb(tree, node.l, key, comp, low);
    }
}
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
341352
public void depthFirstSearch(Context context, SearchResultVisitor visitor, Resource root) {
        ArrayDeque<SearchResults.Result> stack = Queues.newArrayDeque();

        // Build an instance of a SearchResult for the root resource
        // but don't invoke the visitor with it
        boolean skipFirstVisit = true;
        SearchResults initialResults = new SearchResults();
        initialResults.addResult(root, new ArrayList<String>(0));
        stack.add(initialResults.iterator().next());

        while (!stack.isEmpty()) {
            SearchResults.Result r = stack.pop();
            if (skipFirstVisit) {
                skipFirstVisit = false;
            } else {
                if (!visitor.visit(r)) {
                    return;
                }
            }

            // Reverse the order of the results so we walk the left-most
            // branches first
            ImmutableList<SearchResults.Result> results = ImmutableList.copyOf(m_searcher.search(
                    context, matchKeyAndValue(Constants.PARENT_TERM_FIELD, r.getResource().getId())));
            for (SearchResults.Result result : results.reverse()) {
                stack.push(result);
            }
        }
    }
23168
private SearchNode getSearchNode()
    {
        Object x = _searchNode.get();
        SearchNode g = null;
        if (x != null)
        {
            g = (SearchNode) x;
            g.reset();
        }
        else
        {
            g = new SearchNode();
            x = (Object) g;
            _searchNode.set(x);
        }
        return g;
    }
1034171
def a_star_search(graph, start, goal):
    
    all_nodes = graph.get_all_node_ids()
    if start not in all_nodes:
        raise NonexistentNodeError(start)
    if goal not in all_nodes:
        raise NonexistentNodeError(goal)

    came_from, cost_so_far, goal_reached = _a_star_search_internal(graph, start, goal)
    if goal_reached:
        path = reconstruct_path(came_from, start, goal)
        path.reverse()
        return path
    else:
        return []