Description
Your task in the next two weeks (this MP is hard—do
NOT wait!) is to implement a request matching and
pathfinding subroutines for a tool that helps people to
find walking partners.
In particular, you must write C subroutines that identify
possible starting and ending points and that find the
shortest path between any pair of starting and ending
points. For this purpose, you will make use of a
‘pyramid tree’ and write code to implement a heap for
use by Dijkstra’s single-source shortest-paths algorithm.
The objective for this week is for you to gain experience
with array-based data structures in C, as well as some
experience in looking up well-known algorithms, such
as heaps.
Background
The screenshot above is generated automatically based on the output of your routines. As you might guess,
the input data are taken from OpenStreetMap data for the ZJUI campus area, and the image generation is
provided by your MP5 code. In the image, the yellow and orange circles represent the starting and ending
locales for two different people. Light grey lines represent roads, and blue dots represent nodes not in the
intersection of the yellow and orange circles. Green dots represent nodes in the intersection of the yellow
and orange circles (either the starting locales or the ending locales). Green dots are thus possible starting
and ending points for the shared walk. The black line is then the chosen shortest path between any pair of
green dots, assuming that the path must follow the roads.
In addition to a copy of the graph itself
with vertex positions (x,y), neighbors, and
distances between neighbors, you are
provided with a pyramid tree containing
all vertices in the graph. A pyramid tree
enables one to quickly locate nodes with
a specified geographic area. The pyramid
tree consists of a fixed number of nodes
fit into a single array as shown to the right.
The number of leaf nodes is equal to the
number of nodes in the graph, and each
vertex in the graph occupies one leaf
node. Internal nodes in the pyramid tree
divide space into (up to) four quadrants
(one node may have fewer children). For
example, if one examines an internal node
at array index N, array index 4N+1 is a
subtree in which all nodes have x values no greater than the x value of the internal node at array index N
and y values no greater than the y value of the internal node at array index N.
Pyramid tree node structure for node N. Leaf nodes (with no
children: 4N+1 ≥ # of nodes) represent graph vertices as
(x,y_left). Nodes with children subdivide space into up to four
parts. Note that children in any quadrant can be located on
the lines (equality is allowed in both directions).
Pieces
Your program will consist of a total of three files:
mp9.h This header file provides type definitions, function declarations, and brief
descriptions of the subroutines that you must write for this assignment. You
should read through the file before you begin coding.
mp9.c The main source file for your code. A version has been provided to you with
placeholders for the subroutines described in this document. You will need to
implement several heap-related subroutines—please place them in this file as
well.
mp9match.c The source file for your implementation of the match_requests function.
Four other files are also provided to you:
graph The map data. Feel free to test with your own graphs as well.
Makefile A file that simplifies the building and visualization process. See the section below
on Compiling and Executing Your Program.
mp9main.c A source file that interprets commands, calls your subroutines, implements some
game logic, and provides you with a few helper functions (described later). You
need not read this file, although you are welcome to do so. You may want to read
the headers of the helper functions before using them.
requests The requests used to generate the image at the start of this document. The file
consists of two requests (one per line). Each request consists of a starting locale
and an ending locale, and each locale consists of an X position, a Y position, and
an acceptable range (distance) from that center point.
Finally, we have included slightly modified copies of mp5.h and mp5main.c for visualization purposes.
In order to visualize your results, you must first add your own mp5.c solution file to your MP9H directory.
Only draw_line and draw_circle are used from your code, so as long as those functions are reasonably
correct, the visualization should work.
The Task
The total amount of code needed in my version of this assignment was under 200 extra lines.
The primary function for this MP has the following signature:
int32_t match_requests (graph_t* g, pyr_tree_t* p, heap_t* h,
request_t* r1, request_t* r2,
vertex_set_t* src_vs, vertex_set_t* dst_vs,
path_t* path);
The function provides you with a copy of the graph, a pyramid tree containing all vertices in the graph, a
“blank” heap for your use with Dijkstra’s algorithm, and two requests for walking partners. Each request
consists of two locales, a starting point and an ending point. Your code must identify up to
MAX_IN_VERTEX_SET graph vertices within range of the starting point for both requests—these should be
written into the src_vs argument. Similarly, your code must identify graph vertices within range of the
ending point for both requests—these should be written into the dst_vs argument. Finally, your code must
use a slightly modified version of Dijkstra’s single-source shortest path algorithm to find the shortest path
between any node in the source set and any node in the destination set. A forward path, including both the
initial and final nodes, should then be written into the path argument. If the source node set or the
destination node set is empty, or if the path requires more than MAX_PATH_LENGTH nodes (counting both
the starting and ending nodes), your function should return 0, in which case all outputs are ignored.
Otherwise, your function should return 1.
As a first step, you should implement a function to walk the pyramid tree and find any nodes within range
of a specified locale:
void find_nodes (locale_t* loc, vertex_set_t* vs, pyr_tree_t* p, int32_t nnum);
The find_nodes function should start at array index nnum and walk the pyramid tree recursively in order
to fill the vertex set vs with the array indices of any graph vertices found to be in range of locale loc. The
count of vertices in the vertex set should be initialized to 0 before calling find_nodes. You do not need
to recurse optimally, but you do need to be reasonably efficient, so use the splitting information in internal
pyramid nodes as best you can to avoid recursion. You must use the following function to check whether
a leaf node (a graph vertex) is in range of the given locale:
int32_t in_range (locale_t* loc, int32_t x, int32_t y);
Next, implement a function to remove any graph vertices that are not in range of a locale from a vertex set:
void trim_nodes (graph_t* g, vertex_set_t* vs, locale_t* loc);
Together, these two functions will enable your match_requests function to identify the possible starting
and ending graph vertices for the given pair of requests.
The last required function must implement Dijkstra’s single-source shortest path algorithm (see, for
example, https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm, or one of many other
sources of information about this algorithm online):
int32_t dijkstra (graph_t* g, heap_t* h,
vertex_set_t* src, vertex_set_t* dest, path_t* path);
The function should return 1 if a path is found that can fit into the path structure. You are encouraged to
make use of the heap provided to you to implement the algorithm. You will need to write several additional
heap-related subroutines to do so, including heap initialization, removing the closest unvisited graph vertex
from the heap, and reducing the distance to a vertex still in the heap. You have seen heaps in MP7. Here,
a parent node at array index N should be smaller (nearer, with smaller from_src distance) than both of its
children. Fields have been provided in the graph vertex structure to help you implement the algorithm.
You will need to modify the algorithm slightly (rather than calling it once for each possible starting point)
in order to obtain full credit. Your Dijkstra routine should write the shortest path found between any pair
of vertices in the src and dest vertex sets (respectively) into the path parameter. You may also want to
use the MY_INFINITY preprocessor constant to represent infinity in the algorithm.
Specifics
Be sure that you have read the type definitions and other information in the code and header file as well as
descriptions of Dijkstra’s algorithm (and, if necessary, heaps) before you begin coding.
Your code must be written in C and must be contained in the mp9.c and mp9match.c files in the
mp/mp9 subdirectory of your repository. Functions must appear in the correct files, as in the
distributed versions. We will NOT grade files with any other name, nor will we grade files with
functions moved between the files. You may add fields to vertex_t if desired for your
implementation of Dijkstra’s algorithm, but you may not make other changes to other files
except for debugging purposes. Track any such changes with care, and make sure to test without
them. If your code does not work properly without such changes, you are likely to receive 0 credit.
You must implement the match_requests, find_nodes, trim_nodes, and dijkstra
functions correctly.
You may NOT make any assumptions about the values of preprocessor constants in mp9.h. You
MUST use their symbolic names for full credit. We may choose to test your code with modified
versions of mp9.h.
You may assume that the parameter values passed into your match_requests function are valid
(the output parameters will contain bits, of course). You must ensure that your routines are then
passed valid parameters. We may test the individual routines mentioned with parameters other than
those provided to you as examples. You may, however, also assume that both vertex sets passed
into dijkstra contain at least one vertex.
Your routine’s return values and outputs must be correct.
Your code must be well-commented. Follow the commenting style of the code examples provided
in class and in the textbook, and be sure to add function headers containing the information that
has been provided for you in previous assignments (inputs, outputs, return value, and any side
effects, as well as a brief description).
Compiling and Executing Your Program
When you are ready to compile, type:
make
Warnings and debugging information are turned on in the Makefile, so you can use gdb to find your bugs
(you will have some).
If compilation succeeds, you can then execute the program by typing, “./mp9 graph requests” (no
quotes). You can also specify other graph files or other request pairs, but you will have to create such files
yourself (you may share them with other students for testing purposes). If your match_requests function
returns 1, visualization information will be written into a file called result.c.
After creating the file, you can visualize the given result by typing:
make image
which will produce the file image.png. Be sure to put a copy of your mp5.c implementation into the
MP9H directory before trying to make an image. If you make the image without executing mp9, the
Makefile will execute mp9 for you with the default arguments (the graph file and the requests file).
To clean up, type “make clean” (no quotes), or to really clean up, type “make clear” (as usual, no
quotes).
Grading Rubric
Functionality (60%)
15% – match_requests function works correctly
15% – find_nodes function works correctly
5% – trim_nodes function works correctly
25% – dijkstra function works correctly
Style (20%)
5% – find_nodes is reasonably efficient in recursing down the pyramid tree (no worse than the
gold version)
5% – trim_nodes compresses the vertex array in place by removing out-of-range vertices
5% – heap implemented well for Dijkstra’s algorithm
5% – uses only one execution of Dijkstra’s algorithm to find shortest path from any starting vertex
to any ending vertex
Comments, Clarity, and Write-up (20%)
5% – introductory paragraph explaining what you did (even if it’s just the required work)
5% – function headers are complete for all implemented functions (including those for heap or other
support functions)
10% – code is clear and well-commented, and compilation generates no warnings (note: any
warning means 0 points here)
Note that some categories in the rubric may depend on other categories and/or criteria. For example, if you
code does not compile, you will receive no functionality points. As always, your functions must be able to
be called many times and produce the correct results, so we suggest that you avoid using any static storage
(or you may lose most/all of your functionality points).
