Programming Assignment 4 - Witness Relocation

See the assignment turn-in page (last modified on 21 January 2003) for instructions on turning in your assignment.

1. A town may hold at most one witness-criminal at any time.

2. If two towns are directly connected by a road, then only one of the two towns may hold a witness-criminal.

Given an area map showing towns and the roads between them, the FWRP is greatly interested in knowing the maximum number of witness-criminals it can relocate to the area under the above two rules.

typedef std::vector<unsigned> uvec;
typedef std::vector<uvec>     umat;

uvec maximum_placement(const umat & map);

that accepts an area map and returns the largest possible list of towns to which witness-criminals can be relocated, subject to the two constraints given in the Background Section.

Towns are represented by the unsigned numbers 0 through map.size() - 1 inclusive. The vector map[i] contains the list of towns that are directly connected to town i. A town never has a road to itself (that is, i is never contained in the vector map[i], and roads are two-way (that is, the graph is undirected: if i is contained in the vector map[j], then j is contained in the vector map[i]). The return vector contains a list of towns in no particular order.

The uvec and umat typedefs and the maximum_placement prototype are defined in maximum-placement.h in the assignment directory /export/home/class/cs-509/pa4.

You can test your procedure by compiling it with the file

where os is either linux, solaris, or stlport-solaris. Running the resulting executable calls maximum_placement() and compares the answer returned with my answer. If you get no output, then everything's fine; otherwise you'll get an error message indicating a problem.

The -s command-line option takes an integer argument and uses it as the seed for the random-number generator. You can run your code repeatedly on the same set of randomly-generated data by passing in the same value with -s on each execution. The default is to generate a different randomly-generated map with each execution.

The source file for main() will not be made available because it contains my answer to the problem.

If you use with stlport-solaris-main.o, make sure you compile and link everything with STLPort files; otherwise you'll get link errors.

Your implementation of maximum_placement() should not exploit any extra properties of the input data; I'll be generating different input data when I test your assignments.

To be correct, your solution must be efficient; that is, you solution should take no more than twice the execution time my solution takes on the same input. The test executable keeps track of execution times. The -t command-line option prints the execution time taken by your version of maximum_placement().