57#include <lal/linear_arrangement.hpp>
58#include <lal/graphs/rooted_tree.hpp>
59#include <lal/detail/array.hpp>
60#include <lal/iterators/E_iterator.hpp>
61#include <lal/detail/graphs/size_subtrees.hpp>
62#include <lal/detail/sorting/counting_sort.hpp>
63#include <lal/detail/properties/tree_centroid.hpp>
94static inline constexpr bool is_even(uint64_t i)
noexcept {
return (i&0x1) == 0; }
123template <sorting::sort_type type>
128 const uint64_t n = t.get_num_nodes();
129 const node r = t.get_root();
137 const std::size_t k = t.are_size_subtrees_valid() ? 0 : t.get_num_nodes();
144 if (t.are_size_subtrees_valid()) {
146 while (not E_it.
end()) {
148 const node v = e.second;
149 const uint64_t suv = t.get_num_nodes_subtree(v);
159 while (not E_it.
end()) {
161 const node v = e.second;
162 const uint64_t suv = size_subtrees[v];
175 [](
const edge_size& T) -> std::size_t {
return T.size; },
184 const auto [u, v] = T.
e;
185 const uint64_t nv = T.size;
186 L[u].push_back({v,nv});
188 assert(t.has_edge(u,v));
193 for (
node u = 0; u < n; ++u) {
194 assert(L[u].size() == t.get_out_degree(u));
Rooted tree graph class.
Definition rooted_tree.hpp:109
Iterator over the set of edges of a graph.
Definition E_iterator.hpp:97
void next() noexcept
Moves the iterator to the next edge.
Definition E_iterator.hpp:142
bool end() const noexcept
Returns true if the end of the iteration was reached.
Definition E_iterator.hpp:117
const edge & get_edge() const noexcept
Returns the current edge.
Definition E_iterator.hpp:120
unsigned char side
Useful typedef to denote relative position.
Definition Dopt_utils.hpp:74
static constexpr side other_side(side s) noexcept
Other side of a vertex. If s is RIGHT_SIDE, returns LEFT_SIDE.
Definition Dopt_utils.hpp:91
static constexpr place PLACE_RIGHT_OF
A vertex is to be placed to the right of a vertex.
Definition Dopt_utils.hpp:79
static constexpr side LEFT_SIDE
Left side of a vertex.
Definition Dopt_utils.hpp:86
static constexpr char NO_ANCHOR
The tree is not anchored.
Definition Dopt_utils.hpp:101
static constexpr char ANCHOR
The tree is anchored.
Definition Dopt_utils.hpp:103
void make_sorted_adjacency_list_rooted(const graphs::rooted_tree &t, std::vector< std::vector< node_size > > &L) noexcept
Make a sorted, rooted adjacency list sorted according to the sizes of the subtrees of the input roote...
Definition Dopt_utils.hpp:125
static constexpr side RIGHT_SIDE
Right side of a vertex.
Definition Dopt_utils.hpp:84
static constexpr char RIGHT_ANCHOR
The tree is right-anchored.
Definition Dopt_utils.hpp:99
static constexpr bool is_even(uint64_t i) noexcept
Is an integer number even?
Definition Dopt_utils.hpp:94
static constexpr char LEFT_ANCHOR
The tree is left-anchored.
Definition Dopt_utils.hpp:97
static constexpr place PLACE_LEFT_OF
A vertex is to be placed to the left of a vertex.
Definition Dopt_utils.hpp:77
static constexpr place PLACE_NONE_OF
There is no vertex to use as reference to determine the side.
Definition Dopt_utils.hpp:81
unsigned char place
Useful typedef to denote relative position.
Definition Dopt_utils.hpp:72
void counting_sort(const value_iterator_t begin, const value_iterator_t end, const std::size_t largest_key_plus_1, const Callable &key, countingsort::memory< value_t > &mem) noexcept
Counting sort algorithm with reusable memory.
Definition counting_sort.hpp:152
void get_size_subtrees(const tree_t &t, const node u, const node v, uint64_t *const sizes) noexcept
Calculate the size of every subtree of the tree t.
Definition size_subtrees.hpp:74
Main namespace of the library.
Definition basic_types.hpp:48
std::pair< node, node > edge
See Edge page for further details.
Definition basic_types.hpp:56
std::vector< edge > edge_list
See Edge list page for further details.
Definition basic_types.hpp:60
uint64_t node
Node type. See Node / Vertex page for further details.
Definition basic_types.hpp:51
Wrapper of a C array for automatic deallocation of memory.
Definition array.hpp:59
T * begin() noexcept
Non-constant raw pointer to first element.
Definition array.hpp:300
Struct used in many algorithms to sort edges according to some integer value.
Definition pairs_utils.hpp:65
edge e
Edege.
Definition pairs_utils.hpp:67
Memory used for the counting sort algorithm.
Definition counting_sort.hpp:72
array< std::size_t > count
Amount of times the key of an element occurs.
Definition counting_sort.hpp:74