lemon-0.x: comparison src/hugo/graph

equal deleted inserted replaced

-:80d2f67e4b41
+:bf5717581e8a
 ///This file contains several useful graph wrapper functions.
 ///
 ///\author Marton Makai
 #include <hugo/invalid.h>
+#include <hugo/maps.h>
 //#include <iter_map.h>
 namespace hugo {
 // Graph wrappers
 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 {
 friend class GraphWrapper<Graph>;
 typename Graph::NodeIt n;
 void erase(const Node& i) const { graph->erase(i); }
 void erase(const Edge& i) const { graph->erase(i); }
 void clear() const { graph->clear(); }
+bool forward(const Edge& e) const { graph->forward(e); }
+bool backward(const Edge& e) const { graph->backward(e); }
+Edge opposite(const Edge& e) const { Edge(graph->opposite(e)); }
 template<typename T> class NodeMap : public Graph::template NodeMap<T> {
 typedef typename Graph::template NodeMap<T> Parent;
 public:
 NodeMap(const GraphWrapper<Graph>& _G) :  Parent(*(_G.graph)) { }
 NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
 /// Thus \c Graph have to be a directed graph type.
 ///
 ///\author Marton Makai
 template<typename Graph>
 class RevGraphWrapper : public GraphWrapper<Graph> {
+public:
+typedef GraphWrapper<Graph> Parent;
 protected:
 RevGraphWrapper() : GraphWrapper<Graph>() { }
 public:
 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
 ///
 ///\author Marton Makai
 template<typename Graph, typename NodeFilterMap,
 	   typename EdgeFilterMap>
 class SubGraphWrapper : public GraphWrapper<Graph> {
+public:
+typedef GraphWrapper<Graph> Parent;
 protected:
 NodeFilterMap* node_filter_map;
 EdgeFilterMap* edge_filter_map;
 SubGraphWrapper() : GraphWrapper<Graph>(),
 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
 edge_filter_map=&_edge_filter_map;
 }
 public:
 SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
 		    EdgeFilterMap& _edge_filter_map) :
 GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
 edge_filter_map(&_edge_filter_map) { }
 /// the orientation of a directed one.
 ///
 /// \author Marton Makai
 template<typename Graph>
 class UndirGraphWrapper : public GraphWrapper<Graph> {
+public:
+typedef GraphWrapper<Graph> Parent;
 protected:
 UndirGraphWrapper() : GraphWrapper<Graph>() { }
 public:
 typedef typename GraphWrapper<Graph>::Node Node;
 Parent::setGraph(gr);
 }
 };
-///\brief A wrapper for composing bidirected graph from a directed one.
+///\brief A wrapper for composing a subgraph of a
+/// bidirected graph composed from a directed one.
 /// experimental, for fezso's sake.
 ///
-/// A wrapper for composing bidirected graph 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.
-template<typename Graph>
+template<typename Graph,
-class BidirGraphWrapper : public GraphWrapper<Graph> {
+	   typename ForwardFilterMap, typename BackwardFilterMap>
+class SubBidirGraphWrapper : public GraphWrapper<Graph> {
+public:
+typedef GraphWrapper<Graph> Parent;
 protected:
 //const CapacityMap* capacity;
 //FlowMap* flow;
-BidirGraphWrapper() : GraphWrapper<Graph>()/*,
+ForwardFilterMap* forward_filter;
+BackwardFilterMap* backward_filter;
+SubBidirGraphWrapper() : GraphWrapper<Graph>()/*,
 						 capacity(0), flow(0)*/ { }
-//     void setCapacityMap(const CapacityMap& _capacity) {
+void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
-//       capacity=&_capacity;
+forward_filter=&_forward_filter;
-//     }
+}
-//     void setFlowMap(FlowMap& _flow) {
+void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
-//       flow=&_flow;
+backward_filter=&_backward_filter;
-//     }
+}
 public:
-BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity,
+SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter,
-				     FlowMap& _flow*/) :
+			 BackwardFilterMap& _backward_filter) :
-GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
+GraphWrapper<Graph>(_graph),
+forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
 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>;
+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
 		static_cast<typename Graph::Edge>(v));
 }
 };
 class OutEdgeIt {
-friend class BidirGraphWrapper<Graph>;
+friend class SubBidirGraphWrapper<Graph,
+					ForwardFilterMap, BackwardFilterMap>;
 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) {
+OutEdgeIt(const SubBidirGraphWrapper<Graph,
+		ForwardFilterMap, BackwardFilterMap>& _G, Node v) {
 	backward=false;
 	_G.graph->first(out, v);
-	while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
+	while(_G.graph->valid(out) && !(*_G.forward_filter)[*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); }
+	  while(_G.graph->valid(in) && !(*_G.backward_filter)[*this]) { _G.graph->next(in); }
 	}
 }
 operator Edge() const {
 //	Edge e;
 //	e.forward=this->forward;
 	  return Edge(out, this->backward);
 }
 };
 class InEdgeIt {
-friend class BidirGraphWrapper<Graph>;
+friend class SubBidirGraphWrapper<Graph,
+					ForwardFilterMap, BackwardFilterMap>;
 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) {
+InEdgeIt(const SubBidirGraphWrapper<Graph,
+	       ForwardFilterMap, BackwardFilterMap>& _G, Node v) {
 	backward=false;
 	_G.graph->first(in, v);
-	while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
+	while(_G.graph->valid(in) && !(*_G.forward_filter)[*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); }
+	  while(_G.graph->valid(out) && !(*_G.backward_filter)[*this]) { _G.graph->next(out); }
 	}
 }
 operator Edge() const {
 //	Edge e;
 //	e.forward=this->forward;
 	  return Edge(in, this->backward);
 }
 };
 class EdgeIt {
-friend class BidirGraphWrapper<Graph>;
+friend class SubBidirGraphWrapper<Graph,
+					ForwardFilterMap, BackwardFilterMap>;
 protected:
 typename Graph::EdgeIt e;
 bool backward;
 public:
 EdgeIt() { }
 EdgeIt(const Invalid& i) : e(i), backward(true) { }
-EdgeIt(const BidirGraphWrapper<Graph>& _G) {
+EdgeIt(const SubBidirGraphWrapper<Graph,
+	     ForwardFilterMap, BackwardFilterMap>& _G) {
 	backward=false;
 	_G.graph->first(e);
-	while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
+	while (_G.graph->valid(e) && !(*_G.forward_filter)[*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);
+	  while (_G.graph->valid(e) && !(*_G.backward_filter)[*this]) _G.graph->next(e);
 	}
 }
 operator Edge() const {
 	return Edge(e, this->backward);
 }
 //    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)) {
+	while(this->graph->valid(e.out) && !(*forward_filter)[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)) {
+	  while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
 	    this->graph->next(e.in); }
 	}
 } else {
 	this->graph->next(e.in);
-	while(this->graph->valid(e.in) && !enabled(e)) {
+	while(this->graph->valid(e.in) && !(*backward_filter)[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)) {
+	while(this->graph->valid(e.in) && !(*forward_filter)[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)) {
+	  while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
 	    this->graph->next(e.out); }
 	}
 } else {
 	this->graph->next(e.out);
-	while(this->graph->valid(e.out) && !enabled(e)) {
+	while(this->graph->valid(e.out) && !(*backward_filter)[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)) {
+	while(this->graph->valid(e.e) && !(*forward_filter)[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)) {
+	  while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
 	    this->graph->next(e.e); }
 	}
 } else {
 	this->graph->next(e.e);
-	while(this->graph->valid(e.e) && !enabled(e)) {
+	while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
 	  this->graph->next(e.e); }
 }
 return e;
 }
 //       else
 // // 	flow->set(e.in, flow->get(e.in)-a);
 // 	flow->set(e, (*flow)[e]-a);
 //     }
-bool enabled(const Edge& e) const {
+//     bool enabled(const Edge& e) const {
-if (!e.backward)
+//       if (!e.backward)
-//	return (capacity->get(e.out)-flow->get(e.out));
+// //	return (capacity->get(e.out)-flow->get(e.out));
-	//return ((*capacity)[e]-(*flow)[e]);
+// 	//return ((*capacity)[e]-(*flow)[e]);
-	return true;
+// 	return true;
-else
+//       else
-//	return (flow->get(e.in));
+// //	return (flow->get(e.in));
-	//return ((*flow)[e]);
+// 	//return ((*flow)[e]);
-	return true;
+// 	return true;
-}
+//     }
 //     Number enabled(typename Graph::OutEdgeIt out) const {
 // //      return (capacity->get(out)-flow->get(out));
 //       return ((*capacity)[out]-(*flow)[out]);
 //     }
 class EdgeMap {
 typename Graph::template EdgeMap<T> forward_map, backward_map;
 public:
 typedef T ValueType;
 typedef Edge KeyType;
-EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
+EdgeMap(const SubBidirGraphWrapper<Graph,
-EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
+	      ForwardFilterMap, BackwardFilterMap>& _G) :
+	forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
+EdgeMap(const SubBidirGraphWrapper<Graph,
+	      ForwardFilterMap, BackwardFilterMap>& _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);
 // 	else
 // 	  return backward_map.get(e.in);
 //       }
 };
 };
