Algorithm for depth-first searching the vertices of a graph.
344967
def DFS(G):
    
    if not G.vertices:
        raise GraphInsertError("This graph have no vertices.")
    color = {}
    pred = {}
    reach = {}
    finish = {}

    def DFSvisit(G, current, time):
        color[current] = 'grey'
        time += 1
        reach[current] = time
        for vertex in G.vertices[current]:
            if color[vertex] == 'white':
                pred[vertex] = current
                time = DFSvisit(G, vertex, time)
        color[current] = 'black'
        time += 1
        finish[current] = time
        return time

    for vertex in G.vertices:
        color[vertex] = 'white'
        pred[vertex] = None
        reach[vertex] = 0
        finish[vertex] = 0
    time = 0
    for vertex in G.vertices:
        if color[vertex] == 'white':
            time = DFSvisit(G, vertex, time)
    # Dictionary for vertex data after DFS
    # -> vertex_data = {vertex: (predecessor, reach, finish), }
    vertex_data = {}
    for vertex in G.vertices:
        vertex_data[vertex] = (pred[vertex], reach[vertex], finish[vertex])
    return vertex_data
606464
def find_node_match(simple_vertices, complex_vertices):
    

    import scipy.spatial

    # make array for writing in final voronoi seed indices
    voronoi_seed_idx = np.zeros((simple_vertices.shape[0],), dtype='int64')-1
    missing = np.where(voronoi_seed_idx == -1)[0].shape[0]
    mapping_single = np.zeros_like(voronoi_seed_idx)

    neighbours = 0
    col = 0

    while missing != 0:

        neighbours += 100
        # find nearest neighbours
        inaccuracy, mapping = scipy.spatial.KDTree(
            complex_vertices).query(simple_vertices, k=neighbours)
        # go through columns of nearest neighbours until unique mapping is
        # achieved, if not before end of neighbours, extend number of
        # neighbours
        while col < neighbours:
            # find all missing voronoi seed indices
            missing_idx = np.where(voronoi_seed_idx == -1)[0]
            missing = missing_idx.shape[0]
            if missing == 0:
                break
            else:
                # for missing entries fill in next neighbour
                mapping_single[missing_idx] = np.copy(
                    mapping[missing_idx, col])
                # find unique values in mapping_single
                unique, double_idx = np.unique(
                    mapping_single, return_inverse=True)
                # empty voronoi seed index
                voronoi_seed_idx = np.zeros(
                    (simple_vertices.shape[0],), dtype='int64')-1
                # fill voronoi seed idx with unique values
                for u in range(unique.shape[0]):
                    # find the indices of this value in mapping
                    entries = np.where(double_idx == u)[0]
                    # set the first entry to the value
                    voronoi_seed_idx[entries[0]] = unique[u]
                # go to next column
                col += 1

    return voronoi_seed_idx, inaccuracy
246917
def find_cycle(graph):
    
    n = len(graph)
    prec = [None] * n  # ancestor marks for visited vertices
    for u in range(n):
        if prec[u] is None:  # unvisited vertex
            S = [u]  # start new DFS
            prec[u] = u  # mark root (not necessary for this algorithm)
            while S:
                u = S.pop()
                for v in graph[u]:  # for all neighbors
                    if v != prec[u]:  # except arcs to father in DFS tree
                        if prec[v] is not None:
                            cycle = [v, u]  # cycle found, (u,v) back edge
                            while u != prec[v] and u != prec[u]:  # directed
                                u = prec[u]  # climb up the tree
                                cycle.append(u)
                            return cycle
                        else:
                            prec[v] = u  # v is new vertex in tree
                            S.append(v)
    return None
795093
private List<Tree<K, V>> findDepth(List<Tree<K, V>> zipper, int depth) {
        if (zipper.isEmpty())
            throw new RuntimeException("Defect: unexpected empty zipper while computing range");

        if (isBlackTree(zipper.get(0))) {
            return depth <= 1 ? zipper : findDepth(zipper.subList(1, zipper.size()), depth - 1);
        } else {
            return findDepth(zipper.subList(1, zipper.size()), depth);
        }
    }
740039
def breadth_first(problem, graph_search=False, viewer=None):
    '''
    
    '''
    return _search(problem,
                   FifoList(),
                   graph_search=graph_search,
                   viewer=viewer)
180108
public void findAllCC() {
		if (nodeCC == null) {
			CCFirstNode = new int[n];
			CCNextNode = new int[n];
			nodeCC = new int[n];
			sizeCC = new int[n];
		}
		sizeMinCC = 0;
		sizeMaxCC = 0;
		ISet act = graph.getNodes();
		for (int i : act) {
			p[i] = -1;
		}
		for (int i = 0; i < CCFirstNode.length; i++) {
			CCFirstNode[i] = -1;
			sizeCC[i] = -1;
		}
		int cc = 0;
		for (int i : act) {
			if (p[i] == -1) {
				findCC(i, cc);
				if (sizeMinCC == 0 || sizeMinCC > sizeCC[cc]) {
					sizeMinCC = sizeCC[cc];
				}
				if (sizeMaxCC < sizeCC[cc]) {
					sizeMaxCC = sizeCC[cc];
				}
				cc++;
			}
		}
		nbCC = cc;
	}
