Class that computes nearest common ancestors in a tree. More...

#include <Nca.h>

Collaboration diagram for grafalgo::Nca:

Classes
struct	VertexPair
Public Member Functions
	Nca (Graph &, vertex, VertexPair[], int, vertex[])
	Compute nearest common ancestors of specified pairs of vertices.
Private Types
enum	state_t { unreached, open, closed }
Private Member Functions
void	compute_nca (vertex, vertex)
	Recursive computation of nca values.
Private Attributes
Graph *	tp
vertex	root
VertexPair *	pairs
int	np
vertex *	ncav
Graph *	gp
Partition *	pp
vertex *	noa
state_t *	state

Detailed Description

Class that computes nearest common ancestors in a tree.

The computation is invoked using the constructor.

Definition at line 23 of file Nca.h.

Constructor & Destructor Documentation

Compute nearest common ancestors of specified pairs of vertices.

Parameters:

t	is a reference to a graph object that is a tree
root1	is the root of the tree
pairs1	is an array of VertexPair structures that identify the pairs of vertices for which we compute ncas
np1	is the number of pairs in pairs1
ncav1	is an array in which the nca values are returned

Definition at line 21 of file Nca.cpp.

Here is the call graph for this function:

void grafalgo::Nca::compute_nca	(	vertex	u,
		vertex	pu
	)		`[private]`

Recursive computation of nca values.

Parameters:

u	is the current vertex in the recursive computation
pu	is the parent of u; in the top-level call pu==0

Definition at line 43 of file Nca.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

The documentation for this class was generated from the following files: