Stree Class Reference

Class of compact Safra trees used for Piterman's NBW to DPW procedure. More...

#include <Stree.hh>

Public Member Functions
	Stree (void)
	Constructor.
int	size (void) const
	Returns the number of nodes in the tree.
std::set< State >	getLabel (int node) const
	Returns the set of states that label a node of the tree.
void	setLabel (int node, std::set< State > newlabel)
	Sets the label of a node in the tree.
void	addLastChild (int parent, std::set< State > const &childLabel)
	Adds a node to the tree as last child of "parent.".
void	removeSubtree (int node)
	Removes the subtree rooted at "node.".
void	makeContiguous (void)
	Gives contiguous numbers to the nodes of the tree.
void	restrictLabels (void)
	Restricts the label of a node to help restore the tree invariant.
bool	isGreen (int node) const
	Checks whether node of tree "flashes green.".
void	removeDescendants (int node)
	Removes the descendants of a node from the tree.
void	preorder (std::vector< int > &order) const
	Returns the nodes of the tree in preorder.
bool	isIsomorphic (Stree const &other, int root=0, int otherRoot=0) const
	Compares two trees.
std::string	toString (void) const
	Returns a string describing the tree.
std::string	toDot (std::string graphname=std::string("tree"), std::string subgraph=std::string("")) const
	Converts the tree to dot format. More...

Static Public Attributes
static constexpr int	undef = -1
	Index of an undefined node.

Detailed Description

Class of compact Safra trees used for Piterman's NBW to DPW procedure.

These are multiway branching trees where each child points to its parent and each parent points to the youngest of its children. Each node also points to younger and elder sibling.

Member Function Documentation

toDot()

string Stree::toDot	(	std::string	graphname = std::string("tree"),
		std::string	subgraph = std::string("")
	)		const

Converts the tree to dot format.

If subgraph is nonempty, create a cluster instead of a top-level graph. Use subgraph as the cluster name and as prefix to the node names for disambiguation.

---

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

• LTS/Stree.hh
• LTS/Stree.cc