Bonus Project
CSC 445/545, Fall 2014
Dominating Set Challenge- Testing Heuristics

A dominating set of a graph G is a subset S of the vertices of G such that every vertex is either in S or it has at least one neighbour in S. The goal is to find a minimum dominating set. Some notes on the dominating set problem are available: CSC 422/522 Notes: See lectures 15, 16, and 20.

The goal is to design two fast C or C++ heuristics for the dominating set problem. Then compare them in terms of both the time that they take and the quality of the results. If you are also taking CSC 422/522, then you should implement 3 heuristics instead of 2 (one for CSC 422/522). The program takes as input a sequence of graphs, and finds a small (but not necessarily minimum) dominating set for each one.

Use some of the tactics presented in class:

1. Hill Climbing (Random restart)/Iterated Greedy Algorithm
2. Tabu Search
3. Simulated annealing
4. Genetic algorithms
5. Ant Colony algorithms
6. Neural Networks

Input must be from standard input. and output must go to standard output. I am going to run it like this:
a.out < in.txt > out.txt

Do not hardcode a file name into your program. Your programs will be tested for correctness using various command files. If you want your program to run correctly, it is very important to follow the input and output specifications exactly.

Use:
#include <stdio.h>
#include <stdlib.h>
Some compilers include these automatically. Others do not and programs without them do not compile.

Use a constant NMAX for the maximum number of vertices:
#define NMAX 800
If you use an adjacency list data structure, you can use:
#define MAX_DEGREE 100
If NMAX is not big enough, print an error message that explains that the user should increase NMAX and recompile. If MAX_DEGREE is not big enough, print an error message that explains that the user should increase MAX_DEGREE and recompile. Do not use malloc/free. Using repeated malloc/free calls will end up slowing the program down and could create bugs that cause memory leaks. Memory leaks are a disaster when you are working with large computations.

The Input Format

Vertices of an n-vertex graph are numbered from 0 to n-1.
A graph is input as:
<number of vertices>
Then for each vertex v:
<degree of v> <neighbours of v>

Your program should permit the user to use arbitrary amount of white space and arbitrary line spacing when typing these numbers in.

For example, an input file like this:

 10
3   1   4   5
3   2   0   6
3   3   1   7
3   4   2   8
3   0   3   9
3   0   9   6
3   1   5   7
3   2   6   8
3   3   7   9
3   4   8   5

 12
3   1   5   6
3   2   0   7
3   3   1   8
3   4   2   9
3   5   3  10
3   0   4  11
3   0  11   7
3   1   6   8
3   2   7   9
3   3   8  10
3   4   9  11
3   5  10   6

Represents the following two graphs:

The Output

For each graph, first print the graph number (number the graphs starting at 1) followed by the number of vertices. Each time you find a better dominating set, print it. To print a dominating set:
First print either 0, 1, or 2 where:
0 means that the dominating set is the best found so far, and
1 means that the dominating set is a minimum dominating set for the graph,
and 2 means the algorithm is terminating with a dominating set but it not able to ascertain that it is a minimum dominating set.
Then print the number of vertices in the dominating set followed by the vertices in the dominating set. It is assumed that after you have printed a dominating set prefaced by 1 or 2 that the computation on that graph has completed.

For example, for the input file above, the output might be:

  1  10
0   5   5   6   7   8   9 
0   3   4   6   7 
1   3   4   6   7 

  2  12
0   6   6   7   8   9  10  11 
0   4   5   7   8   9 
1   4   5   7   8   9 

The second line represents this dominating set:

The third line is printed at the end of the computation for the graph and indicates that this dominating set is a minimum one.

The first line for the second graph represents this dominating set:

The second line gives this dominating set:

The third line for this graph indicates that this dominating set is a minimum dominating set.

IMPORTANT: The test cases could include either problems that are too difficult for your program to solve in a reasonable amount of time or may include too many problems. To get credit for what your program can do within the time limit, use
fflush(stdout);
each time you print a dominating set. Here is some sample code that you could use:

#include 
// Status 0 means the dominating set is the best so far.
// Status 1 means the dominating set is a minimum dominating set.
// Status 2 means program terminated with this dominating set but it may not be a minimum dominating set.
// Code created by Wendy Myrvold.
void print_solution(int status, int size, int dom_set[])
{
    int i;
    printf("%1d %3d ", status, size);
    for (i=0; i < size; i++)
        printf(" %3d", dom_set[i]);
    printf("\n");
    fflush(stdout);
}

Upload to connex:

Upload each file separately. Do not archive or compress the files. You are allowed an unlimited number of submissions until the deadline. Do not upload "draft" submissions (they do not get downloaded for marking).

Upload one program (your first heuristic) under the Heuristic1 assignment. Upload your second program (your second heuristic) under the Heuristic2 assignment.

1. For each program, preface each file name with your first name. For example, I might have:
   wendy_include.h
   wendy_io.c
   wendy_main.c
   Your program should compile if I use
   gcc *.c
   for a C program, or
   g++ *.cpp
   for a C++ program.
2. Upload a .pdf document that describes the algorithms you implemented in the Heuristic1 assignment. Preface the file name with your first name. For example, I would use the file name wendy.pdf

Marking Scheme

The marking scheme:

For each heuristic:

1. [5] Good modular code design.
2. [5] Lots of comments.
3. [20] Correctness.
4. [5] Speed.
5. [5] Creativity in applying the tactic chosen. It is OK if your approach is simple if it gives high quality answers.

1. [10] Description of the two heuristics.
2. [10] Comparison of results: time and quality. You do not have to compare the results on all the sample input files. Instead, choose some interesting selection of graphs from the random graphs or interesting graphs provided (preferably some which illustrate a difference in performance for your two heuristics).