ExpandedDijkstra.h

// Copyright 2011 Robin Schirrmeister and Simon Skilevic
// Chair of Algorithms and Datastructures Uni Freiburg


#ifndef ROUTEPLANNING_EXPANDEDDIJKSTRA_H_
#define ROUTEPLANNING_EXPANDEDDIJKSTRA_H_

#include <queue>
#include "./Graph.h"
#include "./TransitNetworkExpanded.h"

using std::priority_queue;

class ExpandedDijkstra
{
public:
  ExpandedDijkstra(TransitNetworkExpanded* transitNetwork);
  virtual ~ExpandedDijkstra();
  // convenience function, just calls the function below
  double computeShortestPath(string startStop, Time time,
                             string endStop, bool buildPath);
  // computes shortest path inbetween the two stops starting at the given start
  // time, returns lenght of that path..
  double computeShortestPath(int startStopId, Time startTime, int endStopId,
                           bool reconstructPath);
  // the shortest path: last Edge is a dummy edge...
  vector<pair<NodeExpanded, Edge> > transitShortestPath;
private:
  void reconstructShortestPath(const unordered_set<int>& startIds, int endId);
  TransitNetworkExpanded* _transitGraph;
  vector<int> _timesFromStart;
  priority_queue <pair<int, int>,
                    std::vector<pair<int, int> >,
                    std::greater<pair<int, int > > > _openNodeQueue;

  // stores which nodeid (index of vector)
  // was expanded from which node id (first part of pair)
  // with which edge (second part of pair)
  vector<pair<int, int> > _expandedFrom;
  vector<bool> _expanded;
};

#endif  // ROUTEPLANNING_EXPANDEDDIJKSTRA_H_