**ECE220: Computer Systems & Programming **

**Machine Problem 9 **

**Mieber: Walk Me There **

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 the 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. The 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 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 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.

**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 **mp9 **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_tnnum);

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 **mp9 **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).

更多代写：cs北美留学生代写 代考被抓 英国精算代考 北美Academic source代写 澳洲数学网课代考 硕士论文课业代写