Program Listing for File ReachableNodes.hpp¶

#ifndef NETWORKIT_REACHABILITY_REACHABLE_NODES_HPP_
#define NETWORKIT_REACHABILITY_REACHABLE_NODES_HPP_

#include <vector>

#include <networkit/base/Algorithm.hpp>
#include <networkit/graph/Graph.hpp>

namespace NetworKit {

class ReachableNodes final : public Algorithm {
public:
    ReachableNodes(const Graph &G, bool exact = true);

    void run() override;

    count numberOfReachableNodes(node u) const {
        assureFinished();
        if (!exact)
            throw std::runtime_error("The number of nodes is not computed exactly, run the "
                                     "algorithm with exact = true.");
        return reachableLB[u];
    }

    count numberOfReachableNodesLB(node u) const { return reachableLB[u]; }

    count numberOfReachableNodesUB(node u) const {
        assureFinished();
        if (G->isDirected())
            return exact ? reachableLB[u] : reachableUB[u];
        else
            return reachableLB[u];
    }

    /*
     * Whether or not to compute the reachable nodes exactly.
     */
    bool exact;

private:
    const Graph *G;
    std::vector<count> reachableLB, reachableUB;

    void runDirected();
    void runUndirected();
};
} // namespace NetworKit

#endif // NETWORKIT_REACHABILITY_REACHABLE_NODES_HPP_