| 1 | /* |
|---|
| 2 | * distproc.c Adachi, J. 1994.07.22 |
|---|
| 3 | * Copyright (C) 1993, 1994 J. Adachi & M. Hasegawa, All rights reserved. |
|---|
| 4 | */ |
|---|
| 5 | |
|---|
| 6 | #include "tridist.h" |
|---|
| 7 | |
|---|
| 8 | Node ** |
|---|
| 9 | new_npvector(n) |
|---|
| 10 | int n; |
|---|
| 11 | /* memory allocate a node pointer vector */ |
|---|
| 12 | { |
|---|
| 13 | Node **v; |
|---|
| 14 | |
|---|
| 15 | v = (Node **) malloc((unsigned)n * sizeof(Node *)); |
|---|
| 16 | if (v == NULL) maerror("in new_npvector()."); |
|---|
| 17 | return v; |
|---|
| 18 | } |
|---|
| 19 | |
|---|
| 20 | void |
|---|
| 21 | free_npvector(v) |
|---|
| 22 | Node **v; |
|---|
| 23 | { |
|---|
| 24 | free((char *) v); |
|---|
| 25 | } |
|---|
| 26 | |
|---|
| 27 | void |
|---|
| 28 | getsize(ifp, numspc, commentp) |
|---|
| 29 | FILE *ifp; |
|---|
| 30 | int *numspc; |
|---|
| 31 | char **commentp; |
|---|
| 32 | { |
|---|
| 33 | char *cp, *np; |
|---|
| 34 | char line[BUFLINE]; |
|---|
| 35 | |
|---|
| 36 | if (fgets(line, BUFLINE, ifp) != NULL) { |
|---|
| 37 | if (sscanf(line, "%d", numspc) == 1) { |
|---|
| 38 | for (cp = line; isdigit(*cp); cp++) |
|---|
| 39 | ; |
|---|
| 40 | for ( ; isspace(*cp) && *cp != '\0'; cp++) |
|---|
| 41 | ; |
|---|
| 42 | *commentp = new_cvector(strlen(cp) + 1); |
|---|
| 43 | if (*cp != '\0') { |
|---|
| 44 | for (np = *commentp; *cp != '\n' && *cp != '\0'; cp++) |
|---|
| 45 | *np++ = *cp; |
|---|
| 46 | *np = '\0'; |
|---|
| 47 | } else { |
|---|
| 48 | **commentp = '\0'; |
|---|
| 49 | } |
|---|
| 50 | #if DEBUG |
|---|
| 51 | if (Debug) printf("%d OTUs, %s\n\n", *numspc, *commentp); |
|---|
| 52 | #endif |
|---|
| 53 | } else { |
|---|
| 54 | fputs(line, stderr); |
|---|
| 55 | fprintf(stderr, "\nBad format, first line of input file.\n"); |
|---|
| 56 | exit(1); |
|---|
| 57 | } |
|---|
| 58 | } else { |
|---|
| 59 | fprintf(stderr, "\nCan't read input file.\n"); |
|---|
| 60 | exit(1); |
|---|
| 61 | } |
|---|
| 62 | return; |
|---|
| 63 | } /*_ getsize */ |
|---|
| 64 | |
|---|
| 65 | |
|---|
| 66 | void |
|---|
| 67 | header(ofp, numspc, commentp) |
|---|
| 68 | FILE *ofp; |
|---|
| 69 | int *numspc; |
|---|
| 70 | char **commentp; |
|---|
| 71 | { |
|---|
| 72 | char date[32]; |
|---|
| 73 | |
|---|
| 74 | strftime(date, 32, "%x", localtime(&Ct0)); |
|---|
| 75 | fprintf(ofp, "%s %s (%s)", Prog_name, VERSION, date); |
|---|
| 76 | fprintf(ofp, " %d OTUs %s\n", *numspc, *commentp); |
|---|
| 77 | } /*_ header */ |
|---|
| 78 | |
|---|
| 79 | |
|---|
| 80 | /* getid */ |
|---|
| 81 | void |
|---|
| 82 | getid(ifp, identif, sciname, engname, nl, notu) |
|---|
| 83 | FILE *ifp; |
|---|
| 84 | char **identif; |
|---|
| 85 | char **sciname; |
|---|
| 86 | char **engname; |
|---|
| 87 | int *nl; |
|---|
| 88 | int *notu; |
|---|
| 89 | { |
|---|
| 90 | char line[BUFLINE]; |
|---|
| 91 | char idbuf[BUFLINE]; |
|---|
| 92 | char *cp, *np; |
|---|
| 93 | |
|---|
| 94 | while (fgets(line, BUFLINE, ifp) != NULL) { |
|---|
| 95 | (*nl)++; /* line counter */ |
|---|
| 96 | if (line[0] == '#') /* comment line skip */ |
|---|
| 97 | continue; |
|---|
| 98 | for (cp = line; isspace(*cp); cp++) /* white line skip */ |
|---|
| 99 | ; |
|---|
| 100 | if (*cp == '\0') |
|---|
| 101 | continue; |
|---|
| 102 | for (np = idbuf; !isspace(*cp); *np++ = *cp++) /* identifier */ |
|---|
| 103 | ; |
|---|
| 104 | *np = '\0'; |
|---|
| 105 | identif[*notu] = |
|---|
| 106 | (char *)malloc((unsigned)(strlen(idbuf) + 1) * sizeof(char)); |
|---|
| 107 | if (identif[*notu] == NULL) maerror("in getid, identif"); |
|---|
| 108 | strcpy(identif[*notu], idbuf); |
|---|
| 109 | |
|---|
| 110 | for ( ; isspace(*cp); cp++) /* white char skip */ |
|---|
| 111 | ; |
|---|
| 112 | /* science name */ |
|---|
| 113 | if (*cp != '(' && *cp != '\0' && *cp != '#' && *cp != '\n') { |
|---|
| 114 | for (np = idbuf; *cp!='(' && *cp!='#' && *cp!='\0' && *cp!='\n'; *np++ = *cp++) |
|---|
| 115 | ; |
|---|
| 116 | for ( ; isspace(*(np-1)); np--) |
|---|
| 117 | ; |
|---|
| 118 | *np = '\0'; |
|---|
| 119 | } else { |
|---|
| 120 | idbuf[0] = '\0'; |
|---|
| 121 | } |
|---|
| 122 | sciname[*notu] = |
|---|
| 123 | (char *)malloc((unsigned)(strlen(idbuf) + 1) * sizeof(char)); |
|---|
| 124 | if (identif[*notu] == NULL) maerror("in getid, sciname"); |
|---|
| 125 | strcpy(sciname[*notu], idbuf); |
|---|
| 126 | |
|---|
| 127 | /* english name */ |
|---|
| 128 | if (*cp != '\0' && *cp != '#' && *cp != '\n') { /* science name */ |
|---|
| 129 | for (np = idbuf; *cp!='#' && *cp!='\0' && *cp!='\n'; *np++ = *cp++) |
|---|
| 130 | ; |
|---|
| 131 | for ( ; isspace(*(np-1)); np--) |
|---|
| 132 | ; |
|---|
| 133 | *np = '\0'; |
|---|
| 134 | } else { |
|---|
| 135 | idbuf[0] = '\0'; |
|---|
| 136 | } |
|---|
| 137 | engname[*notu] = |
|---|
| 138 | (char *)malloc((unsigned)(strlen(idbuf) + 1) * sizeof(char)); |
|---|
| 139 | if (identif[*notu] == NULL) maerror("in getid, engname"); |
|---|
| 140 | strcpy(engname[*notu], idbuf); |
|---|
| 141 | |
|---|
| 142 | #ifdef DEBUG |
|---|
| 143 | if (Debug) { |
|---|
| 144 | printf("%3d spc. \"%s\"", *notu+1, identif[*notu]); |
|---|
| 145 | if (sciname[*notu] != '\0') { |
|---|
| 146 | putchar(' '); |
|---|
| 147 | fputs(sciname[*notu], stdout); |
|---|
| 148 | } |
|---|
| 149 | if (engname[*notu] != '\0') { |
|---|
| 150 | putchar(' '); |
|---|
| 151 | fputs(engname[*notu], stdout); |
|---|
| 152 | } |
|---|
| 153 | putchar('\n'); |
|---|
| 154 | } |
|---|
| 155 | #endif |
|---|
| 156 | break; |
|---|
| 157 | } |
|---|
| 158 | return; |
|---|
| 159 | } /*_ getid */ |
|---|
| 160 | |
|---|
| 161 | |
|---|
| 162 | /* getdist */ |
|---|
| 163 | void |
|---|
| 164 | getdist(ifp, distanmat, numspc, nl, notu) |
|---|
| 165 | FILE *ifp; |
|---|
| 166 | dmatrix distanmat; |
|---|
| 167 | int numspc, *nl, *notu; |
|---|
| 168 | { |
|---|
| 169 | char line[BUFLINE]; |
|---|
| 170 | char *cp, *np, **npp; |
|---|
| 171 | int motu; |
|---|
| 172 | double dis; |
|---|
| 173 | |
|---|
| 174 | motu = 0; |
|---|
| 175 | npp = &np; |
|---|
| 176 | while (fgets(line, BUFLINE, ifp) != NULL) { |
|---|
| 177 | (*nl)++; /* line counter */ |
|---|
| 178 | if (line[0] == '#') continue; /* comment line skip */ |
|---|
| 179 | for (cp = line; (dis = strtod(cp,npp)) || np != cp; cp = np, motu++) { |
|---|
| 180 | if (*notu < motu) { |
|---|
| 181 | distanmat[*notu][motu] = dis; |
|---|
| 182 | } else if (*notu == motu) { |
|---|
| 183 | if (dis == 0.0) { |
|---|
| 184 | distanmat[*notu][motu] = 0.0; |
|---|
| 185 | } else { |
|---|
| 186 | fprintf(stderr, "error! distanmat[%d][%d] = %f.5\n", |
|---|
| 187 | *notu, motu, dis); |
|---|
| 188 | exit(1); |
|---|
| 189 | } |
|---|
| 190 | } else { |
|---|
| 191 | if (distanmat[motu][*notu] != dis) { |
|---|
| 192 | distanmat[*notu][motu] = dis * 10000.0; |
|---|
| 193 | } else { |
|---|
| 194 | distanmat[*notu][motu] = dis * 100.0; |
|---|
| 195 | } |
|---|
| 196 | distanmat[motu][*notu] *= 100.0; |
|---|
| 197 | } |
|---|
| 198 | if (Debug_optn) printf("%8.3f", dis); |
|---|
| 199 | if (motu > numspc) { /* || (np == cp && np != NULL) */ |
|---|
| 200 | fputs(cp, stderr); |
|---|
| 201 | exit(1); |
|---|
| 202 | } |
|---|
| 203 | } |
|---|
| 204 | if (motu >= numspc) |
|---|
| 205 | break; |
|---|
| 206 | } |
|---|
| 207 | if (Debug_optn) putchar('\n'); |
|---|
| 208 | return; |
|---|
| 209 | } /* getdist */ |
|---|
| 210 | |
|---|
| 211 | |
|---|
| 212 | void getdata(ifp, identif, sciname, engname, distanmat, numspc) |
|---|
| 213 | FILE *ifp; |
|---|
| 214 | char **identif, **sciname, **engname; |
|---|
| 215 | dmatrix distanmat; |
|---|
| 216 | int numspc; |
|---|
| 217 | { |
|---|
| 218 | int notu; |
|---|
| 219 | int nl = 0; |
|---|
| 220 | |
|---|
| 221 | for (notu = 0; notu < numspc; notu++) { |
|---|
| 222 | getid(ifp, identif, sciname, engname, &nl, ¬u); |
|---|
| 223 | getdist(ifp, distanmat, numspc, &nl, ¬u); |
|---|
| 224 | } |
|---|
| 225 | return; |
|---|
| 226 | } /*_ getdistan */ |
|---|
| 227 | |
|---|
| 228 | |
|---|
| 229 | void getdatas(ifp, identif, distanmat, numspc) |
|---|
| 230 | FILE *ifp; |
|---|
| 231 | char **identif; |
|---|
| 232 | dmatrix distanmat; |
|---|
| 233 | int numspc; |
|---|
| 234 | { |
|---|
| 235 | int notu, motu, i; |
|---|
| 236 | double dis; |
|---|
| 237 | char line[BUFLINE]; |
|---|
| 238 | char idbuf[BUFLINE]; |
|---|
| 239 | char *cp, *np, **npp; |
|---|
| 240 | |
|---|
| 241 | for (notu = 0; notu < numspc; notu++) { |
|---|
| 242 | motu = -1; |
|---|
| 243 | while (fgets(line, BUFLINE, ifp) != NULL) { |
|---|
| 244 | if (line[0] == '#') /* comment line skip */ |
|---|
| 245 | continue; |
|---|
| 246 | for (cp = line; isspace(*cp); cp++) /* white line skip */ |
|---|
| 247 | ; |
|---|
| 248 | if (*cp == '\0') |
|---|
| 249 | continue; |
|---|
| 250 | if (motu == -1) { |
|---|
| 251 | for (np=idbuf, i=0; !isspace(*cp) && i<NMLNGTH; *np++ = *cp++, i++) |
|---|
| 252 | ; /* identifier */ |
|---|
| 253 | *np = '\0'; |
|---|
| 254 | identif[notu] = |
|---|
| 255 | (char *)malloc((unsigned)(strlen(idbuf)+1) * sizeof(char)); |
|---|
| 256 | if (identif[notu] == NULL) maerror("in getid, identif"); |
|---|
| 257 | strcpy(identif[notu], idbuf); |
|---|
| 258 | motu = 0; |
|---|
| 259 | } |
|---|
| 260 | npp = &np; |
|---|
| 261 | for ( ; (dis = strtod(cp,npp)) || np != cp; cp = np, motu++) { |
|---|
| 262 | distanmat[notu][motu] = dis * 100.0; |
|---|
| 263 | if (Debug_optn) printf("%8.3f", dis); |
|---|
| 264 | if (motu > numspc) { /* || (np == cp && np != NULL) */ |
|---|
| 265 | fputs(cp, stderr); |
|---|
| 266 | exit(1); |
|---|
| 267 | } |
|---|
| 268 | } |
|---|
| 269 | if (motu >= numspc) |
|---|
| 270 | break; |
|---|
| 271 | } |
|---|
| 272 | if (Debug_optn) putchar('\n'); |
|---|
| 273 | } |
|---|
| 274 | return; |
|---|
| 275 | } /*_ getdistan */ |
|---|
| 276 | |
|---|
| 277 | |
|---|
| 278 | void |
|---|
| 279 | copydist(distanmat2, distanmat, numspc) |
|---|
| 280 | dmatrix distanmat2, distanmat; |
|---|
| 281 | int numspc; |
|---|
| 282 | { |
|---|
| 283 | int i, j; |
|---|
| 284 | |
|---|
| 285 | for (i = 0; i < numspc; i++) |
|---|
| 286 | for (j = 0; j < numspc; j++) |
|---|
| 287 | distanmat2[i][j] = distanmat[i][j]; |
|---|
| 288 | } /*_ copydist */ |
|---|
| 289 | |
|---|
| 290 | |
|---|
| 291 | void |
|---|
| 292 | changedistan(distanmat, distanvec, numspc) |
|---|
| 293 | dmatrix distanmat; |
|---|
| 294 | dvector distanvec; |
|---|
| 295 | int numspc; |
|---|
| 296 | { |
|---|
| 297 | int i, j, k; |
|---|
| 298 | |
|---|
| 299 | for (k = 0, i = 0; i < (numspc - 1); i++) { |
|---|
| 300 | for (j = i + 1; j < numspc; j++, k++) |
|---|
| 301 | distanvec[k] = distanmat[i][j]; |
|---|
| 302 | } |
|---|
| 303 | } |
|---|
| 304 | |
|---|
| 305 | |
|---|
| 306 | Tree * |
|---|
| 307 | newtree(maxbrnch) |
|---|
| 308 | int maxbrnch; |
|---|
| 309 | { |
|---|
| 310 | int n, i; |
|---|
| 311 | Tree *tr; |
|---|
| 312 | Node *dp, *up; |
|---|
| 313 | |
|---|
| 314 | tr = (Tree *) malloc(sizeof(Tree)); |
|---|
| 315 | if (tr == NULL) maerror("tr in newtree()."); |
|---|
| 316 | tr->brnchp = (Node **) malloc((unsigned) (maxbrnch * sizeof(Node *))); |
|---|
| 317 | if (tr->brnchp == NULL) maerror("brnchp in newtree()."); |
|---|
| 318 | tr->paths = new_imatrix(maxbrnch, Numspc); |
|---|
| 319 | for (n = 0; n < maxbrnch; n++) { |
|---|
| 320 | dp = (Node *) malloc((unsigned) sizeof(Node)); |
|---|
| 321 | if (dp == NULL) maerror("dp in newtree()."); |
|---|
| 322 | up = (Node *) malloc((unsigned) sizeof(Node)); |
|---|
| 323 | if (up == NULL) maerror("up in newtree()."); |
|---|
| 324 | dp->isop = NULL; |
|---|
| 325 | up->isop = NULL; |
|---|
| 326 | dp->descen = TRUE; |
|---|
| 327 | up->descen = FALSE; |
|---|
| 328 | dp->num = n; |
|---|
| 329 | up->num = n; |
|---|
| 330 | dp->length = 0.0; |
|---|
| 331 | up->length = 0.0; |
|---|
| 332 | dp->kinp = up; |
|---|
| 333 | up->kinp = dp; |
|---|
| 334 | tr->brnchp[n] = dp; |
|---|
| 335 | for (i = 0; i < Numspc; i++) { |
|---|
| 336 | if (i == n) |
|---|
| 337 | tr->paths[n][i] = TRUE; |
|---|
| 338 | else |
|---|
| 339 | tr->paths[n][i] = FALSE; |
|---|
| 340 | } |
|---|
| 341 | } |
|---|
| 342 | tr->rootp = NULL; |
|---|
| 343 | tr->firstp = tr->brnchp[0]->kinp; /* !? */ |
|---|
| 344 | |
|---|
| 345 | return tr; |
|---|
| 346 | } /*_ newtree */ |
|---|
| 347 | |
|---|
| 348 | |
|---|
| 349 | #ifdef DEBUG |
|---|
| 350 | void |
|---|
| 351 | prcurtree(tr) |
|---|
| 352 | Tree *tr; |
|---|
| 353 | { |
|---|
| 354 | Node *dp, *up, *cp; |
|---|
| 355 | int i; |
|---|
| 356 | |
|---|
| 357 | /* printf("\nStructure of Tree\n"); */ |
|---|
| 358 | printf("\n%4s%5s%5s%5s%7s%11s%13s\n", |
|---|
| 359 | "num","kinp","isop","isop","descen","length", "namesp"); |
|---|
| 360 | for (i = 0; i < Numbrnch; i++) { |
|---|
| 361 | dp = tr->brnchp[i]; |
|---|
| 362 | up = dp->kinp; |
|---|
| 363 | printf("%4d", dp->num+1); |
|---|
| 364 | printf("%5d", up->num+1); |
|---|
| 365 | if (dp->isop == NULL) printf("%5s", "null"); |
|---|
| 366 | else printf("%5d", dp->isop->num+1); |
|---|
| 367 | if (up->isop == NULL) printf("%5s", "null"); |
|---|
| 368 | else printf("%5d", up->isop->num+1); |
|---|
| 369 | printf("%3d", dp->descen); |
|---|
| 370 | printf("%3d", up->descen); |
|---|
| 371 | printf("%8.3f", dp->length); |
|---|
| 372 | printf("%8.3f", up->length); |
|---|
| 373 | if (i < Numspc) { |
|---|
| 374 | for (cp = up->isop; cp != up; cp = cp->isop) { |
|---|
| 375 | printf("%5d", cp->num+1); |
|---|
| 376 | } |
|---|
| 377 | } |
|---|
| 378 | putchar('\n'); |
|---|
| 379 | } |
|---|
| 380 | dp = tr->rootp; |
|---|
| 381 | printf("%4d", dp->num+1); |
|---|
| 382 | for (cp = dp->isop; cp != dp; cp = cp->isop) { |
|---|
| 383 | printf("%5d", cp->num+1); |
|---|
| 384 | } |
|---|
| 385 | putchar('\n'); |
|---|
| 386 | } /*_ prcurtree */ |
|---|
| 387 | #endif |
|---|
| 388 | |
|---|
| 389 | |
|---|
| 390 | void |
|---|
| 391 | pathing(tr) |
|---|
| 392 | Tree *tr; |
|---|
| 393 | { |
|---|
| 394 | Node *cp, *rp, *xp, *yp; |
|---|
| 395 | int i; |
|---|
| 396 | imatrix pths; |
|---|
| 397 | |
|---|
| 398 | pths = tr->paths; |
|---|
| 399 | cp = rp = tr->rootp; |
|---|
| 400 | do { |
|---|
| 401 | cp = cp->isop->kinp; |
|---|
| 402 | if (cp->isop == NULL) { /* external node */ |
|---|
| 403 | cp = cp->kinp; |
|---|
| 404 | } else { /* internal node */ |
|---|
| 405 | if (!cp->descen) { |
|---|
| 406 | for (yp = cp->kinp, xp = yp->isop; xp != yp; xp = xp->isop) { |
|---|
| 407 | for (i = 0; i < Numspc; i++) |
|---|
| 408 | if (pths[xp->num][i]) |
|---|
| 409 | pths[yp->num][i] = TRUE; |
|---|
| 410 | } |
|---|
| 411 | } |
|---|
| 412 | } |
|---|
| 413 | } while (cp != rp); |
|---|
| 414 | } /* pathing */ |
|---|
| 415 | |
|---|
| 416 | |
|---|
| 417 | void |
|---|
| 418 | getproportion(proportion, distanmat, maxspc) |
|---|
| 419 | double *proportion; |
|---|
| 420 | dmatrix distanmat; |
|---|
| 421 | int maxspc; |
|---|
| 422 | { |
|---|
| 423 | int i, j; |
|---|
| 424 | double maxdis; |
|---|
| 425 | |
|---|
| 426 | maxdis = 0.0; |
|---|
| 427 | for (i = 1; i < maxspc; i++) { |
|---|
| 428 | for (j = 0; j < i; j++) { |
|---|
| 429 | if (distanmat[i][j] > maxdis) { |
|---|
| 430 | maxdis = distanmat[i][j]; |
|---|
| 431 | } |
|---|
| 432 | } |
|---|
| 433 | } |
|---|
| 434 | *proportion = (double)MAXCOLUMN / (maxdis * 3.0); |
|---|
| 435 | if (*proportion > 1.0) *proportion = 1.0; |
|---|
| 436 | if (Debug) printf("Proportion: %.5f maxdis: %.5f\n", *proportion,maxdis); |
|---|
| 437 | } /* getproportion */ |
|---|
| 438 | |
|---|
| 439 | |
|---|
| 440 | void |
|---|
| 441 | copylengths(tr, lengths, numbrnch) |
|---|
| 442 | Tree *tr; |
|---|
| 443 | dvector lengths; |
|---|
| 444 | int numbrnch; |
|---|
| 445 | { |
|---|
| 446 | int i; |
|---|
| 447 | double leng; |
|---|
| 448 | |
|---|
| 449 | for (i = 0; i < numbrnch; i++) { |
|---|
| 450 | leng = lengths[i]; |
|---|
| 451 | tr->brnchp[i]->length = leng; |
|---|
| 452 | tr->brnchp[i]->kinp->length = leng; |
|---|
| 453 | } |
|---|
| 454 | } /*_ copylengths */ |
|---|
| 455 | |
|---|
| 456 | |
|---|
| 457 | void |
|---|
| 458 | prdistanmat(distanmat, numspc) |
|---|
| 459 | dmatrix distanmat; |
|---|
| 460 | int numspc; |
|---|
| 461 | { |
|---|
| 462 | int i, j, k, n, m; |
|---|
| 463 | |
|---|
| 464 | for (k = 0; k < numspc; k = m) { |
|---|
| 465 | fputs("\n ", stdout); |
|---|
| 466 | for (n = 0, j = k; n < 10 && j < numspc; j++, n++) { |
|---|
| 467 | printf("%7.5s", Identif[j]); |
|---|
| 468 | } |
|---|
| 469 | m = j; |
|---|
| 470 | putchar('\n'); |
|---|
| 471 | for (i = 0; i < numspc; i++) { |
|---|
| 472 | printf("%-5.5s", Identif[i]); |
|---|
| 473 | for (j = k; j < m && j < numspc; j++) { |
|---|
| 474 | if (i == j) |
|---|
| 475 | printf("%7.5s", Identif[i]); |
|---|
| 476 | else |
|---|
| 477 | printf("%7.2f", distanmat[i][j]); |
|---|
| 478 | } |
|---|
| 479 | printf("\n"); |
|---|
| 480 | } |
|---|
| 481 | } |
|---|
| 482 | } /* prdistanmat */ |
|---|
| 483 | |
|---|
| 484 | |
|---|
| 485 | static void |
|---|
| 486 | luequation(amat, yvec, size) |
|---|
| 487 | dmatrix amat; |
|---|
| 488 | dvector yvec; |
|---|
| 489 | int size; |
|---|
| 490 | { |
|---|
| 491 | /* SOLVE THE LINEAR SET OF EQUATIONS ON LU DECOMPOSITION */ |
|---|
| 492 | double eps = 1.0e-20; /* ! */ |
|---|
| 493 | int i, j, k, l, maxi, idx; |
|---|
| 494 | double sum, tmp, maxb, aw; |
|---|
| 495 | dvector wk; |
|---|
| 496 | ivector index; |
|---|
| 497 | |
|---|
| 498 | wk = new_dvector(size); |
|---|
| 499 | index = new_ivector(size); |
|---|
| 500 | aw = 1.0; |
|---|
| 501 | for (i = 0; i < size; i++) { |
|---|
| 502 | maxb = 0.0; |
|---|
| 503 | for (j = 0; j < size; j++) { |
|---|
| 504 | if (fabs(amat[i][j]) > maxb) |
|---|
| 505 | maxb = fabs(amat[i][j]); |
|---|
| 506 | } |
|---|
| 507 | if (maxb == 0.0) { |
|---|
| 508 | fprintf(stderr, "luequation: singular matrix\n"); |
|---|
| 509 | exit(1); |
|---|
| 510 | } |
|---|
| 511 | wk[i] = 1.0 / maxb; |
|---|
| 512 | } |
|---|
| 513 | for (j = 0; j < size; j++) { |
|---|
| 514 | for (i = 0; i < j; i++) { |
|---|
| 515 | sum = amat[i][j]; |
|---|
| 516 | for (k = 0; k < i; k++) |
|---|
| 517 | sum -= amat[i][k] * amat[k][j]; |
|---|
| 518 | amat[i][j] = sum; |
|---|
| 519 | } |
|---|
| 520 | maxb = 0.0; |
|---|
| 521 | for (i = j; i < size; i++) { |
|---|
| 522 | sum = amat[i][j]; |
|---|
| 523 | for (k = 0; k < j; k++) |
|---|
| 524 | sum -= amat[i][k] * amat[k][j]; |
|---|
| 525 | amat[i][j] = sum; |
|---|
| 526 | tmp = wk[i] * fabs(sum); |
|---|
| 527 | if (tmp >= maxb) { |
|---|
| 528 | maxb = tmp; |
|---|
| 529 | maxi = i; |
|---|
| 530 | } |
|---|
| 531 | } |
|---|
| 532 | if (j != maxi) { |
|---|
| 533 | for (k = 0; k < size; k++) { |
|---|
| 534 | tmp = amat[maxi][k]; |
|---|
| 535 | amat[maxi][k] = amat[j][k]; |
|---|
| 536 | amat[j][k] = tmp; |
|---|
| 537 | } |
|---|
| 538 | aw = -aw; |
|---|
| 539 | wk[maxi] = wk[j]; |
|---|
| 540 | } |
|---|
| 541 | index[j] = maxi; |
|---|
| 542 | if (amat[j][j] == 0.0) |
|---|
| 543 | amat[j][j] = eps; |
|---|
| 544 | if (j != size - 1) { |
|---|
| 545 | tmp = 1.0 / amat[j][j]; |
|---|
| 546 | for (i = j + 1; i < size; i++) |
|---|
| 547 | amat[i][j] *= tmp; |
|---|
| 548 | } |
|---|
| 549 | } |
|---|
| 550 | |
|---|
| 551 | l = -1; |
|---|
| 552 | for (i = 0; i < size; i++) { |
|---|
| 553 | idx = index[i]; |
|---|
| 554 | sum = yvec[idx]; |
|---|
| 555 | yvec[idx] = yvec[i]; |
|---|
| 556 | if (l != -1) { |
|---|
| 557 | for (j = l; j < i; j++) |
|---|
| 558 | sum -= amat[i][j] * yvec[j]; |
|---|
| 559 | } else if (sum != 0.0) |
|---|
| 560 | l = i; |
|---|
| 561 | yvec[i] = sum; |
|---|
| 562 | } |
|---|
| 563 | for (i = size - 1; i >= 0; i--) { |
|---|
| 564 | sum = yvec[i]; |
|---|
| 565 | for (j = i + 1; j < size; j++) |
|---|
| 566 | sum -= amat[i][j] * yvec[j]; |
|---|
| 567 | yvec[i] = sum / amat[i][i]; |
|---|
| 568 | } |
|---|
| 569 | free_ivector(index); |
|---|
| 570 | free_dvector(wk); |
|---|
| 571 | } /*_ luequation */ |
|---|
| 572 | |
|---|
| 573 | |
|---|
| 574 | void |
|---|
| 575 | lslength(tr, distanvec, lengths) |
|---|
| 576 | Tree *tr; |
|---|
| 577 | dvector distanvec; |
|---|
| 578 | dvector lengths; |
|---|
| 579 | { |
|---|
| 580 | int i, i1, i2, j, k; |
|---|
| 581 | double sum, leng, alllen, rss; |
|---|
| 582 | imatrix pths; |
|---|
| 583 | dmatrix amt, atamt; |
|---|
| 584 | |
|---|
| 585 | amt = new_dmatrix(Numpair, Numbrnch); |
|---|
| 586 | atamt = new_dmatrix(Numbrnch, Numbrnch); |
|---|
| 587 | pths = tr->paths; |
|---|
| 588 | if (Debug) { |
|---|
| 589 | putchar('\n'); |
|---|
| 590 | for (i = 0; i < Numbrnch; i++) { |
|---|
| 591 | for (j = 0; j < Numspc; j++) { |
|---|
| 592 | printf("%2d",pths[i][j]); |
|---|
| 593 | } putchar('\n'); |
|---|
| 594 | } |
|---|
| 595 | } |
|---|
| 596 | for (i = 0, i1 = 0; i1 < (Numspc - 1); i1++) { |
|---|
| 597 | for (i2 = i1 + 1; i2 < Numspc; i2++, i++) { |
|---|
| 598 | for (j = 0; j < Numbrnch; j++) { |
|---|
| 599 | if (pths[j][i1] != pths[j][i2]) |
|---|
| 600 | amt[i][j] = 1.0; |
|---|
| 601 | else |
|---|
| 602 | amt[i][j] = 0.0; |
|---|
| 603 | } |
|---|
| 604 | } |
|---|
| 605 | } |
|---|
| 606 | if (Debug) { |
|---|
| 607 | putchar('\n'); |
|---|
| 608 | for (i = 0; i < Numpair; i++) { |
|---|
| 609 | for (j = 0; j < Numbrnch; j++) |
|---|
| 610 | printf("%3.0f",amt[i][j]); |
|---|
| 611 | printf("%6.1f\n",distanvec[i]); |
|---|
| 612 | } |
|---|
| 613 | } |
|---|
| 614 | #ifdef DIST |
|---|
| 615 | putchar('\n'); |
|---|
| 616 | for (i = 0; i < Numpair; i++) |
|---|
| 617 | printf("%5.1f",distanvec[i]); |
|---|
| 618 | putchar('\n'); |
|---|
| 619 | #endif |
|---|
| 620 | for (i = 0; i < Numbrnch; i++) { |
|---|
| 621 | for (j = 0; j < Numbrnch; j++) { |
|---|
| 622 | for (k = 0, sum = 0.0; k < Numpair; k++) |
|---|
| 623 | sum += amt[k][i] * amt[k][j]; |
|---|
| 624 | atamt[i][j] = sum; |
|---|
| 625 | } |
|---|
| 626 | for (k = 0, sum = 0.0; k < Numpair; k++) |
|---|
| 627 | sum += amt[k][i] * distanvec[k]; |
|---|
| 628 | lengths[i] = sum; |
|---|
| 629 | } |
|---|
| 630 | |
|---|
| 631 | luequation(atamt, lengths, Numbrnch); |
|---|
| 632 | /* |
|---|
| 633 | putchar('\n'); |
|---|
| 634 | for (i = 0; i < Numbrnch; i++) { |
|---|
| 635 | for (j = 0; j < Numbrnch; j++) |
|---|
| 636 | printf("%5.1f", atamt[i][j]); |
|---|
| 637 | printf("%7.3f",lengths[i]); |
|---|
| 638 | putchar('\n'); |
|---|
| 639 | } |
|---|
| 640 | */ |
|---|
| 641 | if (Debug) { |
|---|
| 642 | for (i = 0; i < Numbrnch; i++) { |
|---|
| 643 | printf("%7.3f",lengths[i]); |
|---|
| 644 | } putchar('\n'); |
|---|
| 645 | } |
|---|
| 646 | for (i = 0, rss = 0.0; i < Numpair; i++) { |
|---|
| 647 | sum = distanvec[i]; |
|---|
| 648 | for (j = 0; j < Numbrnch; j++) { |
|---|
| 649 | if (amt[i][j] == 1.0 && lengths[j] > 0.0) |
|---|
| 650 | sum -= lengths[j]; |
|---|
| 651 | } |
|---|
| 652 | rss += sum * sum; |
|---|
| 653 | } |
|---|
| 654 | tr->rssleast = sqrt(rss / Numpair); /* !? */ |
|---|
| 655 | for (i = 0, alllen = 0.0; i < Numbrnch; i++) { |
|---|
| 656 | leng = lengths[i]; |
|---|
| 657 | /* if (leng > 0.0) */ |
|---|
| 658 | alllen += leng; |
|---|
| 659 | if (leng < 0.0) leng = 0.0; |
|---|
| 660 | /* tr->brnchp[i]->length = leng; |
|---|
| 661 | tr->brnchp[i]->kinp->length = leng; */ |
|---|
| 662 | } |
|---|
| 663 | tr->ablength = alllen; |
|---|
| 664 | free_dmatrix(amt); |
|---|
| 665 | free_dmatrix(atamt); |
|---|
| 666 | free_dvector(lengths); |
|---|
| 667 | } /*_ lslength */ |
|---|
| 668 | |
|---|
| 669 | |
|---|
| 670 | void |
|---|
| 671 | fputctopology(fp, tr) |
|---|
| 672 | FILE *fp; |
|---|
| 673 | Tree *tr; |
|---|
| 674 | { |
|---|
| 675 | Node *cp, *rp; |
|---|
| 676 | |
|---|
| 677 | cp = rp = tr->rootp; |
|---|
| 678 | putc('(', fp); |
|---|
| 679 | do { |
|---|
| 680 | cp = cp->isop->kinp; |
|---|
| 681 | if (cp->isop == NULL) { /* external node */ |
|---|
| 682 | fputs(Identif[cp->num], fp); |
|---|
| 683 | cp = cp->kinp; |
|---|
| 684 | } else { /* internal node */ |
|---|
| 685 | if (cp->descen) |
|---|
| 686 | putc('(', fp); |
|---|
| 687 | else |
|---|
| 688 | putc(')', fp); |
|---|
| 689 | } |
|---|
| 690 | if (!cp->descen && !cp->isop->descen && cp != rp) /* not last subtree */ |
|---|
| 691 | putc(',', fp); |
|---|
| 692 | } while (cp != rp); |
|---|
| 693 | fputs(");\n", fp); |
|---|
| 694 | |
|---|
| 695 | } /* putctopology */ |
|---|
| 696 | |
|---|
| 697 | |
|---|
| 698 | void |
|---|
| 699 | fputcphylogeny(fp, tr) |
|---|
| 700 | FILE *fp; |
|---|
| 701 | Tree *tr; |
|---|
| 702 | { |
|---|
| 703 | Node *cp, *rp; |
|---|
| 704 | int n; |
|---|
| 705 | |
|---|
| 706 | cp = rp = tr->rootp; |
|---|
| 707 | putc('(', fp); |
|---|
| 708 | n = 1; |
|---|
| 709 | do { |
|---|
| 710 | cp = cp->isop->kinp; |
|---|
| 711 | if (cp->isop == NULL) { /* external node */ |
|---|
| 712 | if (n > 60) { putc('\n', fp); n = 0; } |
|---|
| 713 | fputs(Identif[cp->num], fp); |
|---|
| 714 | n += strlen(Identif[cp->num]); |
|---|
| 715 | fprintf(fp, ":%.3f", cp->length); |
|---|
| 716 | n += 6; |
|---|
| 717 | cp = cp->kinp; |
|---|
| 718 | } else { /* internal node */ |
|---|
| 719 | if (cp->descen) { |
|---|
| 720 | if (n > 60) { putc('\n', fp); n = 0; } |
|---|
| 721 | putc('(', fp); |
|---|
| 722 | n++; |
|---|
| 723 | } else { |
|---|
| 724 | putc(')', fp); |
|---|
| 725 | n++; |
|---|
| 726 | if (n > 70) { putc('\n', fp); n = 0; } |
|---|
| 727 | fprintf(fp, ":%.3f", cp->length); |
|---|
| 728 | n += 6; |
|---|
| 729 | } |
|---|
| 730 | } |
|---|
| 731 | if (!cp->descen && !cp->isop->descen && cp != rp) { |
|---|
| 732 | putc(',', fp); /* not last subtree */ |
|---|
| 733 | n++; |
|---|
| 734 | } |
|---|
| 735 | } while (cp != rp); |
|---|
| 736 | fputs(");\n", fp); |
|---|
| 737 | } /* fputcphylogeny */ |
|---|
| 738 | |
|---|
| 739 | |
|---|
| 740 | static void |
|---|
| 741 | prbranch(up, depth, m, maxm, umbrella, column) |
|---|
| 742 | Node *up; |
|---|
| 743 | int depth, m, maxm; |
|---|
| 744 | ivector umbrella; |
|---|
| 745 | ivector column; |
|---|
| 746 | { |
|---|
| 747 | int i, nn, n, maxn, lim; |
|---|
| 748 | Node *cp; |
|---|
| 749 | char bch; |
|---|
| 750 | |
|---|
| 751 | if ((int)(up->length * Proportion) >= MAXOVER) { |
|---|
| 752 | column[depth] = MAXLENG; |
|---|
| 753 | bch = '+'; |
|---|
| 754 | } else { |
|---|
| 755 | column[depth] = (int)(up->length * Proportion) + 3; |
|---|
| 756 | bch = '-'; |
|---|
| 757 | } |
|---|
| 758 | |
|---|
| 759 | if (up->isop == NULL) { /* external branch */ |
|---|
| 760 | nn = up->num + 1; /* offset */ |
|---|
| 761 | if (m == 1) umbrella[depth - 1] = TRUE; |
|---|
| 762 | for (i = 0; i < depth; i++) { |
|---|
| 763 | if (umbrella[i]) |
|---|
| 764 | printf("%*c", column[i], ':'); |
|---|
| 765 | else |
|---|
| 766 | printf("%*c", column[i], ' '); |
|---|
| 767 | } |
|---|
| 768 | if (m == maxm) umbrella[depth - 1] = FALSE; |
|---|
| 769 | for (i = 0, lim = column[depth] - 3; i < lim; i++) |
|---|
| 770 | putchar(bch); |
|---|
| 771 | printf("-%d ", nn); |
|---|
| 772 | puts(Identif[up->num]); |
|---|
| 773 | return; |
|---|
| 774 | } |
|---|
| 775 | |
|---|
| 776 | nn = up->num + 1; /* + Numspc offset, internal branch */ |
|---|
| 777 | for (cp = up->isop, maxn = 0; cp != up; cp = cp->isop, maxn++) |
|---|
| 778 | ; |
|---|
| 779 | for (cp = up->isop, n = 1; cp != up; cp = cp->isop, n++) { |
|---|
| 780 | prbranch(cp->kinp, depth + 1, n, maxn, umbrella, column); |
|---|
| 781 | if (m == 1 && n == maxn / 2) umbrella[depth - 1] = TRUE; |
|---|
| 782 | if (n != maxn) { |
|---|
| 783 | for (i = 0; i < depth; i++) { |
|---|
| 784 | if (umbrella[i]) |
|---|
| 785 | printf("%*c", column[i], ':'); |
|---|
| 786 | else |
|---|
| 787 | printf("%*c", column[i], ' '); |
|---|
| 788 | } |
|---|
| 789 | if (n == maxn / 2) { /* internal branch */ |
|---|
| 790 | for (i = 0, lim = column[depth] - 3; i < lim; i++) |
|---|
| 791 | putchar(bch); |
|---|
| 792 | if (nn < 10) |
|---|
| 793 | printf("--%d", nn); |
|---|
| 794 | else if (nn < 100) |
|---|
| 795 | printf("-%2d", nn); |
|---|
| 796 | else |
|---|
| 797 | printf("%3d", nn); |
|---|
| 798 | } else { |
|---|
| 799 | if (umbrella[depth]) |
|---|
| 800 | printf("%*c", column[depth], ':'); |
|---|
| 801 | else |
|---|
| 802 | printf("%*c", column[depth], ' '); |
|---|
| 803 | } |
|---|
| 804 | putchar('\n'); |
|---|
| 805 | } |
|---|
| 806 | if (m == maxm) umbrella[depth - 1] = FALSE; |
|---|
| 807 | } |
|---|
| 808 | return; |
|---|
| 809 | } /*_ prbranch */ |
|---|
| 810 | |
|---|
| 811 | |
|---|
| 812 | void |
|---|
| 813 | prtopology(tr) |
|---|
| 814 | Tree *tr; |
|---|
| 815 | { |
|---|
| 816 | int n, maxn, depth; |
|---|
| 817 | ivector umbrella; |
|---|
| 818 | ivector column; |
|---|
| 819 | Node *cp, *rp; |
|---|
| 820 | |
|---|
| 821 | umbrella = new_ivector(Numspc); |
|---|
| 822 | column = new_ivector(Numspc); |
|---|
| 823 | |
|---|
| 824 | for (n = 0; n < Numspc; n++) { |
|---|
| 825 | umbrella[n] = FALSE; |
|---|
| 826 | column[n] = 3; |
|---|
| 827 | } |
|---|
| 828 | column[0] = 1; |
|---|
| 829 | rp = tr->rootp; |
|---|
| 830 | for (maxn = 1, cp = rp->isop; cp != rp; cp = cp->isop, maxn++) |
|---|
| 831 | ; |
|---|
| 832 | depth = 1; |
|---|
| 833 | n = 0; |
|---|
| 834 | putchar('\n'); |
|---|
| 835 | cp = rp; |
|---|
| 836 | do { |
|---|
| 837 | cp = cp->isop; |
|---|
| 838 | n++; |
|---|
| 839 | prbranch(cp->kinp, depth, n, maxn, umbrella, column); |
|---|
| 840 | if (cp != rp) printf("%*c\n", column[0], ':'); |
|---|
| 841 | } while (cp != rp); |
|---|
| 842 | |
|---|
| 843 | free_ivector(umbrella); |
|---|
| 844 | free_ivector(column); |
|---|
| 845 | } /*_ prtopology */ |
|---|
| 846 | |
|---|
| 847 | |
|---|
| 848 | void |
|---|
| 849 | resulttree(tr) |
|---|
| 850 | Tree *tr; |
|---|
| 851 | { |
|---|
| 852 | int ne, ni; |
|---|
| 853 | Node *ep, *ip; |
|---|
| 854 | |
|---|
| 855 | /* printf("\nNo.%-3d", Cnotree + 1); offset */ |
|---|
| 856 | printf("\n%6s", ""); |
|---|
| 857 | if (Least_optn) |
|---|
| 858 | printf("%9s%7s%7s%8s%7s%7s\n", "num","NJ ","L.S.","num","NJ ","L.S."); |
|---|
| 859 | else |
|---|
| 860 | printf("%9s%7s%8s%7s\n", "num","length","num","length"); |
|---|
| 861 | for (ne = 0, ni = Numspc; ne < Numspc; ne++, ni++) { |
|---|
| 862 | ep = tr->brnchp[ne]; |
|---|
| 863 | printf("%-10.10s", Identif[ne]); |
|---|
| 864 | fputs(" ", stdout); |
|---|
| 865 | printf("%3d%7.2f", ne + 1, ep->length); /* offset */ |
|---|
| 866 | if (Least_optn) |
|---|
| 867 | printf("%7.2f", Lengths[ne]); |
|---|
| 868 | if (ni < Numbrnch) { |
|---|
| 869 | ip = tr->brnchp[ni]; |
|---|
| 870 | printf("%8d%7.2f", ni + 1, ip->length); /* offset */ |
|---|
| 871 | if (Least_optn) |
|---|
| 872 | printf("%7.2f", Lengths[ni]); |
|---|
| 873 | putchar('\n'); |
|---|
| 874 | } else { |
|---|
| 875 | #if 0 |
|---|
| 876 | if (ne == Numspc - 2 && Info_optn && Least_optn) |
|---|
| 877 | printf("%12s%10.1f", "RS :",tr->rssleast); |
|---|
| 878 | if (ne == Numspc - 1 && Info_optn) |
|---|
| 879 | printf("%12s%10.1f", "Total :",tr->ablength); |
|---|
| 880 | #endif |
|---|
| 881 | putchar('\n'); |
|---|
| 882 | } |
|---|
| 883 | } |
|---|
| 884 | } /*_ resulttree */ |
|---|
| 885 | |
|---|
| 886 | |
|---|
| 887 | void |
|---|
| 888 | reroot(tr, rp) |
|---|
| 889 | Tree *tr; |
|---|
| 890 | Node *rp; |
|---|
| 891 | { |
|---|
| 892 | Node *cp, *op, *xp, *yp; |
|---|
| 893 | |
|---|
| 894 | tr->rootp = rp; |
|---|
| 895 | cp = rp; |
|---|
| 896 | do { |
|---|
| 897 | cp = cp->isop->kinp; |
|---|
| 898 | if (cp->isop == NULL) { /* external node */ |
|---|
| 899 | cp->descen = TRUE; |
|---|
| 900 | cp = cp->kinp; |
|---|
| 901 | cp->descen = FALSE; |
|---|
| 902 | } else { /* internal node */ |
|---|
| 903 | if (cp->descen != -1) { |
|---|
| 904 | cp->descen = TRUE; |
|---|
| 905 | cp->kinp->descen = -1; |
|---|
| 906 | tr->brnchp[cp->num] = cp; |
|---|
| 907 | } else { |
|---|
| 908 | cp->descen = FALSE; |
|---|
| 909 | } |
|---|
| 910 | if (!cp->descen) { |
|---|
| 911 | op = cp->kinp; |
|---|
| 912 | xp = op->isop; |
|---|
| 913 | yp = xp->isop; |
|---|
| 914 | if (xp->num > yp->num) { |
|---|
| 915 | op->isop = yp; |
|---|
| 916 | yp->isop = xp; |
|---|
| 917 | xp->isop = op; |
|---|
| 918 | } |
|---|
| 919 | cp->num = op->isop->num; |
|---|
| 920 | xp->num = xp->kinp->num; |
|---|
| 921 | yp->num = yp->kinp->num; |
|---|
| 922 | } |
|---|
| 923 | } |
|---|
| 924 | } while (cp != rp); |
|---|
| 925 | op = cp; |
|---|
| 926 | xp = op->isop; |
|---|
| 927 | yp = xp->isop; |
|---|
| 928 | if (xp->num > yp->num) { |
|---|
| 929 | op->isop = yp; |
|---|
| 930 | yp->isop = xp; |
|---|
| 931 | xp->isop = op; |
|---|
| 932 | } |
|---|
| 933 | xp->num = xp->kinp->num; |
|---|
| 934 | yp->num = yp->kinp->num; |
|---|
| 935 | op->num = op->kinp->num; |
|---|
| 936 | } /* reroot */ |
|---|
