RhodeCode

LEMON code without an explicit copyright notice is covered by the following

copyright/license.

Kutatocsoport (Egervary Combinatorial Optimization Research Group,

EGRES).

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

Boost Software License, Version 1.0

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

Permission is hereby granted, free of charge, to any person or organization

obtaining a copy of the software and accompanying documentation covered by

this license (the "Software") to use, reproduce, display, distribute,

execute, and transmit the Software, and to prepare derivative works of the

Software, and to permit third-parties to whom the Software is furnished to

do so, all subject to the following:

The copyright notices in the Software and this entire statement, including

the above license grant, this restriction and the following disclaimer,

must be included in all copies of the Software, in whole or in part, and

all derivative works of the Software, unless such copies or derivative

works are solely in the form of machine-executable object code generated by

a source language processor.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT

*/

/**

@defgroup heaps Heap Structures

@ingroup datas

\brief %Heap structures implemented in LEMON.

This group contains the heap structures implemented in LEMON.

LEMON provides several heap classes. They are efficient implementations

of the abstract data type \e priority \e queue. They store items with

specified values called \e priorities in such a way that finding and

removing the item with minimum priority are efficient.

The basic operations are adding and erasing items, changing the priority

of an item, etc.

Heaps are crucial in several algorithms, such as Dijkstra and Prim.

The heap implementations have the same interface, thus any of them can be

used easily in such algorithms.

\sa \ref concepts::Heap "Heap concept"

*/

/**

@defgroup auxdat Auxiliary Data Structures

@ingroup datas

\brief Auxiliary data structures implemented in LEMON.

This group contains some data structures implemented in LEMON in

order to make it easier to implement combinatorial algorithms.

*/

/**

@defgroup geomdat Geometric Data Structures

@ingroup auxdat

\brief Geometric data structures implemented in LEMON.

This group contains geometric data structures implemented in LEMON.

 - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional

   vector with the usual operations.

 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the

   rectangular bounding box of a set of \ref lemon::dim2::Point

   "dim2::Point"'s.

*/

/**

@defgroup matrices Matrices

*/

/**

@defgroup min_mean_cycle Minimum Mean Cycle Algorithms

@ingroup algs

\brief Algorithms for finding minimum mean cycles.

This group contains the algorithms for finding minimum mean cycles

\ref clrs01algorithms, \ref amo93networkflows.

The \e minimum \e mean \e cycle \e problem is to find a directed cycle

of minimum mean length (cost) in a digraph.

The mean length of a cycle is the average length of its arcs, i.e. the

ratio between the total length of the cycle and the number of arcs on it.

This problem has an important connection to \e conservative \e length

\e functions, too. A length function on the arcs of a digraph is called

conservative if and only if there is no directed cycle of negative total

length. For an arbitrary length function, the negative of the minimum

cycle mean is the smallest \f$\epsilon\f$ value so that increasing the

arc lengths uniformly by \f$\epsilon\f$ results in a conservative length

function.

LEMON contains three algorithms for solving the minimum mean cycle problem:

  \ref dasdan98minmeancycle.

  version of Karp's algorithm \ref dasdan98minmeancycle.

  \ref dasdan98minmeancycle.

*/

/**

@defgroup matching Matching Algorithms

@ingroup algs

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

This group contains the algorithms for calculating

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

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

edge.

There are several different algorithms for calculate matchings in

graphs.  The matching problems in bipartite graphs are generally

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

can be finding maximum cardinality, maximum weight or minimum cost

matching. The search can be constrained to find perfect or

maximum cardinality matching.

The matching algorithms implemented in LEMON:

- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm

  for calculating maximum cardinality matching in bipartite graphs.

- \ref PrBipartiteMatching Push-relabel algorithm

  for calculating maximum cardinality matching in bipartite graphs.

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

 * purpose.

 *

 */

#ifndef LEMON_ARG_PARSER_H

#define LEMON_ARG_PARSER_H

#include <vector>

#include <map>

#include <list>

#include <string>

#include <iostream>

#include <sstream>

