TTK
Loading...
Searching...
No Matches
Classes | Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
ttk::LowestCommonAncestor Class Reference

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:
ttk::Debug ttk::BaseClass

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.
 
NodegetNode (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)
 

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< Nodenode_ {}
 
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_
 
Wrapperwrapper_
 

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 175 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: