Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | Private Types | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag > Class Template Reference

Link-Cut Tree with edge weights and path aggregations. More...

#include <tpl_link_cut_tree_with_edges.H>

Inheritance diagram for Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >:
[legend]
Collaboration diagram for Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >:
[legend]

Classes

struct  EdgeKey
 
struct  EdgeKeyEq
 
struct  EdgeKeyHash
 
struct  EdgeRec
 
struct  ExportData
 Data stored in each exported Tree_Node. More...
 
struct  NodePtrEq
 

Public Types

using Node = typename InternalLCT::Node
 Opaque vertex handle (same type as internal LCT node).
 

Public Member Functions

 Gen_Link_Cut_Tree_WithEdges ()=default
 Default constructor for an empty Link-Cut Tree with edges.
 
 Gen_Link_Cut_Tree_WithEdges (const Gen_Link_Cut_Tree_WithEdges &)=delete
 Deleted copy constructor.
 
Gen_Link_Cut_Tree_WithEdges & operator= (const Gen_Link_Cut_Tree_WithEdges &)=delete
 Deleted copy assignment.
 
 Gen_Link_Cut_Tree_WithEdges (Gen_Link_Cut_Tree_WithEdges &&)=delete
 Deleted move constructor.
 
Gen_Link_Cut_Tree_WithEdges & operator= (Gen_Link_Cut_Tree_WithEdges &&)=delete
 Deleted move assignment.
 
Node * make_vertex (const VT &val=VT{})
 Create an isolated vertex.
 
size_t size () const noexcept
 Total number of user vertices (excluding internal edge nodes).
 
size_t num_components () const noexcept
 Number of connected components.
 
size_t num_edges () const noexcept
 Number of edges in the forest.
 
const VT & get_vertex_val (Node *x) const
 Read the stored payload of a user vertex.
 
void set_vertex_val (Node *x, const VT &val)
 Replace the stored payload of a user vertex.
 
bool connected (Node *u, Node *v)
 Test whether u and v are in the same tree.
 
void link (Node *u, Node *v, const ET &weight)
 Add an edge (u, v) with weight weight.
 
void cut (Node *u, Node *v)
 Remove the edge between u and v.
 
ET path_query (Node *u, Node *v)
 Aggregate edge values on the path from u to v.
 
void make_root (Node *x)
 Make x the root of its represented tree.
 
Node * find_root (Node *x)
 Find the root of the tree containing x.
 
size_t path_size (Node *u, Node *v)
 Number of user vertices on the path from u to v.
 
void set_edge_val (Node *u, Node *v, const ET &new_weight)
 Update the weight of an existing edge (u, v).
 
const ET & get_edge_val (Node *u, Node *v)
 Read the weight of an existing edge (u, v).
 
Tree_Node< ExportData > * export_to_tree_node (Node *root)
 Export the represented tree rooted at root as a Tree_Node.
 

Private Types

using InternalLCT = Gen_Link_Cut_Tree< ET, EdgeMonoid, LazyTag >
 

Private Member Functions

size_t find_edge_idx (Node *u, Node *v) const noexcept
 
void remove_edge_at (size_t idx)
 
const VT & lookup_vertex_val (Node *nd) const
 
void require_vertex (Node *x) const
 

Static Private Member Functions

static size_t edge_key_hash (const EdgeKey &key) noexcept
 
static size_t node_ptr_hash (Node *const &nd) noexcept
 
static EdgeKey make_edge_key (Node *u, Node *v) noexcept
 

Private Attributes

InternalLCT lct_
 
Array< EdgeRec > edge_recs_
 
DynMapHash< EdgeKey, size_t, EdgeKeyEq > edge_idx_
 
DynMapHash< Node *, VT, NodePtrEq > vertex_vals_
 
size_t n_vertices_ = 0
 
size_t n_components_ = 0
 

Detailed Description

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
requires LCTMonoid<EdgeMonoid, ET>
class Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >

Link-Cut Tree with edge weights and path aggregations.

Template Parameters
VTVertex payload type (stored but not aggregated).
ETEdge value type (aggregated via EdgeMonoid).
EdgeMonoidAssociative combiner for edge aggregation.
LazyTagLazy-tag policy for deferred edge updates.

Definition at line 82 of file tpl_link_cut_tree_with_edges.H.

Member Typedef Documentation

◆ InternalLCT

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
using Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::InternalLCT = Gen_Link_Cut_Tree<ET, EdgeMonoid, LazyTag>
private

Definition at line 84 of file tpl_link_cut_tree_with_edges.H.

