To get the program described here, and the 12 sample input files:
I ran my simple dominating set algorithm for two minutes on each input file. The output files I got are included. Note that most of the time, the dominating set algorithm was not able to finish.
I created a program that can generate various sorts of random graphs for testing dominating set algorithms. To compile the random graph generator:
gcc -o gen gen.c
Then to run it:
Usage: gen < type > < start_n > < end_n > < increment > < density/degree> Type: 1: standard random graph with a given density. 2: random grid graph with a given density. 3: random almost regular graph with given density. 4: random regular graph with given degree.For each type, the program will output one graph for each value of n for n starting at start_n, increasing at each step by increment and going up to n at most end_n. For types 1-3, the last parameter is the desired edge density (the percentage of all possible edges that will be present in the generated graph). For example, if you use density=50, 50% of the possible edges will be added to the graph. The number of edges the graph will have is m= density * (n * (n-1) / 2 ) / 100. For type 4, the last parameter gives the degree of the regular graph generated.
The commands used to generate the input files:
gen 1 20 300 20 10 > in_1_10.txt gen 1 20 300 20 20 > in_1_20.txt gen 1 20 300 20 30 > in_1_30.txt gen 1 20 300 20 40 > in_1_40.txt gen 2 20 300 20 10 > in_2_10.txt gen 2 20 300 20 20 > in_2_20.txt gen 2 20 300 20 30 > in_2_30.txt gen 2 20 300 20 40 > in_2_40.txt gen 3 20 300 20 10 > in_3_10.txt gen 3 20 300 20 20 > in_3_20.txt gen 3 20 300 20 30 > in_3_30.txt gen 3 20 300 20 40 > in_3_40.txt gen 4 20 300 20 3 > in_4_3.txt gen 4 20 300 20 4 > in_4_4.txt gen 4 20 300 20 5 > in_4_5.txt gen 4 20 300 20 6 > in_4_6.txt
The output file obtained after running the dominating set algorithm for two minutes on each input file are:
odom_1_10.txt odom_1_30.txt odom_1_20.txt odom_1_40.txt odom_2_10.txt odom_2_30.txt odom_2_20.txt odom_2_40.txt odom_3_20.txt odom_3_40.txt odom_3_10.txt odom_3_30.txt odom_4_3.txt odom_4_5.txt odom_4_4.txt odom_4_6.txt
I first generate an array containing all the possible edges in the graph. Then I choose a random permutation of the edges. The first m edges are then added to the graph.
The vertices are first given (x,y)-coordinates where x and y are in the range [0, n-1]. For example, for a 10 vertex graph, the locations of the vertices numbered 0 to 9 could be like this:
__ __ __ __ __ __ __ __ __ __ __ 6 8 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ 0 __ __ 5 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ 7 __ __ __ 4 __ __ __ __ __ __ 9 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ 3 __ 2 __ __ __ __ __ 1 __ __ __ __ __ __
For each possible edge, the distance between its endpoints is computed. The edges are then sorted according to these distances. The first m edges are then added to the graph. The resulting graph with edge density 15% is:
10 2 6 7 1 3 1 3 2 1 2 0 0 2 0 8 2 0 9 1 6 1 7
A picture of this graph:
These graphs are very different from random graphs because vertices close to each other are connected to each other leading to local cliques of vertices. This model of random graph can represent randomly sprinkled wireless sensors where the edges are added between any pair of sensors that are close enough to communicate with each other.
To create these graphs, I first choose a random permutation of the vertices. The permutation p is interpreted as a matching that has the edges (p[2k], p[2k+1]) for k=0 to .. n/2. This matching is added to the graph. Then we keep selecting new random matchings and adding any edges that would not create multiple edges until the desired number of edges are included. These graphs are regular if no multiple edges arise. They are different from the first two classes of random graphs: the degrees fall into a more narrow range.
This option generates regular graphs. The last parameter is the degree for the regular graph. I used the same approach to generate these graphs as for the almost-regular graphs, but if multiple edges arise, the graph is rejected, and the process is restarted. The algorithm is repeated until a graph that is regular is generated.