Main Page   Compound List   File List   Compound Members   File Members   Related Pages  

SearchTree.hh

Go to the documentation of this file.
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 /*******************SearchTree class***********************/
00031 /**********************************************************/  class SearchTree 
00033 {
00034  
00035   
00036    /***************ATTRIBUTES****************************/
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   /***************METHODES****************************/
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                 //delete [] tree;
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];}//checking coherence only in the current and past time sample
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)&&currentLevel>=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                 //if (nodek2==-1){cout<<"linked to extra node"<<endl;}
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)&&currentLevel>=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                 //cout<<"number of leaves in the SearchTree : "<<tree[nbTotalLevels-1].size()<<endl;
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                 //calculating branches cost
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                 //sorting
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                 //sorting the branches to be pruned in index order (for the vector.erase() procedure in the pruning)  
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                 //pruning
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 

Generated on Thu Feb 17 11:03:19 2005 for Interactive Learning of Sub-Graphs Semantics by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002