XJCO 1921- Programming Project
Coursework 2 – Route Planning
Deadline: 12 PM BST on Monday, 15 May 2023
This work is the second coursework for this module. It corresponds to 60% of the overall assessment for
this module. Submissions should be made via Gradescope.
Course Specification
Create a software program in C to compute the best path between 2 points on a map according to the
specification below. Use Github (link via Minerva) for version control throughout the project.
1. Coursework Specification:
You are given a large data set (to be downloaded from the GitHub Classroom) that represents all the
footpaths on the Leeds University Campus that you can use to test your application
1. Your program should read a map from a file. The data file is quite complex, and you have to decide
how to store the data. A suitable data structure candidate would be an Adjacency List which stores
a list of points in the data, and for every point, a list of points that are connected to it with edges.
You should also find a suitable data structure to store the map attributes, potentially by extending
the Adjacency List. Care should be taken to maximise memory access efficiency while minimising
your program's memory footprint.
2. You will need to implement an algorithm to compute the best route between two locations.
Like a real-life route navigation system, the "best" route can be:
a. The shortest route (by considering the distance between two points)
b. The quickest route (by considering the speed limit of roads)
c. The shortest route that meets some constraints, e.g., must pass a given location or POI (point of
interest)
A good implementation (1st) should flexibly support all these routing options.
3. You should consider a suitable way to visualise the data - for example, a basic requirement would
be plotting routes and edges in Gnuplot. However, A 1st mark would require using a graphical library
to visualise the data as part of your program in real time.
4. Your program should allow editing the map attributes by adding new routes and adding or changing
road attributes like speed limits. The edited map should be saved and can be reloaded by your
program.
Data file:
• The data file contains several lists of different types of data.
• The most basic is the "node", which is a point in space with coordinates defined by (lat,lon) - you
can use them as (x,y). Each node has a defined "id".
• The next is the "link", which is a line defined by 2 node id's.
• There is extra data in that file that you can use, and your program should be able to extend the
attributes if needed.
• There are several ways to read the data file. One way is to use fgets() and sscanf().
Notes:
• Your program must have more than one module (C file).
• The program should provide adequate error handling, i.e., display meaningful messages if an
error occurs and handle common errors. We will be running our own test cases to mark the
assignments and doing our best to devise creative ways to break your code! You should
therefore develop your test cases to beat us to it.
• Your code should not make hard code any relative paths. All file names should be specified by
command-line arguments. This will allow us to test any file location for input and output.
2. Good Programming Practice:
You should follow good software development practices. For this exercise, you are asked to:
• Follow modular development by making sure the code is modular and well structured; code with
proper comments
• Use Makefile for code compilation;
• Use a git repository for version control
Notes:
1. Makefile: You should also submit a Makefile with at least two targets: all and clean. "make all"
compiles your code to generate an executable binary, while "make clean" removes all object files
(.o), all executables, and any temporary files created during your run.
2. Modular design: We will check the commit logs of your git repository. By the end of Week 9, you
should commit a text file called "modules.txt" describing your proposed modules and their purpose.
Each module should have 1 paragraph of no more than 500 characters describing the module and
its purpose.
3. Test plan: By the end of Week 10, you should also commit a text file called "testplan.txt" with no
more than 2 paragraphs, each of no more than 500 characters, describing your test plan.
4. Version control: We will check the commit logs of your git repository. We expect to see steady
progress towards completion, as revealed in the pattern of git commits. One of the implications of
this is that we will be penalising any student who develops their code without git and then dumps it
all into git at the last minute.
Assessment/marking criteria grid
1. [5 marks]: Correctly load and store map files using an appropriate data structure (marks are capped
at 5 if static arrays are used)
2. [10 marks]: Implement an algorithm to find the best route to meet at least one of the "best" criteria
3. [10 marks]: Extend the implementation to support all best route definitions outlined in the
specification
4. [10 marks]: Support editing and adding map attributes
5. [10 marks]: Data visualisation and points for implementations that go beyond the expectation
6. [15 marks]: Programming practices (e.g., modular design, test plan and version control). Note that
the overall mark will be capped at 30 / 60 if the student gets less than 50% in this category
Submission
Your work should be submitted to the submission portal on Gradescope.
Your submission should be in a directory in the root of your git repository called "cw2" and contain
files that conform to the assignment specification. Your submission should contain all the relevant
source code and header files, a brief README file explaining how to run your submission and a
Makefile which builds all of the executables.
It is your responsibility to ensure that your submission compiles and executes on the lab machine.
Your git commit and push must be made prior to the submission deadline.
You should also include a test script called "test.sh" to automatically execute your test cases and any
test files you rely on.
In summary, your hand-in should include:
1. All necessary .c and .h files
2. A makefile as described above
3. A test script "test.sh"
4. A readme file called "readme.txt"
5. A test plan file called "testplan.txt"
6. A file called "modules.txt"
7. Any test data files which you use for your test script.
With the exception of the test files, all of these files must be in the cw2 directory. You may place the
test data files in a subdirectory if you wish.
Submit all your files in a single zip (.zip or .gz) file through Gradescope. If there are ANY other files
(e.g., object files or executable binary) or subdirectories in the directory when it has been handed in,
you will lose marks (from the programming practices category). This includes any hidden file (prefixed
with .), except for .git and .gitignore.
You should follow the instructions below on how to prepare your submission. Late submissions are
accepted up to 7 days late. Each day, or part of a day, will incur a 5% penalty.
Important notes on the submission:
• Write the program in standard C. If you write your code in any other language, it will not be
assessed, and you will get a zero mark.
• This is an individual project, and you are not supposed to work in groups or pairs
with other students.
• Be aware that plagiarism in your code will earn you a zero mark and will have very serious
consequences. If two (or more) students have large portions of their files nearly identical, they
will be accused of plagiarism or collusion. If found guilty, all parties involved will incur the
penalty, regardless of who was the author of the code. For this reason, never show or give
access to your code to anyone. Do not help a colleague by sharing your code, or you will both
be found guilty of collusion.
• It is your responsibility to make sure that nobody has access to your code. Lock the session
ifyou leave your computer unattended.
• Make sure to download and check your submission. Corrupted files, binary files, wrong
versions, copies of your project (over the years, we have seen it all), or anything other than
what is requested in this document will be considered invalid submissions.
• We will not accept submissions other than through Gradescope.
Marking and Demonstration
• This exercise will be marked during a lab session after the submission deadline.
• You will be asked to demonstrate your work from your Gradescope submission.
• You need to demonstrate your work to a member of the course team; failing to do so will
result in 0 marks.
• You need to come to the marking session with your completed exercise. We will not be able
to provide support for this exercise during marking.
• You should be able to explain what you have done clearly, to show that you understand the
concepts introduced.
• Checks for plagiarism and collusion will be carried out on all work.