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