# HG changeset patch
# User marci
# Date 1083915884 0
# Node ID 3b6afd33c221ef63a7977d10e3ddb1fcf264eaa4
# Parent  ed0a4de239230adf28919f9a9959be4c0cb0413d
BidirGraphWrapper<Graph>, the map values are different for the opposite edges.

diff -r ed0a4de23923 -r 3b6afd33c221 src/hugo/graph_wrapper.h
--- a/src/hugo/graph_wrapper.h	Fri May 07 06:58:24 2004 +0000
+++ b/src/hugo/graph_wrapper.h	Fri May 07 07:44:44 2004 +0000
@@ -218,6 +218,8 @@
     };
   };
 
+
+
   /// A graph wrapper which reverses the orientation of the edges.
 
   /// A graph wrapper which reverses the orientation of the edges.
@@ -292,6 +294,8 @@
 
   };
 
+
+
   /// Wrapper for hiding nodes and edges from a graph.
   
   /// This wrapper shows a graph with filtered node-set and 
@@ -463,6 +467,8 @@
     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
   };
 
+
+
   /// A wrapper for forgetting the orientation of a graph.
 
   /// A wrapper for getting an undirected graph by forgetting
@@ -560,7 +566,321 @@
     }
   };
 
+
+
+  /// A wrapper for composing bidirected graph from a directed one. 
+  /// experimental, for fezso's sake.
+  template<typename Graph>
+  class BidirGraphWrapper : public GraphWrapper<Graph> {
+  protected:
+    //const CapacityMap* capacity;
+    //FlowMap* flow;
+
+    BidirGraphWrapper() : GraphWrapper<Graph>()/*, 
+						 capacity(0), flow(0)*/ { }
+//     void setCapacityMap(const CapacityMap& _capacity) {
+//       capacity=&_capacity;
+//     }
+//     void setFlowMap(FlowMap& _flow) {
+//       flow=&_flow;
+//     }
+
+  public:
+
+    BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, 
+				     FlowMap& _flow*/) : 
+      GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
+
+    class Edge; 
+    class OutEdgeIt; 
+    friend class Edge; 
+    friend class OutEdgeIt; 
+
+    typedef typename GraphWrapper<Graph>::Node Node;
+    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
+    class Edge : public Graph::Edge {
+      friend class BidirGraphWrapper<Graph>;
+    protected:
+      bool backward; //true, iff backward
+//      typename Graph::Edge e;
+    public:
+      Edge() { }
+      Edge(const typename Graph::Edge& _e, bool _backward) : 
+	Graph::Edge(_e), backward(_backward) { }
+      Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
+//the unique invalid iterator
+      friend bool operator==(const Edge& u, const Edge& v) { 
+	return (v.backward==u.backward && 
+		static_cast<typename Graph::Edge>(u)==
+		static_cast<typename Graph::Edge>(v));
+      } 
+      friend bool operator!=(const Edge& u, const Edge& v) { 
+	return (v.backward!=u.backward || 
+		static_cast<typename Graph::Edge>(u)!=
+		static_cast<typename Graph::Edge>(v));
+      } 
+    };
+
+    class OutEdgeIt {
+      friend class BidirGraphWrapper<Graph>;
+    protected:
+      typename Graph::OutEdgeIt out;
+      typename Graph::InEdgeIt in;
+      bool backward;
+    public:
+      OutEdgeIt() { }
+      //FIXME
+//      OutEdgeIt(const Edge& e) : Edge(e) { }
+      OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
+//the unique invalid iterator
+      OutEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) { 
+	backward=false;
+	_G.graph->first(out, v);
+	while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
+	if (!_G.graph->valid(out)) {
+	  backward=true;
+	  _G.graph->first(in, v);
+	  while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
+	}
+      }
+      operator Edge() const { 
+//	Edge e;
+//	e.forward=this->forward;
+//	if (this->forward) e=out; else e=in;
+//	return e;
+	if (this->backward) 
+	  return Edge(in, this->backward); 
+	else 
+	  return Edge(out, this->backward);
+      }
+    };
+
+    class InEdgeIt {
+      friend class BidirGraphWrapper<Graph>;
+    protected:
+      typename Graph::OutEdgeIt out;
+      typename Graph::InEdgeIt in;
+      bool backward;
+    public:
+      InEdgeIt() { }
+      //FIXME
+//      OutEdgeIt(const Edge& e) : Edge(e) { }
+      InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
+//the unique invalid iterator
+      InEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) { 
+	backward=false;
+	_G.graph->first(in, v);
+	while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
+	if (!_G.graph->valid(in)) {
+	  backward=true;
+	  _G.graph->first(out, v);
+	  while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
+	}
+      }
+      operator Edge() const { 
+//	Edge e;
+//	e.forward=this->forward;
+//	if (this->forward) e=out; else e=in;
+//	return e;
+	if (this->backward) 
+	  return Edge(out, this->backward); 
+	else 
+	  return Edge(in, this->backward);
+      }
+    };
+
+    class EdgeIt {
+      friend class BidirGraphWrapper<Graph>;
+    protected:
+      typename Graph::EdgeIt e;
+      bool backward;
+    public:
+      EdgeIt() { }
+      EdgeIt(const Invalid& i) : e(i), backward(true) { }
+      EdgeIt(const BidirGraphWrapper<Graph>& _G) { 
+	backward=false;
+	_G.graph->first(e);
+	while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
+	if (!_G.graph->valid(e)) {
+	  backward=true;
+	  _G.graph->first(e);
+	  while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
+	}
+      }
+      operator Edge() const { 
+	return Edge(e, this->backward);
+      }
+    };
+
+    using GraphWrapper<Graph>::first;
+//     NodeIt& first(NodeIt& i) const { 
+//       i=NodeIt(*this); return i;
+//     }
+    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;
+    }
+    EdgeIt& first(EdgeIt& i) const { 
+      i=EdgeIt(*this); return i;
+    }
   
