BnB.hpp

/*********************************************************************
 *
 * Linear Arrangement Library - A library that implements a collection
 * algorithms for linear arrangments of graphs.
 *
 * Copyright (C) 2019 - 2024
 *
 * 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 (lluis.alemany.puig@upc.edu)
 *         LQMC (Quantitative, Mathematical, and Computational Linguisitcs)
 *         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)
 *         LQMC (Quantitative, Mathematical, and Computational Linguisitcs)
 *         CQL (Complexity and Quantitative Linguistics Lab)
 *         Office 220, Omega building
 *         Jordi Girona St 1-3, Campus Nord UPC, 08034 Barcelona.   CATALONIA, SPAIN
 *         Webpage: https://cqllab.upc.edu/people/rferrericancho/
 *
 ********************************************************************/
 
#pragma once
 
// lal includes
#include <lal/basic_types.hpp>
#include <lal/graphs/free_tree.hpp>
#include <lal/graphs/rooted_tree.hpp>
#include <lal/properties/branchless_path.hpp>
#include <lal/properties/bipartite_graph_coloring.hpp>
#include <lal/detail/array.hpp>
#include <lal/detail/set_array.hpp>
#include <lal/detail/macros/basic_convert.hpp>
#include <lal/detail/sorting/counting_sort.hpp>
 
#include <lal/detail/linarr/D/DMax/unconstrained/branch_and_bound/AEF/set_maximum_arrangements.hpp>
#include <lal/detail/linarr/D/DMax/unconstrained/branch_and_bound/AEF/reason_discard.hpp>
#include <lal/detail/linarr/D/DMax/unconstrained/branch_and_bound/AEF/next_action.hpp>
#include <lal/detail/linarr/D/DMax/unconstrained/branch_and_bound/AEF/level_value_propagation_origin.hpp>
#include <lal/detail/linarr/D/DMax/unconstrained/branch_and_bound/AEF/propagation_result.hpp>
 
#if defined __LAL_DEBUG_DMax_Unc_BnB
#if !defined DEBUG
#error("'__LAL_DEBUG_DMax_Unc_BnB' must be defined along with 'DEBUG'")
#endif
#endif
 
namespace lal {
namespace detail {
namespace DMax {
namespace unconstrained {
 
class AEF_BnB {
public:
    static constexpr char VERTEX_ASSIGNED = 1;
    static constexpr char VERTEX_UNASSIGNED = 0;
 
    static constexpr bool debug_BnB =
#if defined __LAL_DEBUG_DMax_Unc_BnB
    true;
#else
    false;
#endif
 
    typedef std::conditional_t<debug_BnB, bool, void>
    exe_result_type;
 
public:
    enum process_end_result {
        did_not_reach_end   = 0b00000000,
        reached_end         = 0b00000001,
        found_max           = 0b00000010
    };
 
    [[nodiscard]] constexpr bool did_reach_end(const int at) const noexcept
    { return at & process_end_result::reached_end; }
 
    [[nodiscard]] constexpr bool did_find_max(const int at) const noexcept
    { return at & process_end_result::found_max; }
 
public:
    const graphs::free_tree& m_t;
    graphs::rooted_tree m_rt;
 
    set_maximum_arrangements m_max_arrs;
    linear_arrangement m_arr;
 
public:
    AEF_BnB(
        const graphs::free_tree& t,
        const array<std::vector<node>>& leaves,
        // colors of vertices
        const properties::bipartite_graph_coloring& colors,
        const uint64_t num_verts_blue,
        const uint64_t num_verts_red,
        // paths
        const std::vector<properties::branchless_path>& paths_in_tree,
        const array<std::size_t>& node_to_path_idx,
        const array<std::vector<node>>& incident_antennas,
        // orbits
        const std::vector<std::vector<node>>& orbits,
        const array<std::size_t>& vertex_to_orbit
    )
    noexcept;
    ~AEF_BnB() noexcept = default;
 
    void initialize
    (const std::pair<uint64_t, linear_arrangement>& initial_DMax)
    noexcept;
 
    void exe(node first_node) noexcept;
 
protected:
 
    // -- constraints --
 
    [[nodiscard]] reason_discard check_propagation_node_to_node(
        const node u, const int64_t level_u,
        const node v, const int64_t level_v
    ) const noexcept;
    [[nodiscard]] reason_discard discard_node__degree_2__bridge__level_0
    (const node u)
    const noexcept;
    [[nodiscard]] reason_discard discard_node__degree_2__bridge__level_pm2
    (const node u, const int64_t level_u)
    const noexcept;
    [[nodiscard]] reason_discard discard_node_degree_2
    (const node u, const int64_t level_u)
    const noexcept;
    [[nodiscard]] reason_discard discard_node_degree_3
    (const node u, const int64_t level_u)
    const noexcept;
 
