SHARE
TWEET

Untitled

a guest Oct 20th, 2019 99 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #include <math.h>
  5. #include <stdbool.h>
  6. #include "vptree.h"
  7. #define INT_MAX 2147483647
  8.  
  9. #ifndef VPTREE_H_INCLUDED
  10. #define VPTREE_H_INCLUDED
  11.  
  12.  
  13.  
  14. struct vptree{
  15.  
  16.     double *points;
  17.     int n; // number of points
  18.     int d; //dimensions
  19.     struct vptree *innerTree;
  20.     struct vptree *outerTree;
  21.     double median;
  22.     double * cooVP; //coordinates of vantage point
  23.     int indx;
  24.  
  25.     int *indexArray;//THELEI DOULEIA
  26.  
  27.  
  28. };
  29. //DATASET STRUCT
  30. struct helpStruct{
  31. double *dataSet;
  32. int dataLength;
  33. };
  34.  
  35.  
  36.  
  37. int isFather=5;
  38. struct helpStruct index;
  39.  
  40.  
  41.  
  42.  
  43. //DATASET
  44.  
  45. typedef struct vptree vptree;
  46. //PRWTOTUPA SUNARTHSEWN
  47.  vptree * buildvp(double * X,int n,int d);
  48.  vptree * getInner( vptree * T);
  49.  vptree * getOuter( vptree * T);
  50.  
  51. double getMD( vptree *T);
  52. double * getVP( vptree *T);
  53.  
  54. int getIDX( vptree *T);
  55.  
  56. int partition(double arr[], int l, int r);
  57. double kthSmallest(double arr[], int l, int r, int k);
  58. //PRWTOTUPA SUNARTHSEWN
  59. #endif // VPTREE_H_INCLUDED
  60.  
  61.  
  62.  
  63.  
  64.  
  65.  
  66.  
  67.  
  68.  
  69. int main()
  70. {
  71.     int n=5;//data
  72.     int d=3;//dimensions
  73.     int i,j;
  74.  
  75.     double  * dataArr=(double*)malloc(n*d*sizeof(double));
  76.  
  77.     for (i=0;i<n;i++){
  78.  
  79.             for(j=0;j<d;j++){
  80.                 *(dataArr+i*d+j)=rand()%100; //na to ftiaksw na epistrefei random double numbers
  81.                 printf("%f ---",*(dataArr+i*d+j));
  82.             }printf("\n");
  83.     }
  84.  vptree *one =( vptree*)malloc(100*sizeof( vptree));
  85. one=buildvp(dataArr,n,d);
  86.  
  87. //printf(" --%d root index %f ",one->innerTree->index,one->innerTree->cooVP[2] );
  88.  
  89.  
  90. }
  91.  
  92.  
  93.  
  94.  vptree * buildvp(double *X,int n,int d){
  95.      if(isFather==5){
  96.         index.dataSet=X;
  97.         index.dataLength=n;
  98.         isFather=0;
  99.         printf("\nGIA TON ISFATHER");
  100.      }
  101.     vptree * node=( vptree*)malloc(sizeof( vptree));
  102.  
  103.     node->d=d;
  104.     node->n=n;
  105.  
  106.     node->points=X;
  107.  
  108.     node->cooVP=getVP(node);
  109.  
  110.     node->median=getMD(node);
  111.  
  112.     node->innerTree=(vptree*)malloc(sizeof(vptree));
  113.     node->innerTree=getInner(node);
  114.     if(node->innerTree!=NULL)node->innerTree=buildvp(node->innerTree->points,node->innerTree->n,node->innerTree->d);
  115.  
  116.     node->outerTree=(vptree*)malloc(sizeof(vptree));
  117.     node->outerTree=getOuter(node);
  118.     if(node->outerTree!=NULL)node->outerTree=buildvp(node->outerTree->points,node->outerTree->n,node->outerTree->d);
  119.  
  120.     node->indx=getIDX(node);//den to exw valei akoma sth swsth seira
  121.  
  122.     return node;
  123.  
  124. };
  125.  
  126.  vptree * getInner( vptree * T){
  127.  
  128.    if(T->n>1){
  129.     vptree* inNode=( vptree*)malloc(sizeof( vptree));
  130.  
  131.    double coo[T->n][T->d];
  132.    int l;
  133.    int k;
  134.    for(l=0;l<(T->n);l++){
  135.         for(k=0;k<T->d;k++){
  136.             coo[l][k]=T->points[(T->d)*l+k];//einai swsto??? EINAI
  137.     }}
  138.     double* distance=(double*)malloc(((T->n)-1)*sizeof(double));
  139.     int i;
  140.     int j;
  141.     double sqrtValue;
  142.     for(i=0;i<(T->n)-1;i++){
  143.         sqrtValue=0;
  144.             for(j=0;j<(T->d);j++){
  145.                 sqrtValue+=(coo[i][j]-coo[(T->n)-1][j])*(coo[i][j]-coo[(T->n)-1][j]);
  146.  
  147.             }
  148.         distance[i]=sqrt(sqrtValue);}
  149.  
  150.         //------------------------------PANW GINETAI O UPOLOGISMOS DISTANCE
  151.  
  152.  
  153.         int w,h;
  154.         int z=0;
  155.         int indexCounter=0;
  156.         for(w=0;w<(T->n)-1;w++){
  157.                 if(distance[w]<T->median)indexCounter++;
  158.           }
  159.  
  160.  
  161.         inNode->points=(double*)malloc((indexCounter*T->d)*sizeof(double));
  162.         for(w=0;w<(T->n)-1;w++){
  163.                 if(distance[w]<T->median){
  164.  
  165.                     for(h=0;h<T->d;h++){
  166.                   inNode->points[(T->d)*z+h]=coo[w][h];}//vazei tis katallhles suntetagmenes ston points tou inner
  167.                   z++;
  168.                }
  169.           }
  170.         inNode->n=z;
  171.         inNode->d=T->d;
  172.  
  173. return inNode;
  174.    }
  175.    else //printf("\n  ---->  ",T->index, T->cooVP[0]);
  176. return NULL;
  177. };
  178.  vptree * getOuter( vptree * T){
  179.     if(T->n>1){
  180.     vptree* outNode=( vptree*)malloc(sizeof( vptree));
  181.  
  182.    double coo[T->n][T->d];
  183.    int l;
  184.    int k;
  185.    for(l=0;l<(T->n);l++){
  186.         for(k=0;k<T->d;k++){
  187.             coo[l][k]=T->points[(T->d)*l+k];//einai swsto??? EINAI
  188.     }}
  189.     double* distance=(double*)malloc(((T->n)-1)*sizeof(double));
  190.     int i;
  191.     int j;
  192.     double sqrtValue;
  193.     for(i=0;i<(T->n)-1;i++){
  194.         sqrtValue=0;
  195.             for(j=0;j<(T->d);j++){
  196.                 sqrtValue+=(coo[i][j]-coo[(T->n)-1][j])*(coo[i][j]-coo[(T->n)-1][j]);
  197.  
  198.             }
  199.         distance[i]=sqrt(sqrtValue);}
  200.  
  201.         //------------------------------PANW GINETAI O UPOLOGISMOS DISTANCE
  202.  
  203.  
  204.         int w,h;
  205.         int z=0;
  206.         int indexCounter=0;
  207.         for(w=0;w<(T->n)-1;w++){
  208.                 if(distance[w]>=T->median)indexCounter++;
  209.           }
  210.  
  211.  
  212.         outNode->points=(double*)malloc((indexCounter*T->d)*sizeof(double));
  213.         for(w=0;w<(T->n)-1;w++){
  214.                 if(distance[w]>=T->median){
  215.  
  216.                     for(h=0;h<T->d;h++){
  217.                   outNode->points[(T->d)*z+h]=coo[w][h];}//vazei tis katallhles suntetagmenes ston points tou inner
  218.                   z++;
  219.                }
  220.           }
  221.         outNode->n=z;
  222.         outNode->d=T->d;
  223.  
  224. return outNode;
  225.    }
  226.    else //printf("\n  ---->  ",T->index, T->cooVP[0]);
  227. return NULL;
  228.  
  229. };
  230.  
  231. double getMD( vptree *T){
  232.     double* distance=(double*)malloc(((T->n)-1)*sizeof(double));
  233.  
  234.     double coo[T->n][T->d]; //periexei oles tis suntetagmenes olwn twn stoixeiwn
  235.     double sqrtValue=0;
  236.  
  237.     int i;
  238.     int k;
  239.     int j;
  240.     int l;
  241.  
  242.     for(l=0;l<(T->n);l++){
  243.         for(k=0;k<T->d;k++){
  244.             coo[l][k]=T->points[(T->d)*l+k];//einai swsto????
  245.     }}
  246.  
  247.     for(i=0;i<(T->n)-1;i++){
  248.         sqrtValue=0;
  249.             for(j=0;j<(T->d);j++){
  250.                 sqrtValue+=(coo[i][j]-coo[(T->n)-1][j])*(coo[i][j]-coo[(T->n)-1][j]);
  251.  
  252.             }
  253.         distance[i]=sqrt(sqrtValue);}
  254.  
  255. return kthSmallest(distance,0,(T->n)-2,((T->n)-1)/2);
  256. };
  257.  
  258. double * getVP( vptree *T){//epistrefei gia to vptree T to vantage point pou tha xrhsimopoihthei
  259.     int j; // metavlhtes gia na prospelasw thn for
  260.  
  261.     int n=T->n;//krataw diastaseis tou pinaka twn point tou T gia na paiksw sth for apo katv
  262.     int d=T->d;//ta dia me panw
  263.  
  264.     double* arrayVP=(double*)malloc(d*sizeof(double));// o vector poy tha epistrafei kai periexei coordinates tou VP
  265.  
  266.         for(j=0;j<d;j++){
  267.             arrayVP[j]=(*(T->points+(n-1)*d+j));
  268.         }
  269.  
  270. return arrayVP;
  271. };
  272.  
  273. int getIDX( vptree *T){//nomizw me afton ton tropo epistrefw amesws ton deikth tou teleftaiou stoixeiou
  274.     int k;
  275.     int l;
  276.  
  277.     vptree* outNode=( vptree*)malloc(sizeof( vptree));
  278.  
  279.    double coo[index.dataLength][T->d];
  280.  
  281.    for(l=0;l<index.dataLength;l++){
  282.         for(k=0;k<T->d;k++){
  283.             coo[l][k]=index.dataSet[(T->d)*l+k];//einai swsto??? EINAI
  284.     }}
  285.     double* distance=(double*)malloc((index.dataLength)*sizeof(double));
  286.     int i;
  287.     int j,m;
  288.     double sqrtValue;
  289.     for(i=0;i<index.dataLength;i++){
  290.         sqrtValue=0;
  291.             for(j=0;j<(T->d);j++){
  292.                 sqrtValue+=(coo[i][j]-T->cooVP[j])*(coo[i][j]-T->cooVP[j]);
  293.  
  294.             }
  295.         distance[i]=sqrt(sqrtValue);
  296.  
  297.         }
  298.  
  299.  
  300.     for(m=0;m<index.dataLength;m++){if(distance[m]==0)return m;}
  301.  
  302.     printf("h index exei themaaaaaaa");
  303.     return 0;
  304.  
  305. };
  306.  
  307. int partition(double arr[], int l, int r)
  308. {   double temp;
  309.     double x = arr[r];
  310.     int i = l;
  311.     int j;
  312.     for (j = l; j <= r - 1; j++) {
  313.         if (arr[j] <= x) {
  314.             temp=arr[i];
  315.             arr[i]=arr[j];
  316.             arr[j]=temp;
  317.  
  318.             i++;
  319.         }
  320.     }
  321.     temp=arr[i];
  322.     arr[i]=arr[r];
  323.     arr[r]=temp;
  324.  
  325.     return i;
  326. };
  327.  
  328. double kthSmallest(double arr[], int l, int r, int k)
  329. {
  330.     if (k > 0 && k <= r - l + 1) {
  331.         int index = partition(arr, l, r);
  332.         if (index - l == k - 1)
  333.             return arr[index];
  334.         if (index - l > k - 1)
  335.             return kthSmallest(arr, l, index - 1, k);
  336.  
  337.         return kthSmallest(arr, index + 1, r,
  338.                             k - index + l - 1);
  339.     }
  340.     return INT_MAX;
  341. };
  342.  
  343. //Ara kathe vptree stoixeio tha periexei mesa to VP tou (dhladh tha mas leei poio VP einai sa node) to index tou node aftou ston megalo pinaka kai to aristero kai deksi tree
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top