Assignment — Trivial Navigation System

CMPUT 275 — Tangible Computing 
Assignment — Trivial Navigation System
Note: This is the assignment specification for individuals.
Groups of 2 should find their assignment specification on eClass.
Trivial Navigation System
You will be implementing a navigation system (like Google Maps) that allows the user to scroll around
on a map, e.g., the map of Edmonton, to select start and end points of a trip. The trip information, which
includes coordinates of these points, is sent to a central route finding server. This server computes the
shortest path between the selected two points (or nearest points to them in the road network), and returns
to the client the route information, which is coordinates of the waypoints along the shortest path. The
client displays the route as line segments overlaid on the original map by passing the waypoints to a
plotting application that also runs on the client side. Figure 1 is a schematic overview of this system.
The navigation system can be viewed as a client/server application where a client and a server, which
may run on the same machine or different machines, communicate with each other using a pair of sockets
to solve a complex problem that cannot be easily solved by the client alone. In this assignment, two
independent programs run on the client side:
• A plotter program that displays the map and allows the user to use the mouse or keyboard to
zoom and scroll around on a map of Edmonton to select the start and end points of a trip.
• A C++ program that obtains this data from the plotter and communicates with the route finding
server using sockets. Specifically, it sends the trip information to the server and consequently
receives the route information. It then passes the route information over to the plotter application
so that the route can be drawn on the map.
The server is a single C++ program that runs the graph search algorithm on a road network (i.e., a directed
graph) upon receiving the trip information from the client. It then sends the waypoints along the route,
which are nodes on the shortest path, from the trip’s start point to its end point (i.e., the path information)
to the client. The user can then repeatedly query new points via the client to receive new routes. The
client and server will both run on the same machine, that is your VM in this assignment.
We will provide a text file containing information about the Edmonton road network. You will use the
the weighted directed graph class and Dijkstra’s algorithm discussed in class for efficient route finding.
The assignment must be submitted in two parts. The first part is due 11:55pm Monday, March 29.
The second part is due 11:55pm Friday, April 9. In Part I, you are responsible for implementing the
following functions in the server program (more details on each task will follow):
1. A function for parsing the text file describing the road network. This function builds the weighted
directed graph and stores coordinates (i.e., latitude and longitude) of every vertex.
2. A function for computing the Manhattan distance between every two vertices of this graph. This
function is called by the function that builds the graph to compute the weight of an edge before it
is added to the graph.
1
3. A function that efficiently computes least cost (or shortest) paths starting from a given vertex. This
function is expected to run Dijkstra’s algorithm using an instance of the binary heap class.
Instead of communicating with the client, which will be done in Part II, in this part your server uses
stdin and stdout to receive and respond to a route finding request. Hence, the plotter will not be
used in this part to visualize the routes.
In Part II, you are responsible for
1. Adding a function to the server program (written in Part I) that accepts a route finding request from
the client, serves this request by computing the shortest path using the functions implemented in
Part I, and sends the route information back to the client.
2. Adding a function to the client program, which is provided as part of the starter coded for Part II.
This function must send the trip information obtained from the plotter application to the server and
receive the route information from the server. The route information will be used by the plotter
that we will also provide as part of the starter to display the route.
The client and server adopt a specific communication protocol which will be discussed later.
Part I: Server
You will implement a standalone C++ program that emulates the route finding server. It reads the trip
information from stdin and prints the route information to stdout.
Graph Building
Upon starting up, your server will need to load the Edmonton map data into a WDigraph object, and
store the ancillary information about vertex locations in an appropriate data structure. You will be given
the definition of the WDigraph class in wdigraph.h; it is derived from the Digraph class.
The road network data is stored in CSV format in a file. An excerpt of the file looks as follows:
V,29577354,53.430996,-113.491331
V,1503281720,53.434340,-113.490152
V,36396914,53.429491,-113.491863
E,36396914,29577354,Queen Elizabeth II Highway
E,29577354,1503281720,Queen Elizabeth II Highway
There are two types of lines: those starting with V (standing for “vertex”) and those starting with E
(standing for “edge”). In a line that starts with V you will find a unique vertex identifier followed by two
coordinates, giving the latitude and longitude of the vertex (in degrees). In a line that starts with E you
will find the identifiers of the two vertices connected by the edge, followed by the street name along the
edge. We guarantee that no street name has a comma and no two vertex lines have the same identifier.
The endpoints of an edge will be specified on previous lines before the line that describes the edge.
Your code must satisfy the following requirements:
1. You must use the identifiers read from the file and converted to integers as the vertex identifiers in
the graph.
2
2. You must store the coordinates in 100,000-ths of a degree using an integer data type (long long)
because the float type does not have enough significant digits. The client side will use this convention too. If you read a coordinate, such as 53.430996, into a double variable coord, you must
convert it to a long long variable by using static cast < long long (coord ∗ 100000). In this
example you would get 5343099. The latitude and longitude will then be stored in the following
data structure, called Point:
struct Point {
long long lat; // latitude of the point
long long lon; // longitude of the point
};
You will need to implement the following function:
void readGraph(string filename, WDigraph& graph, unordered_map<int, Point& points) {
/*
Read the Edmonton map data from the provided file
and load it into the given WDigraph object.
Store vertex coordinates in Point struct and map
each vertex to its corresponding Point struct.
PARAMETERS:
filename: name of the file describing a road network
graph: an instance of the weighted directed graph (WDigraph) class
points: a mapping between vertex identifiers and their coordinates
*/
}
The server calls this function with filename being "edmonton-roads-2.0.1.txt". Note we are
not using the street names in this assignment; thus, they can be ignored. The readGraph function is
essentially the same as the function you wrote for Weekly Exercise 5 with three main differences: (a) you
will instantiate an object from WDigraph class enabling you to store and later retrieve the cost associated
with each edge, (b) you will store vertex coordinates in a hash table so that you can display the least cost
path on the map in the second part of this assignment, (c) it should be the directed graph so do not add
both directions of each edge to make it undirected (unless both directions exist in the file already).
Cost Function
You will also need to write a function that computes the cost of an edge read from the road network
file. The function will take two variables of type Point and return the Manhattan distance between these
points, i.e., the sum of the horizontal and vertical distances between them. The Manhattan distance
between two points (x1, y1) and (x2, y2) is defined as
|x1 − x2| + |y1 − y2|
where |z| represents the absolute value of z.
Your task is to implement a function with the following declaration:
long long manhattan(const Point& pt1, const Point& pt2) {
// Return the Manhattan distance between the two given points
}
3
Dijkstra’s Algorithm
Your task is to write a function to find the search tree of least-cost paths from a given node. The function
has the following declaration.
void dijkstra(const WDigraph& graph, int startVertex, unordered_map<int, PIL& tree) {
/*
Compute least cost paths that start from a given vertex
Use a binary heap to efficiently retrieve an unexplored
vertex that has the minimum distance from the start vertex
at every iteration
PIL is an alias for "pair<int, long long" type as discussed in class
PARAMETERS:
WDigraph: an instance of the weighted directed graph (WDigraph) class
startVertex: a vertex in this graph which serves as the root of the search tree
tree: a search tree used to construct the least cost path to some vertex
*/
}
The declaration of this function is provided in dijkstra.h.
The running time of dijstrak() should be O(m log m) where m is the number of edges in the graph
represented by graph (under the usual assumption that lookups and updates with unordered_set
take constant time).
Heaps
In class, you will see how to design a binary heap but a full C++ implementation will not be provided.
Groups of 2 must complete the implementation of the binary hearp. For individuals, you may use the
built-in heaps in C++.
They are called priority queues:
https://www.cplusplus.com/reference/queue/priority_queue/
Note, by default in C++ a priority queue is built on a max heap meaning the item that is greatest with
respect to the < operator will be found at the top of the heap (e.g., via the top() method) and this is the
item that will be removed when you call the pop() method. To make the C++ priority queues act like a
min heap (as required by Dijkstra’s algorithm), you can declare a priority queue for a type T (that can be
compared via a relational operator) as follows:
priority_queue< T, std::vector<T, std::greater<T
Any priority queue of this type will have the minimum item appearing at the top.
Putting it all together
After loading the Edmonton map data, your server needs to provide routes based on requests from clients.
For Part I, your server will be receiving and processing requests by reading from and writing to stdin
and stdout, respectively. For Part II, your server will be communicating with the client that runs the
plotter. In both cases we will use the same protocol described below, the only difference is that the server
4
will be reading from and writing to a socket in Part II (how to do this will be described in class). Thus,
while the description below talks about the server communicating with the client, for Part I the client
will not be there and the server will be reading from and printing to stdin and stdout.
All requests will be made by simply providing a latitude and longitude (in 100,000-ths of degrees) of the
start and end points in ASCII, separated by single spaces. The line should start with the character R. For
example,
R 5365486 -11333915 5364728 -11335891
is a valid request sent to the server. The server will serve the request by first finding the closest vertices in
the Edmonton’s road network to the start and end points according to the Manhattan distance (breaking
ties arbitrarily), next computing a shortest path along Edmonton streets between the two vertices found,
and finally communicating the found waypoints from the first vertex to the last back to the client.
The communication of the waypoints to the client is done by a series of messages sent using stream
sockets. Each message consists of the latitude and longitude of a waypoint along the path. However,
before communicating the first waypoint, the server tells the client the number of waypoints it is going
to send. After each print, the client must acknowledge the receipt of data (preventing unwanted buffer
overflows) by responding with the character A. As an example, assume that the number of waypoints is
8. Then, the server starts with
N 8
and the client responds with
A
Next, the server sends the coordinates of the first waypoint (corresponding to the location of the first
vertex):
W 5365488 -11333914
The client responds again with
A
Upon receiving this acknowledgement, the server sends the next waypoint, which the client acknowledges again. This continues until there are no more waypoints; the server sends the character ‘E’:
E
This ends the session between the client and the server.
• Part I: At this point your program should end. It will process only one request.
• Part II: The server’s next state is to wait for the next request from the client, and the client will
show the route and allow the user to select new start and end points.
If we print the data sent by the server in black and the data sent by the client in blue, the above exchange
of messages can be displayed as follows:
R 5365486 -11333915 5364728 -11335891
N 8
A
5
W 5365488 -11333914
A
W 5365238 -11334423
A
W 5365157 -11334634
A
W 5365035 -11335026
A
W 5364789 -11335776
A
W 5364774 -11335815
A
W 5364756 -11335849
A
W 5364727 -11335890
A
E
The number of spaces between the letters and numbers in all cases is one.
When there is no path from the start to the end vertex nearest to the start and end points sent to the server,
the server should return an empty path to the client by sending the “no path” message, that is:
N 0
Upon receiving this message the client should let the user select a new pair of start and end points (in
Part II). The client does not need to acknowledge (by sending A) the receipt of the “no path” message.
Accordingly, upon sending the “no path” message, the server should consider the answer to the client’s
request complete and move to the wait state again.
Part I Submission
You should submit all source files compressed as part1.tar.gz or part1.zip. Your submission
must include the following files.
• server.cpp: the server program. Its main function should call readGraph and dijkstra
functions described earlier in addition to input processing and output formatting.
• dijkstra.cpp: implementation of Dijkstra’s algorithm using a heap.
• All source code files related to the graph and weighted graph class.
• dijkstra.h: header file for Dijkstra’s algorithm
• a custom Makefile with at least these targets: (a) the main target server which simply links
all object files, (b) the target dijkstra.o which compiles the object, (c) the target server.o
which compiles the object, (d) the target digraph.o which compiles the object, and (e) the target
clean which removes the executable and objects.
• your README, following the Code Submission Guidelines
6
If you want to add more files to the project, then create appropriate Makefile targets and clearly
indicate in the README the purpose of these new files.
You can test your entire server program using the files provided with this assignment on eClass. These
test files are in the tests.tar.gz file. For example:
make server
./server < test00-input.txt mysol.txt
This will load the graph of Edmonton from "edmonton-roads-2.0.1.txt", read a request from
test00-output.txt instead of the keyboard, and print the output to mysol.txt instead of the
terminal. You can examine the output by looking at mysol.txt. You can quickly determine if the
output agrees with with the provided expected output test00-output.txt by running
diff mysol.txt test00-output.txt
Please Note: There is not always a unique minimum-cost path between two locations (eg. between
opposite corners of a perfectly-rectangular block). So the output might not agree with the provided
output. But you can check if the total driving length of your output agrees with the driving length of
the provided output. Also, feel free to discuss these tests and other examples on the eClass discussion
forums.
Note that we will also test your implementation of Dijkstra’s algorithm separately.
Part II: Client/Server Application
In this part you will implement the communication protocol between client and server. A video demonstrating the expected behaviour of both programs will be uploaded before the deadline of Part I.
Plotter
We provide you an executable, named plotter, that loads the map of Edmonton and makes it possible
for the user to scroll around, zoom in/out, and select start and end points using the mouse and keyboard.
In particular, the user can:
• press W/S/A/D to move up/down/left/right the patch that is displayed in the window, respectively;
• press R to remove all routes and selected points on the map;
• press Q and E to respectively zoom in and out on the map, keeping the mouse cursor at its previous
position;
• click left mouse button to select current point as the start or end point of a trip;
• drag left mouse button to scroll around on the map.
When the user selects both start and end points of a trip, the plotter writes their coordinates to a named
pipe, called inpipe, as shown below:
53.530870 -113.532972
53.530870 -113.514991
7
The client can then read the coordinates from this pipe and send them to the route finding server. Similarly, when the client receives the waypoints along the shortest path from the route finding server, it writes
them to another pipe, called outpipe, so that the plotter can read the coordinates of each waypoint and
display the route by drawing a line between every two waypoints:
53.53087 -113.53297
53.51620 -113.53297
53.51620 -113.51499
53.53087 -113.51499
E
The character E in the last line signals the plotter that there is no more waypoint coordinates to read
from the pipe for this route. Note, no trailing spaces are allowed at the end of each line, and there is a
single space character between the latitude and longitude of every waypoint. Each line must end with
the newline character (\n). So make sure you do not print a null character at the end of each line.
The function create_and_open_fifo() in the starter code creates the two named pipes, inpipe
and outpipe, and opens them for read and write operations respectively. You will use read and
write functions with these pipes (blocking operations) in the client to transfer data between the client
and plotter.
As explained in Part 1, the server reads/writes coordinates in 100,000-ths of degrees, whereas the plotter
reads/writes them in degrees. Thus, the client is responsible for making the conversion before performing
I/O operations on pipes and sockets. Note that in this conversion, the last digit will get chopped off. You
do not need to worry about it because the coordinates are accurate enough even if the last digit is lost.
The client can be viewed as the middleman between the server and plotter as shown in Figure 1. After
the points’ coordinates are sent to the client, the plotter goes to a state where it waits to receive each
waypoint’s coordinates from the client. When the route is displayed completely, the user can continue
scrolling around on the map. If they select new start and end points, a new path should be retrieved from
the server. Finally, when they close the plotter, it writes a single character Q to the pipe. When the client
receives this character, it also writes Q to the socket and quits. The server cleans up and quits too when
it reads Q from the socket.
Two-way Communication between Client and Server
You will also implement the communication mechanism between the C++ client and server programs
using a pair of sockets. In particular, you will create a socket in the client program to send trip information
to and receive route information from the server program. An example of creating a client and a server
that interact via sockets can be found on eClass and an in-class demonstration of how to use these files
will be given.
8
Client program Server program
Plotter
inpipe
outpipe
Computing
Shortest Path
client
socket
server socket
127.0.0.1:8888
client server
Figure 1: Communication between the client and server.
The server program takes one command-line argument in Part II, and the client program takes two
command-line arguments. More specifically, these programs are executed as shown below:
./server [port]
./client [port] [server IP address]
For example, you can enter:
./server 8888
in a terminal to run the server on your VM. It will start listening to Port 8888 and accept incoming
connections. You can also run the client on your VM by entering this command in terminal:
./client 8888 127.0.0.1
The client will create a socket and try to establish a connection with the server that runs on the same
machine (since 127.0.0.1 is the localhost) and listens to Port 8888. This is how we test your client
and server in this assignment.
Note that the plotter should be run after a connection is established between the client and server. You
can run it by typing in a terminal:
./plotter
Part II Submission
You should submit a single file part2.tar.gz or part2.zip containing your solution. Put the
client and server programs in two separate subdirectories, named client and server, respectively.
The makefile should be placed in the main directory of your archive next to plotter. Running make
in the main directory should compile the object files and create two executables, one for the client and
one for the server in their respective subdirectories. This allows us to run the client program from
the main directory by typing ./client/client [port] [server IP address] in terminal,
and the server program from the main directory by typing ./server/server [port] in terminal. The plotter will be run after starting up both server and client by typing ./plotter in terminal.
9
If you are running all these programs from the main directory of your submission, you must move
edmonton-roads-2.0.1.txt to this directory too.
Your README file should also be placed in the main directory of your archive. Hence, after we extract
the submitted archive we should see the following files/directories:
• client directory
• server directory
• README
• Makefile
• plotter
The file README should be clearly broken into two sections, one for the client and one for the server.
The following targets are required in your Makefile:
• all: runs the server and client targets to generate all the executables. This is your main
target.
• server: links all object files for the server and builds an executable called server in the same
directory as your server.cpp.
• server.o: compiles the corresponding object (similar to Part I).
• dijkstra.o: that compiles the corresponding object (similar to Part I).
• digraph.o: that compiles the corresponding object (similar to Part I).
• client: links all object files for the client and builds an executable called client in the same
directory as your client.cpp.
• client.o: compiles the object.
• clean: removes all executable, objects, and named pipes.
You might add additional targets if necessary.
Additional Details
Your two main tasks in this part are as follows:
• Modify server.cpp so that it uses a socket to communicate the client. As described earlier, if
there is no path between two points in the Edmonton road network, the server should simply send N
0 and return to the state where it is waiting for a request. It does not wait for an acknowledgement
in this case.
• Modify client.cpp to implement two-way communication with the server and communication with the plotter. The client communicates with the server to get the route information (i.e.,
coordinates of the waypoints). The client should use exactly the same protocol described above.
Misc. Notes
• The assignment should be completed on the virtual machine that we provided for this course. The
plotter is built specifically for this VM and may not run on other platforms.
10
• If your client or server terminates unexpectedly, the named pipes will not close and you will get
an error that says mkfifo() failed in the next run. In that case, delete inpipe and outpipe
before running your code again.
• You may notice that it takes longer for the plotter to load the map in the highest zoom level than
the lowest zoom level. This is because it has to load and render an image that is larger in size.
• To make the search run faster for queries near each other, you may terminate it as soon as the
endpoint is added to the search tree in dijkstra(). It will not be a dictionary of all reachable
vertices, but it has the endpoint vertex of interest. This is optional.
• You may have heard about the “A∗
” heuristic improvement to Dijkstra’s algorithm (not covered in
class) which works very well with geographic graphs like road networks. Feel free to use this if you
want, but clearly document in your README that you have done so. This is the only acceptable
excuse to modify the parameters of the dijkstra() function. Again, this is optional and you
will lose marks for not properly implementing this search if you choose to incorporate this into
your submitted solution.
• Carefully read the starter code we provide in Part II, and play with the plotter application! It is
possible to finish the assignment by only working in a few places of the code, but it certainly helps
to understand everything that is going on.
The comments in the code suggesting you should make changes at those locations are just that:
suggestions. Feel free to ignore. You may add additional files if it helps.
• Indicate in the README every place where the client code was modified apart from the two .cpp
files we indicated you should modify! This may be slightly tedious, but it is required. We don’t
need an exhaustive description of what was changed (it should be clear from your comments), we
just need to know where to look.
If you forget where you edited, you can use diff with your solution against the original template
code.
• If you spot a bug in the starter code, you are not required to fix it but the instructors would still like
to know about it!
• If you properly set up the socket, your client should be able to communicate with a server running
on any computer with a known IP address assuming that it is not behind a firewall and the address
is static. For instance, you can try running the client program on your VM and the server on
another computer in your local area network. That being said, we will only test your submission
when the client and server both run on the VM.
• Remember to use a high number port that can be used for general purposes, like Port 8888. Do
not use port numbers less than 1024, such as port 20, 22, and 80; they are system/reserved ports
and can only be used for specific applications, such as SSH, Telnet, FTP. Typically, port numbers
in the range of 5000 to 64000 are safe to use.
11