doc/groups.dox
 author Peter Kovacs Wed, 29 Apr 2009 03:15:24 +0200 changeset 687 6c408d864fa1 parent 658 85cb3aa71cce child 698 3adf5e2d1e62 child 843 189760a7cdd0 permissions -rw-r--r--
Support negative costs and bounds in NetworkSimplex (#270)

* The interface is reworked to support negative costs and bounds.
- ProblemType and problemType() are renamed to
- ProblemType type is introduced similarly to the LP interface.
- 'bool run()' is replaced by 'ProblemType run()' to handle
unbounded problem instances, as well.
- Add INF public member constant similarly to the LP interface.
* Update the problem definition in the MCF module.
* Remove the usage of Circulation (and adaptors) for checking feasibility.
Check feasibility by examining the artifical arcs instead (after solving
the problem).
* Additional check for unbounded negative cycles found during the
algorithm (it is possible now, since negative costs are allowed).
* Fix in the constructor (the value types needn't be integer any more),
* Improve and extend the doc.
* Rework the test file and add test cases for negative costs and bounds.
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-

     2  *

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

     4  *

     5  * Copyright (C) 2003-2009

     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

     8  *

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

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

    11  * precise terms see the accompanying LICENSE file.

    12  *

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

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

    15  * purpose.

    16  *

    17  */

    18

    19 namespace lemon {

    20

    21 /**

    22 @defgroup datas Data Structures

    23 This group contains the several data structures implemented in LEMON.

    24 */

    25

    26 /**

    27 @defgroup graphs Graph Structures

    28 @ingroup datas

    29 \brief Graph structures implemented in LEMON.

    30

    31 The implementation of combinatorial algorithms heavily relies on

    32 efficient graph implementations. LEMON offers data structures which are

    33 planned to be easily used in an experimental phase of implementation studies,

    34 and thereafter the program code can be made efficient by small modifications.

    35

    36 The most efficient implementation of diverse applications require the

    37 usage of different physical graph implementations. These differences

    38 appear in the size of graph we require to handle, memory or time usage

    39 limitations or in the set of operations through which the graph can be

    40 accessed.  LEMON provides several physical graph structures to meet

    41 the diverging requirements of the possible users.  In order to save on

    42 running time or on memory usage, some structures may fail to provide

    43 some graph features like arc/edge or node deletion.

    44

    45 Alteration of standard containers need a very limited number of

    46 operations, these together satisfy the everyday requirements.

    47 In the case of graph structures, different operations are needed which do

    48 not alter the physical graph, but gives another view. If some nodes or

    49 arcs have to be hidden or the reverse oriented graph have to be used, then

    50 this is the case. It also may happen that in a flow implementation

    51 the residual graph can be accessed by another algorithm, or a node-set

    52 is to be shrunk for another algorithm.

    53 LEMON also provides a variety of graphs for these requirements called

    54 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only

    55 in conjunction with other graph representations.

    56

    57 You are free to use the graph structure that fit your requirements

    58 the best, most graph algorithms and auxiliary data structures can be used

    59 with any graph structure.

    60

    61 <b>See also:</b> \ref graph_concepts "Graph Structure Concepts".

    62 */

    63

    64 /**

    65 @defgroup graph_adaptors Adaptor Classes for Graphs

    66 @ingroup graphs

    67 \brief Adaptor classes for digraphs and graphs

    68

    69 This group contains several useful adaptor classes for digraphs and graphs.

    70

    71 The main parts of LEMON are the different graph structures, generic

    72 graph algorithms, graph concepts, which couple them, and graph

    73 adaptors. While the previous notions are more or less clear, the

    74 latter one needs further explanation. Graph adaptors are graph classes

    75 which serve for considering graph structures in different ways.

    76

    77 A short example makes this much clearer.  Suppose that we have an

    78 instance \c g of a directed graph type, say ListDigraph and an algorithm

    79 \code

    80 template <typename Digraph>

    81 int algorithm(const Digraph&);

    82 \endcode

    83 is needed to run on the reverse oriented graph.  It may be expensive

    84 (in time or in memory usage) to copy \c g with the reversed

    85 arcs.  In this case, an adaptor class is used, which (according

    86 to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.

    87 The adaptor uses the original digraph structure and digraph operations when

    88 methods of the reversed oriented graph are called.  This means that the adaptor

    89 have minor memory usage, and do not perform sophisticated algorithmic

    90 actions.  The purpose of it is to give a tool for the cases when a

    91 graph have to be used in a specific alteration.  If this alteration is

    92 obtained by a usual construction like filtering the node or the arc set or

    93 considering a new orientation, then an adaptor is worthwhile to use.

    94 To come back to the reverse oriented graph, in this situation

    95 \code

    96 template<typename Digraph> class ReverseDigraph;

    97 \endcode

    98 template class can be used. The code looks as follows

    99 \code

   100 ListDigraph g;

   101 ReverseDigraph<ListDigraph> rg(g);

   102 int result = algorithm(rg);

   103 \endcode

   104 During running the algorithm, the original digraph \c g is untouched.

   105 This techniques give rise to an elegant code, and based on stable

   106 graph adaptors, complex algorithms can be implemented easily.

   107

   108 In flow, circulation and matching problems, the residual

   109 graph is of particular importance. Combining an adaptor implementing

   110 this with shortest path algorithms or minimum mean cycle algorithms,

   111 a range of weighted and cardinality optimization algorithms can be

   112 obtained. For other examples, the interested user is referred to the

   113 detailed documentation of particular adaptors.

   114

   115 The behavior of graph adaptors can be very different. Some of them keep

   116 capabilities of the original graph while in other cases this would be

   117 meaningless. This means that the concepts that they meet depend

   118 on the graph adaptor, and the wrapped graph.

   119 For example, if an arc of a reversed digraph is deleted, this is carried

   120 out by deleting the corresponding arc of the original digraph, thus the

   121 adaptor modifies the original digraph.

   122 However in case of a residual digraph, this operation has no sense.

   123

   124 Let us stand one more example here to simplify your work.

   125 ReverseDigraph has constructor

   126 \code

   127 ReverseDigraph(Digraph& digraph);

   128 \endcode

   129 This means that in a situation, when a <tt>const %ListDigraph&</tt>

   130 reference to a graph is given, then it have to be instantiated with

   131 <tt>Digraph=const %ListDigraph</tt>.

   132 \code

   133 int algorithm1(const ListDigraph& g) {

   134   ReverseDigraph<const ListDigraph> rg(g);

   135   return algorithm2(rg);

   136 }

   137 \endcode

   138 */

   139

   140 /**

   141 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs

   142 @ingroup graphs

   143 \brief Graph types between real graphs and graph adaptors.

   144

   145 This group contains some graph types between real graphs and graph adaptors.

   146 These classes wrap graphs to give new functionality as the adaptors do it.

   147 On the other hand they are not light-weight structures as the adaptors.

   148 */

   149

   150 /**

   151 @defgroup maps Maps

   152 @ingroup datas

   153 \brief Map structures implemented in LEMON.

   154

   155 This group contains the map structures implemented in LEMON.

   156

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

   158 new maps from existing ones.

   159

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

   161 */

   162

   163 /**

   164 @defgroup graph_maps Graph Maps

   165 @ingroup maps

   166 \brief Special graph-related maps.

   167

   168 This group contains maps that are specifically designed to assign

   169 values to the nodes and arcs/edges of graphs.

   170

   171 If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,

   172 \c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".

   173 */

   174

   175 /**

   176 \defgroup map_adaptors Map Adaptors

   177 \ingroup maps

   178 \brief Tools to create new maps from existing ones

   179

   180 This group contains map adaptors that are used to create "implicit"

   181 maps from other maps.

   182

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

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

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

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

   187

   188 The typical usage of this classes is passing implicit maps to

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

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

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

   192 \code

   193   Color nodeColor(int deg) {

   194     if (deg >= 2) {

   195       return Color(0.5, 0.0, 0.5);

   196     } else if (deg == 1) {

   197       return Color(1.0, 0.5, 1.0);

   198     } else {

   199       return Color(0.0, 0.0, 0.0);

   200     }

   201   }

   202

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

   204

   205   graphToEps(graph, "graph.eps")

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

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

   208     .run();

   209 \endcode

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

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

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

   213 get the color of each node.

   214

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

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

   217 function map adaptors give back temporary objects.

   218 \code

   219   Digraph graph;

   220

   221   typedef Digraph::ArcMap<double> DoubleArcMap;

   222   DoubleArcMap length(graph);

   223   DoubleArcMap speed(graph);

   224

   225   typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;

   226   TimeMap time(length, speed);

   227

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

   229   dijkstra.run(source, target);

   230 \endcode

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

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

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

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

   235 \c Dijkstra algorithm.

   236 */

   237

   238 /**

   239 @defgroup matrices Matrices

   240 @ingroup datas

   241 \brief Two dimensional data storages implemented in LEMON.

   242

   243 This group contains two dimensional data storages implemented in LEMON.

   244 */

   245

   246 /**

   247 @defgroup paths Path Structures

   248 @ingroup datas

   249 \brief %Path structures implemented in LEMON.

   250

   251 This group contains the path structures implemented in LEMON.

   252

   253 LEMON provides flexible data structures to work with paths.

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

   255 assignment operators and copy constructors. This makes it easy and

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

   257 any kind of path structure.

   258

   259 \sa lemon::concepts::Path

   260 */

   261

   262 /**

   263 @defgroup auxdat Auxiliary Data Structures

   264 @ingroup datas

   265 \brief Auxiliary data structures implemented in LEMON.

   266

   267 This group contains some data structures implemented in LEMON in

   268 order to make it easier to implement combinatorial algorithms.

   269 */

   270

   271 /**

   272 @defgroup algs Algorithms

   273 \brief This group contains the several algorithms

   274 implemented in LEMON.

   275

   276 This group contains the several algorithms

   277 implemented in LEMON.

   278 */

   279

   280 /**

   281 @defgroup search Graph Search

   282 @ingroup algs

   283 \brief Common graph search algorithms.

   284

   285 This group contains the common graph search algorithms, namely

   286 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).

   287 */

   288

   289 /**

   290 @defgroup shortest_path Shortest Path Algorithms

   291 @ingroup algs

   292 \brief Algorithms for finding shortest paths.

   293

   294 This group contains the algorithms for finding shortest paths in digraphs.

   295

   296  - \ref Dijkstra algorithm for finding shortest paths from a source node

   297    when all arc lengths are non-negative.

   298  - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths

   299    from a source node when arc lenghts can be either positive or negative,

   300    but the digraph should not contain directed cycles with negative total

   301    length.

   302  - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms

   303    for solving the \e all-pairs \e shortest \e paths \e problem when arc

   304    lenghts can be either positive or negative, but the digraph should

   305    not contain directed cycles with negative total length.

   306  - \ref Suurballe A successive shortest path algorithm for finding

   307    arc-disjoint paths between two nodes having minimum total length.

   308 */

   309

   310 /**

   311 @defgroup max_flow Maximum Flow Algorithms

   312 @ingroup algs

   313 \brief Algorithms for finding maximum flows.

   314

   315 This group contains the algorithms for finding maximum flows and

   316 feasible circulations.

   317

   318 The \e maximum \e flow \e problem is to find a flow of maximum value between

   319 a single source and a single target. Formally, there is a \f$G=(V,A)\f$

   320 digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and

   321 \f$s, t \in V\f$ source and target nodes.

   322 A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the

   323 following optimization problem.

   324

   325 \f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]

   326 \f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)

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

   328 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]

   329

   330 LEMON contains several algorithms for solving maximum flow problems:

   331 - \ref EdmondsKarp Edmonds-Karp algorithm.

   332 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.

   333 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.

   334 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.

   335

   336 In most cases the \ref Preflow "Preflow" algorithm provides the

   337 fastest method for computing a maximum flow. All implementations

   338 provides functions to also query the minimum cut, which is the dual

   339 problem of the maximum flow.

   340 */

   341

   342 /**

   343 @defgroup min_cost_flow Minimum Cost Flow Algorithms

   344 @ingroup algs

   345

   346 \brief Algorithms for finding minimum cost flows and circulations.

   347

   348 This group contains the algorithms for finding minimum cost flows and

   349 circulations.

   350

   351 The \e minimum \e cost \e flow \e problem is to find a feasible flow of

   352 minimum total cost from a set of supply nodes to a set of demand nodes

   353 in a network with capacity constraints (lower and upper bounds)

   354 and arc costs.

   355 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$,

   356 \f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and

   357 upper bounds for the flow values on the arcs, for which

   358 \f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,

   359 \f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow

   360 on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the

   361 signed supply values of the nodes.

   362 If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$

   363 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with

   364 \f$-sup(u)\f$ demand.

   365 A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution

   366 of the following optimization problem.

   367

   368 \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]

   369 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq

   370     sup(u) \quad \forall u\in V \f]

   371 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]

   372

   373 The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be

   374 zero or negative in order to have a feasible solution (since the sum

   375 of the expressions on the left-hand side of the inequalities is zero).

   376 It means that the total demand must be greater or equal to the total

   377 supply and all the supplies have to be carried out from the supply nodes,

   378 but there could be demands that are not satisfied.

   379 If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand

   380 constraints have to be satisfied with equality, i.e. all demands

   381 have to be satisfied and all supplies have to be used.

   382

   383 If you need the opposite inequalities in the supply/demand constraints

   384 (i.e. the total demand is less than the total supply and all the demands

   385 have to be satisfied while there could be supplies that are not used),

   386 then you could easily transform the problem to the above form by reversing

   387 the direction of the arcs and taking the negative of the supply values

   388 (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).

   389 However \ref NetworkSimplex algorithm also supports this form directly

   390 for the sake of convenience.

   391

   392 A feasible solution for this problem can be found using \ref Circulation.

   393

   394 Note that the above formulation is actually more general than the usual

   395 definition of the minimum cost flow problem, in which strict equalities

   396 are required in the supply/demand contraints, i.e.

   397

   398 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =

   399     sup(u) \quad \forall u\in V. \f]

   400

   401 However if the sum of the supply values is zero, then these two problems

   402 are equivalent. So if you need the equality form, you have to ensure this

   403 additional contraint for the algorithms.

   404

   405 The dual solution of the minimum cost flow problem is represented by node

   406 potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.

   407 An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem

   408 is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$

   409 node potentials the following \e complementary \e slackness optimality

   410 conditions hold.

   411

   412  - For all \f$uv\in A\f$ arcs:

   413    - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;

   414    - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;

   415    - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.

   416  - For all \f$u\in V\f$ nodes:

   417    - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,

   418      then \f$\pi(u)=0\f$.

   419

   420 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc

   421 \f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.

   422 \f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]

   423

   424 All algorithms provide dual solution (node potentials) as well,

   425 if an optimal flow is found.

   426

   427 LEMON contains several algorithms for solving minimum cost flow problems.

   428  - \ref NetworkSimplex Primal Network Simplex algorithm with various

   429    pivot strategies.

   430  - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on

   431    cost scaling.

   432  - \ref CapacityScaling Successive Shortest %Path algorithm with optional

   433    capacity scaling.

   434  - \ref CancelAndTighten The Cancel and Tighten algorithm.

   435  - \ref CycleCanceling Cycle-Canceling algorithms.

   436

   437 Most of these implementations support the general inequality form of the

   438 minimum cost flow problem, but CancelAndTighten and CycleCanceling

   439 only support the equality form due to the primal method they use.

   440

   441 In general NetworkSimplex is the most efficient implementation,

   442 but in special cases other algorithms could be faster.

   443 For example, if the total supply and/or capacities are rather small,

   444 CapacityScaling is usually the fastest algorithm (without effective scaling).

   445 */

   446

   447 /**

   448 @defgroup min_cut Minimum Cut Algorithms

   449 @ingroup algs

   450

   451 \brief Algorithms for finding minimum cut in graphs.

   452

   453 This group contains the algorithms for finding minimum cut in graphs.

   454

   455 The \e minimum \e cut \e problem is to find a non-empty and non-complete

   456 \f$X\f$ subset of the nodes with minimum overall capacity on

   457 outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a

   458 \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum

   459 cut is the \f$X\f$ solution of the next optimization problem:

   460

   461 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}

   462     \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]

   463

   464 LEMON contains several algorithms related to minimum cut problems:

   465

   466 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut

   467   in directed graphs.

   468 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for

   469   calculating minimum cut in undirected graphs.

   470 - \ref GomoryHu "Gomory-Hu tree computation" for calculating

   471   all-pairs minimum cut in undirected graphs.

   472

   473 If you want to find minimum cut just between two distinict nodes,

   474 see the \ref max_flow "maximum flow problem".

   475 */

   476

   477 /**

   478 @defgroup graph_properties Connectivity and Other Graph Properties

   479 @ingroup algs

   480 \brief Algorithms for discovering the graph properties

   481

   482 This group contains the algorithms for discovering the graph properties

   483 like connectivity, bipartiteness, euler property, simplicity etc.

   484

   485 \image html edge_biconnected_components.png

   486 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth

   487 */

   488

   489 /**

   490 @defgroup planar Planarity Embedding and Drawing

   491 @ingroup algs

   492 \brief Algorithms for planarity checking, embedding and drawing

   493

   494 This group contains the algorithms for planarity checking,

   495 embedding and drawing.

   496

   497 \image html planar.png

   498 \image latex planar.eps "Plane graph" width=\textwidth

   499 */

   500

   501 /**

   502 @defgroup matching Matching Algorithms

   503 @ingroup algs

   504 \brief Algorithms for finding matchings in graphs and bipartite graphs.

   505

   506 This group contains the algorithms for calculating

   507 matchings in graphs and bipartite graphs. The general matching problem is

   508 finding a subset of the edges for which each node has at most one incident

   509 edge.

   510

   511 There are several different algorithms for calculate matchings in

   512 graphs.  The matching problems in bipartite graphs are generally

   513 easier than in general graphs. The goal of the matching optimization

   514 can be finding maximum cardinality, maximum weight or minimum cost

   515 matching. The search can be constrained to find perfect or

   516 maximum cardinality matching.

   517

   518 The matching algorithms implemented in LEMON:

   519 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm

   520   for calculating maximum cardinality matching in bipartite graphs.

   521 - \ref PrBipartiteMatching Push-relabel algorithm

   522   for calculating maximum cardinality matching in bipartite graphs.

   523 - \ref MaxWeightedBipartiteMatching

   524   Successive shortest path algorithm for calculating maximum weighted

   525   matching and maximum weighted bipartite matching in bipartite graphs.

   526 - \ref MinCostMaxBipartiteMatching

   527   Successive shortest path algorithm for calculating minimum cost maximum

   528   matching in bipartite graphs.

   529 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating

   530   maximum cardinality matching in general graphs.

   531 - \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating

   532   maximum weighted matching in general graphs.

   533 - \ref MaxWeightedPerfectMatching

   534   Edmond's blossom shrinking algorithm for calculating maximum weighted

   535   perfect matching in general graphs.

   536

   537 \image html bipartite_matching.png

   538 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth

   539 */

   540

   541 /**

   542 @defgroup spantree Minimum Spanning Tree Algorithms

   543 @ingroup algs

   544 \brief Algorithms for finding a minimum cost spanning tree in a graph.

   545

   546 This group contains the algorithms for finding a minimum cost spanning

   547 tree in a graph.

   548 */

   549

   550 /**

   551 @defgroup auxalg Auxiliary Algorithms

   552 @ingroup algs

   553 \brief Auxiliary algorithms implemented in LEMON.

   554

   555 This group contains some algorithms implemented in LEMON

   556 in order to make it easier to implement complex algorithms.

   557 */

   558

   559 /**

   560 @defgroup approx Approximation Algorithms

   561 @ingroup algs

   562 \brief Approximation algorithms.

   563

   564 This group contains the approximation and heuristic algorithms

   565 implemented in LEMON.

   566 */

   567

   568 /**

   569 @defgroup gen_opt_group General Optimization Tools

   570 \brief This group contains some general optimization frameworks

   571 implemented in LEMON.

   572

   573 This group contains some general optimization frameworks

   574 implemented in LEMON.

   575 */

   576

   577 /**

   578 @defgroup lp_group Lp and Mip Solvers

   579 @ingroup gen_opt_group

   580 \brief Lp and Mip solver interfaces for LEMON.

   581

   582 This group contains Lp and Mip solver interfaces for LEMON. The

   583 various LP solvers could be used in the same manner with this

   584 interface.

   585 */

   586

   587 /**

   588 @defgroup lp_utils Tools for Lp and Mip Solvers

   589 @ingroup lp_group

   590 \brief Helper tools to the Lp and Mip solvers.

   591

   592 This group adds some helper tools to general optimization framework

   593 implemented in LEMON.

   594 */

   595

   596 /**

   597 @defgroup metah Metaheuristics

   598 @ingroup gen_opt_group

   599 \brief Metaheuristics for LEMON library.

   600

   601 This group contains some metaheuristic optimization tools.

   602 */

   603

   604 /**

   605 @defgroup utils Tools and Utilities

   606 \brief Tools and utilities for programming in LEMON

   607

   608 Tools and utilities for programming in LEMON.

   609 */

   610

   611 /**

   612 @defgroup gutils Basic Graph Utilities

   613 @ingroup utils

   614 \brief Simple basic graph utilities.

   615

   616 This group contains some simple basic graph utilities.

   617 */

   618

   619 /**

   620 @defgroup misc Miscellaneous Tools

   621 @ingroup utils

   622 \brief Tools for development, debugging and testing.

   623

   624 This group contains several useful tools for development,

   625 debugging and testing.

   626 */

   627

   628 /**

   629 @defgroup timecount Time Measuring and Counting

   630 @ingroup misc

   631 \brief Simple tools for measuring the performance of algorithms.

   632

   633 This group contains simple tools for measuring the performance

   634 of algorithms.

   635 */

   636

   637 /**

   638 @defgroup exceptions Exceptions

   639 @ingroup utils

   640 \brief Exceptions defined in LEMON.

   641

   642 This group contains the exceptions defined in LEMON.

   643 */

   644

   645 /**

   646 @defgroup io_group Input-Output

   647 \brief Graph Input-Output methods

   648

   649 This group contains the tools for importing and exporting graphs

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

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

   652 postscript (EPS) format.

   653 */

   654

   655 /**

   656 @defgroup lemon_io LEMON Graph Format

   657 @ingroup io_group

   658 \brief Reading and writing LEMON Graph Format.

   659

   660 This group contains methods for reading and writing

   661 \ref lgf-format "LEMON Graph Format".

   662 */

   663

   664 /**

   665 @defgroup eps_io Postscript Exporting

   666 @ingroup io_group

   667 \brief General \c EPS drawer and graph exporter

   668

   669 This group contains general \c EPS drawing methods and special

   670 graph exporting tools.

   671 */

   672

   673 /**

   674 @defgroup dimacs_group DIMACS format

   675 @ingroup io_group

   676 \brief Read and write files in DIMACS format

   677

   678 Tools to read a digraph from or write it to a file in DIMACS format data.

   679 */

   680

   681 /**

   682 @defgroup nauty_group NAUTY Format

   683 @ingroup io_group

   684 \brief Read \e Nauty format

   685

   686 Tool to read graphs from \e Nauty format data.

   687 */

   688

   689 /**

   690 @defgroup concept Concepts

   691 \brief Skeleton classes and concept checking classes

   692

   693 This group contains the data/algorithm skeletons and concept checking

   694 classes implemented in LEMON.

   695

   696 The purpose of the classes in this group is fourfold.

   697

   698 - These classes contain the documentations of the %concepts. In order

   699   to avoid document multiplications, an implementation of a concept

   700   simply refers to the corresponding concept class.

   701

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

   703   implementation of the %concepts should provide, however completely

   704   without implementations and real data structures behind the

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

   706   the algorithms working on a data structure meeting a certain concept

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

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

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

   710

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

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

   713   concept indeed provides all the required features.

   714

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

   716 */

   717

   718 /**

   719 @defgroup graph_concepts Graph Structure Concepts

   720 @ingroup concept

   721 \brief Skeleton and concept checking classes for graph structures

   722

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

   724 graph structures and helper classes used to implement these.

   725 */

   726

   727 /**

   728 @defgroup map_concepts Map Concepts

   729 @ingroup concept

   730 \brief Skeleton and concept checking classes for maps

   731

   732 This group contains the skeletons and concept checking classes of maps.

   733 */

   734

   735 /**

   736 \anchor demoprograms

   737

   738 @defgroup demos Demo Programs

   739

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

   741 the \c demo subdirectory of the source tree.

   742

   743 In order to compile them, use the <tt>make demo</tt> or the

   744 <tt>make check</tt> commands.

   745 */

   746

   747 /**

   748 @defgroup tools Standalone Utility Applications

   749

   750 Some utility applications are listed here.

   751

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

   753 them, as well.

   754 */

   755

   756 }