/* Tree.h */
#include "../cfiles.h"
#include "../IV.h"
#include "../DV.h"
/*--------------------------------------------------------------------*/
/*
-----------------------
simple tree object
created -- 95nov15, cca
-----------------------
*/
typedef struct _Tree Tree ;
struct _Tree {
int n ;
int root ;
int *par ;
int *fch ;
int *sib ;
} ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in basics.c ----------------------------------------
------------------------------------------------------------------------
*/
/*
-----------------------------------------------
purpose -- create and return a new Tree object
created -- 95nov15, cca
-----------------------------------------------
*/
Tree *
Tree_new (
void
) ;
/*
------------------------------------------------------
purpose -- set the default fields for the Tree object
created -- 95nov15, cca
------------------------------------------------------
*/
void
Tree_setDefaultFields (
Tree *tree
) ;
/*
--------------------------------
purpose -- clear the data fields
created -- 95nov15, cca
--------------------------------
*/
void
Tree_clearData (
Tree *tree
) ;
/*
--------------------------------
purpose -- free the Tree object
created -- 95nov15, cca
--------------------------------
*/
void
Tree_free (
Tree *tree
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in instance.c --------------------------------------
------------------------------------------------------------------------
*/
/*
-------------------------------------------------
purpose -- return the number of nodes in the tree
created -- 98jun12, cca
-------------------------------------------------
*/
int
Tree_nnodes (
Tree *tree
) ;
/*
--------------------------------------
purpose -- return the root of the tree
created -- 98jun12, cca
--------------------------------------
*/
int
Tree_root (
Tree *tree
) ;
/*
------------------------------------------------
purpose -- return a pointer to the parent vector
created -- 98jun12, cca
------------------------------------------------
*/
int *
Tree_par (
Tree *tree
) ;
/*
-----------------------------------------------------
purpose -- return a pointer to the first child vector
created -- 98jun12, cca
-----------------------------------------------------
*/
int *
Tree_fch (
Tree *tree
) ;
/*
-------------------------------------------------
purpose -- return a pointer to the sibling vector
created -- 98jun12, cca
-------------------------------------------------
*/
int *
Tree_sib (
Tree *tree
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in init.c ------------------------------------------
------------------------------------------------------------------------
*/
/*
-----------------------
simplest constructor
created -- 95nov15, cca
-----------------------
*/
void
Tree_init1 (
Tree *tree,
int size
) ;
/*
--------------------------------
initialize given a parent vector
created -- 95nov15, cca
--------------------------------
*/
void
Tree_init2 (
Tree *tree,
int size,
int par[]
) ;
/*
---------------------------------
initialize given the tree vectors
created -- 95nov15, cca
---------------------------------
*/
void
Tree_init3 (
Tree *tree,
int size,
int par[],
int fch[],
int sib[]
) ;
/*
------------------------------------
set the fch[], sib[] and root fields
created -- 95nov15, cca
------------------------------------
*/
void
Tree_setFchSibRoot (
Tree *tree
) ;
/*
-----------------------
set the root field
created -- 95nov15, cca
-----------------------
*/
void
Tree_setRoot (
Tree *tree
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in maximizeGain.c ----------------------------------
------------------------------------------------------------------------
*/
/*
-------------------------------------------------------
purpose --
given a gain value assigned to each node,
find a set of nodes, no two in a child-ancestor
relationship, that maximizes the total gain.
this problem arises in finding the optimal domain/schur
complement partition for a semi-implicit factorization.
created -- 98jun20, cca
-------------------------------------------------------
*/
IV *
Tree_maximizeGainIV (
Tree *tree,
IV *gainIV,
int *ptotalgain,
int msglvl,
FILE *msgFile
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in subtree.c ---------------------------------------
------------------------------------------------------------------------
*/
/*
-------------------------------------------------
purpose -- to initialize subtree with the subtree
of tree using nodes in nodeidsIV
return values ---
1 -- normal return
-1 -- subtree is NULL
-2 -- nodeidsIV is NULL
-3 -- tree is NULL
-4 -- nodeidsIV is invalid
created -- 98oct15, cca
-------------------------------------------------
*/
int
Tree_initFromSubtree (
Tree *subtree,
IV *nodeidsIV,
Tree *tree
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in util.c ------------------------------------------
------------------------------------------------------------------------
*/
/*
-------------------------------------------------
return the first vertex in a post-order traversal
created -- 95nov15, cca
-------------------------------------------------
*/
int
Tree_postOTfirst (
Tree *tree
) ;
/*
----------------------------------------------------------
return the vertex that follows v in a post-order traversal
----------------------------------------------------------
*/
int
Tree_postOTnext (
Tree *tree,
int v
) ;
/*
------------------------------------------------
return the first vertex in a pre-order traversal
created -- 95nov15, cca
------------------------------------------------
*/
int
Tree_preOTfirst (
Tree *tree
) ;
/*
---------------------------------------------------------
return the vertex that follows v in a pre-order traversal
created -- 95nov15, cca
---------------------------------------------------------
*/
int
Tree_preOTnext (
Tree *tree,
int v
) ;
/*
---------------------------------------
return the number of leaves in the tree
created -- 95nov15, cca
---------------------------------------
*/
int
Tree_nleaves (
Tree *tree
) ;
/*
-----------------------------------------------
return the number of roots of the tree (forest)
created -- 95nov15, cca
-----------------------------------------------
*/
int
Tree_nroots (
Tree *tree
) ;
/*
-----------------------------------------
return the number of children of a vertex
created -- 95nov15, cca
-----------------------------------------
*/
int
Tree_nchild (
Tree *tree,
int v
) ;
/*
-------------------------------------------
this method returns an IV object that holds
the number of children for the tree nodes.
created -- 96dec18, cca
-------------------------------------------
*/
IV *
Tree_nchildIV (
Tree *tree
) ;
/*
-----------------------------
return the height of the tree
created -- 96aug23, cca
-----------------------------
*/
int
Tree_height (
Tree *tree
) ;
/*
-------------------------------------------------------------
return the maximum number of children of any node in the tree
created -- 96sep05, cca
-------------------------------------------------------------
*/
int
Tree_maxNchild (
Tree *tree
) ;
/*
---------------------------------------------
return the number of bytes used by the object
---------------------------------------------
*/
int
Tree_sizeOf (
Tree *tree
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in metrics.c ---------------------------------------
------------------------------------------------------------------------
*/
/*
------------------------------------------------------
create and return a subtree metric IV object
input : vmetricIV -- a metric defined on the vertices
return : tmetricIV -- a metric defined on the subtrees
created -- 96jun23, cca
------------------------------------------------------
*/
IV *
Tree_setSubtreeImetric (
Tree *tree,
IV *vmetricIV
) ;
/*
------------------------------------------------------
create and return a subtree metric DV object
input : vmetricDV -- a metric defined on the vertices
return : tmetricDV -- a metric defined on the subtrees
created -- 96jun23, cca
------------------------------------------------------
*/
DV *
Tree_setSubtreeDmetric (
Tree *tree,
DV *vmetricDV
) ;
/*
------------------------------------------------------------
create and return a depth metric IV object
input : vmetricIV -- a metric defined on the vertices
output : dmetric[] -- a depth metric defined on the vertices
dmetric[u] = vmetric[u] + dmetric[par[u]] if par[u] != -1
= vmetric[u] if par[u] == -1
created -- 96jun23, cca
------------------------------------------------------------
*/
IV *
Tree_setDepthImetric (
Tree *tree,
IV *vmetricIV
) ;
/*
------------------------------------------------------------
create and return a depth metric DV object
input : vmetricDV -- a metric defined on the vertices
output : dmetric[] -- a depth metric defined on the vertices
dmetric[u] = vmetric[u] + dmetric[par[u]] if par[u] != -1
= vmetric[u] if par[u] == -1
created -- 96jun23, cca
------------------------------------------------------------
*/
DV *
Tree_setDepthDmetric (
Tree *tree,
DV *vmetricDV
) ;
/*
------------------------------------------------------------------
create and return a height metric IV object
input : vmetricIV -- a metric defined on the vertices
output : dmetricIV -- a depth metric defined on the vertices
hmetric[v] = vmetric[v] + max{p(u) = v} hmetric[u] if fch[v] != -1
= vmetric[v] if fch[v] == -1
created -- 96jun23, cca
------------------------------------------------------------------
*/
IV *
Tree_setHeightImetric (
Tree *tree,
IV *vmetricIV
) ;
/*
------------------------------------------------------------------
create and return a height metric DV object
input : vmetricDV -- a metric defined on the vertices
output : dmetricDV -- a depth metric defined on the vertices
hmetric[v] = vmetric[v] + max{p(u) = v} hmetric[u] if fch[v] != -1
= vmetric[v] if fch[v] == -1
created -- 96jun23, cca
------------------------------------------------------------------
*/
DV *
Tree_setHeightDmetric (
Tree *tree,
DV *vmetricDV
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in justify.c ---------------------------------------
------------------------------------------------------------------------
*/
/*
------------------------------------------------------------
left-justify a tree by subtree size
children are linked in ascending order of their subtree size
created -- 95nov15, cca
------------------------------------------------------------
*/
void
Tree_leftJustify (
Tree *tree
) ;
/*
------------------------------------------------------
left-justify a tree by a metric
children are linked in ascending order of their metric
created -- 96jun23, cca
------------------------------------------------------
*/
void
Tree_leftJustifyI (
Tree *tree,
IV *metricIV
) ;
/*
------------------------------------------------------
left-justify a tree by a metric
children are linked in ascending order of their metric
created -- 96jun23, cca
------------------------------------------------------
*/
void
Tree_leftJustifyD (
Tree *tree,
DV *metricDV
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in perms.c -----------------------------------------
------------------------------------------------------------------------
*/
/*
--------------------------------------
fill the new-to-old permutation vector
created -- 95nov15, cca
--------------------------------------
*/
void
Tree_fillNewToOldPerm (
Tree *tree,
int newToOld[]
) ;
/*
--------------------------------------
fill the old-to-new permutation vector
created -- 95nov15, cca
--------------------------------------
*/
void
Tree_fillOldToNewPerm (
Tree *tree,
int oldToNew[]
) ;
/*
------------------------------------------------------
fill the new-to-old and old-to-new permutation vectors
created -- 95nov15, cca
------------------------------------------------------
*/
void
Tree_fillBothPerms (
Tree *tree,
int newToOld[],
int oldToNew[]
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in IO.c --------------------------------------------
------------------------------------------------------------------------
*/
/*
------------------------------------------------
purpose -- to read in an Tree object from a file
input --
fn -- filename, must be *.treeb or *.treef
return value -- 1 if success, 0 if failure
created -- 95nov15, cca
------------------------------------------------
*/
int
Tree_readFromFile (
Tree *tree,
char *fn
) ;
/*
-------------------------------------------------------
purpose -- to read an Tree object from a formatted file
return value -- 1 if success, 0 if failure
created -- 95nov15, cca
-------------------------------------------------------
*/
int
Tree_readFromFormattedFile (
Tree *tree,
FILE *fp
) ;
/*
---------------------------------------------------
purpose -- to read an Tree object from a binary file
return value -- 1 if success, 0 if failure
created -- 95nov15, cca
---------------------------------------------------
*/
int
Tree_readFromBinaryFile (
Tree *tree,
FILE *fp
) ;
/*
--------------------------------------------
purpose -- to write an Tree object to a file
input --
fn -- filename
*.treeb -- binary
*.treef -- formatted
anything else -- for human eye
return value -- 1 if success, 0 otherwise
created -- 95nov15, cca
--------------------------------------------
*/
int
Tree_writeToFile (
Tree *tree,
char *fn
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------
purpose -- to write an Tree object to a formatted file
return value -- 1 if success, 0 otherwise
created -- 95nov15, cca
------------------------------------------------------
*/
int
Tree_writeToFormattedFile (
Tree *tree,
FILE *fp
) ;
/*
---------------------------------------------------
purpose -- to write an Tree object to a binary file
return value -- 1 if success, 0 otherwise
created -- 95nov15, cca
---------------------------------------------------
*/
int
Tree_writeToBinaryFile (
Tree *tree,
FILE *fp
) ;
/*
--------------------------------------------------
purpose -- to write an Tree object for a human eye
return value -- 1 if success, 0 otherwise
created -- 95nov15, cca
--------------------------------------------------
*/
int
Tree_writeForHumanEye (
Tree *tree,
FILE *fp
) ;
/*
----------------------------------------------------------
purpose -- to write out the statistics for the Tree object
return value -- 1 if success, 0 otherwise
created -- 95nov15, cca
----------------------------------------------------------
*/
int
Tree_writeStats (
Tree *tree,
FILE *fp
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in compress.c --------------------------------------
------------------------------------------------------------------------
*/
/*
--------------------------------------------
create and return an IV object that contains
the map from vertices to fundamental chains.
return value -- # of fundamental chains
created -- 96jun23, cca
-------------------------------------------
*/
IV *
Tree_fundChainMap (
Tree *tree
) ;
/*
-----------------------------------------------------------------
compress a tree based on a map from old vertices to new vertices.
the restriction on the map is that the set {u | map[u] = U} must
be connected for all U.
created -- 95nov15, cca
modified -- 96jan04, cca
bug fixed, N computed incorrectly
modified -- 96jun23, cca
in calling sequence, int map[] converted to IV *mapIV
-----------------------------------------------------------------
*/
Tree *
Tree_compress (
Tree *tree,
IV *mapIV
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in permute.c ---------------------------------------
------------------------------------------------------------------------
*/
/*
-----------------------
return a permuted tree
created -- 96jan04, cca
-----------------------
*/
Tree *
Tree_permute (
Tree *tree,
int newToOld[],
int oldToNew[]
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in setBoxes.c --------------------------------------
------------------------------------------------------------------------
*/
/*
-------------------------------------------------------------
purpose -- fill boxes arrays for display of a tree
vmetric[] -- vector of metric on the nodes
tmetric[] -- vector of metric on the subtrees
xmin, xmax, ymin, ymax -- bounds on box for root
west[], east[], south[], north[] -- vector to hold bounds for
the nodes in the tree
return value --
1 --> success
2 --> no success, maxnchild > 3
created -- 96dec20, cca
-------------------------------------------------------------
*/
int
Tree_setBoxesII (
Tree *tree,
int vmetric[],
int tmetric[],
double xmin,
double xmax,
double ymin,
double ymax,
double west[],
double east[],
double south[],
double north[]
) ;
/*
-------------------------------------------------------------
purpose -- fill boxes arrays for display of a tree
vmetric[] -- vector of metric on the nodes
tmetric[] -- vector of metric on the subtrees
xmin, xmax, ymin, ymax -- bounds on box for root
west[], east[], south[], north[] -- vector to hold bounds for
the nodes in the tree
return value --
1 --> success
2 --> no success, maxnchild > 3
created -- 96dec20, cca
-------------------------------------------------------------
*/
int
Tree_setBoxesDD (
Tree *tree,
double vmetric[],
double tmetric[],
double xmin,
double xmax,
double ymin,
double ymax,
double west[],
double east[],
double south[],
double north[]
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in getCoords.c -------------------------------------
------------------------------------------------------------------------
*/
/*
------------------------------------------------
purpose -- to get simple x[] and y[] coordinates
for the tree vertices
return values --
1 -- normal return
-1 -- tree is NULL
-2 -- heightflag is invalid
-3 -- coordflag is invalid
-4 -- xDV is NULL
-5 -- yDV is NULL
created -- 99jan07, cca
------------------------------------------------
*/
int
Tree_getSimpleCoords (
Tree *tree,
char heightflag,
char coordflag,
DV *xDV,
DV *yDV
) ;
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------------
----- methods found in draw.c ------------------------------------------
------------------------------------------------------------------------
*/
/*
------------------------------------------------------------
purpose -- to write an EPS file with a picture of a tree.
each node can have its own radius and label
filename -- name of the file to be written
xDV -- x coordinates
yDV -- y coordinates
rscale -- scaling factor for radius of nodes
radiusDV -- radius of nodes, if NULL then radius = 1
labelflag -- flag to specify whether labels are to be drawn
1 -- draw labels
otherwise -- do not draw labels
fontscale -- scaling factor for font
labelsIV -- IV object that contains the labels of the nodes.
if NULL then the node ids are used
bbox[] -- bounding box for figure
bbox[0] -- x_min
bbox[1] -- y_min
bbox[2] -- x_max
bbox[3] -- y_max
frame[] -- frame to hold tree
frame[0] -- x_min
frame[1] -- y_min
frame[2] -- x_max
frame[3] -- y_max
bounds[] -- bounds for local coordinates
if bounds is NULL then
the tree fills the frame. note, this is a nonlinear process
when the nodes have non-constant radii, and may not converge
when the maximum radius is large when compared to the frame.
if the process does not converge, a message is printed and
the program exits.
else
bounds[0] -- xi_min
bounds[1] -- eta_min
bounds[2] -- xi_max
bounds[3] -- eta_max
endif
recommendations,
bbox[] = { 0, 0, 500, 200 } for tall skinny trees
{ 0, 0, 500, 500 } for wide trees
frame[0] = bbox[0] + 10
frame[1] = bbox[1] + 10
frame[2] = bbox[2] - 10
frame[3] = bbox[3] - 10
return value
1 -- normal return
-1 -- tree is NULL
-2 -- filename is NULL
-3 -- xDV is NULL
-4 -- yDV is NULL
-5 -- rscale is negative
-6 -- fontscale is negative
-7 -- bbox is NULL
-8 -- frame is NULL
created -- 99jan07, cca
------------------------------------------------------------
*/
int
Tree_drawToEPS (
Tree *tree,
char *filename,
DV *xDV,
DV *yDV,
double rscale,
DV *radiusDV,
int labelflag,
double fontscale,
IV *labelsIV,
double bbox[],
double frame[],
double bounds[]
) ;
/*--------------------------------------------------------------------*/
syntax highlighted by Code2HTML, v. 0.9.1