search

josherrickson / rlemon

rlemon - R interface to C++ LEMON graph library
http://errickson.net/rlemon/
8 stars 3 forks source link
r r-package rstats

readme

rlemon: R interface to LEMON solver

Package website: release | development

CRAN_Status_Badge R-CMD-check

rlemon provides convenient access to the LEMON C++ graph library. Built with the most recent version of LEMON (1.3.1), it provides an R interface to algorithms to solve the following problems:

Problem Algorithm(s)
Graph Search breadth-first search (BFS), depth-first search (DFS), Maximum Cardinality Search
Shortest Path Bellman-Ford, Dijkstra, Suurballe
Minimum Spanning Tree Kruskal, Minimum Cost Arborescence
MaxFlow Push-relabel algorithm for the network circulation, Edmonds-Karp, Preflow
MinCostFlow Primal Network Simplex, Capacity Scaling, Cost Scaling, Cycle Canceling
Minimum Cut Hao-Orlin, Gomory-Hu, Nagamochi-Ibaraki
minMeanCycle Hartmann-Orlin, Howard's policy iteration, Karp's
Matching Edmond's blossom shrinking algorithms, Push-relabel , Augmenting path
Connectivity Algorithms Topological Sort, Check for Bipartite, loops, simple, or eulerian graphs, check for parallel edges
PlanarEmbedding and Drawing Planar Embedding, Schnyder's planar drawing, Planar Coloring
Traveling Salesperson Christosfides, Greedy, Insertion heuristic, Nearest Neighbor, 2-opt
Approximation Algorithms Grosso, Locatelli, and Pullan

1-indexing vs 0-indexing

The LEMON C++ library uses 0-indexing, as is common in C++, meaning a graph of 5 nodes will be labeled 0 through 4. R almost exclusively uses 1-indexing, meaning the same graph of 5 nodes will be labeled 1 through 5.

For consistency in R, all function in R expect 1-indexing, and convert to 0-indexing before passing to C++.

Rebuilding website

Run make build_site (or, directly, devtools::build_site(quiet = FALSE)) to build the site. Assuming the package is currently on a development version, this will build the dev site to docs/dev. To build the release site, checkout the most recent tagged release, e.g. git checkout v0.2.1. Build the site in that commit, which should populate docs/. Checkout back to main, and both pkgdown sites should be build.