klao@445: // -*- c++ -*-
klao@445: #ifndef HUGO_GRAPH_WRAPPER_H
klao@445: #define HUGO_GRAPH_WRAPPER_H
klao@445: 
klao@445: #include <invalid.h>
klao@445: #include <iter_map.h>
klao@445: 
klao@445: namespace hugo {
klao@445: 
klao@445:   // Graph wrappers
klao@445: 
klao@445:   /// \addtogroup gwrappers
klao@445:   /// A main parts of HUGOlib are the different graph structures, 
klao@445:   /// generic graph algorithms, graph concepts which couple these, and 
klao@445:   /// graph wrappers. While the previous ones are more or less clear, the 
klao@445:   /// latter notion needs further explanation.
klao@445:   /// Graph wrappers are graph classes which serve for considering graph 
klao@445:   /// structures in different ways. A short example makes the notion much 
klao@445:   /// clearer. 
klao@445:   /// Suppose that we have an instance \c g of a directed graph
klao@445:   /// type say \c ListGraph and an algorithm 
klao@445:   /// \code template<typename Graph> int algorithm(const Graph&); \endcode 
klao@445:   /// is needed to run on the reversely oriented graph. 
klao@445:   /// It may be expensive (in time or in memory usage) to copy 
klao@445:   /// \c g with the reverse orientation. 
klao@445:   /// Thus, a wrapper class
klao@445:   /// \code template<typename Graph> class RevGraphWrapper; \endcode is used. 
klao@445:   /// The code looks as follows
klao@445:   /// \code
klao@445:   /// ListGraph g;
klao@445:   /// RevGraphWrapper<ListGraph> rgw(g);
klao@445:   /// int result=algorithm(rgw);
klao@445:   /// \endcode
klao@445:   /// After running the algorithm, the original graph \c g 
klao@445:   /// remains untouched. Thus the graph wrapper used above is to consider the 
klao@445:   /// original graph with reverse orientation. 
klao@445:   /// This techniques gives rise to an elegant code, and 
klao@445:   /// based on stable graph wrappers, complex algorithms can be 
klao@445:   /// implemented easily. 
klao@445:   /// In flow, circulation and bipartite matching problems, the residual 
klao@445:   /// graph is of particular importance. Combining a wrapper implementing 
klao@445:   /// this, shortest path algorithms and minimum mean cycle algorithms, 
klao@445:   /// a range of weighted and cardinality optimization algorithms can be 
klao@445:   /// obtained. For lack of space, for other examples, 
klao@445:   /// the interested user is referred to the detailed documentation of graph 
klao@445:   /// wrappers. 
klao@445:   /// The behavior of graph wrappers can be very different. Some of them keep 
klao@445:   /// capabilities of the original graph while in other cases this would be 
klao@445:   /// meaningless. This means that the concepts that they are a model of depend 
klao@445:   /// on the graph wrapper, and the wrapped graph(s). 
klao@445:   /// If an edge of \c rgw is deleted, this is carried out by 
klao@445:   /// deleting the corresponding edge of \c g. But for a residual 
klao@445:   /// graph, this operation has no sense. 
klao@445:   /// Let we stand one more example here to simplify your work. 
klao@445:   /// wrapper class
klao@445:   /// \code template<typename Graph> class RevGraphWrapper; \endcode 
klao@445:   /// has constructor 
klao@445:   /// <tt> RevGraphWrapper(Graph& _g)</tt>. 
klao@445:   /// This means that in a situation, 
klao@445:   /// when a <tt> const ListGraph& </tt> reference to a graph is given, 
klao@445:   /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
klao@445:   /// \code
klao@445:   /// int algorithm1(const ListGraph& g) {
klao@445:   ///   RevGraphWrapper<const ListGraph> rgw(g);
klao@445:   ///   return algorithm2(rgw);
klao@445:   /// }
klao@445:   /// \endcode
klao@445: 
klao@445:   /// \addtogroup gwrappers
klao@445:   /// @{
klao@445: 
klao@445:   ///Base type for the Graph Wrappers
klao@445: 
klao@445:   ///This is the base type for the Graph Wrappers.
klao@445:   ///\todo Some more docs...
klao@445: 
klao@445:   template<typename Graph>
klao@445:   class GraphWrapper {
klao@445:   protected:
klao@445:     Graph* graph;
klao@445:   
klao@445:   public:
klao@445:     typedef Graph BaseGraph;
klao@445:     typedef Graph ParentGraph;
klao@445: 
klao@445: //     GraphWrapper() : graph(0) { }
klao@445:     GraphWrapper(Graph& _graph) : graph(&_graph) { }
klao@445: //     void setGraph(Graph& _graph) { graph=&_graph; }
klao@445: //     Graph& getGraph() const { return *graph; }
klao@445:  
klao@445: //    typedef typename Graph::Node Node;
klao@445:     class Node : public Graph::Node {
klao@445:       friend class GraphWrapper<Graph>;
klao@445:     public:
klao@445:       Node() { }
klao@445:       Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
klao@445:       Node(const Invalid& i) : Graph::Node(i) { }
klao@445:     };
klao@445:     class NodeIt { 
klao@445:       friend class GraphWrapper<Graph>;
klao@445:       typename Graph::NodeIt n;
klao@445:      public:
klao@445:       NodeIt() { }
klao@445:       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
klao@445:       NodeIt(const Invalid& i) : n(i) { }
klao@445:       NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
klao@445:       operator Node() const { return Node(typename Graph::Node(n)); }
klao@445:     };
klao@445: //    typedef typename Graph::Edge Edge;
klao@445:     class Edge : public Graph::Edge {
klao@445:       friend class GraphWrapper<Graph>;
klao@445:     public:
klao@445:       Edge() { }
klao@445:       Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
klao@445:       Edge(const Invalid& i) : Graph::Edge(i) { }
klao@445:     };
klao@445:     class OutEdgeIt { 
klao@445:       friend class GraphWrapper<Graph>;
klao@445:       typename Graph::OutEdgeIt e;
klao@445:     public:
klao@445:       OutEdgeIt() { }
klao@445:       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
klao@445:       OutEdgeIt(const Invalid& i) : e(i) { }
klao@445:       OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 
klao@445: 	e(*(_G.graph), typename Graph::Node(_n)) { }
klao@445:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
klao@445:     };
klao@445:     class InEdgeIt { 
klao@445:       friend class GraphWrapper<Graph>;
klao@445:       typename Graph::InEdgeIt e;
klao@445:     public:
klao@445:       InEdgeIt() { }
klao@445:       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
klao@445:       InEdgeIt(const Invalid& i) : e(i) { }
klao@445:       InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 
klao@445: 	e(*(_G.graph), typename Graph::Node(_n)) { }
klao@445:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
klao@445:     };
klao@445:     //typedef typename Graph::SymEdgeIt SymEdgeIt;
klao@445:     class EdgeIt { 
klao@445:       friend class GraphWrapper<Graph>;
klao@445:       typename Graph::EdgeIt e;
klao@445:     public:
klao@445:       EdgeIt() { }
klao@445:       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
klao@445:       EdgeIt(const Invalid& i) : e(i) { }
klao@445:       EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
klao@445:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
klao@445:     };
klao@445:    
klao@445:     NodeIt& first(NodeIt& i) const { 
klao@445:       i=NodeIt(*this); return i;
klao@445:     }
klao@445:     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
klao@445:       i=OutEdgeIt(*this, p); return i;
klao@445:     }
klao@445:     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
klao@445:       i=InEdgeIt(*this, p); return i;
klao@445:     }
klao@445:     EdgeIt& first(EdgeIt& i) const { 
klao@445:       i=EdgeIt(*this); return i;
klao@445:     }
klao@445: 
klao@445:     NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
klao@445:     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
klao@445:     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
klao@445:     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }    
klao@445: 
klao@445:     Node tail(const Edge& e) const { 
klao@445:       return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
klao@445:     Node head(const Edge& e) const { 
klao@445:       return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
klao@445: 
klao@445:     bool valid(const Node& n) const { 
klao@445:       return graph->valid(static_cast<typename Graph::Node>(n)); }
klao@445:     bool valid(const Edge& e) const { 
klao@445:       return graph->valid(static_cast<typename Graph::Edge>(e)); }
klao@445: 
klao@445:     int nodeNum() const { return graph->nodeNum(); }
klao@445:     int edgeNum() const { return graph->edgeNum(); }
klao@445:   
klao@445:     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
klao@445:     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
klao@445:     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
klao@445:     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
klao@445:   
klao@445:     Node addNode() const { return Node(graph->addNode()); }
klao@445:     Edge addEdge(const Node& tail, const Node& head) const { 
klao@445:       return Edge(graph->addEdge(tail, head)); }
klao@445: 
klao@445:     void erase(const Node& i) const { graph->erase(i); }
klao@445:     void erase(const Edge& i) const { graph->erase(i); }
klao@445:   
klao@445:     void clear() const { graph->clear(); }
klao@445:     
klao@445:     template<typename T> class NodeMap : public Graph::template NodeMap<T> { 
klao@445:       typedef typename Graph::template NodeMap<T> Parent;
klao@445:     public:
klao@445:       NodeMap(const GraphWrapper<Graph>& _G) :  Parent(*(_G.graph)) { }
klao@445:       NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
klao@445:     };
klao@445: 
klao@445:     template<typename T> class EdgeMap : public Graph::template EdgeMap<T> { 
klao@445:       typedef typename Graph::template EdgeMap<T> Parent;
klao@445:     public:
klao@445:       EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
klao@445:       EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
klao@445:     };
klao@445:   };
klao@445: 
klao@445:   /// A graph wrapper which reverses the orientation of the edges.
klao@445: 
klao@445:   /// A graph wrapper which reverses the orientation of the edges.
klao@445:   template<typename Graph>
klao@445:   class RevGraphWrapper : public GraphWrapper<Graph> {
klao@445:   public:
klao@445: 
klao@445:     RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  
klao@445: 
klao@445:     typedef typename GraphWrapper<Graph>::Node Node;
klao@445:     typedef typename GraphWrapper<Graph>::Edge Edge;
klao@445:     //If Graph::OutEdgeIt is not defined
klao@445:     //and we do not want to use RevGraphWrapper::InEdgeIt,
klao@445:     //the typdef techinque does not work.
klao@445:     //Unfortunately all the typedefs are instantiated in templates.
klao@445:     //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
klao@445:     //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
klao@445: 
klao@445:     class OutEdgeIt { 
klao@445:       friend class GraphWrapper<Graph>;
klao@445:       friend class RevGraphWrapper<Graph>;
klao@445:       typename Graph::InEdgeIt e;
klao@445:     public:
klao@445:       OutEdgeIt() { }
klao@445:       OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
klao@445:       OutEdgeIt(const Invalid& i) : e(i) { }
klao@445:       OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : 
klao@445: 	e(*(_G.graph), typename Graph::Node(_n)) { }
klao@445:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
klao@445:     };
klao@445:     class InEdgeIt { 
klao@445:       friend class GraphWrapper<Graph>;
klao@445:       friend class RevGraphWrapper<Graph>;
klao@445:       typename Graph::OutEdgeIt e;
klao@445:     public:
klao@445:       InEdgeIt() { }
klao@445:       InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
klao@445:       InEdgeIt(const Invalid& i) : e(i) { }
klao@445:       InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : 
klao@445: 	e(*(_G.graph), typename Graph::Node(_n)) { }
klao@445:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
klao@445:     };
klao@445: 
klao@445:     using GraphWrapper<Graph>::first;
klao@445:     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
klao@445:       i=OutEdgeIt(*this, p); return i;
klao@445:     }
klao@445:     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
klao@445:       i=InEdgeIt(*this, p); return i;
klao@445:     }
klao@445: 
klao@445:     using GraphWrapper<Graph>::next;
klao@445:     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
klao@445:     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
klao@445: 
klao@445:     Node aNode(const OutEdgeIt& e) const { 
klao@445:       return Node(this->graph->aNode(e.e)); }
klao@445:     Node aNode(const InEdgeIt& e) const { 
klao@445:       return Node(this->graph->aNode(e.e)); }
klao@445:     Node bNode(const OutEdgeIt& e) const { 
klao@445:       return Node(this->graph->bNode(e.e)); }
klao@445:     Node bNode(const InEdgeIt& e) const { 
klao@445:       return Node(this->graph->bNode(e.e)); }
klao@445: 
klao@445:     Node tail(const Edge& e) const { 
klao@445:       return GraphWrapper<Graph>::head(e); }
klao@445:     Node head(const Edge& e) const { 
klao@445:       return GraphWrapper<Graph>::tail(e); }
klao@445: 
klao@445:   };
klao@445: 
klao@445:   /// Wrapper for hiding nodes and edges from a graph.
klao@445:   
klao@445:   /// This wrapper shows a graph with filtered node-set and 
klao@445:   /// edge-set. The quick brown fox iterator jumps over 
klao@445:   /// the lazy dog nodes or edges if the values for them are false 
klao@445:   /// in the bool maps. 
klao@445:   template<typename Graph, typename NodeFilterMap, 
klao@445: 	   typename EdgeFilterMap>
klao@445:   class SubGraphWrapper : public GraphWrapper<Graph> {
klao@445:   protected:
klao@445:     NodeFilterMap* node_filter_map;
klao@445:     EdgeFilterMap* edge_filter_map;
klao@445:   public:
klao@445: 
klao@445:     SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, 
klao@445: 		    EdgeFilterMap& _edge_filter_map) : 
klao@445:       GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map), 
klao@445:       edge_filter_map(&_edge_filter_map) { }  
klao@445: 
klao@445:     typedef typename GraphWrapper<Graph>::Node Node;
klao@445:     class NodeIt { 
klao@445:       friend class GraphWrapper<Graph>;
klao@445:       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
klao@445:       typename Graph::NodeIt n;
klao@445:      public:
klao@445:       NodeIt() { }
klao@445:       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
klao@445:       NodeIt(const Invalid& i) : n(i) { }
klao@445:       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
klao@445: 	n(*(_G.graph)) { 
klao@445: 	while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n]) 
klao@445: 	  _G.graph->next(n);
klao@445:       }
klao@445:       operator Node() const { return Node(typename Graph::Node(n)); }
klao@445:     };
klao@445:     typedef typename GraphWrapper<Graph>::Edge Edge;
klao@445:     class OutEdgeIt { 
klao@445:       friend class GraphWrapper<Graph>;
klao@445:       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
klao@445:       typename Graph::OutEdgeIt e;
klao@445:     public:
klao@445:       OutEdgeIt() { }
klao@445:       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
klao@445:       OutEdgeIt(const Invalid& i) : e(i) { }
klao@445:       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 
klao@445: 		const Node& _n) : 
klao@445: 	e(*(_G.graph), typename Graph::Node(_n)) { 
klao@445:       	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
klao@445: 	  _G.graph->next(e);
klao@445:       }
klao@445:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
klao@445:     };
klao@445:     class InEdgeIt { 
klao@445:       friend class GraphWrapper<Graph>;
klao@445:       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
klao@445:       typename Graph::InEdgeIt e;
klao@445:     public:
klao@445:       InEdgeIt() { }
klao@445:       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
klao@445:       InEdgeIt(const Invalid& i) : e(i) { }
klao@445:       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 
klao@445: 	       const Node& _n) : 
klao@445: 	e(*(_G.graph), typename Graph::Node(_n)) { 
klao@445:       	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
klao@445: 	  _G.graph->next(e);
klao@445:       }
klao@445:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
klao@445:     };
klao@445:     //typedef typename Graph::SymEdgeIt SymEdgeIt;
klao@445:     class EdgeIt { 
klao@445:       friend class GraphWrapper<Graph>;
klao@445:       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
klao@445:       typename Graph::EdgeIt e;
klao@445:     public:
klao@445:       EdgeIt() { }
klao@445:       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
klao@445:       EdgeIt(const Invalid& i) : e(i) { }
klao@445:       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 
klao@445: 	e(*(_G.graph)) { 
klao@445:       	while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 
klao@445: 	  _G.graph->next(e);
klao@445:       }
klao@445:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
klao@445:     };
klao@445: 
klao@445:     NodeIt& first(NodeIt& i) const { 
klao@445:       i=NodeIt(*this); return i;
klao@445:     }
klao@445:     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
klao@445:       i=OutEdgeIt(*this, p); return i;
klao@445:     }
klao@445:     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
klao@445:       i=InEdgeIt(*this, p); return i;
klao@445:     }
klao@445:     EdgeIt& first(EdgeIt& i) const { 
klao@445:       i=EdgeIt(*this); return i;
klao@445:     }
klao@445:     
klao@445:     NodeIt& next(NodeIt& i) const {
klao@445:       this->graph->next(i.n); 
klao@445:       while (this->graph->valid(i) && !(*node_filter_map)[i.n]) { 
klao@445: 	this->graph->next(i.n); }
klao@445:       return i;
klao@445:     }
klao@445:     OutEdgeIt& next(OutEdgeIt& i) const {
klao@445:       this->graph->next(i.e); 
klao@445:       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
klao@445: 	this->graph->next(i.e); }
klao@445:       return i;
klao@445:     }
klao@445:     InEdgeIt& next(InEdgeIt& i) const {
klao@445:       this->graph->next(i.e); 
klao@445:       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
klao@445: 	this->graph->next(i.e); }
klao@445:       return i;
klao@445:     }
klao@445:     EdgeIt& next(EdgeIt& i) const {
klao@445:       this->graph->next(i.e); 
klao@445:       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 
klao@445: 	this->graph->next(i.e); }
klao@445:       return i;
klao@445:     }
klao@445: 
klao@445:     Node aNode(const OutEdgeIt& e) const { 
klao@445:       return Node(this->graph->aNode(e.e)); }
klao@445:     Node aNode(const InEdgeIt& e) const { 
klao@445:       return Node(this->graph->aNode(e.e)); }
klao@445:     Node bNode(const OutEdgeIt& e) const { 
klao@445:       return Node(this->graph->bNode(e.e)); }
klao@445:     Node bNode(const InEdgeIt& e) const { 
klao@445:       return Node(this->graph->bNode(e.e)); }
klao@445: 
klao@445:     ///\todo
klao@445:     ///Some doki, please.
klao@445:     void hide(const Node& n) const { node_filter_map->set(n, false); }
klao@445:     ///\todo
klao@445:     ///Some doki, please.
klao@445:     void hide(const Edge& e) const { edge_filter_map->set(e, false); }
klao@445: 
klao@445:     ///\todo
klao@445:     ///Some doki, please.
klao@445:     void unHide(const Node& n) const { node_filter_map->set(n, true); }
klao@445:     ///\todo
klao@445:     ///Some doki, please.
klao@445:     void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
klao@445: 
klao@445:     ///\todo
klao@445:     ///Some doki, please.
klao@445:     bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
klao@445:     ///\todo
klao@445:     ///Some doki, please.
klao@445:     bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
klao@445:   };
klao@445: 
klao@445:   /// A wrapper for forgetting the orientation of a graph.
klao@445: 
klao@445:   /// A wrapper for getting an undirected graph by forgetting
klao@445:   /// the orientation of a directed one.
klao@445:   template<typename Graph>
klao@445:   class UndirGraphWrapper : public GraphWrapper<Graph> {
klao@445:   public:
klao@445:     typedef typename GraphWrapper<Graph>::Node Node;
klao@445:     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
klao@445:     typedef typename GraphWrapper<Graph>::Edge Edge;
klao@445:     typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
klao@445: 
klao@445:     UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  
klao@445: 
klao@445:     class OutEdgeIt {
klao@445:       friend class UndirGraphWrapper<Graph>;
klao@445:       bool out_or_in; //true iff out
klao@445:       typename Graph::OutEdgeIt out;
klao@445:       typename Graph::InEdgeIt in;
klao@445:     public:
klao@445:       OutEdgeIt() { }
klao@445:       OutEdgeIt(const Invalid& i) : Edge(i) { }
klao@445:       OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
klao@445: 	out_or_in=true; _G.graph->first(out, _n);
klao@445: 	if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);	}
klao@445:       } 
klao@445:       operator Edge() const { 
klao@445: 	if (out_or_in) return Edge(out); else return Edge(in); 
klao@445:       }
klao@445:     };
klao@445: 
klao@445: //FIXME InEdgeIt
klao@445:     typedef OutEdgeIt InEdgeIt; 
klao@445: 
klao@445:     using GraphWrapper<Graph>::first;
klao@445: //     NodeIt& first(NodeIt& i) const { 
klao@445: //       i=NodeIt(*this); return i;
klao@445: //     }
klao@445:     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
klao@445:       i=OutEdgeIt(*this, p); return i;
klao@445:     }
klao@445: //FIXME
klao@445: //     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
klao@445: //       i=InEdgeIt(*this, p); return i;
klao@445: //     }
klao@445: //     EdgeIt& first(EdgeIt& i) const { 
klao@445: //       i=EdgeIt(*this); return i;
klao@445: //     }
klao@445: 
klao@445:     using GraphWrapper<Graph>::next;
klao@445: //     NodeIt& next(NodeIt& n) const {
klao@445: //       GraphWrapper<Graph>::next(n);
klao@445: //       return n;
klao@445: //     }
klao@445:     OutEdgeIt& next(OutEdgeIt& e) const {
klao@445:       if (e.out_or_in) {
klao@445: 	typename Graph::Node n=this->graph->tail(e.out);
klao@445: 	this->graph->next(e.out);
klao@445: 	if (!this->graph->valid(e.out)) { 
klao@445: 	  e.out_or_in=false; this->graph->first(e.in, n); }
klao@445:       } else {
klao@445: 	this->graph->next(e.in);
klao@445:       }
klao@445:       return e;
klao@445:     }
klao@445:     //FIXME InEdgeIt
klao@445: //     EdgeIt& next(EdgeIt& e) const {
klao@445: //       GraphWrapper<Graph>::next(n);
klao@445: // //      graph->next(e.e);
klao@445: //       return e;
klao@445: //     }
klao@445: 
klao@445:     Node aNode(const OutEdgeIt& e) const { 
klao@445:       if (e.out_or_in) return this->graph->tail(e); else 
klao@445: 	return this->graph->head(e); }
klao@445:     Node bNode(const OutEdgeIt& e) const { 
klao@445:       if (e.out_or_in) return this->graph->head(e); else 
klao@445: 	return this->graph->tail(e); }
klao@445:   };
klao@445:   
klao@445:   /// A wrapper for composing the residual graph for directed flow and circulation problems.
klao@445: 
klao@445:   /// A wrapper for composing the residual graph for directed flow and circulation problems.
klao@445:   template<typename Graph, typename Number, 
klao@445: 	   typename CapacityMap, typename FlowMap>
klao@445:   class ResGraphWrapper : public GraphWrapper<Graph> {
klao@445:   protected:
klao@445:     const CapacityMap* capacity;
klao@445:     FlowMap* flow;
klao@445:   public:
klao@445: 
klao@445:     ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
klao@445: 		    FlowMap& _flow) : 
klao@445:       GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
klao@445: 
klao@445:     class Edge; 
klao@445:     class OutEdgeIt; 
klao@445:     friend class Edge; 
klao@445:     friend class OutEdgeIt; 
klao@445: 
klao@445:     typedef typename GraphWrapper<Graph>::Node Node;
klao@445:     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
klao@445:     class Edge : public Graph::Edge {
klao@445:       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
klao@445:     protected:
klao@445:       bool forward; //true, iff forward
klao@445: //      typename Graph::Edge e;
klao@445:     public:
klao@445:       Edge() { }
klao@445:       Edge(const typename Graph::Edge& _e, bool _forward) : 
klao@445: 	Graph::Edge(_e), forward(_forward) { }
klao@445:       Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
klao@445: //the unique invalid iterator
klao@445:       friend bool operator==(const Edge& u, const Edge& v) { 
klao@445: 	return (v.forward==u.forward && 
klao@445: 		static_cast<typename Graph::Edge>(u)==
klao@445: 		static_cast<typename Graph::Edge>(v));
klao@445:       } 
klao@445:       friend bool operator!=(const Edge& u, const Edge& v) { 
klao@445: 	return (v.forward!=u.forward || 
klao@445: 		static_cast<typename Graph::Edge>(u)!=
klao@445: 		static_cast<typename Graph::Edge>(v));
klao@445:       } 
klao@445:     };
klao@445: 
klao@445:     class OutEdgeIt {
klao@445:       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
klao@445:     protected:
klao@445:       typename Graph::OutEdgeIt out;
klao@445:       typename Graph::InEdgeIt in;
klao@445:       bool forward;
klao@445:     public:
klao@445:       OutEdgeIt() { }
klao@445:       //FIXME
klao@445: //      OutEdgeIt(const Edge& e) : Edge(e) { }
klao@445:       OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
klao@445: //the unique invalid iterator
klao@445:       OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { 
klao@445: 	forward=true;
klao@445: 	resG.graph->first(out, v);
klao@445: 	while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
klao@445: 	if (!resG.graph->valid(out)) {
klao@445: 	  forward=false;
klao@445: 	  resG.graph->first(in, v);
klao@445: 	  while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
klao@445: 	}
klao@445:       }
klao@445:       operator Edge() const { 
klao@445: //	Edge e;
klao@445: //	e.forward=this->forward;
klao@445: //	if (this->forward) e=out; else e=in;
klao@445: //	return e;
klao@445: 	if (this->forward) 
klao@445: 	  return Edge(out, this->forward); 
klao@445: 	else 
klao@445: 	  return Edge(in, this->forward);
klao@445:       }
klao@445:     };
klao@445: 
klao@445:     class InEdgeIt {
klao@445:       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
klao@445:     protected:
klao@445:       typename Graph::OutEdgeIt out;
klao@445:       typename Graph::InEdgeIt in;
klao@445:       bool forward;
klao@445:     public:
klao@445:       InEdgeIt() { }
klao@445:       //FIXME
klao@445: //      OutEdgeIt(const Edge& e) : Edge(e) { }
klao@445:       InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
klao@445: //the unique invalid iterator
klao@445:       InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { 
klao@445: 	forward=true;
klao@445: 	resG.graph->first(in, v);
klao@445: 	while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
klao@445: 	if (!resG.graph->valid(in)) {
klao@445: 	  forward=false;
klao@445: 	  resG.graph->first(out, v);
klao@445: 	  while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
klao@445: 	}
klao@445:       }
klao@445:       operator Edge() const { 
klao@445: //	Edge e;
klao@445: //	e.forward=this->forward;
klao@445: //	if (this->forward) e=out; else e=in;
klao@445: //	return e;
klao@445: 	if (this->forward) 
klao@445: 	  return Edge(in, this->forward); 
klao@445: 	else 
klao@445: 	  return Edge(out, this->forward);
klao@445:       }
klao@445:     };
klao@445: 
klao@445:     class EdgeIt {
klao@445:       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
klao@445:     protected:
klao@445:       typename Graph::EdgeIt e;
klao@445:       bool forward;
klao@445:     public:
klao@445:       EdgeIt() { }
klao@445:       EdgeIt(const Invalid& i) : e(i), forward(false) { }
klao@445:       EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) { 
klao@445: 	forward=true;
klao@445: 	resG.graph->first(e);
klao@445: 	while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
klao@445: 	if (!resG.graph->valid(e)) {
klao@445: 	  forward=false;
klao@445: 	  resG.graph->first(e);
klao@445: 	  while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
klao@445: 	}
klao@445:       }
klao@445:       operator Edge() const { 
klao@445: 	return Edge(e, this->forward);
klao@445:       }
klao@445:     };
klao@445: 
klao@445:     using GraphWrapper<Graph>::first;
klao@445: //     NodeIt& first(NodeIt& i) const { 
klao@445: //       i=NodeIt(*this); return i;
klao@445: //     }
klao@445:     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
klao@445:       i=OutEdgeIt(*this, p); return i;
klao@445:     }
klao@445: //    FIXME not tested
klao@445:     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
klao@445:       i=InEdgeIt(*this, p); return i;
klao@445:     }
klao@445:     EdgeIt& first(EdgeIt& i) const { 
klao@445:       i=EdgeIt(*this); return i;
klao@445:     }
klao@445:   
klao@445:     using GraphWrapper<Graph>::next;
klao@445: //    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
klao@445:     OutEdgeIt& next(OutEdgeIt& e) const { 
klao@445:       if (e.forward) {
klao@445: 	Node v=this->graph->aNode(e.out);
klao@445: 	this->graph->next(e.out);
klao@445: 	while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
klao@445: 	  this->graph->next(e.out); }
klao@445: 	if (!this->graph->valid(e.out)) {
klao@445: 	  e.forward=false;
klao@445: 	  this->graph->first(e.in, v); 
klao@445: 	  while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
klao@445: 	    this->graph->next(e.in); }
klao@445: 	}
klao@445:       } else {
klao@445: 	this->graph->next(e.in);
klao@445: 	while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
klao@445: 	  this->graph->next(e.in); } 
klao@445:       }
klao@445:       return e;
klao@445:     }
klao@445: //     FIXME Not tested
klao@445:     InEdgeIt& next(InEdgeIt& e) const { 
klao@445:       if (e.forward) {
klao@445: 	Node v=this->graph->aNode(e.in);
klao@445: 	this->graph->next(e.in);
klao@445: 	while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 
klao@445: 	  this->graph->next(e.in); }
klao@445: 	if (!this->graph->valid(e.in)) {
klao@445: 	  e.forward=false;
klao@445: 	  this->graph->first(e.out, v); 
klao@445: 	  while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
klao@445: 	    this->graph->next(e.out); }
klao@445: 	}
klao@445:       } else {
klao@445: 	this->graph->next(e.out);
klao@445: 	while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 
klao@445: 	  this->graph->next(e.out); } 
klao@445:       }
klao@445:       return e;
klao@445:     }
klao@445:     EdgeIt& next(EdgeIt& e) const {
klao@445:       if (e.forward) {
klao@445: 	this->graph->next(e.e);
klao@445: 	while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
klao@445: 	  this->graph->next(e.e); }
klao@445: 	if (!this->graph->valid(e.e)) {
klao@445: 	  e.forward=false;
klao@445: 	  this->graph->first(e.e); 
klao@445: 	  while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
klao@445: 	    this->graph->next(e.e); }
klao@445: 	}
klao@445:       } else {
klao@445: 	this->graph->next(e.e);
klao@445: 	while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 
klao@445: 	  this->graph->next(e.e); } 
klao@445:       }
klao@445:       return e;
klao@445:     }
klao@445: 
klao@445:     Node tail(Edge e) const { 
klao@445:       return ((e.forward) ? this->graph->tail(e) : this->graph->head(e)); }
klao@445:     Node head(Edge e) const { 
klao@445:       return ((e.forward) ? this->graph->head(e) : this->graph->tail(e)); }
klao@445: 
klao@445:     Node aNode(OutEdgeIt e) const { 
klao@445:       return ((e.forward) ? this->graph->aNode(e.out) : 
klao@445: 	      this->graph->aNode(e.in)); }
klao@445:     Node bNode(OutEdgeIt e) const { 
klao@445:       return ((e.forward) ? this->graph->bNode(e.out) : 
klao@445: 	      this->graph->bNode(e.in)); }
klao@445: 
klao@445:     Node aNode(InEdgeIt e) const { 
klao@445:       return ((e.forward) ? this->graph->aNode(e.in) : 
klao@445: 	      this->graph->aNode(e.out)); }
klao@445:     Node bNode(InEdgeIt e) const { 
klao@445:       return ((e.forward) ? this->graph->bNode(e.in) : 
klao@445: 	      this->graph->bNode(e.out)); }
klao@445: 
klao@445: //    int nodeNum() const { return graph->nodeNum(); }
klao@445:     //FIXME
klao@445:     void edgeNum() const { }
klao@445:     //int edgeNum() const { return graph->edgeNum(); }
klao@445: 
klao@445: 
klao@445: //    int id(Node v) const { return graph->id(v); }
klao@445: 
klao@445:     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
klao@445:     bool valid(Edge e) const { 
klao@445:       return this->graph->valid(e);
klao@445: 	//return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
klao@445:     }
klao@445: 
klao@445:     void augment(const Edge& e, Number a) const {
klao@445:       if (e.forward)  
klao@445: // 	flow->set(e.out, flow->get(e.out)+a);
klao@445: 	flow->set(e, (*flow)[e]+a);
klao@445:       else  
klao@445: // 	flow->set(e.in, flow->get(e.in)-a);
klao@445: 	flow->set(e, (*flow)[e]-a);
klao@445:     }
klao@445: 
klao@445:     Number resCap(const Edge& e) const { 
klao@445:       if (e.forward) 
klao@445: //	return (capacity->get(e.out)-flow->get(e.out)); 
klao@445: 	return ((*capacity)[e]-(*flow)[e]); 
klao@445:       else 
klao@445: //	return (flow->get(e.in)); 
klao@445: 	return ((*flow)[e]); 
klao@445:     }
klao@445: 
klao@445: //     Number resCap(typename Graph::OutEdgeIt out) const { 
klao@445: // //      return (capacity->get(out)-flow->get(out)); 
klao@445: //       return ((*capacity)[out]-(*flow)[out]); 
klao@445: //     }
klao@445:     
klao@445: //     Number resCap(typename Graph::InEdgeIt in) const { 
klao@445: // //      return (flow->get(in)); 
klao@445: //       return ((*flow)[in]); 
klao@445: //     }
klao@445: 
klao@445:     template <typename T>
klao@445:     class EdgeMap {
klao@445:       typename Graph::template EdgeMap<T> forward_map, backward_map; 
klao@445:     public:
klao@445:       EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
klao@445:       EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
klao@445:       void set(Edge e, T a) { 
klao@445: 	if (e.forward) 
klao@445: 	  forward_map.set(e.out, a); 
klao@445: 	else 
klao@445: 	  backward_map.set(e.in, a); 
klao@445:       }
klao@445:       T operator[](Edge e) const { 
klao@445: 	if (e.forward) 
klao@445: 	  return forward_map[e.out]; 
klao@445: 	else 
klao@445: 	  return backward_map[e.in]; 
klao@445:       }
klao@445: //       T get(Edge e) const { 
klao@445: // 	if (e.out_or_in) 
klao@445: // 	  return forward_map.get(e.out); 
klao@445: // 	else 
klao@445: // 	  return backward_map.get(e.in); 
klao@445: //       }
klao@445:     };
klao@445:   };
klao@445: 
klao@445:   /// ErasingFirstGraphWrapper for blocking flows.
klao@445: 
klao@445:   /// ErasingFirstGraphWrapper for blocking flows.
klao@445:   template<typename Graph, typename FirstOutEdgesMap>
klao@445:   class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
klao@445:   protected:
klao@445:     FirstOutEdgesMap* first_out_edges;
klao@445:   public:
klao@445:     ErasingFirstGraphWrapper(Graph& _graph, 
klao@445: 			     FirstOutEdgesMap& _first_out_edges) : 
klao@445:       GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }  
klao@445: 
klao@445:     typedef typename GraphWrapper<Graph>::Node Node;
klao@445: //     class NodeIt { 
klao@445: //       friend class GraphWrapper<Graph>;
klao@445: //       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
klao@445: //       typename Graph::NodeIt n;
klao@445: //      public:
klao@445: //       NodeIt() { }
klao@445: //       NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
klao@445: //       NodeIt(const Invalid& i) : n(i) { }
klao@445: //       NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
klao@445: // 	n(*(_G.graph)) { }
klao@445: //       operator Node() const { return Node(typename Graph::Node(n)); }
klao@445: //     };
klao@445:     typedef typename GraphWrapper<Graph>::Edge Edge;
klao@445:     class OutEdgeIt { 
klao@445:       friend class GraphWrapper<Graph>;
klao@445:       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
klao@445: //      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
klao@445:       typename Graph::OutEdgeIt e;
klao@445:     public:
klao@445:       OutEdgeIt() { }
klao@445:       OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
klao@445:       OutEdgeIt(const Invalid& i) : e(i) { }
klao@445:       OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
klao@445: 		const Node& _n) : 
klao@445: 	e((*_G.first_out_edges)[_n]) { }
klao@445:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
klao@445:     };
klao@445:     class InEdgeIt { 
klao@445:       friend class GraphWrapper<Graph>;
klao@445:       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
klao@445: //      typedef typename Graph::InEdgeIt GraphInEdgeIt;
klao@445:       typename Graph::InEdgeIt e;
klao@445:     public:
klao@445:       InEdgeIt() { }
klao@445:       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
klao@445:       InEdgeIt(const Invalid& i) : e(i) { }
klao@445:       InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 
klao@445: 	       const Node& _n) : 
klao@445: 	e(*(_G.graph), typename Graph::Node(_n)) { }
klao@445:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
klao@445:     };
klao@445:     //typedef typename Graph::SymEdgeIt SymEdgeIt;
klao@445:     class EdgeIt { 
klao@445:       friend class GraphWrapper<Graph>;
klao@445:       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
klao@445: //      typedef typename Graph::EdgeIt GraphEdgeIt;
klao@445:       typename Graph::EdgeIt e;
klao@445:     public:
klao@445:       EdgeIt() { }
klao@445:       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
klao@445:       EdgeIt(const Invalid& i) : e(i) { }
klao@445:       EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 
klao@445: 	e(*(_G.graph)) { }
klao@445:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
klao@445:     };
klao@445: 
klao@445:     using GraphWrapper<Graph>::first;
klao@445: //     NodeIt& first(NodeIt& i) const { 
klao@445: //       i=NodeIt(*this); return i;
klao@445: //     }
klao@445:     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
klao@445:       i=OutEdgeIt(*this, p); return i;
klao@445:     }
klao@445:     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
klao@445:       i=InEdgeIt(*this, p); return i;
klao@445:     }
klao@445:     EdgeIt& first(EdgeIt& i) const { 
klao@445:       i=EdgeIt(*this); return i;
klao@445:     }
klao@445: 
klao@445:     using GraphWrapper<Graph>::next;
klao@445: //    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
klao@445:     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
klao@445:     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
klao@445:     EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }    
klao@445:     
klao@445:     Node aNode(const OutEdgeIt& e) const { 
klao@445:       return Node(this->graph->aNode(e.e)); }
klao@445:     Node aNode(const InEdgeIt& e) const { 
klao@445:       return Node(this->graph->aNode(e.e)); }
klao@445:     Node bNode(const OutEdgeIt& e) const { 
klao@445:       return Node(this->graph->bNode(e.e)); }
klao@445:     Node bNode(const InEdgeIt& e) const { 
klao@445:       return Node(this->graph->bNode(e.e)); }
klao@445: 
klao@445:     void erase(const OutEdgeIt& e) const {
klao@445:       OutEdgeIt f=e;
klao@445:       this->next(f);
klao@445:       first_out_edges->set(this->tail(e), f.e);
klao@445:     }
klao@445:   };
klao@445: 
klao@445:   /// A wrapper for composing a bipartite graph.
klao@445:   /// \c _graph have to be a reference to a graph of type \c Graph 
klao@445:   /// and \c _s_false_t_true_map is an \c IterableBoolMap 
klao@445:   /// reference containing the elements for the 
klao@445:   /// color classes S and T. \c _graph is to be referred to an undirected 
klao@445:   /// graph or a directed graph with edges oriented from S to T.
klao@445:   template<typename Graph> 
klao@445:   class BipartiteGraphWrapper : public GraphWrapper<Graph> {
klao@445:     typedef IterableBoolMap< typename Graph::template NodeMap<int> > 
klao@445:     SFalseTTrueMap;
klao@445:     SFalseTTrueMap* s_false_t_true_map;
klao@445: 
klao@445:   public:
klao@445:     //marci
klao@445:     //FIXME vhogy igy kellene, csak az en forditom nem eszi meg
klao@445:     //static const bool S_CLASS=false;
klao@445:     //static const bool T_CLASS=true;
klao@445:     
klao@445:     bool S_CLASS;
klao@445:     bool T_CLASS;
klao@445: 
klao@445:     BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map) 
klao@445:       : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map), 
klao@445:       S_CLASS(false), T_CLASS(true) { }
klao@445:     typedef typename GraphWrapper<Graph>::Node Node;
klao@445:     //using GraphWrapper<Graph>::NodeIt;
klao@445:     typedef typename GraphWrapper<Graph>::Edge Edge;
klao@445:     //using GraphWrapper<Graph>::EdgeIt;
klao@445:     class ClassNodeIt;
klao@445:     friend class ClassNodeIt;
klao@445:     class OutEdgeIt;
klao@445:     friend class OutEdgeIt;
klao@445:     class InEdgeIt;
klao@445:     friend class InEdgeIt;
klao@445:     class ClassNodeIt {
klao@445:       friend class BipartiteGraphWrapper<Graph>;
klao@445:     protected:
klao@445:       Node n;
klao@445:     public:
klao@445:       ClassNodeIt() { }
klao@445:       ClassNodeIt(const Invalid& i) : n(i) { }
klao@445:       ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) { 
klao@445: 	_G.s_false_t_true_map->first(n, _class); 
klao@445:       }
klao@445:       //FIXME needed in new concept, important here
klao@445:       ClassNodeIt(const Node& _n) : n(_n) { }
klao@445:       operator Node() const { return n; }
klao@445:     };
klao@445: //     class SNodeIt {
klao@445: //       Node n;
klao@445: //     public:
klao@445: //       SNodeIt() { }
klao@445: //       SNodeIt(const Invalid& i) : n(i) { }
klao@445: //       SNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 
klao@445: // 	_G.s_false_t_true_map->first(n, false); 
klao@445: //       }
klao@445: //       operator Node() const { return n; }
klao@445: //     };
klao@445: //     class TNodeIt {
klao@445: //       Node n;
klao@445: //     public:
klao@445: //       TNodeIt() { }
klao@445: //       TNodeIt(const Invalid& i) : n(i) { }
klao@445: //       TNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 
klao@445: // 	_G.s_false_t_true_map->first(n, true); 
klao@445: //       }
klao@445: //       operator Node() const { return n; }
klao@445: //     };
klao@445:     class OutEdgeIt { 
klao@445:       friend class BipartiteGraphWrapper<Graph>;
klao@445:     protected:
klao@445:       typename Graph::OutEdgeIt e;
klao@445:     public:
klao@445:       OutEdgeIt() { }
klao@445:       OutEdgeIt(const Invalid& i) : e(i) { }
klao@445:       OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
klao@445: 	if (!(*(_G.s_false_t_true_map))[_n]) 
klao@445: 	  e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
klao@445: 	else 
klao@445: 	  e=INVALID;
klao@445:       }
klao@445:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
klao@445:     };
klao@445:     class InEdgeIt { 
klao@445:       friend class BipartiteGraphWrapper<Graph>;
klao@445:     protected:
klao@445:       typename Graph::InEdgeIt e;
klao@445:     public:
klao@445:       InEdgeIt() { }
klao@445:       InEdgeIt(const Invalid& i) : e(i) { }
klao@445:       InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
klao@445: 	if ((*(_G.s_false_t_true_map))[_n]) 
klao@445: 	  e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));
klao@445: 	else 
klao@445: 	  e=INVALID;
klao@445:       }
klao@445:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
klao@445:     };
klao@445: 
klao@445:     using GraphWrapper<Graph>::first;
klao@445:     ClassNodeIt& first(ClassNodeIt& n, bool _class) const { 
klao@445:       n=ClassNodeIt(*this, _class) ; return n; }
klao@445: //    SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
klao@445: //    TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
klao@445:     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
klao@445:       i=OutEdgeIt(*this, p); return i;
klao@445:     }
klao@445:     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
klao@445:       i=InEdgeIt(*this, p); return i;
klao@445:     }
klao@445: 
klao@445:     using GraphWrapper<Graph>::next;
klao@445:     ClassNodeIt& next(ClassNodeIt& n) const { 
klao@445:       this->s_false_t_true_map->next(n.n); return n; 
klao@445:     }
klao@445: //     SNodeIt& next(SNodeIt& n) const { 
klao@445: //       this->s_false_t_true_map->next(n); return n; 
klao@445: //     }
klao@445: //     TNodeIt& next(TNodeIt& n) const { 
klao@445: //       this->s_false_t_true_map->next(n); return n; 
klao@445: //     }
klao@445:     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
klao@445:     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
klao@445: 
klao@445:     Node tail(const Edge& e) { 
klao@445:       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 
klao@445: 	return Node(this->graph->tail(e));
klao@445:       else
klao@445: 	return Node(this->graph->head(e));	
klao@445:     }
klao@445:     Node head(const Edge& e) { 
klao@445:       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 
klao@445: 	return Node(this->graph->head(e));
klao@445:       else
klao@445: 	return Node(this->graph->tail(e));	
klao@445:     }
klao@445: 
klao@445:     Node aNode(const OutEdgeIt& e) const { 
klao@445:       return Node(this->graph->aNode(e.e)); 
klao@445:     }
klao@445:     Node aNode(const InEdgeIt& e) const { 
klao@445:       return Node(this->graph->aNode(e.e)); 
klao@445:     }
klao@445:     Node bNode(const OutEdgeIt& e) const { 
klao@445:       return Node(this->graph->bNode(e.e)); 
klao@445:     }
klao@445:     Node bNode(const InEdgeIt& e) const { 
klao@445:       return Node(this->graph->bNode(e.e)); 
klao@445:     }
klao@445: 
klao@445:     bool inSClass(const Node& n) const {
klao@445:       return !(*(this->s_false_t_true_map))[n];
klao@445:     }
klao@445:     bool inTClass(const Node& n) const {
klao@445:       return (*(this->s_false_t_true_map))[n];
klao@445:     }
klao@445:   };
klao@445: 
klao@445: 
klao@445: 
klao@445: 
klao@445:   /********************   S-T Graph Wrapper    ********************/
klao@445: 
klao@445: 
klao@445: 
klao@445: 
klao@445: 
klao@445:   template<typename Graph> class stGraphWrapper;
klao@445: 
klao@445:   template<typename Graph>
klao@445:   inline
klao@445:   std::ostream& 
klao@445:   operator<<(std::ostream& os,
klao@445: 	     typename stGraphWrapper<Graph>::Node const& i) { 
klao@445:     os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")";
klao@445:     return os; 
klao@445:   }
klao@445: 
klao@445:   template<typename Graph>
klao@445:   inline
klao@445:   std::ostream& 
klao@445:   operator<<(std::ostream& os,
klao@445: 	     typename stGraphWrapper<Graph>::Edge const& i) { 
klao@445:     os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec
klao@445:        << " node: " << i.n << ")"; 
klao@445:     return os; 
klao@445:   }
klao@445: 
klao@445: 
klao@445:   /// experimentral, do not try it.
klao@445:   /// It eats a bipartite graph, oriented from S to T.
klao@445:   /// Such one can be made e.g. by the above wrapper.
klao@445:   template<typename Graph>
klao@445:   class stGraphWrapper : public GraphWrapper<Graph> {
klao@445:   public:
klao@445:     class Node; 
klao@445:     friend class Node;
klao@445: //GN, int
klao@445: //0 normalis, 1 s, 2, true, ez az iteralasi sorrend, 
klao@445: //es a vege a false azaz (invalid, 3)    
klao@445:     class NodeIt;
klao@445:     friend class NodeIt;
klao@445: //GNI, int
klao@445:     class Edge;
klao@445:     friend class Edge;
klao@445: //GE, int, GN
klao@445: //0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend,
klao@445: //invalid: (invalid, 3, invalid)
klao@445:     class OutEdgeIt;
klao@445:     friend class OutEdgeIt;
klao@445: //GO, int, GNI
klao@445: //normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid)
klao@445: //s-bol (invalid, 1, first), ... (invalid, 3, invalid)
klao@445: //t-bol (invalid, 3, invalid)
klao@445:     class InEdgeIt;
klao@445:     friend class InEdgeIt;
klao@445: //GI, int, GNI
klao@445: //normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid)
klao@445: //s-be (invalid, 3, invalid)
klao@445: //t-be (invalid, 2, first), ... (invalid, 3, invalid)
klao@445:     class EdgeIt;
klao@445:     friend class EdgeIt;
klao@445: //(first, 0, invalid) ...
klao@445: //(invalid, 1, vmi)
klao@445: //(invalid, 2, vmi)
klao@445: //invalid, 3, invalid)
klao@445:     template <typename T> class NodeMap;
klao@445:     template <typename T, typename Parent> class EdgeMap;
klao@445: 
klao@445: //    template <typename T> friend class NodeMap;
klao@445: //    template <typename T> friend class EdgeMap;
klao@445: 
klao@445:     const Node S_NODE;
klao@445:     const Node T_NODE;
klao@445: 
klao@445:     static const bool S_CLASS=false;
klao@445:     static const bool T_CLASS=true;
klao@445: 
klao@445:     stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) , 
klao@445: 				    S_NODE(INVALID, 1), 
klao@445: 				    T_NODE(INVALID, 2) { }
klao@445: 
klao@445:     
klao@445:     class Node : public Graph::Node {
klao@445:     protected:
klao@445:       friend class GraphWrapper<Graph>;
klao@445:       friend class stGraphWrapper<Graph>;
klao@445:       template <typename T> friend class NodeMap;
klao@445:       friend class Edge;
klao@445:       friend class OutEdgeIt;
klao@445:       friend class InEdgeIt;
klao@445:       friend class EdgeIt;
klao@445:       int spec; 
klao@445:     public:
klao@445:       Node() { }
klao@445:       Node(const typename Graph::Node& _n, int _spec=0) : 
klao@445: 	Graph::Node(_n), spec(_spec) { }
klao@445:       Node(const Invalid& i) : Graph::Node(i), spec(3) { }
klao@445:       friend bool operator==(const Node& u, const Node& v) { 
klao@445: 	return (u.spec==v.spec && 
klao@445: 		static_cast<typename Graph::Node>(u)==
klao@445: 		static_cast<typename Graph::Node>(v));
klao@445:       } 
klao@445:       friend bool operator!=(const Node& u, const Node& v) { 
klao@445: 	return (v.spec!=u.spec || 
klao@445: 		static_cast<typename Graph::Node>(u)!=
klao@445: 		static_cast<typename Graph::Node>(v));
klao@445:       }
klao@445:       friend std::ostream& operator<< <Graph>(std::ostream& os, const Node& i);
klao@445:       int getSpec() const { return spec; }
klao@445:     };
klao@445: 
klao@445:     class NodeIt { 
klao@445:       friend class GraphWrapper<Graph>;
klao@445:       friend class stGraphWrapper<Graph>;
klao@445:       typename Graph::NodeIt n;
klao@445:       int spec; 
klao@445:      public:
klao@445:       NodeIt() { }
klao@445:       NodeIt(const typename Graph::NodeIt& _n, int _spec) : 
klao@445: 	n(_n), spec(_spec) { }
klao@445:       NodeIt(const Invalid& i) : n(i), spec(3) { }
klao@445:       NodeIt(const stGraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) { 
klao@445: 	if (!_G.graph->valid(n)) spec=1;
klao@445:       }
klao@445:       operator Node() const { return Node(n, spec); }
klao@445:     };
klao@445: 
klao@445:     typedef NodeIt NodeIt;
klao@445:     typedef Node Node;
klao@445: 
klao@445:     class Edge : public Graph::Edge {
klao@445:       friend class GraphWrapper<Graph>;
klao@445:       friend class stGraphWrapper<Graph>;
klao@445:       template <typename T, typename Parent> friend class EdgeMap;
klao@445:       int spec;
klao@445:       typename Graph::Node n;
klao@445:     public:
klao@445:       Edge() { }
klao@445:       Edge(const typename Graph::Edge& _e, int _spec, 
klao@445: 	   const typename Graph::Node& _n) : 
klao@445: 	Graph::Edge(_e), spec(_spec), n(_n) { 
klao@445:       }
klao@445:       Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { }
klao@445:       friend bool operator==(const Edge& u, const Edge& v) { 
klao@445: 	return (u.spec==v.spec && 
klao@445: 		static_cast<typename Graph::Edge>(u)==
klao@445: 		static_cast<typename Graph::Edge>(v) && 
klao@445: 		u.n==v.n);
klao@445:       } 
klao@445:       friend bool operator!=(const Edge& u, const Edge& v) { 
klao@445: 	return (v.spec!=u.spec || 
klao@445: 		static_cast<typename Graph::Edge>(u)!=
klao@445: 		static_cast<typename Graph::Edge>(v) || 
klao@445: 		u.n!=v.n);
klao@445:       } 
klao@445:       friend std::ostream& operator<< <Graph>(std::ostream& os, const Edge& i);
klao@445:       int getSpec() const { return spec; }
klao@445:     };
klao@445: 
klao@445:     class OutEdgeIt { 
klao@445:       friend class GraphWrapper<Graph>;
klao@445:       friend class stGraphWrapper<Graph>;
klao@445:       typename Graph::OutEdgeIt e;
klao@445:       int spec;
klao@445:       typename Graph::ClassNodeIt n;
klao@445:     public:
klao@445:       OutEdgeIt() { }
klao@445:       OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec, 
klao@445: 		const typename Graph::ClassNodeIt& _n) : 
klao@445: 	e(_e), spec(_spec), n(_n) { 
klao@445:       }
klao@445:       OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
klao@445:       OutEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
klao@445: 	switch (_n.spec) {
klao@445: 	  case 0 : 
klao@445: 	    if (_G.graph->inSClass(_n)) { //S, van normalis kiel 
klao@445: 	      e=typename Graph::OutEdgeIt(*(_G.graph), 
klao@445: 					  typename Graph::Node(_n)); 
klao@445: 	      spec=0;
klao@445: 	      n=INVALID;
klao@445: 	      if (!_G.graph->valid(e)) spec=3;
klao@445: 	    } else { //T, specko kiel van
klao@445: 	      e=INVALID;
klao@445: 	      spec=2;
klao@445: 	      n=_n;
klao@445: 	    }
klao@445: 	    break;
klao@445: 	  case 1:
klao@445: 	    e=INVALID;
klao@445: 	    spec=1;
klao@445: 	    _G.graph->first(n, S_CLASS); //s->vmi;
klao@445: 	    if (!_G.graph->valid(n)) spec=3; //Ha S ures
klao@445: 	    break;
klao@445: 	  case 2:
klao@445: 	    e=INVALID;
klao@445: 	    spec=3;
klao@445: 	    n=INVALID;
klao@445: 	    break;
klao@445: 	}
klao@445:       }
klao@445:       operator Edge() const { return Edge(e, spec, n); }
klao@445:     };
klao@445: 
klao@445:     class InEdgeIt { 
klao@445:       friend class GraphWrapper<Graph>;
klao@445:       friend class stGraphWrapper<Graph>;
klao@445:       typename Graph::InEdgeIt e;
klao@445:       int spec;
klao@445:       typename Graph::ClassNodeIt n;
klao@445:     public:
klao@445:       InEdgeIt() { }
klao@445:       InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec, 
klao@445: 	       const typename Graph::ClassNodeIt& _n) : 
klao@445: 	e(_e), spec(_spec), n(_n) { 
klao@445:       }
klao@445:       InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
klao@445:       InEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
klao@445: 	switch (_n.spec) {
klao@445: 	  case 0 : 
klao@445: 	    if (_G.graph->inTClass(_n)) { //T, van normalis beel 
klao@445: 	      e=typename Graph::InEdgeIt(*(_G.graph), 
klao@445: 					 typename Graph::Node(_n)); 
klao@445: 	      spec=0;
klao@445: 	      n=INVALID;
klao@445: 	      if (!_G.graph->valid(e)) spec=3;
klao@445: 	    } else { //S, specko beel van
klao@445: 	      e=INVALID;
klao@445: 	      spec=1;
klao@445: 	      n=_n;
klao@445: 	    }
klao@445: 	    break;
klao@445: 	  case 1:
klao@445: 	    e=INVALID;
klao@445: 	    spec=3;
klao@445: 	    n=INVALID;
klao@445: 	    break;
klao@445: 	  case 2:
klao@445: 	    e=INVALID;
klao@445: 	    spec=2;
klao@445: 	    _G.graph->first(n, T_CLASS); //vmi->t;
klao@445: 	    if (!_G.graph->valid(n)) spec=3; //Ha T ures
klao@445: 	    break;
klao@445: 	}
klao@445:       }
klao@445:       operator Edge() const { return Edge(e, spec, n); }
klao@445:     };
klao@445: 
klao@445:     class EdgeIt { 
klao@445:       friend class GraphWrapper<Graph>;
klao@445:       friend class stGraphWrapper<Graph>;
klao@445:       typename Graph::EdgeIt e;
klao@445:       int spec;
klao@445:       typename Graph::ClassNodeIt n;
klao@445:     public:
klao@445:       EdgeIt() { }
klao@445:       EdgeIt(const typename Graph::EdgeIt& _e, int _spec, 
klao@445: 	     const typename Graph::ClassNodeIt& _n) : 
klao@445: 	e(_e), spec(_spec), n(_n) { }
klao@445:       EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
klao@445:       EdgeIt(const stGraphWrapper<Graph>& _G) : 
klao@445: 	e(*(_G.graph)), spec(0), n(INVALID) { 
klao@445: 	if (!_G.graph->valid(e)) {
klao@445: 	  spec=1;
klao@445: 	  _G.graph->first(n, S_CLASS);
klao@445: 	  if (!_G.graph->valid(n)) { //Ha S ures
klao@445: 	    spec=2;
klao@445: 	    _G.graph->first(n, T_CLASS);
klao@445: 	    if (!_G.graph->valid(n)) { //Ha T ures
klao@445: 	      spec=3;
klao@445: 	    }
klao@445: 	  }
klao@445: 	}
klao@445:       }
klao@445:       operator Edge() const { return Edge(e, spec, n); }
klao@445:     };
klao@445:    
klao@445:     NodeIt& first(NodeIt& i) const { 
klao@445:       i=NodeIt(*this); return i;
klao@445:     }
klao@445:     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
klao@445:       i=OutEdgeIt(*this, p); return i;
klao@445:     }
klao@445:     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
klao@445:       i=InEdgeIt(*this, p); return i;
klao@445:     }
klao@445:     EdgeIt& first(EdgeIt& i) const { 
klao@445:       i=EdgeIt(*this); return i;
klao@445:     }
klao@445: 
klao@445:     NodeIt& next(NodeIt& i) const { 
klao@445:       switch (i.spec) {
klao@445: 	case 0:
klao@445: 	  this->graph->next(i.n);
klao@445: 	  if (!this->graph->valid(i.n)) {
klao@445: 	    i.spec=1;
klao@445: 	  }
klao@445: 	  break;
klao@445: 	case 1:
klao@445: 	  i.spec=2;
klao@445: 	  break;
klao@445: 	case 2:
klao@445: 	  i.spec=3;
klao@445: 	  break;
klao@445:       }
klao@445:       return i; 
klao@445:     }
klao@445:     OutEdgeIt& next(OutEdgeIt& i) const { 
klao@445:       typename Graph::Node v;
klao@445:       switch (i.spec) {
klao@445: 	case 0: //normal edge
klao@445: 	  v=this->graph->aNode(i.e);
klao@445: 	  this->graph->next(i.e);
klao@445: 	  if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
klao@445: 	    if (this->graph->inSClass(v)) { //S, nincs kiel
klao@445: 	      i.spec=3;
klao@445: 	      i.n=INVALID;
klao@445: 	    } else { //T, van kiel
klao@445: 	      i.spec=2; 
klao@445: 	      i.n=v;
klao@445: 	    }
klao@445: 	  }
klao@445: 	  break;
klao@445: 	case 1: //s->vmi
klao@445: 	  this->graph->next(i.n);
klao@445: 	  if (!this->graph->valid(i.n)) i.spec=3;
klao@445: 	  break;
klao@445: 	case 2: //vmi->t
klao@445: 	  i.spec=3;
klao@445: 	  i.n=INVALID;
klao@445: 	  break;
klao@445:       }
klao@445:       return i; 
klao@445:     }
klao@445:     InEdgeIt& next(InEdgeIt& i) const { 
klao@445:       typename Graph::Node v;
klao@445:       switch (i.spec) {
klao@445: 	case 0: //normal edge
klao@445: 	  v=this->graph->aNode(i.e);
klao@445: 	  this->graph->next(i.e);
klao@445: 	  if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
klao@445: 	    if (this->graph->inTClass(v)) { //S, nincs beel
klao@445: 	      i.spec=3;
klao@445: 	      i.n=INVALID;
klao@445: 	    } else { //S, van beel
klao@445: 	      i.spec=1; 
klao@445: 	      i.n=v;
klao@445: 	    }
klao@445: 	  }
klao@445: 	  break;
klao@445: 	case 1: //s->vmi
klao@445: 	  i.spec=3;
klao@445: 	  i.n=INVALID;
klao@445: 	  break;
klao@445: 	case 2: //vmi->t
klao@445: 	  this->graph->next(i.n);
klao@445: 	  if (!this->graph->valid(i.n)) i.spec=3;
klao@445: 	  break;
klao@445:       }
klao@445:       return i; 
klao@445:     }
klao@445: 
klao@445:     EdgeIt& next(EdgeIt& i) const { 
klao@445:       switch (i.spec) {
klao@445: 	case 0:
klao@445: 	  this->graph->next(i.e);
klao@445: 	  if (!this->graph->valid(i.e)) { 
klao@445: 	    i.spec=1;
klao@445: 	    this->graph->first(i.n, S_CLASS);
klao@445: 	    if (!this->graph->valid(i.n)) {
klao@445: 	      i.spec=2;
klao@445: 	      this->graph->first(i.n, T_CLASS);
klao@445: 	      if (!this->graph->valid(i.n)) i.spec=3;
klao@445: 	    }
klao@445: 	  }
klao@445: 	  break;
klao@445: 	case 1:
klao@445: 	  this->graph->next(i.n);
klao@445: 	  if (!this->graph->valid(i.n)) {
klao@445: 	    i.spec=2;
klao@445: 	    this->graph->first(i.n, T_CLASS);
klao@445: 	    if (!this->graph->valid(i.n)) i.spec=3;
klao@445: 	  }
klao@445: 	  break;
klao@445: 	case 2:
klao@445: 	  this->graph->next(i.n);
klao@445: 	  if (!this->graph->valid(i.n)) i.spec=3;
klao@445: 	  break;
klao@445:       }
klao@445:       return i; 
klao@445:     }    
klao@445: 
klao@445:     Node tail(const Edge& e) const { 
klao@445:       switch (e.spec) {
klao@445:       case 0: 
klao@445: 	return Node(this->graph->tail(e));
klao@445: 	break;
klao@445:       case 1:
klao@445: 	return S_NODE;
klao@445: 	break;
klao@445:       case 2:
klao@445:       default:
klao@445: 	return Node(e.n);
klao@445: 	break;
klao@445:       }
klao@445:     }
klao@445:     Node head(const Edge& e) const { 
klao@445:       switch (e.spec) {
klao@445:       case 0: 
klao@445: 	return Node(this->graph->head(e));
klao@445: 	break;
klao@445:       case 1:
klao@445: 	return Node(e.n);
klao@445: 	break;
klao@445:       case 2:
klao@445:       default:
klao@445: 	return T_NODE;
klao@445: 	break;
klao@445:       }
klao@445:     }
klao@445: 
klao@445:     bool valid(const Node& n) const { return (n.spec<3); }
klao@445:     bool valid(const Edge& e) const { return (e.spec<3); }
klao@445: 
klao@445:     int nodeNum() const { return this->graph->nodeNum()+2; }
klao@445:     int edgeNum() const { 
klao@445:       return this->graph->edgeNum()+this->graph->nodeNum(); 
klao@445:     }
klao@445:   
klao@445:     Node aNode(const OutEdgeIt& e) const { return tail(e); }
klao@445:     Node aNode(const InEdgeIt& e) const { return head(e); }
klao@445:     Node bNode(const OutEdgeIt& e) const { return head(e); }
klao@445:     Node bNode(const InEdgeIt& e) const { return tail(e); }
klao@445: 
klao@445:     void addNode() const { }
klao@445:     void addEdge() const { }
klao@445:     
klao@445: //    Node addNode() const { return Node(this->graph->addNode()); }
klao@445: //    Edge addEdge(const Node& tail, const Node& head) const { 
klao@445: //      return Edge(this->graph->addEdge(tail, head)); }
klao@445: 
klao@445: //    void erase(const Node& i) const { this->graph->erase(i); }
klao@445: //    void erase(const Edge& i) const { this->graph->erase(i); }
klao@445:   
klao@445: //    void clear() const { this->graph->clear(); }
klao@445:     
klao@445:     template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> { 
klao@445:       typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;
klao@445:       T s_value, t_value;
klao@445:     public:
klao@445:       NodeMap(const stGraphWrapper<Graph>& _G) :  Parent(_G), 
klao@445: 						  s_value(), 
klao@445: 						  t_value() { }
klao@445:       NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), 
klao@445: 						      s_value(a), 
klao@445: 						      t_value(a) { }
klao@445:       T operator[](const Node& n) const { 
klao@445: 	switch (n.spec) {
klao@445: 	case 0: 
klao@445: 	  return Parent::operator[](n);
klao@445: 	  break;
klao@445: 	case 1:
klao@445: 	  return s_value;
klao@445: 	  break;
klao@445: 	case 2: 
klao@445: 	default:
klao@445: 	  return t_value;
klao@445: 	  break;
klao@445: 	}
klao@445:       }
klao@445:       void set(const Node& n, T t) { 
klao@445: 	switch (n.spec) {
klao@445: 	case 0: 
klao@445: 	  GraphWrapper<Graph>::template NodeMap<T>::set(n, t);
klao@445: 	  break;
klao@445: 	case 1:
klao@445: 	  s_value=t;
klao@445: 	  break;
klao@445: 	case 2:
klao@445: 	default:
klao@445: 	  t_value=t;
klao@445: 	  break;
klao@445: 	}
klao@445:       }
klao@445:     };
klao@445: 
klao@445:     template<typename T, 
klao@445: 	     typename Parent=
klao@445: 	     typename GraphWrapper<Graph>::template EdgeMap<T> > 
klao@445:     class EdgeMap : public Parent { 
klao@445:       //typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
klao@445:       typename GraphWrapper<Graph>::template NodeMap<T> node_value;
klao@445:     public:
klao@445:       EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G), 
klao@445: 						 node_value(_G) { }
klao@445:       EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), 
klao@445: 						      node_value(_G, a) { }
klao@445:       T operator[](const Edge& e) const { 
klao@445: 	switch (e.spec) {
klao@445: 	case 0: 
klao@445: 	  return Parent::operator[](e);
klao@445: 	  break;
klao@445: 	case 1:
klao@445: 	  return node_value[e.n];
klao@445: 	  break;
klao@445: 	case 2:
klao@445: 	default:
klao@445: 	  return node_value[e.n];
klao@445: 	  break;
klao@445: 	}
klao@445:       }
klao@445:       void set(const Edge& e, T t) { 
klao@445: 	switch (e.spec) {
klao@445: 	case 0: 
klao@445: 	  Parent::set(e, t);
klao@445: 	  break;
klao@445: 	case 1:
klao@445: 	  node_value.set(e.n, t);
klao@445: 	  break;
klao@445: 	case 2:
klao@445: 	default:
klao@445: 	  node_value.set(e.n, t);
klao@445: 	  break;
klao@445: 	}
klao@445:       }
klao@445:     };
klao@445: 
klao@445: //     template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> { 
klao@445: //       typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
klao@445: //       typename GraphWrapper<Graph>::template NodeMap<T> node_value;
klao@445: //     public:
klao@445: //       EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G), 
klao@445: // 						 node_value(_G) { }
klao@445: //       EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), 
klao@445: // 						      node_value(_G, a) { }
klao@445: //       T operator[](const Edge& e) const { 
klao@445: // 	switch (e.spec) {
klao@445: // 	case 0: 
klao@445: // 	  return Parent::operator[](e);
klao@445: // 	  break;
klao@445: // 	case 1:
klao@445: // 	  return node_value[e.n];
klao@445: // 	  break;
klao@445: // 	case 2:
klao@445: // 	default:
klao@445: // 	  return node_value[e.n];
klao@445: // 	  break;
klao@445: // 	}
klao@445: //       }
klao@445: //       void set(const Edge& e, T t) { 
klao@445: // 	switch (e.spec) {
klao@445: // 	case 0: 
klao@445: // 	  GraphWrapper<Graph>::template EdgeMap<T>::set(e, t);
klao@445: // 	  break;
klao@445: // 	case 1:
klao@445: // 	  node_value.set(e.n, t);
klao@445: // 	  break;
klao@445: // 	case 2:
klao@445: // 	default:
klao@445: // 	  node_value.set(e.n, t);
klao@445: // 	  break;
klao@445: // 	}
klao@445: //       }
klao@445: //     };
klao@445: 
klao@445:   };
klao@445: 
klao@445:   ///@}
klao@445: 
klao@445: } //namespace hugo
klao@445: 
klao@445: 
klao@445: #endif //HUGO_GRAPH_WRAPPER_H
klao@445: