private void extendSubgraph(Set<Integer> subgraph, Set<Integer> extension, 
                                Integer v) {
        // If we found a set of vertices that match the required subgraph size,
        // create a snapshot of it from the original graph and 
        if (subgraph.size() == subgraphSize) {
            Graph<T> sub = g.copy(subgraph);
            nextSubgraphs.add(sub);
            return;
        }

        // Randomly decide whether this portion of the subgraph search space
        // will be explored.
        int depth = subgraph.size();
        double explorationProbability = traversalProbabilitiesAtDepth[depth];
        int numChildren = extension.size();
        BitSet childrenToExplore = null;        

        // Special case for when we plan to explore all the children.  This
        // frequently happens in shallow depths where pruning would remove too
        // many children to be effective
        if (explorationProbability == 1d) {
            childrenToExplore = new BitSet(numChildren);
            // Mark all the children as needing to be explored.
            childrenToExplore.set(0, numChildren);
        }
        // Special case for when the extension has no children to set, at which
        // the tree-based traversal can just stop early.
        else if (numChildren == 0) {
            childrenToExplore = new BitSet(numChildren);
        }
        else {
            // Decide how many children to explore
            int numChildrenToExplore = 
                   (Math.random() <= (numChildren * explorationProbability) - 
                    Math.floor((numChildren * explorationProbability)))
                ? (int)(Math.ceil(numChildren * explorationProbability))
                : (int)(Math.floor(numChildren * explorationProbability));

            // Generate a bit mask over the children saying which of them will be
            // expanded.  We do this to avoid creating another Set<Integer>, which
            // wastes more space, or to just iterate until the sample size has been
            // reached, which isn't necessarily random.
            childrenToExplore = Statistics.
                randomDistribution(numChildrenToExplore, numChildren);
        }

        int child = 0;
        Iterator<Integer> iter = extension.iterator();
        while (extension.size() > 0) {
            // Choose and remove an aribitrary vertex from the extension            
            Integer w = iter.next();
            iter.remove();
            
            // If this child was not in the list of children that will be
            // randomly explored, then skip further processing here.
            if (!childrenToExplore.get(child++))
                continue;

            // The next extension is formed from all edges to vertices whose
            // indices are greater than the currently selected vertex, w, and
            // that point to a vertex in the exclusive neighborhood of w.  The
            // exclusive neighborhood is defined relative to a set of vertices
            // N: all vertices that are adjacent to w but are not in N or the
            // neighbors of N.  In this case, N is the current subgraph's
            // vertices
            Set<Integer> nextExtension = new HashSet<Integer>(extension);
            next_vertex:
            for (Integer n : g.getNeighbors(w))
                // Perform the fast vertex value test and check for whether the
                // vertex is currently in the subgraph
                if (n > v && !subgraph.contains(n)) {
                    // Then perform the most expensive exclusive-neighborhood
                    // test that looks at the neighbors of the vertices in the
                    // current subgraph
                    for (int inCur : subgraph) {
                        // If we find n within the neighbors of a vertex in the
                        // current subgraph, then skip the remaining checks and
                        // examine another vertex adjacent to w.
                        if (g.getNeighbors(inCur).contains(n))
                            continue next_vertex;
                    }
                    // Otherwise, n is in the exclusive neighborhood of w, so
                    // add it to the future extension.
                    nextExtension.add(n);
                }
            Set<Integer> nextSubgraph = new HashSet<Integer>(subgraph);
            nextSubgraph.add(w);
            
            extendSubgraph(nextSubgraph, nextExtension, v);
        }
    }
private void extendSubgraph ( Set < Integer > subgraph , Set < Integer > extension , Integer v ) { if ( subgraph . size ( ) == subgraphSize ) { Graph < T > sub = g . copy ( subgraph ) ; nextSubgraphs . add ( sub ) ; return ; } int depth = subgraph . size ( ) ; double explorationProbability = traversalProbabilitiesAtDepth [ depth ] ; int numChildren = extension . size ( ) ; BitSet childrenToExplore = null ; if ( explorationProbability == 1d ) { childrenToExplore = new BitSet ( numChildren ) ; childrenToExplore . set ( 0 , numChildren ) ; } else if ( numChildren == 0 ) { childrenToExplore = new BitSet ( numChildren ) ; } else { int numChildrenToExplore = ( Math . random ( ) <= ( numChildren * explorationProbability ) - Math . floor ( ( numChildren * explorationProbability ) ) ) ? ( int ) ( Math . ceil ( numChildren * explorationProbability ) ) : ( int ) ( Math . floor ( numChildren * explorationProbability ) ) ; childrenToExplore = Statistics . randomDistribution ( numChildrenToExplore , numChildren ) ; } int child = 0 ; Iterator < Integer > iter = extension . iterator ( ) ; while ( extension . size ( ) > 0 ) { Integer w = iter . next ( ) ; iter . remove ( ) ; if ( ! childrenToExplore . get ( child ++ ) ) continue ; Set < Integer > nextExtension = new HashSet < Integer > ( extension ) ; next_vertex : for ( Integer n : g . getNeighbors ( w ) ) if ( n > v && ! subgraph . contains ( n ) ) { for ( int inCur : subgraph ) { if ( g . getNeighbors ( inCur ) . contains ( n ) ) continue next_vertex ; } nextExtension . add ( n ) ; } Set < Integer > nextSubgraph = new HashSet < Integer > ( subgraph ) ; nextSubgraph . add ( w ) ; extendSubgraph ( nextSubgraph , nextExtension , v ) ; } }
For the set of vertices in {@code subgraph}, and the next set of
reachable vertices in {@code extension}, creates the non-duplicated
subgraphs and adds them to {@code nextSubgraphs}.

@param subgraph the current set of vertices making up the subgraph
@param extension the set of vertices that may be added to {@code
subgraph} to expand the current subgraph
@param v the vertex from which the next expansion will take place