I wrote a program compare.c that you can use for comparing results from various algorithms for your dominating set project. You may use it as part of your research for the class. You can use the tables it generates in your reports. You may not distribute the code to anyone else. You may not upload the code to the internet. You can get the code from the resources section on connex.
You can use it to compare your exact algorithm results to mine. It is also very useful in comparing various heuristics to each other and to the exact algorithm results.
The program will check to ensure your output files are in the correct format. If not, or if you have a dominating set that is not correct, you will see an error message. It is your responsibility to ensure your output files are in the correct format (without anything else printing). Check them with this program to make sure they are OK before submitting. I am going to use this program to evaluate the quality of your results when marking the project.
To compile:
gcc compare.c
If you just type the name of your executable file,
it will tell you how to use the program.
For example, I would type:
a.out
and it prints:
Usage a.out <input file> <dominating set output files>
I had 3 output files based on the input file icage.txt:
ocage.txt: results from running my exact algorithm for 2 minutes.
o30cage.txt: results from running my exact algorithm for 30 minutes.
ocage_heur.txt: results from running a heuristic algorithm.
To compare these output files, I use:
a.out icage.txt ocage.txt o30cage.txt ocage_heur.txt
The starred entries in the output file are the best results.
The value in the []'s is the number of vertices of the graph.
The output file looks like this:
Input file: icage.txt
Output files: ocage.txt o30cage.txt ocage_heur.txt
Graph 1 [ 4]: 1* 1* 1*
Graph 2 [ 6]: 2* 2* 2*
Graph 3 [ 10]: 3* 3* 3*
Graph 4 [ 14]: 4* 4* 4*
Graph 5 [ 24]: 7* 7* 7*
Graph 6 [ 30]: 9* 9* 9*
Graph 7 [ 58]: 15* 15* 16
Graph 8 [ 58]: 16* 16* 17
Graph 9 [ 58]: 16* 16* 16*
Graph 10 [ 58]: 16* 16* 17
Graph 11 [ 58]: 15* 15* 17
Graph 12 [ 58]: 15* 15* 17
Graph 13 [ 58]: 15* 15* 17
Graph 14 [ 58]: 16* 16* 17
Graph 15 [ 58]: 15* 15* 17
Graph 16 [ 58]: 15* 15* 16
Graph 17 [ 58]: 15* 15* 17
Graph 18 [ 58]: ___ 15* 16
Graph 19 [ 58]: ___ 15* 16
Graph 20 [ 58]: ___ 15* 17
Graph 21 [ 58]: ___ 16* 16*
Graph 22 [ 58]: ___ 16* 16*
Graph 23 [ 58]: ___ 16* 16*
Graph 24 [ 58]: ___ 15* 17
Graph 25 [ 70]: ___ 18* 20
Graph 26 [ 70]: ___ 19* 20
Graph 27 [ 70]: ___ ___ 20*
Graph 28 [112]: ___ ___ 35*
Graph 29 [272]: ___ ___ 86*
Graph 30 [384]: ___ ___ 123*
Number of times that each algorithm had a best answer:
: 17 26* 14
Number of cases with an answer:
: 17 26 30*
Number of graphs in the file: 30