RhodeCode

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

 *

 */

#ifndef LEMON_ADAPTORS_H

#define LEMON_ADAPTORS_H

/// \ingroup graph_adaptors

/// \file

/// \brief Adaptor classes for digraphs and graphs

///

/// This file contains several useful adaptors for digraphs and graphs.

#include <lemon/core.h>

#include <lemon/maps.h>

#include <lemon/bits/variant.h>

#include <lemon/bits/graph_adaptor_extender.h>

#include <lemon/tolerance.h>

#include <algorithm>

namespace lemon {

#ifdef _MSC_VER

#define LEMON_SCOPE_FIX(OUTER, NESTED) OUTER::NESTED

#else

#define LEMON_SCOPE_FIX(OUTER, NESTED) typename OUTER::template NESTED

#endif

  template<typename DGR>

  class DigraphAdaptorBase {

  public:

    typedef DGR Digraph;

    typedef DigraphAdaptorBase Adaptor;

  protected:

    DGR* _digraph;

    DigraphAdaptorBase() : _digraph(0) { }

    void initialize(DGR& digraph) { _digraph = &digraph; }

  public:

    DigraphAdaptorBase(DGR& digraph) : _digraph(&digraph) { }

    typedef typename DGR::Node Node;

    typedef typename DGR::Arc Arc;

    void first(Node& i) const { _digraph->first(i); }

    void first(Arc& i) const { _digraph->first(i); }

    void firstIn(Arc& i, const Node& n) const { _digraph->firstIn(i, n); }

/* -*- C++ -*-

 *

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

 *

 */

#ifndef LEMON_BITS_EDGE_SET_EXTENDER_H

#define LEMON_BITS_EDGE_SET_EXTENDER_H

#include <lemon/error.h>

#include <lemon/bits/default_map.h>

///\ingroup digraphbits

///\file

///\brief Extenders for the arc set types

namespace lemon {

  /// \ingroup digraphbits

  ///

  /// \brief Extender for the ArcSets

  template <typename Base>

  class ArcSetExtender : public Base {

  public:

    typedef Base Parent;

    typedef ArcSetExtender Digraph;

    // Base extensions

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    int maxId(Node) const {

      return Parent::maxNodeId();

    }

    int maxId(Arc) const {

      return Parent::maxArcId();

    }

    Node fromId(int id, Node) const {

      return Parent::nodeFromId(id);

    }

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

 *

 */

#ifndef LEMON_BITS_PRED_MAP_PATH_H

#define LEMON_BITS_PRED_MAP_PATH_H

namespace lemon {

  template <typename _Digraph, typename _PredMap>

  class PredMapPath {

  public:

    typedef True RevPathTag;

    typedef _Digraph Digraph;

    typedef typename Digraph::Arc Arc;

    typedef _PredMap PredMap;

    PredMapPath(const Digraph& _digraph, const PredMap& _predMap,

                typename Digraph::Node _target)

      : digraph(_digraph), predMap(_predMap), target(_target) {}

    int length() const {

      int len = 0;

      typename Digraph::Node node = target;

      typename Digraph::Arc arc;

      while ((arc = predMap[node]) != INVALID) {

        node = digraph.source(arc);

        ++len;

      }

      return len;

    }

    bool empty() const {

      return predMap[target] != INVALID;

    }

    class RevArcIt {

    public:

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

 *

 */

#ifndef LEMON_BITS_SOLVER_BITS_H

#define LEMON_BITS_SOLVER_BITS_H

namespace lemon {

  namespace _solver_bits {

    class VarIndex {

    private:

      struct ItemT {

        int prev, next;

        int index;

      };

      std::vector<ItemT> items;

      int first_item, last_item, first_free_item;

      std::vector<int> cross;

    public:

      VarIndex()

        : first_item(-1), last_item(-1), first_free_item(-1) {

      }

      void clear() {

        first_item = -1;

        first_free_item = -1;

        items.clear();

        cross.clear();

      }

      int addIndex(int idx) {

        int n;

        if (first_free_item == -1) {

          n = items.size();

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

 *

 */

///\ingroup concept

///\file

///\brief The concept of heaps.

#ifndef LEMON_CONCEPT_HEAP_H

#define LEMON_CONCEPT_HEAP_H

#include <lemon/core.h>

namespace lemon {

  namespace concepts {

    /// \addtogroup concept

    /// @{

    /// \brief The heap concept.

    ///

    /// Concept class describing the main interface of heaps.

    template <typename Priority, typename ItemIntMap>

    class Heap {

    public:

      /// Type of the items stored in the heap.

      typedef typename ItemIntMap::Key Item;

      /// Type of the priorities.

      typedef Priority Prio;

      /// \brief Type to represent the states of the items.

      ///

      /// Each item has a state associated to it. It can be "in heap",

      /// "pre heap" or "post heap". The later two are indifferent

      /// from the point of view of the heap, but may be useful for

      /// the user.

      ///

      /// The \c ItemIntMap must be initialized in such a way, that it

      /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item.

      enum State {

        IN_HEAP = 0,

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

 *

 */

#ifndef LEMON_ELEVATOR_H

#define LEMON_ELEVATOR_H

///\ingroup auxdat

///\file

///\brief Elevator class

///

///Elevator class implements an efficient data structure

///for labeling items in push-relabel type algorithms.

///

#include <lemon/bits/traits.h>

namespace lemon {

  ///Class for handling "labels" in push-relabel type algorithms.

  ///A class for handling "labels" in push-relabel type algorithms.

  ///

  ///\ingroup auxdat

  ///Using this class you can assign "labels" (nonnegative integer numbers)

  ///to the edges or nodes of a graph, manipulate and query them through

  ///operations typically arising in "push-relabel" type algorithms.

  ///

  ///Each item is either \em active or not, and you can also choose a

  ///highest level active item.

  ///

  ///\sa LinkedElevator

  ///

  ///\param Graph Type of the underlying graph.

  ///\param Item Type of the items the data is assigned to (Graph::Node,

  ///Graph::Arc, Graph::Edge).

  template<class Graph, class Item>

  class Elevator

  {

  public:

    typedef Item Key;

    typedef int Value;

  private:

    typedef Item *Vit;

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

 *

 */

#ifndef LEMON_SUURBALLE_H

#define LEMON_SUURBALLE_H

///\ingroup shortest_path

///\file

///\brief An algorithm for finding arc-disjoint paths between two

/// nodes having minimum total length.

#include <vector>

#include <lemon/bin_heap.h>

#include <lemon/path.h>

namespace lemon {

  /// \addtogroup shortest_path

  /// @{

  /// \brief Algorithm for finding arc-disjoint paths between two nodes

  /// having minimum total length.

  ///

  /// \ref lemon::Suurballe "Suurballe" implements an algorithm for

  /// finding arc-disjoint paths having minimum total length (cost)

  /// from a given source node to a given target node in a digraph.

  ///

  /// In fact, this implementation is the specialization of the

  /// \ref CapacityScaling "successive shortest path" algorithm.

  ///

  /// \tparam Digraph The digraph type the algorithm runs on.

  /// The default value is \c ListDigraph.

  /// \tparam LengthMap The type of the length (cost) map.

  /// The default value is <tt>Digraph::ArcMap<int></tt>.

  ///

  /// \warning Length values should be \e non-negative \e integers.

  ///

  /// \note For finding node-disjoint paths this algorithm can be used

  /// with \ref SplitNodes.

#ifdef DOXYGEN

  template <typename Digraph, typename LengthMap>

#else

  template < typename Digraph = ListDigraph,

             typename LengthMap = typename Digraph::template ArcMap<int> >

#endif

  class Suurballe