Changeset 1620:09feafe81053 in lemon-0.x

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:

• graph.h (modified) (3 diffs)
• graph_component.h (modified) (2 diffs)
• undir_graph.h (modified) (5 diffs)

lemon/concept/graph.h

@@ -32 +32 @@
 
     
-    /// \addtogroup graph_concepts
-    /// @{
-
     /**************** The full-featured graph concepts ****************/
 
@@ -101 +98 @@
       };
     };
+
+    /// \addtogroup graph_concepts
+    /// @{
 
     /// An empty static graph class.
@@ -253 +253 @@
         /// Inequality operator
 
-        /// \sa operator==(Node n)
+        /// \sa operator==(Edge n)
         ///
         bool operator!=(Edge) const { return true; }

lemon/concept/graph_component.h

@@ -30 +30 @@
 namespace lemon {
   namespace concept {
-
-    /// \addtogroup graph_concepts
-    /// @{
 
     /****************   Graph iterator concepts   ****************/
@@ -997 +994 @@
     };
 
-    /// @}
-
   }
 

lemon/concept/undir_graph.h

@@ -27 +27 @@
 
 #include <lemon/concept/graph_component.h>
+#include <lemon/concept/graph.h>
 #include <lemon/utility.h>
 
 namespace lemon {
   namespace concept {
-
-    /// \addtogroup graph_concepts
-    /// @{
-
 
     /// Skeleton class which describes an edge with direction in \ref
@@ -109 +106 @@
           checkConcept<BaseIterableGraphComponent, Graph>();
           checkConcept<GraphItem<>, UndirEdge>();
-          checkConcept<UndirGraphEdge<Graph>, Edge>();
+          //checkConcept<UndirGraphEdge<Graph>, Edge>();
 
           graph.first(ue);
@@ -217 +214 @@
 
     };
+
+    /// \addtogroup graph_concepts
+    /// @{
+
 
     /// Class describing the concept of Undirected Graphs.
@@ -233 +234 @@
     /// a tutorial about undirected graphs.
 
-    class UndirGraph {
+    class UndirGraph : public StaticGraph {
     public:
       ///\e
@@ -241 +242 @@
       typedef True UndirTag;
 
-      /// Type describing a node in the graph
-      typedef GraphNode Node;
-
-      /// Type describing an undirected edge
-      typedef GraphItem<'u'> UndirEdge;
-
-      /// Type describing an UndirEdge with direction
-#ifndef DOXYGEN
-      typedef UndirGraphEdge<UndirGraph> Edge;
-#else
-      typedef UndirGraphEdge Edge;
-#endif
-
-      /// Iterator type which iterates over all nodes
-#ifndef DOXYGEN
-      typedef GraphIterator<UndirGraph, Node> NodeIt;
-#else
-      typedef GraphIterator NodeIt;
-#endif
-
-      /// Iterator type which iterates over all undirected edges
-#ifndef DOXYGEN
-      typedef GraphIterator<UndirGraph, UndirEdge> UndirEdgeIt;
-#else
-      typedef GraphIterator UndirEdgeIt;
-#endif
-
-      /// Iterator type which iterates over all directed edges.
-
-      /// Iterator type which iterates over all edges (each undirected
-      /// edge occurs twice with both directions.
-#ifndef DOXYGEN
-      typedef GraphIterator<UndirGraph, Edge> EdgeIt;
-#else
-      typedef GraphIterator EdgeIt;
-#endif
-
-
-      /// Iterator of undirected edges incident to a node
-#ifndef DOXYGEN
-      typedef GraphIncIterator<UndirGraph, UndirEdge, 'u'> IncEdgeIt;
-#else
-      typedef GraphIncIterator IncEdgeIt;
-#endif
-
-      /// Iterator of edges incoming to a node
-#ifndef DOXYGEN
-      typedef GraphIncIterator<UndirGraph, Edge, 'i'> InEdgeIt;
-#else
-      typedef GraphIncIterator InEdgeIt;
-#endif
-
-      /// Iterator of edges outgoing from a node
-#ifndef DOXYGEN
-      typedef GraphIncIterator<UndirGraph, Edge, 'o'> OutEdgeIt;
-#else
-      typedef GraphIncIterator OutEdgeIt;
-#endif
-
-      /// NodeMap template
-#ifdef DOXYGEN
-      typedef GraphMap NodeMap<T>;
-#endif
-
-      /// UndirEdgeMap template
-#ifdef DOXYGEN
-      typedef GraphMap UndirEdgeMap<T>;
-#endif
-
-      /// EdgeMap template
-#ifdef DOXYGEN
-      typedef GraphMap EdgeMap<T>;
-#endif
-
-      template <typename T>
-      class NodeMap : public GraphMap<UndirGraph, Node, T> {
-        typedef GraphMap<UndirGraph, Node, T> Parent;
+      /// The base type of the undirected edge iterators.
+      
+      /// The base type of the undirected edge iterators.
+      ///
+      class UndirEdge {
       public:
-
-        explicit NodeMap(const UndirGraph &g) : Parent(g) {}
-        NodeMap(const UndirGraph &g, T t) : Parent(g, t) {}
-      };
-
-      template <typename T>
-      class UndirEdgeMap : public GraphMap<UndirGraph, UndirEdge, T> {
-        typedef GraphMap<UndirGraph, UndirEdge, T> Parent;
+        /// Default constructor
+
+        /// @warning The default constructor sets the iterator
+        /// to an undefined value.
+        UndirEdge() { }
+        /// Copy constructor.
+
+        /// Copy constructor.
+        ///
+        UndirEdge(const UndirEdge&) { }
+        /// Edge -> UndirEdge conversion
+
+        /// Edge -> UndirEdge conversion
+        ///
+        UndirEdge(const Edge&) { }
+        /// Initialize the iterator to be invalid.
+
+        /// Initialize the iterator to be invalid.
+        ///
+        UndirEdge(Invalid) { }
+        /// Equality operator
+
+        /// Two iterators are equal if and only if they point to the
+        /// same object or both are invalid.
+        bool operator==(UndirEdge) const { return true; }
+        /// Inequality operator
+
+        /// \sa operator==(UndirEdge n)
+        ///
+        bool operator!=(UndirEdge) const { return true; }
+
+        ///\e
+
+        ///\todo Do we need this?
+        ///
+        bool operator<(const UndirEdge &that) const { return true; }
+      };
+    
+      /// This iterator goes through each undirected edge.
+
+      /// This iterator goes through each undirected edge of a graph.
+      /// Its usage is quite simple, for example you can count the number
+      /// of edges in a graph \c g of type \c Graph as follows:
+      /// \code
+      /// int count=0;
+      /// for(Graph::UndirEdgeIt e(g); e!=INVALID; ++e) ++count;
+      /// \endcode
+      class UndirEdgeIt : public UndirEdge {
       public:
-
-        explicit UndirEdgeMap(const UndirGraph &g) : Parent(g) {}
-        UndirEdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
-      };
-
-      template <typename T>
-      class EdgeMap : public GraphMap<UndirGraph, Edge, T> {
-        typedef GraphMap<UndirGraph, Edge, T> Parent;
+        /// Default constructor
+        
+        /// @warning The default constructor sets the iterator
+        /// to an undefined value.
+        UndirEdgeIt() { }
+        /// Copy constructor.
+        
+        /// Copy constructor.
+        ///
+        UndirEdgeIt(const UndirEdgeIt& e) : UndirEdge(e) { }
+        /// Initialize the iterator to be invalid.
+
+        /// Initialize the iterator to be invalid.
+        ///
+        UndirEdgeIt(Invalid) { }
+        /// This constructor sets the iterator to the first edge.
+    
+        /// This constructor sets the iterator to the first edge of \c g.
+        ///@param g the graph
+        UndirEdgeIt(const UndirGraph&) { }
+        /// UndirEdge -> UndirEdgeIt conversion
+
+        /// Sets the iterator to the value of the trivial iterator \c e.
+        /// This feature necessitates that each time we 
+        /// iterate the edge-set, the iteration order is the same.
+        UndirEdgeIt(const UndirGraph&, const UndirEdge&) { } 
+        ///Next edge
+        
+        /// Assign the iterator to the next edge.
+        UndirEdgeIt& operator++() { return *this; }
+      };
+
+      /// This iterator goes trough the incident undirected edges of a node.
+
+      /// This iterator goes trough the incident undirected edges
+      /// of a certain node
+      /// of a graph.
+      /// Its usage is quite simple, for example you can compute the
+      /// degree (i.e. count the number
+      /// of incident edges of a node \c n
+      /// in graph \c g of type \c Graph as follows.
+      /// \code
+      /// int count=0;
+      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
+      /// \endcode
+      class IncEdgeIt : public UndirEdge {
       public:
-
-        explicit EdgeMap(const UndirGraph &g) : Parent(g) {}
-        EdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
+        /// Default constructor
+
+        /// @warning The default constructor sets the iterator
+        /// to an undefined value.
+        IncEdgeIt() { }
+        /// Copy constructor.
+
+        /// Copy constructor.
+        ///
+        IncEdgeIt(const IncEdgeIt& e) : UndirEdge(e) { }
+        /// Initialize the iterator to be invalid.
+
+        /// Initialize the iterator to be invalid.
+        ///
+        IncEdgeIt(Invalid) { }
+        /// This constructor sets the iterator to first incident edge.
+    
+        /// This constructor set the iterator to the first incident edge of
+        /// the node.
+        ///@param n the node
+        ///@param g the graph
+        IncEdgeIt(const UndirGraph&, const Node&) { }
+        /// UndirEdge -> IncEdgeIt conversion
+
+        /// Sets the iterator to the value of the trivial iterator \c e.
+        /// This feature necessitates that each time we 
+        /// iterate the edge-set, the iteration order is the same.
+        IncEdgeIt(const UndirGraph&, const UndirEdge&) { }
+        /// Next incident edge
+
+        /// Assign the iterator to the next incident edge
+        /// of the corresponding node.
+        IncEdgeIt& operator++() { return *this; }
+      };
+
+      /// Read write map of the undirected edges to type \c T.
+
+      /// Reference map of the edges to type \c T.
+      /// \sa Reference
+      /// \warning Making maps that can handle bool type (UndirEdgeMap<bool>)
+      /// needs some extra attention!
+      template<class T> 
+      class UndirEdgeMap : public ReadWriteMap<UndirEdge,T>
+      {
+      public:
+
+        ///\e
+        UndirEdgeMap(const UndirGraph&) { }
+        ///\e
+        UndirEdgeMap(const UndirGraph&, T) { }
+        ///Copy constructor
+        UndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap<UndirEdge,T>(em) { }
+        ///Assignment operator
+        UndirEdgeMap &operator=(const UndirEdgeMap&) { return *this; }
+        // \todo fix this concept    
       };