Tree Class Reference

Public Member Functions
void	readSegmentsFile (std::string)
Node *	getRoot ()
int	getTreeSize ()
int	getTotalTrapezoids ()
void	insert (Segment *)
void	printTree (Node *, int=0)
void	addLeafNodes (Node *)
void	deleteLeafNodes (Node *)
void	setupLists (Node *)
void	printLists ()
void	initAdjacencyMatrix ()
void	writeAdjacencyMatrix (Node *)
void	writeSumsAdjacencyMatrix ()
void	printAdjacencyMatrix ()
void	writeAdjacencyMatrixToFile (std::string)
void	findPoint (int, int, Node *)
void	findPrivatePoint (Encryptor &, PrivPointUtil *, helib::Ctxt, helib::Ctxt &, helib::Ctxt, Node *, int, int)
void	cleanTree (Node *)
void	setupPathLabels (Node *, std::string)
void	printPathLabels ()
std::vector< std::string >	getAllPaths ()
void	evaluateOnePath (Encryptor &, PrivPointUtil *, helib::Ctxt, helib::Ctxt &, int, int, std::string)
void	getPathResult (Encryptor &, PrivPointUtil *, helib::Ctxt, helib::Ctxt &, int, int, std::string)
helib::Ctxt	evaluateAllNodes (Encryptor &, PrivPointUtil *, helib::Ctxt, int, int)

Member Function Documentation

addLeafNodes()

void Tree::addLeafNodes

(

Node *

node

)

Traverse the tree recursively after new X and Y nodes have been added, and fill in new leaf nodes

Parameters

Node	* startNode - starting from this node then traverse to all children

Returns

void

cleanTree()

void Tree::cleanTree

(

Node *

startNode

)

Clean Tree updates the IDs of the Leaf nodes so they start from 0 and end at totalTrapezoids-1

Parameters

Node	* startNode - traverse starting from this node as root

Returns

void

deleteLeafNodes()

void Tree::deleteLeafNodes

(

Node *

node

)

Delete leaf nodes in the subtree specified by the Node input

Parameters

Node	* startNode - starting from this node then traverse to all children

Returns

void

evaluateAllNodes()

helib::Ctxt Tree::evaluateAllNodes	(	Encryptor &	encryptor,
		PrivPointUtil *	privUtil,
		helib::Ctxt	pointCtxt,
		int	maxBits,
		int	nSlots
	)

Main function to run the parallel point location. First evaluates all the nodes in parallel, then calls getPathResult for each path in parallel. Uses OpenMP to coordinate parallelization and accumulate results in one ciphertext to return to the user.

Parameters

Encryptor	& - encryptor object
PrivPointUtil	* - privPointUtil object pointer
helib::Ctxt	pointCtxt - ciphertext encoding the point [–x–, –y–]
int	maxBits - bit length of encoded binary numbers
int	nSlots - slot count of the ciphertexts (the size of vector underneath the ciphertext)

Returns

helib::Ctxt - result

evaluateOnePath()

void Tree::evaluateOnePath	(	Encryptor &	encryptor,
		PrivPointUtil *	privUtil,
		helib::Ctxt	pointCtxt,
		helib::Ctxt &	resultCtxt,
		int	maxBits,
		int	nSlots,
		std::string	pathLabel
	)

Evaluates just one Path homomorphically - used for debugging one path.

Parameters

Encryptor	& - encryptor object
PrivPointUtil	* - privPointUtil object pointer
helib::Ctxt	pointCtxt - ciphertext encoding the point [–x–, –y–]
helib::Ctxt	& resultCtxt - accumulates the result
int	maxBits - bit length of encoded binary numbers
int	nSlots - slot count of the ciphertexts (the size of vector underneath the ciphertext)
std::string	- label of the path to test

Returns

void (result updated by reference)

findPoint()

void Tree::findPoint	(	int	x,
		int	y,
		Node *	startNode
	)

Plaintext version of planar point location

Parameters

int	x
int	y
int	Node * startNode

Returns

void

findPrivatePoint()

void Tree::findPrivatePoint	(	Encryptor &	encryptor,
		PrivPointUtil *	privUtil,
		helib::Ctxt	pointCtxt,
		helib::Ctxt &	resultCtxt,
		helib::Ctxt	tmpResult,
		Node *	startNode,
		int	maxBits,
		int	nSlots
	)

Privacy Preserving planar point location – NO Parallelization. Returns a ciphertext with the result. Runs without any parallelization

Parameters

Encryptor	& - encryptor object
PrivPointUtil	* - privPointUtil object pointer
helib::Ctxt	pointCtxt - ciphertext encoding the point [–x–, –y–]
helib::Ctxt	& resultCtxt - accumulates the result

Returns

void (result updated by reference)

getAllPaths()

std::vector< std::string > Tree::getAllPaths

(

)

Returns the allPaths vector, containing all paths in the structure

Parameters

void

Returns

std::vector<std::string> allPaths

getPathResult()

void Tree::getPathResult	(	Encryptor &	encryptor,
		PrivPointUtil *	privUtil,
		helib::Ctxt	pointCtxt,
		helib::Ctxt &	resultCtxt,
		int	maxBits,
		int	nSlots,
		std::string	pathLabel
	)

Used for parallel processing of the paths. This function is used after all nodes have been evaluated and assumes they store the correct result This function traverses the path accumulating the node results (through AND/*).

Parameters

Encryptor	& - encryptor object
PrivPointUtil	* - privPointUtil object pointer
helib::Ctxt	pointCtxt - ciphertext encoding the point [–x–, –y–]
helib::Ctxt	& resultCtxt - accumulates the result
int	maxBits - bit length of encoded binary numbers
int	nSlots - slot count of the ciphertexts (the size of vector underneath the ciphertext)
std::string	- label of the path

Returns

void (result updated by reference)

getRoot()

Node * Tree::getRoot

(

)

Return a pointer to the Node which is the root of the Tree

Parameters

void

Returns

Node *

getTotalTrapezoids()

int Tree::getTotalTrapezoids

(

)

Get the total leaf nodes in the tree

Parameters

void

Returns

int

getTreeSize()

int Tree::getTreeSize

(

)

Get total Nodes in the tree

Parameters

void

Returns

int

initAdjacencyMatrix()

void Tree::initAdjacencyMatrix

(

)

Initialize the adjacency matrix as a 2D vector based upon the number of nodes

Parameters

void

Returns

void

insert()

void Tree::insert

(

Segment *

s

)

Insert a segment into the tree

Parameters

Segment

*

Returns

void

printAdjacencyMatrix()

void Tree::printAdjacencyMatrix

(

)

Print the adjacency matrix

Parameters

void

Returns

void

printLists()

void Tree::printLists

(

)

Print all lists: Q-Nodes, P-Nodes, S-Nodes, T-Nodes

Parameters

void

Returns

void

printPathLabels()

void Tree::printPathLabels

(

)

Print the path labels for all Leaf nodes

Parameters

void

Returns

void

printTree()

void Tree::printTree	(	Node *	startNode,
		int	depth = 0
	)

Print the tree in the console

Parameters

Node	* startNode - starting with this node as a root
int=0	depth - starting depth

Returns

void

readSegmentsFile()

void Tree::readSegmentsFile

(

std::string

filename

)

Read the segments file, create Segments objects, insert into Tree

Parameters

std::string

filename

Returns

void

setupLists()

void Tree::setupLists

(

Node *

startNode

)

Initialize all lists for creating the adjacency matrix and the lists of paths

Parameters

Node	* startNode - starting from this node then traverse to all children

Returns

void

setupPathLabels()

void Tree::setupPathLabels	(	Node *	startNode,
		std::string	label
	)

Setup the path labels. Passes a Node pointer and string as parameters. It is a recursive function. If the current node is not a leaf node it calls setupPathLabels(startNode->left, label+"0") for its left child, and setupPathLabels(startNode->right, label+"1") for the right. When reaching a leaf node, add the path label to stored labels. Also adds to allPaths vector stored by the Tree object.

Parameters

Node	* startNode - traverse starting from this node as root
std::string	label - carries the path label

Returns

void

writeAdjacencyMatrix()

void Tree::writeAdjacencyMatrix

(

Node *

startNode

)

Write to the adjacency matrix the labels of the nodes and connections between nodes

Parameters

Node	* startNode - starting from this node then traverse to all children

Returns

void

writeAdjacencyMatrixToFile()

void Tree::writeAdjacencyMatrixToFile

(

std::string

filename

)

Write the adjacency matrix to a file

Parameters

std::string

filename

Returns

void

writeSumsAdjacencyMatrix()

void Tree::writeSumsAdjacencyMatrix

(

)

Fill in the sum row/column of the adjacency matrix

Parameters

void

Returns

void

---

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

• include/Tree.h
• src/Tree.cpp