Your task is to implement your lex-labelling algorithm for posets, and use that as your "priority" for shelling a poset -- in that way, you will produce the minimum bump linear extension.

Amend the program so that it has the following behaviour:

./bump pos.lanky.treduc
0(8) 2(7) 1(6) 4(4) 3(5)--5(3) 6(2) 7(0) 8(1)
bump number is 1
Time is 0.015

1. You have already developed a program that reads in poset data from a file, populates the relevant data structures, and shells the poset into a linear extension, using priorities (for prototyping, the element "name" was the priority) on each element in a "greedy" manner when there are multiple options of what elements to shell.
   
   Your new program will be based on this program, so copy it over into your new directory, and give it a new name -- call the file that contains main "bump.cpp", or an analagous name if you are using a language other than C++.
   
   
2. Adapt the code from the previous lab that traverses the poset, from the top, and as lex labels get assigned, updates the lex profile of the lower elements; and when a lex profile is complete, submits that element to the appropriate data structure so that it can be assigned a lex-label.
   
   Note: Your lex-labelling may differ somewhat, depending on how your program breaks ties when two elements have the same list of lex labels of upper-covers. The above is a correct solution for the sample poset pos.lanky provided in the repository. You can also choose to lex-label in a parsimonious way -- i.e., when two elements are tied, they get the same lex label. The parsimonious lex labelling yeilds exactly one correct lex labelling, though there may still be multiple linear extensions realizing the optimal bump number. Parsimony in lex labels is superior, and requires a little more coding. In the comments in your code, identify your choice of parsimonious or linear lex labeling.
   
   Note: deque and vector are options for the lists of lex numbers of the upper covers. (See this web page. When declaring your data type for the list of lex numbers, put in a comment describing why you chose the data structure.
   
   You will have to get a lexicographic comparator operator working. This operator takes two sets and returns a boolean value indicating whether the first argument is ≤ the second, in the lexicographic sense. You can write and test this method; it may be that if you choose deque (or vector?) as your data structure in C++, the comparator operator is already overloaded to do lexicographic comparison. Yay!
   
   
3. First working subset:
   Once you have lexicographic labelling implemented and integrated into your poset-shelling program, you can be generating linear extensions in a manner that selects the highest lex-number when shelling the poset, when there are multiple elements available for shelling. This will involve a max-heap or Priority Queue, but this time the key values will be lex numbers, not the element name (number). You can use the Standard Template Library heap.
   
   
4. There is just one more step to having a program that generate the linear extension with the minimum bumps.
   
   When shelling the poset, amend your program so that you avoid shelling an element that covers the element just previously shelled. Among the elements that are not upper covers of the most-recently shelled element, select the one with the highest lex number.
   
   The above amendment requires you to think about the best way to accomplish this -- a tidy, elegent way. Give it some thought. You have a Priority Queue. When do you want to insert elements into it? Is it different when you know you have to take a bump, as opposed to when you know you'll be able to select the next element without introducing a bump?

1. An element can only be shelled if all its lower covers have already been shelled.
2. Within the elements that can be shelled, pick an element that is not a cover of the most recently shelled element. If none exist then you must shell an element that is a cover of the most recently shelled element.
3. Within the elements identified by the process given above, shell the element that has the largest lexicographic number.

Calling your program should be as follows:
> ./bump poset1.treduc
The output should be a linear extension which shows and enumerates the bumps:

0 2 3-4 1
bump number is 1
Time is 0.015

The location of the bump is given as two dashes between element 3 and element 4. You may want to be able to generate the lex numbers of each of the elements as well for testing purposes (you may put an "ifdef" in your code so that if "verbose" mode is on, you print out
0 (3) 2 (2) 3 (2)-4 (1) 1 (1)
as the linear extension, showing the lex numbers as well as element names. however, for testing purposes and comparison with known outputs, your program should also be capable of producing the output given above -- just element names separated by a single space, or a dash in the case of a bump. For the time, use the header <time> and add this line to the start of your code after your program has read in the file of less-than relations, but before it has performed any computation of lex numbers etc.:

clock_t start;
start = clock();

Then, at the end of your program after you have written out the linear extension, print out the time as follows:

cout << "Time: "<<(clock()-start)/(double(CLOCKS_PER_SEC/1000))<< endl;

For this lab, you will submit the code via git. Submit a makefile.