R/RcppExports.R

In vrunge/M2algorithmique: Example of an Rcpp package for M2 Data Science students

# Generated by using Rcpp::compileAttributes() -> do not edit by hand
# Generator token: 10BE3573-1514-4C36-9D1C-5A225CD40393

#' TSP Naive Algorithm (C++ Implementation)
#'
#' @description
#' This function implements a naive heuristic approach for solving the \bold{Traveling Salesman Problem (TSP)} in C++ and is exported to R using Rcpp. 
#' The algorithm uses a simple insertion method to construct a tour by adding cities one by one, minimizing the distance at each step (greedy strategy).
#'
#' The algorithm starts from a specified city and iteratively adds the nearest non-visited city to the tour, updating the tour until all cities are visited. 
#' In \code{"all"} mode, the best tour is selected by testing all possible starting cities and computing the total distance for each tour.
#'
#' @param data A numeric matrix or data frame where each row represents a city and each column represents the coordinates of that city (e.g., x and y coordinates in 2D space).
#' @param type A character string specifying how the starting city is chosen. Options include:
#'  \itemize{
#'   \item \code{"one"} (default): Randomly selects a single starting city.
#'   \item \code{"all"}: Tests all cities as possible starting points and selects the best tour.
#' }
#'
#' @return A numeric vector representing the order of cities in the shortest found tour. The vector is assigned the class "TSP".
#'
#' @details
#' The algorithm is a heuristic approach and does not guarantee the global optimal solution, but aims to find a good solution in a reasonable amount of time.
#'  \itemize{
#'   \item \bold{Time Complexity:} O(n²), where `n` is the number of cities. The algorithm computes the pairwise distances for each pair of cities.
#'   \item \bold{Space Complexity:} O(n²) due to the storage of the distance matrix.
#' }
#' The result is a tour with the shortest found distance, based on the starting point(s) and insertion method.
#'
#' @examples
#' n <- 40
#' villes <- matrix(runif(2*n), n, 2)
#' TSP_naif_Rcpp(villes, type = "one")
#' @export
TSP_naif_Rcpp <- function(data, type = "one") {
    .Call(`_M2algorithmique_TSP_naif_Rcpp`, data, type)
}

#' TSP Cheapest Insertion Algorithm (C++ Implementation)
#'
#' @description
#' This function implements the \bold{Cheapest Insertion} heuristic approach for solving the \bold{Traveling Salesman Problem (TSP)} in C++ and is exported to R using Rcpp. 
#' The algorithm builds the tour by inserting cities into the existing tour in the position that minimizes the increase in tour length.
#'
#' The algorithm starts from a specified city and iteratively inserts cities one by one, choosing the insertion position that results in the cheapest (minimum) increase in the total distance at each step. 
#' In \code{"all"} mode, the best tour is selected by testing all possible starting cities and computing the total distance for each tour.
#'
#' @param data A numeric matrix or data frame where each row represents a city and each column represents the coordinates of that city (e.g., x and y coordinates in 2D space).
#' @param type A character string specifying how the starting city is chosen. Options include:
#'  \itemize{
#'   \item \code{"one"} (default): Randomly selects a single starting city.
#'   \item \code{"all"}: Tests all cities as possible starting points and selects the best tour.
#' }
#'
#' @return A numeric vector representing the order of cities in the shortest found tour. The vector is assigned the class "TSP".
#'
#' @details
#' The algorithm is a heuristic approach and does not guarantee the global optimal solution, but aims to find a good solution in a reasonable amount of time.
#'  \itemize{
#'   \item \bold{Time Complexity:} O(n³), where `n` is the number of cities. The algorithm computes the best insertion for each city and tries every possible insertion position.
#'   \item \bold{Space Complexity:} O(n²) due to the storage of the distance matrix.
#' }
#' The result is a tour with the shortest found distance, based on the starting point(s) and insertion method.
#'
#' @examples
#' n <- 40
#' villes <- matrix(runif(2*n), n, 2)
#' TSP_cheapest_Rcpp(villes, type = "one")
#' @export
TSP_cheapest_Rcpp <- function(data, type = "one") {
    .Call(`_M2algorithmique_TSP_cheapest_Rcpp`, data, type)
}

