Graph Drawing Toolkit

An object-oriented C++ library for handling and drawing graphs

---

tree Class Reference

#include <rm3_tree.h>

Inheritance diagram for tree:

[legend]

Collaboration diagram for tree:

[legend]

List of all members.

Public Member Functions
	tree ()
	~tree ()
	tree (const undi_graph &ug, gdtnode v)
	tree (const tree &tr)
tree &	operator= (const undi_graph &)
tree &	operator= (const tree &)
void	local_get (gdtnode p1, gdt::gdtnode_map< struct_tree_node_info > *p2)
gdtnode	root_of_tree () const
gdtnode	father_node (gdtnode v) const
gdtnode	father_node (gdtedge e) const
gdtnode	first_son_node (gdtnode v) const
gdtnode	last_son_node (gdtnode v) const
gdtnode	son_succ (gdtnode w, gdtnode v) const
gdtnode	son_pred (gdtnode w, gdtnode v) const
gdtedge	father_edge (gdtnode v) const
gdtedge	father_edge (gdtedge e) const
gdtedge	first_son_edge (gdtnode v) const
gdtedge	last_son_edge (gdtnode v) const
gdtedge	son_succ (gdtedge e, gdtnode v) const
gdtedge	son_pred (gdtedge e, gdtnode v) const
int	get_level (gdtnode v) const
int	number_of_sons (gdtnode v) const
int	depth_of_subtree (gdtnode v=NULL_NODE, int i=0) const
int	BFS_of_subtree (gdt::gdtnode_array< int > &lev, gdt::gdtlist< gdtnode > &order, gdtnode v=NULL_NODE, int i=0) const
int	DFS_of_subtree (gdt::gdtnode_array< int > &lev, gdt::gdtlist< gdtnode > &order, gdtnode v=NULL_NODE, int i=0) const
int	post_order_of_subtree (gdt::gdtnode_array< int > &lev, gdt::gdtlist< gdtnode > &order, gdtnode v=NULL_NODE, int i=0) const
gdtnode	new_son_of_node (gdtnode v, int new_node_id=AUTO_ID, int new_edge_id=AUTO_ID)
gdtnode	new_son_of_node (gdtnode v, gdtnode w, int new_node_id=AUTO_ID, int new_edge_id=AUTO_ID, int dir=gdt::after)
void	make_root (gdtnode v)
void	del_subtree (gdtnode v)
void	clear ()
void	steal_from (undi_graph &ug, gdtnode)
void	mirror (tree &)
void	forget ()
void	print_tree (std::ostream &os=std::cout)
void	preprocessing_lca ()
gdtnode	LCA (gdtnode n1, gdtnode n2)

---

Detailed Description

CLASS tree A 'tree' represents a connected acyclic undi_graph with a gdtnode chosen as root. Each gdtnode of a tree, different from root, has a 'father_node', a 'father_edge', and an ordered linear list (left-right) of son-nodes. Also, each gdtnode has associated a level, that is the length of a shortest path from root to the given gdtnode (root is at level 0).

Definition at line 61 of file rm3_tree.h.

---

Constructor & Destructor Documentation

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.

---

Member Function Documentation

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.

tree& tree::operator=

(

const tree &

)

Copy equality operator.

void tree::local_get	(	gdtnode	p1,
		gdt::gdtnode_map< struct_tree_node_info > *	p2
	)

Get all private variables.

gdtnode tree::root_of_tree

(

)

const

Return the root-gdtnode of tree

gdtnode tree::father_node

(

gdtnode

v

)

const

Return the father gdtnode of gdtnode v.

gdtnode tree::father_node

(

gdtedge

e

)

const

Return the father gdtnode of gdtedge e.

gdtnode tree::first_son_node

(

gdtnode

v

)

const

Return the first son gdtnode of gdtnode v.

gdtnode tree::last_son_node

(

gdtnode

v

)

const

Return the last son gdtnode of gdtnode v.

gdtnode tree::son_succ	(	gdtnode	w,
		gdtnode	v
	)			const

Return the son gdtnode of gdtnode v, successive to gdtnode w.

gdtnode tree::son_pred	(	gdtnode	w,
		gdtnode	v
	)			const

Return the son gdtnode of gdtnode v, previous to gdtnode w.

gdtedge tree::father_edge

(

gdtnode

v

)

const

Return the father gdtedge of gdtnode v.

gdtedge tree::father_edge

(

gdtedge

e

)

const

Return the father gdtedge of gdtedge e.

gdtedge tree::first_son_edge

(

gdtnode

v

)

const

Return the first son gdtedge of gdtnode v.

gdtedge tree::last_son_edge

(

gdtnode

v

)

const

Return the last son gdtedge of gdtnode v.

gdtedge tree::son_succ	(	gdtedge	e,
		gdtnode	v
	)			const

Return the son gdtedge of gdtnode v, successive to gdtedge e.

gdtedge tree::son_pred	(	gdtedge	e,
		gdtnode	v
	)			const

Return the son gdtedge of gdtnode v, previous to gdtedge e.

int tree::get_level

(

gdtnode

v

)

const

Return the level of gdtnode v.

int tree::number_of_sons

(

gdtnode

v

)

const

Return the number of sons of gdtnode v.

int tree::depth_of_subtree	(	gdtnode	v = NULL_NODE,
		int	i = 0
	)			const

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

gdtnode tree::new_son_of_node	(	gdtnode	v,
		int	new_node_id = AUTO_ID,
		int	new_edge_id = AUTO_ID
	)

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

)

Evert tree, making gdtnode v as new root.

Reimplemented in SPQR_tree.

void tree::del_subtree

(

gdtnode

v

)

Delete the subtree rooted at v.

void tree::clear

(

)

Delete all nodes and edges.

Reimplemented from undi_graph.

Reimplemented in SPQR_tree.

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

(

tree &

)

Copy all private variables of tree in *this.

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.

gdtnode tree::LCA	(	gdtnode	n1,
		gdtnode	n2
	)

Find the lowest common ancestor (LCA) of two nodes. PRECONDITION: method preprocessing_lca must be applied.

---

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

• rm3_tree.h

---