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