LEMON
| LEMON | |
|---|---|
| Информация | |
| Начальный выпуск | 30 сентября 2004 |
| Стабильная версия | 1.3.1 / 7 июля 2014 |
| Язык программирования | C++ |
| Операционная система | Кроссплатформенная |
| Платформа | gcc,icc,Visual Studio, xlC |
| Тип | Библиотека для работы с графами и сетевыми оптимизациями |
| Лицензия | Свободное программное обеспечение (Лицензия Boost) |
| Сайт | lemon.cs.elte.hu |
| Репозиторий | lemon.cs.elte.hu/hg/lemon/ |
LEMON — это библиотека для работы с графами с открытым исходным кодом, написанная на языке C++. Она предоставляет реализации распространённых структур данных и алгоритмов с фокусом на задачи комбинаторной оптимизации, связанные в основном с графами и сетями. Библиотека является частью проекта COIN-OR.
LEMON — это аббревиатура от Library for Efficient Modeling and Optimization in Networks (Библиотека для эффективного моделирования и оптимизации в сетях).
Конструктивные особенности[править]
LEMON использует обобщённое программирование в C++ с помощью шаблонов. Инструменты библиотеки разработаны как универсальные, удобные и высокоэффективные. Их можно легко комбинировать для решения сложных реальных задач оптимизации. Например, графы LEMON могут различаться по многим параметрам (в зависимости от представления и других особенностей), но все они должны удовлетворять одному или нескольким концептам графов, которые представляют собой стандартизированные интерфейсы для взаимодействия с остальной частью библиотеки.
Возможности[править]
LEMON предоставляет:
- Графовые структуры и связанные с ними инструменты
- Алгоритмы поиска по графу
- Алгоритмы поиска кратчайших путей
- Алгоритмы поиска максимального потока
- Алгоритмы поиска потока минимальной стоимости
- Алгоритмы поиска минимального разреза
- Алгоритмы проверки связности и других свойств графов
- Алгоритмы поиска максимального паросочетания и паросочетания минимальной стоимости
- Алгоритмы поиска остовного дерева минимальной стоимости
- Аппроксимационные алгоритмы
- Вспомогательные алгоритмы
LEMON также содержит некоторые инструменты метаэвристической оптимизации и предоставляет общий высокоуровневый интерфейс для нескольких решателей задач линейного и целочисленного программирования (LP и MIP), таких как GLPK, ILOG CPLEX, CLP, CBC, SoPlex.
LEMON имеет собственный формат хранения графов, так называемый Lemon Graph Format (Формат графов LEMON), и включает общие методы EPS-рисования, а также специальные инструменты для экспорта графов.
LEMON также включает несколько вспомогательных инструментов. Например, он предоставляет простые средства для измерения производительности алгоритмов, которые можно использовать для сравнения различных реализаций одной и той же задачи.