Method findPath

src/rnabloom/util/GraphUtils.java:1497–1579

(BloomFilterDeBruijnGraph graph, Kmer left, Kmer right, int bound, int lookahead, float minKmerCov)

    }
    
    public static ArrayDeque<Kmer> findPath(BloomFilterDeBruijnGraph graph, Kmer left, Kmer right, int bound, int lookahead, float minKmerCov) {
        if (!graph.isLowComplexity(left) && !graph.isLowComplexity(right)) {
            int k = graph.getK();
            int numHash = graph.getMaxNumHash();

            ArrayDeque<Kmer> rightExtension = new ArrayDeque<>();

            ArrayDeque<Kmer> neighbors = new ArrayDeque<>(4);
            for (int i=0; i<bound; ++i) {
                right.getPredecessors(k, numHash, graph, neighbors, minKmerCov);

                if (neighbors.size() == 1) {
                    Kmer kmer = neighbors.pop();

                    if (left.equals(kmer)) {
                        return rightExtension;
                    }

                    rightExtension.addFirst(kmer);
                }
                else {
                    break;
                }
            }

            if (!rightExtension.isEmpty()) {
                bound -= rightExtension.size();
                right = rightExtension.getFirst();
            }

            // data structure to store visited kmers at defined depth
            HashSet<Kmer> visitedBranchingKmers = new HashSet<>();

            int depth = 0;

            ArrayDeque<LinkedList<Kmer>> branchesStack = new ArrayDeque<>();
            branchesStack.add(getSuccessorsRanked(left, graph, lookahead));

            ArrayDeque<Kmer> extension = new ArrayDeque<>();
            HashSet<Kmer> extensionKmers = new HashSet<>();

            while (!branchesStack.isEmpty()) {
                LinkedList<Kmer> branches = branchesStack.getLast();

                if (branches.isEmpty()) {
                    extensionKmers.remove(extension.pollLast());
                    branchesStack.removeLast();
                    --depth;
                }
                else {
                    Kmer cursor = branches.pop();

                    if (cursor.equals(right)) {
                        if (!rightExtension.isEmpty()) {
                            extension.addAll(rightExtension);
                        }

                        return extension;