994382
def depth_first_visit (u, vis = DFSVisitor.new(self), &b)
      vis.color_map[u] = :GRAY
      vis.handle_examine_vertex(u)
      each_adjacent(u) { |v|
        vis.handle_examine_edge(u, v)
        if vis.follow_edge?(u, v)            # (u,v) is a tree edge
          vis.handle_tree_edge(u, v)         # also discovers v
          vis.color_map[v] = :GRAY           # color of v was :WHITE
          depth_first_visit(v, vis, &b)
        else                                 # (u,v) is a non tree edge
          if vis.color_map[v] == :GRAY
            vis.handle_back_edge(u, v)       # (u,v) has gray target
          else
            vis.handle_forward_edge(u, v)    # (u,v) is a cross or forward edge 
          end
        end
      }
      vis.color_map[u] = :BLACK
      vis.handle_finish_vertex(u)           # finish vertex
      b.call(u)
    end
1009588
private void dfs(int v, int[] cc, int id) {
        cc[v] = id;
        for (int t = 0; t < n; t++) {
            if (graph[v][t] != 0.0) {
                if (cc[t] == -1) {
                    dfs(t, cc, id);
                }
            }
        }
    }
112302
function(){
      for( var i = 0; i < depths.length; i++ ){
        var eles = depths[i];

        for( var j = 0; j < eles.length; j++ ){
          var ele = eles[j];

          ele._private.scratch.BreadthFirstLayout = {
            depth: i,
            index: j
          };
        }
      }
    }
419146
private void topologicalSortVisit(V n, List<V> L, Set<V> visited, LinkedHashSet<V> sequence) throws CycleException, EX {
		//    if n has not been visited yet then
		//        mark n as visited
		if(visited.add(n)) {
			//        for each node m with an edge from n to m do
			for(Edge<V> e : (isForward ? graph.getEdgesFrom(n) : graph.getEdgesTo(n))) {
				V m = isForward ? e.getTo() : e.getFrom();
				//            visit(m)
				if(!sequence.add(m)) {
					List<V> vertices = new ArrayList<>();
					boolean found = false;
					for(V seq : sequence) {
						if(!found && seq.equals(m)) found = true;
						if(found) vertices.add(seq);
					}
					vertices.add(m);
					throw new CycleException(AoCollections.optimalUnmodifiableList(vertices));
				}
				topologicalSortVisit(m, L, visited, sequence);
				sequence.remove(m);
			}
			//        add n to L
			L.add(n);
		}
	}
242085
private Edge findDirectionalEdge(Graph g, int u) {
        List<Edge> edges = g.edges(u);
        if (edges.size() == 1)
            return null;
        Edge first = null;
        for (Edge e : edges) {
            Bond b = e.bond();
            if (b == Bond.UP || b == Bond.DOWN) {
                if (first == null)
                    first = e;
                else if (((first.either() == e.either()) == (first.bond() == b)))
                    return null;
            }
        }
        return first;
    }
1346323
def _depth_first_search(self, target_id, layer_id_list, node_list):
        """"""
        assert len(node_list) <= self.n_nodes
        u = node_list[-1]
        if u == target_id:
            return True

        for v, layer_id in self.adj_list[u]:
            layer_id_list.append(layer_id)
            node_list.append(v)
            if self._depth_first_search(target_id, layer_id_list, node_list):
                return True
            layer_id_list.pop()
            node_list.pop()

        return False
1078076
def connected_components(graph):
    
    recursionlimit = getrecursionlimit()
    setrecursionlimit(max(len(graph.nodes())*2,recursionlimit))
    
    visited = {}
    count = 1

    # For 'each' node not found to belong to a connected component, find its connected
    # component.
    for each in graph:
        if (each not in visited):
            _dfs(graph, visited, count, each)
            count = count + 1
    
    setrecursionlimit(recursionlimit)
    return visited
