Changeset 335:999eb3cd7b49 in lemon-0.x for src/work/marci/graph_wrapper.h

Timestamp:

04/16/04 10:26:00 (21 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

jflsjfljskf

File:

• src/work/marci/graph_wrapper.h (modified) (8 diffs)

src/work/marci/graph_wrapper.h

@@ -7 +7 @@
 namespace hugo {
 
+  /// Graph wrappers
+
+  /// The main parts of HUGOlib are the different graph structures, 
+  /// generic graph algorithms, graph concepts which couple these, and 
+  /// graph wrappers. While the previous ones are more or less clear, the 
+  /// latter notion needs further explanation.
+  /// Graph wrappers are graph classes which serve for considering graph 
+  /// structures in different ways. A short example makes the notion much more 
+  /// clear. 
+  /// Suppose that we have an instance \code g \endcode of a directed graph
+  /// type say \code ListGraph \endcode and an algorithm 
+  /// \code template<typename Graph> int algorithm(const Graph&); \endcode 
+  /// is needed to run on the reversed oriented graph. 
+  /// It can be expensive (in time or in memory usage) to copy 
+  /// \code g \endcode with the reversed orientation. 
+  /// Thus, a wrapper class
+  /// \code template<typename Graph> class RevGraphWrapper; \endcode is used. 
+  /// The code looks as follows
+  /// \code
+  /// ListGraph g;
+  /// RevGraphWrapper<ListGraph> rgw(g);
+  /// int result=algorithm(rgw);
+  /// \endcode
+  /// After running the algorithm, the original graph \code g \endcode 
+  /// is untouched. Thus the above used graph wrapper is to consider the 
+  /// original graph with reversed orientation. 
+  /// This techniques gives rise to an elegant code, and 
+  /// based on stable graph wrappers, complex algorithms can be 
+  /// implemented easily. 
+  /// In flow, circulation and bipartite matching problems, the residual 
+  /// graph is of particualar significance. Combining a wrapper impleneting 
+  /// this, shortest path algorithms and mimimum mean cycle algorithms, 
+  /// a range of weighted and cardinality optimization algorithms can be 
+  /// obtained. For lack of space, for other examples, 
+  /// the interested user is referred to the detailed domumentation of graph 
+  /// wrappers. 
+  /// The behavior of graph wrappers are very different. Some of them keep 
+  /// capabilities of the original graph while in other cases this would be 
+  /// meaningless. This means that the concepts that they are model of depend 
+  /// on the graph wrapper, and the wrapped graph(s). 
+  /// If an edge of \code rgw \endcode is deleted, this is carried out by 
+  /// deleting the corresponding edge of \code g \endcode. But for a residual 
+  /// graph, this operation has no sense. 
+  /// Let we stand one more example here to simplify your work. 
+  /// wrapper class
+  /// \code template<typename Graph> class RevGraphWrapper; \endcode 
+  /// has constructor 
+  /// \code RevGraphWrapper(Graph& _g); \endcode. 
+  /// This means that in a situation, 
+  /// when a \code const ListGraph& \endcode reference to a graph is given, 
+  /// then it have to be instatiated with Graph=const ListGraph.
+  /// \code
+  /// int algorithm1(const ListGraph& g) {
+  ///   RevGraphWrapper<const ListGraph> rgw(g);
+  ///   return algorithm2(rgw);
+  /// }
+  /// \endcode
   template<typename Graph>
   class GraphWrapper {
@@ -110 +167 @@
     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }    
 //    template<typename I> I& next(I &i) const { graph->next(i); return i; }    
-    template< typename It > It first() const { 
-      It e; this->first(e); return e; }
-
-    template< typename It > It first(const Node& v) const { 
-      It e; this->first(e, v); return e; }
+//     template< typename It > It first() const { 
+//       It e; this->first(e); return e; }
+
+//     template< typename It > It first(const Node& v) const { 
+//       It e; this->first(e, v); return e; }
 
     Node head(const Edge& e) const { 
@@ -275 +332 @@
   };
 
-  //Subgraph on the same node-set and partial edge-set
+  /// Wrapper for hiding nodes and edges from a graph.
+  
+  /// This wrapper shows a graph with filtered node-set and 
+  /// edge-set. The quick brown fox iterators jumps over 
+  /// the lazy dog nodes or edges if the values for them are false 
+  /// in the bool maps. 
   template<typename Graph, typename NodeFilterMap, 
            typename EdgeFilterMap>
@@ -484 +546 @@
     bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
 
-    template< typename It > It first() const { 
-      It e; this->first(e); return e; }
-    
-    template< typename It > It first(const Node& v) const { 
-      It e; this->first(e, v); return e; }
+//     template< typename It > It first() const { 
+//       It e; this->first(e); return e; }
+    
+//     template< typename It > It first(const Node& v) const { 
+//       It e; this->first(e, v); return e; }
   };
 
@@ -743 +805 @@
     }
 
-    template<typename I> I& first(I& i) const { graph->first(i); return i; }
-    template<typename I, typename P> I& first(I& i, const P& p) const { 
-      graph->first(i, p); return i; }
+//     template<typename I> I& first(I& i) const { graph->first(i); return i; }
+//     template<typename I, typename P> I& first(I& i, const P& p) const { 
+//       graph->first(i, p); return i; }
 
     NodeIt& next(NodeIt& n) const {
@@ -769 +831 @@
 
 //    template<typename I> I& next(I &i) const { graph->next(i); return i; }    
-    template< typename It > It first() const { 
-      It e; this->first(e); return e; }
-
-    template< typename It > It first(const Node& v) const { 
-      It e; this->first(e, v); return e; }
+//     template< typename It > It first() const { 
+//       It e; this->first(e); return e; }
+
+//     template< typename It > It first(const Node& v) const { 
+//       It e; this->first(e, v); return e; }
 
 //    Node head(const Edge& e) const { return gw.head(e); }
@@ -1252 +1314 @@
     
 
-    template< typename It >
-    It first() const { 
-      It e;
-      first(e);
-      return e; 
-    }
-
-    template< typename It >
-    It first(Node v) const { 
-      It e;
-      first(e, v);
-      return e; 
-    }
+//     template< typename It >
+//     It first() const { 
+//       It e;
+//       first(e);
+//       return e; 
+//     }
+
+//     template< typename It >
+//     It first(Node v) const { 
+//       It e;
+//       first(e, v);
+//       return e; 
+//     }
 
     Node tail(Edge e) const { 
@@ -1801 +1863 @@
 //     }
     
-    template< typename It > It first() const { 
-      It e; this->first(e); return e; }
-    
-    template< typename It > It first(const Node& v) const { 
-      It e; this->first(e, v); return e; }
+//     template< typename It > It first() const { 
+//       It e; this->first(e); return e; }
+    
+//     template< typename It > It first(const Node& v) const { 
+//       It e; this->first(e, v); return e; }
 
     void erase(const OutEdgeIt& e) const {