Package: gor 1.0

Cesar Asensio

gor: Algorithms for the Subject Graphs and Network Optimization

Informal implementation of some algorithms from Graph Theory and Combinatorial Optimization which arise in the subject "Graphs and Network Optimization" from first course of the EUPLA (Escuela Universitaria Politecnica de La Almunia) degree of Data Engineering in Industrial Processes. References used are: Cook et al (1998, ISBN:0-471-55894-X), Korte, Vygen (2018) <doi:10.1007/978-3-662-56039-6>, Hromkovic (2004) <doi:10.1007/978-3-662-05269-3>, Hartmann, Weigt (2005, ISBN:978-3-527-40473-5).

Authors:Cesar Asensio [aut, cre]

gor_1.0.tar.gz
gor_1.0.tar.gz(r-4.5-noble)gor_1.0.tar.gz(r-4.4-noble)
gor_1.0.tgz(r-4.4-emscripten)gor_1.0.tgz(r-4.3-emscripten)
gor.pdf |gor.html✨
gor/json (API)

# Install 'gor' in R:
install.packages('gor', repos = c('https://cran.r-universe.dev', 'https://cloud.r-project.org'))

Peer review:

This package does not link to any Github/Gitlab/R-forge repository. No issue tracker or development information is available.

1.00 score 3 scripts 137 downloads 50 exports 11 dependencies

Last updated 2 years agofrom:95dc0d651e. Checks:OK: 1 NOTE: 1. Indexed: yes.

TargetResultDate
Doc / VignettesOKOct 29 2024
R-4.5-linuxNOTEOct 29 2024

Exports:apply_incidence_mapbfs_treebuild_cover_approxbuild_cover_greedybuild_cover_randombuild_cut_greedybuild_cut_randombuild_tour_2treebuild_tour_greedybuild_tour_nnbuild_tour_nn_bestcolor_graph_greedycompute_cut_weightcompute_distance_matrixcompute_gain_transpcompute_lower_bound_1treecompute_lower_bound_HKcompute_p_distancecompute_path_distancecompute_tour_distancecrossover_sequencescrossover_toursdfs_treedijkfind_cover_BBfind_eulerfind_tour_BBgauge_tourgenerate_fundamental_cyclesimprove_cover_flipimprove_cut_flipimprove_tour_2optimprove_tour_3optimprove_tour_LinKeris_covermutate_binary_sequenceneigh_indexnext_indexperturb_tour_4excplot_coverplot_cutplot_toursearch_cover_antssearch_cover_randomsearch_cut_geneticsearch_tour_antssearch_tour_chain2optsearch_tour_geneticshave_cyclesum_g

Dependencies:clicpp11glueigraphlatticelifecyclemagrittrMatrixpkgconfigrlangvctrs

Readme and manuals

Help Manual

Help pageTopics
Apply incidence map of a graph to an edge vectorapply_incidence_map
Breadth-first search treebfs_tree
2-approximation algorithm for vertex coverbuild_cover_approx
Greedy algorithm for vertex cover in a graphbuild_cover_greedy
Random vertex coversbuild_cover_random
Greedy algorithm aimed to build a large weight cut in a graphbuild_cut_greedy
Random cut generation on a graphbuild_cut_random
Double-tree heuristic for TSPbuild_tour_2tree
Building a tour for a TSP using the greedy heuristicbuild_tour_greedy
Building a tour for a TSP using the nearest neighbor heuristicbuild_tour_nn
Build a tour for a TSP using the best nearest neighbor heuristicbuild_tour_nn_best
Greedy coloring of a graphcolor_graph_greedy
Compute cut weight and sizecompute_cut_weight
p-distance matrix computationcompute_distance_matrix
Distance gain when transposing two cities in a tourcompute_gain_transp
Computing the 1-tree lower bound for a TSP instancecompute_lower_bound_1tree
Held-Karp lower bound estimatecompute_lower_bound_HK
Distance-p between two-dimensional pointscompute_p_distance
Compute the distance of a TSP pathcompute_path_distance
Compute the distance of a TSP tourcompute_tour_distance
Crossover of sequencescrossover_sequences
Crossover operation used by the TSP genetic algorithmcrossover_tours
Depth-first search treedfs_tree
Dijkstra' algorithm for shortest pathsdijk
Branch-and-Bound algorithm for the Vertex-Cover problemfind_cover_BB
Constructing an Eulerian Cyclefind_euler
Branch-and-Bound algorithm for the TSPfind_tour_BB
Gauging a tourgauge_tour
Generate fundamental cycles in a connected graphgenerate_fundamental_cycles
Graphs and Network Optimization algorithmsgor
Improving a cover with local searchimprove_cover_flip
Improving a cut with local searchimprove_cut_flip
Tour improving for a TSP using the 2-opt heuristicimprove_tour_2opt
Tour improving for a TSP using the 3-opt heuristicimprove_tour_3opt
Tour improving for a TSP using a poor version of the Lin-Kernighan heuristicimprove_tour_LinKer
Check vertex coveris_cover
Binary sequence mutationmutate_binary_sequence
Previous, current, and next positions of a given index in a cycle.neigh_index
Next position to i in a cyclenext_index
Random 4-exchange transformationperturb_tour_4exc
Vertex cover plottingplot_cover
Cut plottingplot_cut
TSP tour simple plottingplot_tour
Ant colony optimization algorithm for Vertex-Coversearch_cover_ants
Random vertex coverssearch_cover_random
Genetic Algorithm for Max-Cutsearch_cut_genetic
Ant colony optimization algorithm for the TSPsearch_tour_ants
Chained 2-opt search with multiple, random starting tourssearch_tour_chain2opt
Genetic Algorithm for the TSPsearch_tour_genetic
Shaving a hairy cycleshave_cycle
Sum of the higher terms of a listsum_g