Day: May 7, 2020

I have a project that I need to be implemented in C. It requires an implementation of a given priority queue specification and then using that to implement 4 algorithms: BFS, Bellman-Ford, Dijkstra’s and A*.

Project files have been given and it just requires the interfaces in pq.h and sp_algorithms.h to be implemented and ap.c to have its functionality completed. There are additional tests that need to pass to check the code works well (Provided).

FULL Description:

Intended Learning Outcomes (ILOs)
Upon successful completion of this lab, you will be able to

explain the various shortest path algorithms and their advantages/disadvantages

use existing data structures in your algorithms

combine existing data structures to get new functionality

write C code for the above concepts

use a test-driven development approach for algorithms and data structures

Assignment
Summary: Implement the interfaces specified in pq.h, sp_algorithms.h , and the functionality described in ap.c.

General Notes
Unless otherwise specified, its fine to over-estimate required array sizes to avoid dynamic re-allocation. For example, the queue required for BFS can be implemented as array with a size of num_nodes. This is the worst-case space required, but in most cases, significantly less nodes will be required, such that a dynamically growing queue would be more efficient (but also more complicated to implement1)

Try to program in a modular way. Do not duplicate functionality, but move it to own functions. Also, do not artificially inline unrelated functionality (for example, priority queue operations should not go inline into Dijkstras algorithm!). This only makes the algorithms complicated to read, and does not even bring efficiency advantages, as modern compilers are very good at automatically inlining themselves.

The assignment comes with a test-generator , which will test your data-structures and algorithms on randomly generated input data. Use this to test each module in isolation, before you build modules depending on it! Its much simpler to debug Dijkstras algorithms if you know that your priority queue is correct!

Also, feel free to modify the tests, e.g., to generate additional output useful for debugging your problem, or to pin down a particular bug. You can use the msg and assertmsg macros, that accept printf format strings.

Have a look at for the tests that we will run on your submission!

Min-Heaps
The elements of the heap will be nodes (node_t = unsigned integer). The priorities are given by an array D from nodes to weights (see weights.h for the available operations on weights)..

You have already seen a heap data structure, implemented by a tree encoded into an array. In this assignment, you will extend this idea to support an efficient operation to decrease the priority of a node that is already on the heap, as well as an efficient check whether a node is on the heap. For this, you maintain an additional mapping from nodes to heap-indexes. After decreasing a nodes priority, you use its heap-index to start a sift-up operation.

The file specifies the interface, including the required complexities for most operations. The file provides some suggestions how to implement the operations. You are free to follow them, or do your own implementation from scratch.

Shortest Paths Algorithms
The file specifies basic graph operations. The file provides an interface how to return results for single-source shortest path algorithms. You have to implement:

BFS, that ignores the weights and returns paths with minimal number of edges.

Bellman-Ford. First, dont care about negative weight cycles. Once you have got the algorithm correct for this case, you can try to correctly handle negative weight cycles: If, after |V|1 steps, you can still relax edges, set their target nodes distance to . Continue (for at most |V|1 more steps) until all nodes reachable via negative weight cycles have distance . However, do not update the predecessor map in this second phase!

Dijkstra. This will need a working priority queue implementation.

A*. We strongly recommend to implement this after Dijkstra! You can assume a monotone heuristics, such that it will be very similar to Dijkstra.

The Airport Example
In this example you will work on a graph generated from the openflight database, that encodes connections between airports on the world.

Your task is to implement a (DFS) based algorithm to count the number of airports that can be reached from a given start airport, and to compute shortest routes between two given airports. Use your graph algorithms!

See for the interface, and for a description what to implement. Exactly stick to the output format described there!