#include <rm3_tree.h>
Definition at line 61 of file rm3_tree.h.
tree::tree | ( | ) |
Empty constructor.
tree::~tree | ( | ) |
Destructor.
tree::tree | ( | const undi_graph & | ug, | |
gdtnode | v | |||
) |
Constructor from the undi_graph class. Node v will be the root. PRECONDITIONS: undi_graph must be acyclic and connected
tree::tree | ( | const tree & | tr | ) |
Copy constructor.
tree& tree::operator= | ( | const undi_graph & | ) |
Equality operator from the undi_graph. Root will be the first_node() of undi_graph. PRECONDITIONS: undi_graph must be acyclic and connected
Reimplemented from undi_graph.
void tree::local_get | ( | gdtnode | p1, | |
gdt::gdtnode_map< struct_tree_node_info > * | p2 | |||
) |
Get all private variables.
Return the son gdtnode of gdtnode v, successive to gdtnode w.
Return the son gdtnode of gdtnode v, previous to gdtnode w.
Return the son gdtedge of gdtnode v, successive to gdtedge e.
Return the son gdtedge of gdtnode v, previous to gdtedge e.
Return the depth of subtree rooted at v, with respect to the start-level i. NOTE: if v = NULL_NODE, assume v as root gdtnode.
int tree::BFS_of_subtree | ( | gdt::gdtnode_array< int > & | lev, | |
gdt::gdtlist< gdtnode > & | order, | |||
gdtnode | v = NULL_NODE , |
|||
int | i = 0 | |||
) | const |
Execute a BFS of subtree rooted at v, scanning the sons of all nodes of subtree from left to right. NOTE: if v = NULL_NODE assume v as root gdtnode. lev[w] = level of gdtnode w with respect to the start-level i order = ordered list of visited nodes. Method returns the depth of the subtree from the start-level i. (ADVICE: the start-level i is not the v level in the general case, but only a reference start level).
int tree::DFS_of_subtree | ( | gdt::gdtnode_array< int > & | lev, | |
gdt::gdtlist< gdtnode > & | order, | |||
gdtnode | v = NULL_NODE , |
|||
int | i = 0 | |||
) | const |
Execute a DFS of subtree rooted at v, scanning the sons of all nodes of subtree from left to right. NOTE: if v = NULL_NODE assume v = root. lev[w] = level of gdtnode w with respect to the start-level i order = ordered list of visited nodes. Method returns the depth of the subtree from the start-level i. (ADVICE: the start-level i is not the v level in the general case, but only a reference start level).
int tree::post_order_of_subtree | ( | gdt::gdtnode_array< int > & | lev, | |
gdt::gdtlist< gdtnode > & | order, | |||
gdtnode | v = NULL_NODE , |
|||
int | i = 0 | |||
) | const |
Execute a post-order visit of subtree rooted v (a gdtnode is visited only after that all its sons are visited). NOTE: if v = NULL_NODE assume v = root. lev[w] = level of gdtnode w with respect to the start-level i order = ordered list of visited nodes. Method returns the depth of the subtree from the start-level i. (ADVICE: the start-level i is not the v level in the general case, but only a reference start level).
Append, and return, a new son gdtnode to gdtnode v; new_node_id and new_edge_id will be the son gdtnode- and son gdtedge-identifier, respectively.
gdtnode tree::new_son_of_node | ( | gdtnode | v, | |
gdtnode | w, | |||
int | new_node_id = AUTO_ID , |
|||
int | new_edge_id = AUTO_ID , |
|||
int | dir = gdt::after | |||
) |
Append after(before) son gdtnode w, and return, a new son gdtnode to gdtnode v; new_node_id and new_edge_id will be the son gdtnode- and son gdtedge-identifier, respectively.
void tree::make_root | ( | gdtnode | v | ) |
void tree::del_subtree | ( | gdtnode | v | ) |
Delete the subtree rooted at v.
void tree::clear | ( | ) |
void tree::steal_from | ( | undi_graph & | ug, | |
gdtnode | ||||
) |
Make *this with the undi_graph ug internal variables and cut these variables from ug. This method is used to make an undi_graph as a tree, manteining the same internal variables. WARNING: ug has an empty body after this method is applied PRECONDITIONS: ug must be acyclic and connected
void tree::forget | ( | ) |
Cut all private variables in *this.
Reimplemented from undi_graph.
void tree::print_tree | ( | std::ostream & | os = std::cout |
) |
Print the graph on ostream os.
void tree::preprocessing_lca | ( | ) |
Perform the preprocessing phase of the Schieber and Vishkin algorithm. This preprocessing allows to find the Lowest Common Ancestor of two nodes in constant time.
Find the lowest common ancestor (LCA) of two nodes. PRECONDITION: method preprocessing_lca must be applied.