Program Listing for File IncompleteDijkstra.hpp¶

/*
 * IncompleteDijkstra.hpp
 *
 *  Created on: 15.07.2014
 *      Author: dhoske
 */

#ifndef NETWORKIT_DISTANCE_INCOMPLETE_DIJKSTRA_HPP_
#define NETWORKIT_DISTANCE_INCOMPLETE_DIJKSTRA_HPP_

#include <unordered_set>
#include <vector>

#include <tlx/container/d_ary_addressable_int_heap.hpp>

#include <networkit/auxiliary/PrioQueue.hpp>
#include <networkit/auxiliary/VectorComparator.hpp>
#include <networkit/distance/IncompleteSSSP.hpp>
#include <networkit/graph/Graph.hpp>

namespace NetworKit {

class IncompleteDijkstra : public IncompleteSSSP {
public:
    IncompleteDijkstra(const Graph *G, const std::vector<node> &sources,
                       const std::unordered_set<node> *explored = nullptr);

    bool hasNext() override;
    std::pair<node, edgeweight> next() override;

private:
    // Stored reference to outside data structures
    const Graph *G;
    const std::unordered_set<node> *explored;

    std::vector<edgeweight> dists;

    tlx::d_ary_addressable_int_heap<node, 2, Aux::LessInVector<edgeweight>> heap;
};

} // namespace NetworKit

#endif // NETWORKIT_DISTANCE_INCOMPLETE_DIJKSTRA_HPP_