Introduction
The purpose of our algorithm was to solve the Project File Dependencies problem. We wanted to solve it in an easy to understand manner, while using as much existing code as possible to minimize the chance of bugs in our code.
Details
To accomplish our goal, we made extensive use of STL containers and algorithms. This gives us the advantage of having fast, robust, and easy to use containers without having to roll our own.
task_list
The task_list class did the bulk of the work in solving PFD problems. It provided three methods for use by main: read_input, process, and output.
read_input
The main goal of read_input was to take in data from a generic stream and store into task_list's internal data structure. It finishes the store after the last line of input is entered.
process
We implemented process to do the actual heavy lifting of our solution. It uses task_list's internal data structure to calculate a list of tasks in the order in which they should be executed. This list is stored in internal task_list memory.
output
For displaying the results to the user, output takes in an output stream. It then writes any results of the previous process computation to the stream in the order in which they are stored in the list.
Internal Data Store
We used two main data structures within task_list in order to calculate execution order.
The first, map_rules, directly stores the input given by the user and serves as input to the process method. It uses the STL map structure to set up a fast association between task ids and their prerequisites. Each element is indexed by task_id, which is a nice way of accessing each task in logn time. It also provides a fast way of removing elements without the expense of resizing like std::vector.
Each actual values stored in the map is an STL set; this allows us to minimize storage and also have fast querying of elements. Each element in the set is a prerequisite for the map key.
Our second data structure for storing results was simply a STL vector. Each element is the task to be executed. The vector is sorted in order of execution. We then iterate through the vector on output and print out each element in order.
Algorithm
We used an STL priority_queue to sort groups of tasks in our PFD algorithm. While we still have elements in the map to process, we check for any keys that have an empty set of values. This would indicate that the corresponding task has no prerequisites. We then go through each task and remove the current task from the prerequisite list. Finally, we remove the task from the map so it doesn't get processed again and add it to our priority queue.
When all keys with empty values are processed, we unwind the priority queue. Since all processed keys are stored in the queue, we can retrieve each value in lexicographical order by popping from the front of the queue. We add these to the result vector. At the end of this operation, the priority queue is empty again. We continue the loop and search for more keys with empty values.
Conclusion
As a result of using STL containers such as map, set, vector, and priority_queue, we were able to quickly implement our solution while keeping it bug free. Our code is also extensible; by taking advantage of generic containers such as map, we can easily modify our code to accomplish similar tasks. For example, we could process a list of any kind of object for tasks instead of just integers. A future implementation could use strings of class descriptions and our code would require very little modification.