00001
00011
00012 #ifndef SEARCHTREE_H
00013 #define SEARCHTREE_H
00014
00015 #include <iostream>
00016 #include <fstream>
00017 #include <string>
00018 #include <vector>
00019
00020 #include <cstdio>
00021 #include <cstdlib>
00022 #include <cmath>
00023 #include <cassert>
00024
00025 #include "TreeNode.hh"
00026
00027 #define Inf 1e20
00028 using namespace std;
00029
00030
00031 class SearchTree
00033 {
00034
00035
00036
00037
00038 public:
00040 vector<TreeNode>* tree;
00042 int nbTimeSamp;
00044 int nbMTClusters;
00046 int *nbTimeLevels;
00048 int nbTotalLevels;
00050 int IndexminiCost;
00052 float miniCost;
00054 bool emptyTree;
00055
00056
00058 SearchTree(){
00059
00060 emptyTree=true;
00061
00062 }
00064 virtual~SearchTree(){
00065
00066 for (int i=0;i<nbTotalLevels;i++){
00067 tree[i].clear();
00068 }
00069
00070
00071 }
00073 void Init(int nbTimes, int nbMT,int *nbNodes1){
00074
00075 nbTimeSamp=nbTimes;
00076 nbMTClusters=nbMT;
00077 nbTimeLevels=new int[nbTimeSamp];
00078 nbTotalLevels=0;
00079 for (int time=0;time<nbTimeSamp;time++){
00080 nbTimeLevels[time]=nbNodes1[time];
00081 nbTotalLevels+=nbTimeLevels[time];
00082 }
00083 tree=new vector<TreeNode>[nbTotalLevels];
00084 emptyTree=false;
00085
00086 }
00088 bool CheckUnusedNode(int time, int currentLevel,int preIndex, int nodek2,int MTk2){
00089
00090 bool notUsedYet=true;
00091 int auxlevel=0;
00092 for (int i=0;i<time;i++){auxlevel+=nbTimeLevels[i];}
00093 while(currentLevel>auxlevel){
00094 currentLevel--;
00095 if (tree[currentLevel][preIndex].g2VertexIndex==nodek2&&tree[currentLevel][preIndex].g2MTIndex==MTk2){
00096 notUsedYet=false;
00097 }
00098 preIndex=tree[currentLevel][preIndex].branch;
00099 }
00100 return notUsedYet;
00101
00102 }
00104 bool CheckMTCoherentNode(int time, int currentLevel,int preIndex,int MTk1,int MTk2){
00105
00106 bool coherent=true;
00107 int auxlevel=0;
00108 for (int i=0;i<time-1;i++){auxlevel+=nbTimeLevels[i];}
00109 while(currentLevel>auxlevel){
00110 currentLevel--;
00111 if (tree[currentLevel][preIndex].g1MTIndex==MTk1){
00112 if (tree[currentLevel][preIndex].g2MTIndex!=MTk2)
00113 coherent=false;
00114 }
00115 if (tree[currentLevel][preIndex].g1MTIndex!=MTk1){
00116 if (tree[currentLevel][preIndex].g2MTIndex==MTk2)
00117 coherent=false;
00118 }
00119 preIndex=tree[currentLevel][preIndex].branch;
00120 }
00121 return coherent;
00122
00123 }
00125 int getPreTimeCorresNodeIndex(int time, int currentLevel,int preIndex,int nodek1, int MTk1){
00126
00127 int nodek2=-1;
00128 int timeaux=time;
00129 while(timeaux>time-1){
00130 currentLevel--;
00131 timeaux=tree[currentLevel][preIndex].timeLevel;
00132 if (timeaux==(time-1)){break;}
00133 else{preIndex=tree[currentLevel][preIndex].branch;}
00134 }
00135 while(timeaux==(time-1)&¤tLevel>=0){
00136 if (tree[currentLevel][preIndex].g1VertexIndex==nodek1&&tree[currentLevel][preIndex].g1MTIndex==MTk1){
00137 nodek2=tree[currentLevel][preIndex].g2VertexIndex;
00138 break;
00139 }
00140 else{
00141
00142 preIndex=tree[currentLevel][preIndex].branch;
00143 currentLevel--;
00144 timeaux=tree[currentLevel][preIndex].timeLevel;
00145 }
00146 }
00147
00148 return nodek2;
00149
00150 }
00152 int getPreTimeCorresMTIndex(int time, int currentLevel,int preIndex,int nodek1, int MTk1){
00153
00154 int MTindex=-1;
00155 int timeaux=time;
00156 while(timeaux>time-1){
00157 currentLevel--;
00158 timeaux=tree[currentLevel][preIndex].timeLevel;
00159 if (timeaux==(time-1)){break;}
00160 else{preIndex=tree[currentLevel][preIndex].branch;}
00161 }
00162 while(timeaux==(time-1)&¤tLevel>=0){
00163 if (tree[currentLevel][preIndex].g1VertexIndex==nodek1&&tree[currentLevel][preIndex].g1MTIndex==MTk1){
00164 MTindex=tree[currentLevel][preIndex].g2MTIndex;
00165 break;
00166 }
00167 else{
00168 preIndex=tree[currentLevel][preIndex].branch;
00169 currentLevel--;
00170 timeaux=tree[currentLevel][preIndex].timeLevel;
00171 }
00172 }
00173
00174 if (MTindex==-1){cout<<"Error occured in SearchTree.getPreTimeCorresMTIndex(...)"<<endl;}
00175 return MTindex;
00176
00177 }
00179 void AddNode(int time, int currentLevel, int preIndex,int nodek1,int MTk1,int nodek2,int MTk2,float cost,float weightMTinTLDiffCost,float TL1TL2DivCost,float flowDiffCost, float divDiffCost, float MIDiffCost, float divMTaMTbCost, float timeCost){
00180
00181 TreeNode auxtreeNode;
00182 auxtreeNode.timeLevel=time;
00183 auxtreeNode.g2VertexIndex=nodek2;
00184 auxtreeNode.g2MTIndex=MTk2;
00185 auxtreeNode.g1VertexIndex=nodek1;
00186 auxtreeNode.g1MTIndex=MTk1;
00187 auxtreeNode.branch=preIndex;
00188 auxtreeNode.nodeCost=cost;
00189 auxtreeNode.weightMTinTLDiffCost=weightMTinTLDiffCost;
00190 auxtreeNode.TL1TL2DivCost=TL1TL2DivCost;
00191 auxtreeNode.flowDiffCost=flowDiffCost;
00192 auxtreeNode.divDiffCost=divDiffCost;
00193 auxtreeNode.MIDiffCost=MIDiffCost;
00194 auxtreeNode.divMTaMTbCost=divMTaMTbCost;
00195 auxtreeNode.timeCost=timeCost;
00196
00197 tree[currentLevel].push_back(auxtreeNode);
00198
00199 }
00201 float LowestCosts(float * costs){
00202
00203 miniCost=Inf;
00204 IndexminiCost=-1;
00205 float currentCost;
00206 float *currentCosts= new float[7];
00207 int currentLevel;
00208 int preIndex;
00209 if (nbTotalLevels-1<=0){cout<<"empty graph ..."<<endl;}
00210
00211 for (int k=0;(unsigned int)k<tree[nbTotalLevels-1].size();k++){
00212 currentCost=0;for(int kCost=0;kCost<7;kCost++){currentCosts[kCost]=0;}
00213 currentCost+=tree[nbTotalLevels-1][k].nodeCost;
00214 currentCosts[0]+=tree[nbTotalLevels-1][k].weightMTinTLDiffCost;
00215 currentCosts[1]+=tree[nbTotalLevels-1][k].TL1TL2DivCost;
00216 currentCosts[2]+=tree[nbTotalLevels-1][k].flowDiffCost;
00217 currentCosts[3]+=tree[nbTotalLevels-1][k].divDiffCost;
00218 currentCosts[4]+=tree[nbTotalLevels-1][k].MIDiffCost;
00219 currentCosts[5]+=tree[nbTotalLevels-1][k].divMTaMTbCost;
00220 currentCosts[6]+=tree[nbTotalLevels-1][k].timeCost;
00221 currentLevel=nbTotalLevels-1;
00222 preIndex=k;
00223 while(currentLevel>0){
00224 preIndex=tree[currentLevel][preIndex].branch;
00225 currentLevel--;
00226 currentCost+=tree[currentLevel][preIndex].nodeCost;
00227 currentCosts[0]+=tree[currentLevel][preIndex].weightMTinTLDiffCost;
00228 currentCosts[1]+=tree[currentLevel][preIndex].TL1TL2DivCost;
00229 currentCosts[2]+=tree[currentLevel][preIndex].flowDiffCost;
00230 currentCosts[3]+=tree[currentLevel][preIndex].divDiffCost;
00231 currentCosts[4]+=tree[currentLevel][preIndex].MIDiffCost;
00232 currentCosts[5]+=tree[currentLevel][preIndex].divMTaMTbCost;
00233 currentCosts[6]+=tree[currentLevel][preIndex].timeCost;
00234 }
00235 if (currentCost<miniCost){
00236 miniCost=currentCost;
00237 for(int kCost=0;kCost<7;kCost++){costs[kCost]=currentCosts[kCost];}
00238 costs[7]=miniCost;
00239 IndexminiCost=k;
00240 }
00241 }
00242
00243
00244
00245 return miniCost;
00246 }
00248 float LowestCosts(float * costs, float* para){
00249
00250 miniCost=Inf;
00251 IndexminiCost=-1;
00252 float currentCost;
00253 float *currentCosts= new float[7];
00254 int currentLevel;
00255 int preIndex;
00256 if (nbTotalLevels-1<=0){cout<<"empty graph ..."<<endl;}
00257 for (int k=0;(unsigned int)k<tree[nbTotalLevels-1].size();k++){
00258 currentCost=0;for(int kCost=0;kCost<7;kCost++){currentCosts[kCost]=0;}
00259 tree[nbTotalLevels-1][k].nodeCost=tree[nbTotalLevels-1][k].weightMTinTLDiffCost*para[0];
00260 tree[nbTotalLevels-1][k].nodeCost+=tree[nbTotalLevels-1][k].TL1TL2DivCost*para[1];
00261 tree[nbTotalLevels-1][k].nodeCost+=tree[nbTotalLevels-1][k].flowDiffCost*para[2];
00262 tree[nbTotalLevels-1][k].nodeCost+=tree[nbTotalLevels-1][k].divDiffCost*para[3];
00263 tree[nbTotalLevels-1][k].nodeCost+=tree[nbTotalLevels-1][k].MIDiffCost*para[4];
00264 tree[nbTotalLevels-1][k].nodeCost+=tree[nbTotalLevels-1][k].divMTaMTbCost*para[5];
00265 tree[nbTotalLevels-1][k].nodeCost+=tree[nbTotalLevels-1][k].timeCost*para[6];
00266 currentCost+=tree[nbTotalLevels-1][k].nodeCost;
00267 currentCosts[0]+=tree[nbTotalLevels-1][k].weightMTinTLDiffCost;
00268 currentCosts[1]+=tree[nbTotalLevels-1][k].TL1TL2DivCost;
00269 currentCosts[2]+=tree[nbTotalLevels-1][k].flowDiffCost;
00270 currentCosts[3]+=tree[nbTotalLevels-1][k].divDiffCost;
00271 currentCosts[4]+=tree[nbTotalLevels-1][k].MIDiffCost;
00272 currentCosts[5]+=tree[nbTotalLevels-1][k].divMTaMTbCost;
00273 currentCosts[6]+=tree[nbTotalLevels-1][k].timeCost;
00274 currentLevel=nbTotalLevels-1;
00275 preIndex=k;
00276 while(currentLevel>0){
00277 preIndex=tree[currentLevel][preIndex].branch;
00278 currentLevel--;
00279 tree[currentLevel][preIndex].nodeCost=tree[currentLevel][preIndex].weightMTinTLDiffCost*para[0];
00280 tree[currentLevel][preIndex].nodeCost+=tree[currentLevel][preIndex].TL1TL2DivCost*para[1];
00281 tree[currentLevel][preIndex].nodeCost+=tree[currentLevel][preIndex].flowDiffCost*para[2];
00282 tree[currentLevel][preIndex].nodeCost+=tree[currentLevel][preIndex].divDiffCost*para[3];
00283 tree[currentLevel][preIndex].nodeCost+=tree[currentLevel][preIndex].MIDiffCost*para[4];
00284 tree[currentLevel][preIndex].nodeCost+=tree[currentLevel][preIndex].divMTaMTbCost*para[5];
00285 tree[currentLevel][preIndex].nodeCost+=tree[currentLevel][preIndex].timeCost*para[6];
00286 currentCost+=tree[currentLevel][preIndex].nodeCost;
00287 currentCosts[0]+=tree[currentLevel][preIndex].weightMTinTLDiffCost;
00288 currentCosts[1]+=tree[currentLevel][preIndex].TL1TL2DivCost;
00289 currentCosts[2]+=tree[currentLevel][preIndex].flowDiffCost;
00290 currentCosts[3]+=tree[currentLevel][preIndex].divDiffCost;
00291 currentCosts[4]+=tree[currentLevel][preIndex].MIDiffCost;
00292 currentCosts[5]+=tree[currentLevel][preIndex].divMTaMTbCost;
00293 currentCosts[6]+=tree[currentLevel][preIndex].timeCost;
00294 }
00295 if (currentCost<miniCost){
00296 miniCost=currentCost;
00297 for(int kCost=0;kCost<7;kCost++){costs[kCost]=currentCosts[kCost];}
00298 costs[7]=miniCost;
00299 IndexminiCost=k;
00300 }
00301 }
00302
00303
00304
00305 return miniCost;
00306 }
00308 void PruneTree(int nbMiniBranches, int currentLevel){
00309
00310
00311 int nb_branches=(int)tree[currentLevel].size();
00312 if (nb_branches>nbMiniBranches){
00313
00314
00315 int pruneLevel=currentLevel;
00316 int preIndex;
00317 float *brancheCost=new float[nb_branches];
00318 float *sortedBrancheCost=new float[nb_branches];
00319 float *prunedBranches=new float[nb_branches-nbMiniBranches];
00320 float *sortedPrunedBranches=new float[nb_branches-nbMiniBranches];
00321 for (int k=0;k<nb_branches;k++){
00322 brancheCost[k]=0;
00323 sortedBrancheCost[k]=-1;
00324 currentLevel=pruneLevel;
00325 brancheCost[k]+=tree[pruneLevel][k].nodeCost;
00326 preIndex=k;
00327 while(currentLevel>0){
00328 preIndex=tree[currentLevel][preIndex].branch;
00329 currentLevel--;
00330 brancheCost[k]+=tree[currentLevel][preIndex].nodeCost;
00331 }
00332 }
00333
00334 float miniCost;
00335 bool aux=true;
00336 for (int i=0;i<nb_branches;i++){
00337 miniCost=Inf;
00338 for (int k=0;k<nb_branches;k++){
00339 if (brancheCost[k]<miniCost){
00340 aux=true;
00341 for (int l=0;l<nb_branches;l++){if (sortedBrancheCost[l]==k){aux=false;}}
00342 if (aux){
00343 sortedBrancheCost[i]=k;
00344 miniCost=brancheCost[k];
00345 }
00346 }
00347 }
00348 }
00349
00350 for (int i=nbMiniBranches;i<nb_branches;i++){
00351 prunedBranches[i-nbMiniBranches]=sortedBrancheCost[i];
00352 sortedPrunedBranches[i-nbMiniBranches]=-1;
00353 }
00354 float maxiIndex;
00355 for (int i=0;i<nb_branches-nbMiniBranches;i++){
00356 maxiIndex=-Inf;
00357 for (int k=0;k<nb_branches-nbMiniBranches;k++){
00358 if (prunedBranches[k]>maxiIndex){
00359 aux=true;
00360 for (int l=0;l<nb_branches-nbMiniBranches;l++){if (sortedPrunedBranches[l]==prunedBranches[k]){aux=false;}}
00361 if (aux){
00362 sortedPrunedBranches[i]=prunedBranches[k];
00363 maxiIndex=prunedBranches[k];
00364 }
00365 }
00366 }
00367 }
00368
00369
00370 vector<TreeNode>::iterator currentIterator;
00371 for (int i=0;i<nb_branches-nbMiniBranches;i++){
00372 currentIterator = tree[pruneLevel].begin();
00373 int k=0;
00374 while(k<(int)sortedPrunedBranches[i]){currentIterator++;k++;}
00375 tree[pruneLevel].erase( currentIterator );
00376 }
00377
00378 delete [] brancheCost;
00379 delete [] sortedBrancheCost;
00380 delete [] prunedBranches;
00381 delete [] sortedPrunedBranches;
00382
00383 }
00384 }
00385
00386
00387 };
00388
00389 #endif
00390
00391
00392
00393
00394