lib/phyloTree.c File Reference

#include "common.h"
#include "linefile.h"
#include "dystring.h"
#include "phyloTree.h"

Include dependency graph for phyloTree.c:

Go to the source code of this file.

Functions
phyloTree *	phyloReadTree (struct lineFile *lf)
phyloTree *	phyloOpenTree (char *fileName)
static struct phyloName *	parseIdent (char **ptrPtr)
static struct phyloTree *	newEdge (struct phyloTree *parent, struct phyloTree *child)
phyloTree *	phyloAddEdge (struct phyloTree *parent, struct phyloTree *child)
static struct phyloTree *	parseSubTree (char **ptrPtr)
phyloTree *	phyloParseString (char *string)
static void	tabOut (FILE *f)
static void	pTree (struct phyloTree *tree, FILE *f, boolean noDups)
void	phyloPrintTreeNoDups (struct phyloTree *tree, FILE *f)
void	phyloPrintTree (struct phyloTree *tree, FILE *f)
void	phyloDebugTree (struct phyloTree *tree, FILE *f)
phyloTree *	phyloFindName (struct phyloTree *tree, char *name)
void	phyloClearTreeMarks (struct phyloTree *tree)
phyloTree *	phyloFindMarkUpTree (struct phyloTree *tree)
void	phyloMarkUpTree (struct phyloTree *tree)
char *	phyloFindPath (struct phyloTree *tree, char *ref, char *cross)
static void	nodeNames (struct phyloTree *tree, struct dyString *ds)
char *	phyloNodeNames (struct phyloTree *tree)
static void	reParent (struct phyloTree *tree)
phyloTree *	phyloReRoot (struct phyloTree *tree)
void	phyloDeleteEdge (struct phyloTree *tree, struct phyloTree *edge)
int	phyloCountLeaves (struct phyloTree *tree)
Variables
static int	recurseCount = 0

---

Function Documentation

static struct phyloTree* newEdge	(	struct phyloTree *	parent,
		struct phyloTree *	child
	)			[static, read]

Definition at line 69 of file phyloTree.c.

References phyloTree::allocedEdges, phyloTree::edges, needMoreMem(), phyloTree::numEdges, and phyloTree::parent.

Referenced by bfGraphFromRangeGraph(), parseSubTree(), phyloAddEdge(), and reParent().

