Assignment 9
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Assignment 9
• Due Apr 18 by 8:59pm
• Points 0
• Available after Apr 5 at 8pm
This assignment is to completed individually. Please review the standards for academic integrity in the syllabus.
This assignment asks you to implement a weighted directed algorithm and implement two algorithms on it.
Note: You are allowed to work on these programs on your local computer. However remember to make sure that your programs work correctly on the Khoury Linux machines. We will be grading your assignments on those machines only!
The Graph
The above starter file provides a partial implementation of a weighted directed graph.
The characteristics of this graph implementation are:
1. This graph will represent a weighted directed graph. That is, the add_edge adds an edge from a given vertex to a given vertex. It does not add the reverse edge by default.
2. This graph represents adjacency information using an adjacency list representation.
3. This graph, once initialized, does not change the number of vertices.
4. Vertices of this graph are denoted by integer numbers, starting with 0.
Begin by completing the representation of this graph using an adjacency list representation. You may choose to use the given structure to represent a single node in this representation, or come up with your own implementation. In a list, each vertex stores its outgoing neighbors in any order. But each neighbor must occur exactly once in this list. The adjacency list representation also stores the weights of all edges.
Next, implement the functions that initialize and delete the graph in a file called graph.c .
Finally read the documentation of the add_edge and lengths_unweighted_shortest_paths functions and implement them in graph.c . Think about, and write the tests for these functions before you implement them. This will involve drawing out a directed graph, thinking about the shortest paths to all vertices from a specific vertex, and then writing a test that does this.
Feel free to add any helpers, although you do not have to test them directly.
Note that the lengths_unweighted_shortest_paths function returns an entire array of lengths! The length of this array is the same as the number of vertices in the graph. Also this function requires a queue. You are free to implement a queue in any way: an array or a linked list. But remember to implement it in graph.c : do not create additional .c files as the autograder will not include them in its compilation!
Weighted Shortest Paths
In this part you will implement a single function the returns the shortest paths from a given specific vertex to all vertices considering the edge weights. This is the function int *lengths_weighted_shortest_paths(graph_t *graph,int from) .
This implementation will use the Dijkstra's shortest path algorithm to find the lengths of the shortest paths from the specified vertex to all other vertices in the graph. This algorithm requires a priority queue with the following operations:
5. Add a vertex with a given priority to the queue.
6. Remove and return the vertex with the minimum priority.
7. Change the priority of an existing vertex in the queue.
You are free to implement this priority queue in any way (you may use a simple array, list or implement the binary min-heap). Implement the priority queue directly in the graph.c file: do not create additional .c files as the autograder will not include them in its compilation!
Write tests for this function, but not for the priority queue implementation.
What to Submit
Please submit the following:
• Source code, suitably styled and commented (graph.h, graph.c, tests_graph.c).
Grading Criteria
Source code
Your work will be graded using the following criteria:
• Style (code): suitable indentation, appropriate variable names, variables defined at the correct place (not using global variables)
• Functional correctness (code): program producing expected outputs for valid inputs, program producing expected messages for invalid inputs or invalid results. Also program not having any memory leaks and segmentation faults when run.
• Tests (code): different situations that you tested for, and whether the tests you wrote actually test for what you wanted to
• Comments (code): whether you wrote good comments (above each test, inside each function you are implementing as appropriate).
2024-04-10