    [[nodiscard]] reason_discard discard_vertex(const node u, const position_t pos)
    const noexcept;
 
    // -- bounds --
 
    [[nodiscard]] uint64_t upper_bound_generic
    (const uint64_t D_p, const uint64_t D_ps_m, const position_t pos) noexcept;
 
    [[nodiscard]] next_action what_to_do_next
    (const uint64_t D_p, const uint64_t D_ps_m, const position_t pos) noexcept;
 
    // -- state manipulation --
 
    void update_state
    (const node u, const position_t pos, uint64_t& D_p, uint64_t& D_ps_m)
    noexcept;
 
    void recover_state(const position_t pos) noexcept;
 
    // -- propagation of constraints -- //
 
    void propagate_LV__antenna__from_hub
    (const node h, const node u) noexcept;
    void propagate_LV__antenna__from_leaf
    (const node u) noexcept;
    void propagate_LV__antenna__from_internal
    (const node u) noexcept;
 
    [[nodiscard]] propagation_result propagate_LV__bridge__check_lowest_can_be_predicted
    (const std::size_t path_idx, const LV_propagation_origin origin)
    noexcept;
 
    void propagate_LV__bridge__from_hub__h2
    (const std::size_t path_idx) noexcept;
    void propagate_LV__bridge__from_hub__h1
    (const std::size_t path_idx) noexcept;
    [[nodiscard]] propagation_result propagate_LV__bridge__from_hub
    (const node h, const std::size_t path_idx) noexcept;
 
    void propagate_LV__bridge__from_lowest__level_0__towards_h2
    (const std::size_t path_idx) noexcept;
    void propagate_LV__bridge__from_lowest__level_0__towards_h1
    (const std::size_t path_idx) noexcept;
    void propagate_LV__bridge__from_lowest__level_0
    (const node u) noexcept;
 
    [[nodiscard]] propagation_result propagate_LV__bridge__from_lowest__level_pm2
    (const node u) noexcept;
 
    [[nodiscard]] propagation_result propagate_LV__bridge__from_internal
    (const node u) noexcept;
 
    [[nodiscard]] propagation_result propagate_constraints
    (const node u) noexcept;
 
    // -- rollback constraints -- //
 
    void roll_back_LV__antenna
    (const node u) noexcept;
 
    void roll_back_LV__bridge__from_hub__h2
    (const std::size_t path_idx) noexcept;
    void roll_back_LV__bridge__from_hub__h1
    (const std::size_t path_idx) noexcept;
    void roll_back_LV__bridge__from_hub
    (const node h, const std::size_t path_idx) noexcept;
 
    void roll_back_LV__bridge__from_lowest__level_0__towards_h2
    (const std::size_t path_idx) noexcept;
    void roll_back_LV__bridge__from_lowest__level_0__towards_h1
    (const std::size_t path_idx) noexcept;
    void roll_back_LV__bridge__from_lowest__level_0
    (const node u) noexcept;
 
    void roll_back_LV__bridge__from_lowest__level_pm2
    (const node u) noexcept;
 
    void roll_back_LV__bridge__from_internal
    (const node u) noexcept;
    void roll_back_constraints
    (const node u) noexcept;
 
    [[nodiscard]] int process_end(const uint64_t D, const position pos) noexcept;
 
    // -- others --
 
    [[nodiscard]] bool is_vertex_assigned(const node u) const noexcept {
        return m_is_node_assigned[u] == VERTEX_ASSIGNED;
    }
 
    [[nodiscard]] bool is_vertex_thistle(const node u) const noexcept {
#if defined DEBUG
        assert(is_vertex_assigned(u));
#endif
        return to_uint64(std::abs(m_node_level[u])) != m_t.get_degree(u);
    }
 
    [[nodiscard]] node leaf_parent(const node u) const noexcept {
#if defined DEBUG
        assert(m_t.get_degree(u) == 1);
#endif
        return m_t.get_neighbors(u)[0];
    }
 
    // -------------------------------------------------------------------------
    // execute Branch and Bound for an independent set of vertices
 
    /* Functions
     *      'exe_independent_set'
     * and
     *      'exe_independent_set_leaves'
     * do not call the 'update_state' functions since the construction of the
     * arrangement is easy, final, and the information updated by the 'update_state'
     * function is not needed anymore. Moreover, each call to 'update_state' requires
     * a subsequent call to 'recover_state'.
     *
     * The value of D passed as parameter, 'D_p' is the sum of the lengths of all
     * the edges whose both endpoints are assigned to the prefix of the arrangement
     * before calling the function.
     */
 
    exe_result_type exe_independent_set
    (const uint64_t D_p, position pos) noexcept;
 
    exe_result_type exe_independent_set_leaves
    (const uint64_t D_p, position pos) noexcept;
 
    // -------------------------------------------------------------------------
    // execute Branch and Bound for any tree
 
    exe_result_type exe
    (const uint64_t D_p, const uint64_t D_ps_m, const position pos)
    noexcept;
 
private:
    // -------------------------------------------------------------------------
    // Tree-related data
 
    const uint64_t m_n_nodes;
    const array<std::vector<node>>& m_leaves;
    const properties::bipartite_graph_coloring& m_vertex_colors;
    const uint64_t m_num_nodes_blue;
    const uint64_t m_num_nodes_red;
    uint64_t m_num_assigned_nodes_blue;
    uint64_t m_num_assigned_nodes_red;
    const std::vector<properties::branchless_path>& m_paths_in_tree;
    const array<std::size_t>& m_node_to_path_idx;
    const array<std::vector<node>>& m_incident_antennas;
    const std::vector<std::vector<node>>& m_orbits;
    const array<std::size_t>& m_node_to_orbit;
 
    // -------------------------------------------------------------------------
    // Data used for upper bounds
 
    array<uint64_t> m_degree_count;
 
    array<uint64_t> m_num_assigned_neighbors;
    array<uint64_t> m_num_unassigned_neighbors;
 
    /* -------------------------- BORDER VERTICES -------------------------- */
    // memory used to sort those vertices with some neighbor assigned.
    // sorted by amount of assigned neighbors
 
    set_array<node> m_border_nodes;
    sorting::countingsort::memory<node> m_sorting_memory;
 
    /* -------------------------- BORDER VERTICES -------------------------- */
 
    // -------------------------------------------------------------------------
    // Algorithm control
 
    struct path_info {
        uint64_t num_thistles;
        uint64_t num_assigned_nodes;
        uint64_t num_assigned_nodes_p2;
        uint64_t num_assigned_nodes_m2;
 
        uint64_t min_pm_two;
        uint64_t max_pm_two;
 
        // number of vertices of level +-2 to assign to the arrangement
        // known after the entire propagation of the path is complete
        // (done only for antennas)
        std::optional<uint64_t> nodes_p2_to_assign;
        std::optional<uint64_t> nodes_m2_to_assign;
    };
    array<path_info> m_path_info;
 
    node m_first_node;
 
    array<char> m_is_node_assigned;
 
    class indexer_edge {
    private:
        std::size_t m_capacity;
 
    public:
        void init(std::size_t cap) noexcept {
            m_capacity = cap;
        }
        [[nodiscard]] std::size_t operator()(const edge& p) const noexcept {
            return p.first + p.second*m_capacity;
        }
    };
 
    set_array<edge, indexer_edge> m_E_p;
    set_array<edge, indexer_edge> m_E_ps;
    set_array<edge, indexer_edge> m_E_s;
 
    array<uint64_t> m_node_left_degree;
    array<uint64_t> m_node_right_degree;
    array<int64_t> m_node_level;
 
    array<uint64_t> m_cut_values;
 
    array<int64_t> m_predicted_LV;
    array<LV_propagation_origin> m_predicted_LV__origin;
 
    [[nodiscard]] bool has_valid_LV_prediction(node u) const noexcept
    { return m_predicted_LV__origin[u] != LV_propagation_origin::none; }
 
    [[nodiscard]] bool is_node_a_trigger_of_LV(node u) const noexcept
    { return m_predicted_LV__origin[u] == LV_propagation_origin::self; }
 
#if defined __LAL_DEBUG_DMax_Unc_BnB
    // -------------------------------------------------------------------------
    // Display of algorithm's data and progress
 
    void output_edge_list() const noexcept;
    void output_arrangement() const noexcept;
    void output_invarr(const position p) const noexcept;
    void output_degree_sequence(const position p) const noexcept;
    void output_left_degree_sequence(const position p) const noexcept;
    void output_right_degree_sequence(const position p) const noexcept;
    void output_level_sequence(const position p) const noexcept;
    void output_cut_signature(const position p) const noexcept;
    void output_num_assigned_neighbors() const noexcept;
    void output_num_unassigned_neighbors() const noexcept;
    void output_border_nodes() const noexcept;
    void output_predicted_level_values() const noexcept;
    void output_path_info() const noexcept;
    void display_all_info
    (const uint64_t D_p, const uint64_t D_ps_m, const position pos)
    noexcept;
 
    // progress of algorithm
    std::string m_tabstr;
    const std::string& tab() const noexcept { return m_tabstr; }
    void push_tab(const std::string& add = "|   ") noexcept { m_tabstr += add; }
    void pop_tab() noexcept { m_tabstr = m_tabstr.substr(0, m_tabstr.length() - 4); }
#endif
};
 
} // -- namespace unconstrained
} // -- namespace DMax
} // -- namespace detail
} // -- namespace lal