COIN-OR::LEMON - Graph Library

Changeset 209:765619b7cbb2 in lemon-1.0 for lemon/concepts/graph.h


Ignore:
Timestamp:
07/13/08 20:51:02 (11 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Phase:
public
Message:

Apply unify-sources.sh to the source tree

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/concepts/graph.h

    r125 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    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.
    44 *
    55 * Copyright (C) 2003-2008
     
    6666    /// direction. The IncEdgeIt iterates also on the same edges
    6767    /// as the OutArcIt and InArcIt but it is not convertible to Arc just
    68     /// to Edge. 
     68    /// to Edge.
    6969    class Graph {
    7070    public:
     
    7373      ///
    7474      /// The undirected graph should be tagged by the UndirectedTag. This
    75       /// tag helps the enable_if technics to make compile time 
    76       /// specializations for undirected graphs. 
     75      /// tag helps the enable_if technics to make compile time
     76      /// specializations for undirected graphs.
    7777      typedef True UndirectedTag;
    7878
    79       /// \brief The base type of node iterators, 
     79      /// \brief The base type of node iterators,
    8080      /// or in other words, the trivial node iterator.
    8181      ///
    8282      /// This is the base type of each node iterator,
    8383      /// thus each kind of node iterator converts to this.
    84       /// More precisely each kind of node iterator should be inherited 
     84      /// More precisely each kind of node iterator should be inherited
    8585      /// from the trivial node iterator.
    8686      class Node {
     
    109109
    110110        /// Inequality operator
    111        
     111
    112112        /// \sa operator==(Node n)
    113113        ///
    114114        bool operator!=(Node) const { return true; }
    115115
    116         /// Artificial ordering operator.
    117        
    118         /// To allow the use of graph descriptors as key type in std::map or
    119         /// similar associative container we require this.
    120         ///
    121         /// \note This operator only have to define some strict ordering of
    122         /// the items; this order has nothing to do with the iteration
    123         /// ordering of the items.
    124         bool operator<(Node) const { return false; }
    125 
    126       };
    127    
     116        /// Artificial ordering operator.
     117
     118        /// To allow the use of graph descriptors as key type in std::map or
     119        /// similar associative container we require this.
     120        ///
     121        /// \note This operator only have to define some strict ordering of
     122        /// the items; this order has nothing to do with the iteration
     123        /// ordering of the items.
     124        bool operator<(Node) const { return false; }
     125
     126      };
     127
    128128      /// This iterator goes through each node.
    129129
     
    143143        NodeIt() { }
    144144        /// Copy constructor.
    145        
     145
    146146        /// Copy constructor.
    147147        ///
     
    159159        /// Node -> NodeIt conversion.
    160160
    161         /// Sets the iterator to the node of \c the graph pointed by 
    162         /// the trivial iterator.
    163         /// This feature necessitates that each time we 
     161        /// Sets the iterator to the node of \c the graph pointed by
     162        /// the trivial iterator.
     163        /// This feature necessitates that each time we
    164164        /// iterate the arc-set, the iteration order is the same.
    165165        NodeIt(const Graph&, const Node&) { }
     
    170170        NodeIt& operator++() { return *this; }
    171171      };
    172    
    173    
     172
     173
    174174      /// The base type of the edge iterators.
    175175
     
    204204        bool operator!=(Edge) const { return true; }
    205205
    206         /// Artificial ordering operator.
    207        
    208         /// To allow the use of graph descriptors as key type in std::map or
    209         /// similar associative container we require this.
    210         ///
    211         /// \note This operator only have to define some strict ordering of
    212         /// the items; this order has nothing to do with the iteration
    213         /// ordering of the items.
    214         bool operator<(Edge) const { return false; }
     206        /// Artificial ordering operator.
     207
     208        /// To allow the use of graph descriptors as key type in std::map or
     209        /// similar associative container we require this.
     210        ///
     211        /// \note This operator only have to define some strict ordering of
     212        /// the items; this order has nothing to do with the iteration
     213        /// ordering of the items.
     214        bool operator<(Edge) const { return false; }
    215215      };
    216216
     
    242242        EdgeIt(Invalid) { }
    243243        /// This constructor sets the iterator to the first edge.
    244    
     244
    245245        /// This constructor sets the iterator to the first edge.
    246246        EdgeIt(const Graph&) { }
     
    249249        /// Sets the iterator to the value of the trivial iterator.
    250250        /// This feature necessitates that each time we
    251         /// iterate the edge-set, the iteration order is the 
    252         /// same.
    253         EdgeIt(const Graph&, const Edge&) { } 
     251        /// iterate the edge-set, the iteration order is the
     252        /// same.
     253        EdgeIt(const Graph&, const Edge&) { }
    254254        /// Next edge
    255        
     255
    256256        /// Assign the iterator to the next edge.
    257257        EdgeIt& operator++() { return *this; }
    258258      };
    259259
    260       /// \brief This iterator goes trough the incident undirected 
     260      /// \brief This iterator goes trough the incident undirected
    261261      /// arcs of a node.
    262262      ///
    263263      /// This iterator goes trough the incident edges
    264       /// of a certain node of a graph. You should assume that the 
     264      /// of a certain node of a graph. You should assume that the
    265265      /// loop arcs will be iterated twice.
    266       /// 
     266      ///
    267267      /// Its usage is quite simple, for example you can compute the
    268268      /// degree (i.e. count the number of incident arcs of a node \c n
    269       /// in graph \c g of type \c Graph as follows. 
     269      /// in graph \c g of type \c Graph as follows.
    270270      ///
    271271      ///\code
     
    291291        IncEdgeIt(Invalid) { }
    292292        /// This constructor sets the iterator to first incident arc.
    293    
     293
    294294        /// This constructor set the iterator to the first incident arc of
    295295        /// the node.
     
    298298
    299299        /// Sets the iterator to the value of the trivial iterator \c e.
    300         /// This feature necessitates that each time we 
     300        /// This feature necessitates that each time we
    301301        /// iterate the arc-set, the iteration order is the same.
    302302        IncEdgeIt(const Graph&, const Edge&) { }
     
    304304
    305305        /// Assign the iterator to the next incident arc
    306         /// of the corresponding node.
     306        /// of the corresponding node.
    307307        IncEdgeIt& operator++() { return *this; }
    308308      };
     
    341341        bool operator!=(Arc) const { return true; }
    342342
    343         /// Artificial ordering operator.
    344        
    345         /// To allow the use of graph descriptors as key type in std::map or
    346         /// similar associative container we require this.
    347         ///
    348         /// \note This operator only have to define some strict ordering of
    349         /// the items; this order has nothing to do with the iteration
    350         /// ordering of the items.
    351         bool operator<(Arc) const { return false; }
    352        
    353       }; 
     343        /// Artificial ordering operator.
     344
     345        /// To allow the use of graph descriptors as key type in std::map or
     346        /// similar associative container we require this.
     347        ///
     348        /// \note This operator only have to define some strict ordering of
     349        /// the items; this order has nothing to do with the iteration
     350        /// ordering of the items.
     351        bool operator<(Arc) const { return false; }
     352
     353      };
    354354      /// This iterator goes through each directed arc.
    355355
     
    379379        ArcIt(Invalid) { }
    380380        /// This constructor sets the iterator to the first arc.
    381    
     381
    382382        /// This constructor sets the iterator to the first arc of \c g.
    383383        ///@param g the graph
     
    386386
    387387        /// Sets the iterator to the value of the trivial iterator \c e.
    388         /// This feature necessitates that each time we 
     388        /// This feature necessitates that each time we
    389389        /// iterate the arc-set, the iteration order is the same.
    390         ArcIt(const Graph&, const Arc&) { } 
     390        ArcIt(const Graph&, const Arc&) { }
    391391        ///Next arc
    392        
     392
    393393        /// Assign the iterator to the next arc.
    394394        ArcIt& operator++() { return *this; }
    395395      };
    396    
     396
    397397      /// This iterator goes trough the outgoing directed arcs of a node.
    398398
     
    406406      /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
    407407      ///\endcode
    408    
     408
    409409      class OutArcIt : public Arc {
    410410      public:
     
    425425        OutArcIt(Invalid) { }
    426426        /// This constructor sets the iterator to the first outgoing arc.
    427    
     427
    428428        /// This constructor sets the iterator to the first outgoing arc of
    429429        /// the node.
     
    431431        ///@param g the graph
    432432        OutArcIt(const Graph& n, const Node& g) {
    433           ignore_unused_variable_warning(n);
    434           ignore_unused_variable_warning(g);
    435         }
     433          ignore_unused_variable_warning(n);
     434          ignore_unused_variable_warning(g);
     435        }
    436436        /// Arc -> OutArcIt conversion
    437437
    438438        /// Sets the iterator to the value of the trivial iterator.
    439         /// This feature necessitates that each time we
     439        /// This feature necessitates that each time we
    440440        /// iterate the arc-set, the iteration order is the same.
    441441        OutArcIt(const Graph&, const Arc&) { }
    442442        ///Next outgoing arc
    443        
    444         /// Assign the iterator to the next 
     443
     444        /// Assign the iterator to the next
    445445        /// outgoing arc of the corresponding node.
    446446        OutArcIt& operator++() { return *this; }
     
    477477        InArcIt(Invalid) { }
    478478        /// This constructor sets the iterator to first incoming arc.
    479    
     479
    480480        /// This constructor set the iterator to the first incoming arc of
    481481        /// the node.
    482482        ///@param n the node
    483483        ///@param g the graph
    484         InArcIt(const Graph& g, const Node& n) { 
    485           ignore_unused_variable_warning(n);
    486           ignore_unused_variable_warning(g);
    487         }
     484        InArcIt(const Graph& g, const Node& n) {
     485          ignore_unused_variable_warning(n);
     486          ignore_unused_variable_warning(g);
     487        }
    488488        /// Arc -> InArcIt conversion
    489489
    490490        /// Sets the iterator to the value of the trivial iterator \c e.
    491         /// This feature necessitates that each time we 
     491        /// This feature necessitates that each time we
    492492        /// iterate the arc-set, the iteration order is the same.
    493493        InArcIt(const Graph&, const Arc&) { }
     
    500500
    501501      /// \brief Read write map of the nodes to type \c T.
    502       /// 
     502      ///
    503503      /// ReadWrite map of the nodes to type \c T.
    504504      /// \sa Reference
    505       template<class T> 
     505      template<class T>
    506506      class NodeMap : public ReadWriteMap< Node, T >
    507507      {
     
    517517        ///Assignment operator
    518518        template <typename CMap>
    519         NodeMap& operator=(const CMap&) { 
     519        NodeMap& operator=(const CMap&) {
    520520          checkConcept<ReadMap<Node, T>, CMap>();
    521           return *this; 
     521          return *this;
    522522        }
    523523      };
     
    527527      /// Reference map of the directed arcs to type \c T.
    528528      /// \sa Reference
    529       template<class T> 
     529      template<class T>
    530530      class ArcMap : public ReadWriteMap<Arc,T>
    531531      {
     
    540540        ///Assignment operator
    541541        template <typename CMap>
    542         ArcMap& operator=(const CMap&) { 
     542        ArcMap& operator=(const CMap&) {
    543543          checkConcept<ReadMap<Arc, T>, CMap>();
    544           return *this; 
     544          return *this;
    545545        }
    546546      };
     
    550550      /// Reference map of the arcs to type \c T.
    551551      /// \sa Reference
    552       template<class T> 
     552      template<class T>
    553553      class EdgeMap : public ReadWriteMap<Edge,T>
    554554      {
     
    563563        ///Assignment operator
    564564        template <typename CMap>
    565         EdgeMap& operator=(const CMap&) { 
     565        EdgeMap& operator=(const CMap&) {
    566566          checkConcept<ReadMap<Edge, T>, CMap>();
    567           return *this; 
     567          return *this;
    568568        }
    569569      };
     
    574574      /// will be the given node.
    575575      Arc direct(const Edge&, const Node&) const {
    576         return INVALID;
     576        return INVALID;
    577577      }
    578578
     
    584584      /// the directed arc is the same when the given bool is true.
    585585      Arc direct(const Edge&, bool) const {
    586         return INVALID;
     586        return INVALID;
    587587      }
    588588
     
    626626
    627627      /// \brief Returns the id of the node.
    628       int id(Node) const { return -1; } 
     628      int id(Node) const { return -1; }
    629629
    630630      /// \brief Returns the id of the edge.
    631       int id(Edge) const { return -1; } 
     631      int id(Edge) const { return -1; }
    632632
    633633      /// \brief Returns the id of the arc.
    634       int id(Arc) const { return -1; } 
     634      int id(Arc) const { return -1; }
    635635
    636636      /// \brief Returns the node with the given id.
    637637      ///
    638638      /// \pre The argument should be a valid node id in the graph.
    639       Node nodeFromId(int) const { return INVALID; } 
     639      Node nodeFromId(int) const { return INVALID; }
    640640
    641641      /// \brief Returns the edge with the given id.
    642642      ///
    643643      /// \pre The argument should be a valid edge id in the graph.
    644       Edge edgeFromId(int) const { return INVALID; } 
     644      Edge edgeFromId(int) const { return INVALID; }
    645645
    646646      /// \brief Returns the arc with the given id.
    647647      ///
    648648      /// \pre The argument should be a valid arc id in the graph.
    649       Arc arcFromId(int) const { return INVALID; } 
     649      Arc arcFromId(int) const { return INVALID; }
    650650
    651651      /// \brief Returns an upper bound on the node IDs.
    652       int maxNodeId() const { return -1; } 
     652      int maxNodeId() const { return -1; }
    653653
    654654      /// \brief Returns an upper bound on the edge IDs.
    655       int maxEdgeId() const { return -1; } 
     655      int maxEdgeId() const { return -1; }
    656656
    657657      /// \brief Returns an upper bound on the arc IDs.
    658       int maxArcId() const { return -1; } 
     658      int maxArcId() const { return -1; }
    659659
    660660      void first(Node&) const {}
     
    684684
    685685      // Dummy parameter.
    686       int maxId(Node) const { return -1; } 
     686      int maxId(Node) const { return -1; }
    687687      // Dummy parameter.
    688       int maxId(Edge) const { return -1; } 
     688      int maxId(Edge) const { return -1; }
    689689      // Dummy parameter.
    690       int maxId(Arc) const { return -1; } 
     690      int maxId(Arc) const { return -1; }
    691691
    692692      /// \brief Base node of the iterator
     
    694694      /// Returns the base node (the source in this case) of the iterator
    695695      Node baseNode(OutArcIt e) const {
    696         return source(e);
     696        return source(e);
    697697      }
    698698      /// \brief Running node of the iterator
     
    701701      /// iterator
    702702      Node runningNode(OutArcIt e) const {
    703         return target(e);
     703        return target(e);
    704704      }
    705705
     
    708708      /// Returns the base node (the target in this case) of the iterator
    709709      Node baseNode(InArcIt e) const {
    710         return target(e);
     710        return target(e);
    711711      }
    712712      /// \brief Running node of the iterator
     
    715715      /// iterator
    716716      Node runningNode(InArcIt e) const {
    717         return source(e);
     717        return source(e);
    718718      }
    719719
     
    722722      /// Returns the base node of the iterator
    723723      Node baseNode(IncEdgeIt) const {
    724         return INVALID;
     724        return INVALID;
    725725      }
    726      
     726
    727727      /// \brief Running node of the iterator
    728728      ///
    729729      /// Returns the running node of the iterator
    730730      Node runningNode(IncEdgeIt) const {
    731         return INVALID;
     731        return INVALID;
    732732      }
    733733
    734734      template <typename _Graph>
    735735      struct Constraints {
    736         void constraints() {
    737           checkConcept<IterableGraphComponent<>, _Graph>();
    738           checkConcept<IDableGraphComponent<>, _Graph>();
    739           checkConcept<MappableGraphComponent<>, _Graph>();
    740         }
     736        void constraints() {
     737          checkConcept<IterableGraphComponent<>, _Graph>();
     738          checkConcept<IDableGraphComponent<>, _Graph>();
     739          checkConcept<MappableGraphComponent<>, _Graph>();
     740        }
    741741      };
    742742
Note: See TracChangeset for help on using the changeset viewer.