TSP problem fixed
[charm.git] / examples / charm++ / state_space_searchengine / TSP_SE / main.C
1 #include "main.decl.h"
2
3 #include "searchEngine.h"
4 #include "exampleTsp.h"
5 #include <time.h>
6 #include <vector>
7 using namespace std;
8 int initial_grainsize;
9
10 CkVec< double> graph;
11
12 int  N;
13
14
15 #undef M_PI
16 #define M_PI 3.14159265358979323846264
17 /*
18 int geom_edgelen (int i, int j, CCdatagroup *dat)
19 {
20      double lati, latj, longi, longj;
21      double q1, q2, q3, q4, q5;
22
23      lati = M_PI * dat->x[i] / 180.0;
24      latj = M_PI * dat->x[j] / 180.0;
25
26      longi = M_PI * dat->y[i] / 180.0;
27      longj = M_PI * dat->y[j] / 180.0;
28
29      q1 = cos (latj) * sin(longi - longj);
30      q3 = sin((longi - longj)/2.0);
31      q4 = cos((longi - longj)/2.0);
32      q2 = sin(lati + latj) * q3 * q3 - sin(lati - latj) * q4 * q4;
33      q5 = cos(lati - latj) * q4 * q4 - cos(lati + latj) * q3 * q3;
34      return (int) (6378388.0 * atan2(sqrt(q1*q1 + q2*q2), q5) + 1.0);
35 }
36 */
37
38 void writeOutput()
39 {
40     FILE *file;
41     char filename[10];
42     sprintf(filename, "%d.tsp", N);
43     file = fopen(filename, "w");
44     if(file == NULL)
45     {
46         printf("file write error %s\n", filename);
47         CkExit();
48     }
49     fprintf(file, "%d", N);
50     graph.resize(N*N);
51     srand(time(0));
52     for (int i = 0; i < N; i++) {
53         for (int j = 0; j < i; j++) {
54             int edge = (int)( 1.1 * abs( (rand() % 701)) );
55             graph[i*N+j] = edge;
56             graph[j*N+i] = edge;
57             //CkPrintf("%d\t", edge);
58             fprintf(file, "%d ",edge); 
59         }
60         fprintf(file, "\n");
61         //CkPrintf("\n");
62     }
63     fclose(file);
64
65 }
66 void readinput_2(char* filename)
67 {
68     FILE *file;
69
70     char line[128];
71     char value[64];
72     vector<double> xcoord;
73     vector<double> ycoord;
74     int start;
75     int k, j;
76
77     file = fopen(filename, "r");
78     if(file == NULL)
79     {
80         printf("file read error %s\n", filename);
81         CkExit();
82     }
83     /* parse the header lines to get the number of vertices*/
84     fgets(line, 128, file);
85     sscanf(line, "%d", &N);
86     graph.resize(N*N);
87     for(int i=1; i<N; i++)
88     {
89         fgets(line, 128, file);
90         k = 0;
91         start = 0;
92         j=0;
93         while(line[k]!='\0')
94         {
95             if(line[k]==' ')
96             {
97                 memcpy(value, line+start, k-start); 
98                 value[k-start]='\0';
99                 //CkPrintf("value=%s, length=%d",  value, k-start);
100                 start = k+1;
101                 graph[i*N+j] = atof(value);
102                 graph[j*N+i] = atof(value);
103                 //CkPrintf("%f ", graph[i*N+j]);
104                 j++;
105             }
106             k++;
107         }
108         //CkPrintf("\n");
109     }
110     fclose(file);
111 }
112
113 void readinput(char* filename)
114 {
115     FILE *file;
116
117     char line[128];
118     char variable[64];
119     char value[64];
120     vector<double> xcoord;
121     vector<double> ycoord;
122
123     file = fopen(filename, "r");
124     if(file == NULL)
125     {
126         printf("file read error %s\n", filename);
127         CkExit();
128     }
129     /* parse the header lines to get the number of vertices*/
130     while(fgets(line, 128, file) != NULL)
131     {
132         if(strncmp(line, "DIMENSION", 9) == 0)
133         {
134             sscanf(line, "%s : %s", variable, value);
135             N= atoi(value);
136         }else if(strncmp(line, "NODE_COORD_SECTION", 18) == 0)
137         {
138             break;
139         }
140     }
141
142     xcoord.resize(N);
143     ycoord.resize(N);
144     int index;
145     float x, y; 
146     for(int i=0; i<N; i++)
147     {
148         fgets(line, sizeof line, file);
149
150         sscanf(line, "%d %f %f", &index, &x, &y);
151         xcoord[i] = x;
152         ycoord[i] = y;
153         CkPrintf("%d %f %f\n", index, x, y);
154     }
155     graph.resize(N*N);
156     for(int i=0; i<N; i++)
157         for(int j=0; j<i; j++)
158         {
159             double distance =  sqrt ((xcoord[i]-xcoord[j])*(xcoord[i]-xcoord[j]) + (ycoord[i]-ycoord[j])*(ycoord[i]-ycoord[j]));
160             graph[i*N+j]= distance;
161             graph[j*N+i]= distance;
162         }
163     CkPrintf("Done with reading\n");
164     fclose(file);
165 }
166  
167
168 class Main
169 {
170 public:
171     Main(CkArgMsg* m )
172     {
173
174         int arg_index = 1;
175         if(m->argc<2)
176         {
177             CkPrintf("Usage: tsp type(0-random graph, 1 inputfile, 2 inputfile) (Size of Problem) initialgrain\n");
178             delete m;
179             CkExit();
180         }
181         int type = atoi(m->argv[1]);
182         if(type == 0)
183         {
184             N = atoi(m->argv[2]);
185             writeOutput();
186         }else if(type == 1) //read from file
187         {
188             /* input file */
189             readinput(m->argv[2]);
190         }else if(type == 2)
191         {
192             readinput_2(m->argv[2]);
193         }
194         initial_grainsize = atoi(m->argv[3]);
195
196         CkPrintf("start\n");
197         searchEngineProxy.start();
198         delete m;
199     }
200
201 };
202
203 #include "main.def.h"