COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 734:bd72f8d20f33 in lemon-1.2 for lemon/concepts/digraph.h


Ignore:
Timestamp:
08/23/09 11:07:50 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Doc improvements and unification for graph concepts (#311)

File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/concepts/digraph.h

    r580 r734  
    3636    /// \brief Class describing the concept of directed graphs.
    3737    ///
    38     /// This class describes the \ref concept "concept" of the
    39     /// immutable directed digraphs.
     38    /// This class describes the common interface of all directed
     39    /// graphs (digraphs).
    4040    ///
    41     /// Note that actual digraph implementation like @ref ListDigraph or
    42     /// @ref SmartDigraph may have several additional functionality.
     41    /// Like all concept classes, it only provides an interface
     42    /// without any sensible implementation. So any general algorithm for
     43    /// directed graphs should compile with this class, but it will not
     44    /// run properly, of course.
     45    /// An actual digraph implementation like \ref ListDigraph or
     46    /// \ref SmartDigraph may have additional functionality.
    4347    ///
    44     /// \sa concept
     48    /// \sa Graph
    4549    class Digraph {
    4650    private:
    47       ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
    48 
    49       ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
    50       ///
    51       Digraph(const Digraph &) {};
    52       ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
    53       ///\e not allowed. Use DigraphCopy() instead.
    54 
    55       ///Assignment of \ref Digraph "Digraph"s to another ones are
    56       ///\e not allowed.  Use DigraphCopy() instead.
    57 
     51      /// Diraphs are \e not copy constructible. Use DigraphCopy instead.
     52      Digraph(const Digraph &) {}
     53      /// \brief Assignment of a digraph to another one is \e not allowed.
     54      /// Use DigraphCopy instead.
    5855      void operator=(const Digraph &) {}
     56
    5957    public:
    60       ///\e
    61 
    62       /// Defalult constructor.
    63 
    64       /// Defalult constructor.
    65       ///
     58      /// Default constructor.
    6659      Digraph() { }
    67       /// Class for identifying a node of the digraph
     60
     61      /// The node type of the digraph
    6862
    6963      /// This class identifies a node of the digraph. It also serves
    7064      /// as a base class of the node iterators,
    71       /// thus they will convert to this type.
     65      /// thus they convert to this type.
    7266      class Node {
    7367      public:
    7468        /// Default constructor
    7569
    76         /// @warning The default constructor sets the iterator
    77         /// to an undefined value.
     70        /// Default constructor.
     71        /// \warning It sets the object to an undefined value.
    7872        Node() { }
    7973        /// Copy constructor.
    … …  
    8377        Node(const Node&) { }
    8478
    85         /// Invalid constructor \& conversion.
    86 
    87         /// This constructor initializes the iterator to be invalid.
     79        /// %Invalid constructor \& conversion.
     80
     81        /// Initializes the object to be invalid.
    8882        /// \sa Invalid for more details.
    8983        Node(Invalid) { }
    9084        /// Equality operator
    9185
     86        /// Equality operator.
     87        ///
    9288        /// Two iterators are equal if and only if they point to the
    93         /// same object or both are invalid.
     89        /// same object or both are \c INVALID.
    9490        bool operator==(Node) const { return true; }
    9591
    9692        /// Inequality operator
    9793
    98         /// \sa operator==(Node n)
    99         ///
     94        /// Inequality operator.
    10095        bool operator!=(Node) const { return true; }
    10196
    10297        /// Artificial ordering operator.
    10398
    104         /// To allow the use of digraph descriptors as key type in std::map or
    105         /// similar associative container we require this.
    106         ///
    107         /// \note This operator only have to define some strict ordering of
    108         /// the items; this order has nothing to do with the iteration
    109         /// ordering of the items.
     99        /// Artificial ordering operator.
     100        ///
     101        /// \note This operator only has to define some strict ordering of
     102        /// the nodes; this order has nothing to do with the iteration
     103        /// ordering of the nodes.
    110104        bool operator<(Node) const { return false; }
    111 
    112       };
    113 
    114       /// This iterator goes through each node.
    115 
    116       /// This iterator goes through each node.
     105      };
     106
     107      /// Iterator class for the nodes.
     108
     109      /// This iterator goes through each node of the digraph.
    117110      /// Its usage is quite simple, for example you can count the number
    118       /// of nodes in digraph \c g of type \c Digraph like this:
     111      /// of nodes in a digraph \c g of type \c %Digraph like this:
    119112      ///\code
    120113      /// int count=0;
    … …  
    125118        /// Default constructor
    126119
    127         /// @warning The default constructor sets the iterator
    128         /// to an undefined value.
     120        /// Default constructor.
     121        /// \warning It sets the iterator to an undefined value.
    129122        NodeIt() { }
    130123        /// Copy constructor.
    … …  
    133126        ///
    134127        NodeIt(const NodeIt& n) : Node(n) { }
    135         /// Invalid constructor \& conversion.
    136 
    137         /// Initialize the iterator to be invalid.
     128        /// %Invalid constructor \& conversion.
     129
     130        /// Initializes the iterator to be invalid.
    138131        /// \sa Invalid for more details.
    139132        NodeIt(Invalid) { }
    140133        /// Sets the iterator to the first node.
    141134
    142         /// Sets the iterator to the first node of \c g.
    143         ///
    144         NodeIt(const Digraph&) { }
    145         /// Node -> NodeIt conversion.
    146 
    147         /// Sets the iterator to the node of \c the digraph pointed by
    148         /// the trivial iterator.
    149         /// This feature necessitates that each time we
    150         /// iterate the arc-set, the iteration order is the same.
     135        /// Sets the iterator to the first node of the given digraph.
     136        ///
     137        explicit NodeIt(const Digraph&) { }
     138        /// Sets the iterator to the given node.
     139
     140        /// Sets the iterator to the given node of the given digraph.
     141        ///
    151142        NodeIt(const Digraph&, const Node&) { }
    152143        /// Next node.
    … …  
    158149
    159150
    160       /// Class for identifying an arc of the digraph
     151      /// The arc type of the digraph
    161152
    162153      /// This class identifies an arc of the digraph. It also serves
    … …  
    167158        /// Default constructor
    168159
    169         /// @warning The default constructor sets the iterator
    170         /// to an undefined value.
     160        /// Default constructor.
     161        /// \warning It sets the object to an undefined value.
    171162        Arc() { }
    172163        /// Copy constructor.
    … …  
    175166        ///
    176167        Arc(const Arc&) { }
    177         /// Initialize the iterator to be invalid.
    178 
    179         /// Initialize the iterator to be invalid.
    180         ///
     168        /// %Invalid constructor \& conversion.
     169
     170        /// Initializes the object to be invalid.
     171        /// \sa Invalid for more details.
    181172        Arc(Invalid) { }
    182173        /// Equality operator
    183174
     175        /// Equality operator.
     176        ///
    184177        /// Two iterators are equal if and only if they point to the
    185         /// same object or both are invalid.
     178        /// same object or both are \c INVALID.
    186179        bool operator==(Arc) const { return true; }
    187180        /// Inequality operator
    188181
    189         /// \sa operator==(Arc n)
    190         ///
     182        /// Inequality operator.
    191183        bool operator!=(Arc) const { return true; }
    192184
    193185        /// Artificial ordering operator.
    194186
    195         /// To allow the use of digraph descriptors as key type in std::map or
    196         /// similar associative container we require this.
    197         ///
    198         /// \note This operator only have to define some strict ordering of
    199         /// the items; this order has nothing to do with the iteration
    200         /// ordering of the items.
     187        /// Artificial ordering operator.
     188        ///
     189        /// \note This operator only has to define some strict ordering of
     190        /// the arcs; this order has nothing to do with the iteration
     191        /// ordering of the arcs.
    201192        bool operator<(Arc) const { return false; }
    202193      };
    203194
    204       /// This iterator goes trough the outgoing arcs of a node.
     195      /// Iterator class for the outgoing arcs of a node.
    205196
    206197      /// This iterator goes trough the \e outgoing arcs of a certain node
    … …  
    208199      /// Its usage is quite simple, for example you can count the number
    209200      /// of outgoing arcs of a node \c n
    210       /// in digraph \c g of type \c Digraph as follows.
     201      /// in a digraph \c g of type \c %Digraph as follows.
    211202      ///\code
    212203      /// int count=0;
    213       /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
     204      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
    214205      ///\endcode
    215 
    216206      class OutArcIt : public Arc {
    217207      public:
    218208        /// Default constructor
    219209
    220         /// @warning The default constructor sets the iterator
    221         /// to an undefined value.
     210        /// Default constructor.
     211        /// \warning It sets the iterator to an undefined value.
    222212        OutArcIt() { }
    223213        /// Copy constructor.
    … …  
    226216        ///
    227217        OutArcIt(const OutArcIt& e) : Arc(e) { }
    228         /// Initialize the iterator to be invalid.
    229 
    230         /// Initialize the iterator to be invalid.
    231         ///
     218        /// %Invalid constructor \& conversion.
     219
     220        /// Initializes the iterator to be invalid.
     221        /// \sa Invalid for more details.
    232222        OutArcIt(Invalid) { }
    233         /// This constructor sets the iterator to the first outgoing arc.
    234 
    235         /// This constructor sets the iterator to the first outgoing arc of
    236         /// the node.
     223        /// Sets the iterator to the first outgoing arc.
     224
     225        /// Sets the iterator to the first outgoing arc of the given node.
     226        ///
    237227        OutArcIt(const Digraph&, const Node&) { }
    238         /// Arc -> OutArcIt conversion
    239 
    240         /// Sets the iterator to the value of the trivial iterator.
    241         /// This feature necessitates that each time we
    242         /// iterate the arc-set, the iteration order is the same.
     228        /// Sets the iterator to the given arc.
     229
     230        /// Sets the iterator to the given arc of the given digraph.
     231        ///
    243232        OutArcIt(const Digraph&, const Arc&) { }
    244         ///Next outgoing arc
     233        /// Next outgoing arc
    245234
    246235        /// Assign the iterator to the next
    … …  
    249238      };
    250239
    251       /// This iterator goes trough the incoming arcs of a node.
     240      /// Iterator class for the incoming arcs of a node.
    252241
    253242      /// This iterator goes trough the \e incoming arcs of a certain node
    254243      /// of a digraph.
    255244      /// Its usage is quite simple, for example you can count the number
    256       /// of outgoing arcs of a node \c n
    257       /// in digraph \c g of type \c Digraph as follows.
     245      /// of incoming arcs of a node \c n
     246      /// in a digraph \c g of type \c %Digraph as follows.
    258247      ///\code
    259248      /// int count=0;
    260       /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
     249      /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
    261250      ///\endcode
    262 
    263251      class InArcIt : public Arc {
    264252      public:
    265253        /// Default constructor
    266254
    267         /// @warning The default constructor sets the iterator
    268         /// to an undefined value.
     255        /// Default constructor.
     256        /// \warning It sets the iterator to an undefined value.
    269257        InArcIt() { }
    270258        /// Copy constructor.
    … …  
    273261        ///
    274262        InArcIt(const InArcIt& e) : Arc(e) { }
    275         /// Initialize the iterator to be invalid.
    276 
    277         /// Initialize the iterator to be invalid.
    278         ///
     263        /// %Invalid constructor \& conversion.
     264
     265        /// Initializes the iterator to be invalid.
     266        /// \sa Invalid for more details.
    279267        InArcIt(Invalid) { }
    280         /// This constructor sets the iterator to first incoming arc.
    281 
    282         /// This constructor set the iterator to the first incoming arc of
    283         /// the node.
     268        /// Sets the iterator to the first incoming arc.
     269
     270        /// Sets the iterator to the first incoming arc of the given node.
     271        ///
    284272        InArcIt(const Digraph&, const Node&) { }
    285         /// Arc -> InArcIt conversion
    286 
    287         /// Sets the iterator to the value of the trivial iterator \c e.
    288         /// This feature necessitates that each time we
    289         /// iterate the arc-set, the iteration order is the same.
     273        /// Sets the iterator to the given arc.
     274
     275        /// Sets the iterator to the given arc of the given digraph.
     276        ///
    290277        InArcIt(const Digraph&, const Arc&) { }
    291278        /// Next incoming arc
    292279
    293         /// Assign the iterator to the next inarc of the corresponding node.
    294         ///
     280        /// Assign the iterator to the next
     281        /// incoming arc of the corresponding node.
    295282        InArcIt& operator++() { return *this; }
    296283      };
    297       /// This iterator goes through each arc.
    298 
    299       /// This iterator goes through each arc of a digraph.
     284
     285      /// Iterator class for the arcs.
     286
     287      /// This iterator goes through each arc of the digraph.
    300288      /// Its usage is quite simple, for example you can count the number
    301       /// of arcs in a digraph \c g of type \c Digraph as follows:
     289      /// of arcs in a digraph \c g of type \c %Digraph as follows:
    302290      ///\code
    303291      /// int count=0;
    304       /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
     292      /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
    305293      ///\endcode
    306294      class ArcIt : public Arc {
    … …  
    308296        /// Default constructor
    309297
    310         /// @warning The default constructor sets the iterator
    311         /// to an undefined value.
     298        /// Default constructor.
     299        /// \warning It sets the iterator to an undefined value.
    312300        ArcIt() { }
    313301        /// Copy constructor.
    … …  
    316304        ///
    317305        ArcIt(const ArcIt& e) : Arc(e) { }
    318         /// Initialize the iterator to be invalid.
    319 
    320         /// Initialize the iterator to be invalid.
    321         ///
     306        /// %Invalid constructor \& conversion.
     307
     308        /// Initializes the iterator to be invalid.
     309        /// \sa Invalid for more details.
    322310        ArcIt(Invalid) { }
    323         /// This constructor sets the iterator to the first arc.
    324 
    325         /// This constructor sets the iterator to the first arc of \c g.
    326         ///@param g the digraph
    327         ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
    328         /// Arc -> ArcIt conversion
    329 
    330         /// Sets the iterator to the value of the trivial iterator \c e.
    331         /// This feature necessitates that each time we
    332         /// iterate the arc-set, the iteration order is the same.
     311        /// Sets the iterator to the first arc.
     312
     313        /// Sets the iterator to the first arc of the given digraph.
     314        ///
     315        explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
     316        /// Sets the iterator to the given arc.
     317
     318        /// Sets the iterator to the given arc of the given digraph.
     319        ///
    333320        ArcIt(const Digraph&, const Arc&) { }
    334         ///Next arc
     321        /// Next arc
    335322
    336323        /// Assign the iterator to the next arc.
     324        ///
    337325        ArcIt& operator++() { return *this; }
    338326      };
    339       ///Gives back the target node of an arc.
    340 
    341       ///Gives back the target node of an arc.
    342       ///
     327
     328      /// \brief The source node of the arc.
     329      ///
     330      /// Returns the source node of the given arc.
     331      Node source(Arc) const { return INVALID; }
     332
     333      /// \brief The target node of the arc.
     334      ///
     335      /// Returns the target node of the given arc.
    343336      Node target(Arc) const { return INVALID; }
    344       ///Gives back the source node of an arc.
    345 
    346       ///Gives back the source node of an arc.
    347       ///
    348       Node source(Arc) const { return INVALID; }
    349 
    350       /// \brief Returns the ID of the node.
     337
     338      /// \brief The ID of the node.
     339      ///
     340      /// Returns the ID of the given node.
    351341      int id(Node) const { return -1; }
    352342
    353       /// \brief Returns the ID of the arc.
     343      /// \brief The ID of the arc.
     344      ///
     345      /// Returns the ID of the given arc.
    354346      int id(Arc) const { return -1; }
    355347
    356       /// \brief Returns the node with the given ID.
    357       ///
    358       /// \pre The argument should be a valid node ID in the graph.
     348      /// \brief The node with the given ID.
     349      ///
     350      /// Returns the node with the given ID.
     351      /// \pre The argument should be a valid node ID in the digraph.
    359352      Node nodeFromId(int) const { return INVALID; }
    360353
    361       /// \brief Returns the arc with the given ID.
    362       ///
    363       /// \pre The argument should be a valid arc ID in the graph.
     354      /// \brief The arc with the given ID.
     355      ///
     356      /// Returns the arc with the given ID.
     357      /// \pre The argument should be a valid arc ID in the digraph.
    364358      Arc arcFromId(int) const { return INVALID; }
    365359
    366       /// \brief Returns an upper bound on the node IDs.
     360      /// \brief An upper bound on the node IDs.
     361      ///
     362      /// Returns an upper bound on the node IDs.
    367363      int maxNodeId() const { return -1; }
    368364
    369       /// \brief Returns an upper bound on the arc IDs.
     365      /// \brief An upper bound on the arc IDs.
     366      ///
     367      /// Returns an upper bound on the arc IDs.
    370368      int maxArcId() const { return -1; }
    371369
    … …  
    393391      int maxId(Arc) const { return -1; }
    394392
     393      /// \brief The opposite node on the arc.
     394      ///
     395      /// Returns the opposite node on the given arc.
     396      Node oppositeNode(Node, Arc) const { return INVALID; }
     397
    395398      /// \brief The base node of the iterator.
    396399      ///
    397       /// Gives back the base node of the iterator.
    398       /// It is always the target of the pointed arc.
    399       Node baseNode(const InArcIt&) const { return INVALID; }
     400      /// Returns the base node of the given outgoing arc iterator
     401      /// (i.e. the source node of the corresponding arc).
     402      Node baseNode(OutArcIt) const { return INVALID; }
    400403
    401404      /// \brief The running node of the iterator.
    402405      ///
    403       /// Gives back the running node of the iterator.
    404       /// It is always the source of the pointed arc.
    405       Node runningNode(const InArcIt&) const { return INVALID; }
     406      /// Returns the running node of the given outgoing arc iterator
     407      /// (i.e. the target node of the corresponding arc).
     408      Node runningNode(OutArcIt) const { return INVALID; }
    406409
    407410      /// \brief The base node of the iterator.
    408411      ///
    409       /// Gives back the base node of the iterator.
    410       /// It is always the source of the pointed arc.
    411       Node baseNode(const OutArcIt&) const { return INVALID; }
     412      /// Returns the base node of the given incomming arc iterator
     413      /// (i.e. the target node of the corresponding arc).
     414      Node baseNode(InArcIt) const { return INVALID; }
    412415
    413416      /// \brief The running node of the iterator.
    414417      ///
    415       /// Gives back the running node of the iterator.
    416       /// It is always the target of the pointed arc.
    417       Node runningNode(const OutArcIt&) const { return INVALID; }
    418 
    419       /// \brief The opposite node on the given arc.
    420       ///
    421       /// Gives back the opposite node on the given arc.
    422       Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
    423 
    424       /// \brief Reference map of the nodes to type \c T.
    425       ///
    426       /// Reference map of the nodes to type \c T.
     418      /// Returns the running node of the given incomming arc iterator
     419      /// (i.e. the source node of the corresponding arc).
     420      Node runningNode(InArcIt) const { return INVALID; }
     421
     422      /// \brief Standard graph map type for the nodes.
     423      ///
     424      /// Standard graph map type for the nodes.
     425      /// It conforms to the ReferenceMap concept.
    427426      template<class T>
    428427      class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
    429428      public:
    430429
    431         ///\e
    432         NodeMap(const Digraph&) { }
    433         ///\e
     430        /// Constructor
     431        explicit NodeMap(const Digraph&) { }
     432        /// Constructor with given initial value
    434433        NodeMap(const Digraph&, T) { }
    435434
    … …  
    446445      };
    447446
    448       /// \brief Reference map of the arcs to type \c T.
    449       ///
    450       /// Reference map of the arcs to type \c T.
     447      /// \brief Standard graph map type for the arcs.
     448      ///
     449      /// Standard graph map type for the arcs.
     450      /// It conforms to the ReferenceMap concept.
    451451      template<class T>
    452452      class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
    453453      public:
    454454
    455         ///\e
    456         ArcMap(const Digraph&) { }
    457         ///\e
     455        /// Constructor
     456        explicit ArcMap(const Digraph&) { }
     457        /// Constructor with given initial value
    458458        ArcMap(const Digraph&, T) { }
     459
    459460      private:
    460461        ///Copy constructor
Note: See TracChangeset for help on using the changeset viewer.