COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/concepts/graph.h

    r956 r704  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    1919///\ingroup graph_concepts
    2020///\file
    21 ///\brief The concept of undirected graphs.
     21///\brief The concept of Undirected Graphs.
    2222
    2323#ifndef LEMON_CONCEPTS_GRAPH_H
    … …  
    2525
    2626#include <lemon/concepts/graph_components.h>
    27 #include <lemon/concepts/maps.h>
    28 #include <lemon/concept_check.h>
    2927#include <lemon/core.h>
    3028
    … …  
    3432    /// \ingroup graph_concepts
    3533    ///
    36     /// \brief Class describing the concept of undirected graphs.
     34    /// \brief Class describing the concept of Undirected Graphs.
    3735    ///
    38     /// This class describes the common interface of all undirected
    39     /// graphs.
     36    /// This class describes the common interface of all Undirected
     37    /// Graphs.
    4038    ///
    41     /// Like all concept classes, it only provides an interface
    42     /// without any sensible implementation. So any general algorithm for
    43     /// undirected graphs should compile with this class, but it will not
     39    /// As all concept describing classes it provides only interface
     40    /// without any sensible implementation. So any algorithm for
     41    /// undirected graph should compile with this class, but it will not
    4442    /// run properly, of course.
    45     /// An actual graph implementation like \ref ListGraph or
    46     /// \ref SmartGraph may have additional functionality.
    4743    ///
    48     /// The undirected graphs also fulfill the concept of \ref Digraph
    49     /// "directed graphs", since each edge can also be regarded as two
    50     /// oppositely directed arcs.
    51     /// Undirected graphs provide an Edge type for the undirected edges and
    52     /// an Arc type for the directed arcs. The Arc type is convertible to
    53     /// Edge or inherited from it, i.e. the corresponding edge can be
    54     /// obtained from an arc.
    55     /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt
    56     /// and ArcMap classes can be used for the arcs (just like in digraphs).
    57     /// Both InArcIt and OutArcIt iterates on the same edges but with
    58     /// opposite direction. IncEdgeIt also iterates on the same edges
    59     /// as OutArcIt and InArcIt, but it is not convertible to Arc,
    60     /// only to Edge.
     44    /// The LEMON undirected graphs also fulfill the concept of
     45    /// directed graphs (\ref lemon::concepts::Digraph "Digraph
     46    /// Concept"). Each edges can be seen as two opposite
     47    /// directed arc and consequently the undirected graph can be
     48    /// seen as the direceted graph of these directed arcs. The
     49    /// Graph has the Edge inner class for the edges and
     50    /// the Arc type for the directed arcs. The Arc type is
     51    /// convertible to Edge or inherited from it so from a directed
     52    /// arc we can get the represented edge.
    6153    ///
    62     /// In LEMON, each undirected edge has an inherent orientation.
    63     /// Thus it can defined if an arc is forward or backward oriented in
    64     /// an undirected graph with respect to this default oriantation of
    65     /// the represented edge.
    66     /// With the direction() and direct() functions the direction
    67     /// of an arc can be obtained and set, respectively.
     54    /// In the sense of the LEMON each edge has a default
     55    /// direction (it should be in every computer implementation,
     56    /// because the order of edge's nodes defines an
     57    /// orientation). With the default orientation we can define that
     58    /// the directed arc is forward or backward directed. With the \c
     59    /// direction() and \c direct() function we can get the direction
     60    /// of the directed arc and we can direct an edge.
    6861    ///
    69     /// Only nodes and edges can be added to or removed from an undirected
    70     /// graph and the corresponding arcs are added or removed automatically.
    71     ///
    72     /// \sa Digraph
     62    /// The EdgeIt is an iterator for the edges. We can use
     63    /// the EdgeMap to map values for the edges. The InArcIt and
     64    /// OutArcIt iterates on the same edges but with opposite
     65    /// direction. The IncEdgeIt iterates also on the same edges
     66    /// as the OutArcIt and InArcIt but it is not convertible to Arc just
     67    /// to Edge.
    7368    class Graph {
    74     private:
    75       /// Graphs are \e not copy constructible. Use DigraphCopy instead.
    76       Graph(const Graph&) {}
    77       /// \brief Assignment of a graph to another one is \e not allowed.
    78       /// Use DigraphCopy instead.
    79       void operator=(const Graph&) {}
    80 
    8169    public:
    82       /// Default constructor.
    83       Graph() {}
    84 
    85       /// \brief Undirected graphs should be tagged with \c UndirectedTag.
    86       ///
    87       /// Undirected graphs should be tagged with \c UndirectedTag.
    88       ///
    89       /// This tag helps the \c enable_if technics to make compile time
     70      /// \brief The undirected graph should be tagged by the
     71      /// UndirectedTag.
     72      ///
     73      /// The undirected graph should be tagged by the UndirectedTag. This
     74      /// tag helps the enable_if technics to make compile time
    9075      /// specializations for undirected graphs.
    9176      typedef True UndirectedTag;
    9277
    93       /// The node type of the graph
    94 
    95       /// This class identifies a node of the graph. It also serves
    96       /// as a base class of the node iterators,
    97       /// thus they convert to this type.
     78      /// \brief The base type of node iterators,
     79      /// or in other words, the trivial node iterator.
     80      ///
     81      /// This is the base type of each node iterator,
     82      /// thus each kind of node iterator converts to this.
     83      /// More precisely each kind of node iterator should be inherited
     84      /// from the trivial node iterator.
    9885      class Node {
    9986      public:
    10087        /// Default constructor
    10188
    102         /// Default constructor.
    103         /// \warning It sets the object to an undefined value.
     89        /// @warning The default constructor sets the iterator
     90        /// to an undefined value.
    10491        Node() { }
    10592        /// Copy constructor.
    … …  
    10996        Node(const Node&) { }
    11097
    111         /// %Invalid constructor \& conversion.
    112 
    113         /// Initializes the object to be invalid.
     98        /// Invalid constructor \& conversion.
     99
     100        /// This constructor initializes the iterator to be invalid.
    114101        /// \sa Invalid for more details.
    115102        Node(Invalid) { }
    116103        /// Equality operator
    117104
    118         /// Equality operator.
    119         ///
    120105        /// Two iterators are equal if and only if they point to the
    121         /// same object or both are \c INVALID.
     106        /// same object or both are invalid.
    122107        bool operator==(Node) const { return true; }
    123108
    124109        /// Inequality operator
    125110
    126         /// Inequality operator.
     111        /// \sa operator==(Node n)
     112        ///
    127113        bool operator!=(Node) const { return true; }
    128114
    129115        /// Artificial ordering operator.
    130116
    131         /// Artificial ordering operator.
    132         ///
    133         /// \note This operator only has to define some strict ordering of
     117        /// To allow the use of graph descriptors as key type in std::map or
     118        /// similar associative container we require this.
     119        ///
     120        /// \note This operator only have to define some strict ordering of
    134121        /// the items; this order has nothing to do with the iteration
    135122        /// ordering of the items.
    … …  
    138125      };
    139126
    140       /// Iterator class for the nodes.
    141 
    142       /// This iterator goes through each node of the graph.
    143       /// Its usage is quite simple, for example, you can count the number
    144       /// of nodes in a graph \c g of type \c %Graph like this:
     127      /// This iterator goes through each node.
     128
     129      /// This iterator goes through each node.
     130      /// Its usage is quite simple, for example you can count the number
     131      /// of nodes in graph \c g of type \c Graph like this:
    145132      ///\code
    146133      /// int count=0;
    … …  
    151138        /// Default constructor
    152139
    153         /// Default constructor.
    154         /// \warning It sets the iterator to an undefined value.
     140        /// @warning The default constructor sets the iterator
     141        /// to an undefined value.
    155142        NodeIt() { }
    156143        /// Copy constructor.
    … …  
    159146        ///
    160147        NodeIt(const NodeIt& n) : Node(n) { }
    161         /// %Invalid constructor \& conversion.
    162 
    163         /// Initializes the iterator to be invalid.
     148        /// Invalid constructor \& conversion.
     149
     150        /// Initialize the iterator to be invalid.
    164151        /// \sa Invalid for more details.
    165152        NodeIt(Invalid) { }
    166153        /// Sets the iterator to the first node.
    167154
    168         /// Sets the iterator to the first node of the given digraph.
    169         ///
    170         explicit NodeIt(const Graph&) { }
    171         /// Sets the iterator to the given node.
    172 
    173         /// Sets the iterator to the given node of the given digraph.
    174         ///
     155        /// Sets the iterator to the first node of \c g.
     156        ///
     157        NodeIt(const Graph&) { }
     158        /// Node -> NodeIt conversion.
     159
     160        /// Sets the iterator to the node of \c the graph pointed by
     161        /// the trivial iterator.
     162        /// This feature necessitates that each time we
     163        /// iterate the arc-set, the iteration order is the same.
    175164        NodeIt(const Graph&, const Node&) { }
    176165        /// Next node.
    … …  
    182171
    183172
    184       /// The edge type of the graph
    185 
    186       /// This class identifies an edge of the graph. It also serves
    187       /// as a base class of the edge iterators,
    188       /// thus they will convert to this type.
     173      /// The base type of the edge iterators.
     174
     175      /// The base type of the edge iterators.
     176      ///
    189177      class Edge {
    190178      public:
    191179        /// Default constructor
    192180
    193         /// Default constructor.
    194         /// \warning It sets the object to an undefined value.
     181        /// @warning The default constructor sets the iterator
     182        /// to an undefined value.
    195183        Edge() { }
    196184        /// Copy constructor.
    … …  
    199187        ///
    200188        Edge(const Edge&) { }
    201         /// %Invalid constructor \& conversion.
    202 
    203         /// Initializes the object to be invalid.
    204         /// \sa Invalid for more details.
     189        /// Initialize the iterator to be invalid.
     190
     191        /// Initialize the iterator to be invalid.
     192        ///
    205193        Edge(Invalid) { }
    206194        /// Equality operator
    207195
    208         /// Equality operator.
    209         ///
    210196        /// Two iterators are equal if and only if they point to the
    211         /// same object or both are \c INVALID.
     197        /// same object or both are invalid.
    212198        bool operator==(Edge) const { return true; }
    213199        /// Inequality operator
    214200
    215         /// Inequality operator.
     201        /// \sa operator==(Edge n)
     202        ///
    216203        bool operator!=(Edge) const { return true; }
    217204
    218205        /// Artificial ordering operator.
    219206
    220         /// Artificial ordering operator.
    221         ///
    222         /// \note This operator only has to define some strict ordering of
    223         /// the edges; this order has nothing to do with the iteration
    224         /// ordering of the edges.
     207        /// To allow the use of graph descriptors as key type in std::map or
     208        /// similar associative container we require this.
     209        ///
     210        /// \note This operator only have to define some strict ordering of
     211        /// the items; this order has nothing to do with the iteration
     212        /// ordering of the items.
    225213        bool operator<(Edge) const { return false; }
    226214      };
    227215
    228       /// Iterator class for the edges.
    229 
    230       /// This iterator goes through each edge of the graph.
    231       /// Its usage is quite simple, for example, you can count the number
    232       /// of edges in a graph \c g of type \c %Graph as follows:
     216      /// This iterator goes through each edge.
     217
     218      /// This iterator goes through each edge of a graph.
     219      /// Its usage is quite simple, for example you can count the number
     220      /// of edges in a graph \c g of type \c Graph as follows:
    233221      ///\code
    234222      /// int count=0;
    … …  
    239227        /// Default constructor
    240228
    241         /// Default constructor.
    242         /// \warning It sets the iterator to an undefined value.
     229        /// @warning The default constructor sets the iterator
     230        /// to an undefined value.
    243231        EdgeIt() { }
    244232        /// Copy constructor.
    … …  
    247235        ///
    248236        EdgeIt(const EdgeIt& e) : Edge(e) { }
    249         /// %Invalid constructor \& conversion.
    250 
    251         /// Initializes the iterator to be invalid.
    252         /// \sa Invalid for more details.
     237        /// Initialize the iterator to be invalid.
     238
     239        /// Initialize the iterator to be invalid.
     240        ///
    253241        EdgeIt(Invalid) { }
    254         /// Sets the iterator to the first edge.
    255 
    256         /// Sets the iterator to the first edge of the given graph.
    257         ///
    258         explicit EdgeIt(const Graph&) { }
    259         /// Sets the iterator to the given edge.
    260 
    261         /// Sets the iterator to the given edge of the given graph.
    262         ///
     242        /// This constructor sets the iterator to the first edge.
     243
     244        /// This constructor sets the iterator to the first edge.
     245        EdgeIt(const Graph&) { }
     246        /// Edge -> EdgeIt conversion
     247
     248        /// Sets the iterator to the value of the trivial iterator.
     249        /// This feature necessitates that each time we
     250        /// iterate the edge-set, the iteration order is the
     251        /// same.
    263252        EdgeIt(const Graph&, const Edge&) { }
    264253        /// Next edge
    265254
    266255        /// Assign the iterator to the next edge.
    267         ///
    268256        EdgeIt& operator++() { return *this; }
    269257      };
    270258
    271       /// Iterator class for the incident edges of a node.
    272 
    273       /// This iterator goes trough the incident undirected edges
    274       /// of a certain node of a graph.
    275       /// Its usage is quite simple, for example, you can compute the
    276       /// degree (i.e. the number of incident edges) of a node \c n
    277       /// in a graph \c g of type \c %Graph as follows.
     259      /// \brief This iterator goes trough the incident undirected
     260      /// arcs of a node.
     261      ///
     262      /// This iterator goes trough the incident edges
     263      /// of a certain node of a graph. You should assume that the
     264      /// loop arcs will be iterated twice.
     265      ///
     266      /// Its usage is quite simple, for example you can compute the
     267      /// degree (i.e. count the number of incident arcs of a node \c n
     268      /// in graph \c g of type \c Graph as follows.
    278269      ///
    279270      ///\code
    … …  
    281272      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
    282273      ///\endcode
    283       ///
    284       /// \warning Loop edges will be iterated twice.
    285274      class IncEdgeIt : public Edge {
    286275      public:
    287276        /// Default constructor
    288277
    289         /// Default constructor.
    290         /// \warning It sets the iterator to an undefined value.
     278        /// @warning The default constructor sets the iterator
     279        /// to an undefined value.
    291280        IncEdgeIt() { }
    292281        /// Copy constructor.
    … …  
    295284        ///
    296285        IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
    297         /// %Invalid constructor \& conversion.
    298 
    299         /// Initializes the iterator to be invalid.
    300         /// \sa Invalid for more details.
     286        /// Initialize the iterator to be invalid.
     287
     288        /// Initialize the iterator to be invalid.
     289        ///
    301290        IncEdgeIt(Invalid) { }
    302         /// Sets the iterator to the first incident edge.
    303 
    304         /// Sets the iterator to the first incident edge of the given node.
    305         ///
     291        /// This constructor sets the iterator to first incident arc.
     292
     293        /// This constructor set the iterator to the first incident arc of
     294        /// the node.
    306295        IncEdgeIt(const Graph&, const Node&) { }
    307         /// Sets the iterator to the given edge.
    308 
    309         /// Sets the iterator to the given edge of the given graph.
    310         ///
     296        /// Edge -> IncEdgeIt conversion
     297
     298        /// Sets the iterator to the value of the trivial iterator \c e.
     299        /// This feature necessitates that each time we
     300        /// iterate the arc-set, the iteration order is the same.
    311301        IncEdgeIt(const Graph&, const Edge&) { }
    312         /// Next incident edge
    313 
    314         /// Assign the iterator to the next incident edge
     302        /// Next incident arc
     303
     304        /// Assign the iterator to the next incident arc
    315305        /// of the corresponding node.
    316306        IncEdgeIt& operator++() { return *this; }
    317307      };
    318308
    319       /// The arc type of the graph
    320 
    321       /// This class identifies a directed arc of the graph. It also serves
    322       /// as a base class of the arc iterators,
    323       /// thus they will convert to this type.
     309      /// The directed arc type.
     310
     311      /// The directed arc type. It can be converted to the
     312      /// edge or it should be inherited from the undirected
     313      /// edge.
    324314      class Arc {
    325315      public:
    326316        /// Default constructor
    327317
    328         /// Default constructor.
    329         /// \warning It sets the object to an undefined value.
     318        /// @warning The default constructor sets the iterator
     319        /// to an undefined value.
    330320        Arc() { }
    331321        /// Copy constructor.
    … …  
    334324        ///
    335325        Arc(const Arc&) { }
    336         /// %Invalid constructor \& conversion.
    337 
    338         /// Initializes the object to be invalid.
    339         /// \sa Invalid for more details.
     326        /// Initialize the iterator to be invalid.
     327
     328        /// Initialize the iterator to be invalid.
     329        ///
    340330        Arc(Invalid) { }
    341331        /// Equality operator
    342332
    343         /// Equality operator.
    344         ///
    345333        /// Two iterators are equal if and only if they point to the
    346         /// same object or both are \c INVALID.
     334        /// same object or both are invalid.
    347335        bool operator==(Arc) const { return true; }
    348336        /// Inequality operator
    349337
    350         /// Inequality operator.
     338        /// \sa operator==(Arc n)
     339        ///
    351340        bool operator!=(Arc) const { return true; }
    352341
    353342        /// Artificial ordering operator.
    354343
    355         /// Artificial ordering operator.
    356         ///
    357         /// \note This operator only has to define some strict ordering of
    358         /// the arcs; this order has nothing to do with the iteration
    359         /// ordering of the arcs.
     344        /// To allow the use of graph descriptors as key type in std::map or
     345        /// similar associative container we require this.
     346        ///
     347        /// \note This operator only have to define some strict ordering of
     348        /// the items; this order has nothing to do with the iteration
     349        /// ordering of the items.
    360350        bool operator<(Arc) const { return false; }
    361351
    362         /// Converison to \c Edge
    363 
    364         /// Converison to \c Edge.
    365         ///
     352        /// Converison to Edge
    366353        operator Edge() const { return Edge(); }
    367354      };
    368 
    369       /// Iterator class for the arcs.
    370 
    371       /// This iterator goes through each directed arc of the graph.
    372       /// Its usage is quite simple, for example, you can count the number
    373       /// of arcs in a graph \c g of type \c %Graph as follows:
     355      /// This iterator goes through each directed arc.
     356
     357      /// This iterator goes through each arc of a graph.
     358      /// Its usage is quite simple, for example you can count the number
     359      /// of arcs in a graph \c g of type \c Graph as follows:
    374360      ///\code
    375361      /// int count=0;
    376       /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;
     362      /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
    377363      ///\endcode
    378364      class ArcIt : public Arc {
    … …  
    380366        /// Default constructor
    381367
    382         /// Default constructor.
    383         /// \warning It sets the iterator to an undefined value.
     368        /// @warning The default constructor sets the iterator
     369        /// to an undefined value.
    384370        ArcIt() { }
    385371        /// Copy constructor.
    … …  
    388374        ///
    389375        ArcIt(const ArcIt& e) : Arc(e) { }
    390         /// %Invalid constructor \& conversion.
    391 
    392         /// Initializes the iterator to be invalid.
    393         /// \sa Invalid for more details.
     376        /// Initialize the iterator to be invalid.
     377
     378        /// Initialize the iterator to be invalid.
     379        ///
    394380        ArcIt(Invalid) { }
    395         /// Sets the iterator to the first arc.
    396 
    397         /// Sets the iterator to the first arc of the given graph.
    398         ///
    399         explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
    400         /// Sets the iterator to the given arc.
    401 
    402         /// Sets the iterator to the given arc of the given graph.
    403         ///
     381        /// This constructor sets the iterator to the first arc.
     382
     383        /// This constructor sets the iterator to the first arc of \c g.
     384        ///@param g the graph
     385        ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
     386        /// Arc -> ArcIt conversion
     387
     388        /// Sets the iterator to the value of the trivial iterator \c e.
     389        /// This feature necessitates that each time we
     390        /// iterate the arc-set, the iteration order is the same.
    404391        ArcIt(const Graph&, const Arc&) { }
    405         /// Next arc
     392        ///Next arc
    406393
    407394        /// Assign the iterator to the next arc.
    408         ///
    409395        ArcIt& operator++() { return *this; }
    410396      };
    411397
    412       /// Iterator class for the outgoing arcs of a node.
    413 
    414       /// This iterator goes trough the \e outgoing directed arcs of a
    415       /// certain node of a graph.
    416       /// Its usage is quite simple, for example, you can count the number
     398      /// This iterator goes trough the outgoing directed arcs of a node.
     399
     400      /// This iterator goes trough the \e outgoing arcs of a certain node
     401      /// of a graph.
     402      /// Its usage is quite simple, for example you can count the number
    417403      /// of outgoing arcs of a node \c n
    418       /// in a graph \c g of type \c %Graph as follows.
     404      /// in graph \c g of type \c Graph as follows.
    419405      ///\code
    420406      /// int count=0;
    421       /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
     407      /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
    422408      ///\endcode
     409
    423410      class OutArcIt : public Arc {
    424411      public:
    425412        /// Default constructor
    426413
    427         /// Default constructor.
    428         /// \warning It sets the iterator to an undefined value.
     414        /// @warning The default constructor sets the iterator
     415        /// to an undefined value.
    429416        OutArcIt() { }
    430417        /// Copy constructor.
    … …  
    433420        ///
    434421        OutArcIt(const OutArcIt& e) : Arc(e) { }
    435         /// %Invalid constructor \& conversion.
    436 
    437         /// Initializes the iterator to be invalid.
    438         /// \sa Invalid for more details.
     422        /// Initialize the iterator to be invalid.
     423
     424        /// Initialize the iterator to be invalid.
     425        ///
    439426        OutArcIt(Invalid) { }
    440         /// Sets the iterator to the first outgoing arc.
    441 
    442         /// Sets the iterator to the first outgoing arc of the given node.
    443         ///
     427        /// This constructor sets the iterator to the first outgoing arc.
     428
     429        /// This constructor sets the iterator to the first outgoing arc of
     430        /// the node.
     431        ///@param n the node
     432        ///@param g the graph
    444433        OutArcIt(const Graph& n, const Node& g) {
    445434          ignore_unused_variable_warning(n);
    446435          ignore_unused_variable_warning(g);
    447436        }
    448         /// Sets the iterator to the given arc.
    449 
    450         /// Sets the iterator to the given arc of the given graph.
    451         ///
     437        /// Arc -> OutArcIt conversion
     438
     439        /// Sets the iterator to the value of the trivial iterator.
     440        /// This feature necessitates that each time we
     441        /// iterate the arc-set, the iteration order is the same.
    452442        OutArcIt(const Graph&, const Arc&) { }
    453         /// Next outgoing arc
     443        ///Next outgoing arc
    454444
    455445        /// Assign the iterator to the next
    … …  
    458448      };
    459449
    460       /// Iterator class for the incoming arcs of a node.
    461 
    462       /// This iterator goes trough the \e incoming directed arcs of a
    463       /// certain node of a graph.
    464       /// Its usage is quite simple, for example, you can count the number
    465       /// of incoming arcs of a node \c n
    466       /// in a graph \c g of type \c %Graph as follows.
     450      /// This iterator goes trough the incoming directed arcs of a node.
     451
     452      /// This iterator goes trough the \e incoming arcs of a certain node
     453      /// of a graph.
     454      /// Its usage is quite simple, for example you can count the number
     455      /// of outgoing arcs of a node \c n
     456      /// in graph \c g of type \c Graph as follows.
    467457      ///\code
    468458      /// int count=0;
    469       /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
     459      /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
    470460      ///\endcode
     461
    471462      class InArcIt : public Arc {
    472463      public:
    473464        /// Default constructor
    474465
    475         /// Default constructor.
    476         /// \warning It sets the iterator to an undefined value.
     466        /// @warning The default constructor sets the iterator
     467        /// to an undefined value.
    477468        InArcIt() { }
    478469        /// Copy constructor.
    … …  
    481472        ///
    482473        InArcIt(const InArcIt& e) : Arc(e) { }
    483         /// %Invalid constructor \& conversion.
    484 
    485         /// Initializes the iterator to be invalid.
    486         /// \sa Invalid for more details.
     474        /// Initialize the iterator to be invalid.
     475
     476        /// Initialize the iterator to be invalid.
     477        ///
    487478        InArcIt(Invalid) { }
    488         /// Sets the iterator to the first incoming arc.
    489 
    490         /// Sets the iterator to the first incoming arc of the given node.
    491         ///
     479        /// This constructor sets the iterator to first incoming arc.
     480
     481        /// This constructor set the iterator to the first incoming arc of
     482        /// the node.
     483        ///@param n the node
     484        ///@param g the graph
    492485        InArcIt(const Graph& g, const Node& n) {
    493486          ignore_unused_variable_warning(n);
    494487          ignore_unused_variable_warning(g);
    495488        }
    496         /// Sets the iterator to the given arc.
    497 
    498         /// Sets the iterator to the given arc of the given graph.
    499         ///
     489        /// Arc -> InArcIt conversion
     490
     491        /// Sets the iterator to the value of the trivial iterator \c e.
     492        /// This feature necessitates that each time we
     493        /// iterate the arc-set, the iteration order is the same.
    500494        InArcIt(const Graph&, const Arc&) { }
    501495        /// Next incoming arc
    502496
    503         /// Assign the iterator to the next
    504         /// incoming arc of the corresponding node.
     497        /// Assign the iterator to the next inarc of the corresponding node.
     498        ///
    505499        InArcIt& operator++() { return *this; }
    506500      };
    507501
    508       /// \brief Standard graph map type for the nodes.
    509       ///
    510       /// Standard graph map type for the nodes.
    511       /// It conforms to the ReferenceMap concept.
     502      /// \brief Reference map of the nodes to type \c T.
     503      ///
     504      /// Reference map of the nodes to type \c T.
    512505      template<class T>
    513506      class NodeMap : public ReferenceMap<Node, T, T&, const T&>
    … …  
    515508      public:
    516509
    517         /// Constructor
    518         explicit NodeMap(const Graph&) { }
    519         /// Constructor with given initial value
     510        ///\e
     511        NodeMap(const Graph&) { }
     512        ///\e
    520513        NodeMap(const Graph&, T) { }
    521514
    … …  
    532525      };
    533526
    534       /// \brief Standard graph map type for the arcs.
    535       ///
    536       /// Standard graph map type for the arcs.
    537       /// It conforms to the ReferenceMap concept.
     527      /// \brief Reference map of the arcs to type \c T.
     528      ///
     529      /// Reference map of the arcs to type \c T.
    538530      template<class T>
    539531      class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
    … …  
    541533      public:
    542534
    543         /// Constructor
    544         explicit ArcMap(const Graph&) { }
    545         /// Constructor with given initial value
     535        ///\e
     536        ArcMap(const Graph&) { }
     537        ///\e
    546538        ArcMap(const Graph&, T) { }
    547 
    548539      private:
    549540        ///Copy constructor
    … …  
    558549      };
    559550
    560       /// \brief Standard graph map type for the edges.
    561       ///
    562       /// Standard graph map type for the edges.
    563       /// It conforms to the ReferenceMap concept.
     551      /// Reference map of the edges to type \c T.
     552
     553      /// Reference map of the edges to type \c T.
    564554      template<class T>
    565555      class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
    … …  
    567557      public:
    568558
    569         /// Constructor
    570         explicit EdgeMap(const Graph&) { }
    571         /// Constructor with given initial value
     559        ///\e
     560        EdgeMap(const Graph&) { }
     561        ///\e
    572562        EdgeMap(const Graph&, T) { }
    573 
    574563      private:
    575564        ///Copy constructor
    … …  
    584573      };
    585574
    586       /// \brief The first node of the edge.
    587       ///
    588       /// Returns the first node of the given edge.
    589       ///
    590       /// Edges don't have source and target nodes, however, methods
    591       /// u() and v() are used to query the two end-nodes of an edge.
    592       /// The orientation of an edge that arises this way is called
    593       /// the inherent direction, it is used to define the default
    594       /// direction for the corresponding arcs.
     575      /// \brief Direct the given edge.
     576      ///
     577      /// Direct the given edge. The returned arc source
     578      /// will be the given node.
     579      Arc direct(const Edge&, const Node&) const {
     580        return INVALID;
     581      }
     582
     583      /// \brief Direct the given edge.
     584      ///
     585      /// Direct the given edge. The returned arc
     586      /// represents the given edge and the direction comes
     587      /// from the bool parameter. The source of the edge and
     588      /// the directed arc is the same when the given bool is true.
     589      Arc direct(const Edge&, bool) const {
     590        return INVALID;
     591      }
     592
     593      /// \brief Returns true if the arc has default orientation.
     594      ///
     595      /// Returns whether the given directed arc is same orientation as
     596      /// the corresponding edge's default orientation.
     597      bool direction(Arc) const { return true; }
     598
     599      /// \brief Returns the opposite directed arc.
     600      ///
     601      /// Returns the opposite directed arc.
     602      Arc oppositeArc(Arc) const { return INVALID; }
     603
     604      /// \brief Opposite node on an arc
     605      ///
     606      /// \return The opposite of the given node on the given edge.
     607      Node oppositeNode(Node, Edge) const { return INVALID; }
     608
     609      /// \brief First node of the edge.
     610      ///
     611      /// \return The first node of the given edge.
     612      ///
     613      /// Naturally edges don't have direction and thus
     614      /// don't have source and target node. However we use \c u() and \c v()
     615      /// methods to query the two nodes of the arc. The direction of the
     616      /// arc which arises this way is called the inherent direction of the
     617      /// edge, and is used to define the "default" direction
     618      /// of the directed versions of the arcs.
    595619      /// \sa v()
    596620      /// \sa direction()
    597621      Node u(Edge) const { return INVALID; }
    598622
    599       /// \brief The second node of the edge.
    600       ///
    601       /// Returns the second node of the given edge.
    602       ///
    603       /// Edges don't have source and target nodes, however, methods
    604       /// u() and v() are used to query the two end-nodes of an edge.
    605       /// The orientation of an edge that arises this way is called
    606       /// the inherent direction, it is used to define the default
    607       /// direction for the corresponding arcs.
     623      /// \brief Second node of the edge.
     624      ///
     625      /// \return The second node of the given edge.
     626      ///
     627      /// Naturally edges don't have direction and thus
     628      /// don't have source and target node. However we use \c u() and \c v()
     629      /// methods to query the two nodes of the arc. The direction of the
     630      /// arc which arises this way is called the inherent direction of the
     631      /// edge, and is used to define the "default" direction
     632      /// of the directed versions of the arcs.
    608633      /// \sa u()
    609634      /// \sa direction()
    610635      Node v(Edge) const { return INVALID; }
    611636
    612       /// \brief The source node of the arc.
    613       ///
    614       /// Returns the source node of the given arc.
     637      /// \brief Source node of the directed arc.
    615638      Node source(Arc) const { return INVALID; }
    616639
    617       /// \brief The target node of the arc.
    618       ///
    619       /// Returns the target node of the given arc.
     640      /// \brief Target node of the directed arc.
    620641      Node target(Arc) const { return INVALID; }
    621642
    622       /// \brief The ID of the node.
    623       ///
    624       /// Returns the ID of the given node.
     643      /// \brief Returns the id of the node.
    625644      int id(Node) const { return -1; }
    626645
    627       /// \brief The ID of the edge.
    628       ///
    629       /// Returns the ID of the given edge.
     646      /// \brief Returns the id of the edge.
    630647      int id(Edge) const { return -1; }
    631648
    632       /// \brief The ID of the arc.
    633       ///
    634       /// Returns the ID of the given arc.
     649      /// \brief Returns the id of the arc.
    635650      int id(Arc) const { return -1; }
    636651
    637       /// \brief The node with the given ID.
    638       ///
    639       /// Returns the node with the given ID.
    640       /// \pre The argument should be a valid node ID in the graph.
     652      /// \brief Returns the node with the given id.
     653      ///
     654      /// \pre The argument should be a valid node id in the graph.
    641655      Node nodeFromId(int) const { return INVALID; }
    642656
    643       /// \brief The edge with the given ID.
    644       ///
    645       /// Returns the edge with the given ID.
    646       /// \pre The argument should be a valid edge ID in the graph.
     657      /// \brief Returns the edge with the given id.
     658      ///
     659      /// \pre The argument should be a valid edge id in the graph.
    647660      Edge edgeFromId(int) const { return INVALID; }
    648661
    649       /// \brief The arc with the given ID.
    650       ///
    651       /// Returns the arc with the given ID.
    652       /// \pre The argument should be a valid arc ID in the graph.
     662      /// \brief Returns the arc with the given id.
     663      ///
     664      /// \pre The argument should be a valid arc id in the graph.
    653665      Arc arcFromId(int) const { return INVALID; }
    654666
    655       /// \brief An upper bound on the node IDs.
    656       ///
    657       /// Returns an upper bound on the node IDs.
     667      /// \brief Returns an upper bound on the node IDs.
    658668      int maxNodeId() const { return -1; }
    659669
    660       /// \brief An upper bound on the edge IDs.
    661       ///
    662       /// Returns an upper bound on the edge IDs.
     670      /// \brief Returns an upper bound on the edge IDs.
    663671      int maxEdgeId() const { return -1; }
    664672
    665       /// \brief An upper bound on the arc IDs.
    666       ///
    667       /// Returns an upper bound on the arc IDs.
     673      /// \brief Returns an upper bound on the arc IDs.
    668674      int maxArcId() const { return -1; }
    669 
    670       /// \brief The direction of the arc.
    671       ///
    672       /// Returns \c true if the direction of the given arc is the same as
    673       /// the inherent orientation of the represented edge.
    674       bool direction(Arc) const { return true; }
    675 
    676       /// \brief Direct the edge.
    677       ///
    678       /// Direct the given edge. The returned arc
    679       /// represents the given edge and its direction comes
    680       /// from the bool parameter. If it is \c true, then the direction
    681       /// of the arc is the same as the inherent orientation of the edge.
    682       Arc direct(Edge, bool) const {
    683         return INVALID;
    684       }
    685 
    686       /// \brief Direct the edge.
    687       ///
    688       /// Direct the given edge. The returned arc represents the given
    689       /// edge and its source node is the given node.
    690       Arc direct(Edge, Node) const {
    691         return INVALID;
    692       }
    693 
    694       /// \brief The oppositely directed arc.
    695       ///
    696       /// Returns the oppositely directed arc representing the same edge.
    697       Arc oppositeArc(Arc) const { return INVALID; }
    698 
    699       /// \brief The opposite node on the edge.
    700       ///
    701       /// Returns the opposite node on the given edge.
    702       Node oppositeNode(Node, Edge) const { return INVALID; }
    703675
    704676      void first(Node&) const {}
    … …  
    734706      int maxId(Arc) const { return -1; }
    735707
    736       /// \brief The base node of the iterator.
    737       ///
    738       /// Returns the base node of the given incident edge iterator.
    739       Node baseNode(IncEdgeIt) const { return INVALID; }
    740 
    741       /// \brief The running node of the iterator.
    742       ///
    743       /// Returns the running node of the given incident edge iterator.
    744       Node runningNode(IncEdgeIt) const { return INVALID; }
    745 
    746       /// \brief The base node of the iterator.
    747       ///
    748       /// Returns the base node of the given outgoing arc iterator
    749       /// (i.e. the source node of the corresponding arc).
    750       Node baseNode(OutArcIt) const { return INVALID; }
    751 
    752       /// \brief The running node of the iterator.
    753       ///
    754       /// Returns the running node of the given outgoing arc iterator
    755       /// (i.e. the target node of the corresponding arc).
    756       Node runningNode(OutArcIt) const { return INVALID; }
    757 
    758       /// \brief The base node of the iterator.
    759       ///
    760       /// Returns the base node of the given incomming arc iterator
    761       /// (i.e. the target node of the corresponding arc).
    762       Node baseNode(InArcIt) const { return INVALID; }
    763 
    764       /// \brief The running node of the iterator.
    765       ///
    766       /// Returns the running node of the given incomming arc iterator
    767       /// (i.e. the source node of the corresponding arc).
    768       Node runningNode(InArcIt) const { return INVALID; }
     708      /// \brief Base node of the iterator
     709      ///
     710      /// Returns the base node (the source in this case) of the iterator
     711      Node baseNode(OutArcIt e) const {
     712        return source(e);
     713      }
     714      /// \brief Running node of the iterator
     715      ///
     716      /// Returns the running node (the target in this case) of the
     717      /// iterator
     718      Node runningNode(OutArcIt e) const {
     719        return target(e);
     720      }
     721
     722      /// \brief Base node of the iterator
     723      ///
     724      /// Returns the base node (the target in this case) of the iterator
     725      Node baseNode(InArcIt e) const {
     726        return target(e);
     727      }
     728      /// \brief Running node of the iterator
     729      ///
     730      /// Returns the running node (the source in this case) of the
     731      /// iterator
     732      Node runningNode(InArcIt e) const {
     733        return source(e);
     734      }
     735
     736      /// \brief Base node of the iterator
     737      ///
     738      /// Returns the base node of the iterator
     739      Node baseNode(IncEdgeIt) const {
     740        return INVALID;
     741      }
     742
     743      /// \brief Running node of the iterator
     744      ///
     745      /// Returns the running node of the iterator
     746      Node runningNode(IncEdgeIt) const {
     747        return INVALID;
     748      }
    769749
    770750      template <typename _Graph>
Note: See TracChangeset for help on using the changeset viewer.