CSCI 422 Fall 2022: Assignment 5: Poset "Get LE with Priority"


For the student to submit, using Git ( instructions)

Due: Nov 31, 11:59 pm

Objective: to extract an optimal linear extension from a poset presented as a Hasse diagram (i.e., covers relations -- the transitive reduction).

Some learning objectives: To manipulate multiple interacting data structures; to learn effective use of STL vector, deque or multiset, and heap or other priority queue.

You will be provided with an executable program called ``reduce" that works as follows:
$> ls
reduce pos.6.test
$> ./reduce pos.6.test
$> ls
reduce pos.6.test pos.6.test.treduc
$> cat pos.6.test
6
0 2 4 3 5 6
1 3 5 4 6
2 4 6
5 6
6
$> cat pos.6.test.treduc
6
0 2 3 6
1 3 6
2 4 6
3 4 5 6
4 6
5 6
6

The "reduce" program computes the transitive reduction of a poset and writes it to a file with ".treduc" as the name extension -- like your program from a previous assignment, but it is standalone.


2. (16 marks) Write a program called "bump" that takes a file name as an argument on the command line and opens the file, assumes it is in the format of the transitively-reduced data output from Part 1, and reads in the poset into a sparse data structure for the covers relations. Use your previous poset program as a basis. However, be aware that your program should run in O(n log n +m), where n is the number of elements and m is the number of cover relations. Consequently, you will not have "time" to fill a covers matrix, as you did in Lab3 ("Less").

Calling your program should be as follows:
> ./bump poset1.treduc
3 5 4 6 9 11 1 2 10 7 8
3 5 4 6 9 11 1 2 10 7 8


(Not the actual "greedy" linear extension ... I will update it.) The program should populate the appropriate data structures, using the data from the file. Then is should compute the following: Find a linear extension that is optimal given a set of priorities on the elements. I.e., when possible, higher priority elements will be pushed to the front of the linear ordering of the elements, but the ordering must nevertheless obey the precedence constraints given in the partial order.

For each element, you will initially take the element name to be the value of its priority. However, you will program it anticipating that another key value may be attributed to each element, and that key value will be used as the priority. The key type will be an integer. (Eventually, it will be the lex-label of the element.) Your program will find the linear extension (a 1-processor schedule) that greedily chooses the highest-priority element that can be scheduled in any given time slot. Some implementation of a Priority Queue (max-heap) will be required. You can write your own or use the STL heap or other such priority queue. Reference your source if it is not STL or your own code for the priority queue. Keep your running time within O(n log n+m).

Calling your program should produce output like the following:

> ./bump poset1.treduc
3 5 4 6 9 11 1 2 10 7 8
3 5 4 6 9 11 1 2 10 7 8

Above, 3 5 4 6 9 11 1 2 10 7 8 is a linear extension of poset1.treduc, and it is the linear extension that has greedily selects for highest priority first. The second line is the same linear extension, but instead of printing out the name of the element, you are printing out the key of the element. The key is, in this instance, the same as the element name.

You are to use git to push our bump.cpp, reduce.cpp, makefile, poset.h, bump.h files.

For this lab, you will submit the code via git. Instructions are here:
Git instructions

You will be marked on: