Functions
Likelihood evaluation

Functions

void pllEvaluateIterative (pllInstance *tr, partitionList *pr, boolean getPerSiteLikelihoods)
 Evaluate the log likelihood of a specific branch of the topology. More...
 
void pllEvaluateGeneric (pllInstance *tr, partitionList *pr, nodeptr p, boolean fullTraversal, boolean getPerSiteLikelihoods)
 Evaluate the log likelihood of the tree topology. More...
 

Static functions

static double evaluateGAMMA_FLEX (const boolean fastScaling, int *ex1, int *ex2, int *wptr, double *x1_start, double *x2_start, double *tipVector, unsigned char *tipX1, const int n, double *diagptable, const int states, double *perSiteLikelihoods, boolean getPerSiteLikelihoods)
 A generic (and slow) implementation of log likelihood evaluation of a tree using the GAMMA model of rate heterogeneity. More...
 
static double evaluateGAMMA_FLEX_SAVE (const boolean fastScaling, int *ex1, int *ex2, int *wptr, double *x1_start, double *x2_start, double *tipVector, unsigned char *tipX1, const int n, double *diagptable, const int states, double *perSiteLikelihoods, boolean getPerSiteLikelihoods, double *x1_gapColumn, double *x2_gapColumn, unsigned int *x1_gap, unsigned int *x2_gap)
 Memory saving version of the generic (and slow) implementation of log likelihood evaluation of a tree using the GAMMA model of rate heterogeneity. More...
 
static double evaluateCAT_FLEX (const boolean fastScaling, int *ex1, int *ex2, int *cptr, int *wptr, double *x1, double *x2, double *tipVector, unsigned char *tipX1, int n, double *diagptable_start, const int states, double *perSiteLikelihoods, boolean getPerSiteLikelihoods)
 A generic (and slow) implementation of log likelihood evaluation of a tree using the CAT model of rate heterogeneity. More...
 
static double evaluateCAT_FLEX_SAVE (const boolean fastScaling, int *ex1, int *ex2, int *cptr, int *wptr, double *x1, double *x2, double *tipVector, unsigned char *tipX1, int n, double *diagptable_start, const int states, double *perSiteLikelihoods, boolean getPerSiteLikelihoods, double *x1_gapColumn, double *x2_gapColumn, unsigned int *x1_gap, unsigned int *x2_gap)
 A generic (and slow) implementation of log likelihood evaluation of a tree using the CAT model of rate heterogeneity with memory saving. More...
 
static double evaluateGTRGAMMAPROT_LG4 (int *ex1, int *ex2, int *wptr, double *x1, double *x2, double *tipVector[4], unsigned char *tipX1, int n, double *diagptable, const boolean fastScaling)
 Evaluation of log likelihood of a tree under the GAMMA model of rate heterogeneity and LG4 model of evolution. More...
 
static double evaluateGTRGAMMAPROT_GAPPED_SAVE (const boolean fastScaling, int *ex1, int *ex2, int *wptr, double *x1, double *x2, double *tipVector, unsigned char *tipX1, int n, double *diagptable, double *x1_gapColumn, double *x2_gapColumn, unsigned int *x1_gap, unsigned int *x2_gap)
 Evaluation of log likelihood of a tree using the GAMMA model of rate heterogeneity and the memory saving technique (Optimized SSE3 version for AA data) More...
 
static double evaluateGTRGAMMAPROT (const boolean fastScaling, int *ex1, int *ex2, int *wptr, double *x1, double *x2, double *tipVector, unsigned char *tipX1, int n, double *diagptable)
 Evaluation of log likelihood of a tree using the GAMMA model of rate heterogeneity (Optimized SSE3 version for AA data) More...
 
static double evaluateGTRCATPROT (const boolean fastScaling, int *ex1, int *ex2, int *cptr, int *wptr, double *x1, double *x2, double *tipVector, unsigned char *tipX1, int n, double *diagptable_start)
 Evaluation of log likelihood of a tree using the CAT model of rate heterogeneity (Optimized SSE3 version for AA data) More...
 
static double evaluateGTRCATPROT_SAVE (const boolean fastScaling, int *ex1, int *ex2, int *cptr, int *wptr, double *x1, double *x2, double *tipVector, unsigned char *tipX1, int n, double *diagptable_start, double *x1_gapColumn, double *x2_gapColumn, unsigned int *x1_gap, unsigned int *x2_gap)
 Evaluation of log likelihood of a tree using the CAT model of rate heterogeneity with memory saving (Optimized SSE3 version for AA data) More...
 
static double evaluateGTRCAT_SAVE (const boolean fastScaling, int *ex1, int *ex2, int *cptr, int *wptr, double *x1_start, double *x2_start, double *tipVector, unsigned char *tipX1, int n, double *diagptable_start, double *x1_gapColumn, double *x2_gapColumn, unsigned int *x1_gap, unsigned int *x2_gap)
 Evaluation of log likelihood of a tree using the CAT model of rate heterogeneity with memory saving (Optimized SSE3 version for DNA data) More...
 
static double evaluateGTRGAMMA_GAPPED_SAVE (const boolean fastScaling, int *ex1, int *ex2, int *wptr, double *x1_start, double *x2_start, double *tipVector, unsigned char *tipX1, const int n, double *diagptable, double *x1_gapColumn, double *x2_gapColumn, unsigned int *x1_gap, unsigned int *x2_gap)
 Evaluation of log likelihood of a tree using the GAMMA model of rate heterogeneity with memory saving (Optimized SSE3 version for DNA data) More...
 
static double evaluateGTRGAMMA (const boolean fastScaling, int *ex1, int *ex2, int *wptr, double *x1_start, double *x2_start, double *tipVector, unsigned char *tipX1, const int n, double *diagptable)
 Evaluation of log likelihood of a tree using the GAMMA model of rate heterogeneity (Optimized SSE3 version for DNA data) More...
 
static double evaluateGTRCAT (const boolean fastScaling, int *ex1, int *ex2, int *cptr, int *wptr, double *x1_start, double *x2_start, double *tipVector, unsigned char *tipX1, int n, double *diagptable_start)
 Evaluation of log likelihood of a tree using the CAT model of rate heterogeneity (Optimized SSE3 version for DNA data) More...
 

Detailed Description

This set of functions deals with the evaluation of likelihood for the current topology

Function Documentation

static double evaluateCAT_FLEX ( const boolean  fastScaling,
int *  ex1,
int *  ex2,
int *  cptr,
int *  wptr,
double *  x1,
double *  x2,
double *  tipVector,
unsigned char *  tipX1,
int  n,
double *  diagptable_start,
const int  states,
double *  perSiteLikelihoods,
boolean  getPerSiteLikelihoods 
)
static

A generic (and slow) implementation of log likelihood evaluation of a tree using the CAT model of rate heterogeneity.

Computes the log likelihood of the topology for a specific partition, assuming that the CAT model of rate heterogeneity is used. The likelihood is computed at a virtual root placed at an edge whose two end-points (nodes) have the conditional likelihood vectors x1 and x2. Furthermore, if getPerSiteLikelihoods is set to PLL_TRUE, then the log likelihood for each site is also computed and stored at the corresponding position in the array perSiteLikelihoods.

Parameters
fastScalingIf set to PLL_FALSE, then the likelihood of each site is also multiplied by log(PLL_MINLIKELIHOOD) times the number of times it has been scaled down
ex1An array that holds how many times a site has been scaled and points at the entries for node p. This parameter is used if fastScaling is set to PLL_FALSE.
ex2An array that holds how many times a site has been scaled and points at the entries for node q. This parameter is used if fastScaling is set to PLL_TRUE.
cptrArray holding the rate for each site in the compressed partition alignment
wptrArray holding the weight for each site in the compressed partition alignment
x1Conditional likelihood vectors for one of the two end-points of the specific edge for which we are evaluating the likelihood
x2Conditional likelihood vectors for the other end-point of the specific edge for which we are evaluating the likelihood
tipVectorPrecomputed table where the number of rows is equal to the number of possible basepair characters for the current data type, i.e.16 for DNA and 23 for AA, and each rows contains states elements each of which contains transition probabilities computed from the eigenvectors of the decomposed Q matrix.
tipX1If one of the two end-points (nodes) of the specific edge (for which we are evaluating the likelihood) is a tip, then this holds a pointer to the sequence data (basepairs) already converted in the internal integer representation, and x2 holds the conditional likelihood vectors for the internal node.
nNumber of sites for which we are doing the evaluation. For the single-thread version this is the number of sites in the current partition, for multi-threads this is the number of sites assigned to the running thread from the current partition.
diagptable_startStart of the array that contains the P-Matrix diagonal of the specific edge for which we are evaluating the likehood, and for each category of the CAT model
statesNumber of states (4 for DNA, 20 for AA)
perSiteLikelihoodsArray to store per-site log likelihoods if getPerSiteLikelihoods is set to PLL_TRUE
getPerSiteLikelihoodsIf set to PLL_TRUE then per-site log likelihoods are also computed and stored in perSiteLikelihoods
Returns
The evaluated log likelihood of the tree topology

+ Here is the caller graph for this function:

static double evaluateCAT_FLEX_SAVE ( const boolean  fastScaling,
int *  ex1,
int *  ex2,
int *  cptr,
int *  wptr,
double *  x1,
double *  x2,
double *  tipVector,
unsigned char *  tipX1,
int  n,
double *  diagptable_start,
const int  states,
double *  perSiteLikelihoods,
boolean  getPerSiteLikelihoods,
double *  x1_gapColumn,
double *  x2_gapColumn,
unsigned int *  x1_gap,
unsigned int *  x2_gap 
)
static

A generic (and slow) implementation of log likelihood evaluation of a tree using the CAT model of rate heterogeneity with memory saving.

This is the same as evaluateCAT_FLEX but with the memory saving technique enabled. Please check evaluateCAT_FLEX for more information and a description of the common input parameters

Parameters
x1_gapColumn
x2_gapColumn
x1_gapGap bitvector for the left child node
x2_gapGap bitvector for the right child node
Todo:
Comment on x1_gapColumn and x2_gapColumn

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static double evaluateGAMMA_FLEX ( const boolean  fastScaling,
int *  ex1,
int *  ex2,
int *  wptr,
double *  x1_start,
double *  x2_start,
double *  tipVector,
unsigned char *  tipX1,
const int  n,
double *  diagptable,
const int  states,
double *  perSiteLikelihoods,
boolean  getPerSiteLikelihoods 
)
static

A generic (and slow) implementation of log likelihood evaluation of a tree using the GAMMA model of rate heterogeneity.

Computes the log likelihood of the topology for a specific partition, assuming that the GAMMA model of rate heterogeneity is used. The likelihood is computed at a virtual root placed at an edge whose two end-points (nodes) have the conditional likelihood vectors x1 and x2. Furthermore, if getPerSiteLikelihoods is set to PLL_TRUE, then the log likelihood for each site is also computed and stored at the corresponding position in the array perSiteLikelihoods.

Parameters
fastScalingIf set to PLL_FALSE, then the likelihood of each site is also multiplied by log(PLL_MINLIKELIHOOD) times the number of times it has been scaled down
ex1An array that holds how many times a site has been scaled and points at the entries for node p. This parameter is used if fastScaling is set to PLL_FALSE.
ex2An array that holds how many times a site has been scaled and points at the entries for node q. This parameter is used if fastScaling is set to PLL_TRUE.
wptrArray holding the weight for each site in the compressed partition alignment
x1_startConditional likelihood vectors for one of the two end-points of the specific edge for which we are evaluating the likelihood
x2_startConditional likelihood vectors for the other end-point of the specific edge for which we are evaluating the likelihood
tipVectorPrecomputed table where the number of rows is equal to the number of possible basepair characters for the current data type, i.e.16 for DNA and 23 for AA, and each rows contains states elements each of which contains transition probabilities computed from the eigenvectors of the decomposed Q matrix.
tipX1If one of the two end-points (nodes) of the specific edge (for which we are evaluating the likelihood) is a tip, then this holds a pointer to the sequence data (basepairs) already converted in the internal integer representation, and x2 holds the conditional likelihood vectors for the internal node.
nNumber of sites for which we are doing the evaluation. For the single-thread version this is the number of sites in the current partition, for multi-threads this is the number of sites assigned to the running thread from the current partition.
diagptableStart of the array that contains the P-Matrix diagonal of the specific edge for which we are evaluating the likehood, and for each category of the GAMMA model
statesNumber of states (4 for DNA, 20 for AA)
perSiteLikelihoodsArray to store per-site log likelihoods if getPerSiteLikelihoods is set to PLL_TRUE
getPerSiteLikelihoodsIf set to PLL_TRUE then per-site log likelihoods are also computed and stored in perSiteLikelihoods
Returns
The evaluated log likelihood of the tree topology

+ Here is the caller graph for this function:

static double evaluateGAMMA_FLEX_SAVE ( const boolean  fastScaling,
int *  ex1,
int *  ex2,
int *  wptr,
double *  x1_start,
double *  x2_start,
double *  tipVector,
unsigned char *  tipX1,
const int  n,
double *  diagptable,
const int  states,
double *  perSiteLikelihoods,
boolean  getPerSiteLikelihoods,
double *  x1_gapColumn,
double *  x2_gapColumn,
unsigned int *  x1_gap,
unsigned int *  x2_gap 
)
static

Memory saving version of the generic (and slow) implementation of log likelihood evaluation of a tree using the GAMMA model of rate heterogeneity.

Computes the log likelihood of the topology for a specific partition, assuming that the GAMMA model of rate heterogeneity is used and memory saving technique is enabled. The likelihood is computed at a virtual root placed at an edge whose two end-points (nodes) have the conditional likelihood vectors x1 and x2. Furthermore, if getPerSiteLikelihoods is set to PLL_TRUE, then the log likelihood for each site is also computed and stored at the corresponding position in the array perSiteLikelihoods.

Parameters
fastScalingIf set to PLL_FALSE, then the likelihood of each site is also multiplied by log(PLL_MINLIKELIHOOD) times the number of times it has been scaled down
ex1An array that holds how many times a site has been scaled and points at the entries for node p. This parameter is used if fastScaling is set to PLL_FALSE.
ex2An array that holds how many times a site has been scaled and points at the entries for node q. This parameter is used if fastScaling is set to PLL_TRUE.
wptrArray holding the weight for each site in the compressed partition alignment
x1_startConditional likelihood vectors for one of the two end-points of the specific edge for which we are evaluating the likelihood
x2_startConditional likelihood vectors for the other end-point of the specific edge for which we are evaluating the likelihood
tipVectorPrecomputed table where the number of rows is equal to the number of possible basepair characters for the current data type, i.e.16 for DNA and 23 for AA, and each rows contains states elements each of which contains transition probabilities computed from the eigenvectors of the decomposed Q matrix.
tipX1If one of the two end-points (nodes) of the specific edge (for which we are evaluating the likelihood) is a tip, then this holds a pointer to the sequence data (basepairs) already converted in the internal integer representation, and x2 holds the conditional likelihood vectors for the internal node.
nNumber of sites for which we are doing the evaluation. For the single-thread version this is the number of sites in the current partition, for multi-threads this is the number of sites assigned to the running thread from the current partition.
diagptableStart of the array that contains the P-Matrix diagonal of the specific edge for which we are evaluating the likehood, and for each category of the GAMMA model
statesNumber of states (4 for DNA, 20 for AA)
perSiteLikelihoodsArray to store per-site log likelihoods if getPerSiteLikelihoods is set to PLL_TRUE
getPerSiteLikelihoodsIf set to PLL_TRUE then per-site log likelihoods are also computed and stored in perSiteLikelihoods
x1_gapColumn
x2_gapColumn
x1_gapGap bitvector for the left child node
x2_gapGap bitvector for the right child node
Returns
The evaluated log likelihood of the tree topology
Todo:
Document x1_gapColumn, x2_gapColumn, x1_gap, x2_gap and add a brief description of how this technique works

+ Here is the caller graph for this function:

static double evaluateGTRCAT ( const boolean  fastScaling,
int *  ex1,
int *  ex2,
int *  cptr,
int *  wptr,
double *  x1_start,
double *  x2_start,
double *  tipVector,
unsigned char *  tipX1,
int  n,
double *  diagptable_start 
)
static

Evaluation of log likelihood of a tree using the CAT model of rate heterogeneity (Optimized SSE3 version for DNA data)

This is the SSE3 optimized version of evaluateCAT_FLEX for evaluating the log likelihood at some edge whose two end-points (nodes) have the conditional likelihood vectors x1 and x2. Please check evaluateCAT_FLEX for more information and a description of the common input parameters

+ Here is the caller graph for this function:

