Graph.h

/* Copyright Robin Schirrmeister and Simon Skilevic
 * Lecture Efficient Route Planning Summer Semester 2011
 * Uni Freiburg
 */

#ifndef ROUTEPLANNINGV2_GRAPH_H_
#define ROUTEPLANNINGV2_GRAPH_H_
#include <stdio.h>
#include <assert.h>
#include <string>
#include <vector>
#include <map>
#include "./NodeExpanded.h"
#include "./Edge.h"
using std::vector;
using std::string;
using std::map;

class Graph
{
 public:
  Graph();
  Graph(const Graph& orig);
  virtual ~Graph();
  // add node to roadnetwork
  void addNode(NodeExpanded node);
  void addDummyNode(NodeExpanded node);
  void removeDummyNode();
  // add edge to road network with specified start and end id and time
  void addEdge(int startId, int endId, int time);

  // get pointer to node with given id
  NodeExpanded* getNode(int id) const;
  // get incoming edges for specified id
  vector<Edge>* getInEdges(int nodeId) const;
    // get outgoing edges for specified Id
  vector<Edge>* getOutEdges(int nodeId) const;

  // get total number of nodes in this graph
  size_t getNumNodes() const;

  // find id of the node closes to given coordinates
  int findIdOfClosestNode(double latitude, double longitude);
  // get a random node that has both in and out edges
  NodeExpanded* getRandomNodeWithNeighbours();
  // reduce to graph to its biggest connected component
  void reduceToBiggestComponent();


 protected:
  void findBiggestConnectedSubgraph(vector<size_t>* biggestConnectedSubGraph);
  vector<NodeExpanded>* _nodes;
  vector<vector<Edge> >* _outgoingEdges;
  vector<vector<Edge> >* _incomingEdges;
};

#endif  // ROUTEPLANNINGV2_GRAPH_H_