lemon/concepts/digraph.h
changeset 216 6d7bfcf5b48e
parent 125 19e82bda606a
child 220 a5d8c039f218
equal deleted inserted replaced
3:4ba0ee04fedb 4:14a5089e7225
     1 /* -*- C++ -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2008
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
    44     ///
    44     ///
    45     /// \sa concept
    45     /// \sa concept
    46     class Digraph {
    46     class Digraph {
    47     private:
    47     private:
    48       ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
    48       ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
    49       
    49 
    50       ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
    50       ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
    51       ///
    51       ///
    52       Digraph(const Digraph &) {};
    52       Digraph(const Digraph &) {};
    53       ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
    53       ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
    54       ///\e not allowed. Use DigraphCopy() instead.
    54       ///\e not allowed. Use DigraphCopy() instead.
    55       
    55 
    56       ///Assignment of \ref Digraph "Digraph"s to another ones are
    56       ///Assignment of \ref Digraph "Digraph"s to another ones are
    57       ///\e not allowed.  Use DigraphCopy() instead.
    57       ///\e not allowed.  Use DigraphCopy() instead.
    58 
    58 
    59       void operator=(const Digraph &) {}
    59       void operator=(const Digraph &) {}
    60     public:
    60     public:
    93         /// Two iterators are equal if and only if they point to the
    93         /// Two iterators are equal if and only if they point to the
    94         /// same object or both are invalid.
    94         /// same object or both are invalid.
    95         bool operator==(Node) const { return true; }
    95         bool operator==(Node) const { return true; }
    96 
    96 
    97         /// Inequality operator
    97         /// Inequality operator
    98         
    98 
    99         /// \sa operator==(Node n)
    99         /// \sa operator==(Node n)
   100         ///
   100         ///
   101         bool operator!=(Node) const { return true; }
   101         bool operator!=(Node) const { return true; }
   102 
   102 
   103 	/// Artificial ordering operator.
   103         /// Artificial ordering operator.
   104 	
   104 
   105 	/// To allow the use of digraph descriptors as key type in std::map or
   105         /// To allow the use of digraph descriptors as key type in std::map or
   106 	/// similar associative container we require this.
   106         /// similar associative container we require this.
   107 	///
   107         ///
   108 	/// \note This operator only have to define some strict ordering of
   108         /// \note This operator only have to define some strict ordering of
   109 	/// the items; this order has nothing to do with the iteration
   109         /// the items; this order has nothing to do with the iteration
   110 	/// ordering of the items.
   110         /// ordering of the items.
   111 	bool operator<(Node) const { return false; }
   111         bool operator<(Node) const { return false; }
   112 
   112 
   113       };
   113       };
   114     
   114 
   115       /// This iterator goes through each node.
   115       /// This iterator goes through each node.
   116 
   116 
   117       /// This iterator goes through each node.
   117       /// This iterator goes through each node.
   118       /// Its usage is quite simple, for example you can count the number
   118       /// Its usage is quite simple, for example you can count the number
   119       /// of nodes in digraph \c g of type \c Digraph like this:
   119       /// of nodes in digraph \c g of type \c Digraph like this:
   127 
   127 
   128         /// @warning The default constructor sets the iterator
   128         /// @warning The default constructor sets the iterator
   129         /// to an undefined value.
   129         /// to an undefined value.
   130         NodeIt() { }
   130         NodeIt() { }
   131         /// Copy constructor.
   131         /// Copy constructor.
   132         
   132 
   133         /// Copy constructor.
   133         /// Copy constructor.
   134         ///
   134         ///
   135         NodeIt(const NodeIt& n) : Node(n) { }
   135         NodeIt(const NodeIt& n) : Node(n) { }
   136         /// Invalid constructor \& conversion.
   136         /// Invalid constructor \& conversion.
   137 
   137 
   143         /// Sets the iterator to the first node of \c g.
   143         /// Sets the iterator to the first node of \c g.
   144         ///
   144         ///
   145         NodeIt(const Digraph&) { }
   145         NodeIt(const Digraph&) { }
   146         /// Node -> NodeIt conversion.
   146         /// Node -> NodeIt conversion.
   147 
   147 
   148         /// Sets the iterator to the node of \c the digraph pointed by 
   148         /// Sets the iterator to the node of \c the digraph pointed by
   149 	/// the trivial iterator.
   149         /// the trivial iterator.
   150         /// This feature necessitates that each time we 
   150         /// This feature necessitates that each time we
   151         /// iterate the arc-set, the iteration order is the same.
   151         /// iterate the arc-set, the iteration order is the same.
   152         NodeIt(const Digraph&, const Node&) { }
   152         NodeIt(const Digraph&, const Node&) { }
   153         /// Next node.
   153         /// Next node.
   154 
   154 
   155         /// Assign the iterator to the next node.
   155         /// Assign the iterator to the next node.
   156         ///
   156         ///
   157         NodeIt& operator++() { return *this; }
   157         NodeIt& operator++() { return *this; }
   158       };
   158       };
   159     
   159 
   160     
   160 
   161       /// Class for identifying an arc of the digraph
   161       /// Class for identifying an arc of the digraph
   162 
   162 
   163       /// This class identifies an arc of the digraph. It also serves
   163       /// This class identifies an arc of the digraph. It also serves
   164       /// as a base class of the arc iterators,
   164       /// as a base class of the arc iterators,
   165       /// thus they will convert to this type.
   165       /// thus they will convert to this type.
   189 
   189 
   190         /// \sa operator==(Arc n)
   190         /// \sa operator==(Arc n)
   191         ///
   191         ///
   192         bool operator!=(Arc) const { return true; }
   192         bool operator!=(Arc) const { return true; }
   193 
   193 
   194 	/// Artificial ordering operator.
   194         /// Artificial ordering operator.
   195 	
   195 
   196 	/// To allow the use of digraph descriptors as key type in std::map or
   196         /// To allow the use of digraph descriptors as key type in std::map or
   197 	/// similar associative container we require this.
   197         /// similar associative container we require this.
   198 	///
   198         ///
   199 	/// \note This operator only have to define some strict ordering of
   199         /// \note This operator only have to define some strict ordering of
   200 	/// the items; this order has nothing to do with the iteration
   200         /// the items; this order has nothing to do with the iteration
   201 	/// ordering of the items.
   201         /// ordering of the items.
   202 	bool operator<(Arc) const { return false; }
   202         bool operator<(Arc) const { return false; }
   203       };
   203       };
   204     
   204 
   205       /// This iterator goes trough the outgoing arcs of a node.
   205       /// This iterator goes trough the outgoing arcs of a node.
   206 
   206 
   207       /// This iterator goes trough the \e outgoing arcs of a certain node
   207       /// This iterator goes trough the \e outgoing arcs of a certain node
   208       /// of a digraph.
   208       /// of a digraph.
   209       /// Its usage is quite simple, for example you can count the number
   209       /// Its usage is quite simple, for example you can count the number
   211       /// in digraph \c g of type \c Digraph as follows.
   211       /// in digraph \c g of type \c Digraph as follows.
   212       ///\code
   212       ///\code
   213       /// int count=0;
   213       /// int count=0;
   214       /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
   214       /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
   215       ///\endcode
   215       ///\endcode
   216     
   216 
   217       class OutArcIt : public Arc {
   217       class OutArcIt : public Arc {
   218       public:
   218       public:
   219         /// Default constructor
   219         /// Default constructor
   220 
   220 
   221         /// @warning The default constructor sets the iterator
   221         /// @warning The default constructor sets the iterator
   230 
   230 
   231         /// Initialize the iterator to be invalid.
   231         /// Initialize the iterator to be invalid.
   232         ///
   232         ///
   233         OutArcIt(Invalid) { }
   233         OutArcIt(Invalid) { }
   234         /// This constructor sets the iterator to the first outgoing arc.
   234         /// This constructor sets the iterator to the first outgoing arc.
   235     
   235 
   236         /// This constructor sets the iterator to the first outgoing arc of
   236         /// This constructor sets the iterator to the first outgoing arc of
   237         /// the node.
   237         /// the node.
   238         OutArcIt(const Digraph&, const Node&) { }
   238         OutArcIt(const Digraph&, const Node&) { }
   239         /// Arc -> OutArcIt conversion
   239         /// Arc -> OutArcIt conversion
   240 
   240 
   241         /// Sets the iterator to the value of the trivial iterator.
   241         /// Sets the iterator to the value of the trivial iterator.
   242 	/// This feature necessitates that each time we 
   242         /// This feature necessitates that each time we
   243         /// iterate the arc-set, the iteration order is the same.
   243         /// iterate the arc-set, the iteration order is the same.
   244         OutArcIt(const Digraph&, const Arc&) { }
   244         OutArcIt(const Digraph&, const Arc&) { }
   245         ///Next outgoing arc
   245         ///Next outgoing arc
   246         
   246 
   247         /// Assign the iterator to the next 
   247         /// Assign the iterator to the next
   248         /// outgoing arc of the corresponding node.
   248         /// outgoing arc of the corresponding node.
   249         OutArcIt& operator++() { return *this; }
   249         OutArcIt& operator++() { return *this; }
   250       };
   250       };
   251 
   251 
   252       /// This iterator goes trough the incoming arcs of a node.
   252       /// This iterator goes trough the incoming arcs of a node.
   277 
   277 
   278         /// Initialize the iterator to be invalid.
   278         /// Initialize the iterator to be invalid.
   279         ///
   279         ///
   280         InArcIt(Invalid) { }
   280         InArcIt(Invalid) { }
   281         /// This constructor sets the iterator to first incoming arc.
   281         /// This constructor sets the iterator to first incoming arc.
   282     
   282 
   283         /// This constructor set the iterator to the first incoming arc of
   283         /// This constructor set the iterator to the first incoming arc of
   284         /// the node.
   284         /// the node.
   285         InArcIt(const Digraph&, const Node&) { }
   285         InArcIt(const Digraph&, const Node&) { }
   286         /// Arc -> InArcIt conversion
   286         /// Arc -> InArcIt conversion
   287 
   287 
   288         /// Sets the iterator to the value of the trivial iterator \c e.
   288         /// Sets the iterator to the value of the trivial iterator \c e.
   289         /// This feature necessitates that each time we 
   289         /// This feature necessitates that each time we
   290         /// iterate the arc-set, the iteration order is the same.
   290         /// iterate the arc-set, the iteration order is the same.
   291         InArcIt(const Digraph&, const Arc&) { }
   291         InArcIt(const Digraph&, const Arc&) { }
   292         /// Next incoming arc
   292         /// Next incoming arc
   293 
   293 
   294         /// Assign the iterator to the next inarc of the corresponding node.
   294         /// Assign the iterator to the next inarc of the corresponding node.
   320 
   320 
   321         /// Initialize the iterator to be invalid.
   321         /// Initialize the iterator to be invalid.
   322         ///
   322         ///
   323         ArcIt(Invalid) { }
   323         ArcIt(Invalid) { }
   324         /// This constructor sets the iterator to the first arc.
   324         /// This constructor sets the iterator to the first arc.
   325     
   325 
   326         /// This constructor sets the iterator to the first arc of \c g.
   326         /// This constructor sets the iterator to the first arc of \c g.
   327         ///@param g the digraph
   327         ///@param g the digraph
   328         ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
   328         ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
   329         /// Arc -> ArcIt conversion
   329         /// Arc -> ArcIt conversion
   330 
   330 
   331         /// Sets the iterator to the value of the trivial iterator \c e.
   331         /// Sets the iterator to the value of the trivial iterator \c e.
   332         /// This feature necessitates that each time we 
   332         /// This feature necessitates that each time we
   333         /// iterate the arc-set, the iteration order is the same.
   333         /// iterate the arc-set, the iteration order is the same.
   334         ArcIt(const Digraph&, const Arc&) { } 
   334         ArcIt(const Digraph&, const Arc&) { }
   335         ///Next arc
   335         ///Next arc
   336         
   336 
   337         /// Assign the iterator to the next arc.
   337         /// Assign the iterator to the next arc.
   338         ArcIt& operator++() { return *this; }
   338         ArcIt& operator++() { return *this; }
   339       };
   339       };
   340       ///Gives back the target node of an arc.
   340       ///Gives back the target node of an arc.
   341 
   341 
   347       ///Gives back the source node of an arc.
   347       ///Gives back the source node of an arc.
   348       ///
   348       ///
   349       Node source(Arc) const { return INVALID; }
   349       Node source(Arc) const { return INVALID; }
   350 
   350 
   351       /// \brief Returns the ID of the node.
   351       /// \brief Returns the ID of the node.
   352       int id(Node) const { return -1; } 
   352       int id(Node) const { return -1; }
   353 
   353 
   354       /// \brief Returns the ID of the arc.
   354       /// \brief Returns the ID of the arc.
   355       int id(Arc) const { return -1; } 
   355       int id(Arc) const { return -1; }
   356 
   356 
   357       /// \brief Returns the node with the given ID.
   357       /// \brief Returns the node with the given ID.
   358       ///
   358       ///
   359       /// \pre The argument should be a valid node ID in the graph.
   359       /// \pre The argument should be a valid node ID in the graph.
   360       Node nodeFromId(int) const { return INVALID; } 
   360       Node nodeFromId(int) const { return INVALID; }
   361 
   361 
   362       /// \brief Returns the arc with the given ID.
   362       /// \brief Returns the arc with the given ID.
   363       ///
   363       ///
   364       /// \pre The argument should be a valid arc ID in the graph.
   364       /// \pre The argument should be a valid arc ID in the graph.
   365       Arc arcFromId(int) const { return INVALID; } 
   365       Arc arcFromId(int) const { return INVALID; }
   366 
   366 
   367       /// \brief Returns an upper bound on the node IDs.
   367       /// \brief Returns an upper bound on the node IDs.
   368       int maxNodeId() const { return -1; } 
   368       int maxNodeId() const { return -1; }
   369 
   369 
   370       /// \brief Returns an upper bound on the arc IDs.
   370       /// \brief Returns an upper bound on the arc IDs.
   371       int maxArcId() const { return -1; } 
   371       int maxArcId() const { return -1; }
   372 
   372 
   373       void first(Node&) const {}
   373       void first(Node&) const {}
   374       void next(Node&) const {}
   374       void next(Node&) const {}
   375 
   375 
   376       void first(Arc&) const {}
   376       void first(Arc&) const {}
   387       Node fromId(int, Node) const { return INVALID; }
   387       Node fromId(int, Node) const { return INVALID; }
   388       // The second parameter is dummy.
   388       // The second parameter is dummy.
   389       Arc fromId(int, Arc) const { return INVALID; }
   389       Arc fromId(int, Arc) const { return INVALID; }
   390 
   390 
   391       // Dummy parameter.
   391       // Dummy parameter.
   392       int maxId(Node) const { return -1; } 
   392       int maxId(Node) const { return -1; }
   393       // Dummy parameter.
   393       // Dummy parameter.
   394       int maxId(Arc) const { return -1; } 
   394       int maxId(Arc) const { return -1; }
   395 
   395 
   396       /// \brief The base node of the iterator.
   396       /// \brief The base node of the iterator.
   397       ///
   397       ///
   398       /// Gives back the base node of the iterator.
   398       /// Gives back the base node of the iterator.
   399       /// It is always the target of the pointed arc.
   399       /// It is always the target of the pointed arc.
   421       ///
   421       ///
   422       /// Gives back the opposite node on the given arc.
   422       /// Gives back the opposite node on the given arc.
   423       Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
   423       Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
   424 
   424 
   425       /// \brief Read write map of the nodes to type \c T.
   425       /// \brief Read write map of the nodes to type \c T.
   426       /// 
   426       ///
   427       /// ReadWrite map of the nodes to type \c T.
   427       /// ReadWrite map of the nodes to type \c T.
   428       /// \sa Reference
   428       /// \sa Reference
   429       template<class T> 
   429       template<class T>
   430       class NodeMap : public ReadWriteMap< Node, T > {
   430       class NodeMap : public ReadWriteMap< Node, T > {
   431       public:
   431       public:
   432 
   432 
   433         ///\e
   433         ///\e
   434         NodeMap(const Digraph&) { }
   434         NodeMap(const Digraph&) { }
   437 
   437 
   438         ///Copy constructor
   438         ///Copy constructor
   439         NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
   439         NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
   440         ///Assignment operator
   440         ///Assignment operator
   441         template <typename CMap>
   441         template <typename CMap>
   442         NodeMap& operator=(const CMap&) { 
   442         NodeMap& operator=(const CMap&) {
   443           checkConcept<ReadMap<Node, T>, CMap>();
   443           checkConcept<ReadMap<Node, T>, CMap>();
   444           return *this; 
   444           return *this;
   445         }
   445         }
   446       };
   446       };
   447 
   447 
   448       /// \brief Read write map of the arcs to type \c T.
   448       /// \brief Read write map of the arcs to type \c T.
   449       ///
   449       ///
   450       /// Reference map of the arcs to type \c T.
   450       /// Reference map of the arcs to type \c T.
   451       /// \sa Reference
   451       /// \sa Reference
   452       template<class T> 
   452       template<class T>
   453       class ArcMap : public ReadWriteMap<Arc,T> {
   453       class ArcMap : public ReadWriteMap<Arc,T> {
   454       public:
   454       public:
   455 
   455 
   456         ///\e
   456         ///\e
   457         ArcMap(const Digraph&) { }
   457         ArcMap(const Digraph&) { }
   459         ArcMap(const Digraph&, T) { }
   459         ArcMap(const Digraph&, T) { }
   460         ///Copy constructor
   460         ///Copy constructor
   461         ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
   461         ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
   462         ///Assignment operator
   462         ///Assignment operator
   463         template <typename CMap>
   463         template <typename CMap>
   464         ArcMap& operator=(const CMap&) { 
   464         ArcMap& operator=(const CMap&) {
   465           checkConcept<ReadMap<Arc, T>, CMap>();
   465           checkConcept<ReadMap<Arc, T>, CMap>();
   466           return *this; 
   466           return *this;
   467         }
   467         }
   468       };
   468       };
   469 
   469 
   470       template <typename _Digraph>
   470       template <typename _Digraph>
   471       struct Constraints {
   471       struct Constraints {
   472         void constraints() {
   472         void constraints() {
   473           checkConcept<IterableDigraphComponent<>, _Digraph>();
   473           checkConcept<IterableDigraphComponent<>, _Digraph>();
   474 	  checkConcept<IDableDigraphComponent<>, _Digraph>();
   474           checkConcept<IDableDigraphComponent<>, _Digraph>();
   475           checkConcept<MappableDigraphComponent<>, _Digraph>();
   475           checkConcept<MappableDigraphComponent<>, _Digraph>();
   476         }
   476         }
   477       };
   477       };
   478 
   478 
   479     };
   479     };
   480     
   480 
   481   } //namespace concepts  
   481   } //namespace concepts
   482 } //namespace lemon
   482 } //namespace lemon
   483 
   483 
   484 
   484 
   485 
   485 
   486 #endif // LEMON_CONCEPT_DIGRAPH_H
   486 #endif // LEMON_CONCEPT_DIGRAPH_H