# HG changeset patch
# User marci
# Date 1094147800 0
# Node ID 147eb3a58706f42ca84bb6d20b55ee4850e2af0d
# Parent  7a54630d22b657aa32b2609deb0ca58094464781
Nicer and more documented graph_wrapper.h file.
These are only the first steps for making this file more beautiful.

diff -r 7a54630d22b6 -r 147eb3a58706 src/hugo/graph_wrapper.h
--- a/src/hugo/graph_wrapper.h	Thu Sep 02 17:30:06 2004 +0000
+++ b/src/hugo/graph_wrapper.h	Thu Sep 02 17:56:40 2004 +0000
@@ -100,17 +100,6 @@
 //     Graph& getGraph() const { return *graph; }
  
     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;
       friend class GraphWrapper<Graph>;
@@ -129,13 +118,6 @@
       }
     };
     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;
       friend class GraphWrapper<Graph>;
@@ -277,13 +259,10 @@
 
     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;
       friend class GraphWrapper<Graph>;
@@ -382,21 +361,6 @@
       edge_filter_map(&_edge_filter_map) { }  
 
     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;
       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
@@ -560,21 +524,19 @@
     /// Returns true if \c n is hidden.
     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; 
     }
 
@@ -689,15 +651,31 @@
 
 
   ///\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>
   class SubBidirGraphWrapper : public GraphWrapper<Graph> {
@@ -707,8 +685,7 @@
     ForwardFilterMap* forward_filter;
     BackwardFilterMap* backward_filter;
 
-    SubBidirGraphWrapper() : GraphWrapper<Graph>()/*, 
-						 capacity(0), flow(0)*/ { }
+    SubBidirGraphWrapper() : GraphWrapper<Graph>() { }
     void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
       forward_filter=&_forward_filter;
     }
@@ -733,25 +710,25 @@
     friend class Edge; 
     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) { }
       Edge(Invalid i) : Graph::Edge(i), backward(true) { }
@@ -958,7 +935,6 @@
     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
       i=OutEdgeIt(*this, p); return i;
     }
-//    FIXME not tested
     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
       i=InEdgeIt(*this, p); return i;
     }
@@ -1052,54 +1028,22 @@
       return f;
     }
 
-//    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; 
     public:
@@ -1113,15 +1057,15 @@
 	forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
       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() { 
 	forward_map.update(); 
@@ -1137,12 +1081,9 @@
   };
 
 
-
   ///\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 
   /// the maps are able to attach different values for them.
@@ -1159,22 +1100,12 @@
       ConstMap<typename Graph::Edge, bool> > Parent; 
   protected:
     ConstMap<typename Graph::Edge, bool> cm;
-    //const CapacityMap* capacity;
-    //FlowMap* flow;
 
     BidirGraphWrapper() : Parent(), cm(true) { 
       Parent::setForwardFilterMap(cm);
       Parent::setBackwardFilterMap(cm);
     }
-//     void setCapacityMap(const CapacityMap& _capacity) {
-//       capacity=&_capacity;
-//     }
-//     void setFlowMap(FlowMap& _flow) {
-//       flow=&_flow;
-//     }
-
   public:
-
     BidirGraphWrapper(Graph& _graph) : Parent() { 
       Parent::setGraph(_graph);
       Parent::setForwardFilterMap(cm);
@@ -1188,29 +1119,19 @@
 
 
 
-
+  // 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> {
   public:
     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;
-//     }
+    OldBidirGraphWrapper() : GraphWrapper<Graph>() { }
 
   public:
 
-    OldBidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, 
-				     FlowMap& _flow*/) : 
-      GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
+    OldBidirGraphWrapper(Graph& _graph) : 
+      GraphWrapper<Graph>(_graph) { }
 
     class Edge; 
     class OutEdgeIt; 
@@ -1459,15 +1380,6 @@
     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)); 
@@ -1662,7 +1574,7 @@
 
     /// \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:
       const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
@@ -2007,14 +1919,15 @@
 
   /// 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 
   /// OutEdgeIt& first(OutEdgeIt&, const Node&)
   /// \endcode
   /// is called. 
   ///
-  ///\author Marton Makai
+  /// \author Marton Makai
   template<typename Graph, typename FirstOutEdgesMap>
   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
   public:
@@ -2027,18 +1940,6 @@
       GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }  
 
     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 { 
       friend class GraphWrapper<Graph>;