Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Static Public Attributes | Private Types | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA > Class Template Reference

#include <Tree_Decomposition.H>

Inheritance diagram for Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >:
[legend]
Collaboration diagram for Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >:
[legend]

Public Types

using Node = typename GT::Node
 
using Arc = typename GT::Arc
 

Public Member Functions

 Rooted_Tree_Topology (const GT &g, Node *root, SA sa=SA())
 
size_t size () const noexcept
 
bool is_empty () const noexcept
 
Node * root () const noexcept
 
size_t root_id () const noexcept
 
const Array< Node * > & id_to_node () const noexcept
 
const Array< Array< size_t > > & adjacency () const noexcept
 
size_t id_of (const Node *node) const
 
Node * node_of (const size_t id) const
 
void validate_id (const size_t id, const char *where) const
 

Static Public Attributes

static constexpr size_t NONE = std::numeric_limits<size_t>::max()
 

Private Types

using Pair_Key = std::pair< size_t, size_t >
 

Private Member Functions

void check_id (const size_t id, const char *where) const
 
void index_nodes ()
 
void build_simple_adjacency ()
 
void validate_connected_acyclic () const
 

Static Private Member Functions

static Pair_Key normalize_pair (size_t u, size_t v) noexcept
 

Private Attributes

const GT * graph_ = nullptr
 
SA sa_
 
Node * root_ = nullptr
 
size_t root_id_ = NONE
 
size_t n_ = 0
 
Array< Node * > id_to_node_
 
MapOLhash< Node *, size_t > node_to_id_
 
Array< Array< size_t > > adjacency_
 

Detailed Description

template<class GT, class SA>
class Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >

Definition at line 152 of file Tree_Decomposition.H.

Member Typedef Documentation

◆ Arc

template<class GT , class SA >
using Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::Arc = typename GT::Arc

Definition at line 156 of file Tree_Decomposition.H.

◆ Node

template<class GT , class SA >
using Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::Node = typename GT::Node

Definition at line 155 of file Tree_Decomposition.H.

◆ Pair_Key

template<class GT , class SA >
using Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::Pair_Key = std::pair<size_t, size_t>
private

Definition at line 161 of file Tree_Decomposition.H.

Constructor & Destructor Documentation

◆ Rooted_Tree_Topology()

template<class GT , class SA >
Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::Rooted_Tree_Topology ( const GT &  g,
Node *  root,
SA  sa = SA() 
)
inline

Definition at line 328 of file Tree_Decomposition.H.

References Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::build_simple_adjacency(), Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::index_nodes(), and Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::validate_connected_acyclic().

Member Function Documentation

◆ adjacency()

template<class GT , class SA >
const Array< Array< size_t > > & Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::adjacency ( ) const
inlinenoexcept

Definition at line 346 of file Tree_Decomposition.H.

References Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::adjacency_.

Referenced by Aleph::Gen_Centroid_Decomposition< GT, SA >::append_centroid_annotations(), Aleph::Gen_Centroid_Decomposition< GT, SA >::build_centroid_tree(), Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::build_decomposition(), Aleph::Gen_Centroid_Decomposition< GT, SA >::choose_centroid(), and Aleph::Gen_Centroid_Decomposition< GT, SA >::collect_component_nodes().

◆ build_simple_adjacency()

template<class GT , class SA >
void Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::build_simple_adjacency ( )
inlineprivate

Definition at line 224 of file Tree_Decomposition.H.

References Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::adjacency_, ah_domain_error_if, ah_runtime_error_unless, Aleph::and, Aleph::divide_and_conquer_partition_dp(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::graph_, Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::n_, Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::node_to_id_, Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::normalize_pair(), Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::sa_, and Aleph::MapOpenHash< Key, Data, Cmp, HashTable >::search().

Referenced by Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::Rooted_Tree_Topology().

◆ check_id()

template<class GT , class SA >
void Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::check_id ( const size_t  id,
const char *  where 
) const
inlineprivate

Definition at line 181 of file Tree_Decomposition.H.

References ah_out_of_range_error_if, Aleph::divide_and_conquer_partition_dp(), and Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::n_.

Referenced by Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::node_of(), and Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::validate_id().

◆ id_of()

template<class GT , class SA >
size_t Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::id_of ( const Node *  node) const
inline

Definition at line 351 of file Tree_Decomposition.H.

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

◆ id_to_node()

template<class GT , class SA >
const Array< Node * > & Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::id_to_node ( ) const
inlinenoexcept

Definition at line 341 of file Tree_Decomposition.H.

References Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::id_to_node_.

◆ index_nodes()

template<class GT , class SA >
void Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::index_nodes ( )
inlineprivate

Definition at line 187 of file Tree_Decomposition.H.

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

Referenced by Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::Rooted_Tree_Topology().

◆ is_empty()

template<class GT , class SA >
bool Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::is_empty ( ) const
inlinenoexcept

Definition at line 337 of file Tree_Decomposition.H.

References Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::n_.

◆ node_of()

template<class GT , class SA >
Node * Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::node_of ( const size_t  id) const
inline

Definition at line 363 of file Tree_Decomposition.H.

References Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::check_id(), and Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::id_to_node_.

◆ normalize_pair()

template<class GT , class SA >
static Pair_Key Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::normalize_pair ( size_t  u,
size_t  v 
)
inlinestaticprivatenoexcept

Definition at line 174 of file Tree_Decomposition.H.

Referenced by Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::build_simple_adjacency().

◆ root()

template<class GT , class SA >
Node * Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::root ( ) const
inlinenoexcept

Definition at line 338 of file Tree_Decomposition.H.

References Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::root_.

◆ root_id()

template<class GT , class SA >
size_t Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::root_id ( ) const
inlinenoexcept

Definition at line 339 of file Tree_Decomposition.H.

References Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::root_id_.

Referenced by Aleph::Gen_Centroid_Decomposition< GT, SA >::build_centroid_tree(), and Aleph::Gen_Heavy_Light_Decomposition< GT, SA >::build_decomposition().

◆ size()

template<class GT , class SA >
size_t Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::size ( ) const
inlinenoexcept

Definition at line 336 of file Tree_Decomposition.H.

References Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::n_.

◆ validate_connected_acyclic()

template<class GT , class SA >
void Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::validate_connected_acyclic ( ) const
inlineprivate

Definition at line 280 of file Tree_Decomposition.H.

References Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::adjacency_, ah_domain_error_if, Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), Aleph::DynListStack< T >::is_empty(), Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::n_, Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::NONE, Aleph::DynListStack< T >::pop(), Aleph::DynListStack< T >::push(), Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::root_id_, and Aleph::DynListStack< T >::top().

Referenced by Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::Rooted_Tree_Topology().

◆ validate_id()

template<class GT , class SA >
void Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::validate_id ( const size_t  id,
const char *  where 
) const
inline

Definition at line 369 of file Tree_Decomposition.H.

References Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::check_id(), and Aleph::divide_and_conquer_partition_dp().

Member Data Documentation

◆ adjacency_

template<class GT , class SA >
Array<Array<size_t> > Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::adjacency_
private

Definition at line 172 of file Tree_Decomposition.H.

Referenced by Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::adjacency(), Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::build_simple_adjacency(), and Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::validate_connected_acyclic().

◆ graph_

template<class GT , class SA >
const GT* Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::graph_ = nullptr
private

Definition at line 163 of file Tree_Decomposition.H.

Referenced by Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::build_simple_adjacency(), and Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::index_nodes().

◆ id_to_node_

template<class GT , class SA >
Array<Node *> Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::id_to_node_
private

Definition at line 170 of file Tree_Decomposition.H.

Referenced by Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::id_to_node(), Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::index_nodes(), and Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::node_of().

◆ n_

template<class GT , class SA >
size_t Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::n_ = 0
private

Definition at line 168 of file Tree_Decomposition.H.

Referenced by Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::build_simple_adjacency(), Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::check_id(), Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::index_nodes(), Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::is_empty(), Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::size(), and Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::validate_connected_acyclic().

◆ node_to_id_

template<class GT , class SA >
MapOLhash<Node *, size_t> Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::node_to_id_
private

Definition at line 171 of file Tree_Decomposition.H.

Referenced by Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::build_simple_adjacency(), Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::id_of(), and Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::index_nodes().

◆ NONE

template<class GT , class SA >
constexpr size_t Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::NONE = std::numeric_limits<size_t>::max()
staticconstexpr

Definition at line 158 of file Tree_Decomposition.H.

Referenced by Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::validate_connected_acyclic().

◆ root_

template<class GT , class SA >
Node* Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::root_ = nullptr
private

Definition at line 165 of file Tree_Decomposition.H.

Referenced by Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::index_nodes(), and Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::root().

◆ root_id_

template<class GT , class SA >
size_t Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::root_id_ = NONE
private

Definition at line 166 of file Tree_Decomposition.H.

Referenced by Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::index_nodes(), Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::root_id(), and Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::validate_connected_acyclic().

◆ sa_

template<class GT , class SA >
SA Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::sa_
private

Definition at line 164 of file Tree_Decomposition.H.

Referenced by Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::build_simple_adjacency().

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