RhodeCode

    // The processed nodes in the last round

    std::vector<Node> _process;

    Tolerance _tolerance;

    // Infinite constant

    const LargeValue INF;

  public:

    /// \name Named Template Parameters

    /// @{

    template <typename T>

    struct SetLargeValueTraits : public Traits {

      typedef T LargeValue;

      typedef lemon::Tolerance<T> Tolerance;

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// \c LargeValue type.

    ///

    /// \ref named-templ-param "Named parameter" for setting \c LargeValue

    /// type. It is used for internal computations in the algorithm.

    template <typename T>

    struct SetLargeValue

      : public HartmannOrlin<GR, LEN, SetLargeValueTraits<T> > {

      typedef HartmannOrlin<GR, LEN, SetLargeValueTraits<T> > Create;

    };

    template <typename T>

    struct SetPathTraits : public Traits {

      typedef T Path;

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// \c %Path type.

    ///

    /// \ref named-templ-param "Named parameter" for setting the \c %Path

    /// type of the found cycles.

    /// It must conform to the \ref lemon::concepts::Path "Path" concept

    /// and it must have an \c addFront() function.

    template <typename T>

    struct SetPath

      : public HartmannOrlin<GR, LEN, SetPathTraits<T> > {

      typedef HartmannOrlin<GR, LEN, SetPathTraits<T> > Create;

    };

    /// @}

  public:

    /// \brief Constructor.

    ///

    /// The constructor of the class.

    ///

    /// \param digraph The digraph the algorithm runs on.

    /// \param length The lengths (costs) of the arcs.

    HartmannOrlin( const Digraph &digraph,

                   const LengthMap &length ) :

      _gr(digraph), _length(length), _comp(digraph), _out_arcs(digraph),

      _best_found(false), _best_length(0), _best_size(1),

      _cycle_path(NULL), _local_path(false), _data(digraph),

      INF(std::numeric_limits<LargeValue>::has_infinity ?

          std::numeric_limits<LargeValue>::infinity() :

          std::numeric_limits<LargeValue>::max())

    {}

    /// Destructor.

    ~HartmannOrlin() {

      if (_local_path) delete _cycle_path;

    }

    /// \brief Set the path structure for storing the found cycle.

    ///

    /// This function sets an external path structure for storing the

    /// found cycle.

    ///

    /// If you don't call this function before calling \ref run() or

    /// \ref findMinMean(), it will allocate a local \ref Path "path"

    /// structure. The destuctor deallocates this automatically

    /// allocated object, of course.

    ///

    /// \note The algorithm calls only the \ref lemon::Path::addFront()

    /// "addFront()" function of the given path structure.

    ///

    /// \return <tt>(*this)</tt>

    HartmannOrlin& cycle(Path &path) {

      if (_local_path) {

        delete _cycle_path;

        _local_path = false;

      }

      _cycle_path = &path;

      return *this;

    }

    /// \name Execution control

    /// The simplest way to execute the algorithm is to call the \ref run()

    /// function.\n

    /// If you only need the minimum mean length, you may call

    /// \ref findMinMean().

    /// @{

    /// \brief Run the algorithm.

    ///

    /// This function runs the algorithm.

    /// It can be called more than once (e.g. if the underlying digraph

    /// and/or the arc lengths have been modified).

    ///

    /// \return \c true if a directed cycle exists in the digraph.

    ///

    /// \note <tt>mmc.run()</tt> is just a shortcut of the following code.

    /// \code

    ///   return mmc.findMinMean() && mmc.findCycle();

    /// \endcode

    bool run() {

      return findMinMean() && findCycle();

    }

    /// \brief Find the minimum cycle mean.

    ///

    /// This function finds the minimum mean length of the directed

    /// cycles in the digraph.

    ///

    /// \return \c true if a directed cycle exists in the digraph.

    bool findMinMean() {

      // Initialization and find strongly connected components

      init();

      findComponents();

      // Find the minimum cycle mean in the components

      for (int comp = 0; comp < _comp_num; ++comp) {

        if (!initComponent(comp)) continue;

        processRounds();

        // Update the best cycle (global minimum mean cycle)

        if ( _curr_found && (!_best_found || 

             _curr_length * _best_size < _best_length * _curr_size) ) {

          _best_found = true;

          _best_length = _curr_length;

          _best_size = _curr_size;

          _best_node = _curr_node;

          _best_level = _curr_level;

        }

      }

      return _best_found;

    }

    /// \brief Find a minimum mean directed cycle.

    ///

    /// This function finds a directed cycle of minimum mean length

    /// in the digraph using the data computed by findMinMean().

    ///

    /// \return \c true if a directed cycle exists in the digraph.

    ///

    /// \pre \ref findMinMean() must be called before using this function.

    bool findCycle() {

      if (!_best_found) return false;

      IntNodeMap reached(_gr, -1);

      int r = _best_level + 1;

      Node u = _best_node;

      while (reached[u] < 0) {

        reached[u] = --r;

        u = _gr.source(_data[u][r].pred);

      }

      r = reached[u];

      Arc e = _data[u][r].pred;

      _cycle_path->addFront(e);

      _best_length = _length[e];

      _best_size = 1;

      Node v;

      while ((v = _gr.source(e)) != u) {

        e = _data[v][--r].pred;

        _cycle_path->addFront(e);

        _best_length += _length[e];

        ++_best_size;

      }

      return true;

    }

    /// @}

    /// \name Query Functions

    /// The results of the algorithm can be obtained using these

    /// functions.\n

    /// The algorithm should be executed before using them.

    /// @{

    /// \brief Return the total length of the found cycle.

    ///

    int _qfront, _qback;

    Tolerance _tolerance;

    // Infinite constant

    const LargeValue INF;

  public:

    /// \name Named Template Parameters

    /// @{

    template <typename T>

    struct SetLargeValueTraits : public Traits {

      typedef T LargeValue;

      typedef lemon::Tolerance<T> Tolerance;

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// \c LargeValue type.

    ///

    /// \ref named-templ-param "Named parameter" for setting \c LargeValue

    /// type. It is used for internal computations in the algorithm.

    template <typename T>

    struct SetLargeValue

      : public Howard<GR, LEN, SetLargeValueTraits<T> > {

      typedef Howard<GR, LEN, SetLargeValueTraits<T> > Create;

    };

    template <typename T>

    struct SetPathTraits : public Traits {

      typedef T Path;

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// \c %Path type.

    ///

    /// \ref named-templ-param "Named parameter" for setting the \c %Path

    /// type of the found cycles.

    /// It must conform to the \ref lemon::concepts::Path "Path" concept

    /// and it must have an \c addBack() function.

    template <typename T>

    struct SetPath

      : public Howard<GR, LEN, SetPathTraits<T> > {

      typedef Howard<GR, LEN, SetPathTraits<T> > Create;

    };

    /// @}

  public:

    /// \brief Constructor.

    ///

    /// The constructor of the class.

    ///

    /// \param digraph The digraph the algorithm runs on.

    /// \param length The lengths (costs) of the arcs.

    Howard( const Digraph &digraph,

            const LengthMap &length ) :

      _gr(digraph), _length(length), _best_found(false),

      _best_length(0), _best_size(1), _cycle_path(NULL), _local_path(false),

      _policy(digraph), _reached(digraph), _level(digraph), _dist(digraph),

      _comp(digraph), _in_arcs(digraph),

      INF(std::numeric_limits<LargeValue>::has_infinity ?

          std::numeric_limits<LargeValue>::infinity() :

          std::numeric_limits<LargeValue>::max())

    {}

    /// Destructor.

    ~Howard() {

      if (_local_path) delete _cycle_path;

    }

    /// \brief Set the path structure for storing the found cycle.

    ///

    /// This function sets an external path structure for storing the

    /// found cycle.

    ///

    /// If you don't call this function before calling \ref run() or

    /// \ref findMinMean(), it will allocate a local \ref Path "path"

    /// structure. The destuctor deallocates this automatically

    /// allocated object, of course.

    ///

    /// \note The algorithm calls only the \ref lemon::Path::addBack()

    /// "addBack()" function of the given path structure.

    ///

    /// \return <tt>(*this)</tt>

    Howard& cycle(Path &path) {

      if (_local_path) {

        delete _cycle_path;

        _local_path = false;

      }

      _cycle_path = &path;

      return *this;

    }

    /// \name Execution control

    /// The simplest way to execute the algorithm is to call the \ref run()

    /// function.\n

    /// If you only need the minimum mean length, you may call

    /// \ref findMinMean().

    /// @{

    /// \brief Run the algorithm.

    ///

    /// This function runs the algorithm.

    /// It can be called more than once (e.g. if the underlying digraph

    /// and/or the arc lengths have been modified).

    ///

    /// \return \c true if a directed cycle exists in the digraph.

    ///

    /// \note <tt>mmc.run()</tt> is just a shortcut of the following code.

    /// \code

    ///   return mmc.findMinMean() && mmc.findCycle();

    /// \endcode

    bool run() {

      return findMinMean() && findCycle();

    }

    /// \brief Find the minimum cycle mean.

    ///

    /// This function finds the minimum mean length of the directed

    /// cycles in the digraph.

    ///

    /// \return \c true if a directed cycle exists in the digraph.

    bool findMinMean() {

      // Initialize and find strongly connected components

      init();

      findComponents();

      // Find the minimum cycle mean in the components

      for (int comp = 0; comp < _comp_num; ++comp) {

        // Find the minimum mean cycle in the current component

        if (!buildPolicyGraph(comp)) continue;

        while (true) {

          findPolicyCycle();

          if (!computeNodeDistances()) break;

        }

        // Update the best cycle (global minimum mean cycle)

        if ( _curr_found && (!_best_found ||

             _curr_length * _best_size < _best_length * _curr_size) ) {

          _best_found = true;

          _best_length = _curr_length;

          _best_size = _curr_size;

          _best_node = _curr_node;

        }

      }

      return _best_found;

    }

    /// \brief Find a minimum mean directed cycle.

    ///

    /// This function finds a directed cycle of minimum mean length

    /// in the digraph using the data computed by findMinMean().

    ///

    /// \return \c true if a directed cycle exists in the digraph.

    ///

    /// \pre \ref findMinMean() must be called before using this function.

    bool findCycle() {

      if (!_best_found) return false;

      _cycle_path->addBack(_policy[_best_node]);

      for ( Node v = _best_node;

            (v = _gr.target(_policy[v])) != _best_node; ) {

        _cycle_path->addBack(_policy[v]);

      }

      return true;

    }

    /// @}

    /// \name Query Functions

    /// The results of the algorithm can be obtained using these

    /// functions.\n

    /// The algorithm should be executed before using them.

    /// @{

    /// \brief Return the total length of the found cycle.

    ///

    /// This function returns the total length of the found cycle.

    ///

    /// \pre \ref run() or \ref findMinMean() must be called before

    /// using this function.

    LargeValue cycleLength() const {

      return _best_length;

    }

    /// \brief Return the number of arcs on the found cycle.

    ///

    /// This function returns the number of arcs on the found cycle.

    ///

    // The processed nodes in the last round

    std::vector<Node> _process;

    Tolerance _tolerance;

    // Infinite constant

    const LargeValue INF;

  public:

    /// \name Named Template Parameters

    /// @{

    template <typename T>

    struct SetLargeValueTraits : public Traits {

      typedef T LargeValue;

      typedef lemon::Tolerance<T> Tolerance;

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// \c LargeValue type.

    ///

    /// \ref named-templ-param "Named parameter" for setting \c LargeValue

    /// type. It is used for internal computations in the algorithm.

    template <typename T>

    struct SetLargeValue

      : public Karp<GR, LEN, SetLargeValueTraits<T> > {

      typedef Karp<GR, LEN, SetLargeValueTraits<T> > Create;

    };

    template <typename T>

    struct SetPathTraits : public Traits {

      typedef T Path;

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// \c %Path type.

    ///

    /// \ref named-templ-param "Named parameter" for setting the \c %Path

    /// type of the found cycles.

    /// It must conform to the \ref lemon::concepts::Path "Path" concept

    /// and it must have an \c addFront() function.

    template <typename T>

    struct SetPath

      : public Karp<GR, LEN, SetPathTraits<T> > {

      typedef Karp<GR, LEN, SetPathTraits<T> > Create;

    };

    /// @}

  public:

    /// \brief Constructor.

    ///

    /// The constructor of the class.

    ///

    /// \param digraph The digraph the algorithm runs on.

    /// \param length The lengths (costs) of the arcs.

    Karp( const Digraph &digraph,

          const LengthMap &length ) :

      _gr(digraph), _length(length), _comp(digraph), _out_arcs(digraph),

      _cycle_length(0), _cycle_size(1), _cycle_node(INVALID),

      _cycle_path(NULL), _local_path(false), _data(digraph),

      INF(std::numeric_limits<LargeValue>::has_infinity ?

          std::numeric_limits<LargeValue>::infinity() :

          std::numeric_limits<LargeValue>::max())

    {}

    /// Destructor.

    ~Karp() {

      if (_local_path) delete _cycle_path;

    }

    /// \brief Set the path structure for storing the found cycle.

    ///

    /// This function sets an external path structure for storing the

    /// found cycle.

    ///

    /// If you don't call this function before calling \ref run() or

    /// \ref findMinMean(), it will allocate a local \ref Path "path"

    /// structure. The destuctor deallocates this automatically

    /// allocated object, of course.

    ///

    /// \note The algorithm calls only the \ref lemon::Path::addFront()

    /// "addFront()" function of the given path structure.

    ///

    /// \return <tt>(*this)</tt>

    Karp& cycle(Path &path) {

      if (_local_path) {

        delete _cycle_path;

        _local_path = false;

      }

      _cycle_path = &path;

      return *this;

    }

    /// \name Execution control

    /// The simplest way to execute the algorithm is to call the \ref run()

    /// function.\n

    /// If you only need the minimum mean length, you may call

    /// \ref findMinMean().

    /// @{

    /// \brief Run the algorithm.

    ///

    /// This function runs the algorithm.

    /// It can be called more than once (e.g. if the underlying digraph

    /// and/or the arc lengths have been modified).

    ///

    /// \return \c true if a directed cycle exists in the digraph.

    ///

    /// \note <tt>mmc.run()</tt> is just a shortcut of the following code.

    /// \code

    ///   return mmc.findMinMean() && mmc.findCycle();

    /// \endcode

    bool run() {

      return findMinMean() && findCycle();

    }

    /// \brief Find the minimum cycle mean.

    ///

    /// This function finds the minimum mean length of the directed

    /// cycles in the digraph.

    ///

    /// \return \c true if a directed cycle exists in the digraph.

    bool findMinMean() {

      // Initialization and find strongly connected components

      init();

      findComponents();

      // Find the minimum cycle mean in the components

      for (int comp = 0; comp < _comp_num; ++comp) {

        if (!initComponent(comp)) continue;

        processRounds();

        updateMinMean();

      }

      return (_cycle_node != INVALID);

    }

    /// \brief Find a minimum mean directed cycle.

    ///

    /// This function finds a directed cycle of minimum mean length

    /// in the digraph using the data computed by findMinMean().

    ///

    /// \return \c true if a directed cycle exists in the digraph.

    ///

    /// \pre \ref findMinMean() must be called before using this function.

    bool findCycle() {

      if (_cycle_node == INVALID) return false;

      IntNodeMap reached(_gr, -1);

      int r = _data[_cycle_node].size();

      Node u = _cycle_node;

      while (reached[u] < 0) {

        reached[u] = --r;

        u = _gr.source(_data[u][r].pred);

      }

      r = reached[u];

      Arc e = _data[u][r].pred;

      _cycle_path->addFront(e);

      _cycle_length = _length[e];

      _cycle_size = 1;

      Node v;

      while ((v = _gr.source(e)) != u) {

        e = _data[v][--r].pred;

        _cycle_path->addFront(e);

        _cycle_length += _length[e];

        ++_cycle_size;

      }

      return true;

    }

    /// @}

    /// \name Query Functions

    /// The results of the algorithm can be obtained using these

    /// functions.\n

    /// The algorithm should be executed before using them.

    /// @{

    /// \brief Return the total length of the found cycle.

    ///

    /// This function returns the total length of the found cycle.

    ///

    /// \pre \ref run() or \ref findMinMean() must be called before

    /// using this function.

    LargeValue cycleLength() const {

      return _cycle_length;

    }

    /// \brief Return the number of arcs on the found cycle.

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

 *

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

 *

 * Copyright (C) 2003-2009

 * 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.

 *

 */

#include <iostream>

#include <sstream>

#include <lemon/smart_graph.h>

#include <lemon/lgf_reader.h>

#include <lemon/path.h>

#include <lemon/concepts/digraph.h>

#include <lemon/concept_check.h>

#include <lemon/karp.h>

#include <lemon/hartmann_orlin.h>

#include <lemon/howard.h>

#include "test_tools.h"

using namespace lemon;

char test_lgf[] =

  "@nodes\n"

  "label\n"

  "1\n"

  "2\n"

  "3\n"

  "4\n"

  "5\n"

  "6\n"

  "7\n"

  "@arcs\n"

  "    len1 len2 len3 len4  c1 c2 c3 c4\n"

  "1 2    1    1    1    1   0  0  0  0\n"

  "2 4    5    5    5    5   1  0  0  0\n"

  "2 3    8    8    8    8   0  0  0  0\n"

  "3 2   -2    0    0    0   1  0  0  0\n"

  "3 4    4    4    4    4   0  0  0  0\n"

  "3 7   -4   -4   -4   -4   0  0  0  0\n"

  "4 1    2    2    2    2   0  0  0  0\n"

  "4 3    3    3    3    3   1  0  0  0\n"

  "4 4    3    3    0    0   0  0  1  0\n"

  "5 2    4    4    4    4   0  0  0  0\n"

  "5 6    3    3    3    3   0  1  0  0\n"

  "6 5    2    2    2    2   0  1  0  0\n"

  "6 4   -1   -1   -1   -1   0  0  0  0\n"

  "6 7    1    1    1    1   0  0  0  0\n"

  "7 7    4    4    4   -1   0  0  0  1\n";

// Check the interface of an MMC algorithm

template <typename GR, typename Value>

struct MmcClassConcept

{

  template <typename MMC>

  struct Constraints {

    void constraints() {

      const Constraints& me = *this;

      typedef typename MMC

        ::template SetPath<ListPath<GR> >

        ::template SetLargeValue<Value>

        ::Create MmcAlg;

      MmcAlg mmc(me.g, me.length);

      const MmcAlg& const_mmc = mmc;

      b = mmc.cycle(p).run();

      b = mmc.findMinMean();

      b = mmc.findCycle();

      v = const_mmc.cycleLength();

      i = const_mmc.cycleArcNum();

      d = const_mmc.cycleMean();

      p = const_mmc.cycle();

    }

    typedef concepts::ReadMap<typename GR::Arc, Value> LM;

    GR g;

    LM length;

    ListPath<GR> p;

    Value v;

    int i;

    double d;

    bool b;

  };

};

// Perform a test with the given parameters

template <typename MMC>

void checkMmcAlg(const SmartDigraph& gr,

                 const SmartDigraph::ArcMap<int>& lm,

                 const SmartDigraph::ArcMap<int>& cm,

                 int length, int size) {

  MMC alg(gr, lm);

  alg.findMinMean();

  check(alg.cycleMean() == static_cast<double>(length) / size,

        "Wrong cycle mean");

  alg.findCycle();

  check(alg.cycleLength() == length && alg.cycleArcNum() == size,

        "Wrong path");

  SmartDigraph::ArcMap<int> cycle(gr, 0);

  for (typename MMC::Path::ArcIt a(alg.cycle()); a != INVALID; ++a) {

    ++cycle[a];

  }

  for (SmartDigraph::ArcIt a(gr); a != INVALID; ++a) {

    check(cm[a] == cycle[a], "Wrong path");

  }

}

// Class for comparing types

template <typename T1, typename T2>

struct IsSameType {

  static const int result = 0;

};

template <typename T>

struct IsSameType<T,T> {

  static const int result = 1;

};

int main() {

  #ifdef LEMON_HAVE_LONG_LONG

    typedef long long long_int;

  #else

    typedef long long_int;

  #endif

  // Check the interface

  {

    typedef concepts::Digraph GR;

    // Karp

    checkConcept< MmcClassConcept<GR, int>,

                  Karp<GR, concepts::ReadMap<GR::Arc, int> > >();

    checkConcept< MmcClassConcept<GR, float>,

                  Karp<GR, concepts::ReadMap<GR::Arc, float> > >();

    // HartmannOrlin

    checkConcept< MmcClassConcept<GR, int>,

                  HartmannOrlin<GR, concepts::ReadMap<GR::Arc, int> > >();

    checkConcept< MmcClassConcept<GR, float>,

                  HartmannOrlin<GR, concepts::ReadMap<GR::Arc, float> > >();

    // Howard

    checkConcept< MmcClassConcept<GR, int>,

                  Howard<GR, concepts::ReadMap<GR::Arc, int> > >();

    checkConcept< MmcClassConcept<GR, float>,

                  Howard<GR, concepts::ReadMap<GR::Arc, float> > >();

    if (IsSameType<Howard<GR, concepts::ReadMap<GR::Arc, int> >::LargeValue,

          long_int>::result == 0) check(false, "Wrong LargeValue type");

    if (IsSameType<Howard<GR, concepts::ReadMap<GR::Arc, float> >::LargeValue,

          double>::result == 0) check(false, "Wrong LargeValue type");

  }

  // Run various tests

  {

    typedef SmartDigraph GR;

    DIGRAPH_TYPEDEFS(GR);