◆ Node

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
using Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::Node = typename InternalLCT::Node

Opaque vertex handle (same type as internal LCT node).

Definition at line 88 of file tpl_link_cut_tree_with_edges.H.

Constructor & Destructor Documentation

◆ Gen_Link_Cut_Tree_WithEdges() [1/3]

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::Gen_Link_Cut_Tree_WithEdges ( )
default

Default constructor for an empty Link-Cut Tree with edges.

◆ Gen_Link_Cut_Tree_WithEdges() [2/3]

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::Gen_Link_Cut_Tree_WithEdges ( const Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag > &  )
delete

Deleted copy constructor.

◆ Gen_Link_Cut_Tree_WithEdges() [3/3]

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::Gen_Link_Cut_Tree_WithEdges ( Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag > &&  )
delete

Deleted move constructor.

Member Function Documentation

◆ connected()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
bool Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::connected ( Node *  u,
Node *  v 
)
inline

Test whether u and v are in the same tree.

Exceptions
std::invalid_argumentif either handle is null.
std::domain_errorif either handle does not belong to this tree.

Definition at line 278 of file tpl_link_cut_tree_with_edges.H.

References Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::connected(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::lct_, and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::require_vertex().

Referenced by TEST().

◆ cut()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
void Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::cut ( Node *  u,
Node *  v 
)
inline

Remove the edge between u and v.

Finds the hidden edge node and cuts both internal links u — e and e — v. The orphaned hidden edge node is then destroyed immediately.

Exceptions
std::invalid_argumentif either handle is null.
std::domain_errorif no edge (u, v) exists.

Definition at line 351 of file tpl_link_cut_tree_with_edges.H.

References ah_domain_error_if, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::cut(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::destroy_vertex(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::edge_recs_, Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::find_edge_idx(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::lct_, Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::n_components_, Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::remove_edge_at(), and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::require_vertex().

Referenced by TEST().

◆ edge_key_hash()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
static size_t Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::edge_key_hash ( const EdgeKey &  key)
inlinestaticprivatenoexcept

Definition at line 126 of file tpl_link_cut_tree_with_edges.H.

◆ export_to_tree_node()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
Tree_Node< ExportData > * Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::export_to_tree_node ( Node *  root)
inline

Export the represented tree rooted at root as a Tree_Node.

Materializes the forest component containing root into an explicit n-ary tree of Tree_Node<ExportData>. Each exported node stores a back-pointer to the original LCT vertex and the weight of the edge to its parent (the root stores EdgeMonoid::identity()).

The caller owns the returned tree and must free it with destroy_tree(result).

Parameters
rootVertex to use as the root.
Returns
Newly allocated Tree_Node<ExportData> *.
Exceptions
std::invalid_argumentif root is null.
Complexity
O(E log V) where E is the number of managed edges and V is the number of vertices in the component.

Definition at line 485 of file tpl_link_cut_tree_with_edges.H.

References Aleph::and, Aleph::Array< T >::append(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::connected(), Primes::DefaultPrime, destroy_tree(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::edge_recs_, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::get_val(), Aleph::DynMapHashTable< Key, Data, HashTable, Cmp >::insert(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::lct_, Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::lookup_vertex_val(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::make_root(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::node_ptr_hash(), r, Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::require_vertex(), root(), Aleph::DynMapHashTable< Key, Data, HashTable, Cmp >::search(), Aleph::Array< T >::size(), and w.

◆ find_edge_idx()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
size_t Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::find_edge_idx ( Node *  u,
Node *  v 
) const
inlineprivatenoexcept

Definition at line 160 of file tpl_link_cut_tree_with_edges.H.

References Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::edge_idx_, Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::edge_recs_, and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::make_edge_key().

Referenced by Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::cut(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::get_edge_val(), and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::set_edge_val().

◆ find_root()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
Node * Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::find_root ( Node *  x)
inline

Find the root of the tree containing x.

Note
After rerooting via make_root(), the root is always a vertex node.
Exceptions
std::invalid_argumentif x is null.
std::domain_errorif x does not belong to this tree.

Definition at line 400 of file tpl_link_cut_tree_with_edges.H.

References Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::find_root(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::lct_, and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::require_vertex().

◆ get_edge_val()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
const ET & Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::get_edge_val ( Node *  u,
Node *  v 
)
inline

Read the weight of an existing edge (u, v).

Exceptions
std::invalid_argumentif either handle is null.
std::domain_errorif no edge (u, v) exists.

Definition at line 443 of file tpl_link_cut_tree_with_edges.H.

References ah_domain_error_if, Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::edge_recs_, Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::find_edge_idx(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::get_val(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::lct_, and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::require_vertex().

◆ get_vertex_val()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
const VT & Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::get_vertex_val ( Node *  x) const
inline

Read the stored payload of a user vertex.

Exceptions
std::invalid_argumentif x is null.
std::domain_errorif x does not belong to this tree.

Definition at line 257 of file tpl_link_cut_tree_with_edges.H.

References Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::lookup_vertex_val().

◆ link()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
void Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::link ( Node *  u,
Node *  v,
const ET &  weight 
)
inline

Add an edge (u, v) with weight weight.

Internally creates a hidden edge node e with value weight and links the chain u — e — v in the underlying splay forest.

Parameters
uFirst endpoint.
vSecond endpoint.
weightEdge value / weight.
Exceptions
std::invalid_argumentif u or v is null, or u == v.
std::domain_errorif u and v are already connected.

Definition at line 296 of file tpl_link_cut_tree_with_edges.H.

References ah_domain_error_if, ah_invalid_argument_if, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::connected(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::cut(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::destroy_vertex(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::edge_idx_, Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::edge_recs_, Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::lct_, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::link(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::make_edge_key(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_vertex(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::n_components_, and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::require_vertex().

Referenced by TEST().

◆ lookup_vertex_val()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
const VT & Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::lookup_vertex_val ( Node *  nd) const
inlineprivate

Definition at line 180 of file tpl_link_cut_tree_with_edges.H.

References ah_domain_error_if, ah_invalid_argument_if, Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::vertex_vals_.

Referenced by Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::export_to_tree_node(), and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::get_vertex_val().

◆ make_edge_key()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
static EdgeKey Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::make_edge_key ( Node *  u,
Node *  v 
)
inlinestaticprivatenoexcept

Definition at line 155 of file tpl_link_cut_tree_with_edges.H.

Referenced by Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::find_edge_idx(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::link(), and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::remove_edge_at().

◆ make_root()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
void Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::make_root ( Node *  x)
inline

Make x the root of its represented tree.

Exceptions
std::invalid_argumentif x is null.
std::domain_errorif x does not belong to this tree.

Definition at line 386 of file tpl_link_cut_tree_with_edges.H.

References Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::lct_, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_root(), and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::require_vertex().

Referenced by Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::export_to_tree_node().

◆ make_vertex()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
Node * Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::make_vertex ( const VT &  val = VT{})
inline

Create an isolated vertex.

The vertex payload is stored in the wrapper while the internal LCT node carries EdgeMonoid::identity() so it stays transparent to edge aggregation.

Parameters
valVertex payload stored alongside the opaque handle.
Returns
Stable handle to the new vertex.

Definition at line 220 of file tpl_link_cut_tree_with_edges.H.

Referenced by TEST(), and TEST().

◆ node_ptr_hash()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
static size_t Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::node_ptr_hash ( Node *const &  nd)
inlinestaticprivatenoexcept

Definition at line 131 of file tpl_link_cut_tree_with_edges.H.

References Aleph::divide_and_conquer_partition_dp().

Referenced by Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::export_to_tree_node().

◆ num_components()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
size_t Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::num_components ( ) const
inlinenoexcept

Number of connected components.

Definition at line 241 of file tpl_link_cut_tree_with_edges.H.

References Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::n_components_.

◆ num_edges()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
size_t Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::num_edges ( ) const
inlinenoexcept

Number of edges in the forest.

Definition at line 247 of file tpl_link_cut_tree_with_edges.H.

References Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::edge_recs_.

◆ operator=() [1/2]

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
Gen_Link_Cut_Tree_WithEdges & Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::operator= ( const Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag > &  )
delete

Deleted copy assignment.

◆ operator=() [2/2]

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
Gen_Link_Cut_Tree_WithEdges & Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::operator= ( Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag > &&  )
delete

Deleted move assignment.

◆ path_query()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
ET Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::path_query ( Node *  u,
Node *  v 
)
inline

Aggregate edge values on the path from u to v.

Since vertex nodes carry EdgeMonoid::identity(), the returned value reflects only edge weights along the path.

Exceptions
std::invalid_argumentif either handle is null.
std::domain_errorif u and v are not connected.

Definition at line 374 of file tpl_link_cut_tree_with_edges.H.

References Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::lct_, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::path_query(), and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::require_vertex().

Referenced by TEST().

◆ path_size()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
size_t Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::path_size ( Node *  u,
Node *  v 
)
inline

Number of user vertices on the path from u to v.

Internally each represented edge becomes a hidden node, so the wrapped LCT reports a path length of 2k - 1 for a visible path with k vertices. This wrapper translates the internal count back to the public vertex count.

Exceptions
std::domain_errorif either handle does not belong to this tree.

Definition at line 415 of file tpl_link_cut_tree_with_edges.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::lct_, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::path_size(), and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::require_vertex().

◆ remove_edge_at()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
void Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::remove_edge_at ( size_t  idx)
inlineprivate

Definition at line 166 of file tpl_link_cut_tree_with_edges.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::edge_idx_, Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::edge_recs_, and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::make_edge_key().

Referenced by Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::cut().

◆ require_vertex()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
void Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::require_vertex ( Node *  x) const
inlineprivate

Definition at line 188 of file tpl_link_cut_tree_with_edges.H.

References ah_domain_error_if, ah_invalid_argument_if, and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::vertex_vals_.

Referenced by Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::connected(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::cut(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::export_to_tree_node(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::find_root(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::get_edge_val(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::link(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::make_root(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::path_query(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::path_size(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::set_edge_val(), and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::set_vertex_val().

◆ set_edge_val()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
void Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::set_edge_val ( Node *  u,
Node *  v,
const ET &  new_weight 
)
inline

Update the weight of an existing edge (u, v).

Exceptions
std::invalid_argumentif either handle is null.
std::domain_errorif no edge (u, v) exists.

Definition at line 428 of file tpl_link_cut_tree_with_edges.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::edge_recs_, Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::find_edge_idx(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::lct_, Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::require_vertex(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::set_val().

◆ set_vertex_val()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
void Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::set_vertex_val ( Node *  x,
const VT &  val 
)
inline

Replace the stored payload of a user vertex.

Exceptions
std::invalid_argumentif x is null.
std::domain_errorif x does not belong to this tree.

Definition at line 267 of file tpl_link_cut_tree_with_edges.H.

References Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::require_vertex(), and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::vertex_vals_.

◆ size()

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
size_t Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::size ( ) const
inlinenoexcept

Total number of user vertices (excluding internal edge nodes).

Definition at line 238 of file tpl_link_cut_tree_with_edges.H.

References Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::n_vertices_.

Member Data Documentation

◆ edge_idx_

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
DynMapHash<EdgeKey, size_t, EdgeKeyEq> Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::edge_idx_
private
Initial value:
{
Primes::DefaultPrime, edge_key_hash, EdgeKeyEq()
}
Aleph::Gen_Link_Cut_Tree_WithEdges::edge_key_hash
static size_t edge_key_hash(const EdgeKey &key) noexcept
Definition tpl_link_cut_tree_with_edges.H:126
Primes::DefaultPrime
const unsigned long DefaultPrime
Default prime number used when no specific size is requested.
Definition primes.C:381

Definition at line 146 of file tpl_link_cut_tree_with_edges.H.

Referenced by Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::find_edge_idx(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::link(), and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::remove_edge_at().

◆ edge_recs_

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
Array<EdgeRec> Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::edge_recs_
private

Definition at line 144 of file tpl_link_cut_tree_with_edges.H.

Referenced by Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::cut(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::export_to_tree_node(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::find_edge_idx(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::get_edge_val(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::link(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::num_edges(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::remove_edge_at(), and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::set_edge_val().

◆ lct_

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
InternalLCT Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::lct_
private

Definition at line 143 of file tpl_link_cut_tree_with_edges.H.

Referenced by Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::connected(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::cut(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::export_to_tree_node(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::find_root(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::get_edge_val(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::link(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::make_root(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::path_query(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::path_size(), and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::set_edge_val().

◆ n_components_

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
size_t Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::n_components_ = 0
private

Definition at line 153 of file tpl_link_cut_tree_with_edges.H.

Referenced by Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::cut(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::link(), and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::num_components().

◆ n_vertices_

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
size_t Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::n_vertices_ = 0
private

Definition at line 152 of file tpl_link_cut_tree_with_edges.H.

Referenced by Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::size().

◆ vertex_vals_

template<typename VT = int, typename ET = int, class EdgeMonoid = DefaultMonoid<ET>, class LazyTag = NoLazyTag<ET>>
DynMapHash<Node *, VT, NodePtrEq> Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::vertex_vals_
private
Initial value:
{
Primes::DefaultPrime, node_ptr_hash, NodePtrEq()
}
Aleph::Gen_Link_Cut_Tree_WithEdges::node_ptr_hash
static size_t node_ptr_hash(Node *const &nd) noexcept
Definition tpl_link_cut_tree_with_edges.H:131

Definition at line 149 of file tpl_link_cut_tree_with_edges.H.

Referenced by Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::lookup_vertex_val(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::require_vertex(), and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::set_vertex_val().

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