LAL: Linear Arrangement Library 24.10.00
A library focused on algorithms on linear arrangements of graphs.
Loading...
Searching...
No Matches
set_maximum_arrangements.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 * Ramon Ferrer i Cancho (rferrericancho@cs.upc.edu)
34 * LQMC (Quantitative, Mathematical, and Computational Linguisitcs)
35 * CQL (Complexity and Quantitative Linguistics Lab)
36 * Office 220, Omega building
37 * Jordi Girona St 1-3, Campus Nord UPC, 08034 Barcelona. CATALONIA, SPAIN
38 * Webpage: https://cqllab.upc.edu/people/rferrericancho/
39 *
40 ********************************************************************/
41
42#pragma once
43
44// C++ includes
45#include <vector>
46#if defined DEBUG
47#include <cassert>
48#endif
49
50// lal includes
51#include <lal/linear_arrangement.hpp>
52#include <lal/graphs/free_tree.hpp>
53#include <lal/detail/linarr/level_signature.hpp>
54
55namespace lal {
56namespace detail {
57namespace DMax {
58namespace unconstrained {
59
71private:
74
75public:
78
81
83 void init() noexcept {
84 m_max_value = 0;
85 }
86
87 /* GETTERS */
88
90 [[nodiscard]] uint64_t get_max_value() const noexcept
91 { return m_max_value; }
92
94 [[nodiscard]] std::size_t get_num_representatives() const noexcept
95 { return m_representatives.size(); }
96
98 [[nodiscard]] std::vector<linear_arrangement>&& retrieve_all_representatives()
99 noexcept
100 {
101 return std::move(m_representatives);
102 }
103
105 [[nodiscard]] std::size_t get_size_class(const std::size_t i) const noexcept {
106#if defined DEBUG
107 assert(i < m_amount.size());
108#endif
109 return m_amount[i];
110 }
111
113 [[nodiscard]] const linear_arrangement& get_representative(const std::size_t i)
114 const noexcept
115 {
116#if defined DEBUG
117 assert(i < m_representatives.size());
118#endif
119 return m_representatives[i];
120 }
121
124 (const std::size_t i)
125 const noexcept
126 {
127#if defined DEBUG
128 assert(i < m_level_signatures.size());
129#endif
130 return m_level_signatures[i];
131 }
132
133 /* MODIFIERS */
134
143 void add(const uint64_t value, const linear_arrangement& arr) noexcept {
144 if (m_max_value < value) {
145 m_max_value = value;
146
147 m_representatives.clear();
149 m_level_signatures.clear();
150 m_amount.clear();
151
153
154 m_representatives.push_back(arr);
156 m_level_signatures.push_back(std::move(L));
157 m_amount.push_back(1);
158 }
159 else if (m_max_value == value) {
161 const std::size_t idx_repr = find_representative(L);
162
163 if (idx_repr == m_representatives.size()) {
164 m_representatives.push_back(arr);
166 m_level_signatures.push_back(std::move(L));
167 m_amount.push_back(1);
168 }
169 else {
170 ++m_amount[idx_repr];
171 }
172 }
173 }
174
181 void merge(set_maximum_arrangements&& max_arrs) noexcept {
182 // nothing to do
183 if (m_max_value > max_arrs.m_max_value) {
184 return;
185 }
186
187 // just copy the contents of 'max_arrs'
188 if (m_max_value < max_arrs.m_max_value) {
189 m_representatives.clear();
191 m_level_signatures.clear();
192 m_amount.clear();
193
194 m_max_value = max_arrs.m_max_value;
195 m_representatives = std::move(max_arrs.m_representatives);
196 m_mirrored_level_signatures = std::move(max_arrs.m_mirrored_level_signatures);
197 m_level_signatures = std::move(max_arrs.m_level_signatures);
198 m_amount = std::move(max_arrs.m_amount);
199 return;
200 }
201
202 // actually merge the two sets
203 for (std::size_t i = 0; i < max_arrs.m_representatives.size(); ++i) {
204 // find the representative's index in this set of arrangements
205 const std::size_t idx_repr = find_representative(max_arrs.m_level_signatures[i]);
206
207 // update collection
208 if (idx_repr < m_representatives.size()) {
209 ++m_amount[idx_repr];
210 }
211 else {
212 m_representatives.push_back(std::move(max_arrs.m_representatives[i]));
213 m_mirrored_level_signatures.push_back(std::move(max_arrs.m_mirrored_level_signatures[i]));
214 m_level_signatures.push_back(std::move(max_arrs.m_level_signatures[i]));
215 m_amount.push_back(max_arrs.m_amount[i]);
216 }
217 }
218 }
219
220private:
227 [[nodiscard]] std::size_t find_representative
229 const noexcept
230 {
231 // The isomorphism to use is based on 'simple' arrangement isomorphism
232 for (std::size_t i = 0; i < m_representatives.size(); ++i) {
233
234 const bool isomorphic =
235 (m_level_signatures[i] == L) or
237
238 if (isomorphic) { return i; }
239 }
240
241 return m_representatives.size();
242 }
243
244private:
247
249 uint64_t m_max_value;
251 std::vector<linear_arrangement> m_representatives;
253 std::vector<level_signature_per_position> m_mirrored_level_signatures;
255 std::vector<level_signature_per_position> m_level_signatures;
257 std::vector<uint64_t> m_amount;
258};
259
260} // -- namespace unconstrained
261} // -- namespace DMax
262} // -- namespace detail
263} // -- namespace lal
Set of maximum arrangements up to isomorphism.
Definition set_maximum_arrangements.hpp:70
void merge(set_maximum_arrangements &&max_arrs) noexcept
Merges another set of maximum arrangements into this one.
Definition set_maximum_arrangements.hpp:181
const level_signature_per_position & get_level_signature(const std::size_t i) const noexcept
Returns the level signature of the i-th representative.
Definition set_maximum_arrangements.hpp:124
static constexpr level_signature_type per_position
Typedef to write less.
Definition set_maximum_arrangements.hpp:73
const linear_arrangement & get_representative(const std::size_t i) const noexcept
Returns the i-th representative.
Definition set_maximum_arrangements.hpp:113
std::vector< level_signature_per_position > m_level_signatures
List of level signatures per representatives.
Definition set_maximum_arrangements.hpp:255
std::size_t find_representative(const level_signature_per_position &L) const noexcept
Find the level signature isomorphic to L.
Definition set_maximum_arrangements.hpp:228
std::size_t get_size_class(const std::size_t i) const noexcept
Returns the multiplicity of the i-th representative.
Definition set_maximum_arrangements.hpp:105
uint64_t get_max_value() const noexcept
Returns the maximum value found so far.
Definition set_maximum_arrangements.hpp:90
const graphs::free_tree & m_t
The tree for which the arrangements are stored.
Definition set_maximum_arrangements.hpp:246
std::vector< uint64_t > m_amount
Multiplicities of each representative.
Definition set_maximum_arrangements.hpp:257
std::vector< linear_arrangement > m_representatives
List of representative arrangements.
Definition set_maximum_arrangements.hpp:251
void init() noexcept
Initialize the object.
Definition set_maximum_arrangements.hpp:83
~set_maximum_arrangements() noexcept
Destructor.
Definition set_maximum_arrangements.hpp:80
std::size_t get_num_representatives() const noexcept
Returns the number of representatives.
Definition set_maximum_arrangements.hpp:94
uint64_t m_max_value
Maximum value found.
Definition set_maximum_arrangements.hpp:249
std::vector< linear_arrangement > && retrieve_all_representatives() noexcept
Returns the set of representatives.
Definition set_maximum_arrangements.hpp:98
void add(const uint64_t value, const linear_arrangement &arr) noexcept
Adds a new arrangement to this class.
Definition set_maximum_arrangements.hpp:143
std::vector< level_signature_per_position > m_mirrored_level_signatures
List of mirrored level signatures per representatives.
Definition set_maximum_arrangements.hpp:253
set_maximum_arrangements(const graphs::free_tree &t) noexcept
Constructor bound to a free tree.
Definition set_maximum_arrangements.hpp:77
A class that implements level signatures of an array.
Definition level_signature.hpp:90
Free tree graph class.
Definition free_tree.hpp:60
Linear arrangement of vertices.
Definition linear_arrangement.hpp:103
level_signature_type
Types of level signature.
Definition level_signature.hpp:58
@ per_position
Given per position.
void calculate_level_signature(const graph_t &g, const linear_arrangement &arr, level_signature< t > &L) noexcept
Calculates the level signature of an arrangement of a graph.
Definition level_signature.hpp:308
level_signature_t mirror_level_signature(const level_signature_t &L) noexcept
Mirrors a level signature.
Definition level_signature.hpp:376
Main namespace of the library.
Definition basic_types.hpp:48