1095985
function( roots, fn, directed ){
      directed = arguments.length === 1 && !$$.is.fn(fn) ? fn : directed;
      fn = $$.is.fn(fn) ? fn : function(){};
      var cy = this._private.cy;
      var v = $$.is.string(roots) ? this.filter(roots) : roots;
      var S = [];
      var connectedNodes = [];
      var connectedBy = {};
      var id2depth = {};
      var discovered = {};
      var j = 0;
      var found;
      var edges = this.edges();
      var nodes = this.nodes();

      // push v
      for( var i = 0; i < v.length; i++ ){
        if( v[i].isNode() ){
          S.push( v[i] );

          connectedNodes.push( v[i] );
          id2depth[ v[i].id() ] = 0;
        }
      }

      while( S.length !== 0 ){
        var v = S.pop();

        if( !discovered[ v.id() ] ){
          discovered[ v.id() ] = true;

          var depth = id2depth[ v.id() ];

          var ret = fn.call(v, j++, depth);

          if( ret === true ){
            found = v;
            break;
          }

          if( ret === false ){
            break;
          }

          var vwEdges = v.connectedEdges(directed ? '[source = "' + v.id() + '"]' : undefined).intersect( edges );
          
          for( var i = 0; i < vwEdges.length; i++ ){
            var e = vwEdges[i];
            var w = e.connectedNodes('[id != "' + v.id() + '"]').intersect( nodes );

            if( w.length !== 0 && !discovered[ w.id() ] ){
              w = w[0];

              S.push( w );

              id2depth[ w.id() ] = id2depth[ v.id() ] + 1;

              connectedNodes.push( w );
              connectedBy[ w.id() ] = e;
            }
          }
        }
      }

      var connectedEles = [];

      for( var i = 0; i < connectedNodes.length; i++ ){
        var node = connectedNodes[i];
        var edge = connectedBy[ node.id() ];

        if( edge ){
          connectedEles.push( edge );
        }

        connectedEles.push( node );
      }

      return {
        path: new $$.Collection( cy, connectedEles ),
        found: new $$.Collection( cy, found )
      }
    }
620883
def _search(problem, fringe, graph_search=False, depth_limit=None,
            node_factory=SearchNode, graph_replace_when_better=False,
            viewer=None):
    '''
    
    '''
    if viewer:
        viewer.event('started')

    memory = set()
    initial_node = node_factory(state=problem.initial_state,
                                problem=problem)
    fringe.append(initial_node)

    while fringe:
        if viewer:
            viewer.event('new_iteration', fringe.sorted())

        node = fringe.pop()

        if problem.is_goal(node.state):
            if viewer:
                viewer.event('chosen_node', node, True)
                viewer.event('finished', fringe.sorted(), node, 'goal found')
            return node
        else:
            if viewer:
                viewer.event('chosen_node', node, False)

        memory.add(node.state)

        if depth_limit is None or node.depth < depth_limit:
            expanded = node.expand()
            if viewer:
                viewer.event('expanded', [node], [expanded])

            for n in expanded:
                if graph_search:
                    others = [x for x in fringe if x.state == n.state]
                    assert len(others) in (0, 1)
                    if n.state not in memory and len(others) == 0:
                        fringe.append(n)
                    elif graph_replace_when_better and len(others) > 0 and n < others[0]:
                        fringe.remove(others[0])
                        fringe.append(n)
                else:
                    fringe.append(n)

    if viewer:
        viewer.event('finished', fringe.sorted(), None, 'goal not found')
1336966
def find_articulation_vertices(graph):
    

    articulation_vertices = []

    all_nodes = graph.get_all_node_ids()
    if len(all_nodes) == 0:
        return articulation_vertices

    # Run the algorithm on each of the connected components of the graph
    components = get_connected_components_as_subgraphs(graph)
    for component in components:
        # --Call the internal articulation vertices function to find
        # --the node list for this particular connected component
        vertex_list = _internal_get_cut_vertex_list(component)
        articulation_vertices.extend(vertex_list)

    return articulation_vertices
1238212
def dom_lt(graph):
    """"""

    def _dfs(v, n):
        semi[v] = n = n + 1
        vertex[n] = label[v] = v
        ancestor[v] = 0
        for w in graph.all_sucs(v):
            if not semi[w]:
                parent[w] = v
                n = _dfs(w, n)
            pred[w].add(v)
        return n

    def _compress(v):
        u = ancestor[v]
        if ancestor[u]:
            _compress(u)
            if semi[label[u]] < semi[label[v]]:
                label[v] = label[u]
            ancestor[v] = ancestor[u]

    def _eval(v):
        if ancestor[v]:
            _compress(v)
            return label[v]
        return v

    def _link(v, w):
        ancestor[w] = v

    parent, ancestor, vertex = {}, {}, {}
    label, dom = {}, {}
    pred, bucket = defaultdict(set), defaultdict(set)

    # Step 1:
    semi = {v: 0 for v in graph.nodes}
    n = _dfs(graph.entry, 0)
    for i in range(n, 1, -1):
        w = vertex[i]
        # Step 2:
        for v in pred[w]:
            u = _eval(v)
            y = semi[w] = min(semi[w], semi[u])
        bucket[vertex[y]].add(w)
        pw = parent[w]
        _link(pw, w)
        # Step 3:
        bpw = bucket[pw]
        while bpw:
            v = bpw.pop()
            u = _eval(v)
            dom[v] = u if semi[u] < semi[v] else pw
    # Step 4:
    for i in range(2, n + 1):
        w = vertex[i]
        dw = dom[w]
        if dw != vertex[semi[w]]:
            dom[w] = dom[dw]
    dom[graph.entry] = None
    return dom