LAL: Linear Arrangement Library 24.10.00
A library focused on algorithms on linear arrangements of graphs.
Loading...
Searching...
No Matches
Dopt_utils.hpp
1/*********************************************************************
2 *
3 * Linear Arrangement Library - A library that implements a collection
4 * algorithms for linear arrangments of graphs.
5 *
6 * Copyright (C) 2019 - 2024
7 *
8 * This file is part of Linear Arrangement Library. The full code is available
9 * at:
10 * https://github.com/LAL-project/linear-arrangement-library.git
11 *
12 * Linear Arrangement Library is free software: you can redistribute it
13 * and/or modify it under the terms of the GNU Affero General Public License
14 * as published by the Free Software Foundation, either version 3 of the
15 * License, or (at your option) any later version.
16 *
17 * Linear Arrangement Library is distributed in the hope that it will be
18 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Affero General Public License for more details.
21 *
22 * You should have received a copy of the GNU Affero General Public License
23 * along with Linear Arrangement Library. If not, see <http://www.gnu.org/licenses/>.
24 *
25 * Contact:
26 *
27 * LluĂ­s Alemany Puig (lluis.alemany.puig@upc.edu)
28 * LQMC (Quantitative, Mathematical, and Computational Linguisitcs)
29 * CQL (Complexity and Quantitative Linguistics Lab)
30 * Jordi Girona St 1-3, Campus Nord UPC, 08034 Barcelona. CATALONIA, SPAIN
31 * Webpage: https://cqllab.upc.edu/people/lalemany/
32 *
33 * Juan Luis Esteban (esteban@cs.upc.edu)
34 * LOGPROG: Logics and Programming Research Group
35 * Office 110, Omega building
36 * Jordi Girona St 1-3, Campus Nord UPC, 08034 Barcelona. CATALONIA, SPAIN
37 * Webpage: https://www.cs.upc.edu/~esteban/
38 *
39 * Ramon Ferrer i Cancho (rferrericancho@cs.upc.edu)
40 * LQMC (Quantitative, Mathematical, and Computational Linguisitcs)
41 * CQL (Complexity and Quantitative Linguistics Lab)
42 * Office 220, Omega building
43 * Jordi Girona St 1-3, Campus Nord UPC, 08034 Barcelona. CATALONIA, SPAIN
44 * Webpage: https://cqllab.upc.edu/people/rferrericancho/
45 *
46 ********************************************************************/
47
48#pragma once
49
50// C++ includes
51#if defined DEBUG
52#include <cassert>
53#endif
54#include <vector>
55
56// lal includes
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>
64
65namespace lal {
66namespace detail {
67
69namespace Dopt_utils {
70
72typedef unsigned char place;
74typedef unsigned char side;
75
77static constexpr place PLACE_LEFT_OF = 0;
79static constexpr place PLACE_RIGHT_OF = 1;
81static constexpr place PLACE_NONE_OF = 2;
82
84static constexpr side RIGHT_SIDE = 0;
86static constexpr side LEFT_SIDE = 1;
87
88// if s = 0 then (s+1)&0x1 = 1
89// if s = 1 then (s+1)&0x1 = 0
91static inline constexpr side other_side(side s) noexcept { return ((s + 1)&0x1); }
92
94static inline constexpr bool is_even(uint64_t i) noexcept { return (i&0x1) == 0; }
95
97static constexpr char LEFT_ANCHOR = -1;
99static constexpr char RIGHT_ANCHOR = 1;
101static constexpr char NO_ANCHOR = 0;
103static constexpr char ANCHOR = 1;
104
105/* ************************************************************************** */
106/* ----------------------- ROOTED ADJACENCY LISTS --------------------------- */
107
108/* Functions to calculate the sorted, rooted
109 * adjacency list of rooted and free trees.
110 */
111
123template <sorting::sort_type type>
125(const graphs::rooted_tree& t, std::vector<std::vector<node_size>>& L)
126noexcept
127{
128 const uint64_t n = t.get_num_nodes();
129 const node r = t.get_root();
130
131 // for every edge (u,v), store the tuple
132 // (n_v, (u,v))
133 // at L[u]
135
136 {
137 const std::size_t k = t.are_size_subtrees_valid() ? 0 : t.get_num_nodes();
138 array<uint64_t> size_subtrees(k, 0);
139
141 auto it = edge_list.begin();
142
144 if (t.are_size_subtrees_valid()) {
145 // use the sizes that are already calculated
146 while (not E_it.end()) {
147 const edge e = E_it.get_edge();
148 const node v = e.second;
149 const uint64_t suv = t.get_num_nodes_subtree(v);
150 *it++ = {e, suv};
151 ++memcs.count[suv];
152
153 E_it.next();
154 }
155 }
156 else {
157 // fill in the size of the subtrees
158 get_size_subtrees(t, r, size_subtrees.begin());
159 while (not E_it.end()) {
160 const edge e = E_it.get_edge();
161 const node v = e.second;
162 const uint64_t suv = size_subtrees[v];
163 *it++ = {e, suv};
164 ++memcs.count[suv];
165
166 E_it.next();
167 }
168 }
169
170 // sort all tuples in L using the size of the subtree
172 <edge_size, type, true>
173 (
174 edge_list.begin(), edge_list.end(), n,
175 [](const edge_size& T) -> std::size_t { return T.size; },
176 memcs
177 );
178 }
179
180 // M[u] : adjacency list of vertex u sorted decreasingly according
181 // to the sizes of the subtrees.
182 // This is used to find the optimal projective arrangement of the tree.
183 for (const auto& T : edge_list) {
184 const auto [u, v] = T.e;
185 const uint64_t nv = T.size;
186 L[u].push_back({v,nv});
187#if defined DEBUG
188 assert(t.has_edge(u,v));
189#endif
190 }
191
192#if defined DEBUG
193 for (node u = 0; u < n; ++u) {
194 assert(L[u].size() == t.get_out_degree(u));
195 }
196#endif
197}
198
199} // -- namespcae proj_plan_opt_utils
200} // -- namespace detail
201} // -- namespace lal
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