| 1 | /* |
|---|
| 2 | * triproc.c Adachi, J. 1995.09.22 |
|---|
| 3 | * Copyright (C) 1993-1995 J. Adachi & M. Hasegawa. All rights reserved. |
|---|
| 4 | */ |
|---|
| 5 | |
|---|
| 6 | #define PAIR |
|---|
| 7 | |
|---|
| 8 | #include "tridist.h" |
|---|
| 9 | |
|---|
| 10 | |
|---|
| 11 | void |
|---|
| 12 | redistmat(distan, psotu, underotu, i, j, ip, jp) |
|---|
| 13 | dmatrix distan; |
|---|
| 14 | Node **psotu; |
|---|
| 15 | ivector underotu; |
|---|
| 16 | int i, j; |
|---|
| 17 | Node *ip, *jp; |
|---|
| 18 | { |
|---|
| 19 | int k; |
|---|
| 20 | double dis; |
|---|
| 21 | |
|---|
| 22 | for (k = 0; k < Numspc; k++) { |
|---|
| 23 | if (psotu[k] != NULL) { |
|---|
| 24 | #if 1 |
|---|
| 25 | dis = ( distan[i][k] + distan[j][k] ) * 0.5; |
|---|
| 26 | #else |
|---|
| 27 | dis = ( distan[i][k] * underotus[i] |
|---|
| 28 | + distan[j][k] * underotus[j] ) |
|---|
| 29 | / (underotus[i] + underotus[j]); |
|---|
| 30 | #endif |
|---|
| 31 | distan[i][k] = dis; |
|---|
| 32 | distan[k][i] = dis; |
|---|
| 33 | } |
|---|
| 34 | distan[j][k] = 0.0; |
|---|
| 35 | distan[k][j] = 0.0; |
|---|
| 36 | } |
|---|
| 37 | } /* redistmat */ |
|---|
| 38 | |
|---|
| 39 | |
|---|
| 40 | triadmat(brnchmat, brnchvari, distan, psotu, numspc, nsp2) |
|---|
| 41 | dmatrix brnchmat; |
|---|
| 42 | dmatrix brnchvari; |
|---|
| 43 | dmatrix distan; |
|---|
| 44 | Node **psotu; |
|---|
| 45 | int numspc, nsp2; |
|---|
| 46 | { |
|---|
| 47 | int i, j, k; |
|---|
| 48 | double disij, disik, disjk, brni, brnj, brnk; |
|---|
| 49 | |
|---|
| 50 | for (i = 0; i < numspc; i++) { |
|---|
| 51 | for (j = 0; j < numspc; j++) { |
|---|
| 52 | brnchmat[i][j] = 0.0; |
|---|
| 53 | brnchvari[i][j] = 0.0; |
|---|
| 54 | } |
|---|
| 55 | } |
|---|
| 56 | for (i = 0; i < numspc - 2; i++) { |
|---|
| 57 | if (psotu[i] != NULL) { |
|---|
| 58 | for (j = i + 1; j < numspc - 1; j++) { |
|---|
| 59 | if (psotu[j] != NULL) { |
|---|
| 60 | disij = distan[i][j]; |
|---|
| 61 | for (k = j + 1; k < numspc; k++) { |
|---|
| 62 | if (psotu[k] != NULL) { |
|---|
| 63 | disik = distan[i][k]; |
|---|
| 64 | disjk = distan[j][k]; |
|---|
| 65 | brni = (disij + disik - disjk) * 0.5; |
|---|
| 66 | brnj = disij - brni; |
|---|
| 67 | brnk = disik - brni; |
|---|
| 68 | brnchmat[i][j] += brni; |
|---|
| 69 | brnchmat[i][k] += brni; |
|---|
| 70 | brnchmat[j][k] += brnj; |
|---|
| 71 | brnchmat[j][i] += brnj; |
|---|
| 72 | brnchmat[k][i] += brnk; |
|---|
| 73 | brnchmat[k][j] += brnk; |
|---|
| 74 | } |
|---|
| 75 | } |
|---|
| 76 | } |
|---|
| 77 | } |
|---|
| 78 | } |
|---|
| 79 | } |
|---|
| 80 | for (i = 0; i < numspc; i++) { |
|---|
| 81 | for (j = 0; j < numspc; j++) brnchmat[i][j] /= nsp2; |
|---|
| 82 | } |
|---|
| 83 | |
|---|
| 84 | for (i = 0; i < numspc - 2; i++) { |
|---|
| 85 | if (psotu[i] != NULL) { |
|---|
| 86 | for (j = i + 1; j < numspc - 1; j++) { |
|---|
| 87 | if (psotu[j] != NULL) { |
|---|
| 88 | disij = distan[i][j]; |
|---|
| 89 | for (k = j + 1; k < numspc; k++) { |
|---|
| 90 | if (psotu[k] != NULL) { |
|---|
| 91 | disik = distan[i][k]; |
|---|
| 92 | disjk = distan[j][k]; |
|---|
| 93 | brni = (disij + disik - disjk) * 0.5; |
|---|
| 94 | brnj = disij - brni; |
|---|
| 95 | brnk = disik - brni; |
|---|
| 96 | brnchvari[i][j] += |
|---|
| 97 | (brnchmat[i][j]-brni)*(brnchmat[i][j]-brni); |
|---|
| 98 | brnchvari[i][k] += |
|---|
| 99 | (brnchmat[i][k]-brni)*(brnchmat[i][k]-brni); |
|---|
| 100 | brnchvari[j][k] += |
|---|
| 101 | (brnchmat[j][k]-brnj)*(brnchmat[j][k]-brnj); |
|---|
| 102 | brnchvari[j][i] += |
|---|
| 103 | (brnchmat[j][i]-brnj)*(brnchmat[j][i]-brnj); |
|---|
| 104 | brnchvari[k][i] += |
|---|
| 105 | (brnchmat[k][i]-brnk)*(brnchmat[k][i]-brnk); |
|---|
| 106 | brnchvari[k][j] += |
|---|
| 107 | (brnchmat[k][j]-brnk)*(brnchmat[k][j]-brnk); |
|---|
| 108 | } |
|---|
| 109 | } |
|---|
| 110 | } |
|---|
| 111 | } |
|---|
| 112 | } |
|---|
| 113 | } |
|---|
| 114 | for (i = 0; i < numspc; i++) { |
|---|
| 115 | for (j = 0; j < numspc; j++) brnchvari[i][j] = sqrt(brnchvari[i][j]); |
|---|
| 116 | } |
|---|
| 117 | } /* triadmat */ |
|---|
| 118 | |
|---|
| 119 | |
|---|
| 120 | triadmat2(brnchmat, brnchvari, distan, psotu, underotus, masterotu, numspc) |
|---|
| 121 | dmatrix brnchmat; |
|---|
| 122 | dmatrix brnchvari; |
|---|
| 123 | dmatrix distan; |
|---|
| 124 | Node **psotu; |
|---|
| 125 | ivector underotus; |
|---|
| 126 | ivector masterotu; |
|---|
| 127 | { |
|---|
| 128 | int i, j, k, ii, jj, kk; |
|---|
| 129 | double disij, disik, disjk, brni, brnj, brnk; |
|---|
| 130 | |
|---|
| 131 | for (i = 0; i < numspc; i++) { |
|---|
| 132 | for (j = 0; j < numspc; j++) { |
|---|
| 133 | brnchmat[i][j] = 0.0; |
|---|
| 134 | brnchvari[i][j] = 0.0; |
|---|
| 135 | } |
|---|
| 136 | } |
|---|
| 137 | for (i = 0; i < numspc - 2; i++) { |
|---|
| 138 | ii = masterotu[i]; |
|---|
| 139 | for (j = i + 1; j < numspc - 1; j++) { |
|---|
| 140 | jj = masterotu[j]; |
|---|
| 141 | if (jj != ii) { |
|---|
| 142 | disij = distan[i][j]; |
|---|
| 143 | for (k = j + 1; k < numspc; k++) { |
|---|
| 144 | kk = masterotu[k]; |
|---|
| 145 | if ((kk != jj) && (kk != ii)) { |
|---|
| 146 | disik = distan[i][k]; |
|---|
| 147 | disjk = distan[j][k]; |
|---|
| 148 | brni = (disij + disik - disjk) * 0.5; |
|---|
| 149 | brnj = disij - brni; |
|---|
| 150 | brnk = disik - brni; |
|---|
| 151 | brnchmat[i][jj] += brni; |
|---|
| 152 | brnchmat[i][kk] += brni; |
|---|
| 153 | brnchmat[j][kk] += brnj; |
|---|
| 154 | brnchmat[j][ii] += brnj; |
|---|
| 155 | brnchmat[k][ii] += brnk; |
|---|
| 156 | brnchmat[k][jj] += brnk; |
|---|
| 157 | } |
|---|
| 158 | } |
|---|
| 159 | } |
|---|
| 160 | } |
|---|
| 161 | } |
|---|
| 162 | for (i = 0; i < numspc; i++) { |
|---|
| 163 | ii = underotus[i]; |
|---|
| 164 | for (j = 0; j < numspc; j++) { |
|---|
| 165 | if (psotu[j] != NULL) { |
|---|
| 166 | jj = underotus[j]; |
|---|
| 167 | brnchmat[i][j] /= ((numspc - ii - jj) * jj); |
|---|
| 168 | } |
|---|
| 169 | } |
|---|
| 170 | } |
|---|
| 171 | |
|---|
| 172 | for (i = 0; i < numspc - 2; i++) { |
|---|
| 173 | ii = masterotu[i]; |
|---|
| 174 | for (j = i + 1; j < numspc - 1; j++) { |
|---|
| 175 | jj = masterotu[j]; |
|---|
| 176 | if (jj != ii) { |
|---|
| 177 | disij = distan[i][j]; |
|---|
| 178 | for (k = j + 1; k < numspc; k++) { |
|---|
| 179 | kk = masterotu[k]; |
|---|
| 180 | if ((kk != jj) && (kk != ii)) { |
|---|
| 181 | disik = distan[i][k]; |
|---|
| 182 | disjk = distan[j][k]; |
|---|
| 183 | brni = (disij + disik - disjk) * 0.5; |
|---|
| 184 | brnj = disij - brni; |
|---|
| 185 | brnk = disik - brni; |
|---|
| 186 | brnchvari[i][j] += |
|---|
| 187 | (brnchmat[i][j]-brni)*(brnchmat[i][j]-brni); |
|---|
| 188 | brnchvari[i][k] += |
|---|
| 189 | (brnchmat[i][k]-brni)*(brnchmat[i][k]-brni); |
|---|
| 190 | brnchvari[j][k] += |
|---|
| 191 | (brnchmat[j][k]-brnj)*(brnchmat[j][k]-brnj); |
|---|
| 192 | brnchvari[j][i] += |
|---|
| 193 | (brnchmat[j][i]-brnj)*(brnchmat[j][i]-brnj); |
|---|
| 194 | brnchvari[k][i] += |
|---|
| 195 | (brnchmat[k][i]-brnk)*(brnchmat[k][i]-brnk); |
|---|
| 196 | brnchvari[k][j] += |
|---|
| 197 | (brnchmat[k][j]-brnk)*(brnchmat[k][j]-brnk); |
|---|
| 198 | } |
|---|
| 199 | } |
|---|
| 200 | } |
|---|
| 201 | } |
|---|
| 202 | } |
|---|
| 203 | for (i = 0; i < numspc; i++) { |
|---|
| 204 | ii = underotus[i]; |
|---|
| 205 | for (j = 0; j < numspc; j++) { |
|---|
| 206 | jj = underotus[j]; |
|---|
| 207 | brnchvari[i][j] /= (numspc - ii - jj); |
|---|
| 208 | brnchvari[i][j] = sqrt(brnchvari[i][j]); |
|---|
| 209 | } |
|---|
| 210 | } |
|---|
| 211 | } /* triadmat2 */ |
|---|
| 212 | |
|---|
| 213 | |
|---|
| 214 | void |
|---|
| 215 | minpair(brnchmat, brnchvari, brndiff, brndiff2, minbrnch, minbrnch2, psotu, numspc) |
|---|
| 216 | dmatrix brnchmat; |
|---|
| 217 | dmatrix brnchvari; |
|---|
| 218 | dvector brndiff; |
|---|
| 219 | dvector brndiff2; |
|---|
| 220 | ivector minbrnch; |
|---|
| 221 | ivector minbrnch2; |
|---|
| 222 | Node **psotu; |
|---|
| 223 | int numspc; |
|---|
| 224 | { |
|---|
| 225 | int i, j, k, minj, minj2, minv, minv2; |
|---|
| 226 | double brni, minbrn, minbrn2, temp, vari, minvari, minvari2; |
|---|
| 227 | |
|---|
| 228 | for (i = 0; i < numspc; i++) { |
|---|
| 229 | if (psotu[i] != NULL) { |
|---|
| 230 | minj = minj2 = -1; |
|---|
| 231 | minbrn = minbrn2 = UPPERLIMIT; |
|---|
| 232 | minv = minv2 = -1; |
|---|
| 233 | minvari = minvari2 = UPPERLIMIT; |
|---|
| 234 | for (j = 0; j < numspc; j++) { |
|---|
| 235 | if (psotu[j] != NULL && j != i) { |
|---|
| 236 | brni = brnchmat[i][j]; |
|---|
| 237 | if (brni < minbrn2) { |
|---|
| 238 | if (brni < minbrn) { |
|---|
| 239 | minj2 = minj; |
|---|
| 240 | minbrn2 = minbrn; |
|---|
| 241 | } else { |
|---|
| 242 | minj2 = j; |
|---|
| 243 | minbrn2 = brni; |
|---|
| 244 | } |
|---|
| 245 | } |
|---|
| 246 | if (brni < minbrn) { |
|---|
| 247 | minj = j; |
|---|
| 248 | minbrn = brni; |
|---|
| 249 | } |
|---|
| 250 | |
|---|
| 251 | vari = brnchvari[i][j]; |
|---|
| 252 | if (vari < minvari2) { |
|---|
| 253 | if (vari < minvari) { |
|---|
| 254 | minv2 = minv; |
|---|
| 255 | minvari2 = minvari; |
|---|
| 256 | } else { |
|---|
| 257 | minv2 = j; |
|---|
| 258 | minvari2 = vari; |
|---|
| 259 | } |
|---|
| 260 | } |
|---|
| 261 | if (vari < minvari) { |
|---|
| 262 | minv = j; |
|---|
| 263 | minvari = vari; |
|---|
| 264 | } |
|---|
| 265 | } |
|---|
| 266 | } |
|---|
| 267 | #if 0 |
|---|
| 268 | brndiff[i] = minbrn2 - minbrn; /* !? */ |
|---|
| 269 | #endif |
|---|
| 270 | #if 1 |
|---|
| 271 | brndiff[i] = ( minbrn2 - minbrn ) / minbrn; /* !? */ |
|---|
| 272 | #endif |
|---|
| 273 | minbrnch[i] = minj; |
|---|
| 274 | |
|---|
| 275 | /* brndiff2[i] = minvari2 - minvari; */ |
|---|
| 276 | brndiff2[i] = minvari; |
|---|
| 277 | minbrnch2[i] = minv; |
|---|
| 278 | } |
|---|
| 279 | } |
|---|
| 280 | } /* minpair */ |
|---|
| 281 | |
|---|
| 282 | |
|---|
| 283 | void |
|---|
| 284 | minpair2(brnchmat, brnchvari, brndiff, brndiff2, minbrnch, minbrnch2, psotu, masterotu) |
|---|
| 285 | dmatrix brnchmat; |
|---|
| 286 | dmatrix brnchvari; |
|---|
| 287 | dvector brndiff; |
|---|
| 288 | dvector brndiff2; |
|---|
| 289 | ivector minbrnch; |
|---|
| 290 | ivector minbrnch2; |
|---|
| 291 | Node **psotu; |
|---|
| 292 | ivector masterotu; |
|---|
| 293 | { |
|---|
| 294 | int i, j, k, ii, jj, kk, minj, minj2, minv, minv2; |
|---|
| 295 | double brni, minbrn, minbrn2, temp, vari, minvari, minvari2; |
|---|
| 296 | |
|---|
| 297 | for (i = 0; i < Numspc; i++) { |
|---|
| 298 | ii = masterotu[i]; |
|---|
| 299 | minj = minj2 = -1; |
|---|
| 300 | minbrn = minbrn2 = UPPERLIMIT; |
|---|
| 301 | for (j = 0; j < Numspc; j++) { |
|---|
| 302 | jj = masterotu[j]; |
|---|
| 303 | if (psotu[j] != NULL && jj != ii) { |
|---|
| 304 | brni = brnchmat[i][j]; |
|---|
| 305 | if (brni < minbrn2) { |
|---|
| 306 | if (brni < minbrn) { |
|---|
| 307 | minj2 = minj; |
|---|
| 308 | minbrn2 = minbrn; |
|---|
| 309 | } else { |
|---|
| 310 | minj2 = j; |
|---|
| 311 | minbrn2 = brni; |
|---|
| 312 | } |
|---|
| 313 | } |
|---|
| 314 | if (brni < minbrn) { |
|---|
| 315 | minj = j; |
|---|
| 316 | minbrn = brni; |
|---|
| 317 | } |
|---|
| 318 | } |
|---|
| 319 | } |
|---|
| 320 | for (j = 0; j < Numspc; j++) { |
|---|
| 321 | jj = masterotu[j]; |
|---|
| 322 | if (psotu[j] != NULL && jj != ii) { |
|---|
| 323 | } |
|---|
| 324 | } |
|---|
| 325 | #if 0 |
|---|
| 326 | brndiff[i] = minbrn2 - minbrn; /* !? */ |
|---|
| 327 | #endif |
|---|
| 328 | #if 1 |
|---|
| 329 | brndiff[i] = ( minbrn2 - minbrn ) / minbrn; /* !? */ |
|---|
| 330 | #endif |
|---|
| 331 | minbrnch[i] = masterotu[minj]; |
|---|
| 332 | |
|---|
| 333 | brndiff2[i] = 0.0; |
|---|
| 334 | minbrnch2[i] = masterotu[minj]; |
|---|
| 335 | } |
|---|
| 336 | } /* minpair2 */ |
|---|
| 337 | |
|---|
| 338 | |
|---|
| 339 | void |
|---|
| 340 | prbrnmat(distanmat, minbrnch, underotus, psotu, identif, numspc) |
|---|
| 341 | dmatrix distanmat; |
|---|
| 342 | ivector minbrnch, underotus; |
|---|
| 343 | Node **psotu; |
|---|
| 344 | char **identif; |
|---|
| 345 | int numspc; |
|---|
| 346 | { |
|---|
| 347 | int i, j, k, n, m; |
|---|
| 348 | |
|---|
| 349 | for (k = 0; k < numspc; k = m) { |
|---|
| 350 | fputs("\n ", stdout); |
|---|
| 351 | for ( n = 0, j = k; n < 10 && j < numspc; j++) { |
|---|
| 352 | if (psotu[j] != NULL) { |
|---|
| 353 | printf("%7.5s", identif[j]); |
|---|
| 354 | n++; |
|---|
| 355 | } |
|---|
| 356 | } |
|---|
| 357 | m = j; |
|---|
| 358 | putchar('\n'); |
|---|
| 359 | for (i = 0; i < numspc; i++) { |
|---|
| 360 | if (psotu[i] != NULL) { |
|---|
| 361 | printf("%-5.5s", identif[i]); |
|---|
| 362 | printf("%3d", underotus[i]); |
|---|
| 363 | for (j = k; j < m && j < numspc; j++) { |
|---|
| 364 | if (psotu[j] != NULL) { |
|---|
| 365 | if (i == j) |
|---|
| 366 | printf("%7.5s", identif[i]); |
|---|
| 367 | else if (psotu[i] == NULL || psotu[j] == NULL) |
|---|
| 368 | printf("%7s", ""); |
|---|
| 369 | #if 0 |
|---|
| 370 | else if (minbrnch[j] == i) |
|---|
| 371 | printf("%+7.2f", distanmat[j][i]); |
|---|
| 372 | else |
|---|
| 373 | printf("%7.2f", distanmat[j][i]); |
|---|
| 374 | #else |
|---|
| 375 | else |
|---|
| 376 | printf("%7.2f", distanmat[j][i] |
|---|
| 377 | - distanmat[j][minbrnch[j]]); |
|---|
| 378 | #endif |
|---|
| 379 | } |
|---|
| 380 | } |
|---|
| 381 | printf("\n"); |
|---|
| 382 | } |
|---|
| 383 | } |
|---|
| 384 | } |
|---|
| 385 | } /* prbrnmat */ |
|---|
| 386 | |
|---|
| 387 | |
|---|
| 388 | void |
|---|
| 389 | prbrnmat2(distanmat, minbrnch, underotus, psotu, identif, numspc) |
|---|
| 390 | dmatrix distanmat; |
|---|
| 391 | ivector minbrnch, underotus; |
|---|
| 392 | Node **psotu; |
|---|
| 393 | char **identif; |
|---|
| 394 | int numspc; |
|---|
| 395 | { |
|---|
| 396 | int i, j, k, n, m; |
|---|
| 397 | |
|---|
| 398 | for (k = 0; k < numspc; k = m) { |
|---|
| 399 | fputs("\n ", stdout); |
|---|
| 400 | for ( n = 0, j = k; n < 10 && j < numspc; j++) { |
|---|
| 401 | if (1) { |
|---|
| 402 | printf("%7.5s", identif[j]); |
|---|
| 403 | n++; |
|---|
| 404 | } |
|---|
| 405 | } |
|---|
| 406 | m = j; |
|---|
| 407 | putchar('\n'); |
|---|
| 408 | for (i = 0; i < numspc; i++) { |
|---|
| 409 | if (psotu[i] != NULL) { |
|---|
| 410 | printf("%-5.5s", identif[i]); |
|---|
| 411 | printf("%3d", underotus[i]); |
|---|
| 412 | for (j = k; j < m && j < numspc; j++) { |
|---|
| 413 | if (1) { |
|---|
| 414 | if (i == j) |
|---|
| 415 | printf("%7.5s", identif[i]); |
|---|
| 416 | else if (distanmat[j][i] == 0.0) |
|---|
| 417 | printf("%7s", ""); |
|---|
| 418 | #if 0 |
|---|
| 419 | else if (minbrnch[j] == i) |
|---|
| 420 | printf("%+7.2f", distanmat[j][i]); |
|---|
| 421 | else |
|---|
| 422 | printf("%7.2f", distanmat[j][i]); |
|---|
| 423 | #else |
|---|
| 424 | else |
|---|
| 425 | printf("%7.2f", distanmat[j][i] |
|---|
| 426 | - distanmat[j][minbrnch[j]]); |
|---|
| 427 | #endif |
|---|
| 428 | } |
|---|
| 429 | } |
|---|
| 430 | printf("\n"); |
|---|
| 431 | } |
|---|
| 432 | } |
|---|
| 433 | } |
|---|
| 434 | } /* prbrnmat2 */ |
|---|
| 435 | |
|---|
| 436 | |
|---|
| 437 | void |
|---|
| 438 | prbrnvari(distanvari, minbrnch2, underotus, psotu, identif, numspc) |
|---|
| 439 | dmatrix distanvari; |
|---|
| 440 | ivector minbrnch2, underotus; |
|---|
| 441 | Node **psotu; |
|---|
| 442 | char **identif; |
|---|
| 443 | int numspc; |
|---|
| 444 | { |
|---|
| 445 | int i, j, k, n, m; |
|---|
| 446 | |
|---|
| 447 | for (k = 0; k < numspc; k = m) { |
|---|
| 448 | fputs("\n ", stdout); |
|---|
| 449 | for ( n = 0, j = k; n < 10 && j < numspc; j++) { |
|---|
| 450 | if (psotu[j] != NULL) { |
|---|
| 451 | printf("%7.5s", identif[j]); |
|---|
| 452 | n++; |
|---|
| 453 | } |
|---|
| 454 | } |
|---|
| 455 | m = j; |
|---|
| 456 | putchar('\n'); |
|---|
| 457 | for (i = 0; i < numspc; i++) { |
|---|
| 458 | if (psotu[i] != NULL) { |
|---|
| 459 | printf("%-5.5s", identif[i]); |
|---|
| 460 | printf("%3d", underotus[i]); |
|---|
| 461 | for (j = k; j < m && j < numspc; j++) { |
|---|
| 462 | if (psotu[j] != NULL) { |
|---|
| 463 | if (i == j) |
|---|
| 464 | printf("%7.5s", identif[i]); |
|---|
| 465 | else if (psotu[i] == NULL || psotu[j] == NULL) |
|---|
| 466 | printf("%7s", ""); |
|---|
| 467 | else if (minbrnch2[j] == i) |
|---|
| 468 | printf("%+7.2f", distanvari[j][i]); |
|---|
| 469 | else |
|---|
| 470 | printf("%7.2f", distanvari[j][i]); |
|---|
| 471 | } |
|---|
| 472 | } |
|---|
| 473 | printf("\n"); |
|---|
| 474 | } |
|---|
| 475 | } |
|---|
| 476 | } |
|---|
| 477 | } /* prbrnvari */ |
|---|
| 478 | |
|---|
| 479 | |
|---|
| 480 | void |
|---|
| 481 | pairorder(brndiff, brndiff2, minbrnch, minbrnch2, brnorder, psotu, numspc) |
|---|
| 482 | dvector brndiff, brndiff2; |
|---|
| 483 | ivector minbrnch, minbrnch2, brnorder; |
|---|
| 484 | Node **psotu; |
|---|
| 485 | int numspc; |
|---|
| 486 | { |
|---|
| 487 | int i, j, k, maxi; |
|---|
| 488 | double diff, maxdiff; |
|---|
| 489 | |
|---|
| 490 | maxdiff = -100.0; |
|---|
| 491 | maxi = -1; |
|---|
| 492 | for (i = 0; i < numspc; i++) { |
|---|
| 493 | j = minbrnch[i]; |
|---|
| 494 | if (i == minbrnch[j] && i < j) { |
|---|
| 495 | if (Write_optn) { |
|---|
| 496 | printf(" %8.3f%8.3f (%-5.5s,%-5.5s)", |
|---|
| 497 | brndiff[i], brndiff[j], Identif[i], Identif[j]); |
|---|
| 498 | printf("\t%8.4s%8.3f%8.3f\n", |
|---|
| 499 | (i == minbrnch2[j] && j == minbrnch2[i]) ? "vari" : "----", |
|---|
| 500 | brndiff2[i], brndiff2[j]); |
|---|
| 501 | } |
|---|
| 502 | #if 1 |
|---|
| 503 | (brndiff[i] < brndiff[j]) ? (diff=brndiff[i]) : (diff=brndiff[j]); |
|---|
| 504 | #endif |
|---|
| 505 | #if 0 |
|---|
| 506 | diff = ( brndiff[i] + brndiff[j] ) * 0.5; |
|---|
| 507 | #endif |
|---|
| 508 | /* if (i != minbrnch2[j] || j != minbrnch2[i]) diff -= 10.0; */ |
|---|
| 509 | if (diff > maxdiff) { /* > */ |
|---|
| 510 | maxdiff = diff; |
|---|
| 511 | maxi = i; |
|---|
| 512 | } |
|---|
| 513 | } |
|---|
| 514 | } |
|---|
| 515 | brnorder[0] = maxi; |
|---|
| 516 | |
|---|
| 517 | } /* pairorder */ |
|---|
| 518 | |
|---|
| 519 | |
|---|
| 520 | void |
|---|
| 521 | pairorder2(brndiff, brndiff2, minbrnch, minbrnch2, brnorder, psotu, numspc) |
|---|
| 522 | dvector brndiff, brndiff2; |
|---|
| 523 | ivector minbrnch, minbrnch2, brnorder; |
|---|
| 524 | Node **psotu; |
|---|
| 525 | int numspc; |
|---|
| 526 | { |
|---|
| 527 | int i, j, k, maxi; |
|---|
| 528 | double diff, maxdiff; |
|---|
| 529 | |
|---|
| 530 | maxdiff = -100.0; |
|---|
| 531 | maxi = -1; |
|---|
| 532 | for (i = 0; i < numspc; i++) { |
|---|
| 533 | j = minbrnch[i]; |
|---|
| 534 | if (i == minbrnch[j] && i < j) { |
|---|
| 535 | if (Write_optn) { |
|---|
| 536 | printf(" %8.3f%8.3f (%-5.5s,%-5.5s)", |
|---|
| 537 | brndiff[i], brndiff[j], Identif[i], Identif[j]); |
|---|
| 538 | printf("\t%8.4s%8.3f%8.3f\n", |
|---|
| 539 | (i == minbrnch2[j] && j == minbrnch2[i]) ? "vari" : "----", |
|---|
| 540 | brndiff2[i], brndiff2[j]); |
|---|
| 541 | } |
|---|
| 542 | #if 1 |
|---|
| 543 | (brndiff[i] < brndiff[j]) ? (diff=brndiff[i]) : (diff=brndiff[j]); |
|---|
| 544 | #endif |
|---|
| 545 | #if 0 |
|---|
| 546 | diff = ( brndiff[i] + brndiff[j] ) * 0.5; |
|---|
| 547 | #endif |
|---|
| 548 | /* if (i != minbrnch2[j] || j != minbrnch2[i]) diff -= 10.0; */ |
|---|
| 549 | if (diff > maxdiff) { /* > */ |
|---|
| 550 | maxdiff = diff; |
|---|
| 551 | maxi = i; |
|---|
| 552 | } |
|---|
| 553 | } |
|---|
| 554 | } |
|---|
| 555 | brnorder[0] = maxi; |
|---|
| 556 | |
|---|
| 557 | } /* pairorder2 */ |
|---|
| 558 | |
|---|
| 559 | |
|---|
| 560 | void |
|---|
| 561 | distantree(tr, distan, numspc) |
|---|
| 562 | Tree *tr; |
|---|
| 563 | dmatrix distan; |
|---|
| 564 | int numspc; |
|---|
| 565 | { |
|---|
| 566 | int i, j, k, otui, otuj, otuk, nsp2, cinode, step, restsp; |
|---|
| 567 | double dij, bix, bjx, bkx, sij, smin; |
|---|
| 568 | dmatrix brnchmat, brnchvari; |
|---|
| 569 | dvector brndiff, brndiff2; |
|---|
| 570 | ivector minbrnch, minbrnch2, brnorder, underotus, masterotu; |
|---|
| 571 | Node **psotu, *cp, *ip, *jp, *kp; |
|---|
| 572 | |
|---|
| 573 | nsp2 = numspc - 2; |
|---|
| 574 | cinode = numspc; |
|---|
| 575 | psotu = (Node **)new_npvector(numspc); |
|---|
| 576 | brnchmat = new_dmatrix(numspc, numspc); |
|---|
| 577 | brnchvari = new_dmatrix(numspc, numspc); |
|---|
| 578 | brndiff = new_dvector(numspc); |
|---|
| 579 | brndiff2 = new_dvector(numspc); |
|---|
| 580 | minbrnch = new_ivector(numspc); |
|---|
| 581 | minbrnch2 = new_ivector(numspc); |
|---|
| 582 | brnorder = new_ivector(numspc); |
|---|
| 583 | underotus = new_ivector(numspc); |
|---|
| 584 | masterotu = new_ivector(numspc); |
|---|
| 585 | for (i = 0; i < numspc; i++) { |
|---|
| 586 | psotu[i] = tr->brnchp[i]->kinp; |
|---|
| 587 | underotus[i] = 1; |
|---|
| 588 | masterotu[i] = i; |
|---|
| 589 | } |
|---|
| 590 | restsp = numspc; |
|---|
| 591 | |
|---|
| 592 | for (step = 0; restsp > 3; step++) { |
|---|
| 593 | |
|---|
| 594 | #ifndef PAIR |
|---|
| 595 | triadmat(brnchmat, brnchvari, distan, psotu, numspc, nsp2); |
|---|
| 596 | minpair(brnchmat, brnchvari, brndiff, brndiff2, minbrnch, minbrnch2, |
|---|
| 597 | psotu, numspc); |
|---|
| 598 | #else |
|---|
| 599 | triadmat2(brnchmat, brnchvari, distan, psotu, |
|---|
| 600 | underotus, masterotu, numspc); |
|---|
| 601 | minpair2(brnchmat, brnchvari, brndiff, brndiff2, minbrnch, minbrnch2, |
|---|
| 602 | psotu, masterotu); |
|---|
| 603 | #endif |
|---|
| 604 | if (Write_optn && Info_optn) |
|---|
| 605 | #ifndef PAIR |
|---|
| 606 | prbrnmat(brnchmat, minbrnch, underotus, psotu, Identif, numspc); |
|---|
| 607 | #else |
|---|
| 608 | prbrnmat2(brnchmat, minbrnch, underotus, psotu, Identif, numspc); |
|---|
| 609 | #endif |
|---|
| 610 | /* |
|---|
| 611 | if (Write_optn && Info_optn) |
|---|
| 612 | prbrnvari(brnchvari, minbrnch2, underotus, psotu, Identif, numspc); |
|---|
| 613 | */ |
|---|
| 614 | #ifndef PAIR |
|---|
| 615 | pairorder(brndiff, brndiff2, minbrnch, minbrnch2, |
|---|
| 616 | brnorder, psotu, numspc); |
|---|
| 617 | #else |
|---|
| 618 | pairorder2(brndiff, brndiff2, minbrnch, minbrnch2, |
|---|
| 619 | brnorder, psotu, numspc); |
|---|
| 620 | #endif |
|---|
| 621 | |
|---|
| 622 | for (i = brnorder[0]; i < brnorder[0]+1; i++) { /* numspc */ |
|---|
| 623 | if (restsp == 3) break; |
|---|
| 624 | j = minbrnch[i]; |
|---|
| 625 | if (i == minbrnch[j] && i < j) { /* i == minbrnch[j] */ |
|---|
| 626 | if (Write_optn) |
|---|
| 627 | printf("%-4d%8.3f%8.3f (%s,%s)\n", |
|---|
| 628 | cinode+1, brndiff[i], brndiff[j], Identif[i], Identif[j]); |
|---|
| 629 | |
|---|
| 630 | bix = brnchmat[i][j]; |
|---|
| 631 | bjx = brnchmat[j][i]; |
|---|
| 632 | dij = bix + bjx; |
|---|
| 633 | cp = tr->brnchp[cinode]; |
|---|
| 634 | ip = psotu[i]; |
|---|
| 635 | jp = psotu[j]; |
|---|
| 636 | cp->isop = ip; |
|---|
| 637 | ip->isop = jp; |
|---|
| 638 | jp->isop = cp; |
|---|
| 639 | ip->length += bix; /* += */ |
|---|
| 640 | jp->length += bjx; /* += */ |
|---|
| 641 | if (ip->length < 0.0) ip->length = 0.0; |
|---|
| 642 | if (jp->length < 0.0) jp->length = 0.0; |
|---|
| 643 | ip->kinp->length = ip->length; |
|---|
| 644 | jp->kinp->length = jp->length; |
|---|
| 645 | cp = cp->kinp; |
|---|
| 646 | cp->length = dij * -0.5; |
|---|
| 647 | psotu[i] = NULL; |
|---|
| 648 | psotu[j] = NULL; |
|---|
| 649 | masterotu[j] = i; |
|---|
| 650 | #if 0 |
|---|
| 651 | redistmat(distan, psotu, underotus, i, j, ip, jp); |
|---|
| 652 | #endif |
|---|
| 653 | psotu[i] = cp; |
|---|
| 654 | underotus[i] += underotus[j]; |
|---|
| 655 | underotus[j] = 0; |
|---|
| 656 | cinode++; |
|---|
| 657 | Numbrnch = cinode; |
|---|
| 658 | restsp--; |
|---|
| 659 | nsp2 -= 1.0; |
|---|
| 660 | if (Debug_optn) { |
|---|
| 661 | for (putchar('\n'), i = 0; i < numspc; i++) { |
|---|
| 662 | for (j = 0; j < numspc; j++) |
|---|
| 663 | printf("%8.3f", distan[i][j]); |
|---|
| 664 | putchar('\n'); |
|---|
| 665 | } |
|---|
| 666 | } |
|---|
| 667 | } |
|---|
| 668 | } |
|---|
| 669 | |
|---|
| 670 | } |
|---|
| 671 | |
|---|
| 672 | otui = otuj = otuk = -1; |
|---|
| 673 | for (i = 0; i < numspc; i++) { |
|---|
| 674 | if (psotu[i] != NULL) { |
|---|
| 675 | if (otui == -1) |
|---|
| 676 | otui = i; |
|---|
| 677 | else if (otuj == -1) |
|---|
| 678 | otuj = i; |
|---|
| 679 | else |
|---|
| 680 | otuk = i; |
|---|
| 681 | } |
|---|
| 682 | } |
|---|
| 683 | if (Write_optn && Info_optn) printf("%4d%4d%4d\n", otui, otuj, otuk); |
|---|
| 684 | bix = ( brnchmat[otui][otuj] + brnchmat[otui][otuj] ) * 0.5; |
|---|
| 685 | bjx = ( brnchmat[otuj][otui] + brnchmat[otuj][otuk] ) * 0.5; |
|---|
| 686 | bkx = ( brnchmat[otuk][otui] + brnchmat[otuk][otuj] ) * 0.5; |
|---|
| 687 | ip = psotu[otui]; |
|---|
| 688 | jp = psotu[otuj]; |
|---|
| 689 | kp = psotu[otuk]; |
|---|
| 690 | ip->isop = jp; |
|---|
| 691 | jp->isop = kp; |
|---|
| 692 | kp->isop = ip; |
|---|
| 693 | ip->length += bix; |
|---|
| 694 | jp->length += bjx; |
|---|
| 695 | kp->length += bkx; |
|---|
| 696 | if (ip->length < 0.0) ip->length = 0.0; |
|---|
| 697 | if (jp->length < 0.0) jp->length = 0.0; |
|---|
| 698 | if (kp->length < 0.0) kp->length = 0.0; |
|---|
| 699 | ip->kinp->length = ip->length; |
|---|
| 700 | jp->kinp->length = jp->length; |
|---|
| 701 | kp->kinp->length = kp->length; |
|---|
| 702 | tr->ablength = 0.0; |
|---|
| 703 | if (Outgr_optn) { |
|---|
| 704 | reroot(tr, tr->brnchp[Outgroup]->kinp); |
|---|
| 705 | } else { |
|---|
| 706 | tr->rootp = kp; |
|---|
| 707 | } |
|---|
| 708 | free_npvector(psotu); |
|---|
| 709 | free_ivector(masterotu); |
|---|
| 710 | free_ivector(underotus); |
|---|
| 711 | free_ivector(brnorder); |
|---|
| 712 | free_ivector(minbrnch2); |
|---|
| 713 | free_ivector(minbrnch); |
|---|
| 714 | free_dvector(brndiff2); |
|---|
| 715 | free_dvector(brndiff); |
|---|
| 716 | free_dmatrix(brnchvari); |
|---|
| 717 | free_dmatrix(brnchmat); |
|---|
| 718 | } /*_ distantree */ |
|---|
