RhodeCode

Installation Instructions

=========================

tarballs and successfully extracted it. The latest version of LEMON is

available at our web page (http://lemon.cs.elte.hu/).

issue the following commands:

   1. `cd lemon-x.y.z'

      This command changes to the directory which was created when you

      extracted the sources. The x.y.z part is a version number.

   2. `./configure'

      This command runs the configure shell script, which does some checks and

      creates the makefiles.

   3. `make'

      This command compiles the non-template part of LEMON into libemon.a

   4. `make check'

      This step is optional, but recommended. It runs the test programs that

      we developed for LEMON to check whether the library works properly on

      your platform.

   5. `make install'

      This command installs LEMON under /usr/local (you will need root

      privileges to be able to do that). If you want to install it to some

      other location, then pass the --prefix=DIRECTORY flag to configure in

      step 2. For example: `./configure --prefix=/home/username/lemon'.

   6. `make install-html'

      This command installs the documentation under share/doc/lemon/docs. The

      generated documentation is included in the tarball. If you want to

      generate it yourself, then run `make html'. Note that for this you need

      to have the following programs installed: Doxygen, Graphviz, Ghostscript,

      Latex.

Configure Options and Variables

===============================

and passing options to it. This can be done like this:

`./configure [OPTION]... [VARIABLE=VALUE]...'

CXX='comp'

  Change the C++ compiler to 'comp'.

CXXFLAGS='flags'

  Pass the 'flags' to the compiler. For example CXXFLAGS='-O3 -march=pentium-m'

  turns on generation of aggressively optimized Pentium-M specific code.

--prefix=PREFIX

  Set the installation prefix to PREFIX. By default it is /usr/local.

--enable-demo

   Build the examples in the demo subdirectory.

--disable-demo

   Do not build the examples in the demo subdirectory (default).

--enable-tools

   Build the programs in the tools subdirectory (default).

--disable-tools

   Do not build the programs in the tools subdirectory.

--with-glpk[=PREFIX]

   Enable GLPK support (default). You should specify the prefix too if

   you installed GLPK to some non-standard location (e.g. your home

   directory). If it is not found, GLPK support will be disabled.

--with-glpk-includedir=DIR

   The directory where the GLPK header files are located. This is only

   useful when the GLPK headers and libraries are not under the same

   prefix (which is unlikely).

--with-glpk-libdir=DIR

   The directory where the GLPK libraries are located. This is only

   useful when the GLPK headers and libraries are not under the same

   prefix (which is unlikely).

--without-glpk

   Disable GLPK support.

--with-cplex[=PREFIX]

   Enable CPLEX support (default). You should specify the prefix too

   if you installed CPLEX to some non-standard location

   (e.g. /opt/ilog/cplex75). If it is not found, CPLEX support will be

   disabled.

--with-cplex-includedir=DIR

   The directory where the CPLEX header files are located. This is

   only useful when the CPLEX headers and libraries are not under the

   same prefix (e.g.  /usr/local/cplex/cplex75/include).

--with-cplex-libdir=DIR

   The directory where the CPLEX libraries are located. This is only

   useful when the CPLEX headers and libraries are not under the same

   prefix (e.g.

   /usr/local/cplex/cplex75/lib/i86_linux2_glibc2.2_gcc3.0/static_pic_mt).

--without-cplex

   Disable CPLEX support.

--with-soplex[=PREFIX]

   Enable SoPlex support (default). You should specify the prefix too if

   you installed SoPlex to some non-standard location (e.g. your home

   directory). If it is not found, SoPlex support will be disabled.

--with-soplex-includedir=DIR

   The directory where the SoPlex header files are located. This is only

   useful when the SoPlex headers and libraries are not under the same

   prefix (which is unlikely).

--with-soplex-libdir=DIR

   The directory where the SoPlex libraries are located. This is only

   useful when the SoPlex headers and libraries are not under the same

   prefix (which is unlikely).

--without-soplex

   Disable SoPlex support.

==================================================================

LEMON - a Library of Efficient Models and Optimization in Networks

==================================================================

LEMON is an open source library written in C++. It provides

easy-to-use implementations of common data structures and algorithms

in the area of optimization and helps implementing new ones. The main

focus is on graphs and graph algorithms, thus it is especially

suitable for solving design and optimization problems of

telecommunication networks. To achieve wide usability its data

structures and algorithms provide generic interfaces.

Contents

========

LICENSE

   Copying, distribution and modification conditions and terms.

INSTALL

   General building and installation instructions.

lemon/

   Source code of LEMON library.

doc/

   Documentation of LEMON. The starting page is doc/html/index.html.

demo/

   Some example programs to make you easier to get familiar with LEMON.

test/

tools/

   Various utilities related to LEMON.

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

/**

\dir demo

for educational purposes.

*/

/**

\dir doc

\brief Auxiliary (and the whole generated) documentation.

*/

/**

\dir test

\brief Test programs.

This directory contains several test programs that check the consistency

of the code.

*/

/**

\dir tools

This directory contains the sources of some useful complete executables.

*/

/**

\dir lemon

prefixed with this, e.g.

\code

#include<lemon/list_graph.h>

#include<lemon/dijkstra.h>

\endcode

*/

/**

\dir concepts

*/

/**

\dir bits

*/

/**

@defgroup maps Maps

@ingroup datas

\brief Map structures implemented in LEMON.

This group describes the map structures implemented in LEMON.

LEMON provides several special purpose maps and map adaptors that e.g. combine

new maps from existing ones.

<b>See also:</b> \ref map_concepts "Map Concepts".

*/

/**

@defgroup graph_maps Graph Maps

@ingroup maps

\brief Special graph-related maps.

This group describes maps that are specifically designed to assign

values to the nodes and arcs of graphs.

*/

/**

\defgroup map_adaptors Map Adaptors

\ingroup maps

\brief Tools to create new maps from existing ones

This group describes map adaptors that are used to create "implicit"

maps from other maps.

Most of them are \ref lemon::concepts::ReadMap "read-only maps".

They can make arithmetic and logical operations between one or two maps

(negation, shifting, addition, multiplication, logical 'and', 'or',

'not' etc.) or e.g. convert a map to another one of different Value type.

The typical usage of this classes is passing implicit maps to

algorithms.  If a function type algorithm is called then the function

type map adaptors can be used comfortable. For example let's see the

usage of map adaptors with the \c graphToEps() function.

\code

  Color nodeColor(int deg) {

    if (deg >= 2) {

      return Color(0.5, 0.0, 0.5);

    } else if (deg == 1) {

      return Color(1.0, 0.5, 1.0);

    } else {

      return Color(0.0, 0.0, 0.0);

    }

  }

  Digraph::NodeMap<int> degree_map(graph);

  graphToEps(graph, "graph.eps")

    .coords(coords).scaleToA4().undirected()

    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))

    .run();

\endcode

The \c functorToMap() function makes an \c int to \c Color map from the

\c nodeColor() function. The \c composeMap() compose the \c degree_map

and the previously created map. The composed map is a proper function to

get the color of each node.

The usage with class type algorithms is little bit harder. In this

case the function type map adaptors can not be used, because the

function map adaptors give back temporary objects.

\code

  Digraph graph;

  typedef Digraph::ArcMap<double> DoubleArcMap;

  DoubleArcMap length(graph);

  DoubleArcMap speed(graph);

  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;

  TimeMap time(length, speed);

  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);

  dijkstra.run(source, target);

\endcode

We have a length map and a maximum speed map on the arcs of a digraph.

The minimum time to pass the arc can be calculated as the division of

the two maps which can be done implicitly with the \c DivMap template

class. We use the implicit minimum time map as the length map of the

\c Dijkstra algorithm.

*/

/**

@defgroup matrices Matrices

@ingroup datas

\brief Two dimensional data storages implemented in LEMON.

This group describes two dimensional data storages implemented in LEMON.

*/

/**

@defgroup paths Path Structures

@ingroup datas

This group describes the path structures implemented in LEMON.

LEMON provides flexible data structures to work with paths.

All of them have similar interfaces and they can be copied easily with

assignment operators and copy constructors. This makes it easy and

efficient to have e.g. the Dijkstra algorithm to store its result in

any kind of path structure.

\sa lemon::concepts::Path

*/

/**

@defgroup auxdat Auxiliary Data Structures

@ingroup datas

\brief Auxiliary data structures implemented in LEMON.

This group describes some data structures implemented in LEMON in

order to make it easier to implement combinatorial algorithms.

*/

/**

@defgroup algs Algorithms

\brief This group describes the several algorithms

implemented in LEMON.

This group describes the several algorithms

implemented in LEMON.

*/

/**

@defgroup search Graph Search

@ingroup algs

\brief Common graph search algorithms.

This group describes the common graph search algorithms like

Breadth-First Search (BFS) and Depth-First Search (DFS).

*/

/**

@defgroup shortest_path Shortest Path Algorithms

@ingroup algs

\brief Algorithms for finding shortest paths.

This group describes the algorithms for finding shortest paths in graphs.

*/

/**

@defgroup max_flow Maximum Flow Algorithms

@ingroup algs

\brief Algorithms for finding maximum flows.

This group describes the algorithms for finding maximum flows and

feasible circulations.

The maximum flow problem is to find a flow between a single source and

a single target that is maximum. Formally, there is a \f$G=(V,A)\f$

directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity

function and given \f$s, t \in V\f$ source and target node. The

maximum flow is the \f$f_a\f$ solution of the next optimization problem:

\f[ 0 \le f_a \le c_a \f]

\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}

\qquad \forall u \in V \setminus \{s,t\}\f]

\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]

LEMON contains several algorithms for solving maximum flow problems:

- \ref lemon::EdmondsKarp "Edmonds-Karp"

- \ref lemon::Preflow "Goldberg's Preflow algorithm"

- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"

- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"

In most cases the \ref lemon::Preflow "Preflow" algorithm provides the

fastest method to compute the maximum flow. All impelementations

provides functions to query the minimum cut, which is the dual linear

programming problem of the maximum flow.

*/

/**

@defgroup min_cost_flow Minimum Cost Flow Algorithms

@ingroup algs

\brief Algorithms for finding minimum cost flows and circulations.

This group describes the algorithms for finding minimum cost flows and

circulations.

*/

/**

@defgroup min_cut Minimum Cut Algorithms

@ingroup algs

\brief Algorithms for finding minimum cut in graphs.

This group describes the algorithms for finding minimum cut in graphs.

/**

@defgroup lp_utils Tools for Lp and Mip Solvers

@ingroup lp_group

\brief Helper tools to the Lp and Mip solvers.

This group adds some helper tools to general optimization framework

implemented in LEMON.

*/

/**

@defgroup metah Metaheuristics

@ingroup gen_opt_group

\brief Metaheuristics for LEMON library.

This group describes some metaheuristic optimization tools.

*/

/**

@defgroup utils Tools and Utilities

\brief Tools and utilities for programming in LEMON

Tools and utilities for programming in LEMON.

*/

/**

@defgroup gutils Basic Graph Utilities

@ingroup utils

\brief Simple basic graph utilities.

This group describes some simple basic graph utilities.

*/

/**

@defgroup misc Miscellaneous Tools

@ingroup utils

\brief Tools for development, debugging and testing.

This group describes several useful tools for development,

debugging and testing.

*/

/**

@defgroup timecount Time Measuring and Counting

@ingroup misc

\brief Simple tools for measuring the performance of algorithms.

This group describes simple tools for measuring the performance

of algorithms.

*/

/**

@defgroup exceptions Exceptions

@ingroup utils

\brief Exceptions defined in LEMON.

This group describes the exceptions defined in LEMON.

*/

/**

@defgroup io_group Input-Output

\brief Graph Input-Output methods

This group describes the tools for importing and exporting graphs

and graph related data. Now it supports the \ref lgf-format

"LEMON Graph Format", the \c DIMACS format and the encapsulated

postscript (EPS) format.

*/

/**

@defgroup lemon_io LEMON Input-Output

@ingroup io_group

\brief Reading and writing LEMON Graph Format.

This group describes methods for reading and writing

\ref lgf-format "LEMON Graph Format".

*/

/**

@defgroup eps_io Postscript Exporting

@ingroup io_group

\brief General \c EPS drawer and graph exporter

This group describes general \c EPS drawing methods and special

graph exporting tools.

*/

/**

@defgroup concept Concepts

\brief Skeleton classes and concept checking classes

This group describes the data/algorithm skeletons and concept checking

classes implemented in LEMON.

The purpose of the classes in this group is fourfold.

  to avoid document multiplications, an implementation of a concept

  simply refers to the corresponding concept class.

- These classes declare every functions, <tt>typedef</tt>s etc. an

  without implementations and real data structures behind the

  interface. On the other hand they should provide nothing else. All

  the algorithms working on a data structure meeting a certain concept

  should compile with these classes. (Though it will not run properly,

  of course.) In this way it is easily to check if an algorithm

  doesn't use any extra feature of a certain implementation.

- The concept descriptor classes also provide a <em>checker class</em>

  that makes it possible to check whether a certain implementation of a

  concept indeed provides all the required features.

- Finally, They can serve as a skeleton of a new implementation of a concept.

*/

/**

@defgroup graph_concepts Graph Structure Concepts

@ingroup concept

\brief Skeleton and concept checking classes for graph structures

This group describes the skeletons and concept checking classes of LEMON's

graph structures and helper classes used to implement these.

*/

/**

@defgroup map_concepts Map Concepts

@ingroup concept

\brief Skeleton and concept checking classes for maps

This group describes the skeletons and concept checking classes of maps.

*/

/**

\anchor demoprograms

@defgroup demos Demo programs

Some demo programs are listed here. Their full source codes can be found in

the \c demo subdirectory of the source tree.

It order to compile them, use <tt>--enable-demo</tt> configure option when

build the library.

*/

/**

@defgroup tools Standalone utility applications

Some utility applications are listed here.

The standard compilation procedure (<tt>./configure;make</tt>) will compile

them, as well.

*/