DMax_utils.hpp

/*********************************************************************
 *
 * Linear Arrangement Library - A library that implements a collection
 * algorithms for linear arrangments of graphs.
 *
 * Copyright (C) 2019 - 2023
 *
 * This file is part of Linear Arrangement Library. The full code is available
 * at:
 *      https://github.com/LAL-project/linear-arrangement-library.git
 *
 * Linear Arrangement Library is free software: you can redistribute it
 * and/or modify it under the terms of the GNU Affero General Public License
 * as published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * Linear Arrangement Library is distributed in the hope that it will be
 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with Linear Arrangement Library.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Contact:
 *
 *     Lluís Alemany Puig (lalemany@cs.upc.edu)
 *         LARCA (Laboratory for Relational Algorithmics, Complexity and Learning)
 *         CQL (Complexity and Quantitative Linguistics Lab)
 *         Jordi Girona St 1-3, Campus Nord UPC, 08034 Barcelona.   CATALONIA, SPAIN
 *         Webpage: https://cqllab.upc.edu/people/lalemany/
 *
 *     Juan Luis Esteban (esteban@cs.upc.edu)
 *         LOGPROG: Logics and Programming Research Group
 *         Office 110, Omega building
 *         Jordi Girona St 1-3, Campus Nord UPC, 08034 Barcelona.   CATALONIA, SPAIN
 *         Webpage: https://www.cs.upc.edu/~esteban/
 *
 *     Ramon Ferrer i Cancho (rferrericancho@cs.upc.edu)
 *         LARCA (Laboratory for Relational Algorithmics, Complexity and Learning)
 *         CQL (Complexity and Quantitative Linguistics Lab)
 *         Office S124, Omega building
 *         Jordi Girona St 1-3, Campus Nord UPC, 08034 Barcelona.   CATALONIA, SPAIN
 *         Webpage: https://cqllab.upc.edu/people/rferrericancho/
 *
 ********************************************************************/
 
#pragma once
 
// C++ includes
#if defined DEBUG
#include <cassert>
#endif
#include <vector>
 
// lal includes
#include <lal/linear_arrangement.hpp>
#include <lal/graphs/rooted_tree.hpp>
#include <lal/detail/data_array.hpp>
#include <lal/iterators/E_iterator.hpp>
#include <lal/detail/graphs/size_subtrees.hpp>
#include <lal/detail/sorting/counting_sort.hpp>
#include <lal/detail/properties/tree_centroid.hpp>
#include <lal/detail/macros/basic_convert.hpp>
#include <lal/detail/linarr/Dopt_utils.hpp>
 
namespace lal {
namespace detail {
 
namespace DMax_utils {
 
using namespace Dopt_utils;
 
/* ************************************************************************** */
/* ---------------------- INTERVAL-based methods ---------------------------- */
 
/* The following namespace contains functions for the interval-based algorithms
 * to calculate the planar and projective maximum sum of edge lengths.
 */
 
template <place r_place, bool make_arrangement>
uint64_t arrange
(
    const std::vector<std::vector<node_size>>& L,
    const node r,
    position ini, position fin,
    linear_arrangement& arr
)
noexcept
{
#if defined DEBUG
    assert(ini <= fin);
#endif
 
    if constexpr (make_arrangement) {
        if constexpr (r_place == PLACE_LEFT_OF) {
            arr.assign(r, ini);
        }
        else {
            // It is clear that for the case 'r_place == PLACE_RIGHT_OF', we
            // need the code below. For the case 'r_place == PLACE_NONE_OF', the
            // code below is an arbitrary choice, but it is in accordance with
            // the steps of this algorithm.
            arr.assign(r, fin);
        }
    }
 
    // sizes of the subtrees
    const auto& children = L[r];
 
    // accumulated size of the subtrees
    uint64_t acc_size = 0;
 
    // sum of the optimal D for every subtree +
    // the length of the edge from 'r' to its parent (if any)
    uint64_t D = 0;
 
    // Auxiliary variables that contain the next
    // starting position and the next ending position.
    // Initialized so the compiler does not cry
    position next_ini = 0, next_fin = 0;
 
    constexpr place next_place =
        (r_place == PLACE_LEFT_OF ? PLACE_RIGHT_OF : PLACE_LEFT_OF);
 
    // while placing the children, calculate the
    // length of the edge from 'r' to vertex 'vi'
    for (const auto& [vi, ni] : children) {
 
        if constexpr (make_arrangement) {
            if constexpr (r_place == PLACE_LEFT_OF) {
                next_ini = ini + acc_size + 1;
                next_fin = next_ini + ni - 1;
            }
            else {
                // It is clear that for the case 'r_place == PLACE_RIGHT_OF', we
                // need the code below. For the case 'r_place == PLACE_NONE_OF', the
                // code below is an arbitrary choice, but it is in accordance with
                // the steps of this algorithm.
                next_fin = fin - acc_size - 1;
                next_ini = next_fin - ni + 1;
            }
        }
 
        // recursive call: make the interval of 'vi'
        D += arrange<next_place, make_arrangement>(L, vi, next_ini, next_fin, arr);
 
        D += 1 + acc_size;
        acc_size += ni;
    }
 
    if constexpr (r_place != PLACE_NONE_OF) {
        // accumulate this subtree's anchor
        D += acc_size;
    }
    return D;
}
 
inline uint64_t arrange_projective
(
    uint64_t n, const std::vector<std::vector<node_size>>& L,
    node r, linear_arrangement& arr
)
noexcept
{
    return arrange<PLACE_NONE_OF, true>(L, r, 0, n-1, arr);
}
 
inline uint64_t arrange_projective
(uint64_t n, const std::vector<std::vector<node_size>>& L, node r)
noexcept
{
    linear_arrangement arr;
    return arrange<PLACE_NONE_OF, false>(L, r, 0, n-1, arr);
}
 
} // -- namespcae DMax_utils
} // -- namespace detail
} // -- namespace lal