Graph.h

#pragma once

#include

#include

#include

#include

#ifndef COP$3530\_$PROJECT$\_3\_$GRAPH$\_$H

#define COP$3530\_$PROJECT$\_3\_$GRAPH$\_$H

using namespace std;

class AdjacencyList

$\{$

private:

$//$graph structure

unordered$\_$multimap$>>$ graph;

$//$store lat and long of nodes as pair

unordered$\_$multimap$>$ nodeLocations;

public:

void insertNode$($int nodeID, double latitude, double longitude$)$

$\{$

nodeLocations.insert$(\{$ nodeID, $\{$latitude$,$ longitude$\}\})$;

$\}$

void insertEdge$($int fromID, int toID, double weight$)$

$\{$

graph.insert$(\{$ fromID, $\{\{$toID$,$ weight$\}\}\})$;

$\}$

$//$code referenced from Lecture Slides $-$ Mod $8$a $-$ Graphs Terminology and Implementation $--$ slide $63$

vector bfs$($int startID, int endID$)$

$\{$

$//$create containers for bfs

set visited;

queue queue;

unordered$\_$map previous;

$//$insert and push startID into visited and queue

visited.insert$($startID$)$;

queue.push$($startID$)$;

$//$set node previous to start id as $-1$

previous$[$startID$]=-1$;

while $(!$queue.empty$())$

$\{$

int u $=$ queue.front$()$;

$//$checks if u is the same as the endID, add it to the path and keep adding the previous nodes until it reaches the previous$[$start$]$ which is $-1$

if $($u $==$ endID$)$

$\{$

vector pathTrace;

for $($int i $=$ endID; i $!=-1$; i $=$ previous$[$i$])$

$\{$

pathTrace.push$\_$back$($i$)$;

$\}$

$//$reverse order of path

reverse$($pathTrace$.$begin$(),$ pathTrace.end$())$;

return pathTrace;

$\}$

queue.pop$()$;

$//$check if element is in the visited set, if its not, add it to vector and queue

vector neighbours;

auto it $=$ graph.equal$\_$range$($u$)$;

for $($auto& i $=$ it$.$first; i $!=$ it$.$second; $++$i$)$

$\{$

for $($const auto& neighbour : i$->$second$)$

$\{$

int v $=$ neighbour.first;

if $($visited$.$count$($v$)==0)$

$\{$

visited.insert$($v$)$;

queue.push$($v$)$;

$\}$

$\}$

$\}$

$\}$

$//$no path found return empty

return $\{\}$;

$\}$

vector dijkstras$($int startID, int endID$)$;

unordered$\_$multimap$>>$& getAdjacencyList$()$

$\{$

return graph;

$\}$

unordered$\_$multimap$>$ getNodeLoc$()$

$\{$

return nodeLocations;

$\}$

$\}$;

#endif

$-----------------------------------------------$

Main.cpp

#include

#include "graph.h$"$

#include

#include

#include

#include

#include

#include

#define pi $3\mathrm{.}14159265358979323846$

$//$Earth Radius in Kilometers found online

const double EarthR $=6378\mathrm{.}0$;

$//$formula to calculate weights based on longitude and latitude

double Formula$($double Latitude$\_1,$ double Longitude$\_1,$ double Latitude$\_2,$ double Longitude$\_2)\{$

double Longitude $=($Latitude$\_2-$ Latitude$\_1)*$ pi $/180\mathrm{.}0$;

double Latitude $=($Longitude$\_2-$ Longitude$\_1)*$ pi $/180\mathrm{.}0$;

Latitude$\_1=$ Latitude$\_1*$ pi $/180\mathrm{.}0$;

Latitude$\_2=$ Latitude$\_2*$ pi $/180\mathrm{.}0$;

double Result $=$ sin$($Latitude $/2)*$ sin$($Latitude $/2)+$ cos$($Latitude$\_1)*$ cos$($Latitude$\_2)*$ sin$($Longitude $/2)*$ sin$($Longitude $/2)$;

double Result$\_1=2*$ atan$2($sqrt$($Result$),$ sqrt$(1-$ Result$))$;

double final $=$ EarthR $*$ Result$\_1$;

return final;

$\}$

class Drawer : public osmium::handler::Handler $\{$

public:

AdjacencyList& graph;

int Node$\_$Total $=0$;

const int Node$\_$Max $=100000$;

Drawer$($AdjacencyList& list$)$ : graph$($list$)\{\}$

$//$override node function

void node$($const osmium::Node& nodes$)\{$

if $($Node$\_$Total $<$ Node$\_$Max$)\{$

graph.insertNode$($nodes$.$id$(),$ nodes.location$().$lat$(),$ nodes.location$().$lon$())$;

Node$\_$Total$++$;

cout $<<$ "Node ID: $"<<$ nodes.id$()<<"\backslash$t$"<<$ Node$\_$Total $<<"\backslash$t$"$;

$\}$

$\}$

$//$override way function

void way$($const osmium::Way& Direct$)\{$

const auto& Direction$\_$of$\_$Node $=$ Direct.nodes$()$;

for $($size$\_$t x $=1$; x $<$ Direction$\_$of$\_$Node.size$()$; $++$x$)\{$

auto Node$\_1=$ Direction$\_$of$\_$Node$[$x $-1].$ref$()$;

auto Node$\_2=$ Direction$\_$of$\_$Node$[$x$].$ref$()$;

if $($graph$.$getNodeLoc$().$count$($Node$\_1)$ && graph.getNodeLoc$().$count$($Node$\_2))$

$\{$

auto it$1=$ graph.getNodeLoc$().$equal$\_$range$($Node$\_1)$;

auto it$2=$ graph.getNodeLoc$().$equal$\_$range$($Node$\_2)$;

for $($auto i $=$ it$1.$first; i $!=$ it$1.$second; i$++)$

$\{$

for $($auto j $=$ it$2.$first; j $!=$ it$2.$second; j$++)$

$\{$

double Latitude$\_1=$ i$->$second.first;

double Longitude$\_1=$ i$->$second.second; $\}\}\}\}\}$;

i am getting a derefrencing error at the end two lines in the main.cpp file for some reason. Everything else works