static double evaluateGTRCAT_SAVE ( const boolean  fastScaling,
int *  ex1,
int *  ex2,
int *  cptr,
int *  wptr,
double *  x1_start,
double *  x2_start,
double *  tipVector,
unsigned char *  tipX1,
int  n,
double *  diagptable_start,
double *  x1_gapColumn,
double *  x2_gapColumn,
unsigned int *  x1_gap,
unsigned int *  x2_gap 
)
static

Evaluation of log likelihood of a tree using the CAT model of rate heterogeneity with memory saving (Optimized SSE3 version for DNA data)

This is the SSE3 optimized version of evaluateCAT_FLEX_SAVE for evaluating the log likelihood at some edge whose two end-points (nodes) have the conditional likelihood vectors x1 and x2. Please check evaluateCAT_FLEX_SAVE for more information and a description of the common input parameters

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static double evaluateGTRCATPROT ( const boolean  fastScaling,
int *  ex1,
int *  ex2,
int *  cptr,
int *  wptr,
double *  x1,
double *  x2,
double *  tipVector,
unsigned char *  tipX1,
int  n,
double *  diagptable_start 
)
static

Evaluation of log likelihood of a tree using the CAT model of rate heterogeneity (Optimized SSE3 version for AA data)

This is the SSE3 optimized version of evaluateCAT_FLEX for evaluating the log likelihood at some edge whose two end-points (nodes) have the conditional likelihood vectors x1 and x2. Please check evaluateCAT_FLEX for more information and a description of the common input parameters

+ Here is the caller graph for this function:

static double evaluateGTRCATPROT_SAVE ( const boolean  fastScaling,
int *  ex1,
int *  ex2,
int *  cptr,
int *  wptr,
double *  x1,
double *  x2,
double *  tipVector,
unsigned char *  tipX1,
int  n,
double *  diagptable_start,
double *  x1_gapColumn,
double *  x2_gapColumn,
unsigned int *  x1_gap,
unsigned int *  x2_gap 
)
static

Evaluation of log likelihood of a tree using the CAT model of rate heterogeneity with memory saving (Optimized SSE3 version for AA data)

This is the SSE3 optimized version of evaluateCAT_FLEX_SAVE for evaluating the log likelihood at some edge whose two end-points (nodes) have the conditional likelihood vectors x1 and x2. Please check evaluateCAT_FLEX_SAVE for more information and a description of the common input parameters

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static double evaluateGTRGAMMA ( const boolean  fastScaling,
int *  ex1,
int *  ex2,
int *  wptr,
double *  x1_start,
double *  x2_start,
double *  tipVector,
unsigned char *  tipX1,
const int  n,
double *  diagptable 
)
static

Evaluation of log likelihood of a tree using the GAMMA model of rate heterogeneity (Optimized SSE3 version for DNA data)

This is the SSE3 optimized version of evaluateGAMMA_FLEX for evaluating the log likelihood at some edge whose two end-points (nodes) have the conditional likelihood vectors x1 and x2. Please check evaluateGAMMA_FLEX for more information and a description of the common input parameters

+ Here is the caller graph for this function:

static double evaluateGTRGAMMA_GAPPED_SAVE ( const boolean  fastScaling,
int *  ex1,
int *  ex2,
int *  wptr,
double *  x1_start,
double *  x2_start,
double *  tipVector,
unsigned char *  tipX1,
const int  n,
double *  diagptable,
double *  x1_gapColumn,
double *  x2_gapColumn,
unsigned int *  x1_gap,
unsigned int *  x2_gap 
)
static

Evaluation of log likelihood of a tree using the GAMMA model of rate heterogeneity with memory saving (Optimized SSE3 version for DNA data)

This is the SSE3 optimized version of evaluateGAMMA_FLEX_SAVE for evaluating the log likelihood at some edge whose two end-points (nodes) have the conditional likelihood vectors x1 and x2. Please check evaluateGAMMA_FLEX_SAVE for more information and a description of the common input parameters

+ Here is the caller graph for this function:

static double evaluateGTRGAMMAPROT ( const boolean  fastScaling,
int *  ex1,
int *  ex2,
int *  wptr,
double *  x1,
double *  x2,
double *  tipVector,
unsigned char *  tipX1,
int  n,
double *  diagptable 
)
static

