deba@57: /* -*- C++ -*- deba@57: * deba@57: * This file is a part of LEMON, a generic C++ optimization library deba@57: * alpar@107: * Copyright (C) 2003-2008 deba@57: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@57: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@57: * deba@57: * Permission to use, modify and distribute this software is granted deba@57: * provided that this copyright notice appears in all copies. For deba@57: * precise terms see the accompanying LICENSE file. deba@57: * deba@57: * This software is provided "AS IS" with no warranty of any kind, deba@57: * express or implied, and with no claim as to its suitability for any deba@57: * purpose. deba@57: * deba@57: */ deba@57: deba@57: ///\ingroup graph_concepts deba@57: ///\file deba@57: ///\brief The concept of Undirected Graphs. deba@57: deba@57: #ifndef LEMON_CONCEPT_GRAPH_H deba@57: #define LEMON_CONCEPT_GRAPH_H deba@57: deba@57: #include deba@57: #include deba@57: #include deba@57: deba@57: namespace lemon { deba@57: namespace concepts { deba@57: deba@57: /// \ingroup graph_concepts deba@57: /// deba@57: /// \brief Class describing the concept of Undirected Graphs. deba@57: /// deba@57: /// This class describes the common interface of all Undirected deba@57: /// Graphs. deba@57: /// deba@57: /// As all concept describing classes it provides only interface deba@57: /// without any sensible implementation. So any algorithm for deba@57: /// undirected graph should compile with this class, but it will not deba@57: /// run properly, of course. deba@57: /// deba@57: /// The LEMON undirected graphs also fulfill the concept of deba@57: /// directed graphs (\ref lemon::concepts::Digraph "Digraph deba@57: /// Concept"). Each edges can be seen as two opposite deba@57: /// directed arc and consequently the undirected graph can be deba@57: /// seen as the direceted graph of these directed arcs. The deba@57: /// Graph has the Edge inner class for the edges and deba@57: /// the Arc type for the directed arcs. The Arc type is deba@57: /// convertible to Edge or inherited from it so from a directed deba@57: /// arc we can get the represented edge. deba@57: /// deba@57: /// In the sense of the LEMON each edge has a default deba@57: /// direction (it should be in every computer implementation, deba@57: /// because the order of edge's nodes defines an deba@57: /// orientation). With the default orientation we can define that deba@57: /// the directed arc is forward or backward directed. With the \c deba@57: /// direction() and \c direct() function we can get the direction deba@57: /// of the directed arc and we can direct an edge. deba@57: /// deba@57: /// The EdgeIt is an iterator for the edges. We can use deba@57: /// the EdgeMap to map values for the edges. The InArcIt and deba@57: /// OutArcIt iterates on the same edges but with opposite deba@78: /// direction. The IncEdgeIt iterates also on the same edges deba@57: /// as the OutArcIt and InArcIt but it is not convertible to Arc just deba@57: /// to Edge. deba@57: class Graph { deba@57: public: deba@57: /// \brief The undirected graph should be tagged by the deba@57: /// UndirectedTag. deba@57: /// deba@57: /// The undirected graph should be tagged by the UndirectedTag. This deba@57: /// tag helps the enable_if technics to make compile time deba@57: /// specializations for undirected graphs. deba@57: typedef True UndirectedTag; deba@57: deba@57: /// \brief The base type of node iterators, deba@57: /// or in other words, the trivial node iterator. deba@57: /// deba@57: /// This is the base type of each node iterator, deba@57: /// thus each kind of node iterator converts to this. deba@57: /// More precisely each kind of node iterator should be inherited deba@57: /// from the trivial node iterator. deba@57: class Node { deba@57: public: deba@57: /// Default constructor deba@57: deba@57: /// @warning The default constructor sets the iterator deba@57: /// to an undefined value. deba@57: Node() { } deba@57: /// Copy constructor. deba@57: deba@57: /// Copy constructor. deba@57: /// deba@57: Node(const Node&) { } deba@57: deba@57: /// Invalid constructor \& conversion. deba@57: deba@57: /// This constructor initializes the iterator to be invalid. deba@57: /// \sa Invalid for more details. deba@57: Node(Invalid) { } deba@57: /// Equality operator deba@57: deba@57: /// Two iterators are equal if and only if they point to the deba@57: /// same object or both are invalid. deba@57: bool operator==(Node) const { return true; } deba@57: deba@57: /// Inequality operator deba@57: deba@57: /// \sa operator==(Node n) deba@57: /// deba@57: bool operator!=(Node) const { return true; } deba@57: deba@57: /// Artificial ordering operator. deba@57: deba@57: /// To allow the use of graph descriptors as key type in std::map or deba@57: /// similar associative container we require this. deba@57: /// deba@57: /// \note This operator only have to define some strict ordering of deba@57: /// the items; this order has nothing to do with the iteration deba@57: /// ordering of the items. deba@57: bool operator<(Node) const { return false; } deba@57: deba@57: }; deba@57: deba@57: /// This iterator goes through each node. deba@57: deba@57: /// This iterator goes through each node. deba@57: /// Its usage is quite simple, for example you can count the number deba@57: /// of nodes in graph \c g of type \c Graph like this: deba@57: ///\code deba@57: /// int count=0; deba@57: /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count; deba@57: ///\endcode deba@57: class NodeIt : public Node { deba@57: public: deba@57: /// Default constructor deba@57: deba@57: /// @warning The default constructor sets the iterator deba@57: /// to an undefined value. deba@57: NodeIt() { } deba@57: /// Copy constructor. deba@57: deba@57: /// Copy constructor. deba@57: /// deba@57: NodeIt(const NodeIt& n) : Node(n) { } deba@57: /// Invalid constructor \& conversion. deba@57: deba@57: /// Initialize the iterator to be invalid. deba@57: /// \sa Invalid for more details. deba@57: NodeIt(Invalid) { } deba@57: /// Sets the iterator to the first node. deba@57: deba@57: /// Sets the iterator to the first node of \c g. deba@57: /// deba@57: NodeIt(const Graph&) { } deba@57: /// Node -> NodeIt conversion. deba@57: deba@57: /// Sets the iterator to the node of \c the graph pointed by deba@57: /// the trivial iterator. deba@57: /// This feature necessitates that each time we deba@57: /// iterate the arc-set, the iteration order is the same. deba@57: NodeIt(const Graph&, const Node&) { } deba@57: /// Next node. deba@57: deba@57: /// Assign the iterator to the next node. deba@57: /// deba@57: NodeIt& operator++() { return *this; } deba@57: }; deba@57: deba@57: deba@57: /// The base type of the edge iterators. deba@57: deba@57: /// The base type of the edge iterators. deba@57: /// deba@57: class Edge { deba@57: public: deba@57: /// Default constructor deba@57: deba@57: /// @warning The default constructor sets the iterator deba@57: /// to an undefined value. deba@57: Edge() { } deba@57: /// Copy constructor. deba@57: deba@57: /// Copy constructor. deba@57: /// deba@57: Edge(const Edge&) { } deba@57: /// Initialize the iterator to be invalid. deba@57: deba@57: /// Initialize the iterator to be invalid. deba@57: /// deba@57: Edge(Invalid) { } deba@57: /// Equality operator deba@57: deba@57: /// Two iterators are equal if and only if they point to the deba@57: /// same object or both are invalid. deba@57: bool operator==(Edge) const { return true; } deba@57: /// Inequality operator deba@57: deba@57: /// \sa operator==(Edge n) deba@57: /// deba@57: bool operator!=(Edge) const { return true; } deba@57: deba@57: /// Artificial ordering operator. deba@57: deba@57: /// To allow the use of graph descriptors as key type in std::map or deba@57: /// similar associative container we require this. deba@57: /// deba@57: /// \note This operator only have to define some strict ordering of deba@57: /// the items; this order has nothing to do with the iteration deba@57: /// ordering of the items. deba@57: bool operator<(Edge) const { return false; } deba@57: }; deba@57: deba@57: /// This iterator goes through each edge. deba@57: deba@57: /// This iterator goes through each edge of a graph. deba@57: /// Its usage is quite simple, for example you can count the number deba@57: /// of edges in a graph \c g of type \c Graph as follows: deba@57: ///\code deba@57: /// int count=0; deba@57: /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; deba@57: ///\endcode deba@57: class EdgeIt : public Edge { deba@57: public: deba@57: /// Default constructor deba@57: deba@57: /// @warning The default constructor sets the iterator deba@57: /// to an undefined value. deba@57: EdgeIt() { } deba@57: /// Copy constructor. deba@57: deba@57: /// Copy constructor. deba@57: /// deba@57: EdgeIt(const EdgeIt& e) : Edge(e) { } deba@57: /// Initialize the iterator to be invalid. deba@57: deba@57: /// Initialize the iterator to be invalid. deba@57: /// deba@57: EdgeIt(Invalid) { } deba@57: /// This constructor sets the iterator to the first edge. deba@57: deba@57: /// This constructor sets the iterator to the first edge. deba@57: EdgeIt(const Graph&) { } deba@57: /// Edge -> EdgeIt conversion deba@57: deba@57: /// Sets the iterator to the value of the trivial iterator. deba@57: /// This feature necessitates that each time we deba@57: /// iterate the edge-set, the iteration order is the deba@57: /// same. deba@57: EdgeIt(const Graph&, const Edge&) { } deba@57: /// Next edge deba@57: deba@57: /// Assign the iterator to the next edge. deba@57: EdgeIt& operator++() { return *this; } deba@57: }; deba@57: deba@57: /// \brief This iterator goes trough the incident undirected deba@57: /// arcs of a node. deba@57: /// deba@57: /// This iterator goes trough the incident edges deba@57: /// of a certain node of a graph. You should assume that the deba@57: /// loop arcs will be iterated twice. deba@57: /// deba@57: /// Its usage is quite simple, for example you can compute the deba@57: /// degree (i.e. count the number of incident arcs of a node \c n deba@57: /// in graph \c g of type \c Graph as follows. deba@57: /// deba@57: ///\code deba@57: /// int count=0; deba@78: /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count; deba@57: ///\endcode deba@78: class IncEdgeIt : public Edge { deba@57: public: deba@57: /// Default constructor deba@57: deba@57: /// @warning The default constructor sets the iterator deba@57: /// to an undefined value. deba@78: IncEdgeIt() { } deba@57: /// Copy constructor. deba@57: deba@57: /// Copy constructor. deba@57: /// deba@78: IncEdgeIt(const IncEdgeIt& e) : Edge(e) { } deba@57: /// Initialize the iterator to be invalid. deba@57: deba@57: /// Initialize the iterator to be invalid. deba@57: /// deba@78: IncEdgeIt(Invalid) { } deba@57: /// This constructor sets the iterator to first incident arc. deba@57: deba@57: /// This constructor set the iterator to the first incident arc of deba@57: /// the node. deba@78: IncEdgeIt(const Graph&, const Node&) { } deba@78: /// Edge -> IncEdgeIt conversion deba@57: deba@57: /// Sets the iterator to the value of the trivial iterator \c e. deba@57: /// This feature necessitates that each time we deba@57: /// iterate the arc-set, the iteration order is the same. deba@78: IncEdgeIt(const Graph&, const Edge&) { } deba@57: /// Next incident arc deba@57: deba@57: /// Assign the iterator to the next incident arc deba@57: /// of the corresponding node. deba@78: IncEdgeIt& operator++() { return *this; } deba@57: }; deba@57: deba@57: /// The directed arc type. deba@57: deba@57: /// The directed arc type. It can be converted to the deba@57: /// edge or it should be inherited from the undirected deba@57: /// arc. deba@57: class Arc : public Edge { deba@57: public: deba@57: /// Default constructor deba@57: deba@57: /// @warning The default constructor sets the iterator deba@57: /// to an undefined value. deba@57: Arc() { } deba@57: /// Copy constructor. deba@57: deba@57: /// Copy constructor. deba@57: /// deba@57: Arc(const Arc& e) : Edge(e) { } deba@57: /// Initialize the iterator to be invalid. deba@57: deba@57: /// Initialize the iterator to be invalid. deba@57: /// deba@57: Arc(Invalid) { } deba@57: /// Equality operator deba@57: deba@57: /// Two iterators are equal if and only if they point to the deba@57: /// same object or both are invalid. deba@57: bool operator==(Arc) const { return true; } deba@57: /// Inequality operator deba@57: deba@57: /// \sa operator==(Arc n) deba@57: /// deba@57: bool operator!=(Arc) const { return true; } deba@57: deba@57: /// Artificial ordering operator. deba@57: deba@57: /// To allow the use of graph descriptors as key type in std::map or deba@57: /// similar associative container we require this. deba@57: /// deba@57: /// \note This operator only have to define some strict ordering of deba@57: /// the items; this order has nothing to do with the iteration deba@57: /// ordering of the items. deba@57: bool operator<(Arc) const { return false; } deba@57: deba@57: }; deba@57: /// This iterator goes through each directed arc. deba@57: deba@57: /// This iterator goes through each arc of a graph. deba@57: /// Its usage is quite simple, for example you can count the number deba@57: /// of arcs in a graph \c g of type \c Graph as follows: deba@57: ///\code deba@57: /// int count=0; deba@57: /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count; deba@57: ///\endcode deba@57: class ArcIt : public Arc { deba@57: public: deba@57: /// Default constructor deba@57: deba@57: /// @warning The default constructor sets the iterator deba@57: /// to an undefined value. deba@57: ArcIt() { } deba@57: /// Copy constructor. deba@57: deba@57: /// Copy constructor. deba@57: /// deba@57: ArcIt(const ArcIt& e) : Arc(e) { } deba@57: /// Initialize the iterator to be invalid. deba@57: deba@57: /// Initialize the iterator to be invalid. deba@57: /// deba@57: ArcIt(Invalid) { } deba@57: /// This constructor sets the iterator to the first arc. deba@57: deba@57: /// This constructor sets the iterator to the first arc of \c g. deba@57: ///@param g the graph deba@57: ArcIt(const Graph &g) { ignore_unused_variable_warning(g); } deba@57: /// Arc -> ArcIt conversion deba@57: deba@57: /// Sets the iterator to the value of the trivial iterator \c e. deba@57: /// This feature necessitates that each time we deba@57: /// iterate the arc-set, the iteration order is the same. deba@57: ArcIt(const Graph&, const Arc&) { } deba@57: ///Next arc deba@57: deba@57: /// Assign the iterator to the next arc. deba@57: ArcIt& operator++() { return *this; } deba@57: }; deba@57: deba@57: /// This iterator goes trough the outgoing directed arcs of a node. deba@57: deba@57: /// This iterator goes trough the \e outgoing arcs of a certain node deba@57: /// of a graph. deba@57: /// Its usage is quite simple, for example you can count the number deba@57: /// of outgoing arcs of a node \c n deba@57: /// in graph \c g of type \c Graph as follows. deba@57: ///\code deba@57: /// int count=0; deba@57: /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count; deba@57: ///\endcode deba@57: deba@57: class OutArcIt : public Arc { deba@57: public: deba@57: /// Default constructor deba@57: deba@57: /// @warning The default constructor sets the iterator deba@57: /// to an undefined value. deba@57: OutArcIt() { } deba@57: /// Copy constructor. deba@57: deba@57: /// Copy constructor. deba@57: /// deba@57: OutArcIt(const OutArcIt& e) : Arc(e) { } deba@57: /// Initialize the iterator to be invalid. deba@57: deba@57: /// Initialize the iterator to be invalid. deba@57: /// deba@57: OutArcIt(Invalid) { } deba@57: /// This constructor sets the iterator to the first outgoing arc. deba@57: deba@57: /// This constructor sets the iterator to the first outgoing arc of deba@57: /// the node. deba@57: ///@param n the node deba@57: ///@param g the graph deba@57: OutArcIt(const Graph& n, const Node& g) { deba@57: ignore_unused_variable_warning(n); deba@57: ignore_unused_variable_warning(g); deba@57: } deba@57: /// Arc -> OutArcIt conversion deba@57: deba@57: /// Sets the iterator to the value of the trivial iterator. deba@57: /// This feature necessitates that each time we deba@57: /// iterate the arc-set, the iteration order is the same. deba@57: OutArcIt(const Graph&, const Arc&) { } deba@57: ///Next outgoing arc deba@57: deba@57: /// Assign the iterator to the next deba@57: /// outgoing arc of the corresponding node. deba@57: OutArcIt& operator++() { return *this; } deba@57: }; deba@57: deba@57: /// This iterator goes trough the incoming directed arcs of a node. deba@57: deba@57: /// This iterator goes trough the \e incoming arcs of a certain node deba@57: /// of a graph. deba@57: /// Its usage is quite simple, for example you can count the number deba@57: /// of outgoing arcs of a node \c n deba@57: /// in graph \c g of type \c Graph as follows. deba@57: ///\code deba@57: /// int count=0; deba@57: /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count; deba@57: ///\endcode deba@57: deba@57: class InArcIt : public Arc { deba@57: public: deba@57: /// Default constructor deba@57: deba@57: /// @warning The default constructor sets the iterator deba@57: /// to an undefined value. deba@57: InArcIt() { } deba@57: /// Copy constructor. deba@57: deba@57: /// Copy constructor. deba@57: /// deba@57: InArcIt(const InArcIt& e) : Arc(e) { } deba@57: /// Initialize the iterator to be invalid. deba@57: deba@57: /// Initialize the iterator to be invalid. deba@57: /// deba@57: InArcIt(Invalid) { } deba@57: /// This constructor sets the iterator to first incoming arc. deba@57: deba@57: /// This constructor set the iterator to the first incoming arc of deba@57: /// the node. deba@57: ///@param n the node deba@57: ///@param g the graph deba@57: InArcIt(const Graph& g, const Node& n) { deba@57: ignore_unused_variable_warning(n); deba@57: ignore_unused_variable_warning(g); deba@57: } deba@57: /// Arc -> InArcIt conversion deba@57: deba@57: /// Sets the iterator to the value of the trivial iterator \c e. deba@57: /// This feature necessitates that each time we deba@57: /// iterate the arc-set, the iteration order is the same. deba@57: InArcIt(const Graph&, const Arc&) { } deba@57: /// Next incoming arc deba@57: deba@57: /// Assign the iterator to the next inarc of the corresponding node. deba@57: /// deba@57: InArcIt& operator++() { return *this; } deba@57: }; deba@57: deba@57: /// \brief Read write map of the nodes to type \c T. deba@57: /// deba@57: /// ReadWrite map of the nodes to type \c T. deba@57: /// \sa Reference deba@57: template deba@57: class NodeMap : public ReadWriteMap< Node, T > deba@57: { deba@57: public: deba@57: deba@57: ///\e deba@57: NodeMap(const Graph&) { } deba@57: ///\e deba@57: NodeMap(const Graph&, T) { } deba@57: deba@57: ///Copy constructor deba@57: NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { } deba@57: ///Assignment operator deba@57: template deba@57: NodeMap& operator=(const CMap&) { deba@57: checkConcept, CMap>(); deba@57: return *this; deba@57: } deba@57: }; deba@57: deba@57: /// \brief Read write map of the directed arcs to type \c T. deba@57: /// deba@57: /// Reference map of the directed arcs to type \c T. deba@57: /// \sa Reference deba@57: template deba@57: class ArcMap : public ReadWriteMap deba@57: { deba@57: public: deba@57: deba@57: ///\e deba@57: ArcMap(const Graph&) { } deba@57: ///\e deba@57: ArcMap(const Graph&, T) { } deba@57: ///Copy constructor deba@57: ArcMap(const ArcMap& em) : ReadWriteMap(em) { } deba@57: ///Assignment operator deba@57: template deba@57: ArcMap& operator=(const CMap&) { deba@57: checkConcept, CMap>(); deba@57: return *this; deba@57: } deba@57: }; deba@57: deba@57: /// Read write map of the edges to type \c T. deba@57: deba@57: /// Reference map of the arcs to type \c T. deba@57: /// \sa Reference deba@57: template deba@57: class EdgeMap : public ReadWriteMap deba@57: { deba@57: public: deba@57: deba@57: ///\e deba@57: EdgeMap(const Graph&) { } deba@57: ///\e deba@57: EdgeMap(const Graph&, T) { } deba@57: ///Copy constructor deba@57: EdgeMap(const EdgeMap& em) : ReadWriteMap(em) {} deba@57: ///Assignment operator deba@57: template deba@57: EdgeMap& operator=(const CMap&) { deba@57: checkConcept, CMap>(); deba@57: return *this; deba@57: } deba@57: }; deba@57: deba@57: /// \brief Direct the given edge. deba@57: /// deba@57: /// Direct the given edge. The returned arc source deba@57: /// will be the given node. deba@57: Arc direct(const Edge&, const Node&) const { deba@57: return INVALID; deba@57: } deba@57: deba@57: /// \brief Direct the given edge. deba@57: /// deba@57: /// Direct the given edge. The returned arc deba@57: /// represents the given edge and the direction comes deba@57: /// from the bool parameter. The source of the edge and deba@57: /// the directed arc is the same when the given bool is true. deba@57: Arc direct(const Edge&, bool) const { deba@57: return INVALID; deba@57: } deba@57: deba@57: /// \brief Returns true if the arc has default orientation. deba@57: /// deba@57: /// Returns whether the given directed arc is same orientation as deba@57: /// the corresponding edge's default orientation. deba@57: bool direction(Arc) const { return true; } deba@57: deba@57: /// \brief Returns the opposite directed arc. deba@57: /// deba@57: /// Returns the opposite directed arc. deba@57: Arc oppositeArc(Arc) const { return INVALID; } deba@57: deba@57: /// \brief Opposite node on an arc deba@57: /// deba@57: /// \return the opposite of the given Node on the given Edge deba@57: Node oppositeNode(Node, Edge) const { return INVALID; } deba@57: deba@57: /// \brief First node of the edge. deba@57: /// deba@57: /// \return the first node of the given Edge. deba@57: /// deba@57: /// Naturally edges don't have direction and thus deba@57: /// don't have source and target node. But we use these two methods deba@57: /// to query the two nodes of the arc. The direction of the arc deba@57: /// which arises this way is called the inherent direction of the deba@57: /// edge, and is used to define the "default" direction deba@57: /// of the directed versions of the arcs. deba@57: /// \sa direction deba@57: Node u(Edge) const { return INVALID; } deba@57: deba@57: /// \brief Second node of the edge. deba@57: Node v(Edge) const { return INVALID; } deba@57: deba@57: /// \brief Source node of the directed arc. deba@57: Node source(Arc) const { return INVALID; } deba@57: deba@57: /// \brief Target node of the directed arc. deba@57: Node target(Arc) const { return INVALID; } deba@57: deba@61: /// \brief Returns the id of the node. deba@61: int id(Node) const { return -1; } deba@61: deba@61: /// \brief Returns the id of the edge. deba@61: int id(Edge) const { return -1; } deba@61: deba@61: /// \brief Returns the id of the arc. deba@61: int id(Arc) const { return -1; } deba@61: deba@61: /// \brief Returns the node with the given id. deba@61: /// deba@61: /// \pre The argument should be a valid node id in the graph. deba@61: Node nodeFromId(int) const { return INVALID; } deba@61: deba@61: /// \brief Returns the edge with the given id. deba@61: /// deba@61: /// \pre The argument should be a valid edge id in the graph. deba@61: Edge edgeFromId(int) const { return INVALID; } deba@61: deba@61: /// \brief Returns the arc with the given id. deba@61: /// deba@61: /// \pre The argument should be a valid arc id in the graph. deba@61: Arc arcFromId(int) const { return INVALID; } deba@61: deba@61: /// \brief Returns an upper bound on the node IDs. deba@61: int maxNodeId() const { return -1; } deba@61: deba@61: /// \brief Returns an upper bound on the edge IDs. deba@61: int maxEdgeId() const { return -1; } deba@61: deba@61: /// \brief Returns an upper bound on the arc IDs. deba@61: int maxArcId() const { return -1; } deba@61: deba@57: void first(Node&) const {} deba@57: void next(Node&) const {} deba@57: deba@57: void first(Edge&) const {} deba@57: void next(Edge&) const {} deba@57: deba@57: void first(Arc&) const {} deba@57: void next(Arc&) const {} deba@57: deba@57: void firstOut(Arc&, Node) const {} deba@57: void nextOut(Arc&) const {} deba@57: deba@57: void firstIn(Arc&, Node) const {} deba@57: void nextIn(Arc&) const {} deba@57: deba@57: void firstInc(Edge &, bool &, const Node &) const {} deba@57: void nextInc(Edge &, bool &) const {} deba@57: deba@61: // The second parameter is dummy. deba@61: Node fromId(int, Node) const { return INVALID; } deba@61: // The second parameter is dummy. deba@61: Edge fromId(int, Edge) const { return INVALID; } deba@61: // The second parameter is dummy. deba@61: Arc fromId(int, Arc) const { return INVALID; } deba@61: deba@61: // Dummy parameter. deba@61: int maxId(Node) const { return -1; } deba@61: // Dummy parameter. deba@61: int maxId(Edge) const { return -1; } deba@61: // Dummy parameter. deba@61: int maxId(Arc) const { return -1; } deba@61: deba@57: /// \brief Base node of the iterator deba@57: /// deba@57: /// Returns the base node (the source in this case) of the iterator deba@57: Node baseNode(OutArcIt e) const { deba@57: return source(e); deba@57: } deba@57: /// \brief Running node of the iterator deba@57: /// deba@57: /// Returns the running node (the target in this case) of the deba@57: /// iterator deba@57: Node runningNode(OutArcIt e) const { deba@57: return target(e); deba@57: } deba@57: deba@57: /// \brief Base node of the iterator deba@57: /// deba@57: /// Returns the base node (the target in this case) of the iterator deba@57: Node baseNode(InArcIt e) const { deba@57: return target(e); deba@57: } deba@57: /// \brief Running node of the iterator deba@57: /// deba@57: /// Returns the running node (the source in this case) of the deba@57: /// iterator deba@57: Node runningNode(InArcIt e) const { deba@57: return source(e); deba@57: } deba@57: deba@57: /// \brief Base node of the iterator deba@57: /// deba@57: /// Returns the base node of the iterator deba@78: Node baseNode(IncEdgeIt) const { deba@57: return INVALID; deba@57: } deba@57: deba@57: /// \brief Running node of the iterator deba@57: /// deba@57: /// Returns the running node of the iterator deba@78: Node runningNode(IncEdgeIt) const { deba@57: return INVALID; deba@57: } deba@57: deba@125: template deba@57: struct Constraints { deba@57: void constraints() { deba@125: checkConcept, _Graph>(); deba@125: checkConcept, _Graph>(); deba@125: checkConcept, _Graph>(); deba@57: } deba@57: }; deba@57: deba@57: }; deba@57: deba@57: } deba@57: deba@57: } deba@57: deba@57: #endif