RhodeCode

ACLOCAL_AMFLAGS = -I m4

AM_CXXFLAGS = $(WARNINGCXXFLAGS)

AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)

LDADD = $(top_builddir)/lemon/libemon.la

EXTRA_DIST = \

	AUTHORS \

	LICENSE \

	m4/lx_check_cplex.m4 \

	m4/lx_check_glpk.m4 \

	m4/lx_check_soplex.m4 \

	m4/lx_check_coin.m4 \

	CMakeLists.txt \

	cmake/FindGhostscript.cmake \

	cmake/FindCPLEX.cmake \

	cmake/FindGLPK.cmake \

	cmake/FindCOIN.cmake \

	cmake/version.cmake.in \

	cmake/version.cmake \

	cmake/nsis/lemon.ico \

	cmake/nsis/uninstall.ico

pkgconfigdir = $(libdir)/pkgconfig

lemondir = $(pkgincludedir)

bitsdir = $(lemondir)/bits

conceptdir = $(lemondir)/concepts

pkgconfig_DATA =

lib_LTLIBRARIES =

lemon_HEADERS =

bits_HEADERS =

concept_HEADERS =

noinst_HEADERS =

noinst_PROGRAMS =

bin_PROGRAMS =

check_PROGRAMS =

dist_bin_SCRIPTS =

TESTS =

XFAIL_TESTS =

include lemon/Makefile.am

include test/Makefile.am

include doc/Makefile.am

include tools/Makefile.am

DIST_SUBDIRS = demo

demo:

	$(MAKE) $(AM_MAKEFLAGS) -C demo

MRPROPERFILES = \

	aclocal.m4 \

	config.h.in \

	config.h.in~ \

	configure \

	Makefile.in \

	build-aux/config.guess \

	build-aux/config.sub \

	build-aux/depcomp \

	build-aux/install-sh \

	build-aux/ltmain.sh \

	build-aux/missing \

	doc/doxygen.log

mrproper:

	$(MAKE) $(AM_MAKEFLAGS) maintainer-clean

	-rm -f $(MRPROPERFILES)

dist-bz2: dist

	zcat $(PACKAGE)-$(VERSION).tar.gz | \

	bzip2 --best -c > $(PACKAGE)-$(VERSION).tar.bz2

distcheck-bz2: distcheck

	zcat $(PACKAGE)-$(VERSION).tar.gz | \

	bzip2 --best -c > $(PACKAGE)-$(VERSION).tar.bz2

