Class to answer the lowest common ancestor requests of pairs of nodes in a tree in constant time after a linear time preprocess. More...

#include <LowestCommonAncestor.h>

Inheritance diagram for ttk::LowestCommonAncestor:

Classes
class	Node

Public Member Functions
	LowestCommonAncestor ()

int	addNode ()

void	addNodes (const unsigned int &number)

unsigned int	getNumberOfNodes () const
	Get the number of nodes in the tree.

Node &	getNode (const unsigned int &id)

int	preprocess ()

int	query (int i, int j) const

Public Member Functions inherited from ttk::Debug
	Debug ()

	~Debug () override

virtual int	setDebugLevel (const int &debugLevel)

int	setWrapper (const Wrapper *wrapper) override

int	printMsg (const std::string &msg, const debug::Priority &priority=debug::Priority::INFO, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cout) const

int	printMsg (const std::vector< std::string > &msgs, const debug::Priority &priority=debug::Priority::INFO, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cout) const

int	printErr (const std::string &msg, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cerr) const

int	printWrn (const std::string &msg, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cerr) const

int	printMsg (const std::string &msg, const double &progress, const double &time, const int &threads, const double &memory, const debug::LineMode &lineMode=debug::LineMode::NEW, const debug::Priority &priority=debug::Priority::PERFORMANCE, std::ostream &stream=std::cout) const

int	printMsg (const std::string &msg, const double &progress, const double &time, const debug::LineMode &lineMode=debug::LineMode::NEW, const debug::Priority &priority=debug::Priority::PERFORMANCE, std::ostream &stream=std::cout) const

int	printMsg (const std::string &msg, const double &progress, const double &time, const int &threads, const debug::LineMode &lineMode=debug::LineMode::NEW, const debug::Priority &priority=debug::Priority::PERFORMANCE, std::ostream &stream=std::cout) const

int	printMsg (const std::string &msg, const double &progress, const debug::LineMode &lineMode=debug::LineMode::NEW, const debug::Priority &priority=debug::Priority::PERFORMANCE, std::ostream &stream=std::cout) const

int	printMsg (const std::string &msg, const double &progress, const debug::Priority &priority, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cout) const

int	printMsg (const std::vector< std::vector< std::string > > &rows, const debug::Priority &priority=debug::Priority::INFO, const bool hasHeader=true, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cout) const

int	printMsg (const debug::Separator &separator, const debug::LineMode &lineMode=debug::LineMode::NEW, const debug::Priority &priority=debug::Priority::INFO, std::ostream &stream=std::cout) const

int	printMsg (const debug::Separator &separator, const debug::Priority &priority, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cout) const

int	printMsg (const std::string &msg, const debug::Separator &separator, const debug::LineMode &lineMode=debug::LineMode::NEW, const debug::Priority &priority=debug::Priority::INFO, std::ostream &stream=std::cout) const

void	setDebugMsgPrefix (const std::string &prefix)

Public Member Functions inherited from ttk::BaseClass
	BaseClass ()

virtual	~BaseClass ()=default

int	getThreadNumber () const

virtual int	setThreadNumber (const int threadNumber)

virtual int	setWrapper (const Wrapper *wrapper)

Protected Member Functions
int	computeBlocs ()

int	eulerianTransverse ()

int	RMQuery (const int &i, const int &j) const

unsigned int	min_pos_3 (const std::array< int, 3 > &triplet) const

Protected Member Functions inherited from ttk::Debug
int	printMsgInternal (const std::string &msg, const std::string &right, const std::string &filler, const debug::Priority &priority=debug::Priority::INFO, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cout) const

int	printMsgInternal (const std::string &msg, const debug::Priority &priority, const debug::LineMode &lineMode, std::ostream &stream=std::cout) const

int	welcomeMsg (std::ostream &stream)

Protected Attributes
std::vector< Node >	node_ {}

std::vector< int >	nodeOrder_ {}

std::vector< int >	nodeDepth_ {}

std::vector< int >	nodeFirstAppearance_ {}

int	blocSize_ {}

std::vector< std::pair< int, int > >	blocPartition_ {}

std::vector< int >	blocMinimumValue_ {}

RangeMinimumQuery< int >	blocMinimumValueRMQ_ {}

std::vector< int >	blocMinimumPosition_ {}

std::vector< std::vector< std::vector< int > > >	normalizedBlocTable_ {}

std::vector< int >	blocToNormalizedBloc_ {}

Protected Attributes inherited from ttk::Debug
int	debugLevel_

std::string	debugMsgPrefix_

std::string	debugMsgNamePrefix_

Protected Attributes inherited from ttk::BaseClass
bool	lastObject_

int	threadNumber_

Wrapper *	wrapper_

Additional Inherited Members
Static Protected Attributes inherited from ttk::Debug
static COMMON_EXPORTS debug::LineMode	lastLineMode = ttk::debug::LineMode::NEW

Detailed Description

Class to answer the lowest common ancestor requests of pairs of nodes in a tree in constant time after a linear time preprocess.

Author: Michael Michaux micha.nosp@m.uxmi.nosp@m.chael.nosp@m.89@g.nosp@m.mail..nosp@m.com

Date: August 2016.

Definition at line 20 of file LowestCommonAncestor.h.

Constructor & Destructor Documentation

◆ LowestCommonAncestor()

