Program Listing for File BidirectionalBFS.hpp¶

/*
 * BidirectionalBFS.hpp
 *
 *  Created on: 14.06.2019
 *      Author: Eugenio Angriman <angrimae@hu-berlin.de>
 */

#ifndef NETWORKIT_DISTANCE_BIDIRECTIONAL_BFS_HPP_
#define NETWORKIT_DISTANCE_BIDIRECTIONAL_BFS_HPP_

#include <queue>

#include <networkit/auxiliary/Log.hpp>
#include <networkit/distance/STSP.hpp>

namespace NetworKit {

/*
 * @ingroup distance
 * Implements a bidirectional breadth-first search on a graph from two given source and target
 * nodes. Explores the graph from both the source and target nodes until the two explorations meet.
 */
class BidirectionalBFS final : public STSP {

public:
    BidirectionalBFS(const Graph &G, node source, node target, bool storePred = true)
        : STSP(G, source, target, storePred) {}

    /*
     * Perform a bidirectional BFS from the given source and target nodes.
     */
    void run() override;

private:
    std::vector<uint8_t> visited;
    uint8_t ts = 0;
    static constexpr uint8_t ballMask = uint8_t(1) << 7;
    std::queue<node> sQueue, sQueueNext, tQueue, tQueueNext;
};
} // namespace NetworKit

#endif // NETWORKIT_DISTANCE_BIDIRECTIONAL_BFS_HPP_