Skip to contents

Package website: release | development

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++.