lemon-master

下载 开源库
1

链接：https://pan.baidu.com/s/1-mqZwTguhrDXr5D3Eycxsg?pwd=90l2 提取码：90l2

概述
lemon-master 通常指 LEMON (Library for Efficient Modeling and Optimization in Networks) 的主干分支/源码包。它是一个用现代 C++ 模板实现的高性能图与网络优化算法库，侧重组合优化、网络流、匹配、最短路、最小费用流、生成树等领域。

设计理念

  • 以“图概念”与“算法概念”分离：图是数据结构，算法对图的抽象接口编程。
  • 使用轻量级可替换图结构（ListGraph / SmartGraph / StaticGraph 等）满足不同性能/内存需求。
  • 通过适配器 (Adaptor) 和投影 (Map) 组合修改视图而不复制底层结构（例如过滤节点、边权映射、子图视图）。
  • 强调可扩展与可复用：算法接口接受“图 + 权重/容量 Map”而非硬编码字段。

核心数据结构

  • ListGraph：动态增删节点/边，适合构建期变化。
  • SmartGraph：更紧凑存储，但删除操作受限，适合大量查询。
  • StaticGraph：构建后不可修改，构建阶段进行压缩以提升遍历性能。
  • Graph Adaptors：FilterNodes, FilterEdges, SubGraph, Undirector, ResidualGraph 等用于构造视图。
  • Maps：节点/边到值的映射 (ArrayMap, VectorMap, ConstMap)；算法通过模板参数接收权重/容量/成本。

迭代器与“概念”层

  • Node / Edge / Arc / InArcIt / OutArcIt 等迭代器语义统一。
  • 模板算法对“支持这些迭代器的图概念”编程，提升泛化能力。
  • 避免虚函数（静态多态）减少调用开销。

主要算法分类

  1. 最短路径：Dijkstra, Bellman-Ford, BFS, A*（支持可定制启发式）
  2. 最大流 / 最小割：Edmonds-Karp, Dinic, Preflow-Push
  3. 最小费用流：Network Simplex, Cost Scaling, Capacity Scaling
  4. 匹配：最大匹配（一般图/二分图）、最优匹配（匈牙利/改进算法）
  5. 生成树：最小生成树 (Kruskal, Prim)
  6. 联通性：强连通分量、双连通分量
  7. 路径 / 环：Eulerian, Cycle Canceling
  8. 排序 / 结构：拓扑排序，割点检测
  9. 高级：TSP 近似/启发式（有些在 contrib），分配/装载问题辅助结构
  10. 线性规划/组合优化接口：与 GLPK、CPLEX 可集成（构建时可选）

性能与优化技术

  • 避免虚表：全部模板静态分派。
  • 轻量迭代器：通常只是整数索引封装，易于编译器内联。
  • 分离构建与查询：StaticGraph 预打包结构提升局部性。
  • 适配器零拷贝：组合逻辑延迟到访问时处理。
  • Map 抽象：允许用更高效的数组替代哈希/字典。
  • 网络流与最小费用流实现采用多种策略（例如 Network Simplex 对可行树结构的优化）在大规模实例上通常快于通用解 LP 的方式。

扩展/定制机制

  • 提供 GraphTraits 风格：用户可添加自定义图对象，只要暴露所需嵌套类型/方法。
  • Map 与算法解耦：可把算法需要的权重、容量、成本直接绑定到外部结构。
  • 通过适配器组合：例如 ResidualGraph + FlowMap + CapacityMap 实现场景特定视图。

构建与依赖

  • 主要是头文件 + 部分实现源文件；使用 CMake。
  • 可选：开启 GLPK 支持（最小费用流某些求解策略或线性规划接口）。
  • 不强制依赖 Boost；与 Boost Graph Library (BGL) 的设计理念不同，更专注网络优化。

与 Boost Graph Library 对比

  • 关注点：BGL 广而全，偏“通用图抽象 + 访问器”，LEMON 聚焦网络/优化算法并提供更成熟的流与最小费用流实现。
  • 可读性：LEMON 算法接口较直观；BGL 依赖 traits 和 property bundle，有时学习曲线更陡。
  • 性能：LEMON 在专门的网络流、最小费用流上通常更优（手工微调）。
  • 生态：BGL 与 Boost 生态整合度高；LEMON 较独立，功能范围更窄但垂直。

适用场景

  • 物流/供应链：路径规划、最小费用流、容量优化。
  • 电信/网络：路由仿真、带宽分配、流量工程。
  • 运营与排班：匹配、分配、双边市场。
  • 学术研究：快速原型开发组合优化实验。
  • 能源/流体管网：流量平衡与成本优化。

优势总结

  • 代码紧凑、学习后开发效率高。
  • 高质量最小费用流与流算法（Network Simplex 实现鲁棒）。
  • Map/Adaptor 提供函数式组合风格，降低复制与内存开销。
  • 强调确定性与可预测性能（无隐藏动态分配模式）。

可能局限

  • 生态相对小，文档虽有但示例不如更大众库丰富。
  • 泛化到并行/分布式场景支持有限（基本为单机算法）。
  • 对超大规模（>1e8 边）的图仍需用户自行优化内存布局或裁剪特性。
  • 不自带高级图数据库/图分析指标（PageRank 等需自行实现或外部库）。
#include <lemon/list_graph.h>
#include <lemon/dijkstra.h>
using namespace lemon;
ListGraph g;
ListGraph::Node s = g.addNode();
ListGraph::Node t = g.addNode();
auto n3 = g.addNode();
ListGraph::Edge e1 = g.addEdge(s, t);
ListGraph::Edge e2 = g.addEdge(t, n3);
ListGraph::Edge e3 = g.addEdge(s, n3);

// 建立权重映射
ListGraph::EdgeMap<int> weight(g, 1);
weight[e2] = 5;
weight[e3] = 2;

// 最短路
Dijkstra<ListGraph, ListGraph::EdgeMap<int>> d(g, weight);
d.run(s);
int dist = d.dist(n3);