COIN-OR::LEMON - Graph Library

Changeset 732:33cbc0635e92 in lemon-0.x for src/hugo


Ignore:
Timestamp:
07/22/04 21:59:18 (20 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@988
Message:

Skeletons have been simplified.
"Optional features" have been deleted.
Map skeletons have been renamed.

Location:
src/hugo/skeletons
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/skeletons/graph.h

    r542 r732  
    77
    88#include <hugo/invalid.h>
     9#include <hugo/skeletons/maps.h>
    910
    1011/// The namespace of HugoLib
    1112namespace hugo {
    12 
    13   // @defgroup empty_graph The GraphSkeleton class
    14   // @{
    15 
    16   /// An empty graph class.
    17  
    18   /// This class provides all the common features of a graph structure,
    19   /// however completely without implementations and real data structures
    20   /// behind the interface.
    21   /// All graph algorithms should compile with this class, but it will not
    22   /// run properly, of course.
    23   ///
    24   /// It can be used for checking the interface compatibility,
    25   /// or it can serve as a skeleton of a new graph structure.
    26   ///
    27   /// Also, you will find here the full documentation of a certain graph
    28   /// feature, the documentation of a real graph imlementation
    29   /// like @ref ListGraph or
    30   /// @ref SmartGraph will just refer to this structure.
    31   class GraphSkeleton
    32   {
    33   public:
    34     /// Defalult constructor.
    35     GraphSkeleton() {}
    36     ///Copy consructor.
    37 
    38     ///\todo It is not clear, what we expect from a copy constructor.
    39     ///E.g. How to assign the nodes/edges to each other? What about maps?
    40     GraphSkeleton(const GraphSkeleton &G) {}
    41 
    42     /// The base type of the node iterators.
    43 
    44     /// This is the base type of each node iterators,
    45     /// thus each kind of node iterator will convert to this.
    46     class Node {
    47     public:
    48       /// @warning The default constructor sets the iterator
    49       /// to an undefined value.
    50       Node() {}   //FIXME
    51       /// Invalid constructor \& conversion.
    52 
    53       /// This constructor initializes the iterator to be invalid.
    54       /// \sa Invalid for more details.
    55 
    56       Node(Invalid) {}
    57       //Node(const Node &) {}
    58 
    59       /// Two iterators are equal if and only if they point to the
    60       /// same object or both are invalid.
    61       bool operator==(Node) const { return true; }
    62 
    63       /// \sa \ref operator==(Node n)
    64       ///
    65       bool operator!=(Node) const { return true; }
    66 
    67       bool operator<(Node) const { return true; }
    68     };
    69    
    70     /// This iterator goes through each node.
    71 
    72     /// This iterator goes through each node.
    73     /// Its usage is quite simple, for example you can count the number
    74     /// of nodes in graph \c G of type \c Graph like this:
    75     /// \code
    76     ///int count=0;
    77     ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
    78     /// \endcode
    79     class NodeIt : public Node {
    80     public:
    81       /// @warning The default constructor sets the iterator
    82       /// to an undefined value.
    83       NodeIt() {} //FIXME
    84       /// Invalid constructor \& conversion.
    85 
    86       /// Initialize the iterator to be invalid
    87       /// \sa Invalid for more details.
    88       NodeIt(Invalid) {}
    89       /// Sets the iterator to the first node of \c G.
    90       NodeIt(const GraphSkeleton &) {}
    91       /// @warning The default constructor sets the iterator
    92       /// to an undefined value.
    93       NodeIt(const NodeIt &n) : Node(n) {}
    94     };
    95    
    96    
    97     /// The base type of the edge iterators.
    98     class Edge {
    99     public:
    100       /// @warning The default constructor sets the iterator
    101       /// to an undefined value.
    102       Edge() {}   //FIXME
    103       /// Initialize the iterator to be invalid
    104       Edge(Invalid) {}
    105       /// Two iterators are equal if and only if they point to the
    106       /// same object or both are invalid.
    107       bool operator==(Edge) const { return true; }
    108       bool operator!=(Edge) const { return true; }
    109       bool operator<(Edge) const { return true; }
    110     };
    111    
    112     /// This iterator goes trough the outgoing edges of a node.
    113 
    114     /// This iterator goes trough the \e outgoing edges of a certain node
    115     /// of a graph.
    116     /// Its usage is quite simple, for example you can count the number
    117     /// of outgoing edges of a node \c n
    118     /// in graph \c G of type \c Graph as follows.
    119     /// \code
    120     ///int count=0;
    121     ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
    122     /// \endcode
    123    
    124     class OutEdgeIt : public Edge {
    125     public:
    126       /// @warning The default constructor sets the iterator
    127       /// to an undefined value.
    128       OutEdgeIt() {}
    129       /// Initialize the iterator to be invalid
    130       OutEdgeIt(Invalid) {}
    131       /// This constructor sets the iterator to first outgoing edge.
    132    
    133       /// This constructor set the iterator to the first outgoing edge of
    134       /// node
    135       ///@param n the node
    136       ///@param G the graph
    137       OutEdgeIt(const GraphSkeleton &, Node) {}
    138     };
    139 
    140     /// This iterator goes trough the incoming edges of a node.
    141 
    142     /// This iterator goes trough the \e incoming edges of a certain node
    143     /// of a graph.
    144     /// Its usage is quite simple, for example you can count the number
    145     /// of outgoing edges of a node \c n
    146     /// in graph \c G of type \c Graph as follows.
    147     /// \code
    148     ///int count=0;
    149     ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
    150     /// \endcode
    151 
    152     class InEdgeIt : public Edge {
    153     public:
    154       /// @warning The default constructor sets the iterator
    155       /// to an undefined value.
    156       InEdgeIt() {}
    157       /// Initialize the iterator to be invalid
    158       InEdgeIt(Invalid) {}
    159       InEdgeIt(const GraphSkeleton &, Node) {}   
    160     };
    161     //  class SymEdgeIt : public Edge {};
    162 
    163     /// This iterator goes through each edge.
    164 
    165     /// This iterator goes through each edge of a graph.
    166     /// Its usage is quite simple, for example you can count the number
    167     /// of edges in a graph \c G of type \c Graph as follows:
    168     /// \code
    169     ///int count=0;
    170     ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
    171     /// \endcode
    172     class EdgeIt : public Edge {
    173     public:
    174       /// @warning The default constructor sets the iterator
    175       /// to an undefined value.
    176       EdgeIt() {}
    177       /// Initialize the iterator to be invalid
    178       EdgeIt(Invalid) {}
    179       EdgeIt(const GraphSkeleton &) {}
    180     };
    181 
    182     /// First node of the graph.
    183 
    184     /// \retval i the first node.
    185     /// \return the first node.
     13  namespace skeleton {
     14   
     15    // @defgroup empty_graph The GraphSkeleton class
     16    // @{
     17
     18    /// An empty static graph class.
     19 
     20    /// This class provides all the common features of a graph structure,
     21    /// however completely without implementations and real data structures
     22    /// behind the interface.
     23    /// All graph algorithms should compile with this class, but it will not
     24    /// run properly, of course.
    18625    ///
    187     NodeIt &first(NodeIt &i) const { return i;}
    188 
    189     /// The first incoming edge.
    190     InEdgeIt &first(InEdgeIt &i, Node) const { return i;}
    191     /// The first outgoing edge.
    192     OutEdgeIt &first(OutEdgeIt &i, Node) const { return i;}
    193     //  SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
    194     /// The first edge of the Graph.
    195     EdgeIt &first(EdgeIt &i) const { return i;}
    196 
    197 //     Node getNext(Node) const {}
    198 //     InEdgeIt getNext(InEdgeIt) const {}
    199 //     OutEdgeIt getNext(OutEdgeIt) const {}
    200 //     //SymEdgeIt getNext(SymEdgeIt) const {}
    201 //     EdgeIt getNext(EdgeIt) const {}
    202 
    203     /// Go to the next node.
    204     NodeIt &next(NodeIt &i) const { return i;}
    205     /// Go to the next incoming edge.
    206     InEdgeIt &next(InEdgeIt &i) const { return i;}
    207     /// Go to the next outgoing edge.
    208     OutEdgeIt &next(OutEdgeIt &i) const { return i;}
    209     //SymEdgeIt &next(SymEdgeIt &) const {}
    210     /// Go to the next edge.
    211     EdgeIt &next(EdgeIt &i) const { return i;}
    212 
    213     ///Gives back the head node of an edge.
    214     Node head(Edge) const { return INVALID; }
    215     ///Gives back the tail node of an edge.
    216     Node tail(Edge) const { return INVALID; }
    217  
    218     //   Node aNode(InEdgeIt) const {}
    219     //   Node aNode(OutEdgeIt) const {}
    220     //   Node aNode(SymEdgeIt) const {}
    221 
    222     //   Node bNode(InEdgeIt) const {}
    223     //   Node bNode(OutEdgeIt) const {}
    224     //   Node bNode(SymEdgeIt) const {}
    225 
    226     /// Checks if a node iterator is valid
    227 
    228     ///\todo Maybe, it would be better if iterator converted to
    229     ///bool directly, as Jacint prefers.
    230     bool valid(const Node&) const { return true;}
    231     /// Checks if an edge iterator is valid
    232 
    233     ///\todo Maybe, it would be better if iterator converted to
    234     ///bool directly, as Jacint prefers.
    235     bool valid(const Edge&) const { return true;}
    236 
    237     ///Gives back the \e id of a node.
    238 
    239     ///\warning Not all graph structures provide this feature.
    240     ///
    241     int id(const Node&) const { return 0;}
    242     ///Gives back the \e id of an edge.
    243 
    244     ///\warning Not all graph structures provide this feature.
    245     ///
    246     int id(const Edge&) const { return 0;}
    247 
    248     //void setInvalid(Node &) const {};
    249     //void setInvalid(Edge &) const {};
    250  
    251     ///Add a new node to the graph.
    252 
    253     /// \return the new node.
    254     ///
    255     Node addNode() { return INVALID;}
    256     ///Add a new edge to the graph.
    257 
    258     ///Add a new edge to the graph with tail node \c tail
    259     ///and head node \c head.
    260     ///\return the new edge.
    261     Edge addEdge(Node, Node) { return INVALID;}
    262    
    263     /// Resets the graph.
    264 
    265     /// This function deletes all edges and nodes of the graph.
    266     /// It also frees the memory allocated to store them.
    267     void clear() {}
    268 
    269     int nodeNum() const { return 0;}
    270     int edgeNum() const { return 0;}
    271 
    272     ///Read/write/reference map of the nodes to type \c T.
    273 
    274     ///Read/write/reference map of the nodes to type \c T.
    275     /// \sa MemoryMapSkeleton
    276     /// \todo We may need copy constructor
    277     /// \todo We may need conversion from other nodetype
    278     /// \todo We may need operator=
    279     /// \warning Making maps that can handle bool type (NodeMap<bool>)
    280     /// needs extra attention!
    281 
    282     template<class T> class NodeMap
     26    /// It can be used for checking the interface compatibility,
     27    /// or it can serve as a skeleton of a new graph structure.
     28    ///
     29    /// Also, you will find here the full documentation of a certain graph
     30    /// feature, the documentation of a real graph imlementation
     31    /// like @ref ListGraph or
     32    /// @ref SmartGraph will just refer to this structure.
     33    class StaticGraphSkeleton
    28334    {
    28435    public:
    285       typedef T ValueType;
    286       typedef Node KeyType;
    287 
    288       NodeMap(const GraphSkeleton &) {}
    289       NodeMap(const GraphSkeleton &, T) {}
    290 
    291       template<typename TT> NodeMap(const NodeMap<TT> &) {}
    292 
    293       /// Sets the value of a node.
    294 
    295       /// Sets the value associated with node \c i to the value \c t.
     36      /// Defalult constructor.
     37      StaticGraphSkeleton() {}
     38      ///Copy consructor.
     39
     40      ///\todo It is not clear, what we expect from a copy constructor.
     41      ///E.g. How to assign the nodes/edges to each other? What about maps?
     42      StaticGraphSkeleton(const StaticGraphSkeleton &G) {}
     43
     44      /// The base type of the node iterators.
     45
     46      /// This is the base type of each node iterators,
     47      /// thus each kind of node iterator will convert to this.
     48      class Node {
     49      public:
     50        /// @warning The default constructor sets the iterator
     51        /// to an undefined value.
     52        Node() {}   //FIXME
     53        /// Invalid constructor \& conversion.
     54
     55        /// This constructor initializes the iterator to be invalid.
     56        /// \sa Invalid for more details.
     57
     58        Node(Invalid) {}
     59        //Node(const Node &) {}
     60
     61        /// Two iterators are equal if and only if they point to the
     62        /// same object or both are invalid.
     63        bool operator==(Node) const { return true; }
     64
     65        /// \sa \ref operator==(Node n)
     66        ///
     67        bool operator!=(Node) const { return true; }
     68
     69        bool operator<(Node) const { return true; }
     70      };
     71   
     72      /// This iterator goes through each node.
     73
     74      /// This iterator goes through each node.
     75      /// Its usage is quite simple, for example you can count the number
     76      /// of nodes in graph \c G of type \c Graph like this:
     77      /// \code
     78      ///int count=0;
     79      ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
     80      /// \endcode
     81      class NodeIt : public Node {
     82      public:
     83        /// @warning The default constructor sets the iterator
     84        /// to an undefined value.
     85        NodeIt() {} //FIXME
     86        /// Invalid constructor \& conversion.
     87
     88        /// Initialize the iterator to be invalid
     89        /// \sa Invalid for more details.
     90        NodeIt(Invalid) {}
     91        /// Sets the iterator to the first node of \c G.
     92        NodeIt(const StaticGraphSkeleton &) {}
     93        /// @warning The default constructor sets the iterator
     94        /// to an undefined value.
     95        NodeIt(const NodeIt &n) : Node(n) {}
     96      };
     97   
     98   
     99      /// The base type of the edge iterators.
     100      class Edge {
     101      public:
     102        /// @warning The default constructor sets the iterator
     103        /// to an undefined value.
     104        Edge() {}   //FIXME
     105        /// Initialize the iterator to be invalid
     106        Edge(Invalid) {}
     107        /// Two iterators are equal if and only if they point to the
     108        /// same object or both are invalid.
     109        bool operator==(Edge) const { return true; }
     110        bool operator!=(Edge) const { return true; }
     111        bool operator<(Edge) const { return true; }
     112      };
     113   
     114      /// This iterator goes trough the outgoing edges of a node.
     115
     116      /// This iterator goes trough the \e outgoing edges of a certain node
     117      /// of a graph.
     118      /// Its usage is quite simple, for example you can count the number
     119      /// of outgoing edges of a node \c n
     120      /// in graph \c G of type \c Graph as follows.
     121      /// \code
     122      ///int count=0;
     123      ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
     124      /// \endcode
     125   
     126      class OutEdgeIt : public Edge {
     127      public:
     128        /// @warning The default constructor sets the iterator
     129        /// to an undefined value.
     130        OutEdgeIt() {}
     131        /// Initialize the iterator to be invalid
     132        OutEdgeIt(Invalid) {}
     133        /// This constructor sets the iterator to first outgoing edge.
     134   
     135        /// This constructor set the iterator to the first outgoing edge of
     136        /// node
     137        ///@param n the node
     138        ///@param G the graph
     139        OutEdgeIt(const StaticGraphSkeleton &, Node) {}
     140      };
     141
     142      /// This iterator goes trough the incoming edges of a node.
     143
     144      /// This iterator goes trough the \e incoming edges of a certain node
     145      /// of a graph.
     146      /// Its usage is quite simple, for example you can count the number
     147      /// of outgoing edges of a node \c n
     148      /// in graph \c G of type \c Graph as follows.
     149      /// \code
     150      ///int count=0;
     151      ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
     152      /// \endcode
     153
     154      class InEdgeIt : public Edge {
     155      public:
     156        /// @warning The default constructor sets the iterator
     157        /// to an undefined value.
     158        InEdgeIt() {}
     159        /// Initialize the iterator to be invalid
     160        InEdgeIt(Invalid) {}
     161        InEdgeIt(const StaticGraphSkeleton &, Node) {}   
     162      };
     163      //  class SymEdgeIt : public Edge {};
     164
     165      /// This iterator goes through each edge.
     166
     167      /// This iterator goes through each edge of a graph.
     168      /// Its usage is quite simple, for example you can count the number
     169      /// of edges in a graph \c G of type \c Graph as follows:
     170      /// \code
     171      ///int count=0;
     172      ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
     173      /// \endcode
     174      class EdgeIt : public Edge {
     175      public:
     176        /// @warning The default constructor sets the iterator
     177        /// to an undefined value.
     178        EdgeIt() {}
     179        /// Initialize the iterator to be invalid
     180        EdgeIt(Invalid) {}
     181        EdgeIt(const StaticGraphSkeleton &) {}
     182      };
     183
     184      /// First node of the graph.
     185
     186      /// \retval i the first node.
     187      /// \return the first node.
    296188      ///
    297       void set(Node, T) {}
    298       // Gets the value of a node.
    299       //T get(Node i) const {return *(T*)0;}  //FIXME: Is it necessary?
    300       T &operator[](Node) {return *(T*)0;}
    301       const T &operator[](Node) const {return *(T*)0;}
    302 
    303       /// Updates the map if the graph has been changed
    304 
    305       /// \todo Do we need this?
     189      NodeIt &first(NodeIt &i) const { return i;}
     190
     191      /// The first incoming edge.
     192      InEdgeIt &first(InEdgeIt &i, Node) const { return i;}
     193      /// The first outgoing edge.
     194      OutEdgeIt &first(OutEdgeIt &i, Node) const { return i;}
     195      //  SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
     196      /// The first edge of the Graph.
     197      EdgeIt &first(EdgeIt &i) const { return i;}
     198
     199      //     Node getNext(Node) const {}
     200      //     InEdgeIt getNext(InEdgeIt) const {}
     201      //     OutEdgeIt getNext(OutEdgeIt) const {}
     202      //     //SymEdgeIt getNext(SymEdgeIt) const {}
     203      //     EdgeIt getNext(EdgeIt) const {}
     204
     205      /// Go to the next node.
     206      NodeIt &next(NodeIt &i) const { return i;}
     207      /// Go to the next incoming edge.
     208      InEdgeIt &next(InEdgeIt &i) const { return i;}
     209      /// Go to the next outgoing edge.
     210      OutEdgeIt &next(OutEdgeIt &i) const { return i;}
     211      //SymEdgeIt &next(SymEdgeIt &) const {}
     212      /// Go to the next edge.
     213      EdgeIt &next(EdgeIt &i) const { return i;}
     214
     215      ///Gives back the head node of an edge.
     216      Node head(Edge) const { return INVALID; }
     217      ///Gives back the tail node of an edge.
     218      Node tail(Edge) const { return INVALID; }
     219 
     220      //   Node aNode(InEdgeIt) const {}
     221      //   Node aNode(OutEdgeIt) const {}
     222      //   Node aNode(SymEdgeIt) const {}
     223
     224      //   Node bNode(InEdgeIt) const {}
     225      //   Node bNode(OutEdgeIt) const {}
     226      //   Node bNode(SymEdgeIt) const {}
     227
     228      /// Checks if a node iterator is valid
     229
     230      ///\todo Maybe, it would be better if iterator converted to
     231      ///bool directly, as Jacint prefers.
     232      bool valid(const Node&) const { return true;}
     233      /// Checks if an edge iterator is valid
     234
     235      ///\todo Maybe, it would be better if iterator converted to
     236      ///bool directly, as Jacint prefers.
     237      bool valid(const Edge&) const { return true;}
     238
     239      ///Gives back the \e id of a node.
     240
     241      ///\warning Not all graph structures provide this feature.
    306242      ///
    307       void update() {}
    308       void update(T a) {}   //FIXME: Is it necessary
     243      int id(const Node&) const { return 0;}
     244      ///Gives back the \e id of an edge.
     245
     246      ///\warning Not all graph structures provide this feature.
     247      ///
     248      int id(const Edge&) const { return 0;}
     249
     250      /// Resets the graph.
     251
     252      /// This function deletes all edges and nodes of the graph.
     253      /// It also frees the memory allocated to store them.
     254      void clear() {}
     255
     256      int nodeNum() const { return 0;}
     257      int edgeNum() const { return 0;}
     258
     259
     260
     261      ///Reference map of the nodes to type \c T.
     262
     263      ///Reference map of the nodes to type \c T.
     264      /// \sa ReferenceSkeleton
     265      /// \warning Making maps that can handle bool type (NodeMap<bool>)
     266      /// needs extra attention!
     267
     268      template<class T> class NodeMap
     269        : public ReferenceMap< Node, T >
     270      {
     271      public:
     272
     273        class ReferenceMap<Node,T>;
     274
     275        NodeMap(const StaticGraphSkeleton &) {}
     276        NodeMap(const StaticGraphSkeleton &, T) {}
     277
     278        ///Copy constructor
     279        template<typename TT> NodeMap(const NodeMap<TT> &) {}
     280        ///Assignment operator
     281        template<typename TT> NodeMap &operator=(const NodeMap<TT> &)
     282        {return *this;}
     283      };
     284
     285      ///Reference map of the edges to type \c T.
     286
     287      ///Reference map of the edges to type \c T.
     288      /// \sa ReferenceSkeleton
     289      /// \warning Making maps that can handle bool type (EdgeMap<bool>)
     290      /// needs extra attention!
     291      template<class T> class EdgeMap
     292        : public ReferenceMap<Edge,T>
     293      {
     294      public:
     295        typedef T ValueType;
     296        typedef Edge KeyType;
     297
     298        EdgeMap(const StaticGraphSkeleton &) {}
     299        EdgeMap(const StaticGraphSkeleton &, T ) {}
     300   
     301        ///Copy constructor
     302        template<typename TT> EdgeMap(const EdgeMap<TT> &) {}
     303        ///Assignment operator
     304        template<typename TT> EdgeMap &operator=(const EdgeMap<TT> &)
     305        {return *this;}
     306      };
    309307    };
    310308
    311     ///Read/write/reference map of the edges to type \c T.
    312 
    313     ///Read/write/reference map of the edges to type \c T.
    314     ///It behaves exactly in the same way as \ref NodeMap.
    315     /// \sa NodeMap
    316     /// \sa MemoryMapSkeleton
    317     /// \todo We may need copy constructor
    318     /// \todo We may need conversion from other edgetype
    319     /// \todo We may need operator=
    320     template<class T> class EdgeMap
     309
     310 
     311    /// An empty graph class.
     312
     313    /// This class provides everything that \c StaticGraphSkeleton
     314    /// with additional functionality which enables to build a
     315    /// graph from scratch.
     316    class GraphSkeleton : public StaticGraphSkeleton
    321317    {
    322318    public:
    323       typedef T ValueType;
    324       typedef Edge KeyType;
    325 
    326       EdgeMap(const GraphSkeleton &) {}
    327       EdgeMap(const GraphSkeleton &, T ) {}
    328    
    329       ///\todo It can copy between different types.
     319      /// Defalult constructor.
     320      GraphSkeleton() {}
     321      ///Copy consructor.
     322
     323      ///\todo It is not clear, what we expect from a copy constructor.
     324      ///E.g. How to assign the nodes/edges to each other? What about maps?
     325      GraphSkeleton(const GraphSkeleton &G) {}
     326
     327      ///Add a new node to the graph.
     328
     329      /// \return the new node.
    330330      ///
    331       template<typename TT> EdgeMap(const EdgeMap<TT> &) {}
    332 
    333       void set(Edge, T) {}
    334       //T get(Edge) const {return *(T*)0;}
    335       T &operator[](Edge) {return *(T*)0;}
    336       const T &operator[](Edge) const {return *(T*)0;}
    337    
    338       void update() {}
    339       void update(T a) {}   //FIXME: Is it necessary
     331      Node addNode() { return INVALID;}
     332      ///Add a new edge to the graph.
     333
     334      ///Add a new edge to the graph with tail node \c tail
     335      ///and head node \c head.
     336      ///\return the new edge.
     337      Edge addEdge(Node, Node) { return INVALID;}
     338   
     339      /// Resets the graph.
     340
     341      /// This function deletes all edges and nodes of the graph.
     342      /// It also frees the memory allocated to store them.
     343      /// \todo It might belong to \c EraseableGraphSkeleton.
     344      void clear() {}
    340345    };
    341   };
    342 
    343   /// An empty eraseable graph class.
    344  
    345   /// This class provides all the common features of an \e eraseable graph
    346   /// structure,
    347   /// however completely without implementations and real data structures
    348   /// behind the interface.
    349   /// All graph algorithms should compile with this class, but it will not
    350   /// run properly, of course.
    351   ///
    352   /// \todo This blabla could be replaced by a sepatate description about
    353   /// Skeletons.
    354   ///
    355   /// It can be used for checking the interface compatibility,
    356   /// or it can serve as a skeleton of a new graph structure.
    357   ///
    358   /// Also, you will find here the full documentation of a certain graph
    359   /// feature, the documentation of a real graph imlementation
    360   /// like @ref ListGraph or
    361   /// @ref SmartGraph will just refer to this structure.
    362   class EraseableGraphSkeleton : public GraphSkeleton
    363   {
    364   public:
    365     /// Deletes a node.
    366     void erase(Node n) {}
    367     /// Deletes an edge.
    368     void erase(Edge e) {}
    369 
    370     /// Defalult constructor.
    371     EraseableGraphSkeleton() {}
    372     ///Copy consructor.
    373     EraseableGraphSkeleton(const GraphSkeleton &G) {}
    374   };
    375 
    376  
    377   // @}
    378 
     346
     347    /// An empty eraseable graph class.
     348 
     349    /// This class is an extension of \c GraphSkeleton. It also makes it
     350    /// possible to erase edges or nodes.
     351    class EraseableGraphSkeleton : public GraphSkeleton
     352    {
     353    public:
     354      /// Deletes a node.
     355      void erase(Node n) {}
     356      /// Deletes an edge.
     357      void erase(Edge e) {}
     358
     359      /// Defalult constructor.
     360      EraseableGraphSkeleton() {}
     361      ///Copy consructor.
     362      EraseableGraphSkeleton(const GraphSkeleton &G) {}
     363    };
     364
     365    // @}
     366  } //namespace skeleton
     367 
    379368} //namespace hugo
    380369
  • src/hugo/skeletons/maps.h

    r539 r732  
    1313    /// Readable map concept
    1414    template<typename K, typename T>
    15     class ReadableMap
     15    class ReadMap
    1616    {
    1717    public:
     
    2424      ValueType operator[](const KeyType &k) const {return ValueType();}
    2525
    26       /// Copy contsructor. (optional)
    27       ReadableMap(const ReadableMap&) {}
    28       /// Assignment operator. (optional)
    29       ReadableMap& operator=(const ReadableMap&) {return *this;}
    30 
    31       ReadableMap() {}
     26      ///Default constructor
     27      ReadMap() {}
    3228    };
    3329
     
    3531    /// Writable map concept
    3632    template<typename K, typename T>
    37     class WritableMap
     33    class WriteMap
    3834    {
    3935    public:
     
    4642      void set(const KeyType &k,const ValueType &t) {}
    4743
    48       WritableMap() {}
     44      ///Default constructor
     45      WriteMap() {}
    4946    };
    5047
    5148    ///Read/Writeable map concept
    5249    template<typename K, typename T>
    53     class ReadWritableMap : public ReadableMap<K,T>,
    54                             public WritableMap<K,T>
     50    class ReadWriteMap : public ReadMap<K,T>,
     51                            public WriteMap<K,T>
    5552    {
    5653    public:
     
    6562      void set(const KeyType &k,const ValueType &t) {}
    6663
    67       /// Copy contsructor. (optional)
    68       ReadWritableMap(const ReadWritableMap&) {}
    69       /// Assignment operator. (optional)
    70       ReadWritableMap& operator=(const ReadWritableMap&) {return *this;}
    71 
    72       /// Facility to define a map with an other value type (optional)
    73       template<typename T1>
    74       struct rebind {
    75         /// The type of a map with the given value type
    76         typedef ReadWritableMap<K,T1> other;
    77       };
    78       /// @brief Constructor that copies all keys from the other map and
    79       /// assigns to them a default value (optional)
    80       template<typename T1>
    81       ReadWritableMap(const ReadWritableMap<K,T1> &map, const ValueType &v) {}
    82 
    83       ReadWritableMap() {}
     64      ///Default constructor
     65      ReadWriteMap() {}
    8466    };
    8567 
     
    8769    ///Dereferable map concept
    8870    template<typename K, typename T>
    89     class DereferableMap : public ReadWritableMap<K,T>
     71    class ReferenceMap : public ReadWriteMap<K,T>
    9072    {
    9173    public:
     
    9476      /// Map's value type. (The type of objects associated with the keys).
    9577      typedef T ValueType;
    96       /// Map's reference type. (Reference to an object associated with a key)
     78
     79    protected:
     80      ValueType tmp;
     81    public:
    9782      typedef ValueType& ReferenceType;
    9883      /// Map's const reference type.
     
    10085
    10186      ///Returns a reference to the value associated to a key.
    102       ReferenceType operator[](const KeyType &i);
     87      ReferenceType operator[](const KeyType &i) { return tmp; }
    10388      ///Returns a const reference to the value associated to a key.
    104       ConstReferenceType operator[](const KeyType &i) const;
     89      ConstReferenceType operator[](const KeyType &i) const
     90      { return tmp; }
    10591      /// Sets the value associated with a key.
    10692      void set(const KeyType &k,const ValueType &t) { operator[](k)=t; }
    10793
    108       /// Copy contsructor. (optional)
    109       DereferableMap(const DereferableMap&) {}
    110       /// Assignment operator. (optional)
    111       DereferableMap& operator=(const DereferableMap&) {return *this;}
    112 
    113       /// Facility to define a map with an other value type (optional)
    114       template<typename T1>
    115       struct rebind {
    116         /// The type of a map with the given value type
    117         typedef DereferableMap<K,T1> other;
    118       };
    119       /// @brief Constructor that copies all keys from the other map and
    120       /// assigns to them a default value (optional)
    121       template<typename T1>
    122       DereferableMap(const DereferableMap<K,T1> &map, const ValueType &v) {}
    123 
    124       DereferableMap() {}
     94      ///Default constructor
     95      ReferenceMap() {}
    12596    };
    126 
    127 
    128   }
    129 }
     97  } //namespace skeleton
     98} //namespace hugo
    13099#endif // HUGO_MAPSKELETON_H
Note: See TracChangeset for help on using the changeset viewer.