+///\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.
+template<typename Graph>
+class BidirGraphWrapper :
+public SubBidirGraphWrapper<
+Graph,
+ConstMap<typename Graph::Edge, bool>,
+ConstMap<typename Graph::Edge, bool> > {
+public:
+typedef  SubBidirGraphWrapper<
+Graph,
+ConstMap<typename Graph::Edge, bool>,
+ConstMap<typename Graph::Edge, bool> > Parent;
+protected:
+ConstMap<typename Graph::Edge, bool> cm;
+//const CapacityMap* capacity;
+//FlowMap* flow;
+BidirGraphWrapper() : Parent(), cm(true) { }
+//     void setCapacityMap(const CapacityMap& _capacity) {
+//       capacity=&_capacity;
+//     }
+//     void setFlowMap(FlowMap& _flow) {
+//       flow=&_flow;
+//     }
+public:
+BidirGraphWrapper(Graph& _graph) : Parent() {
+Parent::setGraph(_graph);
+Parent::setForwardFilterMap(cm);
+Parent::setBackwardFilterMap(cm);
+}
+};
+//   ///\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.
+//   template<typename Graph>
+//   class BidirGraphWrapper : public GraphWrapper<Graph> {
+//   public:
+//     typedef GraphWrapper<Graph> Parent;
+//   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;
+//     //template<typename T> class NodeMap;
+//     template<typename T> class EdgeMap;
+//     typedef typename GraphWrapper<Graph>::Node Node;
+//     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
+//     class Edge : public Graph::Edge {
+//       friend class BidirGraphWrapper<Graph>;
+//       ///\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
+//       Edge(const typename Graph::Edge& _e, bool _backward=false) :
+// 	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)); }
+//     /// Gives back the opposite edge.
+//     Edge opposite(const Edge& e) const {
+//       Edge f=e;
+//       f.backward=!f.backward;
+//       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);
+//     }
+//     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:
+//       typedef T ValueType;
+//       typedef Edge KeyType;
+//       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*/];
+//       }
+//       void update() {
+// 	forward_map.update();
+// 	backward_map.update();
+//       }
+// //       T get(Edge e) const {
+// // 	if (e.out_or_in)
+// // 	  return forward_map.get(e.out);
+// // 	else
+// // 	  return backward_map.get(e.in);
+// //       }
+//     };
+//   };
 /// \brief A bidirected graph template.
 ///
 /// A bidirected graph template.
 /// Such a bidirected graph stores each pair of oppositely directed edges
 /// As the oppositely directed edges are logically different ones
 /// the maps are able to attach different values for them.
 /// \ingroup graphs
 template<typename Graph>
 class BidirGraph : public BidirGraphWrapper<Graph> {
+public:
 typedef UndirGraphWrapper<Graph> Parent;
 protected:
 Graph gr;
 public:
 BidirGraph() : BidirGraphWrapper<Graph>() {
 Parent::setGraph(gr);
 }
 };
+/// An experiment for ResGraphWrapper.
+template<typename Graph, typename Number,
+	   typename CapacityMap, typename FlowMap>
+class ForwardFilter {
+const Graph* graph;
+const CapacityMap* capacity;
+const FlowMap* flow;
+public:
+ForwardFilter(const Graph& _graph,
+		  const CapacityMap& _capacity, const FlowMap& _flow) :
+graph(&_graph), capacity(&_capacity), flow(&_flow) { }
+bool operator[](const typename Graph::Edge& e) const {
+return ((*flow)[e] < (*capacity)[e]);
+}
+};
+/// An experiment for ResGraphWrapper.
+template<typename Graph, typename Number,
+	   typename CapacityMap, typename FlowMap>
+class BackwardFilter {
+const Graph* graph;
+const CapacityMap* capacity;
+const FlowMap* flow;
+public:
+BackwardFilter(const Graph& _graph,
+		   const CapacityMap& _capacity, const FlowMap& _flow) :
+graph(&_graph), capacity(&_capacity), flow(&_flow) { }
+bool operator[](const typename Graph::Edge& e) const {
+return (0 < (*flow)[e]);
+}
+};
+/// An experiment for ResGraphWrapper.
+template<typename Graph, typename Number,
+	   typename CapacityMap, typename FlowMap>
+class ExpResGraphWrapper :
+public SubBidirGraphWrapper<
+Graph,
+ForwardFilter<Graph, Number, CapacityMap, FlowMap>,
+BackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
+public:
+typedef SubBidirGraphWrapper<
+Graph,
+ForwardFilter<Graph, Number, CapacityMap, FlowMap>,
+BackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
+protected:
+const CapacityMap* capacity;
+FlowMap* flow;
+ForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
+BackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
+public:
+ExpResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
+		       FlowMap& _flow) :
+Parent(), capacity(&_capacity), flow(&_flow),
+forward_filter(_graph, _capacity, _flow),
+backward_filter(_graph, _capacity, _flow) {
+Parent::setGraph(_graph);
+Parent::setForwardFilterMap(forward_filter);
+Parent::setBackwardFilterMap(backward_filter);
+}
+//    bool forward(const Parent::Edge& e) const { return Parent::forward(e); }
+//bool backward(const Edge& e) const { return e.backward; }
+void augment(const typename Parent::Edge& e, Number a) const {
+if (Parent::forward(e))
+// 	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);
+}
+Number resCap(const typename Parent::Edge& e) const {
+if (Parent::forward(e))
+//	return (capacity->get(e.out)-flow->get(e.out));
+	return ((*capacity)[e]-(*flow)[e]);
+else
+//	return (flow->get(e.in));
+	return ((*flow)[e]);
+}
+};
+//   /// An experiment for ResGraphWrapper.
+//   template<typename Graph, typename Number,
+// 	   typename CapacityMap, typename FlowMap>
+//   class ExpResGraphWrapper :
+//     public SubGraphWrapper< BidirGraphWrapper<Graph>,
+// 			    ConstMap<typename BidirGraphWrapper<Graph>::Node,
+// 				     bool>,
+// 			    EdgeFilter< BidirGraphWrapper<Graph>,
+// 					CapacityMap, FlowMap> > {
+//   public:
+//     typedef SubGraphWrapper< BidirGraphWrapper<Graph>,
+// 			     ConstMap<typename BidirGraphWrapper<Graph>::Node,
+// 				      bool>,
+// 			     EdgeFilter< BidirGraphWrapper<Graph>,
+// 					 CapacityMap, FlowMap> > Parent;
+//   protected:
+//     const CapacityMap* capacity;
+//     FlowMap* flow;
+//     BidirGraphWrapper<Graph> bidir_graph;
+//     ConstMap<typename BidirGraphWrapper<Graph>::Node, bool> node_filter;
+//     EdgeFilter< BidirGraphWrapper<Graph>, CapacityMap, FlowMap> edge_filter;
+//   public:
+//     ExpResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
+// 		       FlowMap& _flow) :
+//       Parent(), capacity(&_capacity), flow(&_flow),
+//       bidir_graph(_graph),
+//       node_filter(true),
+//       edge_filter(bidir_graph, *capacity, *flow) {
+//       Parent::setGraph(bidir_graph);
+//       Parent::setNodeFilterMap(node_filter);
+//       Parent::setEdgeFilterMap(edge_filter);
+//     }
+//     //    bool forward(const Parent::Edge& e) const { return Parent::forward(e); }
+//     //bool backward(const Edge& e) const { return e.backward; }
+//     void augment(const typename Parent::Edge& e, Number a) const {
+//       if (Parent::forward(e))
+// // 	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);
+//     }
+//     Number resCap(const typename Parent::Edge& e) const {
+//       if (Parent::forward(e))
+// //	return (capacity->get(e.out)-flow->get(e.out));
+// 	return ((*capacity)[e]-(*flow)[e]);
+//       else
+// //	return (flow->get(e.in));
+// 	return ((*flow)[e]);
+//     }
+//   };
 /// A wrapper for composing the residual graph for directed flow and circulation problems.
 /// A wrapper for composing the residual graph for directed flow and circulation problems.
 template<typename Graph, typename Number,
 	   typename CapacityMap, typename FlowMap>
 class ResGraphWrapper : public GraphWrapper<Graph> {
+public:
+typedef GraphWrapper<Graph> Parent;
 protected:
 const CapacityMap* capacity;
 FlowMap* flow;
 ResGraphWrapper() : GraphWrapper<Graph>(0),
 /// is called.
 ///
 ///\author Marton Makai
 template<typename Graph, typename FirstOutEdgesMap>
 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
+public:
+typedef GraphWrapper<Graph> Parent;
 protected:
 FirstOutEdgesMap* first_out_edges;
 public:
 ErasingFirstGraphWrapper(Graph& _graph,
 			     FirstOutEdgesMap& _first_out_edges) :

changeset 650	588ff2ca55bd
parent 626	0015642b0990
child 653	c3ad7c661a49