SHOGUN
v2.0.0
|
00001 /* This program is free software: you can redistribute it and/or modify 00002 * it under the terms of the GNU General Public License as published by 00003 * the Free Software Foundation, either version 3 of the License, or 00004 * (at your option) any later version. 00005 * 00006 * This program is distributed in the hope that it will be useful, 00007 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00008 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00009 * GNU General Public License for more details. 00010 * 00011 * You should have received a copy of the GNU General Public License 00012 * along with this program. If not, see <http://www.gnu.org/licenses/>. 00013 * 00014 * Copyright (C) 2009 - 2012 Jun Liu and Jieping Ye 00015 */ 00016 00017 #ifndef SEQUENCE_SLEP 00018 #define SEQUENCE_SLEP 00019 00020 #include <stdlib.h> 00021 #include <stdio.h> 00022 #include <time.h> 00023 #include <math.h> 00024 00025 00026 /* 00027 * In this file, we propose the algorithms for solving the problem: 00028 * 00029 * min 1/2 \|x - u\|^2 00030 * s.t. x1 \ge x2 \ge x3 \ge ... \ge xn \ge 0 00031 * 00032 * 00033 */ 00034 00035 /* 00036 * 00037 * x= sequence_bottomup(u,n) 00038 * 00039 * we compute using a bottom up order 00040 * 00041 */ 00042 00043 void sequence_bottomup(double *x, double *u, int n){ 00044 int i, j; 00045 int *location=(int *)malloc(sizeof(int)*n); 00046 int num; 00047 00048 if(!location){ 00049 printf("\n Allocation of array failure!"); 00050 exit(1); 00051 } 00052 00053 00054 /* 00055 * compute the maximal mean from the root to the i-th point: 00056 * 00057 * x[i]: the maximal mean 00058 * location[i]: the ending index of the mean 00059 * 00060 */ 00061 00062 00063 /* process the last element*/ 00064 if (n<1){ 00065 printf("\n n=%d should be an integer over 1!",n); 00066 exit(1); 00067 } 00068 else{ 00069 i=n-1; 00070 x[i]=u[i]; 00071 location[i]=i; 00072 } 00073 00074 /*process the remaining elements in a bottom-up recursive manner*/ 00075 for(i=n-2;i>=0;i--){ 00076 00077 00078 if (u[i]>x[i+1]){ 00079 x[i]=u[i]; 00080 location[i]=i; 00081 } 00082 else{ 00083 /*make use of x[i: (n-1)] and location[i: (n-1)] for update*/ 00084 00085 /*merge with the first group*/ 00086 num=location[i+1]-i; 00087 x[i]=(u[i] + x[i+1]*num)/(num+1); 00088 location[i]=location[i+1]; 00089 j=location[i+1]+1; 00090 00091 /*If necessary, we need to further merge with the remainig groups */ 00092 for(;j<n;){ 00093 if(x[i] <= x[j]){ 00094 00095 num=location[j]-j +1; 00096 x[i]=( x[i]* (j-i) + x[j]* num ) / (location[j] -i +1); 00097 location[i]=location[j]; 00098 00099 j=location[j]+1; 00100 } 00101 else 00102 break; 00103 } 00104 } 00105 } 00106 00107 /* 00108 for(i=0;i<30;i++) 00109 printf("\n x[%d]=%2.5f, location[%d]=%d",i+1, x[i], i+1, location[i]+1); 00110 */ 00111 00112 /* 00113 * compute the solution x with the mean and location 00114 * 00115 */ 00116 00117 for(i=0;i<n;){ 00118 00119 if (x[i]>0){ 00120 for(j=i+1;j<=location[i];j++){ 00121 x[j]=x[i]; 00122 } 00123 00124 i=location[i]+1; 00125 } 00126 else{ 00127 for(j=i;j<n;j++) 00128 x[j]=0; 00129 break; 00130 } 00131 } 00132 00133 free(location); 00134 } 00135 00136 00137 /* 00138 * 00139 * x= sequence_topdown(u,n) 00140 * 00141 * we compute using a top to down order 00142 * 00143 */ 00144 00145 void sequence_topdown(double *x, double *u, int n){ 00146 int i, j; 00147 double sum, max, mean; 00148 int num; 00149 int *location=(int *)malloc(sizeof(int)*n); 00150 00151 00152 if(!location){ 00153 printf("\n Allocation of array failure!"); 00154 exit(1); 00155 } 00156 00157 for(i=0;i<n;){ 00158 00159 /* 00160 * From each root node i, we compute the maximal mean from. 00161 * 00162 */ 00163 00164 max=0; 00165 location[i]=i; 00166 00167 sum=0; 00168 num=1; 00169 for(j=i;j<n;j++){ 00170 sum+=u[j]; 00171 mean=sum/num; 00172 num++; 00173 00174 /* record the most largest mean and the location*/ 00175 if (mean >= max){ 00176 max=mean; 00177 location[i]=j; 00178 } 00179 } 00180 00181 if (max>0){ 00182 x[i]=max; /*record the maximal mean*/ 00183 i=location[i]+1; /*the next i*/ 00184 } 00185 else{ 00186 x[i]=-1; /* any value less or equal to 0 00187 * 00188 * This shows that the remaining elements should be zero 00189 * 00190 */ 00191 break; 00192 } 00193 } 00194 00195 00196 /* 00197 * compute the solution x with the mean and location 00198 * 00199 */ 00200 00201 for(i=0;i<n;){ 00202 00203 if (x[i]>0){ 00204 for(j=i+1;j<=location[i];j++){ 00205 x[j]=x[i]; 00206 } 00207 00208 i=location[i]+1; 00209 } 00210 else{ 00211 for(j=i;j<n;j++) 00212 x[j]=0; 00213 break; 00214 } 00215 } 00216 00217 free(location); 00218 } 00219 #endif /* ----- #ifndef SEQUENCE_SLEP ----- */ 00220