degrees.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/
 *
 *     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
 
// lal includes
#include <lal/numeric/rational.hpp>
#include <lal/graphs/undirected_graph.hpp>
#include <lal/graphs/directed_graph.hpp>
#include <lal/graphs/free_tree.hpp>
#include <lal/graphs/rooted_tree.hpp>
 
namespace lal {
namespace properties {
 
/* -------------------------------------------------------------------------- */
 
#ifndef SWIG
 
template <class graph_t, class return_type>
inline
return_type sum_powers_degrees
(const graph_t& g, uint64_t p, uint64_t (graph_t::*degree_function)(node) const noexcept)
noexcept
{
    static_assert(
        std::is_same_v<return_type, uint64_t> ||
        std::is_same_v<return_type, numeric::integer>
    );
 
    // sum of powers
    return_type S(0);
    // variable used to calculate powers
    return_type du(0);
 
    for (node u = 0; u < g.get_num_nodes(); ++u) {
        const uint64_t deg = (g.*degree_function)(u);
        // calculate the power of the degree 'deg'
        if constexpr (std::is_same_v<return_type, numeric::integer>) {
            du.set_number(deg);
            du.powt(p);
        }
        else {
            du = 1;
            for (uint64_t i = 0; i < p; ++i) {
                du *= deg;
            }
        }
        // accumulate power
        S += du;
    }
    return S;
}
 
#endif
 
inline
numeric::integer sum_powers_degrees_integer
(const graphs::undirected_graph& g, uint64_t p) noexcept
{
    return
    sum_powers_degrees<graphs::undirected_graph, numeric::integer>
    (g, p, &graphs::undirected_graph::get_degree);
}
inline
uint64_t sum_powers_degrees
(const graphs::undirected_graph& g, uint64_t p) noexcept
{
    return
    sum_powers_degrees<graphs::undirected_graph, uint64_t>
    (g, p, &graphs::undirected_graph::get_degree);
}
 
inline
numeric::integer sum_powers_degrees_integer
(const graphs::directed_graph& g, uint64_t p) noexcept
{
    return
    sum_powers_degrees<graphs::directed_graph, numeric::integer>
    (g, p, &graphs::directed_graph::get_degree);
}
inline
uint64_t sum_powers_degrees
(const graphs::directed_graph& g, uint64_t p) noexcept
{
    return
    sum_powers_degrees<graphs::directed_graph, uint64_t>
    (g, p, &graphs::directed_graph::get_degree);
}
 
inline
numeric::integer sum_powers_in_degrees_integer
(const graphs::directed_graph& g, uint64_t p) noexcept
{
    return
    sum_powers_degrees<graphs::directed_graph, numeric::integer>
    (g, p, &graphs::directed_graph::get_in_degree);
}
inline
uint64_t sum_powers_in_degrees
(const graphs::directed_graph& g, uint64_t p) noexcept
{
    return
    sum_powers_degrees<graphs::directed_graph, uint64_t>
    (g, p, &graphs::directed_graph::get_in_degree);
}
 
inline
numeric::integer sum_powers_in_degrees_integer
(const graphs::rooted_tree& t, uint64_t p)
noexcept
{
    (void(p));
 
#if defined DEBUG
    assert(t.is_rooted_tree());
#endif
    return t.get_num_edges();
}
inline
uint64_t sum_powers_in_degrees(const graphs::rooted_tree& t, uint64_t p) noexcept
{
    (void(p));
 
#if defined DEBUG
    assert(t.is_rooted_tree());
#endif
    return t.get_num_edges();
}
 
inline
numeric::integer sum_powers_out_degrees_integer
(const graphs::directed_graph& g, uint64_t p) noexcept
{
    return
    sum_powers_degrees<graphs::directed_graph, numeric::integer>
    (g, p, &graphs::directed_graph::get_out_degree);
}
inline
uint64_t sum_powers_out_degrees
(const graphs::directed_graph& g, uint64_t p) noexcept
{
    return
    sum_powers_degrees<graphs::directed_graph, uint64_t>
    (g, p, &graphs::directed_graph::get_out_degree);
}
 
/* -------------------------------------------------------------------------- */
 
#ifndef SWIG
 
template <class graph_t, class return_type>
inline
return_type moment_degree
(const graph_t& g, uint64_t p, uint64_t (graph_t::*degree_function)(node) const noexcept)
noexcept
{
    static_assert(
        std::is_floating_point_v<return_type> ||
        std::is_same_v<return_type, numeric::rational>
    );
 
    if constexpr (std::is_floating_point_v<return_type>) {
        const uint64_t S =
            sum_powers_degrees<graph_t,uint64_t>(g,p,degree_function);
        return static_cast<return_type>(S)/static_cast<return_type>(g.get_num_nodes());
    }
    else {
        const numeric::integer S =
            sum_powers_degrees<graph_t,numeric::integer>(g,p,degree_function);
        return numeric::rational(S,g.get_num_nodes());
    }
}
 
#endif
 
inline
numeric::rational moment_degree_rational
(const graphs::undirected_graph& g, uint64_t p) noexcept
{
    return
    moment_degree<graphs::undirected_graph, numeric::rational>
    (g, p, &graphs::undirected_graph::get_degree);
}
inline
double moment_degree(const graphs::undirected_graph& g, uint64_t p) noexcept
{
    return
    moment_degree<graphs::undirected_graph, double>
    (g, p, &graphs::undirected_graph::get_degree);
}
 
inline
numeric::rational moment_degree_rational
(const graphs::directed_graph& g, uint64_t p) noexcept
{
    return
    moment_degree<graphs::directed_graph, numeric::rational>
    (g, p, &graphs::directed_graph::get_degree);
}
inline
double moment_degree(const graphs::directed_graph& g, uint64_t p) noexcept
{
    return
    moment_degree<graphs::directed_graph, double>
    (g, p, &graphs::directed_graph::get_degree);
}
 
inline
numeric::rational moment_in_degree_rational
(const graphs::directed_graph& g, uint64_t p) noexcept
{
    return
    moment_degree<graphs::directed_graph, numeric::rational>
    (g, p, &graphs::directed_graph::get_in_degree);
}
inline
double moment_in_degree(const graphs::directed_graph& g, uint64_t p) noexcept
{
    return
    moment_degree<graphs::directed_graph, double>
    (g, p, &graphs::directed_graph::get_in_degree);
}
 
inline
numeric::rational moment_in_degree_rational(const graphs::rooted_tree& t, uint64_t p)
noexcept
{
    (void(p));
 
#if defined DEBUG
    assert(t.is_rooted_tree());
#endif
    const auto n = t.get_num_nodes();
    return numeric::rational(n - 1, n);
}
inline
double moment_in_degree(const graphs::rooted_tree& t, uint64_t p)
noexcept
{
    (void(p));
 
#if defined DEBUG
    assert(t.is_rooted_tree());
#endif
    const auto n = t.get_num_nodes();
    return static_cast<double>(n - 1)/static_cast<double>(n);
}
 
inline
numeric::rational moment_out_degree_rational
(const graphs::directed_graph& g, uint64_t p) noexcept
{
    return
    moment_degree<graphs::directed_graph, numeric::rational>
    (g, p, &graphs::directed_graph::get_out_degree);
}
inline
double moment_out_degree(const graphs::directed_graph& g, uint64_t p) noexcept
{
    return
    moment_degree<graphs::directed_graph, double>
    (g, p, &graphs::directed_graph::get_out_degree);
}
 
 
/* -------------------------------------------------------------------------- */
 
 
inline
numeric::rational hubiness_rational(const graphs::free_tree& t) noexcept
{
    const uint64_t n = t.get_num_nodes();
 
    // for n <= 3, <k^2>_star = <k^2>_linear
    // which means that hubiness is not defined:
    // division by 0.
#if defined DEBUG
    assert(t.is_tree());
    assert(n > 3);
#endif
 
    const numeric::rational k2_tree = moment_degree_rational(t, 2);
    const numeric::rational k2_linear = numeric::rational(4*n - 6, n);
    const numeric::rational k2_star = numeric::rational(n - 1);
    return (k2_tree - k2_linear)/(k2_star - k2_linear);
}
 
inline
numeric::rational hubiness_rational(const graphs::rooted_tree& t) noexcept
{
    const uint64_t n = t.get_num_nodes();
 
    // for n <= 3, <k^2>_star = <k^2>_linear
    // which means that hubiness is not defined:
    // division by 0.
#if defined DEBUG
    assert(t.is_rooted_tree());
    assert(n > 3);
#endif
 
    const numeric::rational k2_tree = moment_degree_rational(t, 2);
    const numeric::rational k2_linear = numeric::rational(4*n - 6, n);
    const numeric::rational k2_star = numeric::rational(n - 1);
    return (k2_tree - k2_linear)/(k2_star - k2_linear);
}
 
inline
double hubiness(const graphs::free_tree& t) noexcept
{
    const uint64_t n = t.get_num_nodes();
 
    // for n <= 3, <k^2>_star = <k^2>_linear
    // which means that hubiness is not defined:
    // division by 0.
#if defined DEBUG
    assert(t.is_tree());
    assert(n > 3);
#endif
 
    const double k2_tree = moment_degree(t, 2);
    const double k2_linear = static_cast<double>(4*n - 6)/static_cast<double>(n);
    const double k2_star = static_cast<double>(n - 1);
    return (k2_tree - k2_linear)/(k2_star - k2_linear);
}
 
inline
double hubiness(const graphs::rooted_tree& t) noexcept
{
    const uint64_t n = t.get_num_nodes();
 
    // for n <= 3, <k^2>_star = <k^2>_linear
    // which means that hubiness is not defined:
    // division by 0.
#if defined DEBUG
    assert(t.is_rooted_tree());
    assert(n > 3);
#endif
 
    const double k2_tree = moment_degree(t, 2);
    const double k2_linear = static_cast<double>(4*n - 6)/static_cast<double>(n);
    const double k2_star = static_cast<double>(n - 1);
    return (k2_tree - k2_linear)/(k2_star - k2_linear);
}
 
} // -- namespace properties
} // -- namespace lal