KrisLibrary  1.0.0
Chain.h
1 #ifndef ROBOTICS_CHAIN_H
2 #define ROBOTICS_CHAIN_H
3 
4 #include <vector>
5 
16 class Chain
17 {
18 public:
19  enum { NoParent = -1 };
20 
21  bool HasValidOrdering() const;
23  bool IsAncestor(int n, int p) const;
25  inline bool IsDescendent(int n, int c) const { return IsAncestor(c,n);}
27  int LCA(int a,int b) const;
29  void GetChildList(std::vector<std::vector<int> >& children) const;
31  void GetAncestors(int k,std::vector<bool>& ancestors) const;
33  void GetDescendants(int k,std::vector<bool>& descendants) const;
34 
36  std::vector<int> parents;
37 };
38 
39 #endif
bool IsDescendent(int n, int c) const
Returns true if c is a descendant of n.
Definition: Chain.h:25
bool IsAncestor(int n, int p) const
Returns true if p is an ancestor of n.
Definition: Chain.cpp:13
std::vector< int > parents
Topologically sorted list of parents.
Definition: Chain.h:36
void GetAncestors(int k, std::vector< bool > &ancestors) const
Returns a vector where element i is true if it is an ancestor of n.
Definition: Chain.cpp:48
int LCA(int a, int b) const
Least common ancestor.
Definition: Chain.cpp:22
void GetChildList(std::vector< std::vector< int > > &children) const
Returns a vector where element i is a vectors of the children of link i.
Definition: Chain.cpp:36
A tree-based chain structure.
Definition: Chain.h:16
void GetDescendants(int k, std::vector< bool > &descendants) const
Returns a vector where element i is true if it is an descendant of n.
Definition: Chain.cpp:58