NCBI C++ ToolKit
graph.cpp
Go to the documentation of this file.

Go to the SVN repository for this file.

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