+    using GraphWrapper<Graph>::next;
+//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
+    OutEdgeIt& next(OutEdgeIt& e) const { 
+      if (!e.backward) {
+	Node v=this->graph->aNode(e.out);
+	this->graph->next(e.out);
+	while(this->graph->valid(e.out) && !enabled(e)) { 
+	  this->graph->next(e.out); }
+	if (!this->graph->valid(e.out)) {
+	  e.backward=true;
+	  this->graph->first(e.in, v); 
+	  while(this->graph->valid(e.in) && !enabled(e)) { 
+	    this->graph->next(e.in); }
+	}
+      } else {
+	this->graph->next(e.in);
+	while(this->graph->valid(e.in) && !enabled(e)) { 
+	  this->graph->next(e.in); } 
+      }
+      return e;
+    }
+//     FIXME Not tested
+    InEdgeIt& next(InEdgeIt& e) const { 
+      if (!e.backward) {
+	Node v=this->graph->aNode(e.in);
+	this->graph->next(e.in);
+	while(this->graph->valid(e.in) && !enabled(e)) { 
+	  this->graph->next(e.in); }
+	if (!this->graph->valid(e.in)) {
+	  e.backward=true;
+	  this->graph->first(e.out, v); 
+	  while(this->graph->valid(e.out) && !enabled(e)) { 
+	    this->graph->next(e.out); }
+	}
+      } else {
+	this->graph->next(e.out);
+	while(this->graph->valid(e.out) && !enabled(e)) { 
+	  this->graph->next(e.out); } 
+      }
+      return e;
+    }
+    EdgeIt& next(EdgeIt& e) const {
+      if (!e.backward) {
+	this->graph->next(e.e);
+	while(this->graph->valid(e.e) && !enabled(e)) { 
+	  this->graph->next(e.e); }
+	if (!this->graph->valid(e.e)) {
+	  e.backward=true;
+	  this->graph->first(e.e); 
+	  while(this->graph->valid(e.e) && !enabled(e)) { 
+	    this->graph->next(e.e); }
+	}
+      } else {
+	this->graph->next(e.e);
+	while(this->graph->valid(e.e) && !enabled(e)) { 
+	  this->graph->next(e.e); } 
+      }
+      return e;
+    }
+
+    Node tail(Edge e) const { 
+      return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
+    Node head(Edge e) const { 
+      return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
+
+    Node aNode(OutEdgeIt e) const { 
+      return ((!e.backward) ? this->graph->aNode(e.out) : 
+	      this->graph->aNode(e.in)); }
+    Node bNode(OutEdgeIt e) const { 
+      return ((!e.backward) ? this->graph->bNode(e.out) : 
+	      this->graph->bNode(e.in)); }
+
+    Node aNode(InEdgeIt e) const { 
+      return ((!e.backward) ? this->graph->aNode(e.in) : 
+	      this->graph->aNode(e.out)); }
+    Node bNode(InEdgeIt e) const { 
+      return ((!e.backward) ? this->graph->bNode(e.in) : 
+	      this->graph->bNode(e.out)); }
+
+//    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); 
+    }
+
+    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>
+    class EdgeMap {
+      typename Graph::template EdgeMap<T> forward_map, backward_map; 
+    public:
+      EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
+      EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : 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); 
+	else 
+	  backward_map.set(e.in, a); 
+      }
+      T operator[](Edge e) const { 
+	if (!e.backward) 
+	  return forward_map[e.out]; 
+	else 
+	  return backward_map[e.in]; 
+      }
+//       T get(Edge e) const { 
+// 	if (e.out_or_in) 
+// 	  return forward_map.get(e.out); 
+// 	else 
+// 	  return backward_map.get(e.in); 
+//       }
+    };
+  };
+
+
 
   /// A wrapper for composing the residual graph for directed flow and circulation problems.
 
@@ -629,14 +949,14 @@
 //      OutEdgeIt(const Edge& e) : Edge(e) { }
       OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
 //the unique invalid iterator
-      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { 
+      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { 
 	backward=false;
-	resG.graph->first(out, v);
-	while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
-	if (!resG.graph->valid(out)) {
+	_G.graph->first(out, v);
+	while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
+	if (!_G.graph->valid(out)) {
 	  backward=true;
-	  resG.graph->first(in, v);
-	  while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
+	  _G.graph->first(in, v);
+	  while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
 	}
       }
       operator Edge() const { 
@@ -663,14 +983,14 @@
 //      OutEdgeIt(const Edge& e) : Edge(e) { }
       InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
 //the unique invalid iterator
-      InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { 
+      InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { 
 	backward=false;
-	resG.graph->first(in, v);
-	while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
-	if (!resG.graph->valid(in)) {
+	_G.graph->first(in, v);
+	while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
+	if (!_G.graph->valid(in)) {
 	  backward=true;
-	  resG.graph->first(out, v);
-	  while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
+	  _G.graph->first(out, v);
+	  while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
 	}
       }
       operator Edge() const { 
@@ -693,14 +1013,14 @@
     public:
       EdgeIt() { }
       EdgeIt(const Invalid& i) : e(i), backward(true) { }
-      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) { 
+      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) { 
 	backward=false;
-	resG.graph->first(e);
-	while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
-	if (!resG.graph->valid(e)) {
+	_G.graph->first(e);
+	while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
+	if (!_G.graph->valid(e)) {
 	  backward=true;
-	  resG.graph->first(e);
-	  while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
+	  _G.graph->first(e);
+	  while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
 	}
       }
       operator Edge() const { 
@@ -874,6 +1194,8 @@
     };
   };
 
+
+
   /// ErasingFirstGraphWrapper for blocking flows.
 
   /// ErasingFirstGraphWrapper for blocking flows.
diff -r ed0a4de23923 -r 3b6afd33c221 src/work/marci/iterator_bfs_demo.cc
--- a/src/work/marci/iterator_bfs_demo.cc	Fri May 07 06:58:24 2004 +0000
+++ b/src/work/marci/iterator_bfs_demo.cc	Fri May 07 07:44:44 2004 +0000
@@ -314,5 +314,88 @@
     }
   }
 
+
+
+  {
+    typedef BidirGraphWrapper<const Graph> GW;
+    GW gw(G);
+    
+    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
+    
+    cout << "bfs and dfs iterator demo on the undirected graph" << endl;
+    for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { 
+      cout << node_name[GW::Node(n)] << ": ";
+      cout << "out edges: ";
+      for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 
+	cout << edge_name[e] << " ";
+      cout << "in edges: ";
+      for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 
+	cout << edge_name[e] << " ";
+      cout << endl;
+    }
+//     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) { 
+//       cout << edge_name.get(e) << " ";
+//     }
+//     cout << endl;
+
+    cout << "bfs from t ..." << endl;
+    BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
+    bfs.pushAndSetReached(t);
+    while (!bfs.finished()) {
+      //cout << "edge: ";
+      if (gw.valid(GW::OutEdgeIt(bfs))) {
+	cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << 
+	  node_name[gw.aNode(bfs)] << 
+	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+	  node_name[gw.bNode(bfs)] << 
+	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
+	   ": is not newly reached.");
+      } else { 
+	cout << "invalid" << /*endl*/", " << 
+	  node_name[bfs.aNode()] << 
+	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+	  
+	  "invalid.";
+      }
+      cout << endl;
+      ++bfs;
+    }
+
+    cout << "    /-->    ------------->            "<< endl;
+    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
+    cout << "  / |          |    /  /->     \\     "<< endl;
+    cout << " /  |          |   /  |    ^    \\  "<< endl;
+    cout << "s   |          |  /   |    |     \\->  t "<< endl;
+    cout << " \\  |          | /    |    |     /->  "<< endl;
+    cout << "  \\ |       --/ /     |    |    /     "<< endl;
+    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
+    cout << "    \\-->    ------------->         "<< endl;
+    
+    cout << "dfs from t ..." << endl;
+    DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
+    dfs.pushAndSetReached(t);
+    while (!dfs.finished()) {
+      ++dfs;
+      //cout << "edge: ";
+      if (gw.valid(GW::OutEdgeIt(dfs))) {
+	cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << 
+	  node_name[gw.aNode(dfs)] << 
+	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+	  node_name[gw.bNode(dfs)] << 
+	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
+	   ": is not newly reached.");
+      } else { 
+	cout << "invalid" << /*endl*/", " << 
+	  node_name[dfs.aNode()] << 
+	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+	  
+	  "invalid.";
+      }
+      cout << endl;
+    }
+  }
+
+
+
   return 0;
 }