My favorites | Sign in
Project Home Wiki Issues Source
READ-ONLY: This project has been archived. For more information see this post.
Search
for
PageName  
Updated Feb 14, 2012 by J.Wes.Pickens

Introduction

This is Project 2 in CS 373, Spring 2012. The assignment is to write a program in Python to handle the Project File Dependencies problem as described on the Sphere website (http://www.spoj.pl/problems/PFDEP/).

Algorithm Summary

My algorithm accepts as input a directed acyclic graph (aka "DAG") representing a collection of tasks and the dependencies between tasks. The DAG is specified as follows...

  • The first line is two integers. The first integer represents the number of vertices (tasks) in the DAG and the second integer represents the number of rules (dependencies).
  • Subsequent lines contain at least three integers. The first integer specifies the vertex which has dependencies. The second integer, n, represents the number of dependencies the vertex has. This is followed by n integers which are the dependencies for the specified vertex.

The algorithm then outputs a string to stdout of each vertex in the DAG, seperated by a space, in an order representing a topological sort. As such, no vertex is listed before a vertex upon which it has a dependency. Ties are broken with the lowest numbered vertex first.

Algorithm Detail

My algorithm functions as a while loop, constantly repeating the process of reading input, performing the sort operation, and outputting the results until the end of the input file is reached.

When reading input, the algorithm reads the first line of the DAG representation, storing the two integers into an array, such that these values can be more easily passed between functions. Then the values on subsequent lines, representing dependency rules, are read and stored into a 2-dimensional list.

When performing the sort operation, my algorithm maintains a list of vertices with no dependencies. This list is implemented as a binary heap, such that the lowest-valued element in the list is always at the first position. The algorithm first examines the rules to find the initial vertices with no dependencies. (Since a DAG has no cycles, it must have at least one such vertex at all times.) Once the binary heap is initialized, the first element from the heap is written to the output string. Then the 2-dimensional list of dependency rules is examined to find any vertices which have the vertex in question as a dependency. The number of dependencies for all such vertices is decremented. Also, if the vertex in question is has a row in the list of dependency rules, that row is removed. Then the vertex in question is removed from the binary heap and the dependency rules are examined again to find any new vertices with no dependencies. All such vertices are added to the binary heap. This process continues until both the list of dependency rules and the binary heap are empty. The string containing the topological sort is returned.

The algorithm then outputs the sort string to stdout.

Design Process

I found this project a little easier to manage than the first one because I'm now more familiar with the utilities being used. Another simplifying factor was not having to keep two versions of the code in different languages consistent with each other (as with the first project).

I found the most difficult part of the process to be writing the auxiliary program to generate the DAGs needed for use in acceptance testing.

Also, I'm still having some difficulty getting used to writing unit tests before writing code, but I'll adjust.

Powered by Google Project Hosting