ttk::LowestCommonAncestor::LowestCommonAncestor ( )

Definition at line 10 of file LowestCommonAncestor.cpp.

Member Function Documentation

◆ addNode()

int ttk::LowestCommonAncestor::addNode ( )

inline

Add a node in the tree

Returns: Returns the id of the new node

Definition at line 53 of file LowestCommonAncestor.h.

◆ addNodes()

void ttk::LowestCommonAncestor::addNodes ( const unsigned int & number )

inline

Definition at line 60 of file LowestCommonAncestor.h.

◆ computeBlocs()

int ttk::LowestCommonAncestor::computeBlocs ( )

protected

Definition at line 80 of file LowestCommonAncestor.cpp.

◆ eulerianTransverse()

int ttk::LowestCommonAncestor::eulerianTransverse ( )

protected

Definition at line 174 of file LowestCommonAncestor.cpp.

◆ getNode()

Node & ttk::LowestCommonAncestor::getNode ( const unsigned int & id )

inline

Returns: Returns a pointer to the id-th node

Definition at line 73 of file LowestCommonAncestor.h.

◆ getNumberOfNodes()

unsigned int ttk::LowestCommonAncestor::getNumberOfNodes ( ) const

inline

Get the number of nodes in the tree.

Definition at line 68 of file LowestCommonAncestor.h.

◆ min_pos_3()

unsigned int ttk::LowestCommonAncestor::min_pos_3 ( const std::array< int, 3 > & triplet ) const

inlineprotected

Definition at line 96 of file LowestCommonAncestor.h.

◆ preprocess()

int ttk::LowestCommonAncestor::preprocess ( )

Preprocess the tree structure to answer the query() calls in constant time. The preprocess takes linear time in number of nodes in the tree.

Definition at line 14 of file LowestCommonAncestor.cpp.

◆ query()

int ttk::LowestCommonAncestor::query	(	int	i,
		int	j
	)		const

inline

Get the id of the lowest common ancestor of i and j.

Precondition: preprocess() must have been called after the last change in the tree.

Definition at line 84 of file LowestCommonAncestor.h.

◆ RMQuery()

int ttk::LowestCommonAncestor::RMQuery	(	const int &	i,
		const int &	j
	)		const

protected

Definition at line 44 of file LowestCommonAncestor.cpp.

Member Data Documentation

◆ blocMinimumPosition_

std::vector<int> ttk::LowestCommonAncestor::blocMinimumPosition_ {}

protected

Definition at line 130 of file LowestCommonAncestor.h.

◆ blocMinimumValue_

std::vector<int> ttk::LowestCommonAncestor::blocMinimumValue_ {}

protected

Definition at line 126 of file LowestCommonAncestor.h.

◆ blocMinimumValueRMQ_

RangeMinimumQuery<int> ttk::LowestCommonAncestor::blocMinimumValueRMQ_ {}

protected

Definition at line 128 of file LowestCommonAncestor.h.

◆ blocPartition_

std::vector<std::pair<int, int> > ttk::LowestCommonAncestor::blocPartition_ {}

protected

Definition at line 124 of file LowestCommonAncestor.h.

◆ blocSize_

int ttk::LowestCommonAncestor::blocSize_ {}

protected

Definition at line 122 of file LowestCommonAncestor.h.

◆ blocToNormalizedBloc_

std::vector<int> ttk::LowestCommonAncestor::blocToNormalizedBloc_ {}

protected

Definition at line 134 of file LowestCommonAncestor.h.

◆ node_

std::vector<Node> ttk::LowestCommonAncestor::node_ {}

protected

Definition at line 114 of file LowestCommonAncestor.h.

◆ nodeDepth_

std::vector<int> ttk::LowestCommonAncestor::nodeDepth_ {}

protected

Definition at line 118 of file LowestCommonAncestor.h.

◆ nodeFirstAppearance_

std::vector<int> ttk::LowestCommonAncestor::nodeFirstAppearance_ {}

protected

Definition at line 119 of file LowestCommonAncestor.h.

◆ nodeOrder_

std::vector<int> ttk::LowestCommonAncestor::nodeOrder_ {}

protected

Definition at line 117 of file LowestCommonAncestor.h.

◆ normalizedBlocTable_

std::vector<std::vector<std::vector<int> > > ttk::LowestCommonAncestor::normalizedBlocTable_ {}

protected

Definition at line 132 of file LowestCommonAncestor.h.

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

/home/julien/Pro/git/github/ttk-tierny/core/base/lowestCommonAncestor/LowestCommonAncestor.h
/home/julien/Pro/git/github/ttk-tierny/core/base/lowestCommonAncestor/LowestCommonAncestor.cpp

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ LowestCommonAncestor()

Member Function Documentation

◆ addNode()

◆ addNodes()

◆ computeBlocs()

◆ eulerianTransverse()

◆ getNode()

◆ getNumberOfNodes()

◆ min_pos_3()

◆ preprocess()

◆ query()

◆ RMQuery()

Member Data Documentation

◆ blocMinimumPosition_

◆ blocMinimumValue_

◆ blocMinimumValueRMQ_

◆ blocPartition_

◆ blocSize_

◆ blocToNormalizedBloc_

◆ node_

◆ nodeDepth_

◆ nodeFirstAppearance_

◆ nodeOrder_

◆ normalizedBlocTable_