{
parent->numEdges++;

if (parent->numEdges > parent->allocedEdges)
    {
    int oldSize = parent->allocedEdges * sizeof (struct phyloTree *);
    int newSize;

    parent->allocedEdges += 5;
    newSize = parent->allocedEdges * sizeof (struct phyloTree *);
    parent->edges = needMoreMem(parent->edges, oldSize, newSize);
    }

child->parent = parent;
return parent->edges[parent->numEdges -1 ] = child;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void nodeNames	(	struct phyloTree *	tree,
		struct dyString *	ds
	)			[static]

Definition at line 326 of file phyloTree.c.

References ds, dyStringAppendC(), dyStringAppendN(), phyloTree::edges, phyloTree::ident, phyloName::name, and phyloTree::numEdges.

Referenced by phyloNodeNames().

{
int ii;

if (tree->ident->name)
    {
    dyStringAppendN(ds, tree->ident->name, strlen(tree->ident->name));
    dyStringAppendC(ds, ' ');
    }

for (ii=0; ii < tree->numEdges; ii++)
    nodeNames(tree->edges[ii],ds);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct phyloName* parseIdent

(

char **

ptrPtr

)

[static, read]

Definition at line 30 of file phyloTree.c.

References AllocVar, cloneString(), phyloName::length, and phyloName::name.

Referenced by parseSubTree().

{
struct phyloName *pName;
char *start = *ptrPtr;
char *ptr = *ptrPtr;

AllocVar(pName);
/* legal id's are alphanumeric */
while(isalpha(*ptr) || isdigit(*ptr) || (*ptr == '/')
     || (*ptr == '\'')
    || (*ptr == '.') || (*ptr == '_')) 
    ptr++;

/* did we read something? */
if(ptr > start)
    {
    char val;

    val = *ptr;
    *ptr = 0;
    pName->name = cloneString(start);
    *ptr = val;
    }

/* is there some branch length info */
if (*ptr == ':')
    {
    ptr++;
    sscanf(ptr, "%lg", &pName->length);
    while ((*ptr != '[') && (*ptr != ')') && (*ptr != ',') && (*ptr != ';'))
        ptr++;
    }

*ptrPtr = ptr;

return pName;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct phyloTree* parseSubTree

(

char **

ptrPtr

)

[static, read]

Definition at line 93 of file phyloTree.c.

References AllocVar, errAbort(), phyloTree::ident, phyloTree::isDup, newEdge(), phyloTree::parent, parseIdent(), startsWith(), and TRUE.

Referenced by phyloParseString().

{
struct phyloTree *node = NULL;
char *ptr = *ptrPtr;

/* trees are terminated by one of these three chars */
if ((*ptr == ';') || (*ptr == ',') || (*ptr == ')') )
    return NULL;

AllocVar(node);
if (*ptr == '(') 
    {
    struct phyloTree *edge;

    ptr++;

    do
        {
        edge = newEdge(node,parseSubTree(&ptr));
        edge->parent = node;
        } while (*ptr++ == ',');
    --ptr;
    if (*ptr++ != ')') 
        errAbort("unbalanced parenthesis at (%s)",ptr-1);
    node->ident = parseIdent(&ptr);
    }
else 
    if ((*ptr == ':') || (isalpha(*ptr))|| (isdigit(*ptr)) 
         || (*ptr == '\'') || (*ptr == '.'))
        node->ident = parseIdent(&ptr);
else
    errAbort("illegal char '%c' in phyloString",*ptr);

if (*ptr == '[')
    {
    if (startsWith("[&&NHX:D=Y]",ptr))
        node->isDup = TRUE;

    while(*ptr != ']')
        ptr++;

    ptr++;

    }

*ptrPtr = ptr;


return node;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct phyloTree* phyloAddEdge	(	struct phyloTree *	parent,
		struct phyloTree *	child
	)			[read]

Definition at line 87 of file phyloTree.c.

References newEdge(), and phyloTree::parent.

{
return newEdge(parent, child);
}

Here is the call graph for this function:

void phyloClearTreeMarks

(

struct phyloTree *

tree

)

Definition at line 253 of file phyloTree.c.

References phyloTree::edges, phyloTree::mark, phyloTree::numEdges, and phyloClearTreeMarks().

Referenced by phyloClearTreeMarks(), and phyloFindPath().

{
int ii;

tree->mark = 0;

for (ii=0; ii < tree->numEdges; ii++)
    phyloClearTreeMarks(tree->edges[ii]);
}

Here is the call graph for this function:

Here is the caller graph for this function:

int phyloCountLeaves

(

struct phyloTree *

tree

)

Definition at line 394 of file phyloTree.c.

References phyloTree::edges, phyloTree::numEdges, and phyloCountLeaves().

Referenced by phyloCountLeaves().

{
int ii, count = 0;

if (tree->numEdges == 0)
    return 1;

for (ii=0; ii < tree->numEdges; ii++)
    count += phyloCountLeaves(tree->edges[ii]);

return count;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void phyloDebugTree	(	struct phyloTree *	tree,
		FILE *	f
	)

Definition at line 218 of file phyloTree.c.

References phyloTree::edges, phyloTree::ident, phyloName::length, phyloName::name, phyloTree::numEdges, phyloDebugTree(), recurseCount, and tabOut().

Referenced by phyloDebugTree().

{
if (tree)
    {
    int ii;
    fprintf(f,"%s:%g numEdges %d\n",tree->ident->name, tree->ident->length, tree->numEdges);
    recurseCount++;
    for (ii= 0; ii < tree->numEdges; ii++)
        {
        tabOut(f);
        phyloDebugTree(tree->edges[ii], f);
        }
    recurseCount--;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void phyloDeleteEdge	(	struct phyloTree *	tree,
		struct phyloTree *	edge
	)

Definition at line 377 of file phyloTree.c.

References phyloTree::edges, and phyloTree::numEdges.

Referenced by reParent().

{
int ii;

for (ii=0; ii < tree->numEdges; ii++)
    if (tree->edges[ii] == edge)
        {
        memcpy(&tree->edges[ii], &tree->edges[ii+1], sizeof(tree) * (tree->numEdges - ii - 1));
        tree->numEdges--;
        //phyloFreeTree(edge);
        return;
        }

errAbort("tried to delete non-existant edge");
}

Here is the caller graph for this function:

struct phyloTree* phyloFindMarkUpTree

(

struct phyloTree *

tree

)

[read]

Definition at line 264 of file phyloTree.c.

References phyloTree::mark, and phyloTree::parent.

Referenced by phyloFindPath().

{
do
    {
    if (tree->mark)
        return tree;
    tree = tree->parent;
    } while (tree);

return NULL;
}

Here is the caller graph for this function:

struct phyloTree* phyloFindName	(	struct phyloTree *	tree,
		char *	name
	)			[read]

Definition at line 235 of file phyloTree.c.

References phyloTree::edges, phyloTree::ident, phyloName::name, phyloTree::numEdges, phyloFindName(), and sameString.

Referenced by phyloFindName(), and phyloFindPath().

{
struct phyloTree *subTree = NULL;
int ii;

if (tree->ident->name && sameString(tree->ident->name, name))
    return tree;

for (ii=0; ii < tree->numEdges; ii++)
    {
    if ((subTree = phyloFindName( tree->edges[ii], name)) != NULL)
        break;
    }

return subTree;
}

Here is the call graph for this function:

Here is the caller graph for this function:

char* phyloFindPath	(	struct phyloTree *	tree,
		char *	ref,
		char *	cross
	)

Definition at line 285 of file phyloTree.c.

References ds, dyStringAppendC(), dyStringAppendN(), phyloTree::ident, phyloTree::mark, phyloName::name, newDyString(), phyloTree::parent, phyloClearTreeMarks(), phyloFindMarkUpTree(), phyloFindName(), and phyloMarkUpTree().

{
struct phyloTree *treeRef, *treeCross, *parent;
struct dyString *ds = newDyString(0);

if ((treeRef = phyloFindName(tree,ref)) == NULL)
    return NULL;

if ((treeCross = phyloFindName(tree,cross)) == NULL)
    return NULL;

phyloClearTreeMarks(tree);
phyloMarkUpTree(treeCross);
if ((parent = phyloFindMarkUpTree(treeRef)) == NULL)
    return NULL;

/* walk up the tree till we hit the common parent */
while(treeRef != parent)
    {
    treeRef = treeRef->parent;
    if (ds->stringSize)
        dyStringAppendC(ds, ' ');
    if (treeRef->ident->name)
        dyStringAppendN(ds, treeRef->ident->name, strlen(treeRef->ident->name));
    }

/* now walk down the tree till we come to the target species */
while (parent != treeCross)
    {
    parent = parent->mark;
    dyStringAppendC(ds, ' ');
    if (parent->ident->name)
        dyStringAppendN(ds, parent->ident->name, strlen(parent->ident->name));
    }

return ds->string;
}

Here is the call graph for this function:

void phyloMarkUpTree

(

struct phyloTree *

tree

)

Definition at line 277 of file phyloTree.c.

References phyloTree::mark, and phyloTree::parent.

Referenced by phyloFindPath().

{
    tree->mark = tree;
    for(;tree->parent; tree = tree->parent)
        tree->parent->mark = tree;
}

Here is the caller graph for this function:

char* phyloNodeNames

(

struct phyloTree *

tree

)

Definition at line 341 of file phyloTree.c.

References ds, newDyString(), and nodeNames().

{
struct dyString *ds = newDyString(0);

nodeNames(tree, ds);

ds->string[ds->stringSize-1]=0;

return ds->string;
}

Here is the call graph for this function:

struct phyloTree* phyloOpenTree

(

char *

fileName

)

[read]

Definition at line 19 of file phyloTree.c.

References lineFileClose(), lineFileOpen(), phyloReadTree(), and TRUE.

{
struct lineFile *lf = lineFileOpen(fileName, TRUE);
struct phyloTree *tree = phyloReadTree(lf);

lineFileClose(&lf);

return tree;
}

Here is the call graph for this function:

struct phyloTree* phyloParseString

(

char *

string

)

[read]

Definition at line 145 of file phyloTree.c.

References eraseWhiteSpace(), errAbort(), and parseSubTree().

Referenced by phyloReadTree().

{
struct phyloTree *tree = NULL;
char *ptr = string;

eraseWhiteSpace(string);

tree = parseSubTree(&ptr);

if (*ptr != ';')
    errAbort("trees must terminated by ';'");

return tree;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void phyloPrintTree	(	struct phyloTree *	tree,
		FILE *	f
	)

Definition at line 211 of file phyloTree.c.

References FALSE, and pTree().

{
pTree(tree, f, FALSE);
fprintf(f, ";\n");
}

Here is the call graph for this function:

void phyloPrintTreeNoDups	(	struct phyloTree *	tree,
		FILE *	f
	)

Definition at line 204 of file phyloTree.c.

References pTree(), and TRUE.

{
pTree(tree, f, TRUE);
fprintf(f, ";\n");
}

Here is the call graph for this function:

struct phyloTree* phyloReadTree

(

struct lineFile *

lf

)

[read]

Definition at line 6 of file phyloTree.c.

References lineFileNext(), and phyloParseString().

Referenced by phyloOpenTree().

{
struct phyloTree *tree = NULL;
char *ptr;
int len;

if (lineFileNext(lf, &ptr, &len) && (len > 0))
    tree = phyloParseString(ptr);

return tree;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct phyloTree* phyloReRoot

(

struct phyloTree *

tree

)

[read]

Definition at line 368 of file phyloTree.c.

References phyloTree::ident, phyloName::length, and reParent().

{
reParent(tree);
tree->ident->length = 0;

return tree;
}

Here is the call graph for this function:

static void pTree	(	struct phyloTree *	tree,
		FILE *	f,
		boolean	noDups
	)			[static]

Definition at line 173 of file phyloTree.c.

References phyloTree::edges, phyloTree::ident, phyloTree::isDup, phyloName::length, phyloName::name, and phyloTree::numEdges.

Referenced by phyloPrintTree(), phyloPrintTreeNoDups(), and rbTreeFree().

{
if (tree)
    {
    int ii;
    if (noDups && (tree->numEdges == 1))
        pTree(tree->edges[0], f, noDups);
    else 
        {
        if (tree->numEdges)
            {
            fprintf(f,"(");
            for (ii= 0; ii < tree->numEdges; ii++)
                {
                pTree(tree->edges[ii], f, noDups);
                if (ii + 1 < tree->numEdges)
                    fprintf(f,",");
                }
            fprintf(f,")");
            }
        if (tree->ident->name)
            fprintf(f,"%s",tree->ident->name);
        //if (tree->ident->length != 0.0)
            fprintf(f,":%0.04g", tree->ident->length);
        if (tree->isDup)
            fprintf(f,"[&&NHX:D=Y]");
        }
    }
}

Here is the caller graph for this function:

static void reParent

(

struct phyloTree *

tree

)

[static]

Definition at line 354 of file phyloTree.c.

References phyloTree::ident, phyloName::length, newEdge(), phyloTree::parent, and phyloDeleteEdge().

Referenced by phyloReRoot().

{
if (tree->parent)
    {
    struct phyloTree *edge, *saveParent = tree->parent;

    reParent(saveParent);
    phyloDeleteEdge(saveParent, tree);
    edge = newEdge(tree, saveParent);
    edge->parent = tree;
    edge->ident->length = tree->ident->length;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void tabOut

(

FILE *

f

)

[static]

Definition at line 165 of file phyloTree.c.

References recurseCount.

Referenced by phyloDebugTree().

{
int i;

for(i=0; i < recurseCount; i++)
    fputc(' ',f);
}

Here is the caller graph for this function:

---

Variable Documentation

int recurseCount = 0 [static]

Definition at line 163 of file phyloTree.c.

Referenced by phyloDebugTree(), and tabOut().

---