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<AlephGraph GT, ArcFilter< GT > SA>
class Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >

Definition at line 154 of file Tree_Decomposition.H.

Member Typedef Documentation

◆ Arc

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

Definition at line 158 of file Tree_Decomposition.H.

◆ Node

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

Definition at line 157 of file Tree_Decomposition.H.

◆ Pair_Key

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

Definition at line 163 of file Tree_Decomposition.H.

Constructor & Destructor Documentation

◆ Rooted_Tree_Topology()

template<AlephGraph GT, ArcFilter< GT > 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 330 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<AlephGraph GT, ArcFilter< GT > SA>
const Array< Array< size_t > > & Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::adjacency ( ) const
inlinenoexcept

Definition at line 348 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<AlephGraph GT, ArcFilter< GT > SA>
void Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::build_simple_adjacency ( )
inlineprivate

Definition at line 226 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::blossom_maximum_cardinality_matching(), 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<AlephGraph GT, ArcFilter< GT > 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 183 of file Tree_Decomposition.H.

References ah_out_of_range_error_if, Aleph::blossom_maximum_cardinality_matching(), 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<AlephGraph GT, ArcFilter< GT > SA>
size_t Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::id_of ( const Node *  node) const
inline

Definition at line 353 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<AlephGraph GT, ArcFilter< GT > SA>
const Array< Node * > & Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::id_to_node ( ) const
inlinenoexcept

Definition at line 343 of file Tree_Decomposition.H.

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

◆ index_nodes()

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

Definition at line 189 of file Tree_Decomposition.H.

References ah_domain_error_if, ah_runtime_error_unless, Aleph::blossom_maximum_cardinality_matching(), Aleph::Array< T >::create(), 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<AlephGraph GT, ArcFilter< GT > SA>
bool Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::is_empty ( ) const
inlinenoexcept

Definition at line 339 of file Tree_Decomposition.H.

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

◆ node_of()

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

Definition at line 365 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<AlephGraph GT, ArcFilter< GT > 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 176 of file Tree_Decomposition.H.

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

◆ root()

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

Definition at line 340 of file Tree_Decomposition.H.

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

◆ root_id()

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

Definition at line 341 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<AlephGraph GT, ArcFilter< GT > SA>
size_t Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::size ( ) const
inlinenoexcept

Definition at line 338 of file Tree_Decomposition.H.

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

◆ validate_connected_acyclic()

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

Definition at line 282 of file Tree_Decomposition.H.

References Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::adjacency_, ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Array< T >::create(), 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<AlephGraph GT, ArcFilter< GT > 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 371 of file Tree_Decomposition.H.

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

Member Data Documentation

◆ adjacency_

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

Definition at line 174 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<AlephGraph GT, ArcFilter< GT > SA>
const GT* Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::graph_ = nullptr
private

Definition at line 165 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<AlephGraph GT, ArcFilter< GT > SA>
Array<Node *> Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::id_to_node_
private

Definition at line 172 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<AlephGraph GT, ArcFilter< GT > SA>
size_t Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::n_ = 0
private

Definition at line 170 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<AlephGraph GT, ArcFilter< GT > SA>
MapOLhash<Node *, size_t> Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::node_to_id_
private

Definition at line 173 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<AlephGraph GT, ArcFilter< GT > SA>
constexpr size_t Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::NONE = std::numeric_limits<size_t>::max()
staticconstexpr

Definition at line 160 of file Tree_Decomposition.H.

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

◆ root_

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

Definition at line 167 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<AlephGraph GT, ArcFilter< GT > SA>
size_t Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::root_id_ = NONE
private

Definition at line 168 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<AlephGraph GT, ArcFilter< GT > SA>
SA Aleph::tree_decomposition_detail::Rooted_Tree_Topology< GT, SA >::sa_
private

Definition at line 166 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: