All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
IncompleteDijkstra.h
Go to the documentation of this file.
1 /*
2  * IncompleteDijkstra.h
3  *
4  * Created on: 15.07.2014
5  * Author: dhoske
6  */
7 
8 #ifndef INCOMPLETEDIJKSTRA_H_
9 #define INCOMPLETEDIJKSTRA_H_
10 
11 #include <unordered_map>
12 #include <unordered_set>
13 #include <vector>
14 #include <utility>
15 
16 #include "../graph/Graph.h"
17 #include "IncompleteSSSP.h"
18 #include "../auxiliary/PrioQueue.h"
19 
20 namespace NetworKit {
21 
28 public:
47  IncompleteDijkstra(const Graph* G, const std::vector<node>& sources,
48  const std::unordered_set<node>* explored = nullptr);
49 
50  virtual bool hasNext() override;
51  virtual std::pair<node, edgeweight> next() override;
52 
53 private:
54  // discard duplicate elements in pq
55  void discardDuplicates();
56 
57  // Stored reference to outside data structures
58  const Graph* G;
59  const std::unordered_set<node>* explored;
60 
61  // distances aren't stored in a vector because initialising it may be too expensive
62  std::unordered_map<node, edgeweight> dists;
63  // TODO: Fix Aux::PrioQueue to work with arbitrary values.
64  // and use it instead.
65  using PrioValue = std::pair<edgeweight, node>;
66  using Prio = std::priority_queue<PrioValue, std::vector<PrioValue>, std::greater<PrioValue>>;
67  Prio pq;
68 };
69 
70 }
71 
72 #endif
Abstract base class for single-source shortest path algorithms that return the nodes in order of incr...
Definition: IncompleteSSSP.h:21
IncompleteDijkstra(const Graph *G, const std::vector< node > &sources, const std::unordered_set< node > *explored=nullptr)
Creates a IncompleteDijkstra instance from the sources in sources (act like a super source) in the gr...
Definition: IncompleteDijkstra.cpp:23
Implementation of IncompleteSSSP using a normal Dijkstra with binary heaps.
Definition: IncompleteDijkstra.h:27
virtual bool hasNext() override
Returns whether there is a next-nearest node or all of the nodes reachable from the source have alrea...
Definition: IncompleteDijkstra.cpp:38
virtual std::pair< node, edgeweight > next() override
Returns the next-nearest node from the source and its distance to the source.
Definition: IncompleteDijkstra.cpp:43
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79