anshul1004 / lubymis Goto Github PK

Team Members:
Anshul Pardhi arp180012
Jayita Roy jxr190003
Ruchi Singh rxs180057

We have divided the project into several tasks:
1. Study LubyMIS algorithm: Anshul, Jayita, Ruchi
2. Study multithreading in Java: Anshul, Jayita, Ruchi
3. Create input file from graph: Jayita
4. Implement code to parse input file graph: Jayita
5. Implement LubyMIS algorithm: Anshul
6. Implement thread synchronization: Ruchi
7. Integration of LubyMIS algorithm with thread synchronization: Anshul, Jayita, Ruchi
8. Implement method to check if the generated MIS is correct: Anshul
9. Implement code to generate output file to store results: Anshul
10. Test the code with the same input multiple times: Ruchi
11. Create multiple graph input files to test the correctness of the implemented algorithm: Jayita
12. Test the code on new input files, and generate their corresponding output files: Anshul, Ruchi
13. Documentation (code comments, README): Anshul, Jayita, Ruchi

To implement the Luby's MIS algorithm, we have created a Luby.java file. To compile and run the Luby.java code, there are following steps that need to be followed -

a) The algorithm will run on csgrads1 server.
b) Make sure Java 1.8 or any other higher version is installed on the machine.
c) The code takes two command-line arguments i.e., input and output file names. Make sure the input file is in the same directory with the code file or make appropriate changes according to the file path in the command line argument.
d) The input file contains 3 lines -
   1) n, number of vertices in the graph
   2) id array; a one-dimensional array of size n
   3) adjacency matrix (which is a symmetric n by n matrix). 1 represents if the nodes are adjacent to each other and 0 otherwise.
e) First, to compile Luby.java use command "javac Luby.java".
f) A Luby.class file will be created in the same directory after compiling the java file.
g) Now, to run the above code, use command "java Luby inputfile outputfile" e.g. java Luby input1.txt output1.txt
h) An output file will be created which contains the rounds (rounds took to generate the MIS), resultant MIS set and a verification message whether the generated MIS is correct or not.