#' TSP Nearest Insertion Algorithm (C++ Implementation)
#'
#' @description
#' This function implements the **Nearest Insertion** heuristic approach for solving the \bold{Traveling Salesman Problem (TSP)} in C++ and is exported to R using Rcpp. 
#' The algorithm builds the tour by inserting cities into the existing tour by selecting the nearest city to any city already in the tour.
#'
#' The algorithm starts from a specified city and iteratively inserts cities one by one, choosing the nearest city to any city already in the tour. 
#' In "all" mode, the best tour is selected by testing all possible starting cities and computing the total distance for each tour.
#'
#' @param data A numeric matrix or data frame where each row represents a city and each column represents the coordinates of that city (e.g., x and y coordinates in 2D space).
#' @param type A character string specifying how the starting city is chosen. Options include:
#'  \itemize{
#'   \item \code{"one"} (default): Randomly selects a single starting city.
#'   \item \code{"all"}: Tests all cities as possible starting points and selects the best tour.
#' }
#'
#' @return A numeric vector representing the order of cities in the shortest found tour. The vector is assigned the class "TSP".
#'
#' @details
#' The algorithm is a heuristic approach and does not guarantee the global optimal solution, but aims to find a good solution in a reasonable amount of time.
#'  \itemize{
#'   \item \bold{Time Complexity:} O(n³), where `n` is the number of cities. The algorithm computes the best insertion for each city and tries every possible insertion position.
#'   \item \bold{Space Complexity:} O(n²) due to the storage of the distance matrix.
#' }
#' The result is a tour with the shortest found distance, based on the starting point(s) and insertion method.
#'
#' @examples
#' n <- 40
#' villes <- matrix(runif(2*n), n, 2)
#' TSP_nearest_Rcpp(villes, type = "one")
#' @export
TSP_nearest_Rcpp <- function(data, type = "one") {
    .Call(`_M2algorithmique_TSP_nearest_Rcpp`, data, type)
}

compute_distances <- function(data) {
    .Call(`_M2algorithmique_compute_distances`, data)
}

#' Insertion Sort Algorithm (C++ Implementation)
#'
#' @description
#' This function implements the \bold{Insertion Sort} algorithm in C++ and is exported to R using Rcpp. 
#' Insertion Sort is a simple sorting algorithm that builds the sorted sequence one element at a time 
#' by inserting each new element into its correct position within the sorted part of the vector.
#'
#' The algorithm works by iterating through the input vector and shifting larger elements to the right 
#' before inserting the current element (key) into its proper position.
#'
#' @param v A numeric vector containing unsorted elements.
#'
#' @return A numeric vector of the same length as `v`, sorted in ascending order.
#'
#' @details
#'  \itemize{
#'   \item \bold{Time Complexity:} O(n²) in the worst and average cases, O(n) in the best case (already sorted data).
#'   \item \bold{Space Complexity:} O(1) (in-place sorting, no additional memory used).
#'   \item \bold{Stable Sorting Algorithm:} Maintains the relative order of equal elements.
#' }
#' @examples
#' insertion_sort_Rcpp(rnorm(100))
#' insertion_sort_Rcpp(sample(100))
#'
#' @export
insertion_sort_Rcpp <- function(v) {
    .Call(`_M2algorithmique_insertion_sort_Rcpp`, v)
}

#' Maintains the heap property by sifting down an element
#'
#' @description
#' This function ensures the \bold{max-heap property} in a given numeric vector. 
#' It is used internally by heap sort to reorganize the vector into a valid max-heap.
#'
#' @param heap A numeric vector representing a heap.
#' @param i The index of the current element to heapify (1-based indexing).
#' @param n The number of elements in the heap.
#' @return The modified heap with the max-heap property restored.
#' @note This function modifies the input vector in-place.
#'
#' @keywords internal
NULL

#' Heap Sort Algorithm (C++ Implementation)
#'
#' @description
#' This function implements \bold{Heap Sort}, an efficient sorting algorithm that 
#' first builds a max-heap and then repeatedly extracts the maximum element to 
#' produce a sorted sequence.
#'
#' The algorithm consists of two main steps:
#' \enumerate{
#'   \item \bold{Heap Construction:} The input vector is reorganized into a max-heap.
#'   \item \bold{Sorting:} The largest element (root) is swapped with the last element, 
#'     reducing the heap size and reapplying heapify.
#' }
#'
#' @param v A numeric vector containing unsorted elements.
#' @return A numeric vector sorted in ascending order.
#'
#' @details
#' \itemize{
#'   \item \bold{Time Complexity:}
#'     \itemize{
#'       \item Building the heap: O(n)
#'       \item Extracting elements: O(n log n)
#'       \item Overall: O(n log n)
#'     }
#'   \item \bold{Space Complexity:} O(1) (in-place sorting).
#'   \item \bold{Unstable Sort:} The relative order of equal elements may change.
#' }
#' @examples
#' heap_sort_Rcpp(rnorm(100))
#' heap_sort_Rcpp(sample(100))
#'
#' @export
heap_sort_Rcpp <- function(v) {
    .Call(`_M2algorithmique_heap_sort_Rcpp`, v)
}