#include <algorithm>

#include <lemon/assert.h>

///\ingroup misc

///\file

///\brief A tool to parse command line arguments.

namespace lemon {

  ///Exception used by ArgParser

  class ArgParserException : public Exception {

  public:

    enum Reason {

    };

  private:

    Reason _reason;

  public:

    ///Constructor

    ArgParserException(Reason r) throw() : _reason(r) {}

    ///Virtual destructor

    virtual ~ArgParserException() throw() {}

    ///A short description of the exception

    virtual const char* what() const throw() {

      switch(_reason)

        {

        case HELP:

          return "lemon::ArgParseException: ask for help";

          break;

        case UNKNOWN_OPT:

          return "lemon::ArgParseException: unknown option";

          break;

        case INVALID_OPT:

          return "lemon::ArgParseException: invalid combination of options";

          break;

        }

 */

#ifndef LEMON_HARTMANN_ORLIN_MMC_H

#define LEMON_HARTMANN_ORLIN_MMC_H

/// \ingroup min_mean_cycle

///

/// \file

/// \brief Hartmann-Orlin's algorithm for finding a minimum mean cycle.

#include <vector>

#include <limits>

#include <lemon/core.h>

#include <lemon/path.h>

#include <lemon/tolerance.h>

#include <lemon/connectivity.h>

namespace lemon {

  /// \brief Default traits class of HartmannOrlinMmc class.

  ///

  /// Default traits class of HartmannOrlinMmc class.

  /// \tparam GR The type of the digraph.

  /// \tparam CM The type of the cost map.

#ifdef DOXYGEN

  template <typename GR, typename CM>

#else

  template <typename GR, typename CM,

    bool integer = std::numeric_limits<typename CM::Value>::is_integer>

#endif

  struct HartmannOrlinMmcDefaultTraits

  {

    /// The type of the digraph

    typedef GR Digraph;

    /// The type of the cost map

    typedef CM CostMap;

    /// The type of the arc costs

    typedef typename CostMap::Value Cost;

    /// \brief The large cost type used for internal computations

    ///

    /// The large cost type used for internal computations.

    /// It is \c long \c long if the \c Cost type is integer,

    /// otherwise it is \c double.

    /// \c Cost must be convertible to \c LargeCost.

    typedef double LargeCost;

    /// The tolerance type used for internal computations

  struct HartmannOrlinMmcDefaultTraits<GR, CM, true>

  {

    typedef GR Digraph;

    typedef CM CostMap;

    typedef typename CostMap::Value Cost;

#ifdef LEMON_HAVE_LONG_LONG

    typedef long long LargeCost;

#else

    typedef long LargeCost;

#endif

    typedef lemon::Tolerance<LargeCost> Tolerance;

    typedef lemon::Path<Digraph> Path;

  };

  /// \addtogroup min_mean_cycle

  /// @{

  /// \brief Implementation of the Hartmann-Orlin algorithm for finding

  /// a minimum mean cycle.

  ///

  /// This class implements the Hartmann-Orlin algorithm for finding

  /// a directed cycle of minimum mean cost in a digraph

  /// \ref amo93networkflows, \ref dasdan98minmeancycle.

  /// it applies an efficient early termination scheme.

  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).

  ///

  /// \tparam GR The type of the digraph the algorithm runs on.

  /// \tparam CM The type of the cost map. The default

  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

  /// \tparam TR The traits class that defines various types used by the

  /// algorithm. By default, it is \ref HartmannOrlinMmcDefaultTraits

  /// "HartmannOrlinMmcDefaultTraits<GR, CM>".

  /// In most cases, this parameter should not be set directly,

  /// consider to use the named template parameters instead.

#ifdef DOXYGEN

  template <typename GR, typename CM, typename TR>

#else

  template < typename GR,

             typename CM = typename GR::template ArcMap<int>,

             typename TR = HartmannOrlinMmcDefaultTraits<GR, CM> >

#endif

  class HartmannOrlinMmc

  {

  public:

    /// The type of the digraph

    typedef typename TR::Digraph Digraph;