/* -*- C++ -*-
* src/lemon/concept/path.h - Part of LEMON, a generic C++ optimization library
*
* Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Combinatorial Optimization Research Group, 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.
#ifndef LEMON_CONCEPT_PATH_H
#define LEMON_CONCEPT_PATH_H
#include
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 GR The graph type in which the path is.
//!
//! In a sense, the path can be treated as a graph, for is 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
class Path {
public:
/// Type of the underlying graph.
typedef /*typename*/ GR Graph;
/// Edge type of the underlying graph.
typedef typename Graph::Edge GraphEdge;
/// Node type of the underlying graph.
typedef typename Graph::Node GraphNode;
class NodeIt;
class EdgeIt;
/// \param _G The graph in which the path is.
///
Path(const Graph &_G) {}
/// Length of the path.
size_t 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.
GraphNode/*It*/ head() const {return INVALID;}
/// \brief End point of the path.
///
/// End point of the path.
/// Returns INVALID if the path is empty.
GraphNode/*It*/ tail() const {return INVALID;}
/// \brief First NodeIt/EdgeIt.
///
/// Initializes node or edge iterator to point to the first
/// node or edge.
template
It& first(It &i) const { return i=It(*this); }
/// \brief The head of an edge.
///
/// Returns node iterator pointing to the head node of the
/// given edge iterator.
NodeIt head(const EdgeIt& e) const {return INVALID;}
/// \brief The tail of an edge.
///
/// Returns node iterator pointing to the tail node of the
/// given edge iterator.
NodeIt tail(const EdgeIt& e) const {return INVALID;}
/* Iterator classes */
/**
* \brief Iterator class to iterate on the edges of the paths
*
* \ingroup concept
* 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 &_p) {}
operator GraphEdge () const {}
/// Next edge
EdgeIt& operator++() {return *this;}
/// Comparison operator
bool operator==(const EdgeIt& e) const {return true;}
/// Comparison operator
bool operator!=(const EdgeIt& e) const {return true;}
// /// Comparison operator
// /// \todo It is not clear what is the "natural" ordering.
// bool operator<(const EdgeIt& e) const {}
};
/**
* \brief Iterator class to iterate on the nodes of the paths
*
* \ingroup concept
* 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 &_p) {}
///Conversion to Graph::Node
operator const GraphNode& () const {}
/// Next node
NodeIt& operator++() {return *this;}
/// Comparison operator
bool operator==(const NodeIt& e) const {return true;}
/// Comparison operator
bool operator!=(const NodeIt& e) const {return true;}
// /// Comparison operator
// /// \todo It is not clear what is the "natural" ordering.
// bool operator<(const NodeIt& e) const {}
};
friend class Builder;
/**
* \brief Class to build paths
*
* \ingroup concept
* 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:
Path &P;
///\param _P the path you want to fill in.
///
Builder(Path &_P) : P(_P) {}
/// 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 empry path with this functions.
/// (And you \em must \em not use it later).
/// \sa pushFront()
/// \sa pushBack()
void setStartNode(const GraphNode &) {}
///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 GraphEdge& e) {}
///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 GraphEdge& e) {}
///Commit the changes to the path.
void commit() {}
///Reserve (front) storage for the builder in advance.
///If you know an reasonable upper bound of 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 r) {}
///Reserve (back) storage for the builder in advance.
///If you know an reasonable upper bound of 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 r) {}
};
};
///@}
}
} // namespace lemon
#endif // LEMON_CONCEPT_PATH_H