COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 1136:8d066154b66a in lemon-0.x for src/lemon/concept/graph.h


Ignore:
Timestamp:
02/07/05 12:28:37 (20 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1535
Message:

Graph documentation

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/lemon/concept/graph.h

    r1030 r1136  
    2929namespace lemon {
    3030  namespace concept {
     31
    3132   
    3233    /// \addtogroup graph_concepts
    3334    /// @{
    3435
    35 //     /// An empty static graph class.
    36  
    37 //     /// This class provides all the common features of a graph structure,
    38 //     /// however completely without implementations and real data structures
    39 //     /// behind the interface.
    40 //     /// All graph algorithms should compile with this class, but it will not
    41 //     /// run properly, of course.
    42 //     ///
    43 //     /// It can be used for checking the interface compatibility,
    44 //     /// or it can serve as a skeleton of a new graph structure.
    45 //     ///
    46 //     /// Also, you will find here the full documentation of a certain graph
    47 //     /// feature, the documentation of a real graph imlementation
    48 //     /// like @ref ListGraph or
    49 //     /// @ref SmartGraph will just refer to this structure.
    50 //     ///
    51 //     /// \todo A pages describing the concept of concept description would
    52 //     /// be nice.
    53 //     class StaticGraph
    54 //     {
    55 //     public:
    56 //       /// Defalult constructor.
    57 
    58 //       /// Defalult constructor.
    59 //       ///
    60 //       StaticGraph() { }
    61 //       ///Copy consructor.
    62 
    63 // //       ///\todo It is not clear, what we expect from a copy constructor.
    64 // //       ///E.g. How to assign the nodes/edges to each other? What about maps?
    65 // //       StaticGraph(const StaticGraph& g) { }
    66 
    67 //       /// The base type of node iterators,
    68 //       /// or in other words, the trivial node iterator.
    69 
    70 //       /// This is the base type of each node iterator,
    71 //       /// thus each kind of node iterator converts to this.
    72 //       /// More precisely each kind of node iterator should be inherited
    73 //       /// from the trivial node iterator.
    74 //       class Node {
    75 //       public:
    76 //      /// Default constructor
    77 
    78 //      /// @warning The default constructor sets the iterator
    79 //      /// to an undefined value.
    80 //      Node() { }
    81 //      /// Copy constructor.
    82 
    83 //      /// Copy constructor.
    84 //      ///
    85 //      Node(const Node&) { }
    86 
    87 //      /// Invalid constructor \& conversion.
    88 
    89 //      /// This constructor initializes the iterator to be invalid.
    90 //      /// \sa Invalid for more details.
    91 //      Node(Invalid) { }
    92 //      /// Equality operator
    93 
    94 //      /// Two iterators are equal if and only if they point to the
    95 //      /// same object or both are invalid.
    96 //      bool operator==(Node) const { return true; }
    97 
    98 //      /// Inequality operator
    99        
    100 //      /// \sa operator==(Node n)
    101 //      ///
    102 //      bool operator!=(Node) const { return true; }
    103 
    104 //       };
    105    
    106 //       /// This iterator goes through each node.
    107 
    108 //       /// This iterator goes through each node.
    109 //       /// Its usage is quite simple, for example you can count the number
    110 //       /// of nodes in graph \c g of type \c Graph like this:
    111 //       /// \code
    112 //       /// int count=0;
    113 //       /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count;
    114 //       /// \endcode
    115 //       class NodeIt : public Node {
    116 //       public:
    117 //      /// Default constructor
    118 
    119 //      /// @warning The default constructor sets the iterator
    120 //      /// to an undefined value.
    121 //      NodeIt() { }
    122 //      /// Copy constructor.
    123        
    124 //      /// Copy constructor.
    125 //      ///
    126 //      NodeIt(const NodeIt&) { }
    127 //      /// Invalid constructor \& conversion.
    128 
    129 //      /// Initialize the iterator to be invalid.
    130 //      /// \sa Invalid for more details.
    131 //      NodeIt(Invalid) { }
    132 //      /// Sets the iterator to the first node.
    133 
    134 //      /// Sets the iterator to the first node of \c g.
    135 //      ///
    136 //      NodeIt(const StaticGraph& g) { }
    137 //      /// Node -> NodeIt conversion.
    138 
    139 //      /// Sets the iterator to the node of \c g pointed by the trivial
    140 //      /// iterator n.
    141 //      /// This feature necessitates that each time we
    142 //      /// iterate the edge-set, the iteration order is the same.
    143 //      NodeIt(const StaticGraph& g, const Node& n) { }
    144 //      /// Next node.
    145 
    146 //      /// Assign the iterator to the next node.
    147 //      ///
    148 //      NodeIt& operator++() { return *this; }
    149 //       };
    150    
    151    
    152 //       /// The base type of the edge iterators.
    153 
    154 //       /// The base type of the edge iterators.
    155 //       ///
    156 //       class Edge {
    157 //       public:
    158 //      /// Default constructor
    159 
    160 //      /// @warning The default constructor sets the iterator
    161 //      /// to an undefined value.
    162 //      Edge() { }
    163 //      /// Copy constructor.
    164 
    165 //      /// Copy constructor.
    166 //      ///
    167 //      Edge(const Edge&) { }
    168 //      /// Initialize the iterator to be invalid.
    169 
    170 //      /// Initialize the iterator to be invalid.
    171 //      ///
    172 //      Edge(Invalid) { }
    173 //      /// Equality operator
    174 
    175 //      /// Two iterators are equal if and only if they point to the
    176 //      /// same object or both are invalid.
    177 //      bool operator==(Edge) const { return true; }
    178 //      /// Inequality operator
    179 
    180 //      /// \sa operator==(Node n)
    181 //      ///
    182 //      bool operator!=(Edge) const { return true; }
    183 //       };
    184    
    185 //       /// This iterator goes trough the outgoing edges of a node.
    186 
    187 //       /// This iterator goes trough the \e outgoing edges of a certain node
    188 //       /// of a graph.
    189 //       /// Its usage is quite simple, for example you can count the number
    190 //       /// of outgoing edges of a node \c n
    191 //       /// in graph \c g of type \c Graph as follows.
    192 //       /// \code
    193 //       /// int count=0;
    194 //       /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
    195 //       /// \endcode
    196    
    197 //       class OutEdgeIt : public Edge {
    198 //       public:
    199 //      /// Default constructor
    200 
    201 //      /// @warning The default constructor sets the iterator
    202 //      /// to an undefined value.
    203 //      OutEdgeIt() { }
    204 //      /// Copy constructor.
    205 
    206 //      /// Copy constructor.
    207 //      ///
    208 //      OutEdgeIt(const OutEdgeIt&) { }
    209 //      /// Initialize the iterator to be invalid.
    210 
    211 //      /// Initialize the iterator to be invalid.
    212 //      ///
    213 //      OutEdgeIt(Invalid) { }
    214 //      /// This constructor sets the iterator to first outgoing edge.
    215    
    216 //      /// This constructor set the iterator to the first outgoing edge of
    217 //      /// node
    218 //      ///@param n the node
    219 //      ///@param g the graph
    220 //      OutEdgeIt(const StaticGraph& g, const Node& n) { }
    221 //      /// Edge -> OutEdgeIt conversion
    222 
    223 //      /// Sets the iterator to the value of the trivial iterator \c e.
    224 //      /// This feature necessitates that each time we
    225 //      /// iterate the edge-set, the iteration order is the same.
    226 //      OutEdgeIt(const StaticGraph& g, const Edge& e) { }
    227 //      ///Next outgoing edge
    228        
    229 //      /// Assign the iterator to the next
    230 //      /// outgoing edge of the corresponding node.
    231 //      OutEdgeIt& operator++() { return *this; }
    232 //       };
    233 
    234 //       /// This iterator goes trough the incoming edges of a node.
    235 
    236 //       /// This iterator goes trough the \e incoming edges of a certain node
    237 //       /// of a graph.
    238 //       /// Its usage is quite simple, for example you can count the number
    239 //       /// of outgoing edges of a node \c n
    240 //       /// in graph \c g of type \c Graph as follows.
    241 //       /// \code
    242 //       /// int count=0;
    243 //       /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
    244 //       /// \endcode
    245 
    246 //       class InEdgeIt : public Edge {
    247 //       public:
    248 //      /// Default constructor
    249 
    250 //      /// @warning The default constructor sets the iterator
    251 //      /// to an undefined value.
    252 //      InEdgeIt() { }
    253 //      /// Copy constructor.
    254 
    255 //      /// Copy constructor.
    256 //      ///
    257 //      InEdgeIt(const InEdgeIt&) { }
    258 //      /// Initialize the iterator to be invalid.
    259 
    260 //      /// Initialize the iterator to be invalid.
    261 //      ///
    262 //      InEdgeIt(Invalid) { }
    263 //      /// This constructor sets the iterator to first incoming edge.
    264    
    265 //      /// This constructor set the iterator to the first incoming edge of
    266 //      /// node
    267 //      ///@param n the node
    268 //      ///@param g the graph
    269 //      InEdgeIt(const StaticGraph& g, const Node& n) { }
    270 //      /// Edge -> InEdgeIt conversion
    271 
    272 //      /// Sets the iterator to the value of the trivial iterator \c e.
    273 //      /// This feature necessitates that each time we
    274 //      /// iterate the edge-set, the iteration order is the same.
    275 //      InEdgeIt(const StaticGraph& g, const Edge& n) { }
    276 //      /// Next incoming edge
    277 
    278 //      /// Assign the iterator to the next inedge of the corresponding node.
    279 //      ///
    280 //      InEdgeIt& operator++() { return *this; }
    281 //       };
    282 //       /// This iterator goes through each edge.
    283 
    284 //       /// This iterator goes through each edge of a graph.
    285 //       /// Its usage is quite simple, for example you can count the number
    286 //       /// of edges in a graph \c g of type \c Graph as follows:
    287 //       /// \code
    288 //       /// int count=0;
    289 //       /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
    290 //       /// \endcode
    291 //       class EdgeIt : public Edge {
    292 //       public:
    293 //      /// Default constructor
    294 
    295 //      /// @warning The default constructor sets the iterator
    296 //      /// to an undefined value.
    297 //      EdgeIt() { }
    298 //      /// Copy constructor.
    299 
    300 //      /// Copy constructor.
    301 //      ///
    302 //      EdgeIt(const EdgeIt&) { }
    303 //      /// Initialize the iterator to be invalid.
    304 
    305 //      /// Initialize the iterator to be invalid.
    306 //      ///
    307 //      EdgeIt(Invalid) { }
    308 //      /// This constructor sets the iterator to first edge.
    309    
    310 //      /// This constructor set the iterator to the first edge of
    311 //      /// node
    312 //      ///@param g the graph
    313 //      EdgeIt(const StaticGraph& g) { }
    314 //      /// Edge -> EdgeIt conversion
    315 
    316 //      /// Sets the iterator to the value of the trivial iterator \c e.
    317 //      /// This feature necessitates that each time we
    318 //      /// iterate the edge-set, the iteration order is the same.
    319 //      EdgeIt(const StaticGraph&, const Edge&) { }
    320 //      ///Next edge
    321        
    322 //      /// Assign the iterator to the next
    323 //      /// edge of the corresponding node.
    324 //      EdgeIt& operator++() { return *this; }
    325 //       };
    326 //       ///Gives back the target node of an edge.
    327 
    328 //       ///Gives back the target node of an edge.
    329 //       ///
    330 //       Node target(Edge) const { return INVALID; }
    331 //       ///Gives back the source node of an edge.
    332 
    333 //       ///Gives back the source node of an edge.
    334 //       ///
    335 //       Node source(Edge) const { return INVALID; }
    336 //       /// Read write map of the nodes to type \c T.
    337 
    338 //       /// \ingroup concept
    339 //       /// ReadWrite map of the nodes to type \c T.
    340 //       /// \sa Reference
    341 //       /// \warning Making maps that can handle bool type (NodeMap<bool>)
    342 //       /// needs some extra attention!
    343 //       template<class T>
    344 //       class NodeMap : public ReadWriteMap< Node, T >
    345 //       {
    346 //       public:
    347 
    348 //      ///\e
    349 //      NodeMap(const StaticGraph&) { }
    350 //      ///\e
    351 //      NodeMap(const StaticGraph&, T) { }
    352 
    353 //      ///Copy constructor
    354 //      NodeMap(const NodeMap&) { }
    355 //      ///Assignment operator
    356 //      NodeMap& operator=(const NodeMap&) { return *this; }
    357 //      // \todo fix this concept
    358 //       };
    359 
    360 //       /// Read write map of the edges to type \c T.
    361 
    362 //       /// \ingroup concept
    363 //       ///Reference map of the edges to type \c T.
    364 //       /// \sa Reference
    365 //       /// \warning Making maps that can handle bool type (EdgeMap<bool>)
    366 //       /// needs some extra attention!
    367 //       template<class T>
    368 //       class EdgeMap : public ReadWriteMap<Edge,T>
    369 //       {
    370 //       public:
    371 
    372 //      ///\e
    373 //      EdgeMap(const StaticGraph&) { }
    374 //      ///\e
    375 //      EdgeMap(const StaticGraph&, T) { }
    376 //      ///Copy constructor
    377 //      EdgeMap(const EdgeMap&) { }
    378 //      ///Assignment operator
    379 //      EdgeMap& operator=(const EdgeMap&) { return *this; }
    380 //      // \todo fix this concept   
    381 //       };
    382 //     };
    383 
    384 //     /// An empty non-static graph class.
    385    
    386 //     /// This class provides everything that \ref StaticGraph
    387 //     /// with additional functionality which enables to build a
    388 //     /// graph from scratch.
    389 //     class ExtendableGraph : public StaticGraph
    390 //     {
    391 //     public:
    392 //       /// Defalult constructor.
    393 
    394 //       /// Defalult constructor.
    395 //       ///
    396 //       ExtendableGraph() { }
    397 //       ///Add a new node to the graph.
    398 
    399 //       /// \return the new node.
    400 //       ///
    401 //       Node addNode() { return INVALID; }
    402 //       ///Add a new edge to the graph.
    403 
    404 //       ///Add a new edge to the graph with source node \c s
    405 //       ///and target node \c t.
    406 //       ///\return the new edge.
    407 //       Edge addEdge(Node s, Node t) { return INVALID; }
    408    
    409 //       /// Resets the graph.
    410 
    411 //       /// This function deletes all edges and nodes of the graph.
    412 //       /// It also frees the memory allocated to store them.
    413 //       /// \todo It might belong to \ref ErasableGraph.
    414 //       void clear() { }
    415 //     };
    416 
    417 //     /// An empty erasable graph class.
    418  
    419 //     /// This class is an extension of \ref ExtendableGraph. It also makes it
    420 //     /// possible to erase edges or nodes.
    421 //     class ErasableGraph : public ExtendableGraph
    422 //     {
    423 //     public:
    424 //       /// Defalult constructor.
    425 
    426 //       /// Defalult constructor.
    427 //       ///
    428 //       ErasableGraph() { }
    429 //       /// Deletes a node.
    430 
    431 //       /// Deletes node \c n node.
    432 //       ///
    433 //       void erase(Node n) { }
    434 //       /// Deletes an edge.
    435 
    436 //       /// Deletes edge \c e edge.
    437 //       ///
    438 //       void erase(Edge e) { }
    439 //     };
    440 
    441    
    442     /************* New GraphBase stuff **************/
    443 
    444 
    445     /// A minimal GraphBase concept
    446 
    447     /// This class describes a minimal concept which can be extended to a
    448     /// full-featured graph with \ref GraphFactory.
    449     class GraphBase {
    450     public:
    451 
    452       GraphBase() {}
    453 
    454       /// \bug Should we demand that Node and Edge be subclasses of the
    455       /// Graph class???
    456 
    457       typedef GraphItem<'n'> Node;
    458       typedef GraphItem<'e'> Edge;
    459 
    460 //       class Node : public BaseGraphItem<'n'> {};
    461 //       class Edge : public BaseGraphItem<'e'> {};
    462 
    463       // Graph operation
    464       void firstNode(Node &n) const { }
    465       void firstEdge(Edge &e) const { }
    466 
    467       void firstOutEdge(Edge &e, Node) const { }
    468       void firstInEdge(Edge &e, Node) const { }
    469 
    470       void nextNode(Node &n) const { }
    471       void nextEdge(Edge &e) const { }
    472 
    473 
    474       // Question: isn't it reasonable if this methods have a Node
    475       // parameter? Like this:
    476       // Edge& nextOut(Edge &e, Node) const { return e; }
    477       void nextOutEdge(Edge &e) const { }
    478       void nextInEdge(Edge &e) const { }
    479 
    480       Node target(Edge) const { return Node(); }
    481       Node source(Edge) const { return Node(); }
    482      
    483 
    484       // Do we need id, nodeNum, edgeNum and co. in this basic graphbase
    485       // concept?
    486 
    487 
    488       // Maps.
    489       //
    490       // We need a special slimer concept which does not provide maps (it
    491       // wouldn't be strictly slimer, cause for map-factory id() & friends
    492       // a required...)
    493 
    494       template<typename T>
    495       class NodeMap : public GraphMap<GraphBase, Node, T> {};
    496 
    497       template<typename T>
    498       class EdgeMap : public GraphMap<GraphBase, Node, T> {};
    499     };
    500 
    501 
    502 
    503 
    50436    /**************** The full-featured graph concepts ****************/
    50537
    506    
    507     class StaticGraph
     38
     39    /// \brief Modular builded static graph class.
     40    ///     
     41    /// It should be the same as the \c StaticGraph class.
     42    class _StaticGraph
    50843      :  virtual public BaseGraphComponent,
    50944         public IterableGraphComponent, public MappableGraphComponent {
    … …  
    52156    };
    52257
    523     class ExtendableGraph
    524       :  virtual public BaseGraphComponent, public StaticGraph,
     58    /// \brief Modular builded extendable graph class.
     59    ///     
     60    /// It should be the same as the \c ExtendableGraph class.
     61    class _ExtendableGraph
     62      :  virtual public BaseGraphComponent, public _StaticGraph,
    52563         public ExtendableGraphComponent, public ClearableGraphComponent {
    52664    public:
    … …  
    53169      struct Constraints {
    53270        void constraints() {
    533           checkConcept<StaticGraph, _Graph >();
     71          checkConcept<_StaticGraph, _Graph >();
    53472          checkConcept<ExtendableGraphComponent, _Graph >();
    53573          checkConcept<ClearableGraphComponent, _Graph >();
    … …  
    53876    };
    53977
    540     class ErasableGraph
    541       :  virtual public BaseGraphComponent, public ExtendableGraph,
     78    /// \brief Modular builded erasable graph class.
     79    ///     
     80    /// It should be the same as the \c ErasableGraph class.
     81    class _ErasableGraph
     82      :  virtual public BaseGraphComponent, public _ExtendableGraph,
    54283         public ErasableGraphComponent {
    54384    public:
    … …  
    54889      struct Constraints {
    54990        void constraints() {
    550           checkConcept<ExtendableGraph, _Graph >();
     91          checkConcept<_ExtendableGraph, _Graph >();
    55192          checkConcept<ErasableGraphComponent, _Graph >();
    55293        }
    55394      };
    55495    };
     96
     97    /// An empty static graph class.
     98 
     99    /// This class provides all the common features of a graph structure,
     100    /// however completely without implementations and real data structures
     101    /// behind the interface.
     102    /// All graph algorithms should compile with this class, but it will not
     103    /// run properly, of course.
     104    ///
     105    /// It can be used for checking the interface compatibility,
     106    /// or it can serve as a skeleton of a new graph structure.
     107    ///
     108    /// Also, you will find here the full documentation of a certain graph
     109    /// feature, the documentation of a real graph imlementation
     110    /// like @ref ListGraph or
     111    /// @ref SmartGraph will just refer to this structure.
     112    ///
     113    /// \todo A pages describing the concept of concept description would
     114    /// be nice.
     115    class StaticGraph
     116    {
     117    public:
     118      /// Defalult constructor.
     119
     120      /// Defalult constructor.
     121      ///
     122      StaticGraph() { }
     123      ///Copy consructor.
     124
     125//       ///\todo It is not clear, what we expect from a copy constructor.
     126//       ///E.g. How to assign the nodes/edges to each other? What about maps?
     127//       StaticGraph(const StaticGraph& g) { }
     128
     129      /// The base type of node iterators,
     130      /// or in other words, the trivial node iterator.
     131
     132      /// This is the base type of each node iterator,
     133      /// thus each kind of node iterator converts to this.
     134      /// More precisely each kind of node iterator should be inherited
     135      /// from the trivial node iterator.
     136      class Node {
     137      public:
     138        /// Default constructor
     139
     140        /// @warning The default constructor sets the iterator
     141        /// to an undefined value.
     142        Node() { }
     143        /// Copy constructor.
     144
     145        /// Copy constructor.
     146        ///
     147        Node(const Node&) { }
     148
     149        /// Invalid constructor \& conversion.
     150
     151        /// This constructor initializes the iterator to be invalid.
     152        /// \sa Invalid for more details.
     153        Node(Invalid) { }
     154        /// Equality operator
     155
     156        /// Two iterators are equal if and only if they point to the
     157        /// same object or both are invalid.
     158        bool operator==(Node) const { return true; }
     159
     160        /// Inequality operator
     161       
     162        /// \sa operator==(Node n)
     163        ///
     164        bool operator!=(Node) const { return true; }
     165
     166      };
     167   
     168      /// This iterator goes through each node.
     169
     170      /// This iterator goes through each node.
     171      /// Its usage is quite simple, for example you can count the number
     172      /// of nodes in graph \c g of type \c Graph like this:
     173      /// \code
     174      /// int count=0;
     175      /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count;
     176      /// \endcode
     177      class NodeIt : public Node {
     178      public:
     179        /// Default constructor
     180
     181        /// @warning The default constructor sets the iterator
     182        /// to an undefined value.
     183        NodeIt() { }
     184        /// Copy constructor.
     185       
     186        /// Copy constructor.
     187        ///
     188        NodeIt(const NodeIt&) { }
     189        /// Invalid constructor \& conversion.
     190
     191        /// Initialize the iterator to be invalid.
     192        /// \sa Invalid for more details.
     193        NodeIt(Invalid) { }
     194        /// Sets the iterator to the first node.
     195
     196        /// Sets the iterator to the first node of \c g.
     197        ///
     198        NodeIt(const StaticGraph& g) { }
     199        /// Node -> NodeIt conversion.
     200
     201        /// Sets the iterator to the node of \c g pointed by the trivial
     202        /// iterator n.
     203        /// This feature necessitates that each time we
     204        /// iterate the edge-set, the iteration order is the same.
     205        NodeIt(const StaticGraph& g, const Node& n) { }
     206        /// Next node.
     207
     208        /// Assign the iterator to the next node.
     209        ///
     210        NodeIt& operator++() { return *this; }
     211      };
     212   
     213   
     214      /// The base type of the edge iterators.
     215
     216      /// The base type of the edge iterators.
     217      ///
     218      class Edge {
     219      public:
     220        /// Default constructor
     221
     222        /// @warning The default constructor sets the iterator
     223        /// to an undefined value.
     224        Edge() { }
     225        /// Copy constructor.
     226
     227        /// Copy constructor.
     228        ///
     229        Edge(const Edge&) { }
     230        /// Initialize the iterator to be invalid.
     231
     232        /// Initialize the iterator to be invalid.
     233        ///
     234        Edge(Invalid) { }
     235        /// Equality operator
     236
     237        /// Two iterators are equal if and only if they point to the
     238        /// same object or both are invalid.
     239        bool operator==(Edge) const { return true; }
     240        /// Inequality operator
     241
     242        /// \sa operator==(Node n)
     243        ///
     244        bool operator!=(Edge) const { return true; }
     245      };
     246   
     247      /// This iterator goes trough the outgoing edges of a node.
     248
     249      /// This iterator goes trough the \e outgoing edges of a certain node
     250      /// of a graph.
     251      /// Its usage is quite simple, for example you can count the number
     252      /// of outgoing edges of a node \c n
     253      /// in graph \c g of type \c Graph as follows.
     254      /// \code
     255      /// int count=0;
     256      /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
     257      /// \endcode
     258   
     259      class OutEdgeIt : public Edge {
     260      public:
     261        /// Default constructor
     262
     263        /// @warning The default constructor sets the iterator
     264        /// to an undefined value.
     265        OutEdgeIt() { }
     266        /// Copy constructor.
     267
     268        /// Copy constructor.
     269        ///
     270        OutEdgeIt(const OutEdgeIt&) { }
     271        /// Initialize the iterator to be invalid.
     272
     273        /// Initialize the iterator to be invalid.
     274        ///
     275        OutEdgeIt(Invalid) { }
     276        /// This constructor sets the iterator to first outgoing edge.
     277   
     278        /// This constructor set the iterator to the first outgoing edge of
     279        /// node
     280        ///@param n the node
     281        ///@param g the graph
     282        OutEdgeIt(const StaticGraph& g, const Node& n) { }
     283        /// Edge -> OutEdgeIt conversion
     284
     285        /// Sets the iterator to the value of the trivial iterator \c e.
     286        /// This feature necessitates that each time we
     287        /// iterate the edge-set, the iteration order is the same.
     288        OutEdgeIt(const StaticGraph& g, const Edge& e) { }
     289        ///Next outgoing edge
     290       
     291        /// Assign the iterator to the next
     292        /// outgoing edge of the corresponding node.
     293        OutEdgeIt& operator++() { return *this; }
     294      };
     295
     296      /// This iterator goes trough the incoming edges of a node.
     297
     298      /// This iterator goes trough the \e incoming edges of a certain node
     299      /// of a graph.
     300      /// Its usage is quite simple, for example you can count the number
     301      /// of outgoing edges of a node \c n
     302      /// in graph \c g of type \c Graph as follows.
     303      /// \code
     304      /// int count=0;
     305      /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
     306      /// \endcode
     307
     308      class InEdgeIt : public Edge {
     309      public:
     310        /// Default constructor
     311
     312        /// @warning The default constructor sets the iterator
     313        /// to an undefined value.
     314        InEdgeIt() { }
     315        /// Copy constructor.
     316
     317        /// Copy constructor.
     318        ///
     319        InEdgeIt(const InEdgeIt&) { }
     320        /// Initialize the iterator to be invalid.
     321
     322        /// Initialize the iterator to be invalid.
     323        ///
     324        InEdgeIt(Invalid) { }
     325        /// This constructor sets the iterator to first incoming edge.
     326   
     327        /// This constructor set the iterator to the first incoming edge of
     328        /// node
     329        ///@param n the node
     330        ///@param g the graph
     331        InEdgeIt(const StaticGraph& g, const Node& n) { }
     332        /// Edge -> InEdgeIt conversion
     333
     334        /// Sets the iterator to the value of the trivial iterator \c e.
     335        /// This feature necessitates that each time we
     336        /// iterate the edge-set, the iteration order is the same.
     337        InEdgeIt(const StaticGraph& g, const Edge& n) { }
     338        /// Next incoming edge
     339
     340        /// Assign the iterator to the next inedge of the corresponding node.
     341        ///
     342        InEdgeIt& operator++() { return *this; }
     343      };
     344      /// This iterator goes through each edge.
     345
     346      /// This iterator goes through each edge of a graph.
     347      /// Its usage is quite simple, for example you can count the number
     348      /// of edges in a graph \c g of type \c Graph as follows:
     349      /// \code
     350      /// int count=0;
     351      /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
     352      /// \endcode
     353      class EdgeIt : public Edge {
     354      public:
     355        /// Default constructor
     356
     357        /// @warning The default constructor sets the iterator
     358        /// to an undefined value.
     359        EdgeIt() { }
     360        /// Copy constructor.
     361
     362        /// Copy constructor.
     363        ///
     364        EdgeIt(const EdgeIt&) { }
     365        /// Initialize the iterator to be invalid.
     366
     367        /// Initialize the iterator to be invalid.
     368        ///
     369        EdgeIt(Invalid) { }
     370        /// This constructor sets the iterator to first edge.
     371   
     372        /// This constructor set the iterator to the first edge of
     373        /// node
     374        ///@param g the graph
     375        EdgeIt(const StaticGraph& g) { }
     376        /// Edge -> EdgeIt conversion
     377
     378        /// Sets the iterator to the value of the trivial iterator \c e.
     379        /// This feature necessitates that each time we
     380        /// iterate the edge-set, the iteration order is the same.
     381        EdgeIt(const StaticGraph&, const Edge&) { }
     382        ///Next edge
     383       
     384        /// Assign the iterator to the next
     385        /// edge of the corresponding node.
     386        EdgeIt& operator++() { return *this; }
     387      };
     388      ///Gives back the target node of an edge.
     389
     390      ///Gives back the target node of an edge.
     391      ///
     392      Node target(Edge) const { return INVALID; }
     393      ///Gives back the source node of an edge.
     394
     395      ///Gives back the source node of an edge.
     396      ///
     397      Node source(Edge) const { return INVALID; }
     398      /// Read write map of the nodes to type \c T.
     399
     400      /// \ingroup concept
     401      /// ReadWrite map of the nodes to type \c T.
     402      /// \sa Reference
     403      /// \warning Making maps that can handle bool type (NodeMap<bool>)
     404      /// needs some extra attention!
     405      template<class T>
     406      class NodeMap : public ReadWriteMap< Node, T >
     407      {
     408      public:
     409
     410        ///\e
     411        NodeMap(const StaticGraph&) { }
     412        ///\e
     413        NodeMap(const StaticGraph&, T) { }
     414
     415        ///Copy constructor
     416        NodeMap(const NodeMap&) { }
     417        ///Assignment operator
     418        NodeMap& operator=(const NodeMap&) { return *this; }
     419        // \todo fix this concept
     420      };
     421
     422      /// Read write map of the edges to type \c T.
     423
     424      /// \ingroup concept
     425      ///Reference map of the edges to type \c T.
     426      /// \sa Reference
     427      /// \warning Making maps that can handle bool type (EdgeMap<bool>)
     428      /// needs some extra attention!
     429      template<class T>
     430      class EdgeMap : public ReadWriteMap<Edge,T>
     431      {
     432      public:
     433
     434        ///\e
     435        EdgeMap(const StaticGraph&) { }
     436        ///\e
     437        EdgeMap(const StaticGraph&, T) { }
     438        ///Copy constructor
     439        EdgeMap(const EdgeMap&) { }
     440        ///Assignment operator
     441        EdgeMap& operator=(const EdgeMap&) { return *this; }
     442        // \todo fix this concept   
     443      };
     444
     445      template <typename _Graph>
     446      struct Constraints : public _StaticGraph::Constraints<_Graph> {};
     447
     448    };
     449
     450    /// An empty non-static graph class.
     451   
     452    /// This class provides everything that \ref StaticGraph
     453    /// with additional functionality which enables to build a
     454    /// graph from scratch.
     455    class ExtendableGraph : public StaticGraph
     456    {
     457    public:
     458      /// Defalult constructor.
     459
     460      /// Defalult constructor.
     461      ///
     462      ExtendableGraph() { }
     463      ///Add a new node to the graph.
     464
     465      /// \return the new node.
     466      ///
     467      Node addNode() { return INVALID; }
     468      ///Add a new edge to the graph.
     469
     470      ///Add a new edge to the graph with source node \c s
     471      ///and target node \c t.
     472      ///\return the new edge.
     473      Edge addEdge(Node s, Node t) { return INVALID; }
     474   
     475      /// Resets the graph.
     476
     477      /// This function deletes all edges and nodes of the graph.
     478      /// It also frees the memory allocated to store them.
     479      /// \todo It might belong to \ref ErasableGraph.
     480      void clear() { }
     481
     482      template <typename _Graph>
     483      struct Constraints : public _ExtendableGraph::Constraints<_Graph> {};
     484
     485    };
     486
     487    /// An empty erasable graph class.
     488 
     489    /// This class is an extension of \ref ExtendableGraph. It also makes it
     490    /// possible to erase edges or nodes.
     491    class ErasableGraph : public ExtendableGraph
     492    {
     493    public:
     494      /// Defalult constructor.
     495
     496      /// Defalult constructor.
     497      ///
     498      ErasableGraph() { }
     499      /// Deletes a node.
     500
     501      /// Deletes node \c n node.
     502      ///
     503      void erase(Node n) { }
     504      /// Deletes an edge.
     505
     506      /// Deletes edge \c e edge.
     507      ///
     508      void erase(Edge e) { }
     509
     510      template <typename _Graph>
     511      struct Constraints : public _ErasableGraph::Constraints<_Graph> {};
     512
     513    };
     514
     515   
     516    /************* New GraphBase stuff **************/
     517
     518
     519//     /// A minimal GraphBase concept
     520
     521//     /// This class describes a minimal concept which can be extended to a
     522//     /// full-featured graph with \ref GraphFactory.
     523//     class GraphBase {
     524//     public:
     525
     526//       GraphBase() {}
     527
     528//       /// \bug Should we demand that Node and Edge be subclasses of the
     529//       /// Graph class???
     530
     531//       typedef GraphItem<'n'> Node;
     532//       typedef GraphItem<'e'> Edge;
     533
     534// //       class Node : public BaseGraphItem<'n'> {};
     535// //       class Edge : public BaseGraphItem<'e'> {};
     536
     537//       // Graph operation
     538//       void firstNode(Node &n) const { }
     539//       void firstEdge(Edge &e) const { }
     540
     541//       void firstOutEdge(Edge &e, Node) const { }
     542//       void firstInEdge(Edge &e, Node) const { }
     543
     544//       void nextNode(Node &n) const { }
     545//       void nextEdge(Edge &e) const { }
     546
     547
     548//       // Question: isn't it reasonable if this methods have a Node
     549//       // parameter? Like this:
     550//       // Edge& nextOut(Edge &e, Node) const { return e; }
     551//       void nextOutEdge(Edge &e) const { }
     552//       void nextInEdge(Edge &e) const { }
     553
     554//       Node target(Edge) const { return Node(); }
     555//       Node source(Edge) const { return Node(); }
     556     
     557
     558//       // Do we need id, nodeNum, edgeNum and co. in this basic graphbase
     559//       // concept?
     560
     561
     562//       // Maps.
     563//       //
     564//       // We need a special slimer concept which does not provide maps (it
     565//       // wouldn't be strictly slimer, cause for map-factory id() & friends
     566//       // a required...)
     567
     568//       template<typename T>
     569//       class NodeMap : public GraphMap<GraphBase, Node, T> {};
     570
     571//       template<typename T>
     572//       class EdgeMap : public GraphMap<GraphBase, Node, T> {};
     573//     };
    555574
    556575    // @}
Note: See TracChangeset for help on using the changeset viewer.