COIN-OR::LEMON - Graph Library

Changeset 1620:09feafe81053 in lemon-0.x


Ignore:
Timestamp:
08/11/05 15:07:54 (19 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2128
Message:

Start working on UndirGraph? concept clarification and its harmonization with
the directed graph concept.
Not yet done!!!

Location:
lemon/concept
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • lemon/concept/graph.h

    r1563 r1620  
    3232
    3333   
    34     /// \addtogroup graph_concepts
    35     /// @{
    36 
    3734    /**************** The full-featured graph concepts ****************/
    3835
     
    10198      };
    10299    };
     100
     101    /// \addtogroup graph_concepts
     102    /// @{
    103103
    104104    /// An empty static graph class.
     
    253253        /// Inequality operator
    254254
    255         /// \sa operator==(Node n)
     255        /// \sa operator==(Edge n)
    256256        ///
    257257        bool operator!=(Edge) const { return true; }
  • lemon/concept/graph_component.h

    r1563 r1620  
    3030namespace lemon {
    3131  namespace concept {
    32 
    33     /// \addtogroup graph_concepts
    34     /// @{
    3532
    3633    /****************   Graph iterator concepts   ****************/
     
    997994    };
    998995
    999     /// @}
    1000 
    1001996  }
    1002997
  • lemon/concept/undir_graph.h

    r1448 r1620  
    2727
    2828#include <lemon/concept/graph_component.h>
     29#include <lemon/concept/graph.h>
    2930#include <lemon/utility.h>
    3031
    3132namespace lemon {
    3233  namespace concept {
    33 
    34     /// \addtogroup graph_concepts
    35     /// @{
    36 
    3734
    3835    /// Skeleton class which describes an edge with direction in \ref
     
    109106          checkConcept<BaseIterableGraphComponent, Graph>();
    110107          checkConcept<GraphItem<>, UndirEdge>();
    111           checkConcept<UndirGraphEdge<Graph>, Edge>();
     108          //checkConcept<UndirGraphEdge<Graph>, Edge>();
    112109
    113110          graph.first(ue);
     
    217214
    218215    };
     216
     217    /// \addtogroup graph_concepts
     218    /// @{
     219
    219220
    220221    /// Class describing the concept of Undirected Graphs.
     
    233234    /// a tutorial about undirected graphs.
    234235
    235     class UndirGraph {
     236    class UndirGraph : public StaticGraph {
    236237    public:
    237238      ///\e
     
    241242      typedef True UndirTag;
    242243
    243       /// Type describing a node in the graph
    244       typedef GraphNode Node;
    245 
    246       /// Type describing an undirected edge
    247       typedef GraphItem<'u'> UndirEdge;
    248 
    249       /// Type describing an UndirEdge with direction
    250 #ifndef DOXYGEN
    251       typedef UndirGraphEdge<UndirGraph> Edge;
    252 #else
    253       typedef UndirGraphEdge Edge;
    254 #endif
    255 
    256       /// Iterator type which iterates over all nodes
    257 #ifndef DOXYGEN
    258       typedef GraphIterator<UndirGraph, Node> NodeIt;
    259 #else
    260       typedef GraphIterator NodeIt;
    261 #endif
    262 
    263       /// Iterator type which iterates over all undirected edges
    264 #ifndef DOXYGEN
    265       typedef GraphIterator<UndirGraph, UndirEdge> UndirEdgeIt;
    266 #else
    267       typedef GraphIterator UndirEdgeIt;
    268 #endif
    269 
    270       /// Iterator type which iterates over all directed edges.
    271 
    272       /// Iterator type which iterates over all edges (each undirected
    273       /// edge occurs twice with both directions.
    274 #ifndef DOXYGEN
    275       typedef GraphIterator<UndirGraph, Edge> EdgeIt;
    276 #else
    277       typedef GraphIterator EdgeIt;
    278 #endif
    279 
    280 
    281       /// Iterator of undirected edges incident to a node
    282 #ifndef DOXYGEN
    283       typedef GraphIncIterator<UndirGraph, UndirEdge, 'u'> IncEdgeIt;
    284 #else
    285       typedef GraphIncIterator IncEdgeIt;
    286 #endif
    287 
    288       /// Iterator of edges incoming to a node
    289 #ifndef DOXYGEN
    290       typedef GraphIncIterator<UndirGraph, Edge, 'i'> InEdgeIt;
    291 #else
    292       typedef GraphIncIterator InEdgeIt;
    293 #endif
    294 
    295       /// Iterator of edges outgoing from a node
    296 #ifndef DOXYGEN
    297       typedef GraphIncIterator<UndirGraph, Edge, 'o'> OutEdgeIt;
    298 #else
    299       typedef GraphIncIterator OutEdgeIt;
    300 #endif
    301 
    302       /// NodeMap template
    303 #ifdef DOXYGEN
    304       typedef GraphMap NodeMap<T>;
    305 #endif
    306 
    307       /// UndirEdgeMap template
    308 #ifdef DOXYGEN
    309       typedef GraphMap UndirEdgeMap<T>;
    310 #endif
    311 
    312       /// EdgeMap template
    313 #ifdef DOXYGEN
    314       typedef GraphMap EdgeMap<T>;
    315 #endif
    316 
    317       template <typename T>
    318       class NodeMap : public GraphMap<UndirGraph, Node, T> {
    319         typedef GraphMap<UndirGraph, Node, T> Parent;
     244      /// The base type of the undirected edge iterators.
     245     
     246      /// The base type of the undirected edge iterators.
     247      ///
     248      class UndirEdge {
    320249      public:
    321 
    322         explicit NodeMap(const UndirGraph &g) : Parent(g) {}
    323         NodeMap(const UndirGraph &g, T t) : Parent(g, t) {}
    324       };
    325 
    326       template <typename T>
    327       class UndirEdgeMap : public GraphMap<UndirGraph, UndirEdge, T> {
    328         typedef GraphMap<UndirGraph, UndirEdge, T> Parent;
     250        /// Default constructor
     251
     252        /// @warning The default constructor sets the iterator
     253        /// to an undefined value.
     254        UndirEdge() { }
     255        /// Copy constructor.
     256
     257        /// Copy constructor.
     258        ///
     259        UndirEdge(const UndirEdge&) { }
     260        /// Edge -> UndirEdge conversion
     261
     262        /// Edge -> UndirEdge conversion
     263        ///
     264        UndirEdge(const Edge&) { }
     265        /// Initialize the iterator to be invalid.
     266
     267        /// Initialize the iterator to be invalid.
     268        ///
     269        UndirEdge(Invalid) { }
     270        /// Equality operator
     271
     272        /// Two iterators are equal if and only if they point to the
     273        /// same object or both are invalid.
     274        bool operator==(UndirEdge) const { return true; }
     275        /// Inequality operator
     276
     277        /// \sa operator==(UndirEdge n)
     278        ///
     279        bool operator!=(UndirEdge) const { return true; }
     280
     281        ///\e
     282
     283        ///\todo Do we need this?
     284        ///
     285        bool operator<(const UndirEdge &that) const { return true; }
     286      };
     287   
     288      /// This iterator goes through each undirected edge.
     289
     290      /// This iterator goes through each undirected edge of a graph.
     291      /// Its usage is quite simple, for example you can count the number
     292      /// of edges in a graph \c g of type \c Graph as follows:
     293      /// \code
     294      /// int count=0;
     295      /// for(Graph::UndirEdgeIt e(g); e!=INVALID; ++e) ++count;
     296      /// \endcode
     297      class UndirEdgeIt : public UndirEdge {
    329298      public:
    330 
    331         explicit UndirEdgeMap(const UndirGraph &g) : Parent(g) {}
    332         UndirEdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
    333       };
    334 
    335       template <typename T>
    336       class EdgeMap : public GraphMap<UndirGraph, Edge, T> {
    337         typedef GraphMap<UndirGraph, Edge, T> Parent;
     299        /// Default constructor
     300       
     301        /// @warning The default constructor sets the iterator
     302        /// to an undefined value.
     303        UndirEdgeIt() { }
     304        /// Copy constructor.
     305       
     306        /// Copy constructor.
     307        ///
     308        UndirEdgeIt(const UndirEdgeIt& e) : UndirEdge(e) { }
     309        /// Initialize the iterator to be invalid.
     310
     311        /// Initialize the iterator to be invalid.
     312        ///
     313        UndirEdgeIt(Invalid) { }
     314        /// This constructor sets the iterator to the first edge.
     315   
     316        /// This constructor sets the iterator to the first edge of \c g.
     317        ///@param g the graph
     318        UndirEdgeIt(const UndirGraph&) { }
     319        /// UndirEdge -> UndirEdgeIt conversion
     320
     321        /// Sets the iterator to the value of the trivial iterator \c e.
     322        /// This feature necessitates that each time we
     323        /// iterate the edge-set, the iteration order is the same.
     324        UndirEdgeIt(const UndirGraph&, const UndirEdge&) { }
     325        ///Next edge
     326       
     327        /// Assign the iterator to the next edge.
     328        UndirEdgeIt& operator++() { return *this; }
     329      };
     330
     331      /// This iterator goes trough the incident undirected edges of a node.
     332
     333      /// This iterator goes trough the incident undirected edges
     334      /// of a certain node
     335      /// of a graph.
     336      /// Its usage is quite simple, for example you can compute the
     337      /// degree (i.e. count the number
     338      /// of incident edges of a node \c n
     339      /// in graph \c g of type \c Graph as follows.
     340      /// \code
     341      /// int count=0;
     342      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
     343      /// \endcode
     344      class IncEdgeIt : public UndirEdge {
    338345      public:
    339 
    340         explicit EdgeMap(const UndirGraph &g) : Parent(g) {}
    341         EdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
     346        /// Default constructor
     347
     348        /// @warning The default constructor sets the iterator
     349        /// to an undefined value.
     350        IncEdgeIt() { }
     351        /// Copy constructor.
     352
     353        /// Copy constructor.
     354        ///
     355        IncEdgeIt(const IncEdgeIt& e) : UndirEdge(e) { }
     356        /// Initialize the iterator to be invalid.
     357
     358        /// Initialize the iterator to be invalid.
     359        ///
     360        IncEdgeIt(Invalid) { }
     361        /// This constructor sets the iterator to first incident edge.
     362   
     363        /// This constructor set the iterator to the first incident edge of
     364        /// the node.
     365        ///@param n the node
     366        ///@param g the graph
     367        IncEdgeIt(const UndirGraph&, const Node&) { }
     368        /// UndirEdge -> IncEdgeIt conversion
     369
     370        /// Sets the iterator to the value of the trivial iterator \c e.
     371        /// This feature necessitates that each time we
     372        /// iterate the edge-set, the iteration order is the same.
     373        IncEdgeIt(const UndirGraph&, const UndirEdge&) { }
     374        /// Next incident edge
     375
     376        /// Assign the iterator to the next incident edge
     377        /// of the corresponding node.
     378        IncEdgeIt& operator++() { return *this; }
     379      };
     380
     381      /// Read write map of the undirected edges to type \c T.
     382
     383      /// Reference map of the edges to type \c T.
     384      /// \sa Reference
     385      /// \warning Making maps that can handle bool type (UndirEdgeMap<bool>)
     386      /// needs some extra attention!
     387      template<class T>
     388      class UndirEdgeMap : public ReadWriteMap<UndirEdge,T>
     389      {
     390      public:
     391
     392        ///\e
     393        UndirEdgeMap(const UndirGraph&) { }
     394        ///\e
     395        UndirEdgeMap(const UndirGraph&, T) { }
     396        ///Copy constructor
     397        UndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap<UndirEdge,T>(em) { }
     398        ///Assignment operator
     399        UndirEdgeMap &operator=(const UndirEdgeMap&) { return *this; }
     400        // \todo fix this concept   
    342401      };
    343402
Note: See TracChangeset for help on using the changeset viewer.