// -*- c++ -*- #ifndef HUGO_GRAPH_WRAPPER_H #define HUGO_GRAPH_WRAPPER_H #include #include namespace hugo { /// \addtogroup gwrappers /// @{ /// Graph wrappers /// A main parts of HUGOlib 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 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 tail(const Edge& e) const { return Node(graph->tail(static_cast(e))); } Node head(const Edge& e) const { return Node(graph->head(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& tail, const Node& head) const { return Edge(graph->addEdge(tail, head)); } 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 tail(const Edge& e) const { return GraphWrapper::head(e); } Node head(const Edge& e) const { return GraphWrapper::tail(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->tail(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->tail(e); else return this->graph->head(e); } Node bNode(const OutEdgeIt& e) const { if (e.out_or_in) return this->graph->head(e); else return this->graph->tail(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 tail(Edge e) const { return ((e.forward) ? this->graph->tail(e) : this->graph->head(e)); } Node head(Edge e) const { return ((e.forward) ? this->graph->head(e) : this->graph->tail(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->tail(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 tail(const Edge& e) { if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) return Node(this->graph->tail(e)); else return Node(this->graph->head(e)); } Node head(const Edge& e) { if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) return Node(this->graph->head(e)); else return Node(this->graph->tail(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]; } }; /// 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); } }; 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 tail(const Edge& e) const { switch (e.spec) { case 0: return Node(this->graph->tail(e)); break; case 1: return S_NODE; break; case 2: default: return Node(e.n); break; } } Node head(const Edge& e) const { switch (e.spec) { case 0: return Node(this->graph->head(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 tail(e); } Node aNode(const InEdgeIt& e) const { return head(e); } Node bNode(const OutEdgeIt& e) const { return head(e); } Node bNode(const InEdgeIt& e) const { return tail(e); } void addNode() const { } void addEdge() const { } // Node addNode() const { return Node(this->graph->addNode()); } // Edge addEdge(const Node& tail, const Node& head) const { // return Edge(this->graph->addEdge(tail, head)); } // 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; // } // } // }; friend std::ostream& operator<<(std::ostream& os, const Node& i) { os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")"; return os; } friend std::ostream& operator<<(std::ostream& os, const Edge& i) { os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec << " node: " << i.n << ")"; return os; } }; ///@} } //namespace hugo #endif //HUGO_GRAPH_WRAPPER_H