63 return lookup_( node_index_a, node_index_b, root_index );
68 auto const idx = lookup_( node_a.
index(), node_b.
index(), root_node.
index() );
74 return lookup_( node_index_a, node_index_b, root_idx_ );
79 auto const idx = lookup_( node_a.
index(), node_b.
index(), root_idx_ );
87 void LcaLookup::init_(
Tree const& tree )
98 std::vector<RmqIntType> eulertour_levels;
99 eulertour_first_occurrence_.resize( tree.
node_count() );
101 eulertour_first_occurrence_.begin(),
102 eulertour_first_occurrence_.end(),
103 std::numeric_limits<size_t>::max()
108 auto const node_idx = it.node().index();
110 if( dists_to_root[ node_idx ] >=
static_cast<size_t>( std::numeric_limits<RmqIntType>::max() )) {
111 throw std::runtime_error(
"Tree too large for building LCA Lookup." );
114 eulertour_order_.push_back( node_idx );
115 eulertour_levels.push_back(
static_cast<RmqIntType
>( dists_to_root[ node_idx ] ));
116 if( eulertour_first_occurrence_[ node_idx ] == std::numeric_limits<size_t>::max() ) {
117 eulertour_first_occurrence_[ node_idx ] = eulertour_order_.size() - 1;
120 eulertour_rmq_ = utils::RangeMinimumQuery( eulertour_levels );
123 size_t LcaLookup::eulertour_query_(
size_t i,
size_t j )
const
126 return eulertour_rmq_.
query( i, j );
128 return eulertour_rmq_.
query( j, i );
132 size_t LcaLookup::lookup_(
size_t node_index_a,
size_t node_index_b,
size_t root_index )
const
134 auto const sz = eulertour_first_occurrence_.size();
135 if( node_index_a >= sz || node_index_b >= sz || root_index >= sz ) {
136 throw std::invalid_argument(
"Invalid index out of bounds for LCA lookup." );
139 size_t u_euler_idx = eulertour_first_occurrence_[ node_index_a ];
140 size_t v_euler_idx = eulertour_first_occurrence_[ node_index_b ];
141 size_t r_euler_idx = eulertour_first_occurrence_[ root_index ];
143 if( root_index == root_idx_ ) {
144 return eulertour_order_[ eulertour_query_( u_euler_idx, v_euler_idx )];
150 size_t candidate_a = eulertour_order_[ eulertour_query_( u_euler_idx, v_euler_idx )];
151 size_t candidate_b = eulertour_order_[ eulertour_query_( u_euler_idx, r_euler_idx )];
152 size_t candidate_c = eulertour_order_[ eulertour_query_( v_euler_idx, r_euler_idx )];
154 if( candidate_a == candidate_b ) {
156 }
else if( candidate_a == candidate_c ) {
159 assert( candidate_b == candidate_c );