This clas is creating a steiner tree, which is a mst including all the nodes of a given phase gadget plus all the nodes which are neede to connect all the nodes of the gadget. More...

#include <SteinerTree.hpp>

Collaboration diagram for tket::aas::SteinerTree:

[legend]

Public Member Functions
	SteinerTree ()

	SteinerTree (const PathHandler &pathhandler, std::list< unsigned > &nodes_to_add, unsigned root_node)
	Construct a Steinertree from given parameters.

int	cost_of_operation (unsigned i, unsigned j) const
	calculate cost of performing a CNOT between two neighbouring nodes, dependent on the SteinerNodeTypes.

void	init_tree (const PathHandler &pathhandler, std::list< unsigned > &nodes_to_add)
	initialises the tree

void	add_closest_node_to_tree (const PathHandler &pathhandler, std::list< unsigned > &nodes_to_add)
	adds the closesd nodes to a given list to the tree

void	add_path_to_tree (const PathHandler &pathhandler, unsigned node_in_tree, unsigned node_to_add)
	adds a list of nodes to a given list to the tree

OperationList	operations_available (const PathHandler &pathhandler) const
	calculates the available operation in this tree which could be executed

void	add_row (unsigned i, unsigned j)
	Implements a CNOT from node j to node i, updates costs and tree.

bool	fully_reduced () const
	checks is the tree is fully reduced

unsigned	calculate_cost () const
	gives the cost of the tree

unsigned	get_max_element () const
	returns the nodes of the tree which has the highest index.

std::vector< unsigned >	nodes () const
	gives all nodes of the tree which are leaf, one in or zero in

Public Attributes
unsigned	tree_cost

int	last_operation_cost

unsigned	root

std::vector< SteinerNodeType >	node_types

std::vector< unsigned >	num_neighbours

std::list< unsigned >	tree_nodes

Detailed Description

This clas is creating a steiner tree, which is a mst including all the nodes of a given phase gadget plus all the nodes which are neede to connect all the nodes of the gadget.

This class also offers the function to reduce this tree by extracting operations steps by step. This class is designed with architecture aware synthesis in mind; it may not be suitable for other generic purposes.

Definition at line 60 of file SteinerTree.hpp.

Constructor & Destructor Documentation

◆ SteinerTree() [1/2]

tket::aas::SteinerTree::SteinerTree ( )

inline

Definition at line 62 of file SteinerTree.hpp.

◆ SteinerTree() [2/2]

tket::aas::SteinerTree::SteinerTree	(	const PathHandler &	pathhandler,
		std::list< unsigned > &	nodes_to_add,
		unsigned	root_node
	)

explicit

Construct a Steinertree from given parameters.

Parameters

pathhandler	giving the included edges
nodes_to_add	list by ref, will be changed during the construction of the tree
root_node	initial node, deleted in the last step

Definition at line 23 of file SteinerTree.cpp.

Member Function Documentation

◆ add_closest_node_to_tree()

void tket::aas::SteinerTree::add_closest_node_to_tree	(	const PathHandler &	pathhandler,
		std::list< unsigned > &	nodes_to_add
	)

adds the closesd nodes to a given list to the tree

Parameters

pathhandler	connectivity for the construction
nodes_to_add	list of nodes which should be added, the list will be

Definition at line 211 of file SteinerTree.cpp.

◆ add_path_to_tree()

void tket::aas::SteinerTree::add_path_to_tree	(	const PathHandler &	pathhandler,
		unsigned	node_in_tree,
		unsigned	node_to_add
	)

adds a list of nodes to a given list to the tree

Parameters

pathhandler	connectivity for the construction
node_in_tree	node in tree which is closest to the node to add
node_to_add	node which should be added

Definition at line 130 of file SteinerTree.cpp.

◆ add_row()

void tket::aas::SteinerTree::add_row	(	unsigned	i,
		unsigned	j
	)

Implements a CNOT from node j to node i, updates costs and tree.

Parameters

i	control index
j	target index

Definition at line 341 of file SteinerTree.cpp.

◆ calculate_cost()

unsigned tket::aas::SteinerTree::calculate_cost ( ) const

gives the cost of the tree

Returns: cost of the tree

Definition at line 35 of file SteinerTree.cpp.

◆ cost_of_operation()

int tket::aas::SteinerTree::cost_of_operation	(	unsigned	i,
		unsigned	j
	)		const

calculate cost of performing a CNOT between two neighbouring nodes, dependent on the SteinerNodeTypes.

Parameters

i	control index of operation
j	target index of operation

Definition at line 248 of file SteinerTree.cpp.

◆ fully_reduced()

bool tket::aas::SteinerTree::fully_reduced ( ) const

checks is the tree is fully reduced

Returns: true if fully reduced

Definition at line 432 of file SteinerTree.cpp.

◆ get_max_element()

unsigned tket::aas::SteinerTree::get_max_element ( ) const

returns the nodes of the tree which has the highest index.

only the out of tree nodes are not taken into consideration

Returns: index of maximum node

Definition at line 61 of file SteinerTree.cpp.

◆ init_tree()

void tket::aas::SteinerTree::init_tree	(	const PathHandler &	pathhandler,
		std::list< unsigned > &	nodes_to_add
	)

initialises the tree

Parameters

pathhandler	connectivity for the construction
nodes_to_add	list of nodes which should be added, the list will be changes during the process

Definition at line 79 of file SteinerTree.cpp.

◆ nodes()

std::vector< unsigned > tket::aas::SteinerTree::nodes ( ) const

gives all nodes of the tree which are leaf, one in or zero in

Returns: ordered list of all nodes

Definition at line 69 of file SteinerTree.cpp.

◆ operations_available()

OperationList tket::aas::SteinerTree::operations_available ( const PathHandler & pathhandler ) const

calculates the available operation in this tree which could be executed

Parameters

pathhandler conections used for the calculation

Returns: gives the list of all avilable operations

Definition at line 321 of file SteinerTree.cpp.

Member Data Documentation

◆ last_operation_cost

int tket::aas::SteinerTree::last_operation_cost

Definition at line 150 of file SteinerTree.hpp.

◆ node_types

std::vector<SteinerNodeType> tket::aas::SteinerTree::node_types

Definition at line 152 of file SteinerTree.hpp.

◆ num_neighbours

std::vector<unsigned> tket::aas::SteinerTree::num_neighbours

Definition at line 153 of file SteinerTree.hpp.

◆ root

unsigned tket::aas::SteinerTree::root

Definition at line 151 of file SteinerTree.hpp.

◆ tree_cost

unsigned tket::aas::SteinerTree::tree_cost

Definition at line 149 of file SteinerTree.hpp.

◆ tree_nodes

std::list<unsigned> tket::aas::SteinerTree::tree_nodes

Definition at line 154 of file SteinerTree.hpp.

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

include/tket/ArchAwareSynth/SteinerTree.hpp
src/ArchAwareSynth/SteinerTree.cpp

Public Member Functions

Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ SteinerTree() [1/2]

◆ SteinerTree() [2/2]

Member Function Documentation

◆ add_closest_node_to_tree()

◆ add_path_to_tree()

◆ add_row()

◆ calculate_cost()

◆ cost_of_operation()

◆ fully_reduced()

◆ get_max_element()

◆ init_tree()

◆ nodes()

◆ operations_available()

Member Data Documentation

◆ last_operation_cost

◆ node_types

◆ num_neighbours

◆ root

◆ tree_cost

◆ tree_nodes