Pre-processes and extracts tree topology from a graph. More...

#include <Tree_DP.H>

Inheritance diagram for Aleph::tree_dp_detail::Tree_Topology< GT, SA >:

Collaboration diagram for Aleph::tree_dp_detail::Tree_Topology< GT, SA >:

Public Types
using	Node = typename GT::Node
	Node type.

using	Arc = typename GT::Arc
	Arc type.

Public Member Functions
	Tree_Topology (const GT &g, Node *root, SA sa=SA())
	Preprocess tree topology.

size_t	size () const noexcept
	Returns number of nodes.

Node *	root () const noexcept
	Returns root node pointer.

size_t	id_of (Node *node) const
	Returns internal ID of a node.

Node *	node_of (size_t id) const
	Returns node pointer for a given ID.

const Array< size_t > &	children (size_t id) const
	Returns children IDs of a node.

size_t	parent (size_t id) const noexcept
	Returns parent ID of a node.

const Array< size_t > &	post_order () const noexcept
	Returns post-order traversal (leaves first, root last).

const Array< Node * > &	nodes () const noexcept
	Returns all node pointers indexed by ID.

Static Public Attributes
static constexpr size_t	NONE = std::numeric_limits<size_t>::max()
	Sentinel for null/none parent or id.

Private Member Functions
void	index_nodes ()
	Assign unique IDs to nodes and validate the root.

void	build_adjacency ()
	Build undirected adjacency list and verify tree properties.

void	build_order ()
	BFS/DFS traversal to establish parent-child relations and order.

Private Attributes
const GT *	graph_ = nullptr
	Source graph.

SA	sa_
	Arc filter.

Node *	root_ = nullptr
	Tree root.

size_t	n_ = 0
	Number of nodes.

Array< Node * >	id_to_node_
	Mapping from id to node pointer.

MapOLhash< Node *, size_t >	node_to_id_
	Mapping from node pointer to id.

Array< Array< size_t > >	children_
	Children list in the rooted tree.

Array< size_t >	parent_
	Parent id for each node.

Array< size_t >	order_
	Post-order traversal (leaves first).

Detailed Description

template<AlephGraph GT, ArcFilter< GT > SA>
class Aleph::tree_dp_detail::Tree_Topology< GT, SA >

Pre-processes and extracts tree topology from a graph.

Verifies tree properties, assigns internal IDs to nodes, and establishes parent-child relationships for a given root.

Template Parameters

GT	Graph type.
SA	Arc filter.

Definition at line 82 of file Tree_DP.H.

Member Typedef Documentation

◆ Arc

template<AlephGraph GT, ArcFilter< GT > SA>

using Aleph::tree_dp_detail::Tree_Topology< GT, SA >::Arc = typename GT::Arc

Arc type.

Definition at line 86 of file Tree_DP.H.

◆ Node

template<AlephGraph GT, ArcFilter< GT > SA>

using Aleph::tree_dp_detail::Tree_Topology< GT, SA >::Node = typename GT::Node

Node type.

Definition at line 85 of file Tree_DP.H.

Constructor & Destructor Documentation

◆ Tree_Topology()

template<AlephGraph GT, ArcFilter< GT > SA>

Aleph::tree_dp_detail::Tree_Topology< GT, SA >::Tree_Topology	(	const GT &	g,
		Node *	root,
		SA	sa = `SA()`
	)

inline

Preprocess tree topology.

Parameters

[in]	g	The graph tree.
[in]	root	The root node.
[in]	sa	The arc filter.

Exceptions

ah_domain_error if not a tree or root not in graph.

Definition at line 253 of file Tree_DP.H.

References Aleph::tree_dp_detail::Tree_Topology< GT, SA >::build_adjacency(), Aleph::tree_dp_detail::Tree_Topology< GT, SA >::build_order(), and Aleph::tree_dp_detail::Tree_Topology< GT, SA >::index_nodes().

Member Function Documentation

◆ build_adjacency()

template<AlephGraph GT, ArcFilter< GT > SA>

void Aleph::tree_dp_detail::Tree_Topology< GT, SA >::build_adjacency ( )

inlineprivate

Build undirected adjacency list and verify tree properties.

Definition at line 137 of file Tree_DP.H.

References ah_domain_error_if, ah_runtime_error_unless, Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::tree_dp_detail::Tree_Topology< GT, SA >::children_, GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::tree_dp_detail::Tree_Topology< GT, SA >::graph_, Aleph::tree_dp_detail::Tree_Topology< GT, SA >::n_, Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), Aleph::tree_dp_detail::Tree_Topology< GT, SA >::node_to_id_, Aleph::tree_dp_detail::Tree_Topology< GT, SA >::sa_, and Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::search().

Referenced by Aleph::tree_dp_detail::Tree_Topology< GT, SA >::Tree_Topology().

◆ build_order()

template<AlephGraph GT, ArcFilter< GT > SA>

void Aleph::tree_dp_detail::Tree_Topology< GT, SA >::build_order ( )

inlineprivate

BFS/DFS traversal to establish parent-child relations and order.

Definition at line 186 of file Tree_DP.H.

Referenced by Aleph::tree_dp_detail::Tree_Topology< GT, SA >::Tree_Topology().

◆ children()

template<AlephGraph GT, ArcFilter< GT > SA>

const Array< size_t > & Aleph::tree_dp_detail::Tree_Topology< GT, SA >::children ( size_t id ) const

inline

Returns children IDs of a node.

Definition at line 288 of file Tree_DP.H.

References Aleph::tree_dp_detail::Tree_Topology< GT, SA >::children_.

Referenced by Aleph::tree_dp_detail::Tree_Topology< GT, SA >::build_order().

◆ id_of()

template<AlephGraph GT, ArcFilter< GT > SA>

size_t Aleph::tree_dp_detail::Tree_Topology< GT, SA >::id_of ( Node * node ) const

inline

Returns internal ID of a node.

Definition at line 273 of file Tree_DP.H.

References ah_domain_error_if, Aleph::tree_dp_detail::Tree_Topology< GT, SA >::node_to_id_, and Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::search().

◆ index_nodes()

template<AlephGraph GT, ArcFilter< GT > SA>

void Aleph::tree_dp_detail::Tree_Topology< GT, SA >::index_nodes ( )

inlineprivate

Assign unique IDs to nodes and validate the root.

Definition at line 104 of file Tree_DP.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Array< T >::create(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::tree_dp_detail::Tree_Topology< GT, SA >::graph_, Aleph::tree_dp_detail::Tree_Topology< GT, SA >::id_to_node_, Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::insert(), Aleph::tree_dp_detail::Tree_Topology< GT, SA >::n_, Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), Aleph::tree_dp_detail::Tree_Topology< GT, SA >::node_to_id_, Aleph::tree_dp_detail::Tree_Topology< GT, SA >::root_, and Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::search().

Referenced by Aleph::tree_dp_detail::Tree_Topology< GT, SA >::Tree_Topology().

◆ node_of()

template<AlephGraph GT, ArcFilter< GT > SA>

Node * Aleph::tree_dp_detail::Tree_Topology< GT, SA >::node_of ( size_t id ) const

inline

Returns node pointer for a given ID.

Definition at line 281 of file Tree_DP.H.

References ah_out_of_range_error_if, Aleph::tree_dp_detail::Tree_Topology< GT, SA >::id_to_node_, and Aleph::tree_dp_detail::Tree_Topology< GT, SA >::n_.

◆ nodes()

template<AlephGraph GT, ArcFilter< GT > SA>

const Array< Node * > & Aleph::tree_dp_detail::Tree_Topology< GT, SA >::nodes ( ) const

inlinenoexcept

Returns all node pointers indexed by ID.

Definition at line 306 of file Tree_DP.H.

References Aleph::tree_dp_detail::Tree_Topology< GT, SA >::id_to_node_.

◆ parent()

template<AlephGraph GT, ArcFilter< GT > SA>

size_t Aleph::tree_dp_detail::Tree_Topology< GT, SA >::parent ( size_t id ) const

inlinenoexcept

Returns parent ID of a node.

Definition at line 294 of file Tree_DP.H.

References Aleph::tree_dp_detail::Tree_Topology< GT, SA >::parent_.

◆ post_order()

template<AlephGraph GT, ArcFilter< GT > SA>

const Array< size_t > & Aleph::tree_dp_detail::Tree_Topology< GT, SA >::post_order ( ) const

inlinenoexcept

Returns post-order traversal (leaves first, root last).

Definition at line 300 of file Tree_DP.H.

References Aleph::tree_dp_detail::Tree_Topology< GT, SA >::order_.

◆ root()

template<AlephGraph GT, ArcFilter< GT > SA>

Node * Aleph::tree_dp_detail::Tree_Topology< GT, SA >::root ( ) const

inlinenoexcept

Returns root node pointer.

Definition at line 267 of file Tree_DP.H.

References Aleph::tree_dp_detail::Tree_Topology< GT, SA >::root_.

◆ size()

template<AlephGraph GT, ArcFilter< GT > SA>

size_t Aleph::tree_dp_detail::Tree_Topology< GT, SA >::size ( ) const

inlinenoexcept

Returns number of nodes.

Definition at line 261 of file Tree_DP.H.

References Aleph::tree_dp_detail::Tree_Topology< GT, SA >::n_.

Member Data Documentation

◆ children_

template<AlephGraph GT, ArcFilter< GT > SA>

Array<Array<size_t> > Aleph::tree_dp_detail::Tree_Topology< GT, SA >::children_

private

Children list in the rooted tree.

Definition at line 99 of file Tree_DP.H.

Referenced by Aleph::tree_dp_detail::Tree_Topology< GT, SA >::build_adjacency(), Aleph::tree_dp_detail::Tree_Topology< GT, SA >::build_order(), and Aleph::tree_dp_detail::Tree_Topology< GT, SA >::children().

◆ graph_

template<AlephGraph GT, ArcFilter< GT > SA>