.PHONY: demo mrproper dist-bz2 distcheck-bz2

    /// \brief Default constructor

    ///

    /// Default constructor

    SimplePath() {}

    /// \brief Template copy constructor

    ///

    /// This path can be initialized with any other path type. It just

    /// makes a copy of the given path.

    template <typename CPath>

    SimplePath(const CPath& cpath) {

      copyPath(*this, cpath);

    }

    /// \brief Template copy assignment

    ///

    /// This path can be initialized with any other path type. It just

    /// makes a copy of the given path.

    template <typename CPath>

    SimplePath& operator=(const CPath& cpath) {

      copyPath(*this, cpath);

      return *this;

    }

    /// \brief Iterator class to iterate on the arcs of the paths

    ///

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

    ///

    /// Of course it converts to Digraph::Arc

    class ArcIt {

      friend class SimplePath;

    public:

      /// Default constructor

      ArcIt() {}

      /// Invalid constructor

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

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

      ArcIt(const SimplePath &_path)

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

    private:

      /// Constructor with starting point

      ArcIt(const SimplePath &_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 SimplePath *path;

      int idx;

    };

    /// \brief Length of the path.

    int length() const { return data.size(); }

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

    bool empty() const { return data.empty(); }

    /// \brief Reset the path to an empty one.

    void clear() { data.clear(); }

    /// \brief The nth arc.

    ///

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

    const Arc& nth(int n) const {

      return data[n];

    }

    /// \brief  Initializes arc iterator to point to the nth arc.

    ArcIt nthIt(int n) const {

      return ArcIt(*this, n);

    }

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

    const Arc& front() const {

      return data.front();

    }

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

    const Arc& back() const {

      return data.back();

    }

    /// \brief Add a new arc behind the current path.

    void addBack(const Arc& arc) {

      data.push_back(arc);

    }

    /// \brief Erase the last arc of the path

    void eraseBack() {

      data.pop_back();

    }

    typedef True BuildTag;

    template <typename CPath>

    void build(const CPath& path) {

      int len = path.length();

      data.resize(len);

      int index = 0;

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

        data[index] = it;;

        ++index;

      }

    }

    template <typename CPath>

    void buildRev(const CPath& path) {

      int len = path.length();

      data.resize(len);

      int index = len;

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

        --index;

        data[index] = it;;

      }

    }

  protected:

    typedef std::vector<Arc> Container;

    Container data;

  };

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

  ///

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

  /// \tparam GR 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 in the path and the zero length paths

  /// cannot store the source.

  ///

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

  /// path type. It can be indexed in O(k) time, where k is the rank

  /// of the arc in the path. The length can be computed in O(n)

  /// time. The front and back insertion and erasure is O(1) time

  /// and it can be splited and spliced in O(1) time.

  template <typename GR>

  class ListPath {

  public:

    typedef GR Digraph;

    typedef typename Digraph::Arc Arc;

  protected:

    // the std::list<> is incompatible

    // hard to create invalid iterator

    struct Node {

      Arc arc;

      Node *next, *prev;

    };

    Node *first, *last;

    std::allocator<Node> alloc;

  public:

    /// \brief Default constructor

    ///

    /// Default constructor

    ListPath() : first(0), last(0) {}

    /// \brief Template copy constructor

    ///

    /// This path can be initialized with any other path type. It just

    /// makes a copy of the given path.

    template <typename CPath>

    ListPath(const CPath& cpath) : first(0), last(0) {

      copyPath(*this, cpath);

    }

    /// \brief Destructor of the path

    ///

    /// Destructor of the path

    ~ListPath() {

      clear();

    }

    /// \brief Template copy assignment

    ///

    /// This path can be initialized with any other path type. It just

    /// makes a copy of the given path.

    template <typename CPath>

    ListPath& operator=(const CPath& cpath) {

      copyPath(*this, cpath);

      return *this;

    }

    /// \brief Iterator class to iterate on the arcs of the paths

    ///

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

    ///

    /// Of course it converts to Digraph::Arc

    class ArcIt {

      friend class ListPath;

    public:

      /// Default constructor

      ArcIt() {}

      /// Invalid constructor

      ArcIt(Invalid) : path(0), node(0) {}

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

      ArcIt(const ListPath &_path)

        : path(&_path), node(_path.first) {}

    protected:

      ArcIt(const ListPath &_path, Node *_node)

        : path(&_path), node(_node) {}

    public:

      ///Conversion to Digraph::Arc

      operator const Arc&() const {

        return node->arc;

      }

      /// Next arc

      ArcIt& operator++() {

        node = node->next;

        return *this;

      }

      /// Comparison operator

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

      /// Comparison operator

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

      /// Comparison operator

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

    private:

      const ListPath *path;

      Node *node;

    };

    /// \brief The nth arc.

    ///

    /// This function looks for the nth arc in O(n) time.

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

    const Arc& nth(int n) const {

      Node *node = first;

      for (int i = 0; i < n; ++i) {

        node = node->next;

      }

      return node->arc;

    }

    /// \brief Initializes arc iterator to point to the nth arc.

    ArcIt nthIt(int n) const {

      Node *node = first;

      for (int i = 0; i < n; ++i) {

        node = node->next;

      }

      return ArcIt(*this, node);

    }

    /// \brief Length of the path.

    int length() const {

      int len = 0;

      Node *node = first;

      while (node != 0) {

        node = node->next;

        ++len;

      }

      return len;

    }

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

    bool empty() const { return first == 0; }

    /// \brief Reset the path to an empty one.

    void clear() {

      while (first != 0) {

        last = first->next;

        alloc.destroy(first);

        alloc.deallocate(first, 1);

        first = last;

      }

    }

    /// \brief The first arc of the path

    const Arc& front() const {

      return first->arc;

    }

    /// \brief Add a new arc before the current path

    void addFront(const Arc& arc) {

      Node *node = alloc.allocate(1);

      alloc.construct(node, Node());

      node->prev = 0;

      node->next = first;

      node->arc = arc;

      if (first) {

        first->prev = node;

        first = node;

      } else {

        first = last = node;

      }

    }

    /// \brief Erase the first arc of the path

    void eraseFront() {

      Node *node = first;

      first = first->next;

      if (first) {

        first->prev = 0;

      } else {

        last = 0;

      }

      alloc.destroy(node);

      alloc.deallocate(node, 1);

    }

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

    const Arc& back() const {

      return last->arc;

    }

    /// \brief Add a new arc behind the current path.

    void addBack(const Arc& arc) {

      Node *node = alloc.allocate(1);

      alloc.construct(node, Node());

      node->next = 0;

      node->prev = last;

      node->arc = arc;

      if (last) {

        last->next = node;

        last = node;

      } else {

        last = first = node;

      }

    }

    /// \brief Erase the last arc of the path

    void eraseBack() {

      Node *node = last;

      last = last->prev;

      if (last) {

        last->next = 0;

      } else {

        first = 0;

      }

      alloc.destroy(node);

      alloc.deallocate(node, 1);

    }

    /// \brief Splice a path to the back of the current path.

    ///

    /// It splices \c tpath to the back of the current path and \c

    /// tpath becomes empty. The time complexity of this function is

    /// O(1).

    void spliceBack(ListPath& tpath) {

      if (first) {

        if (tpath.first) {

          last->next = tpath.first;

          tpath.first->prev = last;

          last = tpath.last;

        }

      } else {

        first = tpath.first;

        last = tpath.last;

      }

      tpath.first = tpath.last = 0;

    }

    /// \brief Splice a path to the front of the current path.

    ///

    /// It splices \c tpath before the current path and \c tpath

    /// becomes empty. The time complexity of this function

    /// is O(1).

    void spliceFront(ListPath& tpath) {

      if (first) {

        if (tpath.first) {

          first->prev = tpath.last;

          tpath.last->next = first;

          first = tpath.first;

        }

      } else {

        first = tpath.first;

        last = tpath.last;

      }

      tpath.first = tpath.last = 0;

    }

    /// \brief Splice a path into the current path.

    ///

    /// It splices the \c tpath into the current path before the

    /// position of \c it iterator and \c tpath becomes empty. The

    /// time complexity of this function is O(1). If the \c it is

    /// \c INVALID then it will splice behind the current path.

    void splice(ArcIt it, ListPath& tpath) {

      if (it.node) {

        if (tpath.first) {

          tpath.first->prev = it.node->prev;

          if (it.node->prev) {

            it.node->prev->next = tpath.first;

          } else {

            first = tpath.first;

          }

          it.node->prev = tpath.last;

          tpath.last->next = it.node;

        }

      } else {

        if (first) {

          if (tpath.first) {

            last->next = tpath.first;

            tpath.first->prev = last;

            last = tpath.last;

          }

        } else {

          first = tpath.first;

          last = tpath.last;

        }

      }

      tpath.first = tpath.last = 0;

    }

    /// \brief Split the current path.

    ///

    /// It splits the current path into two parts. The part before

    /// the iterator \c it will remain in the current path and the part

    /// starting with

    /// \c it will put into \c tpath. If \c tpath have arcs

    /// before the operation they are removed first.  The time

    /// complexity of this function is O(1) plus the the time of emtying

    /// \c tpath. If \c it is \c INVALID then it just clears \c tpath

    void split(ArcIt it, ListPath& tpath) {

      tpath.clear();

      if (it.node) {

        tpath.first = it.node;

        tpath.last = last;

        if (it.node->prev) {

          last = it.node->prev;

          last->next = 0;

        } else {

          first = last = 0;

        }

        it.node->prev = 0;

      }

    }

    typedef True BuildTag;

    template <typename CPath>

    void build(const CPath& path) {

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

        addBack(it);

      }

    }

    template <typename CPath>

    void buildRev(const CPath& path) {

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

        addFront(it);

      }

    }

  };

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

  ///

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

  /// \tparam GR 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 in the path and the source node of

  /// a zero length path is undefined.

  ///

  /// This implementation is completly static, i.e. it can be copy constucted

  /// or copy assigned from another path, but otherwise it cannot be

  /// modified.

  ///

  /// Being the the most memory efficient path type in LEMON,

  /// it is intented to be

  /// used when you want to store a large number of paths.

  template <typename GR>

  class StaticPath {

  public:

    typedef GR Digraph;

    typedef typename Digraph::Arc Arc;

    /// \brief Default constructor

    ///

    /// Default constructor

    StaticPath() : len(0), arcs(0) {}

    /// \brief Template copy constructor

    ///

    /// This path can be initialized from any other path type.

    template <typename CPath>

    StaticPath(const CPath& cpath) : arcs(0) {

      copyPath(*this, cpath);

    }

    /// \brief Destructor of the path

    ///

    /// Destructor of the path

    ~StaticPath() {

      if (arcs) delete[] arcs;

    }

    /// \brief Template copy assignment

    ///

    /// This path can be made equal to any other path type. It simply

    /// makes a copy of the given path.

    template <typename CPath>

    StaticPath& operator=(const CPath& cpath) {

      copyPath(*this, cpath);

      return *this;

    }

    /// \brief Iterator class to iterate on the arcs of the paths

    ///

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

    ///

    /// Of course it converts to Digraph::Arc

    class ArcIt {

      friend class StaticPath;

    public:

      /// Default constructor

      ArcIt() {}

      /// Invalid constructor

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

      /// Initializate the constructor to the first arc of path

      ArcIt(const StaticPath &_path)

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

    private:

      /// 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 \c n is in the <tt>[0..length() - 1]</tt> 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; }

    /// \brief 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;

  };

  ///////////////////////////////////////////////////////////////////////

  // Additional utilities

  ///////////////////////////////////////////////////////////////////////

  namespace _path_bits {

    template <typename Path, typename Enable = void>

    struct RevPathTagIndicator {

      static const bool value = false;

    };

    template <typename Path>

    struct RevPathTagIndicator<

      Path,

      typename enable_if<typename Path::RevPathTag, void>::type

      > {

      static const bool value = true;

    };

    template <typename Path, typename Enable = void>

    struct BuildTagIndicator {

      static const bool value = false;

    };

    template <typename Path>

    struct BuildTagIndicator<

      Path,

      typename enable_if<typename Path::BuildTag, void>::type

    > {

      static const bool value = true;

    };

    template <typename Target, typename Source,

              bool buildEnable = BuildTagIndicator<Target>::value>

    struct PathCopySelectorForward {

      static void copy(Target& target, const Source& source) {

        target.clear();

        for (typename Source::ArcIt it(source); it != INVALID; ++it) {

          target.addBack(it);

        }

      }

    };

    template <typename Target, typename Source>

    struct PathCopySelectorForward<Target, Source, true> {

      static void copy(Target& target, const Source& source) {

        target.clear();

        target.build(source);

      }

    };

    template <typename Target, typename Source,

              bool buildEnable = BuildTagIndicator<Target>::value>

    struct PathCopySelectorBackward {

      static void copy(Target& target, const Source& source) {

        target.clear();

        for (typename Source::RevArcIt it(source); it != INVALID; ++it) {

          target.addFront(it);

        }

      }

    };

    template <typename Target, typename Source>

    struct PathCopySelectorBackward<Target, Source, true> {

      static void copy(Target& target, const Source& source) {

        target.clear();

        target.buildRev(source);

      }

    };

    template <typename Target, typename Source,

              bool revEnable = RevPathTagIndicator<Source>::value>

    struct PathCopySelector {

      static void copy(Target& target, const Source& source) {

        PathCopySelectorForward<Target, Source>::copy(target, source);

      }      

    };

    template <typename Target, typename Source>

    struct PathCopySelector<Target, Source, true> {

      static void copy(Target& target, const Source& source) {

        PathCopySelectorBackward<Target, Source>::copy(target, source);

      }      

    };

  }

  /// \brief Make a copy of a path.

  ///

  ///  This function makes a copy of a path.

  template <typename Target, typename Source>

  void copyPath(Target& target, const Source& source) {

    checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();

    _path_bits::PathCopySelector<Target, Source>::copy(target, source);

  }

  /// \brief Check the consistency of a path.

  ///

  /// This function checks that the target of each arc is the same

  /// as the source of the next one.

  ///

  template <typename Digraph, typename Path>

  bool checkPath(const Digraph& digraph, const Path& path) {

    typename Path::ArcIt it(path);

    if (it == INVALID) return true;

    typename Digraph::Node node = digraph.target(it);

    ++it;

    while (it != INVALID) {

      if (digraph.source(it) != node) return false;

      node = digraph.target(it);

      ++it;

    }

    return true;

  }

  /// \brief The source of a path

  ///

  template <typename Digraph, typename Path>

  typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {

  }

  /// \brief The target of a path

  ///

  template <typename Digraph, typename Path>

  typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {

  }

  /// \brief Class which helps to iterate through the nodes of a path

  ///

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

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

  /// cannot enumerate the nodes in the path and the zero length paths

  /// cannot have a source node.

  ///

  /// This class implements the node iterator of a path structure. To

  /// provide this feature, the underlying digraph should be passed to

  /// the constructor of the iterator.

  template <typename Path>

  class PathNodeIt {

  private:

    const typename Path::Digraph *_digraph;

    typename Path::ArcIt _it;

    typename Path::Digraph::Node _nd;

  public:

    typedef typename Path::Digraph Digraph;

    typedef typename Digraph::Node Node;

    /// Default constructor

    PathNodeIt() {}

    /// Invalid constructor

    PathNodeIt(Invalid)

      : _digraph(0), _it(INVALID), _nd(INVALID) {}

    /// Constructor

    PathNodeIt(const Digraph& digraph, const Path& path)

      : _digraph(&digraph), _it(path) {

      _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);

    }

    /// Constructor

    PathNodeIt(const Digraph& digraph, const Path& path, const Node& src)

      : _digraph(&digraph), _it(path), _nd(src) {}

    ///Conversion to Digraph::Node

    operator Node() const {

      return _nd;

    }

    /// Next node

    PathNodeIt& operator++() {

      if (_it == INVALID) _nd = INVALID;

      else {

        _nd = _digraph->target(_it);

        ++_it;

      }

      return *this;

    }

    /// Comparison operator

    bool operator==(const PathNodeIt& n) const {

      return _it == n._it && _nd == n._nd;

    }

    /// Comparison operator

    bool operator!=(const PathNodeIt& n) const {

      return _it != n._it || _nd != n._nd;

    }

    /// Comparison operator

    bool operator<(const PathNodeIt& n) const {

      return (_it < n._it && _nd != INVALID);

    }

  };

  ///@}

} // namespace lemon

#endif // LEMON_PATH_H