klao@959: /* -*- C++ -*- klao@959: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@1956: * Copyright (C) 2003-2006 alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@1359: * (Egervary Research Group on Combinatorial Optimization, EGRES). klao@959: * klao@959: * Permission to use, modify and distribute this software is granted klao@959: * provided that this copyright notice appears in all copies. For klao@959: * precise terms see the accompanying LICENSE file. klao@959: * klao@959: * This software is provided "AS IS" with no warranty of any kind, klao@959: * express or implied, and with no claim as to its suitability for any klao@959: * purpose. klao@959: * klao@959: */ klao@959: klao@959: #ifndef LEMON_CONCEPT_GRAPH_H klao@959: #define LEMON_CONCEPT_GRAPH_H klao@959: klao@1030: ///\ingroup graph_concepts klao@959: ///\file klao@959: ///\brief Declaration of Graph. klao@959: deba@1993: #include deba@1993: #include klao@959: #include klao@959: #include deba@2126: #include klao@959: klao@959: namespace lemon { klao@959: namespace concept { deba@1136: alpar@1620: /// \addtogroup graph_concepts alpar@1620: /// @{ alpar@1620: alpar@2117: /// The directed graph concept alpar@2117: alpar@2117: /// This class describes the \ref concept "concept" of the alpar@2117: /// immutable directed graphs. deba@1136: /// alpar@2117: /// Note that actual graph implementation like @ref ListGraph or alpar@2117: /// @ref SmartGraph may have several additional functionality. deba@1136: /// alpar@2117: /// \sa concept deba@2111: class Graph { alpar@2132: private: alpar@2132: ///Graphs are \e not copy constructible. Use GraphCopy() instead. alpar@2132: alpar@2132: ///Graphs are \e not copy constructible. Use GraphCopy() instead. alpar@2132: /// alpar@2134: Graph(const Graph &) {}; alpar@2132: ///\brief Assignment of \ref Graph "Graph"s to another ones are alpar@2132: ///\e not allowed. Use GraphCopy() instead. alpar@2132: alpar@2132: ///Assignment of \ref Graph "Graph"s to another ones are alpar@2132: ///\e not allowed. Use GraphCopy() instead. alpar@2132: alpar@2133: void operator=(const Graph &) {} deba@1136: public: alpar@1448: ///\e alpar@1448: deba@1136: /// Defalult constructor. deba@1136: deba@1136: /// Defalult constructor. deba@1136: /// deba@2111: Graph() { } alpar@2128: /// Class for identifying a node of the graph deba@1136: alpar@2128: /// This class identifies a node of the graph. It also serves alpar@2128: /// as a base class of the node iterators, alpar@2128: /// thus they will convert to this type. deba@1136: class Node { deba@1136: public: ladanyi@1426: /// Default constructor deba@1136: ladanyi@1426: /// @warning The default constructor sets the iterator ladanyi@1426: /// to an undefined value. ladanyi@1426: Node() { } ladanyi@1426: /// Copy constructor. deba@1136: ladanyi@1426: /// Copy constructor. ladanyi@1426: /// ladanyi@1426: Node(const Node&) { } deba@1136: ladanyi@1426: /// Invalid constructor \& conversion. deba@1136: ladanyi@1426: /// This constructor initializes the iterator to be invalid. ladanyi@1426: /// \sa Invalid for more details. ladanyi@1426: Node(Invalid) { } ladanyi@1426: /// Equality operator deba@1136: ladanyi@1426: /// Two iterators are equal if and only if they point to the ladanyi@1426: /// same object or both are invalid. ladanyi@1426: bool operator==(Node) const { return true; } deba@1136: ladanyi@1426: /// Inequality operator ladanyi@1426: ladanyi@1426: /// \sa operator==(Node n) ladanyi@1426: /// ladanyi@1426: bool operator!=(Node) const { return true; } deba@1136: deba@1622: /// Artificial ordering operator. deba@1622: deba@1622: /// To allow the use of graph descriptors as key type in std::map or deba@1622: /// similar associative container we require this. deba@1622: /// deba@1622: /// \note This operator only have to define some strict ordering of deba@1622: /// the items; this order has nothing to do with the iteration deba@1622: /// ordering of the items. deba@1622: bool operator<(Node) const { return false; } deba@1622: deba@1136: }; deba@1136: deba@1136: /// This iterator goes through each node. deba@1136: deba@1136: /// This iterator goes through each node. deba@1136: /// Its usage is quite simple, for example you can count the number deba@1136: /// of nodes in graph \c g of type \c Graph like this: alpar@1946: ///\code deba@1136: /// int count=0; ladanyi@1426: /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count; alpar@1946: ///\endcode deba@1136: class NodeIt : public Node { deba@1136: public: ladanyi@1426: /// Default constructor deba@1136: ladanyi@1426: /// @warning The default constructor sets the iterator ladanyi@1426: /// to an undefined value. ladanyi@1426: NodeIt() { } ladanyi@1426: /// Copy constructor. ladanyi@1426: ladanyi@1426: /// Copy constructor. ladanyi@1426: /// ladanyi@1426: NodeIt(const NodeIt& n) : Node(n) { } ladanyi@1426: /// Invalid constructor \& conversion. deba@1136: ladanyi@1426: /// Initialize the iterator to be invalid. ladanyi@1426: /// \sa Invalid for more details. ladanyi@1426: NodeIt(Invalid) { } ladanyi@1426: /// Sets the iterator to the first node. deba@1136: ladanyi@1426: /// Sets the iterator to the first node of \c g. ladanyi@1426: /// deba@2111: NodeIt(const Graph&) { } ladanyi@1426: /// Node -> NodeIt conversion. deba@1136: deba@1470: /// Sets the iterator to the node of \c the graph pointed by deba@1470: /// the trivial iterator. ladanyi@1426: /// This feature necessitates that each time we ladanyi@1426: /// iterate the edge-set, the iteration order is the same. deba@2111: NodeIt(const Graph&, const Node&) { } ladanyi@1426: /// Next node. deba@1136: ladanyi@1426: /// Assign the iterator to the next node. ladanyi@1426: /// ladanyi@1426: NodeIt& operator++() { return *this; } deba@1136: }; deba@1136: deba@1136: alpar@2128: /// Class for identifying an edge of the graph deba@1136: alpar@2128: /// This class identifies an edge of the graph. It also serves alpar@2128: /// as a base class of the edge iterators, alpar@2128: /// thus they will convert to this type. deba@1136: class Edge { deba@1136: public: ladanyi@1426: /// Default constructor deba@1136: ladanyi@1426: /// @warning The default constructor sets the iterator ladanyi@1426: /// to an undefined value. ladanyi@1426: Edge() { } ladanyi@1426: /// Copy constructor. deba@1136: ladanyi@1426: /// Copy constructor. ladanyi@1426: /// ladanyi@1426: Edge(const Edge&) { } ladanyi@1426: /// Initialize the iterator to be invalid. deba@1136: ladanyi@1426: /// Initialize the iterator to be invalid. ladanyi@1426: /// ladanyi@1426: Edge(Invalid) { } ladanyi@1426: /// Equality operator deba@1136: ladanyi@1426: /// Two iterators are equal if and only if they point to the ladanyi@1426: /// same object or both are invalid. ladanyi@1426: bool operator==(Edge) const { return true; } ladanyi@1426: /// Inequality operator deba@1136: alpar@1620: /// \sa operator==(Edge n) ladanyi@1426: /// ladanyi@1426: bool operator!=(Edge) const { return true; } deba@1622: deba@1622: /// Artificial ordering operator. deba@1622: deba@1622: /// To allow the use of graph descriptors as key type in std::map or deba@1622: /// similar associative container we require this. deba@1622: /// deba@1622: /// \note This operator only have to define some strict ordering of deba@1622: /// the items; this order has nothing to do with the iteration deba@1622: /// ordering of the items. deba@1622: bool operator<(Edge) const { return false; } deba@1136: }; deba@1136: deba@1136: /// This iterator goes trough the outgoing edges of a node. deba@1136: deba@1136: /// This iterator goes trough the \e outgoing edges of a certain node deba@1136: /// of a graph. deba@1136: /// Its usage is quite simple, for example you can count the number deba@1136: /// of outgoing edges of a node \c n deba@1136: /// in graph \c g of type \c Graph as follows. alpar@1946: ///\code deba@1136: /// int count=0; deba@1136: /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count; alpar@1946: ///\endcode deba@1136: deba@1136: class OutEdgeIt : public Edge { deba@1136: public: ladanyi@1426: /// Default constructor deba@1136: ladanyi@1426: /// @warning The default constructor sets the iterator ladanyi@1426: /// to an undefined value. ladanyi@1426: OutEdgeIt() { } ladanyi@1426: /// Copy constructor. deba@1136: ladanyi@1426: /// Copy constructor. ladanyi@1426: /// ladanyi@1426: OutEdgeIt(const OutEdgeIt& e) : Edge(e) { } ladanyi@1426: /// Initialize the iterator to be invalid. deba@1136: ladanyi@1426: /// Initialize the iterator to be invalid. ladanyi@1426: /// ladanyi@1426: OutEdgeIt(Invalid) { } ladanyi@1426: /// This constructor sets the iterator to the first outgoing edge. deba@1136: ladanyi@1426: /// This constructor sets the iterator to the first outgoing edge of ladanyi@1426: /// the node. deba@2111: OutEdgeIt(const Graph&, const Node&) { } ladanyi@1426: /// Edge -> OutEdgeIt conversion deba@1136: deba@1470: /// Sets the iterator to the value of the trivial iterator. deba@1470: /// This feature necessitates that each time we ladanyi@1426: /// iterate the edge-set, the iteration order is the same. deba@2111: OutEdgeIt(const Graph&, const Edge&) { } ladanyi@1426: ///Next outgoing edge ladanyi@1426: ladanyi@1426: /// Assign the iterator to the next ladanyi@1426: /// outgoing edge of the corresponding node. ladanyi@1426: OutEdgeIt& operator++() { return *this; } deba@1136: }; deba@1136: deba@1136: /// This iterator goes trough the incoming edges of a node. deba@1136: deba@1136: /// This iterator goes trough the \e incoming edges of a certain node deba@1136: /// of a graph. deba@1136: /// Its usage is quite simple, for example you can count the number deba@1136: /// of outgoing edges of a node \c n deba@1136: /// in graph \c g of type \c Graph as follows. alpar@1946: ///\code deba@1136: /// int count=0; deba@1136: /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count; alpar@1946: ///\endcode deba@1136: deba@1136: class InEdgeIt : public Edge { deba@1136: public: ladanyi@1426: /// Default constructor deba@1136: ladanyi@1426: /// @warning The default constructor sets the iterator ladanyi@1426: /// to an undefined value. ladanyi@1426: InEdgeIt() { } ladanyi@1426: /// Copy constructor. deba@1136: ladanyi@1426: /// Copy constructor. ladanyi@1426: /// ladanyi@1426: InEdgeIt(const InEdgeIt& e) : Edge(e) { } ladanyi@1426: /// Initialize the iterator to be invalid. deba@1136: ladanyi@1426: /// Initialize the iterator to be invalid. ladanyi@1426: /// ladanyi@1426: InEdgeIt(Invalid) { } ladanyi@1426: /// This constructor sets the iterator to first incoming edge. deba@1136: ladanyi@1426: /// This constructor set the iterator to the first incoming edge of ladanyi@1426: /// the node. deba@2111: InEdgeIt(const Graph&, const Node&) { } ladanyi@1426: /// Edge -> InEdgeIt conversion deba@1136: ladanyi@1426: /// Sets the iterator to the value of the trivial iterator \c e. ladanyi@1426: /// This feature necessitates that each time we ladanyi@1426: /// iterate the edge-set, the iteration order is the same. deba@2111: InEdgeIt(const Graph&, const Edge&) { } ladanyi@1426: /// Next incoming edge deba@1136: ladanyi@1426: /// Assign the iterator to the next inedge of the corresponding node. ladanyi@1426: /// ladanyi@1426: InEdgeIt& operator++() { return *this; } deba@1136: }; deba@1136: /// This iterator goes through each edge. deba@1136: deba@1136: /// This iterator goes through each edge of a graph. deba@1136: /// Its usage is quite simple, for example you can count the number deba@1136: /// of edges in a graph \c g of type \c Graph as follows: alpar@1946: ///\code deba@1136: /// int count=0; deba@1136: /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; alpar@1946: ///\endcode deba@1136: class EdgeIt : public Edge { deba@1136: public: ladanyi@1426: /// Default constructor deba@1136: ladanyi@1426: /// @warning The default constructor sets the iterator ladanyi@1426: /// to an undefined value. ladanyi@1426: EdgeIt() { } ladanyi@1426: /// Copy constructor. deba@1136: ladanyi@1426: /// Copy constructor. ladanyi@1426: /// ladanyi@1426: EdgeIt(const EdgeIt& e) : Edge(e) { } ladanyi@1426: /// Initialize the iterator to be invalid. deba@1136: ladanyi@1426: /// Initialize the iterator to be invalid. ladanyi@1426: /// ladanyi@1426: EdgeIt(Invalid) { } ladanyi@1426: /// This constructor sets the iterator to the first edge. deba@1136: ladanyi@1426: /// This constructor sets the iterator to the first edge of \c g. ladanyi@1426: ///@param g the graph deba@2111: EdgeIt(const Graph& g) { ignore_unused_variable_warning(g); } ladanyi@1426: /// Edge -> EdgeIt conversion deba@1136: ladanyi@1426: /// Sets the iterator to the value of the trivial iterator \c e. ladanyi@1426: /// This feature necessitates that each time we ladanyi@1426: /// iterate the edge-set, the iteration order is the same. deba@2111: EdgeIt(const Graph&, const Edge&) { } ladanyi@1426: ///Next edge ladanyi@1426: ladanyi@1426: /// Assign the iterator to the next edge. ladanyi@1426: EdgeIt& operator++() { return *this; } deba@1136: }; deba@1136: ///Gives back the target node of an edge. deba@1136: deba@1136: ///Gives back the target node of an edge. deba@1136: /// deba@1136: Node target(Edge) const { return INVALID; } deba@1136: ///Gives back the source node of an edge. deba@1136: deba@1136: ///Gives back the source node of an edge. deba@1136: /// deba@1136: Node source(Edge) const { return INVALID; } deba@1563: deba@1563: void first(Node&) const {} deba@1563: void next(Node&) const {} deba@1563: deba@1563: void first(Edge&) const {} deba@1563: void next(Edge&) const {} deba@1563: deba@1563: deba@1563: void firstIn(Edge&, const Node&) const {} deba@1563: void nextIn(Edge&) const {} deba@1563: deba@1563: void firstOut(Edge&, const Node&) const {} deba@1563: void nextOut(Edge&) const {} deba@1563: deba@1563: /// \brief The base node of the iterator. deba@1563: /// deba@1563: /// Gives back the base node of the iterator. deba@1627: /// It is always the target of the pointed edge. deba@1563: Node baseNode(const InEdgeIt&) const { return INVALID; } deba@1563: deba@1563: /// \brief The running node of the iterator. deba@1563: /// deba@1563: /// Gives back the running node of the iterator. deba@1627: /// It is always the source of the pointed edge. deba@1563: Node runningNode(const InEdgeIt&) const { return INVALID; } deba@1563: deba@1563: /// \brief The base node of the iterator. deba@1563: /// deba@1563: /// Gives back the base node of the iterator. deba@1627: /// It is always the source of the pointed edge. deba@1563: Node baseNode(const OutEdgeIt&) const { return INVALID; } deba@1563: deba@1563: /// \brief The running node of the iterator. deba@1563: /// deba@1563: /// Gives back the running node of the iterator. deba@1627: /// It is always the target of the pointed edge. deba@1563: Node runningNode(const OutEdgeIt&) const { return INVALID; } deba@1136: deba@1627: /// \brief The opposite node on the given edge. deba@1627: /// deba@1627: /// Gives back the opposite node on the given edge. deba@1627: Node oppositeNode(const Node&, const Edge&) const { return INVALID; } deba@1627: deba@1627: /// \brief Read write map of the nodes to type \c T. deba@1627: /// deba@1136: /// ReadWrite map of the nodes to type \c T. deba@1136: /// \sa Reference deba@1136: template deba@2121: class NodeMap : public ReadWriteMap< Node, T > { deba@1136: public: deba@1136: ladanyi@1426: ///\e deba@2111: NodeMap(const Graph&) { } ladanyi@1426: ///\e deba@2111: NodeMap(const Graph&, T) { } deba@1136: ladanyi@1426: ///Copy constructor ladanyi@1426: NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { } ladanyi@1426: ///Assignment operator deba@2121: template deba@2121: NodeMap& operator=(const CMap&) { deba@2121: checkConcept, CMap>(); deba@2121: return *this; deba@2121: } deba@1136: }; deba@1136: deba@1627: /// \brief Read write map of the edges to type \c T. deba@1627: /// deba@1627: /// Reference map of the edges to type \c T. deba@1136: /// \sa Reference deba@1136: template deba@2121: class EdgeMap : public ReadWriteMap { deba@1136: public: deba@1136: ladanyi@1426: ///\e deba@2111: EdgeMap(const Graph&) { } ladanyi@1426: ///\e deba@2111: EdgeMap(const Graph&, T) { } ladanyi@1426: ///Copy constructor ladanyi@1426: EdgeMap(const EdgeMap& em) : ReadWriteMap(em) { } ladanyi@1426: ///Assignment operator deba@2121: template deba@2121: EdgeMap& operator=(const CMap&) { deba@2121: checkConcept, CMap>(); deba@2121: return *this; deba@2121: } deba@1136: }; deba@1136: deba@2111: template deba@2121: struct Constraints { deba@2121: void constraints() { deba@2121: checkConcept, Graph>(); deba@2121: checkConcept, Graph>(); deba@2121: checkConcept, Graph>(); deba@2121: } deba@2121: }; deba@1136: deba@1136: }; deba@1136: klao@959: // @} klao@959: } //namespace concept klao@959: } //namespace lemon klao@959: klao@959: klao@959: klao@959: #endif // LEMON_CONCEPT_GRAPH_H