RhodeCode

EXTRA_DIST += \

	lemon/Makefile \

	lemon/lemon.pc.in

pkgconfig_DATA += lemon/lemon.pc

lib_LTLIBRARIES += lemon/libemon.la

lemon_libemon_la_SOURCES = \

        lemon/base.cc \

        lemon/random.cc

lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)

lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)

lemon_HEADERS += \

        lemon/dim2.h \

	lemon/maps.h \

	lemon/path.h \

        lemon/random.h \

	lemon/list_graph.h \

        lemon/tolerance.h

bits_HEADERS += \

	lemon/bits/alteration_notifier.h \

	lemon/bits/array_map.h \

	lemon/bits/base_extender.h \

	lemon/bits/default_map.h \

	lemon/bits/graph_extender.h \

        lemon/bits/invalid.h \

	lemon/bits/map_extender.h \

	lemon/bits/traits.h \

        lemon/bits/utility.h \

	lemon/bits/vector_map.h

concept_HEADERS += \

	lemon/concept_check.h \

	lemon/concepts/digraph.h \

	lemon/concepts/graph.h \

	lemon/concepts/maps.h \

	lemon/concepts/path.h \

	lemon/concepts/graph_components.h

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

 *

 */

///\ingroup paths

///\file

///\brief Classes for representing paths in digraphs.

///

#ifndef LEMON_PATH_H

#define LEMON_PATH_H

#include <vector>

#include <algorithm>

#include <lemon/error.h>

#include <lemon/bits/invalid.h>

namespace lemon {

  /// \addtogroup paths

  /// @{

  /// \brief A structure for representing directed paths in a digraph.

  ///

  /// A structure for representing directed path in a digraph.

  /// \param Digraph The digraph type in which the path is.

  ///

  /// In a sense, the path can be treated as a list of arcs. The

  /// lemon path type stores just this list. As a consequence, it

  /// cannot enumerate the nodes of the path and the source node of

  /// a zero length path is undefined.

  ///

  /// This implementation is a back and front insertable and erasable

  /// path type. It can be indexed in O(1) time. The front and back

  /// insertion and erase is done in O(1) (amortized) time. The

  /// implementation uses two vectors for storing the front and back

  /// insertions.

  template <typename _Digraph>

  class Path {

  public:

    typedef _Digraph Digraph;

    typedef typename Digraph::Arc Arc;

    /// \brief Default constructor

    ///

    /// Default constructor

    Path() {}

    /// \brief Template copy constructor

    ///

    /// This constuctor initializes the path from any other path type.

    /// It simply makes a copy of the given path.

    template <typename CPath>

    Path(const CPath& cpath) {

      copyPath(*this, cpath);

    }

    /// \brief Template copy assignment

    ///

    /// This operator makes a copy of a path of any other type.

    template <typename CPath>

    Path& operator=(const CPath& cpath) {

      copyPath(*this, cpath);

      return *this;

    }

    /// \brief Lemon style iterator for path arcs

    ///

    /// This class is used to iterate on the arcs of the paths.

    class ArcIt {

      friend class Path;

    public:

      /// \brief Default constructor

      ArcIt() {}

      /// \brief Invalid constructor

      ArcIt(Invalid) : path(0), idx(-1) {}

      /// \brief Initializate the iterator to the first arc of path

      ArcIt(const Path &_path) 

        : path(&_path), idx(_path.empty() ? -1 : 0) {}

    private:

      ArcIt(const Path &_path, int _idx) 

        : path(&_path), idx(_idx) {}

    public:

      /// \brief Conversion to Arc

      operator const Arc&() const {

        return path->nth(idx);

      }

      /// \brief Next arc

      ArcIt& operator++() { 

        ++idx;

        if (idx >= path->length()) idx = -1; 

        return *this; 

      }

      /// \brief Comparison operator

      bool operator==(const ArcIt& e) const { return idx==e.idx; }

      /// \brief Comparison operator

      bool operator!=(const ArcIt& e) const { return idx!=e.idx; }

      /// \brief Comparison operator

      bool operator<(const ArcIt& e) const { return idx<e.idx; }

    private:

      const Path *path;

      /// Constructor with starting point

      ArcIt(const StaticPath &_path, int _idx) 

        : idx(_idx), path(&_path) {}

    public:

      ///Conversion to Digraph::Arc

      operator const Arc&() const {

        return path->nth(idx);

      }

      /// Next arc

      ArcIt& operator++() { 

        ++idx;

        if (idx >= path->length()) idx = -1; 

        return *this; 

      }

      /// Comparison operator

      bool operator==(const ArcIt& e) const { return idx==e.idx; }

      /// Comparison operator

      bool operator!=(const ArcIt& e) const { return idx!=e.idx; }

      /// Comparison operator

      bool operator<(const ArcIt& e) const { return idx<e.idx; }

    private:

      const StaticPath *path;

      int idx;

    };

    /// \brief The nth arc.

    ///

    /// \pre n is in the [0..length() - 1] range

    const Arc& nth(int n) const {

      return arcs[n];

    }

    /// \brief The arc iterator pointing to the nth arc.

    ArcIt nthIt(int n) const {

      return ArcIt(*this, n);

    }

    /// \brief The length of the path.

    int length() const { return len; }

    /// \brief Return true when the path is empty.

    int empty() const { return len == 0; }

    /// \break Erase all arcs in the digraph.

    void clear() {

      len = 0;

      if (arcs) delete[] arcs;

      arcs = 0;

    }

    /// \brief The first arc of the path.

    const Arc& front() const {

      return arcs[0];

    }

    /// \brief The last arc of the path.

    const Arc& back() const {

      return arcs[len - 1];

    }

    typedef True BuildTag;

    template <typename CPath>

    void build(const CPath& path) {

      len = path.length();

      arcs = new Arc[len];

      int index = 0;

      for (typename CPath::ArcIt it(path); it != INVALID; ++it) {

        arcs[index] = it;

        ++index;

      }

    }

    template <typename CPath>

    void buildRev(const CPath& path) {

      len = path.length();

      arcs = new Arc[len];

      int index = len;

      for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {

        --index;

        arcs[index] = it;

      }

    }

  private:

    int len;

    Arc* arcs;

  };

  ///@}

} // namespace lemon

#endif // LEMON_PATH_H