Changeset 186:47cd1716870e in lemon-0.x for src

Timestamp:

03/15/04 17:30:20 (21 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@262

Message:

.

Location:

src/work/alpar

Files:

• emptygraph.h (modified) (10 diffs)
• mapskeleton.h (added)
• smart_graph.h (modified) (8 diffs)

src/work/alpar/emptygraph.h

@@ -13 +13 @@
   /// An empty graph class.
   
-  /// This class provides all the common features of a grapf structure,
-  /// however completely without implementations or real data structures
+  /// This class provides all the common features of a graph structure,
+  /// however completely without implementations and real data structures
   /// behind the interface.
   /// All graph algorithms should compile with this class, but it will not
@@ -32 +32 @@
     /// The base type of the node iterators.
 
-    /// This \c Node is the base type of each node iterators,
+    /// This is the base type of each node iterators,
     /// thus each kind of node iterator will convert to this.
     class Node {
@@ -59 +59 @@
     
     /// This iterator goes through each node.
+
+    /// This iterator goes through each node.
+    /// Its usage is quite simple, for example you can count the number
+    /// of nodes in graph \c G of type \c Graph like this:
+    /// \code
+    ///int count=0;
+    ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
+    /// \endcode
     class NodeIt : public Node {
     public:
@@ -92 +100 @@
     };
     
-    /// This iterator goes trought the outgoing edges of a certain graph.
+    /// This iterator goes trought the outgoing edges of a node.
+
+    /// This iterator goes trought the \e outgoing edges of a certain node
+    /// of a graph.
+    /// Its usage is quite simple, for example you can count the number
+    /// of outgoing edges of a node \c n
+    /// in graph \c G of type \c Graph as follows.
+    /// \code
+    ///int count=0;
+    ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
+    /// \endcode
     
     class OutEdgeIt : public Edge {
@@ -110 +128 @@
     };
 
+    /// This iterator goes trought the incoming edges of a node.
+
+    /// This iterator goes trought the \e incoming edges of a certain node
+    /// of a graph.
+    /// Its usage is quite simple, for example you can count the number
+    /// of outgoing edges of a node \c n
+    /// in graph \c G of type \c Graph as follows.
+    /// \code
+    ///int count=0;
+    ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
+    /// \endcode
+
     class InEdgeIt : public Edge {
     public:
@@ -120 +150 @@
     };
     //  class SymEdgeIt : public Edge {};
+
+    /// This iterator goes through each edge.
+
+    /// This iterator goes through each 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::EdgeIt e(G);G.valid(e);G.next(e)) count++;
+    /// \endcode
     class EdgeIt : public Edge {
     public:
@@ -174 +214 @@
 
     /// Checks if a node iterator is valid
+
+    ///\todo Maybe, it would be better if iterator converted to
+    ///bool directly, as Jacint prefers.
     bool valid(const Node) const { return true;}
     /// Checks if an edge iterator is valid
+
+    ///\todo Maybe, it would be better if iterator converted to
+    ///bool directly, as Jacint prefers.
     bool valid(const Edge) const { return true;}
 
@@ -195 +241 @@
 
     /// \return the new node.
+    ///
     Node addNode() { return INVALID;}
     ///Add a new edge to the graph.
@@ -228 +275 @@
   
 
-    ///Read/write map of the nodes to type \c T.
-
+    ///Read/write/reference map of the nodes to type \c T.
+
+    ///Read/write/reference map of the nodes to type \c T.
+    /// \sa MemoryMapSkeleton
     /// \todo We may need copy constructor
     /// \todo We may need conversion from other nodetype
@@ -263 +312 @@
     };
 
-    ///Read/write map of the edges to type \c T.
-
-    ///Read/write map of the edges to type \c T.
-    ///It behaves exactly the same way as \ref NodeMap.
+    ///Read/write/reference map of the edges to type \c T.
+
+    ///Read/write/reference map of the edges to type \c T.
+    ///It behaves exactly in the same way as \ref NodeMap.
+    /// \sa NodeMap
+    /// \sa MemoryMapSkeleton
+    /// \todo We may need copy constructor
+    /// \todo We may need conversion from other edgetype
+    /// \todo We may need operator=
     template<class T> class EdgeMap
     {

src/work/alpar/smart_graph.h

@@ -13 +13 @@
   class SymSmartGraph;
 
-  //  template<typename T> class SymSmartGraph::SymEdgeMap;
-  
+  ///A smart graph class.
+
+  ///This is a simple and fast graph implementation.
+  ///It is also quite memory efficient, but at the price
+  ///that <b> it does not support node and edge deletion</b>.
+  ///Apart from this it conforms to the graph interface documented under
+  ///the description of \ref GraphSkeleton.
+  ///\sa \ref GraphSkeleton.
   class SmartGraph {
 
@@ -56 +62 @@
     //  protected:
     // HELPME:
-  public:
+  protected:
     ///\bug It must be public because of SymEdgeMap.
     ///
@@ -100 +106 @@
     int edgeNum() const { return edges.size(); }  //FIXME: What is this?
 
+    ///\bug This function does something different than
+    ///its name would suggests...
     int maxNodeId() const { return nodes.size(); }  //FIXME: What is this?
+    ///\bug This function does something different than
+    ///its name would suggests...
     int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
 
-    
     Node tail(Edge e) const { return edges[e.n].tail; }
     Node head(Edge e) const { return edges[e.n].head; }
@@ -481 +490 @@
   ///The purpose of this graph structure is to handle graphs
   ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
-  ///of oppositely directed edges. You can define edge maps which
-  ///stores a common value for the edge pairs. The usual edge maps can be used
+  ///of oppositely directed edges.
+  ///There is a new edge map type called
+  ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
+  ///that complements this
+  ///feature by
+  ///storing shared values for the edge pairs. The usual
+  ///\ref GraphSkeleton::EdgeMap "EdgeMap"
+  ///can be used
   ///as well.
   ///
-  ///The oppositely directed edge can also be obtained easily.
+  ///The oppositely directed edge can also be obtained easily
+  ///using \ref opposite.
+  ///\warning It shares the similarity with \ref SmartGraph that
+  ///it is not possible to delete edges or nodes from the graph.
+  //\sa \ref SmartGraph.
 
   class SymSmartGraph : public SmartGraph
   {
   public:
+    template<typename T> class SymEdgeMap;
+    template<typename T> friend class SymEdgeMap;
+
     SymSmartGraph() : SmartGraph() { }
     SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
@@ -499 +521 @@
     }
 
+    ///The oppositely directed edge.
+
+    ///Returns the oppositely directed
+    ///pair of the edge \c e.
     Edge opposite(Edge e) const
     {
@@ -506 +532 @@
     }
     
+    ///Common data storage for the edge pairs.
+
+    ///This map makes it possible to store data shared by the oppositely
+    ///directed pairs of edges.
     template <typename T> class SymEdgeMap : public DynMapBase<Edge>
     {
@@ -514 +544 @@
       typedef Edge KeyType;
 
-      SymEdgeMap(const SmartGraph &_G) :
+      SymEdgeMap(const SymSmartGraph &_G) :
         DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
       {
-        G->dyn_edge_maps.push_back(this);
-      }
-      SymEdgeMap(const SmartGraph &_G,const T &t) :
+        static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
+      }
+      SymEdgeMap(const SymSmartGraph &_G,const T &t) :
         DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
       {
@@ -551 +581 @@
         if(G) {
           std::vector<DynMapBase<Edge>* >::iterator i;
-          for(i=G->dyn_edge_maps.begin();
-              i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
+          for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
+              i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
+                && *i!=this; ++i) ;
           //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
           //A better way to do that: (Is this really important?)
           if(*i==this) {
-            *i=G->dyn_edge_maps.back();
-            G->dyn_edge_maps.pop_back();
+            *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
+            static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
           }
         }