source: lemon-0.x/lemon/concept/path.h @ 2247:269a0dcee70b

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2006
 * 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 graphs.
///
///\todo Iterators have obsolete style

#ifndef LEMON_CONCEPT_PATH_H
#define LEMON_CONCEPT_PATH_H

#include <lemon/bits/invalid.h>
#include <lemon/concept_check.h>

namespace lemon {
  namespace concept {
    /// \addtogroup concept
    /// @{


    //! \brief A skeleton structure for representing directed paths in a graph.
    //!
    //! A skeleton structure for representing directed paths in a graph.
    //! \param _Graph The graph type in which the path is.
    //!
    //! In a sense, the path can be treated as a graph, for it has \c NodeIt
    //! and \c EdgeIt with the same usage. These types converts to the \c Node
    //! and \c Edge of the original graph.
    template<typename _Graph>
    class Path {
    public:

      /// Type of the underlying graph.
      typedef _Graph Graph;
      /// Edge type of the underlying graph.
      typedef typename Graph::Edge Edge;
      /// Node type of the underlying graph.
      typedef typename Graph::Node Node;

      class NodeIt;
      class EdgeIt;

      /// \param _g The graph in which the path is.
      ///
      Path(const Graph &_g) {
        ignore_unused_variable_warning(_g);
      }

      /// Length of the path ie. the number of edges 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 Starting point of the path.
      ///
      /// Starting point of the path.
      /// Returns INVALID if the path is empty.
      Node target() const {return INVALID;}
      /// \brief End point of the path.
      ///
      /// End point of the path.
      /// Returns INVALID if the path is empty.
      Node source() const {return INVALID;}

      /// \brief The target of an edge.
      ///
      /// Returns node iterator pointing to the target node of the
      /// given edge iterator.
      NodeIt target(const EdgeIt&) const {return INVALID;}

      /// \brief The source of an edge.
      ///
      /// Returns node iterator pointing to the source node of the
      /// given edge iterator.
      NodeIt source(const EdgeIt&) const {return INVALID;}

      /// \brief Iterator class to iterate on the nodes of the paths
      ///
      /// This class is used to iterate on the nodes of the paths
      ///
      /// Of course it converts to Graph::Node.
      class NodeIt {
      public:
        /// Default constructor
        NodeIt() {}
        /// Invalid constructor
        NodeIt(Invalid) {}
        /// Constructor with starting point
        NodeIt(const Path &) {}

        ///Conversion to Graph::Node
        operator Node() const { return INVALID; }
        /// Next node
        NodeIt& operator++() {return *this;}

        /// Comparison operator
        bool operator==(const NodeIt&) const {return true;}
        /// Comparison operator
        bool operator!=(const NodeIt&) const {return true;}
        /// Comparison operator
        bool operator<(const NodeIt&) const {return false;}

      };

      /// \brief Iterator class to iterate on the edges of the paths
      ///
      /// This class is used to iterate on the edges of the paths
      ///
      /// Of course it converts to Graph::Edge
      class EdgeIt {
      public:
        /// Default constructor
        EdgeIt() {}
        /// Invalid constructor
        EdgeIt(Invalid) {}
        /// Constructor with starting point
        EdgeIt(const Path &) {}

        operator Edge() const { return INVALID; }

        /// Next edge
        EdgeIt& operator++() {return *this;}

        /// Comparison operator
        bool operator==(const EdgeIt&) const {return true;}
        /// Comparison operator
        bool operator!=(const EdgeIt&) const {return true;}
        /// Comparison operator
        bool operator<(const EdgeIt&) const {return false;}

      };


      friend class Builder;

      /// \brief Class to build paths
      ///
      /// This class is used to fill a path with edges.
      ///
      /// You can push new edges to the front and to the back of the path in
      /// arbitrary order then you should commit these changes to the graph.
      ///
      /// While the builder is active (after the first modifying
      /// operation and until the call of \ref commit()) the
      /// underlining Path is in a "transitional" state (operations on
      /// it have undefined result).
      class Builder {
      public:

        /// Constructor

        /// Constructor
        /// \param _path the path you want to fill in.
        ///

        Builder(Path &_path) { ignore_unused_variable_warning(_path); }

        /// Sets the starting node of the path.

        /// Sets the starting node of the path. Edge added to the path
        /// afterwards have to be incident to this node.
        /// You \em must start building an empty path with these functions.
        /// (And you \em must \em not use it later).
        /// \sa pushFront()
        /// \sa pushBack()
        void setStartNode(const Node &) {}

        ///Push a new edge to the front of the path

        ///Push a new edge to the front of the path.
        ///If the path is empty, you \em must call \ref setStartNode() before
        ///the first use of \ref pushFront().
        void pushFront(const Edge&) {}

        ///Push a new edge to the back of the path

        ///Push a new edge to the back of the path.
        ///If the path is empty, you \em must call \ref setStartNode() before
        ///the first use of \ref pushBack().
        void pushBack(const Edge&) {}

        ///Commit the changes to the path.

        ///Commit the changes to the path.
        ///
        void commit() {}

        ///Reserve (front) storage for the builder in advance.

        ///If you know a reasonable upper bound on the number of the edges
        ///to add to the front of the path,
        ///using this function you may speed up the building.
        void reserveFront(size_t) {}
        ///Reserve (back) storage for the builder in advance.

        ///If you know a reasonable upper bound on the number of the edges
        ///to add to the back of the path,
        ///using this function you may speed up the building.
        void reserveBack(size_t) {}
      };

      template <typename _Path>
      struct Constraints {
        void constraints() {
          typedef typename _Path::Node Node;
          typedef typename _Path::NodeIt NodeIt;
          typedef typename Graph::Node GraphNode;

          typedef typename _Path::Edge Edge;
          typedef typename _Path::EdgeIt EdgeIt;
          typedef typename Graph::Edge GraphEdge;

          typedef typename _Path::Builder Builder;

          path = _Path(graph);

          bool b = cpath.empty();
          int l = cpath.length();

          Node gn;
          Edge ge;
          gn = cpath.source();
          gn = cpath.target();

          NodeIt nit;
          EdgeIt eit(INVALID);
          nit = path.source(eit);
          nit = path.target(eit);
          
          nit = NodeIt();
          nit = NodeIt(cpath);
          nit = INVALID;
          gn = nit;
          ++nit;
          b = nit == nit;
          b = nit != nit;
          b = nit < nit;

          eit = EdgeIt();
          eit = EdgeIt(cpath);
          eit = INVALID;
          ge = eit;
          ++eit;
          b = eit == eit;
          b = eit != eit;
          b = eit < eit;

          size_t st = 0;

          Builder builder(path); 
          builder.setStartNode(gn);
          builder.pushFront(ge);
          builder.pushBack(ge);
          builder.commit();
          builder.reserveFront(st);
          builder.reserveBack(st);
          
          ignore_unused_variable_warning(l);
          ignore_unused_variable_warning(b);
        }

        const Graph& graph;
        const _Path& cpath;
        _Path& path;
      };

    };

  ///@}
  }

} // namespace lemon

#endif // LEMON_CONCEPT_PATH_H