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