const GT* Aleph::tree_dp_detail::Tree_Topology< GT, SA >::graph_ = nullptr

private

Source graph.

Definition at line 92 of file Tree_DP.H.

Referenced by Aleph::tree_dp_detail::Tree_Topology< GT, SA >::build_adjacency(), and Aleph::tree_dp_detail::Tree_Topology< GT, SA >::index_nodes().

◆ id_to_node_

template<AlephGraph GT, ArcFilter< GT > SA>

Array<Node *> Aleph::tree_dp_detail::Tree_Topology< GT, SA >::id_to_node_

private

Mapping from id to node pointer.

Definition at line 97 of file Tree_DP.H.

Referenced by Aleph::tree_dp_detail::Tree_Topology< GT, SA >::index_nodes(), Aleph::tree_dp_detail::Tree_Topology< GT, SA >::node_of(), and Aleph::tree_dp_detail::Tree_Topology< GT, SA >::nodes().

◆ n_

template<AlephGraph GT, ArcFilter< GT > SA>

size_t Aleph::tree_dp_detail::Tree_Topology< GT, SA >::n_ = 0

private

Number of nodes.

Definition at line 95 of file Tree_DP.H.

Referenced by Aleph::tree_dp_detail::Tree_Topology< GT, SA >::build_adjacency(), Aleph::tree_dp_detail::Tree_Topology< GT, SA >::build_order(), Aleph::tree_dp_detail::Tree_Topology< GT, SA >::index_nodes(), Aleph::tree_dp_detail::Tree_Topology< GT, SA >::node_of(), and Aleph::tree_dp_detail::Tree_Topology< GT, SA >::size().

◆ node_to_id_

template<AlephGraph GT, ArcFilter< GT > SA>

MapOLhash<Node *, size_t> Aleph::tree_dp_detail::Tree_Topology< GT, SA >::node_to_id_

private

Mapping from node pointer to id.

Definition at line 98 of file Tree_DP.H.

Referenced by Aleph::tree_dp_detail::Tree_Topology< GT, SA >::build_adjacency(), Aleph::tree_dp_detail::Tree_Topology< GT, SA >::build_order(), Aleph::tree_dp_detail::Tree_Topology< GT, SA >::id_of(), and Aleph::tree_dp_detail::Tree_Topology< GT, SA >::index_nodes().

◆ NONE

template<AlephGraph GT, ArcFilter< GT > SA>

constexpr size_t Aleph::tree_dp_detail::Tree_Topology< GT, SA >::NONE = std::numeric_limits<size_t>::max()

staticconstexpr

Sentinel for null/none parent or id.

Definition at line 89 of file Tree_DP.H.

Referenced by Aleph::tree_dp_detail::Tree_Topology< GT, SA >::build_order().

◆ order_

template<AlephGraph GT, ArcFilter< GT > SA>

Array<size_t> Aleph::tree_dp_detail::Tree_Topology< GT, SA >::order_

private

Post-order traversal (leaves first).

Definition at line 101 of file Tree_DP.H.

Referenced by Aleph::tree_dp_detail::Tree_Topology< GT, SA >::build_order(), and Aleph::tree_dp_detail::Tree_Topology< GT, SA >::post_order().

◆ parent_

template<AlephGraph GT, ArcFilter< GT > SA>

Array<size_t> Aleph::tree_dp_detail::Tree_Topology< GT, SA >::parent_

private

Parent id for each node.

Definition at line 100 of file Tree_DP.H.

Referenced by Aleph::tree_dp_detail::Tree_Topology< GT, SA >::build_order(), and Aleph::tree_dp_detail::Tree_Topology< GT, SA >::parent().

◆ root_

template<AlephGraph GT, ArcFilter< GT > SA>

Node* Aleph::tree_dp_detail::Tree_Topology< GT, SA >::root_ = nullptr

private

Tree root.

Definition at line 94 of file Tree_DP.H.

Referenced by Aleph::tree_dp_detail::Tree_Topology< GT, SA >::build_order(), Aleph::tree_dp_detail::Tree_Topology< GT, SA >::index_nodes(), and Aleph::tree_dp_detail::Tree_Topology< GT, SA >::root().

◆ sa_

template<AlephGraph GT, ArcFilter< GT > SA>

SA Aleph::tree_dp_detail::Tree_Topology< GT, SA >::sa_

private

Arc filter.

Definition at line 93 of file Tree_DP.H.

Referenced by Aleph::tree_dp_detail::Tree_Topology< GT, SA >::build_adjacency().

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

Tree_DP.H

Public Types

Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Arc

◆ Node

Constructor & Destructor Documentation

◆ Tree_Topology()

Member Function Documentation

◆ build_adjacency()

◆ build_order()

◆ children()

◆ id_of()

◆ index_nodes()

◆ node_of()

◆ nodes()

◆ parent()

◆ post_order()

◆ root()

◆ size()

Member Data Documentation

◆ children_

◆ graph_

◆ id_to_node_

◆ n_

◆ node_to_id_

◆ NONE

◆ order_

◆ parent_

◆ root_

◆ sa_