KrisLibrary
1.0.0
|
A tree-based chain structure. More...
#include <Chain.h>
Public Types | |
enum | { NoParent = -1 } |
Public Member Functions | |
bool | HasValidOrdering () const |
bool | IsAncestor (int n, int p) const |
Returns true if p is an ancestor of n. | |
bool | IsDescendent (int n, int c) const |
Returns true if c is a descendant of n. | |
int | LCA (int a, int b) const |
Least common ancestor. | |
void | GetChildList (std::vector< std::vector< int > > &children) const |
Returns a vector where element i is a vectors of the children of link i. | |
void | GetAncestors (int k, std::vector< bool > &ancestors) const |
Returns a vector where element i is true if it is an ancestor of n. | |
void | GetDescendants (int k, std::vector< bool > &descendants) const |
Returns a vector where element i is true if it is an descendant of n. | |
Public Attributes | |
std::vector< int > | parents |
Topologically sorted list of parents. | |
A tree-based chain structure.
Represents the tree as a topologically sorted list of parents. -1 represents no parent.