Changeset 792:147eb3a58706 in lemon-0.x for src/hugo/graph_wrapper.h

Timestamp:

09/02/04 19:56:40 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

Nicer and more documented graph_wrapper.h file.
These are only the first steps for making this file more beautiful.

File:

• src/hugo/graph_wrapper.h (modified) (21 diffs)

src/hugo/graph_wrapper.h

@@ -101 +101 @@
  
     typedef typename Graph::Node Node;
-//     class Node : public Graph::Node {
-//       friend class GraphWrapper<Graph>;
-//     public:
-//       Node() { }
-//       Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
-//       // /// \bug construction throughrthr multiple levels should be 
-//       // /// handled better
-//       // Node(const typename ParentGraph::ParentGraph::Node& _n) : 
-//       // Graph::Node(_n) { }
-//       Node(const Invalid& i) : Graph::Node(i) { }
-//     };
     class NodeIt : public Node { 
       const GraphWrapper<Graph>* gw;
@@ -130 +119 @@
     };
     typedef typename Graph::Edge Edge;
-//     class Edge : public Graph::Edge {
-//       friend class GraphWrapper<Graph>;
-//     public:
-//       Edge() { }
-//       Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
-//       Edge(const Invalid& i) : Graph::Edge(i) { }
-//     };
     class OutEdgeIt : public Edge { 
       const GraphWrapper<Graph>* gw;
@@ -278 +260 @@
     typedef typename GraphWrapper<Graph>::Node Node;
     typedef typename GraphWrapper<Graph>::Edge Edge;
-    //If Graph::OutEdgeIt is not defined
-    //and we do not want to use RevGraphWrapper::InEdgeIt,
-    //the typdef techinque does not work.
-    //Unfortunately all the typedefs are instantiated in templates.
-    //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
-    //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
-
+    //remark: OutEdgeIt and InEdgeIt cannot be typedef-ed to each other
+    //because this does not work is some of them are not defined in the 
+    //original graph. The problem with this is that typedef-ed stuff 
+    //are instantiated in c++.
     class OutEdgeIt : public Edge { 
       const RevGraphWrapper<Graph>* gw;
@@ -383 +362 @@
 
     typedef typename GraphWrapper<Graph>::Node Node;
-//     class NodeIt { 
-//       friend class GraphWrapper<Graph>;
-//       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
-//       typename Graph::NodeIt n;
-//      public:
-//       NodeIt() { }
-//       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
-//       NodeIt(const Invalid& i) : n(i) { }
-//       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
-//      n(*(_G.graph)) { 
-//      while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n]) 
-//        _G.graph->next(n);
-//       }
-//       operator Node() const { return Node(typename Graph::Node(n)); }
-//     };
     class NodeIt : public Node { 
       const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
@@ -561 +525 @@
     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
 
-    /// This is a linear time operation and works only if 
-    /// NodeIt is defined.
+    /// \warning This is a linear time operation and works only if 
+    /// \c Graph::NodeIt is defined.
     int nodeNum() const { 
       int i=0;
-      NodeIt n;
-      for (this->first(n); this->valid(n); this->next(n)) ++i;
+      for (NodeIt n(*this); n!=INVALID; ++n) ++i;
       return i; 
     }
 
-    /// This is a linear time operation and works only if 
-    /// EdgeIt is defined.
+    /// \warning This is a linear time operation and works only if 
+    /// \c Graph::EdgeIt is defined.
     int edgeNum() const { 
       int i=0;
-      EdgeIt e;
-      for (this->first(e); this->valid(e); this->next(e)) ++i;
+      for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
       return i; 
     }
@@ -690 +652 @@
 
   ///\brief A wrapper for composing a subgraph of a 
-  /// bidirected graph composed from a directed one. 
-  /// experimental, for fezso's sake.
+  /// bidirected graph made from a directed one. 
   ///
-  /// A wrapper for composing a subgraps of a 
-  /// bidirected graph composed from a directed one. 
-  /// experimental, for fezso's sake.
-  /// A bidirected graph is composed over the directed one without physical 
-  /// storage. As the oppositely directed edges are logically different ones 
-  /// the maps are able to attach different values for them.
+  /// Suppose that for a directed graph $G=(V, A)$, 
+  /// two predicates on the edge-set, $forward_filter$, and $backward_filter$ 
+  /// is given, and we are dealing with the directed graph
+  /// a $G'=(V, \{uv : uv\in A \mbox{ and } forward_filter(uv) \mbox{ is true}\}+\{vu : uv\in A \mbox{ and } backward_filter(uv) \mbox{ is true}\})$. 
+  /// The purpose of writing + instead of union is because parallel 
+  /// edges can arose. 
+  /// In other words, a subgraph of the bidirected graph obtained, which 
+  /// is given by orienting the edges of the original graph in both directions.
+  /// An example for such a construction is the \c RevGraphWrapper where the 
+  /// forward_filter is everywhere false and the backward_filter is 
+  /// everywhere true. We note that for sake of efficiency, 
+  /// \c RevGraphWrapper is implemented in a different way. 
+  /// But BidirGraphWrapper is obtained from 
+  /// SubBidirGraphWrapper by considering everywhere true 
+  /// predicates both forward_filter and backward_filter. 
+  /// Finally, one of the most important applications of SubBidirGraphWrapper 
+  /// is ResGraphWrapper, which stands for the residual graph in directed 
+  /// flow and circulation problems. 
+  /// As wrappers usually, the SubBidirGraphWrapper implements the 
+  /// above mentioned graph structure without its physical storage, 
+  /// that is the whole stuff eats constant memory. 
+  /// As the oppositely directed edges are logical different, 
+  /// the maps are able to attach different values for them. 
   template<typename Graph, 
            typename ForwardFilterMap, typename BackwardFilterMap>
@@ -708 +686 @@
     BackwardFilterMap* backward_filter;
 
-    SubBidirGraphWrapper() : GraphWrapper<Graph>()/*, 
-                                                 capacity(0), flow(0)*/ { }
+    SubBidirGraphWrapper() : GraphWrapper<Graph>() { }
     void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
       forward_filter=&_forward_filter;
@@ -734 +711 @@
     friend class OutEdgeIt; 
 
-    //template<typename T> class NodeMap;    
     template<typename T> class EdgeMap;
 
     typedef typename GraphWrapper<Graph>::Node Node;
-    //typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
 
     typedef typename Graph::Edge GraphEdge;
+    /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from 
+    /// Graph::Edge. It contains an extra bool flag which shows if the 
+    /// edge is the backward version of the original edge.
     class Edge : public Graph::Edge {
       friend class SubBidirGraphWrapper<Graph, 
                                         ForwardFilterMap, BackwardFilterMap>;
-      ///\bug ez nem is kell
-      //template<typename T> friend class NodeMap;
       template<typename T> friend class EdgeMap;
     protected:
       bool backward; //true, iff backward
-//      typename Graph::Edge e;
     public:
       Edge() { }
-      ///\bug =false kell-e? zsoltnak kell az addEdge miatt
+      /// \todo =false is needed, or causes problems?
+      /// If \c _backward is false, then we get an edge corresponding to the 
+      /// original one, otherwise its oppositely directed pair is obtained.
       Edge(const typename Graph::Edge& e, bool _backward/*=false*/) : 
         Graph::Edge(e), backward(_backward) { }
@@ -959 +936 @@
       i=OutEdgeIt(*this, p); return i;
     }
-//    FIXME not tested
     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
       i=InEdgeIt(*this, p); return i;
@@ -1053 +1029 @@
     }
 
-//    int nodeNum() const { return graph->nodeNum(); }
-    //FIXME
-    void edgeNum() const { }
-    //int edgeNum() const { return graph->edgeNum(); }
-
-
-//    int id(Node v) const { return graph->id(v); }
-
-//     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
-//     bool valid(Edge e) const { 
-//       return this->graph->valid(e);
-//      //return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
-//     }
+    /// \warning This is a linear time operation and works only if 
+    /// \c Graph::EdgeIt is defined.
+    int edgeNum() const { 
+      int i=0;
+      for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
+      return i; 
+    }
 
     bool forward(const Edge& e) const { return !e.backward; }
     bool backward(const Edge& e) const { return e.backward; }
 
-//     void augment(const Edge& e, Number a) const {
-//       if (!e.backward)  
-// //   flow->set(e.out, flow->get(e.out)+a);
-//      flow->set(e, (*flow)[e]+a);
-//       else  
-// //   flow->set(e.in, flow->get(e.in)-a);
-//      flow->set(e, (*flow)[e]-a);
-//     }
-
-//     bool enabled(const Edge& e) const { 
-//       if (!e.backward) 
-// //   return (capacity->get(e.out)-flow->get(e.out)); 
-//      //return ((*capacity)[e]-(*flow)[e]);
-//      return true;
-//       else 
-// //   return (flow->get(e.in)); 
-//      //return ((*flow)[e]); 
-//      return true;
-//     }
-
-//     Number enabled(typename Graph::OutEdgeIt out) const { 
-// //      return (capacity->get(out)-flow->get(out)); 
-//       return ((*capacity)[out]-(*flow)[out]); 
-//     }
-    
-//     Number enabled(typename Graph::InEdgeIt in) const { 
-// //      return (flow->get(in)); 
-//       return ((*flow)[in]); 
-//     }
 
     template <typename T>
+    /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two 
+    /// Graph::EdgeMap one for the forward edges and 
+    /// one for the backward edges.
     class EdgeMap {
       typename Graph::template EdgeMap<T> forward_map, backward_map; 
@@ -1114 +1058 @@
       void set(Edge e, T a) { 
         if (!e.backward) 
-          forward_map.set(e/*.out*/, a); 
+          forward_map.set(e, a); 
         else 
-          backward_map.set(e/*.in*/, a); 
+          backward_map.set(e, a); 
       }
       T operator[](Edge e) const { 
         if (!e.backward) 
-          return forward_map[e/*.out*/]; 
+          return forward_map[e]; 
         else 
-          return backward_map[e/*.in*/]; 
+          return backward_map[e]; 
       }
       void update() { 
@@ -1138 +1082 @@
 
 
-
   ///\brief A wrapper for composing bidirected graph from a directed one. 
-  /// experimental, for fezso's sake.
   ///
   /// A wrapper for composing bidirected graph from a directed one. 
-  /// experimental, for fezso's sake.
   /// A bidirected graph is composed over the directed one without physical 
   /// storage. As the oppositely directed edges are logically different ones 
@@ -1160 +1101 @@
   protected:
     ConstMap<typename Graph::Edge, bool> cm;
-    //const CapacityMap* capacity;
-    //FlowMap* flow;
 
     BidirGraphWrapper() : Parent(), cm(true) { 
@@ -1167 +1106 @@
       Parent::setBackwardFilterMap(cm);
     }
-//     void setCapacityMap(const CapacityMap& _capacity) {
-//       capacity=&_capacity;
-//     }
-//     void setFlowMap(FlowMap& _flow) {
-//       flow=&_flow;
-//     }
-
-  public:
-
+  public:
     BidirGraphWrapper(Graph& _graph) : Parent() { 
       Parent::setGraph(_graph);
@@ -1189 +1120 @@
 
 
-
+  // this is a direct implementation of the bidirected-graph wrapper. 
+  // in early hugo, it was implemented that way.
   template<typename Graph>
   class OldBidirGraphWrapper : public GraphWrapper<Graph> {
@@ -1195 +1127 @@
     typedef GraphWrapper<Graph> Parent; 
   protected:
-    //const CapacityMap* capacity;
-    //FlowMap* flow;
-
-    OldBidirGraphWrapper() : GraphWrapper<Graph>()/*, 
-                                                 capacity(0), flow(0)*/ { }
-//     void setCapacityMap(const CapacityMap& _capacity) {
-//       capacity=&_capacity;
-//     }
-//     void setFlowMap(FlowMap& _flow) {
-//       flow=&_flow;
-//     }
-
-  public:
-
-    OldBidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, 
-                                     FlowMap& _flow*/) : 
-      GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
+    OldBidirGraphWrapper() : GraphWrapper<Graph>() { }
+
+  public:
+
+    OldBidirGraphWrapper(Graph& _graph) : 
+      GraphWrapper<Graph>(_graph) { }
 
     class Edge; 
@@ -1460 +1381 @@
     bool backward(const Edge& e) const { return e.backward; }
 
-//     void augment(const Edge& e, Number a) const {
-//       if (!e.backward)  
-// //   flow->set(e.out, flow->get(e.out)+a);
-//      flow->set(e, (*flow)[e]+a);
-//       else  
-// //   flow->set(e.in, flow->get(e.in)-a);
-//      flow->set(e, (*flow)[e]-a);
-//     }
-
     bool enabled(const Edge& e) const { 
       if (!e.backward) 
@@ -1663 +1575 @@
     /// \brief Residual capacity map.
     ///
-    /// In generic residual graphs the residual capacity can be obtained as a map.
+    /// In generic residual graphs the residual capacity can be obtained as a map. Not tested.
     class ResCap {
     protected:
@@ -2008 +1920 @@
   /// For blocking flows.
 
-  /// This graph wrapper is used for Dinits blocking flow computations.
+  /// This graph wrapper is used for on-the-fly 
+  /// Dinits blocking flow computations.
   /// For each node, an out-edge is stored which is used when the 
   /// \code 
@@ -2015 +1928 @@
   /// is called. 
   ///
-  ///\author Marton Makai
+  /// \author Marton Makai
   template<typename Graph, typename FirstOutEdgesMap>
   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
@@ -2028 +1941 @@
 
     typedef typename GraphWrapper<Graph>::Node Node;
-//     class NodeIt { 
-//       friend class GraphWrapper<Graph>;
-//       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
-//       typename Graph::NodeIt n;
-//      public:
-//       NodeIt() { }
-//       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
-//       NodeIt(const Invalid& i) : n(i) { }
-//       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
-//      n(*(_G.graph)) { }
-//       operator Node() const { return Node(typename Graph::Node(n)); }
-//     };
     typedef typename GraphWrapper<Graph>::Edge Edge;
     class OutEdgeIt : public Edge {