graph.cpp
上传用户:yhdzpy8989
上传日期:2007-06-13
资源大小:13604k
文件大小:6k
源码类别:

生物技术

开发平台:

C/C++

  1. /*
  2.  * ===========================================================================
  3.  * PRODUCTION $Log: graph.cpp,v $
  4.  * PRODUCTION Revision 1000.1  2004/06/01 18:09:59  gouriano
  5.  * PRODUCTION PRODUCTION: UPGRADED [GCC34_MSVC7] Dev-tree R1.2
  6.  * PRODUCTION
  7.  * ===========================================================================
  8.  */
  9. /*  $Id: graph.cpp,v 1000.1 2004/06/01 18:09:59 gouriano Exp $
  10. * ===========================================================================
  11. *
  12. *                            PUBLIC DOMAIN NOTICE
  13. *               National Center for Biotechnology Information
  14. *
  15. *  This software/database is a "United States Government Work" under the
  16. *  terms of the United States Copyright Act.  It was written as part of
  17. *  the author's official duties as a United States Government employee and
  18. *  thus cannot be copyrighted.  This software/database is freely available
  19. *  to the public for use. The National Library of Medicine and the U.S.
  20. *  Government have not placed any restriction on its use or reproduction.
  21. *
  22. *  Although all reasonable efforts have been taken to ensure the accuracy
  23. *  and reliability of the software and data, the NLM and the U.S.
  24. *  Government do not and cannot warrant the performance or results that
  25. *  may be obtained by using this software or data. The NLM and the U.S.
  26. *  Government disclaim all warranties, express or implied, including
  27. *  warranties of performance, merchantability or fitness for any particular
  28. *  purpose.
  29. *
  30. *  Please cite the author in any work or product based on this material.
  31. *
  32. * ===========================================================================
  33. *
  34. * Author:  Richard Desper
  35. *
  36. * File Description:  graph.cpp
  37. *
  38. *    A part of the Miminum Evolution algorithm
  39. *
  40. */
  41. #include <ncbi_pch.hpp>
  42. #include <stdio.h>
  43. #include <stdlib.h>
  44. #include <math.h>
  45. #include "graph.h"
  46. #include "fastme.h"
  47. BEGIN_NCBI_SCOPE
  48. BEGIN_SCOPE(fastme)
  49. boolean leaf(meNode *v)
  50. {
  51.   int count = 0;
  52.   if (NULL != v->parentEdge)
  53.     count++;
  54.   if (NULL != v->leftEdge)
  55.     count++;
  56.   if (NULL != v->rightEdge)
  57.     count++;
  58.   if (NULL != v->middleEdge)
  59.     count++;
  60.   if (count > 1)
  61.     return(FALSE_FASTME);
  62.   return(TRUE_FASTME);
  63. }
  64. meSet *addToSet(meNode *v, meSet *X)
  65. {
  66.   if (NULL == X)
  67.     {
  68.       X = (meSet *) malloc(sizeof(meSet));
  69.       X->firstNode = v;
  70.       X->secondNode = NULL;
  71.     }
  72.   else if (NULL == X->firstNode) 
  73.     X->firstNode = v;
  74.   else
  75.     X->secondNode = addToSet(v,X->secondNode);
  76.   return(X);
  77. }
  78. meNode *makeNode(char *label, meEdge *parentEdge, int index)
  79. {
  80.   meNode *newNode;  /*points to new meNode added to the graph*/
  81.   newNode = (meNode *) malloc(sizeof(meNode));
  82.   strcpy(newNode->label,label);
  83.   newNode->index = index;
  84.   newNode->index2 = -1;
  85.   newNode->parentEdge = parentEdge;
  86.   newNode->leftEdge = NULL;
  87.   newNode->middleEdge = NULL;
  88.   newNode->rightEdge = NULL;
  89.   /*all fields have been initialized*/
  90.   return(newNode);
  91. }
  92. meEdge *makeEdge(char *label, meNode *tail, meNode *head, double weight)
  93. {
  94.   meEdge *newEdge;
  95.   newEdge = (meEdge *) malloc(sizeof(meEdge));
  96.   strcpy(newEdge->label,label);
  97.   newEdge->tail = tail;
  98.   newEdge->head = head;
  99.   newEdge->distance = weight;
  100.   newEdge->totalweight = 0.0;
  101.   return(newEdge);
  102. }
  103. meTree *newTree()
  104. {
  105.   meTree *T;
  106.   T = (meTree *) malloc(sizeof(meTree));
  107.   T->root = NULL;
  108.   T->size = 0;
  109.   T->weight = -1;
  110.   return(T);
  111. }
  112. void freeSubTree(meEdge *e)
  113. {
  114.   meNode *v;
  115.   meEdge *e1, *e2;
  116.   v = e->head;
  117.   e1 = v->leftEdge;
  118.   if (NULL != e1)
  119.     {
  120.       freeSubTree(e1);
  121.       v->leftEdge = NULL;
  122.     }
  123.   e2 = v->rightEdge;
  124.   if (NULL != e2)
  125.     {
  126.       freeSubTree(e2);
  127.       v->rightEdge = NULL;
  128.     }
  129.   v->parentEdge = NULL;
  130.   free(v);
  131.   e->tail = NULL;
  132.   e->head = NULL;
  133.   free(e);
  134. }
  135. void freeTree(meTree *T)
  136. {
  137.   meNode *v;
  138.   v = T->root;
  139.   if (NULL != v->leftEdge)
  140.     freeSubTree(v->leftEdge);
  141.   v->leftEdge = NULL;
  142.   free(v);
  143.   T->root = NULL;
  144.   free(T);
  145. }
  146. void freeSet(meSet *S)
  147. {
  148.   if (NULL != S)
  149.     freeSet(S->secondNode);
  150.   free(S);
  151. }
  152. /*copyNode returns a copy of v which has all of the fields identical to those
  153. of v, except the meNode pointer fields*/
  154. meNode *copyNode(meNode *v)
  155. {
  156.   meNode *w;
  157.   w = makeNode(v->label,NULL,v->index);
  158.   return(w);
  159. }
  160. meNode *makeNewNode(char *label, int i)
  161. {
  162.   return(makeNode(label,NULL,i));
  163. }
  164. /*copyEdge calls makeEdge to make a copy of a given meEdge */
  165. /*does not copy all fields*/
  166. meEdge *copyEdge (meEdge *e)
  167. {
  168.   meEdge *newEdge;
  169.   newEdge = makeEdge(e->label,e->tail,e->head,e->distance);
  170.   newEdge->topsize = e->topsize;
  171.   newEdge->bottomsize = e->bottomsize;
  172.   return(newEdge);
  173. }
  174. /*detrifurcate takes the (possibly trifurcated) input tree
  175.   and reroots the meTree to a leaf*/
  176. /*assumes meTree is only trifurcated at root*/
  177. meTree *detrifurcate(meTree *T)
  178. {
  179.   meNode *v, *w = NULL;
  180.   meEdge *e, *f;
  181.   v = T->root;
  182.   if(leaf(v))
  183.     return(T);
  184.   if (NULL != v->parentEdge)
  185.     {
  186.       fprintf(stderr,"Error: root %s is poorly rooted.n",v->label);
  187.       exit(EXIT_FAILURE);
  188.     }
  189.   for(e = v->middleEdge, v->middleEdge = NULL; NULL != e; e = f )
  190.     {
  191.       w = e->head;
  192.       v = e->tail;
  193.       e->tail = w;
  194.       e->head = v;
  195.       f = w->leftEdge;
  196.       v->parentEdge = e;
  197.       w->leftEdge = e;
  198.       w->parentEdge = NULL;      
  199.     }
  200.   T->root = w;
  201.   return(T);
  202. }
  203. meEdge *siblingEdge(meEdge *e)
  204. {
  205.   if(e == e->tail->leftEdge)
  206.     return(e->tail->rightEdge);
  207.   else
  208.     return(e->tail->leftEdge);
  209. }
  210. void updateSizes(meEdge *e, int direction)
  211. {
  212.   meEdge *f;
  213.   switch(direction)
  214.     {
  215.     case UP:
  216.       f = e->head->leftEdge;
  217.       if (NULL != f)
  218. updateSizes(f,UP);
  219.       f = e->head->rightEdge;
  220.       if (NULL != f)
  221. updateSizes(f,UP);
  222.       e->topsize++;
  223.       break;
  224.     case DOWN:
  225.       f = siblingEdge(e);
  226.       if (NULL != f)
  227. updateSizes(f,UP);
  228.       f = e->tail->parentEdge;
  229.       if (NULL != f)
  230. updateSizes(f,DOWN);
  231.       e->bottomsize++;
  232.       break;
  233.     }
  234. }      
  235. END_SCOPE(fastme)
  236. END_NCBI_SCOPE
  237. /*
  238.  * ===========================================================================
  239.  * $Log: graph.cpp,v $
  240.  * Revision 1000.1  2004/06/01 18:09:59  gouriano
  241.  * PRODUCTION: UPGRADED [GCC34_MSVC7] Dev-tree R1.2
  242.  *
  243.  * Revision 1.2  2004/05/21 21:41:03  gorelenk
  244.  * Added PCH ncbi_pch.hpp
  245.  *
  246.  * Revision 1.1  2004/02/10 15:16:02  jcherry
  247.  * Initial version
  248.  *
  249.  * ===========================================================================
  250.  */