Evaluation of log likelihood of a tree using the GAMMA model of rate heterogeneity (Optimized SSE3 version for AA data)

This is the SSE3 optimized version of evaluateGAMMA_FLEX for evaluating the log likelihood at some edge whose two end-points (nodes) have the conditional likelihood vectors x1 and x2. Please check evaluateGAMMA_FLEX for more information and a description of the common input parameters

+ Here is the caller graph for this function:

static double evaluateGTRGAMMAPROT_GAPPED_SAVE ( const boolean  fastScaling,
int *  ex1,
int *  ex2,
int *  wptr,
double *  x1,
double *  x2,
double *  tipVector,
unsigned char *  tipX1,
int  n,
double *  diagptable,
double *  x1_gapColumn,
double *  x2_gapColumn,
unsigned int *  x1_gap,
unsigned int *  x2_gap 
)
static

Evaluation of log likelihood of a tree using the GAMMA model of rate heterogeneity and the memory saving technique (Optimized SSE3 version for AA data)

This is the SSE3 optimized version of evaluateGAMMA_FLEX_SAVE for evaluating the log likelihood at some edge whose two end-points (nodes) have the conditional likelihood vectors x1 and x2. Please check evaluateGAMMA_FLEX_SAVE for more information and a description of the input parameters

+ Here is the caller graph for this function:

static double evaluateGTRGAMMAPROT_LG4 ( int *  ex1,
int *  ex2,
int *  wptr,
double *  x1,
double *  x2,
double *  tipVector[4],
unsigned char *  tipX1,
int  n,
double *  diagptable,
const boolean  fastScaling 
)
static

Evaluation of log likelihood of a tree under the GAMMA model of rate heterogeneity and LG4 model of evolution.

This is the same as evaluateGAMMA_FLEX but for the LG4 model. It contains two implementations, one which is the generic, and one that is optimized with SSE3 instructions. The two implementations are separated by preprocessor macros. The difference from evaluateGAMMA_FLEX is that we have 4 different tipVectors computed from the 4 different Q matrix decompositions. Please check evaluateGAMMA_FLEX for more information and a description of the common input parameters.

+ Here is the caller graph for this function:

void pllEvaluateGeneric ( pllInstance tr,
partitionList pr,
nodeptr  p,
boolean  fullTraversal,
boolean  getPerSiteLikelihoods 
)

Evaluate the log likelihood of the tree topology.

Evaluate the log likelihood of the tree topology of instance tr by assuming a virtual root between nodes p and p->back. If fullTraversal is set to PLL_TRUE then the log likelihood vectors for each node are recomputed from scratch.

Parameters
trPLL instance
prList of partitions
pSpecifies the virtual root, which is assumed to be a (virtual node) connecting p and p->back
fullTraversalIf set to PLL_TRUE, then the likelihood vectors at all nodes are recomputed, otherwise only the necessary vectors (those that are not oriented in the right direction) are recomputed.
getPerSiteLikelihoodsAlso compute and store (in tr->lhs) the log likelihood of each site of the (compressed) alignment
Note
If getPerSiteLikelihoods is set to PLL_TRUE, then make sure that tr->fastScaling is set to PLL_FALSE, otherwise an assertion will fail.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void pllEvaluateIterative ( pllInstance tr,
partitionList pr,
boolean  getPerSiteLikelihoods 
)

Evaluate the log likelihood of a specific branch of the topology.

Evaluates the likelihood of the tree topology assuming a virtual root is placed at the edge whose end-points are node with number pNumber and qNumber in the first slot of the traversal descriptor. The function first computes the conditional likelihoods for all necessary nodes (the ones in the traversal descriptor list) by calling the function pllNewviewIterative and then evaluates the likelihood at the root. In addition, if getPerSiteLikelihoods is set to PLL_TRUE, the per-site likelihoods are stored in tr->lhs.

Parameters
trPLL instance
prList of partitions
getPerSiteLikelihoodsIf set to PLL_TRUE, compute the log likelihood for each site.
Note
This is an internal function and should not be called by the user. It assumes that a valid traversal descriptor has already been computed. It also assumes that the edge we are referring to is an edge that leads to a tip, i.e. either p or q of the first entry of traversal descriptor are tips.

+ Here is the call graph for this function:

+ Here is the caller graph for this function: