Represents the entire global routing tree. More...

#include <global_router.hpp>

Public Types
using	Keepout = decltype(std::declval< IntPoint >().enlarge_with(1))

Public Member Functions
	GlobalRoutingTree (IntPoint source_position)
	Constructs a new GlobalRoutingTree with a specified source position.

auto	get_source () const -> const RoutingNode< IntPoint > *
	Gets a const pointer to the source node of the tree.

auto	get_source () -> RoutingNode< IntPoint > *
	Gets a non-const pointer to the source node of the tree.

auto	insert_steiner_node (const IntPoint &point, std::optional< std::string > parent_id=std::nullopt) -> std::string
	Inserts a new Steiner node into the routing tree.

auto	insert_terminal_node (const IntPoint &point, std::optional< std::string > parent_id=std::nullopt) -> std::string
	Inserts a new terminal node into the routing tree.

auto	insert_node_on_branch (NodeType new_node_type, const IntPoint &point, std::string branch_start_id, std::string branch_end_id) -> std::string
	Inserts a new node (Steiner or Terminal) onto an existing branch of the tree.

auto	insert_terminal_with_steiner (const IntPoint &point, std::optional< std::vector< Keepout > > keepouts=std::nullopt) -> void
	Inserts a new terminal node with possible Steiner point.

auto	insert_terminal_with_constraints (const IntPoint &point, int allowed_wirelength, std::optional< std::vector< Keepout > > keepouts=std::nullopt) -> void
	Inserts a new terminal node with constraints.

auto	calculate_total_wirelength () const -> int
	Calculates the total wirelength of the routing tree.

auto	calculate_worst_wirelength () const -> int
	Calculates the worst wirelength of the routing tree.

auto	get_tree_structure (const RoutingNode< IntPoint > *current_node=nullptr, int level=0) const -> std::string
	Generates a string representation of the tree structure for visualization or debugging.

auto	find_path_to_source (const std::string &node_id) const -> std::vector< const RoutingNode< IntPoint > * >
	Finds the path from a given node to the source node.

auto	get_all_terminals () const -> std::vector< const RoutingNode< IntPoint > * >
	Retrieves all terminal nodes in the tree.

auto	get_all_steiner_nodes () const -> std::vector< const RoutingNode< IntPoint > * >
	Retrieves all Steiner nodes in the tree.

void	optimize_steiner_points ()
	Optimizes the routing tree by removing redundant Steiner points. A Steiner point is considered redundant if it has only one child and is not the source node.

void	visualize_tree () const
	Visualizes the routing tree (implementation in .cpp file).

Public Attributes
std::unordered_map< std::string, RoutingNode< IntPoint > * >	nodes
	Map from node ID to RoutingNode<IntPoint> pointer.

int	worst_wirelength = 0

Detailed Description

template<typename IntPoint>
class recti::GlobalRoutingTree< IntPoint >

Represents the entire global routing tree.

This class manages the collection of RoutingNodes, including the source, Steiner points, and terminal points, and provides methods for building and manipulating the tree structure.

+-----------------------------+
|      GlobalRoutingTree      |
+-----------------------------+
| source_node (SOURCE)        |
|    |                        |
|    v                        |
| +-------------------------+  |
| | RoutingNode             |  |
| | id: source              |  |
| | type: SOURCE            |  |  A tree structure with
| | pt: (x, y)              |  |  source, terminals,
| | children[]              |  |  and steiner points
| | parent: null            |  |
| +-------------------------+  |
|    |                        |
|    +--> +----------------+   |
|         |RoutingNode     |   |
|         |id: terminal_1  |   |
|         |type: TERMINAL  |   |
|         |pt: (x1, y1)    |   |
|         |children[]      |   |
|         |parent: source  |   |
|         +----------------+   |
|    |                        |
|    +--> +----------------+   |
|         |RoutingNode     |   |
|         |id: steiner_1   |   |
|         |type: STEINER   |   |
|         |pt: (x2, y2)    |   |
|         |children[]      |   |
|         |parent: source  |   |
|         +----------------+   |
|            |                 |
|            +--> +----------+ |
|                 |RoutingNode| |
|                 |id: term_2| |
|                 |type: TERM| |
|                 |pt: (x3,y3)||
|                 |children[]| |
|                 |parent: st| |
|                 +----------+ |
+-----------------------------+

Template Parameters

IntPoint The point type used for coordinates (e.g. Point<int, int>).

Member Typedef Documentation

◆ Keepout

template<typename IntPoint >

using recti::GlobalRoutingTree< IntPoint >::Keepout = decltype(std::declval<IntPoint>().enlarge_with(1))

Constructor & Destructor Documentation

◆ GlobalRoutingTree()

template<typename IntPoint >

recti::GlobalRoutingTree< IntPoint >::GlobalRoutingTree ( IntPoint source_position )

inline

Constructs a new GlobalRoutingTree with a specified source position.

Parameters

source_position The 2D integer coordinates of the source node.

Member Function Documentation

◆ calculate_total_wirelength()

template<typename IntPoint >

auto recti::GlobalRoutingTree< IntPoint >::calculate_total_wirelength ( ) const -> int

Calculates the total wirelength of the routing tree.

Returns: The total wirelength as an integer.

◆ calculate_worst_wirelength()

template<typename IntPoint >

auto recti::GlobalRoutingTree< IntPoint >::calculate_worst_wirelength ( ) const -> int

Calculates the worst wirelength of the routing tree.

Returns: The worst wirelength as an integer.

◆ find_path_to_source()

template<typename IntPoint >

auto recti::GlobalRoutingTree< IntPoint >::find_path_to_source ( const std::string & node_id ) const -> std::vector< const RoutingNode< IntPoint > * >

Finds the path from a given node to the source node.

Parameters

node_id The ID of the starting node.

Returns: A vector of const pointers to RoutingNodes, representing the path from source to the given node.

Exceptions

std::runtime_error if the specified node is not found.

◆ get_all_steiner_nodes()

template<typename IntPoint >

auto recti::GlobalRoutingTree< IntPoint >::get_all_steiner_nodes ( ) const -> std::vector< const RoutingNode< IntPoint > * >

Retrieves all Steiner nodes in the tree.

Returns: A vector of pointers to all RoutingNodes of type STEINER.

◆ get_all_terminals()

template<typename IntPoint >

auto recti::GlobalRoutingTree< IntPoint >::get_all_terminals ( ) const -> std::vector< const RoutingNode< IntPoint > * >

Retrieves all terminal nodes in the tree.

Returns: A vector of pointers to all RoutingNodes of type TERMINAL.

◆ get_source() [1/2]

template<typename IntPoint >

auto recti::GlobalRoutingTree< IntPoint >::get_source ( ) -> RoutingNode<IntPoint>*

inline

Gets a non-const pointer to the source node of the tree.

Returns: A non-const pointer to the source RoutingNode<IntPoint>.

◆ get_source() [2/2]

template<typename IntPoint >

auto recti::GlobalRoutingTree< IntPoint >::get_source ( ) const -> const RoutingNode<IntPoint>*

inline

Gets a const pointer to the source node of the tree.

Returns: A const pointer to the source RoutingNode<IntPoint>.

◆ get_tree_structure()

template<typename IntPoint >

auto recti::GlobalRoutingTree< IntPoint >::get_tree_structure	(	const RoutingNode< IntPoint > *	current_node = `nullptr`,
		int	level = `0`
	)		const -> std::string

Generates a string representation of the tree structure for visualization or debugging.

Parameters

current_node	The starting node for the traversal (defaults to source_node).
level	The current depth level in the tree (for indentation).

Returns: A string representing the tree structure.

◆ insert_node_on_branch()

template<typename IntPoint >

auto recti::GlobalRoutingTree< IntPoint >::insert_node_on_branch	(	NodeType	new_node_type,
		const IntPoint &	point,
		std::string	branch_start_id,
		std::string	branch_end_id
	)		-> std::string

Inserts a new node (Steiner or Terminal) onto an existing branch of the tree.

Parameters

new_node_type	The type of the new node to insert (STEINER or TERMINAL).
point	The position of the new node.
branch_start_id	The ID of the parent node of the branch.
branch_end_id	The ID of the child node of the branch.

Returns: The ID of the newly inserted node.

Exceptions

std::runtime_error if branch nodes are not found or if branch_end_id is not a direct child of branch_start_id.

◆ insert_steiner_node()

template<typename IntPoint >

auto recti::GlobalRoutingTree< IntPoint >::insert_steiner_node	(	const IntPoint &	point,
		std::optional< std::string >	parent_id = `std::nullopt`
	)		-> std::string

Inserts a new Steiner node into the routing tree.

Parameters

point	The position of the new Steiner node.
parent_id	Optional ID of the parent node. If not provided, the source node is used as parent.

Returns: The ID of the newly inserted Steiner node.

Exceptions

std::runtime_error if the specified parent node is not found.

◆ insert_terminal_node()

template<typename IntPoint >

auto recti::GlobalRoutingTree< IntPoint >::insert_terminal_node	(	const IntPoint &	point,
		std::optional< std::string >	parent_id = `std::nullopt`
	)		-> std::string

Inserts a new terminal node into the routing tree.

Parameters

point	The position of the new terminal node.
parent_id	Optional ID of the parent node. If not provided, the nearest existing node is used as parent.

Returns: The ID of the newly inserted terminal node.

Exceptions

std::runtime_error if the specified parent node is not found.

◆ insert_terminal_with_constraints()

template<typename IntPoint >

auto recti::GlobalRoutingTree< IntPoint >::insert_terminal_with_constraints	(	const IntPoint &	point,
		int	allowed_wirelength,
		std::optional< std::vector< Keepout > >	keepouts = `std::nullopt`
	)		-> void

inline

Inserts a new terminal node with constraints.

Parameters

point	The position of the terminal.
allowed_wirelength	The allowed wirelength.
keepouts	Optional keepouts to avoid.

◆ insert_terminal_with_steiner()

template<typename IntPoint >

auto recti::GlobalRoutingTree< IntPoint >::insert_terminal_with_steiner	(	const IntPoint &	point,
		std::optional< std::vector< Keepout > >	keepouts = `std::nullopt`
	)		-> void

inline

Inserts a new terminal node with possible Steiner point.

Parameters

point	The position of the terminal.
keepouts	Optional keepouts to avoid.

◆ optimize_steiner_points()

template<typename IntPoint >

void recti::GlobalRoutingTree< IntPoint >::optimize_steiner_points ( )

Optimizes the routing tree by removing redundant Steiner points. A Steiner point is considered redundant if it has only one child and is not the source node.

◆ visualize_tree()

template<typename IntPoint >

void recti::GlobalRoutingTree< IntPoint >::visualize_tree ( ) const

Visualizes the routing tree (implementation in .cpp file).

Member Data Documentation

◆ nodes

template<typename IntPoint >

std::unordered_map<std::string, RoutingNode<IntPoint>*> recti::GlobalRoutingTree< IntPoint >::nodes

Map from node ID to RoutingNode<IntPoint> pointer.

◆ worst_wirelength

template<typename IntPoint >

int recti::GlobalRoutingTree< IntPoint >::worst_wirelength = 0

The worst-case wirelength constraint for routing (used in constrained routing).

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

recti/global_router.hpp

Public Types

Public Member Functions

Public Attributes

Detailed Description

Member Typedef Documentation

◆ Keepout

Constructor & Destructor Documentation

◆ GlobalRoutingTree()

Member Function Documentation

◆ calculate_total_wirelength()

◆ calculate_worst_wirelength()

◆ find_path_to_source()

◆ get_all_steiner_nodes()

◆ get_all_terminals()

◆ get_source() [1/2]

◆ get_source() [2/2]

◆ get_tree_structure()

◆ insert_node_on_branch()

◆ insert_steiner_node()

◆ insert_terminal_node()

◆ insert_terminal_with_constraints()

◆ insert_terminal_with_steiner()

◆ optimize_steiner_points()

◆ visualize_tree()

Member Data Documentation

◆ nodes

◆ worst_wirelength