Mercurial > defical

comparison defical-c/src/graphmagic.cpp @ 0:ebed2bd0d300

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial import from svn. History be damned.
author Edho P. Arief <me@myconan.net>
date Fri, 02 Apr 2010 23:11:57 +0700
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:ebed2bd0d300
1 #include "graphmagic.h"
2
3 semtd::semtd(){}
4
5 semtd::semtd(uint32_t graphType,uint32_t NumVer, uint32_t numDef)
6 {
7 if(NumVer>3){
8 this->NumVer=NumVer;
9 this->numDef=numDef;
10 this->graphType=graphType;
11 this->TotalVer=NumVer+numDef;
12 this->numEdges=0;
13 this->isSureFail=false;
14 this->edgeLabelAbsoluteMax=this->TotalVer*2-1;
15 //initialize graph array
16 //this->theGraph.resize(this->NumVer+1,vector<bool>(this->NumVer+1,false));
17 for (int i=0; i<1000;i++)
18 {
19 for (int j=0;j<1000;j++)
20 {
21 this->theGraph[i][j]=false;
22 }
23 }
24 draw(this->graphType,1,this->NumVer);
25 resetLabels(0);
26 }
27 }
28
29 void semtd::draw(uint32_t drawType,uint32_t start,uint32_t end)
30 {
31 switch(drawType)
32 {
33 case 0:
34 {
35 for (uint32_t i=start;i<end;i++)
36 connectVertices(i,i+1);
37 break;
38 }
39 case 1:
40 {
41 draw(0,start,end);
42 connectVertices(start,end);
43 break;
44 }
45 case 3:
46 {
47 draw(1,start+1,end);
48 draw(2,start+1,end,start);
49 break;
50 }
51 case 4:
52 {
53 draw(0,start+1,end);
54 draw(2,start+1,end,start);
55 break;
56 }
57 case 5:
58 {
59 draw(4,start+1,end);
60 draw(2,start+2,end,start);
61 break;
62 }
63 }
64 }
65
66 void semtd::draw(uint32_t drawType,uint32_t start,uint32_t end, uint32_t extra)
67 {
68 switch(drawType)
69 {
70 case 2:
71 {
72 for (uint32_t i=start;i<=end;i++)
73 connectVertices(i,extra);
74 break;
75 }
76 }
77 }
78
79 inline void semtd::connectVertices(uint32_t a,uint32_t b)
80 {
81 if(!this->theGraph[a][b])
82 {
83 this->theGraph[a][b]=this->theGraph[b][a]=true;
84 this->numEdges++;
85 }
86 }
87
88 void semtd::resetLabels(uint32_t mode)
89 {
90 if(mode==0)
91 {
92 this->VerLabels.clear();
93 this->VerLabels.resize(this->NumVer+1,0);
94 }
95 this->edgeLabels.clear();
96 this->edgeLabels.resize(NumVer+1,vector<uint32_t>(NumVer+1,0));
97 this->isQuickMode=false;
98 this->scoreCache=-1;
99 //uint32_t *edgeLabelsUsedPtr;
100 //edgeLabelsUsedPtr=(uint32_t*)malloc(this->edgeLabelAbsoluteMax+1*sizeof(uint32_t));
101 this->edgeLabelsUsed.clear();
102 this->edgeLabelsUsed.resize(this->edgeLabelAbsoluteMax+1,0);
103 this->edgeLabelMax=0;this->edgeLabelMin=this->edgeLabelAbsoluteMax;
104 refreshEdgeLabelsMinMax();
105 }
106
107 void semtd::refreshEdgeLabelsMinMax()
108 {
109 uint32_t i;
110 for (i = 1; i <= this->edgeLabelAbsoluteMax; i++)
111 {
112 if (this->edgeLabelsUsed[i] > 0)
113 {
114 this->edgeLabelMin = i;
115 break;
116 }
117 }
118 for (int32_t x = this->edgeLabelAbsoluteMax; x >= 0; x--)
119 {
120 if (this->edgeLabelsUsed[x] > 0)
121 {
122 this->edgeLabelMax = x;
123 break;
124 }
125 }
126 }
127
128 inline uint32_t semtd::edgeLabelRange()
129 {
130 return this->edgeLabelMax-this->edgeLabelMin+1;
131 }
132
133 void semtd::setEdgeLabels(uint32_t verPos)
134 {
135 uint32_t newLabel,i;
136 for (i = 1; i <= this->NumVer; i++)
137 {
138 if (this->VerLabels[i] > 0 && this->theGraph[verPos][i] && i != verPos)
139 {
140 newLabel = this->VerLabels[verPos] + this->VerLabels[i];
141 this->edgeLabels[i][verPos] = this->edgeLabels[i][verPos] = newLabel;
142 this->edgeLabelsUsed[newLabel]++;
143 if (this->edgeLabelsUsed[newLabel] != 1)
144 this->isSureFail = true;
145 }
146 }
147 refreshEdgeLabelsMinMax();
148 }
149
150 void semtd::removeEdgeLabels(uint32_t verPos)
151 {
152 uint32_t i;
153 for (i = 1; i <= this->NumVer; i++)
154 {
155 if (this->VerLabels[i] > 0 && this->theGraph[verPos][i] && i != verPos)
156 {
157 int oldLabel = this->edgeLabels[i][verPos];
158 this->edgeLabelsUsed[oldLabel]--;
159 this->edgeLabels[i][verPos] = this->edgeLabels[verPos][i] = 0;
160 }
161 }
162 refreshEdgeLabelsMinMax();
163 }
164
165 void semtd::SetVerLabel(uint32_t verPos,uint32_t verLabel)
166 {
167 if (this->VerLabels[verPos] > 0) { RemoveVerLabel(verPos); }
168 this->VerLabels[verPos] = verLabel;
169 setEdgeLabels(verPos);
170 }
171
172 void semtd::RemoveVerLabel(uint32_t verPos)
173 {
174 if (this->VerLabels[verPos] > 0)
175 {
176 this->VerLabels[verPos] = 0;
177 removeEdgeLabels(verPos);
178 }
179 }
180
181
182
183 bool semtd::IsValidToLabel(uint32_t verPos,uint32_t verLabel)
184 {
185 uint32_t i,tempLabel;
186 //uint32_t tempMax=this->edgeLabelMax;
187 //uint32_t tempMin=this->edgeLabelMin;
188 for (i = 1; i <= this->NumVer; i++)
189 {
190 tempLabel=this->VerLabels[i] + verLabel;
191 if (i != verPos &&
192 this->theGraph[i][verPos] &&
193 this->VerLabels[i] > 0 &&
194 this->edgeLabelsUsed[tempLabel] == 1)
195 {
196 return false;
197 }
198 /*if(tempLabel>tempMax)
199 tempMax=tempLabel;
200 if(tempLabel<tempMin)
201 tempMin=tempLabel;
202 if(!isValidRange(tempMin,tempMax))
203 return false;*/
204 }
205 return true;
206 }
207
208 bool semtd::isValidRange(uint32_t min,uint32_t max)
209 {
210 uint32_t delta=1+max-min;
211 if(delta<=this->numEdges)
212 return true;
213 return false;
214 }
215
216 double semtd::SemtScore()
217 {
218 //TODO
219 return 0;
220 }
221
222 void semtd::FixLabel()
223 {
224 //TODO
225 }
226
227 void semtd::SwapLabel()
228 {
229 //TODO
230 }
231
232 string semtd::Print(uint32_t withDual)
233 {
234 uint32_t i,j;
235 string ret = "";
236 string n = "\n";
237 bool dualRun=false;
238 bool keepPrinting=true;
239 while (keepPrinting)
240 {
241 ret+="graph: ";
242 switch(this->graphType)
243 {
244 case 3:
245 {
246 ret+="wheel";
247 break;
248 }
249 case 4:
250 {
251 ret+="fan";
252 break;
253 }
254 case 5:
255 {
256 ret+="doublefan";
257 break;
258 }
259 default:
260 {
261 ret+="unknown";
262 break;
263 }
264 }
265 ret+=" | edges: "+uint32_t_to_str(this->numEdges)+" | vertices: " + uint32_t_to_str(this->NumVer)+" | deficiencies: " + uint32_t_to_str(this->numDef) + " | ";
266 uint32_t edgeweight=0,k,edgelabel=0;
267 for (i=1;i<=this->edgeLabelAbsoluteMax;i++)
268 {
269 if(this->edgeLabelsUsed[i])
270 {
271 edgeweight=i;
272 edgelabel=this->numEdges+this->TotalVer;
273 break;
274 }
275 }
276 if(dualRun)
277 {
278 edgeweight=2*(this->TotalVer)+2-edgeweight;
279 edgelabel=2*this->TotalVer+this->numEdges+1-edgelabel;
280 }
281 k=edgeweight+edgelabel;
282 ret+="mnum: "+uint32_t_to_str(k)+" | ";
283 for (i = 1; i <= this->NumVer; i++)
284 {
285 uint32_t theLabel;
286 if(dualRun)
287 theLabel=this->TotalVer+1-this->VerLabels[i];
288 else
289 theLabel=this->VerLabels[i];
290 if(i==1 && this->graphType==3)
291 ret+="c: " + uint32_t_to_str(theLabel) +" | l: ";
292 else if(i==1 && this->graphType==4)
293 ret+="c: " + uint32_t_to_str(theLabel) +" | p: ";
294 else if(i==1 && this->graphType==5)
295 ret+="c: " + uint32_t_to_str(theLabel) + ",";
296 else if(i==2 && this->graphType==5)
297 ret+=uint32_t_to_str(theLabel) + " | p: ";
298 else if(i==this->NumVer)
299 ret+=uint32_t_to_str(theLabel) + " | def: ";
300 else
301 ret+=uint32_t_to_str(theLabel)+",";
302 }
303 if(this->numDef>0)
304 {
305 vector<bool> usedLabels (this->TotalVer+1,false);
306 for(i=1;i<=this->NumVer;i++)
307 usedLabels[this->VerLabels[i]]=true;
308 j=0;
309 for(i=1;i<=this->TotalVer;i++)
310 {
311 uint32_t theLabel;
312 if(!usedLabels[i])
313 {
314 if(dualRun)
315 theLabel=this->TotalVer+1-i;
316 else
317 theLabel=i;
318 if(j==this->numDef-1)
319 {
320 if(dualRun)
321 ret+=uint32_t_to_str(theLabel)+" (dual)"+n;
322 else
323 ret+=uint32_t_to_str(theLabel)+n;
324 j++;
325 }
326 else
327 {
328 ret+=uint32_t_to_str(theLabel)+",";
329 j++;
330 }
331 }
332 }
333 }
334 /*
335 ret += n+"Deficiency: " + uint32_t_to_str(this->numDef);
336 ret += n+"GraphViz code: " + n + "----------------------------------";
337 //tempstr1<<this->graphType; //TODO: graphtype is now integer instead of string. create a convert method
338 ret += n+"graph " + uint32_t_to_str(this->graphType)+ "{";
339 ret += n+"graph[bgcolor=\"transparent\"]";
340 ret += n+"node [fontname=\"Bitstream Vera Sans\", fontsize=\"22.00\", shape=circle, style=\"bold,filled\" fillcolor=white];";
341 ret += n+"edge [style=bold];";
342 ret += n+" ";
343 for (i = 1; i <= this->TotalVer; i++)
344 {
345 ret += uint32_t_to_str(i) + ";";
346 }
347 for (i = 1; i <= this->NumVer; i++)
348 {
349 for (j = i + 1; j <= this->NumVer; j++)
350 {
351 if (this->theGraph[i][j])
352 {
353 uint32_t theLabel;
354 if(dualRun)
355 theLabel=this->TotalVer+1-this->VerLabels[i];
356 else
357 theLabel=this->VerLabels[i];
358 ret += n+uint32_t_to_str(this->VerLabels[i])+ " -- " + uint32_t_to_str(theLabel)+ ";";
359 }
360 }
361 }
362 ret += n+"}";
363 ret += n+"----------------------------------" + n + "End GraphViz code";*/
364 if(withDual==1)
365 {
366 withDual=0;
367 dualRun=true;
368 }else
369 keepPrinting=false;
370 }
371 return ret;
372 }
373
374
375
376 bool semtd::IsSemt()
377 {
378 uint32_t i;
379 if (this->isSureFail) { return false; }
380 else
381 {
382 if (edgeLabelRange() == numEdges)
383 {
384 uint32_t edgeLabelMin = this->edgeLabelMin;
385 uint32_t edgeLabelMax = this->edgeLabelMax;
386 for (i = edgeLabelMin; i <= edgeLabelMax; i++)
387 {
388 if (this->edgeLabelsUsed[i] != 1)
389 {
390 return false;
391 }
392 }
393 return true;
394 }
395 }
396 return false;
397 }
398
399 uint32_t semtd::MinDef()
400 {
401 uint32_t ret=0;
402 switch(this->graphType)
403 {
404 case 3:
405 switch (this->NumVer)
406 {
407 case 3:
408 case 4:
409 case 6:
410 case 7:
411 {
412 ret = 1;
413 break;
414 }
415 default:
416 {
417 ret = 2;
418 break;
419 }
420 }
421 case 4:
422 {
423 ret=1;
424 break;
425 }
426 case 5:
427 {
428 ret = (this->NumVer - 3) / 2;
429 break;
430 }
431 }
432 return ret;
433 }