# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1201174279 0
# Node ID b55e501a90ee50e31c3633507975647029fa1235
# Parent 6ec5dbed8f1896434ffca37a48bd75d60ca0505d
Path related files ported from svn -r3435
but ItemReader/Writer for Path (originally belonging to path_utils.h)
hasn't ported yet.
diff -r 6ec5dbed8f18 -r b55e501a90ee lemon/Makefile.am
--- a/lemon/Makefile.am Wed Jan 23 16:26:41 2008 +0100
+++ b/lemon/Makefile.am Thu Jan 24 11:31:19 2008 +0000
@@ -17,6 +17,8 @@
lemon_HEADERS += \
lemon/dim2.h \
lemon/maps.h \
+ lemon/path.h \
+ lemon/path_utils.h \
lemon/random.h \
lemon/list_graph.h \
lemon/tolerance.h
@@ -38,4 +40,5 @@
lemon/concepts/digraph.h \
lemon/concepts/graph.h \
lemon/concepts/maps.h \
+ lemon/concepts/path.h \
lemon/concepts/graph_components.h
diff -r 6ec5dbed8f18 -r b55e501a90ee lemon/concepts/path.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/concepts/path.h Thu Jan 24 11:31:19 2008 +0000
@@ -0,0 +1,307 @@
+/* -*- 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 concept
+///\file
+///\brief Classes for representing paths in digraphs.
+///
+///\todo Iterators have obsolete style
+
+#ifndef LEMON_CONCEPT_PATH_H
+#define LEMON_CONCEPT_PATH_H
+
+#include <lemon/bits/invalid.h>
+#include <lemon/bits/utility.h>
+#include <lemon/concept_check.h>
+
+namespace lemon {
+ namespace concepts {
+
+ /// \addtogroup concept
+ /// @{
+
+ /// \brief A skeleton structure for representing directed paths in
+ /// a digraph.
+ ///
+ /// A skeleton structure for representing directed paths 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 in the path and the zero length
+ /// paths cannot store the source.
+ ///
+ template <typename _Digraph>
+ class Path {
+ public:
+
+ /// Type of the underlying digraph.
+ typedef _Digraph Digraph;
+ /// Arc type of the underlying digraph.
+ typedef typename Digraph::Arc Arc;
+
+ class ArcIt;
+
+ /// \brief Default constructor
+ Path() {}
+
+ /// \brief Template constructor
+ template <typename CPath>
+ Path(const CPath& cpath) {}
+
+ /// \brief Template assigment
+ template <typename CPath>
+ Path& operator=(const CPath& cpath) {}
+
+ /// Length of the path ie. the number of arcs in the path.
+ int length() const { return 0;}
+
+ /// Returns whether the path is empty.
+ bool empty() const { return true;}
+
+ /// Resets the path to an empty path.
+ void clear() {}
+
+ /// \brief Lemon style iterator for path arcs
+ ///
+ /// This class is used to iterate on the arcs of the paths.
+ class ArcIt {
+ public:
+ /// Default constructor
+ ArcIt() {}
+ /// Invalid constructor
+ ArcIt(Invalid) {}
+ /// Constructor for first arc
+ ArcIt(const Path &) {}
+
+ /// Conversion to Arc
+ operator Arc() const { return INVALID; }
+
+ /// Next arc
+ ArcIt& operator++() {return *this;}
+
+ /// Comparison operator
+ bool operator==(const ArcIt&) const {return true;}
+ /// Comparison operator
+ bool operator!=(const ArcIt&) const {return true;}
+ /// Comparison operator
+ bool operator<(const ArcIt&) const {return false;}
+
+ };
+
+ template <typename _Path>
+ struct Constraints {
+ void constraints() {
+ Path<Digraph> pc;
+ _Path p, pp(pc);
+ int l = p.length();
+ int e = p.empty();
+ p.clear();
+
+ p = pc;
+
+ typename _Path::ArcIt id, ii(INVALID), i(p);
+
+ ++i;
+ typename Digraph::Arc ed = i;
+
+ e = (i == ii);
+ e = (i != ii);
+ e = (i < ii);
+
+ ignore_unused_variable_warning(l);
+ ignore_unused_variable_warning(pp);
+ ignore_unused_variable_warning(e);
+ ignore_unused_variable_warning(id);
+ ignore_unused_variable_warning(ii);
+ ignore_unused_variable_warning(ed);
+ }
+ };
+
+ };
+
+ namespace _path_bits {
+
+ template <typename _Digraph, typename _Path, typename RevPathTag = void>
+ struct PathDumperConstraints {
+ void constraints() {
+ int l = p.length();
+ int e = p.empty();
+
+ typename _Path::ArcIt id, i(p);
+
+ ++i;
+ typename _Digraph::Arc ed = i;
+
+ e = (i == INVALID);
+ e = (i != INVALID);
+
+ ignore_unused_variable_warning(l);
+ ignore_unused_variable_warning(e);
+ ignore_unused_variable_warning(id);
+ ignore_unused_variable_warning(ed);
+ }
+ _Path& p;
+ };
+
+ template <typename _Digraph, typename _Path>
+ struct PathDumperConstraints<
+ _Digraph, _Path,
+ typename enable_if<typename _Path::RevPathTag, void>::type
+ > {
+ void constraints() {
+ int l = p.length();
+ int e = p.empty();
+
+ typename _Path::RevArcIt id, i(p);
+
+ ++i;
+ typename _Digraph::Arc ed = i;
+
+ e = (i == INVALID);
+ e = (i != INVALID);
+
+ ignore_unused_variable_warning(l);
+ ignore_unused_variable_warning(e);
+ ignore_unused_variable_warning(id);
+ ignore_unused_variable_warning(ed);
+ }
+ _Path& p;
+ };
+
+ }
+
+
+ /// \brief A skeleton structure for path dumpers.
+ ///
+ /// A skeleton structure for path dumpers. The path dumpers are
+ /// the generalization of the paths. The path dumpers can
+ /// enumerate the arcs of the path wheter in forward or in
+ /// backward order. In most time these classes are not used
+ /// directly rather it used to assign a dumped class to a real
+ /// path type.
+ ///
+ /// The main purpose of this concept is that the shortest path
+ /// algorithms can enumerate easily the arcs in reverse order.
+ /// If we would like to give back a real path from these
+ /// algorithms then we should create a temporarly path object. In
+ /// Lemon such algorithms gives back a path dumper what can
+ /// assigned to a real path and the dumpers can be implemented as
+ /// an adaptor class to the predecessor map.
+
+ /// \param _Digraph The digraph type in which the path is.
+ ///
+ /// The paths can be constructed from any path type by a
+ /// template constructor or a template assignment operator.
+ ///
+ template <typename _Digraph>
+ class PathDumper {
+ public:
+
+ /// Type of the underlying digraph.
+ typedef _Digraph Digraph;
+ /// Arc type of the underlying digraph.
+ typedef typename Digraph::Arc Arc;
+
+ /// Length of the path ie. the number of arcs in the path.
+ int length() const { return 0;}
+
+ /// Returns whether the path is empty.
+ bool empty() const { return true;}
+
+ /// \brief Forward or reverse dumping
+ ///
+ /// If the RevPathTag is defined and true then reverse dumping
+ /// is provided in the path dumper. In this case instead of the
+ /// ArcIt the RevArcIt iterator should be implemented in the
+ /// dumper.
+ typedef False RevPathTag;
+
+ /// \brief Lemon style iterator for path arcs
+ ///
+ /// This class is used to iterate on the arcs of the paths.
+ class ArcIt {
+ public:
+ /// Default constructor
+ ArcIt() {}
+ /// Invalid constructor
+ ArcIt(Invalid) {}
+ /// Constructor for first arc
+ ArcIt(const PathDumper&) {}
+
+ /// Conversion to Arc
+ operator Arc() const { return INVALID; }
+
+ /// Next arc
+ ArcIt& operator++() {return *this;}
+
+ /// Comparison operator
+ bool operator==(const ArcIt&) const {return true;}
+ /// Comparison operator
+ bool operator!=(const ArcIt&) const {return true;}
+ /// Comparison operator
+ bool operator<(const ArcIt&) const {return false;}
+
+ };
+
+ /// \brief Lemon style iterator for path arcs
+ ///
+ /// This class is used to iterate on the arcs of the paths in
+ /// reverse direction.
+ class RevArcIt {
+ public:
+ /// Default constructor
+ RevArcIt() {}
+ /// Invalid constructor
+ RevArcIt(Invalid) {}
+ /// Constructor for first arc
+ RevArcIt(const PathDumper &) {}
+
+ /// Conversion to Arc
+ operator Arc() const { return INVALID; }
+
+ /// Next arc
+ RevArcIt& operator++() {return *this;}
+
+ /// Comparison operator
+ bool operator==(const RevArcIt&) const {return true;}
+ /// Comparison operator
+ bool operator!=(const RevArcIt&) const {return true;}
+ /// Comparison operator
+ bool operator<(const RevArcIt&) const {return false;}
+
+ };
+
+ template <typename _Path>
+ struct Constraints {
+ void constraints() {
+ function_requires<_path_bits::
+ PathDumperConstraints<Digraph, _Path> >();
+ }
+ };
+
+ };
+
+
+ ///@}
+ }
+
+} // namespace lemon
+
+#endif // LEMON_CONCEPT_PATH_H
diff -r 6ec5dbed8f18 -r b55e501a90ee lemon/path.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/path.h Thu Jan 24 11:31:19 2008 +0000
@@ -0,0 +1,903 @@
+/* -*- 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/path_utils.h>
+#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 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(1) time. The front and back
+ /// insertion and erasure is amortized O(1) time. The
+ /// impelementation is based on two opposite organized vectors.
+ 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 path can be initialized with any other path type. It just
+ /// makes a copy of the given path.
+ template <typename CPath>
+ Path(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>
+ 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 constructor 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;
+ int idx;
+ };
+
+ /// \brief Length of the path.
+ int length() const { return head.size() + tail.size(); }
+ /// \brief Returns whether the path is empty.
+ bool empty() const { return head.empty() && tail.empty(); }
+
+ /// \brief Resets the path to an empty path.
+ void clear() { head.clear(); tail.clear(); }
+
+ /// \brief Gives back the nth arc.
+ ///
+ /// \pre n is in the [0..length() - 1] range
+ const Arc& nth(int n) const {
+ return n < int(head.size()) ? *(head.rbegin() + n) :
+ *(tail.begin() + (n - head.size()));
+ }
+
+ /// \brief Initializes arc iterator to point to the nth arc
+ ///
+ /// \pre n is in the [0..length() - 1] range
+ ArcIt nthIt(int n) const {
+ return ArcIt(*this, n);
+ }
+
+ /// \brief Gives back the first arc of the path
+ const Arc& front() const {
+ return head.empty() ? tail.front() : head.back();
+ }
+
+ /// \brief Add a new arc before the current path
+ void addFront(const Arc& arc) {
+ head.push_back(arc);
+ }
+
+ /// \brief Erase the first arc of the path
+ void eraseFront() {
+ if (!head.empty()) {
+ head.pop_back();
+ } else {
+ head.clear();
+ int halfsize = tail.size() / 2;
+ head.resize(halfsize);
+ std::copy(tail.begin() + 1, tail.begin() + halfsize + 1,
+ head.rbegin());
+ std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin());
+ tail.resize(tail.size() - halfsize - 1);
+ }
+ }
+
+ /// \brief Gives back the last arc of the path
+ const Arc& back() const {
+ return tail.empty() ? head.front() : tail.back();
+ }
+
+ /// \brief Add a new arc behind the current path
+ void addBack(const Arc& arc) {
+ tail.push_back(arc);
+ }
+
+ /// \brief Erase the last arc of the path
+ void eraseBack() {
+ if (!tail.empty()) {
+ tail.pop_back();
+ } else {
+ int halfsize = head.size() / 2;
+ tail.resize(halfsize);
+ std::copy(head.begin() + 1, head.begin() + halfsize + 1,
+ tail.rbegin());
+ std::copy(head.begin() + halfsize + 1, head.end(), head.begin());
+ head.resize(head.size() - halfsize - 1);
+ }
+ }
+
+
+
+ typedef True BuildTag;
+
+ template <typename CPath>
+ void build(const CPath& path) {
+ int len = path.length();
+ tail.reserve(len);
+ for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
+ tail.push_back(it);
+ }
+ }
+
+ template <typename CPath>
+ void buildRev(const CPath& path) {
+ int len = path.length();
+ head.reserve(len);
+ for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
+ head.push_back(it);
+ }
+ }
+
+ protected:
+ typedef std::vector<Arc> Container;
+ Container head, tail;
+
+ };
+
+ /// \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 in the path and the zero length paths
+ /// cannot store the source.
+ ///
+ /// This implementation is a just back insertable and erasable path
+ /// type. It can be indexed in O(1) time. The back insertion and
+ /// erasure is amortized O(1) time. This implementation is faster
+ /// then the \c Path type because it use just one vector for the
+ /// arcs.
+ template <typename _Digraph>
+ class SimplePath {
+ public:
+
+ typedef _Digraph Digraph;
+ typedef typename Digraph::Arc Arc;
+
+ /// \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 Returns whether the path is empty.
+ bool empty() const { return data.empty(); }
+
+ /// \brief Resets the path to an empty path.
+ void clear() { data.clear(); }
+
+ /// \brief Gives back the nth arc.
+ ///
+ /// \pre n is in the [0..length() - 1] 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 Gives back the first arc of the path.
+ const Arc& front() const {
+ return data.front();
+ }
+
+ /// \brief Gives back 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.
+ /// \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 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 _Digraph>
+ class ListPath {
+ public:
+
+ typedef _Digraph 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 Gives back the nth arc.
+ ///
+ /// Gives back the nth arc in O(n) time.
+ /// \pre n is in the [0..length() - 1] 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 Returns whether the path is empty.
+ bool empty() const { return first == 0; }
+
+ /// \brief Resets the path to an empty path.
+ void clear() {
+ while (first != 0) {
+ last = first->next;
+ alloc.destroy(first);
+ alloc.deallocate(first, 1);
+ first = last;
+ }
+ }
+
+ /// \brief Gives back 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 Gives back 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 Splicing the given path to the current path.
+ ///
+ /// It splices the \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 Splicing the given path to the current path.
+ ///
+ /// It splices the \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 Splicing the given 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 Spliting the current path.
+ ///
+ /// It splits the current path into two parts. The part before \c
+ /// it iterator will remain in the current path and the part from
+ /// the it will put into the \c tpath. If the \c tpath had arcs
+ /// before the operation they will be removed first. The time
+ /// complexity of this function is O(1) plus the clearing of \c
+ /// tpath. If the \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.
+ /// \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 in the path and the zero length paths
+ /// cannot store the source.
+ ///
+ /// This implementation is completly static, so it cannot be
+ /// modified exclude the assign an other path. It is intented to be
+ /// used when you want to store a large number of paths because it is
+ /// the most memory efficient path type in the lemon.
+ template <typename _Digraph>
+ class StaticPath {
+ public:
+
+ typedef _Digraph 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 with any other path type. It just
+ /// makes a copy of the given path.
+ 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 initialized with any other path type. It just
+ /// 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 Gives back the nth arc.
+ ///
+ /// \pre n is in the [0..length() - 1] range
+ const Arc& nth(int n) const {
+ return arcs[n];
+ }
+
+ /// \brief Initializes arc iterator to point to the nth arc.
+ ArcIt nthIt(int n) const {
+ return ArcIt(*this, n);
+ }
+
+ /// \brief Gives back the length of the path.
+ int length() const { return len; }
+
+ /// \brief Returns true when the path is empty.
+ int empty() const { return len == 0; }
+
+ /// \break Erase all arc in the digraph.
+ void clear() {
+ len = 0;
+ if (arcs) delete[] arcs;
+ arcs = 0;
+ }
+
+ /// \brief Gives back the first arc of the path.
+ const Arc& front() const {
+ return arcs[0];
+ }
+
+ /// \brief Gives back 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
diff -r 6ec5dbed8f18 -r b55e501a90ee lemon/path_utils.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/path_utils.h Thu Jan 24 11:31:19 2008 +0000
@@ -0,0 +1,204 @@
+/* -*- 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_UTILS_H
+#define LEMON_PATH_UTILS_H
+
+#include <lemon/concepts/path.h>
+
+namespace lemon {
+
+ namespace _path_bits {
+
+ template <typename Path, typename Enable = void>
+ struct RevTagIndicator {
+ static const bool value = false;
+ };
+
+ template <typename Digraph>
+ struct RevTagIndicator<
+ Digraph,
+ typename enable_if<typename Digraph::RevTag, void>::type
+ > {
+ static const bool value = true;
+ };
+
+ template <typename Target, typename Source,
+ typename BuildEnable = void, typename RevEnable = void>
+ struct PathCopySelector {
+ 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, typename BuildEnable>
+ struct PathCopySelector<
+ Target, Source, BuildEnable,
+ typename enable_if<typename Source::RevPathTag, void>::type> {
+ 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, typename RevEnable>
+ struct PathCopySelector<
+ Target, Source,
+ typename enable_if<typename Target::BuildTag, void>::type, RevEnable> {
+ static void copy(Target& target, const Source& source) {
+ target.clear();
+ target.build(source);
+ }
+ };
+
+ template <typename Target, typename Source>
+ struct PathCopySelector<
+ Target, Source,
+ typename enable_if<typename Target::BuildTag, void>::type,
+ typename enable_if<typename Source::RevPathTag, void>::type> {
+ static void copy(Target& target, const Source& source) {
+ target.clear();
+ target.buildRev(source);
+ }
+ };
+
+ }
+
+
+ /// \brief Make of copy of a path.
+ ///
+ /// Make of 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 Checks the path's consistency.
+ ///
+ /// Checks that each arc's target is the next's source.
+ ///
+ 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 Gives back the source of the path
+ ///
+ /// Gives back the source of the path.
+ template <typename Digraph, typename Path>
+ typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
+ return digraph.source(path.front());
+ }
+
+ /// \brief Gives back the target of the path
+ ///
+ /// Gives back the target of the path.
+ template <typename Digraph, typename Path>
+ typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
+ return digraph.target(path.back());
+ }
+
+ /// \brief Class which helps to iterate the nodes of a path
+ ///
+ /// 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 node.
+ ///
+ /// This class implements the node iterator of a path structure. To
+ /// provide this feature, the underlying digraph should be given 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);
+ }
+
+ };
+
+}
+
+#endif
diff -r 6ec5dbed8f18 -r b55e501a90ee test/Makefile.am
--- a/test/Makefile.am Wed Jan 23 16:26:41 2008 +0100
+++ b/test/Makefile.am Thu Jan 24 11:31:19 2008 +0000
@@ -11,6 +11,7 @@
test/dim_test \
test/graph_test \
test/random_test \
+ test/path_test \
test/test_tools_fail \
test/test_tools_pass
@@ -20,6 +21,7 @@
test_digraph_test_SOURCES = test/digraph_test.cc
test_dim_test_SOURCES = test/dim_test.cc
test_graph_test_SOURCES = test/graph_test.cc
+test_path_test_SOURCES = test/path_test.cc
test_random_test_SOURCES = test/random_test.cc
test_test_tools_fail_SOURCES = test/test_tools_fail.cc
test_test_tools_pass_SOURCES = test/test_tools_pass.cc
diff -r 6ec5dbed8f18 -r b55e501a90ee test/path_test.cc
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/test/path_test.cc Thu Jan 24 11:31:19 2008 +0000
@@ -0,0 +1,44 @@
+/* -*- 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.
+ *
+ */
+
+#include <string>
+#include <iostream>
+
+#include <lemon/concepts/path.h>
+#include <lemon/concepts/digraph.h>
+
+#include <lemon/path.h>
+#include <lemon/list_graph.h>
+
+#include "test_tools.h"
+
+using namespace std;
+using namespace lemon;
+
+void check_concepts() {
+ checkConcept<concepts::Path<ListDigraph>, concepts::Path<ListDigraph> >();
+ checkConcept<concepts::Path<ListDigraph>, Path<ListDigraph> >();
+ checkConcept<concepts::Path<ListDigraph>, SimplePath<ListDigraph> >();
+ checkConcept<concepts::Path<ListDigraph>, StaticPath<ListDigraph> >();
+ checkConcept<concepts::Path<ListDigraph>, ListPath<ListDigraph> >();
+}
+
+int main() {
+ check_concepts();
+ return 0;
+}