Student Heuristic Results for the first project submission

For Algorithms 1 and Algorithms 2 I ran your code as submitted. For Algorithm 3, I edited programs to make them conform better to the specifications. For all of the results, the "k 1" column is the best known result for the problem. The "k 2" column is my implementation of Algorithm 1. I hope you can beat these results for your creative heuristics.

Your score for each problem is:

• n if your program fails to find a solution to a problem of size n.
• Otherwise it is your solution minus the k 1 solution.

Smaller scores are better.

1. Algorithm #1: Random vertex order greedy
2. Algorithm #2: Random BFS-order greedy
3. Algorithm #3: Your own creation

You can use command files like the ones I used to make these tables to test multiple variants of your heuristics. Supposed you are in a directiory and each heuristic is in some subdirectory: 1_random, 2_bfs 3_creative, 4_modified, ... The top level directory has the input files and the comparison files:

in_c80.txt          in_football_1.txt   in_football_2.txt  in_football_3.txt  
in_hypercube_1.txt  in_hypercube_2.txt  in_hypercube_3.txt  
in_queen.txt        in_kneser.txt       

c80.txt             football_1.txt      football_2.txt      football_3.txt      
hypercube_1.txt     hypercube_2.txt     hypercube_3.txt    
kneser.txt          queen.txt

Then to get the tabulated results, you can use a command file with the commands in table_com.txt (copy it by right clicking on this link and using "Save as" since the html below might not copy correctly).

The command file looks like this:

echo "C80 fullerenes:" > creative_table.txt
echo " " >> creative_table.txt
a.out c80.txt  */oc80 >> creative_table.txt
echo " " >> creative_table.txt
echo "Football distance 1:" >> creative_table.txt
echo " " >> creative_table.txt
a.out football_1.txt */of1 >> creative_table.txt
echo " " >> creative_table.txt
echo "Football distance 2:" >> creative_table.txt
echo " " >> creative_table.txt
a.out football_2.txt */of2 >> creative_table.txt
echo " " >> creative_table.txt
echo "Football distance 3:" >> creative_table.txt
echo " " >> creative_table.txt
a.out football_3.txt */of3 >> creative_table.txt
echo " " >> creative_table.txt
echo "Hypercube distance 1:" >> creative_table.txt
echo " " >> creative_table.txt
a.out hypercube_1.txt */oh1 >> creative_table.txt
echo " " >> creative_table.txt
echo "Hypercube distance 2:" >> creative_table.txt
echo " " >> creative_table.txt
a.out hypercube_2.txt */oh2 >> creative_table.txt
echo " " >> creative_table.txt
echo "Hypercube distance 3:" >> creative_table.txt
echo " " >> creative_table.txt
a.out hypercube_3.txt */oh3 >> creative_table.txt
echo " " >> creative_table.txt
echo "Kneser Graphs:" >> creative_table.txt
echo " " >> creative_table.txt
a.out kneser.txt */ok >> creative_table.txt
echo " " >> creative_table.txt
echo "Queen Graphs:" >> creative_table.txt
echo " " >> creative_table.txt
a.out queen.txt */oq >> creative_table.txt

To see which columns correspond to which programs you can add this in dom_comp.c:

#define PRINT 1
    for (i=1; i < argc; i++)
    {
        fp[i-1]= fopen(argv[i], "r");
        if (fp[i-1] == NULL)
        {
            printf("Failed to open file %2d: %s\n", i, argv[i]);
            exit(0);
        }
#if PRINT
        printf("File %2d : %s\n", i, argv[i]); // Add to show what columns mean.
#endif
    }

I used command files like this to make the tablulated results but did not include the files names for privacy reasons.