Mercurial > defical

comparison defical-c/src/backtrack.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 "backtrack.h"
2
3 namespace bt{
4 backtrack::backtrack() {}
5
6 backtrack::backtrack(uint32_t graphType,uint32_t numVer,uint32_t numDef,uint32_t firstLabel,bool isAll)
7 {
8 this->theGraph=new semtd(graphType,numVer,numDef);
9 this->graphType=graphType;
10 this->usedLabels.resize(this->theGraph->TotalVer+1,false);
11 this->IsSemt=false;
12 setLabel(1,firstLabel);
13 this->firstLabel=firstLabel;
14 this->Result="";
15 this->RecurseAll=isAll;
16 this->pathLabel=this->startPath=this->endPath=0;
17 switch(graphType)
18 {
19 case 4:
20 {
21 this->startPath=2;
22 this->endPath=this->theGraph->NumVer;
23 break;
24 }
25 case 3:
26 case 5:
27 {
28 this->startPath=3;
29 this->endPath=this->theGraph->NumVer;
30 break;
31 }
32 }
33 }
34
35 inline void backtrack::setLabel(uint32_t verPos,uint32_t verLabel)
36 {
37 this->usedLabels[verLabel]=true;
38 this->theGraph->SetVerLabel(verPos,verLabel);
39 }
40
41 inline void backtrack::removeLabel(uint32_t verPos)
42 {
43 this->usedLabels[this->theGraph->VerLabels[verPos]]=false;
44 this->theGraph->RemoveVerLabel(verPos);
45 }
46
47 void backtrack::walk(uint32_t currentLevel)
48 {
49 if (this->IsProcessing)
50 {
51 if (currentLevel > this->theGraph->NumVer)
52 {
53 if (this->theGraph->IsSemt())
54 {
55 if(!this->RecurseAll)
56 {
57 this->IsProcessing = false;
58 }
59 this->Result += this->theGraph->Print(1);
60 //setDual();
61 //this->Result+="\nDual:\n"+this->theGraph->Print()+"\n";
62 //setDual(); //undo the damage
63 this->IsSemt = true;
64 }
65 removeLabel(currentLevel - 1);
66 }
67 else
68 {
69 //List<int> availableLabels = new List<int>();
70 vector<uint32_t> availableLabels;
71 uint32_t start=1;
72 uint32_t end=this->theGraph->TotalVer;
73 if(currentLevel==2 && this->firstLabel != this->theGraph->TotalVer)
74 {
75 if(this->graphType==3)
76 start=end; //optimization for wheel
77 else if(this->graphType==5)
78 start=this->firstLabel+1;
79 }
80 else if(this->startPath!=0)
81 {
82 if(currentLevel==this->endPath)
83 start=this->pathLabel+1; //remove possibility for reversed path labeling
84 else if(currentLevel==this->startPath && start<end)
85 end=this->theGraph->TotalVer-1; //no need to test last label as it'll be checked already on all previous cases
86 }
87 for (uint32_t i = start; i <= end; i++)
88 if (!this->usedLabels[i])
89 availableLabels.push_back(i);
90 if(availableLabels.size()>0)
91 {
92 for (int32_t x = availableLabels.size()-1; x >= 0; x--)
93 {
94 if((this->startPath!=0) && (currentLevel==this->startPath))
95 this->pathLabel=availableLabels[x];
96 if (this->theGraph->IsValidToLabel(currentLevel, availableLabels[x]))
97 {
98 setLabel(currentLevel,availableLabels[x]);
99 walk(currentLevel + 1);
100 }
101 if (!this->IsProcessing)
102 break;
103 }
104 }
105 if (currentLevel != 2) { removeLabel(currentLevel - 1); }
106 }
107 }
108 }
109 void backtrack::Walk()
110 {
111 if(this->theGraph->numDef>=this->theGraph->MinDef())
112 {
113 this->IsProcessing=true;
114 walk(2);
115 }
116 else
117 {
118 this->IsSemt=false;
119 }
120 }
121 }