marci@556: // -*- c++ -*- marci@556: #ifndef HUGO_GRAPH_WRAPPER_H marci@556: #define HUGO_GRAPH_WRAPPER_H marci@556: marci@556: ///\ingroup gwrappers marci@556: ///\file marci@556: ///\brief Several graph wrappers. marci@556: /// marci@556: ///This file contains several useful graph wrapper functions. marci@556: /// marci@556: ///\author Marton Makai marci@556: marci@556: #include marci@556: //#include marci@556: marci@556: namespace hugo { marci@556: marci@556: // Graph wrappers marci@556: marci@556: /// \addtogroup gwrappers marci@556: /// A main parts of HUGOlib are the different graph structures, marci@556: /// generic graph algorithms, graph concepts which couple these, and marci@556: /// graph wrappers. While the previous ones are more or less clear, the marci@556: /// latter notion needs further explanation. marci@556: /// Graph wrappers are graph classes which serve for considering graph marci@556: /// structures in different ways. A short example makes the notion much marci@556: /// clearer. marci@556: /// Suppose that we have an instance \c g of a directed graph marci@556: /// type say \c ListGraph and an algorithm marci@556: /// \code template int algorithm(const Graph&); \endcode marci@556: /// is needed to run on the reversely oriented graph. marci@556: /// It may be expensive (in time or in memory usage) to copy marci@556: /// \c g with the reverse orientation. marci@556: /// Thus, a wrapper class marci@556: /// \code template class RevGraphWrapper; \endcode is used. marci@556: /// The code looks as follows marci@556: /// \code marci@556: /// ListGraph g; marci@556: /// RevGraphWrapper rgw(g); marci@556: /// int result=algorithm(rgw); marci@556: /// \endcode marci@556: /// After running the algorithm, the original graph \c g marci@556: /// remains untouched. Thus the graph wrapper used above is to consider the marci@556: /// original graph with reverse orientation. marci@556: /// This techniques gives rise to an elegant code, and marci@556: /// based on stable graph wrappers, complex algorithms can be marci@556: /// implemented easily. marci@556: /// In flow, circulation and bipartite matching problems, the residual marci@556: /// graph is of particular importance. Combining a wrapper implementing marci@556: /// this, shortest path algorithms and minimum mean cycle algorithms, marci@556: /// a range of weighted and cardinality optimization algorithms can be marci@556: /// obtained. For lack of space, for other examples, marci@556: /// the interested user is referred to the detailed documentation of graph marci@556: /// wrappers. marci@556: /// The behavior of graph wrappers can be very different. Some of them keep marci@556: /// capabilities of the original graph while in other cases this would be marci@556: /// meaningless. This means that the concepts that they are a model of depend marci@556: /// on the graph wrapper, and the wrapped graph(s). marci@556: /// If an edge of \c rgw is deleted, this is carried out by marci@556: /// deleting the corresponding edge of \c g. But for a residual marci@556: /// graph, this operation has no sense. marci@556: /// Let we stand one more example here to simplify your work. marci@556: /// wrapper class marci@556: /// \code template class RevGraphWrapper; \endcode marci@556: /// has constructor marci@556: /// RevGraphWrapper(Graph& _g). marci@556: /// This means that in a situation, marci@556: /// when a const ListGraph& reference to a graph is given, marci@556: /// then it have to be instantiated with Graph=const ListGraph. marci@556: /// \code marci@556: /// int algorithm1(const ListGraph& g) { marci@556: /// RevGraphWrapper rgw(g); marci@556: /// return algorithm2(rgw); marci@556: /// } marci@556: /// \endcode marci@556: marci@556: /// \addtogroup gwrappers marci@556: /// @{ marci@556: marci@556: ///Base type for the Graph Wrappers marci@556: marci@556: ///This is the base type for the Graph Wrappers. marci@556: ///\todo Some more docs... marci@556: /// marci@612: ///\author Marton Makai marci@556: template marci@556: class GraphWrapper { marci@556: protected: marci@556: Graph* graph; marci@556: GraphWrapper() : graph(0) { } marci@556: void setGraph(Graph& _graph) { graph=&_graph; } marci@556: marci@556: public: marci@556: typedef Graph BaseGraph; marci@556: typedef Graph ParentGraph; marci@556: marci@556: GraphWrapper(Graph& _graph) : graph(&_graph) { } marci@556: // Graph& getGraph() const { return *graph; } marci@556: marci@556: // typedef typename Graph::Node Node; marci@556: class Node : public Graph::Node { marci@556: friend class GraphWrapper; marci@556: public: marci@556: Node() { } marci@556: Node(const typename Graph::Node& _n) : Graph::Node(_n) { } marci@556: Node(const Invalid& i) : Graph::Node(i) { } marci@556: }; marci@556: class NodeIt { marci@556: friend class GraphWrapper; marci@556: typename Graph::NodeIt n; marci@556: public: marci@556: NodeIt() { } marci@556: NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } marci@556: NodeIt(const Invalid& i) : n(i) { } marci@556: NodeIt(const GraphWrapper& _G) : n(*(_G.graph)) { } marci@556: operator Node() const { return Node(typename Graph::Node(n)); } marci@556: }; marci@556: // typedef typename Graph::Edge Edge; marci@556: class Edge : public Graph::Edge { marci@556: friend class GraphWrapper; marci@556: public: marci@556: Edge() { } marci@556: Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { } marci@556: Edge(const Invalid& i) : Graph::Edge(i) { } marci@556: }; marci@556: class OutEdgeIt { marci@556: friend class GraphWrapper; marci@556: typename Graph::OutEdgeIt e; marci@556: public: marci@556: OutEdgeIt() { } marci@556: OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } marci@556: OutEdgeIt(const Invalid& i) : e(i) { } marci@556: OutEdgeIt(const GraphWrapper& _G, const Node& _n) : marci@556: e(*(_G.graph), typename Graph::Node(_n)) { } marci@556: operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@556: }; marci@556: class InEdgeIt { marci@556: friend class GraphWrapper; marci@556: typename Graph::InEdgeIt e; marci@556: public: marci@556: InEdgeIt() { } marci@556: InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } marci@556: InEdgeIt(const Invalid& i) : e(i) { } marci@556: InEdgeIt(const GraphWrapper& _G, const Node& _n) : marci@556: e(*(_G.graph), typename Graph::Node(_n)) { } marci@556: operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@556: }; marci@556: //typedef typename Graph::SymEdgeIt SymEdgeIt; marci@556: class EdgeIt { marci@556: friend class GraphWrapper; marci@556: typename Graph::EdgeIt e; marci@556: public: marci@556: EdgeIt() { } marci@556: EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } marci@556: EdgeIt(const Invalid& i) : e(i) { } marci@556: EdgeIt(const GraphWrapper& _G) : e(*(_G.graph)) { } marci@556: operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@556: }; marci@556: marci@556: NodeIt& first(NodeIt& i) const { marci@556: i=NodeIt(*this); return i; marci@556: } marci@556: OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { marci@556: i=OutEdgeIt(*this, p); return i; marci@556: } marci@556: InEdgeIt& first(InEdgeIt& i, const Node& p) const { marci@556: i=InEdgeIt(*this, p); return i; marci@556: } marci@556: EdgeIt& first(EdgeIt& i) const { marci@556: i=EdgeIt(*this); return i; marci@556: } marci@556: marci@556: NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } marci@556: OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } marci@556: InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } marci@556: EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } marci@556: marci@556: Node tail(const Edge& e) const { marci@556: return Node(graph->tail(static_cast(e))); } marci@556: Node head(const Edge& e) const { marci@556: return Node(graph->head(static_cast(e))); } marci@556: marci@556: bool valid(const Node& n) const { marci@556: return graph->valid(static_cast(n)); } marci@556: bool valid(const Edge& e) const { marci@556: return graph->valid(static_cast(e)); } marci@556: marci@556: int nodeNum() const { return graph->nodeNum(); } marci@556: int edgeNum() const { return graph->edgeNum(); } marci@556: marci@556: Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } marci@556: Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } marci@556: Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } marci@556: Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } marci@556: marci@556: Node addNode() const { return Node(graph->addNode()); } marci@556: Edge addEdge(const Node& tail, const Node& head) const { marci@556: return Edge(graph->addEdge(tail, head)); } marci@556: marci@556: void erase(const Node& i) const { graph->erase(i); } marci@556: void erase(const Edge& i) const { graph->erase(i); } marci@556: marci@556: void clear() const { graph->clear(); } marci@556: marci@556: template class NodeMap : public Graph::template NodeMap { marci@556: typedef typename Graph::template NodeMap Parent; marci@556: public: marci@556: NodeMap(const GraphWrapper& _G) : Parent(*(_G.graph)) { } marci@556: NodeMap(const GraphWrapper& _G, T a) : Parent(*(_G.graph), a) { } marci@556: }; marci@556: marci@556: template class EdgeMap : public Graph::template EdgeMap { marci@556: typedef typename Graph::template EdgeMap Parent; marci@556: public: marci@556: EdgeMap(const GraphWrapper& _G) : Parent(*(_G.graph)) { } marci@556: EdgeMap(const GraphWrapper& _G, T a) : Parent(*(_G.graph), a) { } marci@556: }; marci@556: }; marci@556: marci@569: marci@569: marci@556: /// A graph wrapper which reverses the orientation of the edges. marci@556: marci@556: /// A graph wrapper which reverses the orientation of the edges. marci@612: /// Thus \c Graph have to be a directed graph type. marci@556: /// marci@556: ///\author Marton Makai marci@556: template marci@556: class RevGraphWrapper : public GraphWrapper { marci@556: protected: marci@612: RevGraphWrapper() : GraphWrapper() { } marci@556: public: marci@556: RevGraphWrapper(Graph& _graph) : GraphWrapper(_graph) { } marci@556: marci@556: typedef typename GraphWrapper::Node Node; marci@556: typedef typename GraphWrapper::Edge Edge; marci@556: //If Graph::OutEdgeIt is not defined marci@556: //and we do not want to use RevGraphWrapper::InEdgeIt, marci@556: //the typdef techinque does not work. marci@556: //Unfortunately all the typedefs are instantiated in templates. marci@556: //typedef typename GraphWrapper::OutEdgeIt InEdgeIt; marci@556: //typedef typename GraphWrapper::InEdgeIt OutEdgeIt; marci@556: marci@556: class OutEdgeIt { marci@556: friend class GraphWrapper; marci@556: friend class RevGraphWrapper; marci@556: typename Graph::InEdgeIt e; marci@556: public: marci@556: OutEdgeIt() { } marci@556: OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } marci@556: OutEdgeIt(const Invalid& i) : e(i) { } marci@556: OutEdgeIt(const RevGraphWrapper& _G, const Node& _n) : marci@556: e(*(_G.graph), typename Graph::Node(_n)) { } marci@556: operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@556: }; marci@556: class InEdgeIt { marci@556: friend class GraphWrapper; marci@556: friend class RevGraphWrapper; marci@556: typename Graph::OutEdgeIt e; marci@556: public: marci@556: InEdgeIt() { } marci@556: InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } marci@556: InEdgeIt(const Invalid& i) : e(i) { } marci@556: InEdgeIt(const RevGraphWrapper& _G, const Node& _n) : marci@556: e(*(_G.graph), typename Graph::Node(_n)) { } marci@556: operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@556: }; marci@556: marci@556: using GraphWrapper::first; marci@556: OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { marci@556: i=OutEdgeIt(*this, p); return i; marci@556: } marci@556: InEdgeIt& first(InEdgeIt& i, const Node& p) const { marci@556: i=InEdgeIt(*this, p); return i; marci@556: } marci@556: marci@556: using GraphWrapper::next; marci@556: OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; } marci@556: InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } marci@556: marci@556: Node aNode(const OutEdgeIt& e) const { marci@556: return Node(this->graph->aNode(e.e)); } marci@556: Node aNode(const InEdgeIt& e) const { marci@556: return Node(this->graph->aNode(e.e)); } marci@556: Node bNode(const OutEdgeIt& e) const { marci@556: return Node(this->graph->bNode(e.e)); } marci@556: Node bNode(const InEdgeIt& e) const { marci@556: return Node(this->graph->bNode(e.e)); } marci@556: marci@556: Node tail(const Edge& e) const { marci@556: return GraphWrapper::head(e); } marci@556: Node head(const Edge& e) const { marci@556: return GraphWrapper::tail(e); } marci@556: marci@556: }; marci@556: marci@569: marci@569: marci@612: /// A graph wrapper for hiding nodes and edges from a graph. marci@556: marci@556: /// This wrapper shows a graph with filtered node-set and marci@556: /// edge-set. The quick brown fox iterator jumps over marci@556: /// the lazy dog nodes or edges if the values for them are false marci@556: /// in the bool maps. marci@556: /// marci@556: ///\author Marton Makai marci@556: template marci@556: class SubGraphWrapper : public GraphWrapper { marci@556: protected: marci@556: NodeFilterMap* node_filter_map; marci@556: EdgeFilterMap* edge_filter_map; marci@556: marci@612: SubGraphWrapper() : GraphWrapper(), marci@556: node_filter_map(0), edge_filter_map(0) { } marci@556: void setNodeFilterMap(NodeFilterMap& _node_filter_map) { marci@556: node_filter_map=&_node_filter_map; marci@556: } marci@556: void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) { marci@556: edge_filter_map=&_edge_filter_map; marci@556: } marci@556: marci@556: public: marci@556: marci@556: SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, marci@556: EdgeFilterMap& _edge_filter_map) : marci@556: GraphWrapper(_graph), node_filter_map(&_node_filter_map), marci@556: edge_filter_map(&_edge_filter_map) { } marci@556: marci@556: typedef typename GraphWrapper::Node Node; marci@556: class NodeIt { marci@556: friend class GraphWrapper; marci@556: friend class SubGraphWrapper; marci@556: typename Graph::NodeIt n; marci@556: public: marci@556: NodeIt() { } marci@556: NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } marci@556: NodeIt(const Invalid& i) : n(i) { } marci@556: NodeIt(const SubGraphWrapper& _G) : marci@556: n(*(_G.graph)) { marci@556: while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n]) marci@556: _G.graph->next(n); marci@556: } marci@556: operator Node() const { return Node(typename Graph::Node(n)); } marci@556: }; marci@556: typedef typename GraphWrapper::Edge Edge; marci@556: class OutEdgeIt { marci@556: friend class GraphWrapper; marci@556: friend class SubGraphWrapper; marci@556: typename Graph::OutEdgeIt e; marci@556: public: marci@556: OutEdgeIt() { } marci@556: OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } marci@556: OutEdgeIt(const Invalid& i) : e(i) { } marci@556: OutEdgeIt(const SubGraphWrapper& _G, marci@556: const Node& _n) : marci@556: e(*(_G.graph), typename Graph::Node(_n)) { marci@556: while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) marci@556: _G.graph->next(e); marci@556: } marci@556: operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@556: }; marci@556: class InEdgeIt { marci@556: friend class GraphWrapper; marci@556: friend class SubGraphWrapper; marci@556: typename Graph::InEdgeIt e; marci@556: public: marci@556: InEdgeIt() { } marci@556: InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } marci@556: InEdgeIt(const Invalid& i) : e(i) { } marci@556: InEdgeIt(const SubGraphWrapper& _G, marci@556: const Node& _n) : marci@556: e(*(_G.graph), typename Graph::Node(_n)) { marci@556: while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) marci@556: _G.graph->next(e); marci@556: } marci@556: operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@556: }; marci@556: //typedef typename Graph::SymEdgeIt SymEdgeIt; marci@556: class EdgeIt { marci@556: friend class GraphWrapper; marci@556: friend class SubGraphWrapper; marci@556: typename Graph::EdgeIt e; marci@556: public: marci@556: EdgeIt() { } marci@556: EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } marci@556: EdgeIt(const Invalid& i) : e(i) { } marci@556: EdgeIt(const SubGraphWrapper& _G) : marci@556: e(*(_G.graph)) { marci@556: while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) marci@556: _G.graph->next(e); marci@556: } marci@556: operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@556: }; marci@556: marci@556: NodeIt& first(NodeIt& i) const { marci@556: i=NodeIt(*this); return i; marci@556: } marci@556: OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { marci@556: i=OutEdgeIt(*this, p); return i; marci@556: } marci@556: InEdgeIt& first(InEdgeIt& i, const Node& p) const { marci@556: i=InEdgeIt(*this, p); return i; marci@556: } marci@556: EdgeIt& first(EdgeIt& i) const { marci@556: i=EdgeIt(*this); return i; marci@556: } marci@556: marci@556: NodeIt& next(NodeIt& i) const { marci@556: this->graph->next(i.n); marci@556: while (this->graph->valid(i) && !(*node_filter_map)[i.n]) { marci@556: this->graph->next(i.n); } marci@556: return i; marci@556: } marci@556: OutEdgeIt& next(OutEdgeIt& i) const { marci@556: this->graph->next(i.e); marci@556: while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { marci@556: this->graph->next(i.e); } marci@556: return i; marci@556: } marci@556: InEdgeIt& next(InEdgeIt& i) const { marci@556: this->graph->next(i.e); marci@556: while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { marci@556: this->graph->next(i.e); } marci@556: return i; marci@556: } marci@556: EdgeIt& next(EdgeIt& i) const { marci@556: this->graph->next(i.e); marci@556: while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { marci@556: this->graph->next(i.e); } marci@556: return i; marci@556: } marci@556: marci@556: Node aNode(const OutEdgeIt& e) const { marci@556: return Node(this->graph->aNode(e.e)); } marci@556: Node aNode(const InEdgeIt& e) const { marci@556: return Node(this->graph->aNode(e.e)); } marci@556: Node bNode(const OutEdgeIt& e) const { marci@556: return Node(this->graph->bNode(e.e)); } marci@556: Node bNode(const InEdgeIt& e) const { marci@556: return Node(this->graph->bNode(e.e)); } marci@556: marci@561: /// This function hides \c n in the graph, i.e. the iteration marci@561: /// jumps over it. This is done by simply setting the value of \c n marci@561: /// to be false in the corresponding node-map. marci@556: void hide(const Node& n) const { node_filter_map->set(n, false); } marci@561: marci@561: /// This function hides \c e in the graph, i.e. the iteration marci@561: /// jumps over it. This is done by simply setting the value of \c e marci@561: /// to be false in the corresponding edge-map. marci@556: void hide(const Edge& e) const { edge_filter_map->set(e, false); } marci@556: marci@561: /// The value of \c n is set to be true in the node-map which stores marci@561: /// hide information. If \c n was hidden previuosly, then it is shown marci@561: /// again marci@561: void unHide(const Node& n) const { node_filter_map->set(n, true); } marci@561: marci@561: /// The value of \c e is set to be true in the edge-map which stores marci@561: /// hide information. If \c e was hidden previuosly, then it is shown marci@561: /// again marci@556: void unHide(const Edge& e) const { edge_filter_map->set(e, true); } marci@556: marci@561: /// Returns true if \c n is hidden. marci@561: bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } marci@561: marci@561: /// Returns true if \c n is hidden. marci@561: bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } marci@593: alpar@594: /// This is a linear time operation and works only if marci@593: /// NodeIt is defined. marci@593: int nodeNum() const { marci@593: int i=0; marci@593: NodeIt n; marci@593: for (this->first(n); this->valid(n); this->next(n)) ++i; marci@593: return i; marci@593: } marci@593: marci@593: /// This is a linear time operation and works only if marci@593: /// EdgeIt is defined. marci@593: int edgeNum() const { marci@593: int i=0; marci@593: EdgeIt e; marci@593: for (this->first(e); this->valid(e); this->next(e)) ++i; marci@593: return i; marci@593: } marci@593: marci@556: }; marci@556: marci@569: marci@569: marci@612: /// \brief A wrapper for forgetting the orientation of a graph. marci@612: /// marci@556: /// A wrapper for getting an undirected graph by forgetting marci@556: /// the orientation of a directed one. alpar@589: /// marci@612: /// \author Marton Makai marci@556: template marci@556: class UndirGraphWrapper : public GraphWrapper { marci@556: protected: marci@556: UndirGraphWrapper() : GraphWrapper() { } marci@556: marci@556: public: marci@556: typedef typename GraphWrapper::Node Node; marci@556: typedef typename GraphWrapper::NodeIt NodeIt; marci@556: typedef typename GraphWrapper::Edge Edge; marci@556: typedef typename GraphWrapper::EdgeIt EdgeIt; marci@556: marci@556: UndirGraphWrapper(Graph& _graph) : GraphWrapper(_graph) { } marci@556: marci@556: class OutEdgeIt { marci@556: friend class UndirGraphWrapper; marci@556: bool out_or_in; //true iff out marci@556: typename Graph::OutEdgeIt out; marci@556: typename Graph::InEdgeIt in; marci@556: public: marci@556: OutEdgeIt() { } marci@556: OutEdgeIt(const Invalid& i) : Edge(i) { } marci@556: OutEdgeIt(const UndirGraphWrapper& _G, const Node& _n) { marci@556: out_or_in=true; _G.graph->first(out, _n); marci@556: if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); } marci@556: } marci@556: operator Edge() const { marci@556: if (out_or_in) return Edge(out); else return Edge(in); marci@556: } marci@556: }; marci@556: marci@556: //FIXME InEdgeIt marci@556: typedef OutEdgeIt InEdgeIt; marci@556: marci@556: using GraphWrapper::first; marci@556: // NodeIt& first(NodeIt& i) const { marci@556: // i=NodeIt(*this); return i; marci@556: // } marci@556: OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { marci@556: i=OutEdgeIt(*this, p); return i; marci@556: } marci@556: //FIXME marci@556: // InEdgeIt& first(InEdgeIt& i, const Node& p) const { marci@556: // i=InEdgeIt(*this, p); return i; marci@556: // } marci@556: // EdgeIt& first(EdgeIt& i) const { marci@556: // i=EdgeIt(*this); return i; marci@556: // } marci@556: marci@556: using GraphWrapper::next; marci@556: // NodeIt& next(NodeIt& n) const { marci@556: // GraphWrapper::next(n); marci@556: // return n; marci@556: // } marci@556: OutEdgeIt& next(OutEdgeIt& e) const { marci@556: if (e.out_or_in) { marci@556: typename Graph::Node n=this->graph->tail(e.out); marci@556: this->graph->next(e.out); marci@556: if (!this->graph->valid(e.out)) { marci@556: e.out_or_in=false; this->graph->first(e.in, n); } marci@556: } else { marci@556: this->graph->next(e.in); marci@556: } marci@556: return e; marci@556: } marci@556: //FIXME InEdgeIt marci@556: // EdgeIt& next(EdgeIt& e) const { marci@556: // GraphWrapper::next(n); marci@556: // // graph->next(e.e); marci@556: // return e; marci@556: // } marci@556: marci@556: Node aNode(const OutEdgeIt& e) const { marci@556: if (e.out_or_in) return this->graph->tail(e); else marci@556: return this->graph->head(e); } marci@556: Node bNode(const OutEdgeIt& e) const { marci@556: if (e.out_or_in) return this->graph->head(e); else marci@556: return this->graph->tail(e); } marci@556: }; marci@556: marci@612: /// \brief An undirected graph template. marci@612: /// marci@612: /// An undirected graph template. marci@612: /// This class works as an undirected graph and a directed graph of marci@612: /// class \c Graph is used for the physical storage. marci@612: /// \ingroup graphs marci@556: template marci@556: class UndirGraph : public UndirGraphWrapper { marci@556: typedef UndirGraphWrapper Parent; marci@556: protected: marci@556: Graph gr; marci@556: public: marci@556: UndirGraph() : UndirGraphWrapper() { marci@556: Parent::setGraph(gr); marci@556: } marci@556: }; marci@556: marci@569: marci@612: ///\brief A wrapper for composing bidirected graph from a directed one. marci@612: /// experimental, for fezso's sake. marci@612: /// marci@576: /// A wrapper for composing bidirected graph from a directed one. marci@576: /// experimental, for fezso's sake. marci@612: /// A bidirected graph is composed over the directed one without physical marci@612: /// storage. As the oppositely directed edges are logically different ones marci@612: /// the maps are able to attach different values for them. marci@569: template marci@569: class BidirGraphWrapper : public GraphWrapper { marci@569: protected: marci@569: //const CapacityMap* capacity; marci@569: //FlowMap* flow; marci@569: marci@569: BidirGraphWrapper() : GraphWrapper()/*, marci@569: capacity(0), flow(0)*/ { } marci@569: // void setCapacityMap(const CapacityMap& _capacity) { marci@569: // capacity=&_capacity; marci@569: // } marci@569: // void setFlowMap(FlowMap& _flow) { marci@569: // flow=&_flow; marci@569: // } marci@569: marci@569: public: marci@569: marci@569: BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, marci@569: FlowMap& _flow*/) : marci@569: GraphWrapper(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { } marci@569: marci@569: class Edge; marci@569: class OutEdgeIt; marci@569: friend class Edge; marci@569: friend class OutEdgeIt; marci@569: marci@621: //template class NodeMap; marci@621: template class EdgeMap; marci@621: marci@569: typedef typename GraphWrapper::Node Node; marci@569: typedef typename GraphWrapper::NodeIt NodeIt; marci@621: marci@569: class Edge : public Graph::Edge { marci@569: friend class BidirGraphWrapper; marci@621: ///\bug ez nem is kell marci@621: //template friend class NodeMap; marci@621: template friend class EdgeMap; marci@569: protected: marci@569: bool backward; //true, iff backward marci@569: // typename Graph::Edge e; marci@569: public: marci@569: Edge() { } marci@626: ///\bug =false kell-e? zsoltnak kell az addEdge miatt marci@626: Edge(const typename Graph::Edge& _e, bool _backward=false) : marci@569: Graph::Edge(_e), backward(_backward) { } marci@569: Edge(const Invalid& i) : Graph::Edge(i), backward(true) { } marci@569: //the unique invalid iterator marci@569: friend bool operator==(const Edge& u, const Edge& v) { marci@569: return (v.backward==u.backward && marci@569: static_cast(u)== marci@569: static_cast(v)); marci@569: } marci@569: friend bool operator!=(const Edge& u, const Edge& v) { marci@569: return (v.backward!=u.backward || marci@569: static_cast(u)!= marci@569: static_cast(v)); marci@569: } marci@569: }; marci@569: marci@569: class OutEdgeIt { marci@569: friend class BidirGraphWrapper; marci@569: protected: marci@569: typename Graph::OutEdgeIt out; marci@569: typename Graph::InEdgeIt in; marci@569: bool backward; marci@569: public: marci@569: OutEdgeIt() { } marci@569: //FIXME marci@569: // OutEdgeIt(const Edge& e) : Edge(e) { } marci@569: OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } marci@569: //the unique invalid iterator marci@569: OutEdgeIt(const BidirGraphWrapper& _G, Node v) { marci@569: backward=false; marci@569: _G.graph->first(out, v); marci@569: while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); } marci@569: if (!_G.graph->valid(out)) { marci@569: backward=true; marci@569: _G.graph->first(in, v); marci@569: while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); } marci@569: } marci@569: } marci@569: operator Edge() const { marci@569: // Edge e; marci@569: // e.forward=this->forward; marci@569: // if (this->forward) e=out; else e=in; marci@569: // return e; marci@569: if (this->backward) marci@569: return Edge(in, this->backward); marci@569: else marci@569: return Edge(out, this->backward); marci@569: } marci@569: }; marci@569: marci@569: class InEdgeIt { marci@569: friend class BidirGraphWrapper; marci@569: protected: marci@569: typename Graph::OutEdgeIt out; marci@569: typename Graph::InEdgeIt in; marci@569: bool backward; marci@569: public: marci@569: InEdgeIt() { } marci@569: //FIXME marci@569: // OutEdgeIt(const Edge& e) : Edge(e) { } marci@569: InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } marci@569: //the unique invalid iterator marci@569: InEdgeIt(const BidirGraphWrapper& _G, Node v) { marci@569: backward=false; marci@569: _G.graph->first(in, v); marci@569: while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); } marci@569: if (!_G.graph->valid(in)) { marci@569: backward=true; marci@569: _G.graph->first(out, v); marci@569: while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); } marci@569: } marci@569: } marci@569: operator Edge() const { marci@569: // Edge e; marci@569: // e.forward=this->forward; marci@569: // if (this->forward) e=out; else e=in; marci@569: // return e; marci@569: if (this->backward) marci@569: return Edge(out, this->backward); marci@569: else marci@569: return Edge(in, this->backward); marci@569: } marci@569: }; marci@569: marci@569: class EdgeIt { marci@569: friend class BidirGraphWrapper; marci@569: protected: marci@569: typename Graph::EdgeIt e; marci@569: bool backward; marci@569: public: marci@569: EdgeIt() { } marci@569: EdgeIt(const Invalid& i) : e(i), backward(true) { } marci@569: EdgeIt(const BidirGraphWrapper& _G) { marci@569: backward=false; marci@569: _G.graph->first(e); marci@569: while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e); marci@569: if (!_G.graph->valid(e)) { marci@569: backward=true; marci@569: _G.graph->first(e); marci@569: while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e); marci@569: } marci@569: } marci@569: operator Edge() const { marci@569: return Edge(e, this->backward); marci@569: } marci@569: }; marci@569: marci@569: using GraphWrapper::first; marci@569: // NodeIt& first(NodeIt& i) const { marci@569: // i=NodeIt(*this); return i; marci@569: // } marci@569: OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { marci@569: i=OutEdgeIt(*this, p); return i; marci@569: } marci@569: // FIXME not tested marci@569: InEdgeIt& first(InEdgeIt& i, const Node& p) const { marci@569: i=InEdgeIt(*this, p); return i; marci@569: } marci@569: EdgeIt& first(EdgeIt& i) const { marci@569: i=EdgeIt(*this); return i; marci@569: } marci@556: marci@569: using GraphWrapper::next; marci@569: // NodeIt& next(NodeIt& n) const { GraphWrapper::next(n); return n; } marci@569: OutEdgeIt& next(OutEdgeIt& e) const { marci@569: if (!e.backward) { marci@569: Node v=this->graph->aNode(e.out); marci@569: this->graph->next(e.out); marci@569: while(this->graph->valid(e.out) && !enabled(e)) { marci@569: this->graph->next(e.out); } marci@569: if (!this->graph->valid(e.out)) { marci@569: e.backward=true; marci@569: this->graph->first(e.in, v); marci@569: while(this->graph->valid(e.in) && !enabled(e)) { marci@569: this->graph->next(e.in); } marci@569: } marci@569: } else { marci@569: this->graph->next(e.in); marci@569: while(this->graph->valid(e.in) && !enabled(e)) { marci@569: this->graph->next(e.in); } marci@569: } marci@569: return e; marci@569: } marci@569: // FIXME Not tested marci@569: InEdgeIt& next(InEdgeIt& e) const { marci@569: if (!e.backward) { marci@569: Node v=this->graph->aNode(e.in); marci@569: this->graph->next(e.in); marci@569: while(this->graph->valid(e.in) && !enabled(e)) { marci@569: this->graph->next(e.in); } marci@569: if (!this->graph->valid(e.in)) { marci@569: e.backward=true; marci@569: this->graph->first(e.out, v); marci@569: while(this->graph->valid(e.out) && !enabled(e)) { marci@569: this->graph->next(e.out); } marci@569: } marci@569: } else { marci@569: this->graph->next(e.out); marci@569: while(this->graph->valid(e.out) && !enabled(e)) { marci@569: this->graph->next(e.out); } marci@569: } marci@569: return e; marci@569: } marci@569: EdgeIt& next(EdgeIt& e) const { marci@569: if (!e.backward) { marci@569: this->graph->next(e.e); marci@569: while(this->graph->valid(e.e) && !enabled(e)) { marci@569: this->graph->next(e.e); } marci@569: if (!this->graph->valid(e.e)) { marci@569: e.backward=true; marci@569: this->graph->first(e.e); marci@569: while(this->graph->valid(e.e) && !enabled(e)) { marci@569: this->graph->next(e.e); } marci@569: } marci@569: } else { marci@569: this->graph->next(e.e); marci@569: while(this->graph->valid(e.e) && !enabled(e)) { marci@569: this->graph->next(e.e); } marci@569: } marci@569: return e; marci@569: } marci@569: marci@569: Node tail(Edge e) const { marci@569: return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); } marci@569: Node head(Edge e) const { marci@569: return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); } marci@569: marci@569: Node aNode(OutEdgeIt e) const { marci@569: return ((!e.backward) ? this->graph->aNode(e.out) : marci@569: this->graph->aNode(e.in)); } marci@569: Node bNode(OutEdgeIt e) const { marci@569: return ((!e.backward) ? this->graph->bNode(e.out) : marci@569: this->graph->bNode(e.in)); } marci@569: marci@569: Node aNode(InEdgeIt e) const { marci@569: return ((!e.backward) ? this->graph->aNode(e.in) : marci@569: this->graph->aNode(e.out)); } marci@569: Node bNode(InEdgeIt e) const { marci@569: return ((!e.backward) ? this->graph->bNode(e.in) : marci@569: this->graph->bNode(e.out)); } marci@569: marci@572: /// Gives back the opposite edge. marci@572: Edge opposite(const Edge& e) const { marci@572: Edge f=e; marci@572: f.backward=!f.backward; marci@572: return f; marci@572: } marci@572: marci@569: // int nodeNum() const { return graph->nodeNum(); } marci@569: //FIXME marci@569: void edgeNum() const { } marci@569: //int edgeNum() const { return graph->edgeNum(); } marci@569: marci@569: marci@569: // int id(Node v) const { return graph->id(v); } marci@569: marci@569: bool valid(Node n) const { return GraphWrapper::valid(n); } marci@569: bool valid(Edge e) const { marci@569: return this->graph->valid(e); marci@569: //return e.forward ? graph->valid(e.out) : graph->valid(e.in); marci@569: } marci@569: marci@569: bool forward(const Edge& e) const { return !e.backward; } marci@569: bool backward(const Edge& e) const { return e.backward; } marci@569: marci@569: // void augment(const Edge& e, Number a) const { marci@569: // if (!e.backward) marci@569: // // flow->set(e.out, flow->get(e.out)+a); marci@569: // flow->set(e, (*flow)[e]+a); marci@569: // else marci@569: // // flow->set(e.in, flow->get(e.in)-a); marci@569: // flow->set(e, (*flow)[e]-a); marci@569: // } marci@569: marci@569: bool enabled(const Edge& e) const { marci@569: if (!e.backward) marci@569: // return (capacity->get(e.out)-flow->get(e.out)); marci@569: //return ((*capacity)[e]-(*flow)[e]); marci@569: return true; marci@569: else marci@569: // return (flow->get(e.in)); marci@569: //return ((*flow)[e]); marci@569: return true; marci@569: } marci@569: marci@569: // Number enabled(typename Graph::OutEdgeIt out) const { marci@569: // // return (capacity->get(out)-flow->get(out)); marci@569: // return ((*capacity)[out]-(*flow)[out]); marci@569: // } marci@569: marci@569: // Number enabled(typename Graph::InEdgeIt in) const { marci@569: // // return (flow->get(in)); marci@569: // return ((*flow)[in]); marci@569: // } marci@569: marci@569: template marci@569: class EdgeMap { marci@569: typename Graph::template EdgeMap forward_map, backward_map; marci@569: public: marci@623: typedef T ValueType; marci@623: typedef Edge KeyType; marci@569: EdgeMap(const BidirGraphWrapper& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } marci@569: EdgeMap(const BidirGraphWrapper& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } marci@569: void set(Edge e, T a) { marci@569: if (!e.backward) marci@622: forward_map.set(e/*.out*/, a); marci@569: else marci@622: backward_map.set(e/*.in*/, a); marci@569: } marci@569: T operator[](Edge e) const { marci@569: if (!e.backward) marci@622: return forward_map[e/*.out*/]; marci@569: else marci@622: return backward_map[e/*.in*/]; marci@569: } marci@625: void update() { marci@625: forward_map.update(); marci@625: backward_map.update(); marci@625: } marci@569: // T get(Edge e) const { marci@569: // if (e.out_or_in) marci@569: // return forward_map.get(e.out); marci@569: // else marci@569: // return backward_map.get(e.in); marci@569: // } marci@569: }; marci@569: }; marci@569: marci@612: /// \brief A bidirected graph template. marci@612: /// marci@612: /// A bidirected graph template. marci@612: /// Such a bidirected graph stores each pair of oppositely directed edges marci@612: /// ones in the memory, i.e. a directed graph of type marci@612: /// \c Graph is used for that. marci@612: /// As the oppositely directed edges are logically different ones marci@612: /// the maps are able to attach different values for them. marci@612: /// \ingroup graphs marci@612: template marci@612: class BidirGraph : public BidirGraphWrapper { marci@612: typedef UndirGraphWrapper Parent; marci@612: protected: marci@612: Graph gr; marci@612: public: marci@612: BidirGraph() : BidirGraphWrapper() { marci@612: Parent::setGraph(gr); marci@612: } marci@612: }; marci@569: marci@556: marci@556: /// A wrapper for composing the residual graph for directed flow and circulation problems. marci@556: marci@556: /// A wrapper for composing the residual graph for directed flow and circulation problems. marci@556: template marci@556: class ResGraphWrapper : public GraphWrapper { marci@556: protected: marci@556: const CapacityMap* capacity; marci@556: FlowMap* flow; marci@556: marci@556: ResGraphWrapper() : GraphWrapper(0), marci@556: capacity(0), flow(0) { } marci@560: void setCapacityMap(const CapacityMap& _capacity) { marci@560: capacity=&_capacity; marci@556: } marci@556: void setFlowMap(FlowMap& _flow) { marci@556: flow=&_flow; marci@556: } marci@556: marci@556: public: marci@556: marci@556: ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, marci@556: FlowMap& _flow) : marci@556: GraphWrapper(_graph), capacity(&_capacity), flow(&_flow) { } marci@556: marci@556: class Edge; marci@556: class OutEdgeIt; marci@556: friend class Edge; marci@556: friend class OutEdgeIt; marci@556: marci@556: typedef typename GraphWrapper::Node Node; marci@556: typedef typename GraphWrapper::NodeIt NodeIt; marci@556: class Edge : public Graph::Edge { marci@556: friend class ResGraphWrapper; marci@556: protected: marci@565: bool backward; //true, iff backward marci@556: // typename Graph::Edge e; marci@556: public: marci@556: Edge() { } marci@565: Edge(const typename Graph::Edge& _e, bool _backward) : marci@565: Graph::Edge(_e), backward(_backward) { } marci@565: Edge(const Invalid& i) : Graph::Edge(i), backward(true) { } marci@556: //the unique invalid iterator marci@556: friend bool operator==(const Edge& u, const Edge& v) { marci@565: return (v.backward==u.backward && marci@556: static_cast(u)== marci@556: static_cast(v)); marci@556: } marci@556: friend bool operator!=(const Edge& u, const Edge& v) { marci@565: return (v.backward!=u.backward || marci@556: static_cast(u)!= marci@556: static_cast(v)); marci@556: } marci@556: }; marci@556: marci@556: class OutEdgeIt { marci@556: friend class ResGraphWrapper; marci@556: protected: marci@556: typename Graph::OutEdgeIt out; marci@556: typename Graph::InEdgeIt in; marci@565: bool backward; marci@556: public: marci@556: OutEdgeIt() { } marci@556: //FIXME marci@556: // OutEdgeIt(const Edge& e) : Edge(e) { } marci@565: OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } marci@556: //the unique invalid iterator marci@569: OutEdgeIt(const ResGraphWrapper& _G, Node v) { marci@565: backward=false; marci@569: _G.graph->first(out, v); marci@569: while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); } marci@569: if (!_G.graph->valid(out)) { marci@565: backward=true; marci@569: _G.graph->first(in, v); marci@569: while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); } marci@556: } marci@556: } marci@556: operator Edge() const { marci@556: // Edge e; marci@556: // e.forward=this->forward; marci@556: // if (this->forward) e=out; else e=in; marci@556: // return e; marci@565: if (this->backward) marci@565: return Edge(in, this->backward); marci@556: else marci@565: return Edge(out, this->backward); marci@556: } marci@556: }; marci@556: marci@556: class InEdgeIt { marci@556: friend class ResGraphWrapper; marci@556: protected: marci@556: typename Graph::OutEdgeIt out; marci@556: typename Graph::InEdgeIt in; marci@565: bool backward; marci@556: public: marci@556: InEdgeIt() { } marci@556: //FIXME marci@556: // OutEdgeIt(const Edge& e) : Edge(e) { } marci@565: InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } marci@556: //the unique invalid iterator marci@569: InEdgeIt(const ResGraphWrapper& _G, Node v) { marci@565: backward=false; marci@569: _G.graph->first(in, v); marci@569: while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); } marci@569: if (!_G.graph->valid(in)) { marci@565: backward=true; marci@569: _G.graph->first(out, v); marci@569: while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); } marci@556: } marci@556: } marci@556: operator Edge() const { marci@556: // Edge e; marci@556: // e.forward=this->forward; marci@556: // if (this->forward) e=out; else e=in; marci@556: // return e; marci@565: if (this->backward) marci@565: return Edge(out, this->backward); marci@556: else marci@565: return Edge(in, this->backward); marci@556: } marci@556: }; marci@556: marci@556: class EdgeIt { marci@556: friend class ResGraphWrapper; marci@556: protected: marci@556: typename Graph::EdgeIt e; marci@565: bool backward; marci@556: public: marci@556: EdgeIt() { } marci@565: EdgeIt(const Invalid& i) : e(i), backward(true) { } marci@569: EdgeIt(const ResGraphWrapper& _G) { marci@565: backward=false; marci@569: _G.graph->first(e); marci@569: while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e); marci@569: if (!_G.graph->valid(e)) { marci@565: backward=true; marci@569: _G.graph->first(e); marci@569: while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e); marci@556: } marci@556: } marci@556: operator Edge() const { marci@565: return Edge(e, this->backward); marci@556: } marci@556: }; marci@556: marci@556: using GraphWrapper::first; marci@556: // NodeIt& first(NodeIt& i) const { marci@556: // i=NodeIt(*this); return i; marci@556: // } marci@556: OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { marci@556: i=OutEdgeIt(*this, p); return i; marci@556: } marci@556: // FIXME not tested marci@556: InEdgeIt& first(InEdgeIt& i, const Node& p) const { marci@556: i=InEdgeIt(*this, p); return i; marci@556: } marci@556: EdgeIt& first(EdgeIt& i) const { marci@556: i=EdgeIt(*this); return i; marci@556: } marci@556: marci@556: using GraphWrapper::next; marci@556: // NodeIt& next(NodeIt& n) const { GraphWrapper::next(n); return n; } marci@556: OutEdgeIt& next(OutEdgeIt& e) const { marci@565: if (!e.backward) { marci@556: Node v=this->graph->aNode(e.out); marci@556: this->graph->next(e.out); marci@556: while( this->graph->valid(e.out) && !(resCap(e)>0) ) { marci@556: this->graph->next(e.out); } marci@556: if (!this->graph->valid(e.out)) { marci@565: e.backward=true; marci@556: this->graph->first(e.in, v); marci@556: while( this->graph->valid(e.in) && !(resCap(e)>0) ) { marci@556: this->graph->next(e.in); } marci@556: } marci@556: } else { marci@556: this->graph->next(e.in); marci@556: while( this->graph->valid(e.in) && !(resCap(e)>0) ) { marci@556: this->graph->next(e.in); } marci@556: } marci@556: return e; marci@556: } marci@556: // FIXME Not tested marci@556: InEdgeIt& next(InEdgeIt& e) const { marci@565: if (!e.backward) { marci@556: Node v=this->graph->aNode(e.in); marci@556: this->graph->next(e.in); marci@556: while( this->graph->valid(e.in) && !(resCap(e)>0) ) { marci@556: this->graph->next(e.in); } marci@556: if (!this->graph->valid(e.in)) { marci@565: e.backward=true; marci@556: this->graph->first(e.out, v); marci@556: while( this->graph->valid(e.out) && !(resCap(e)>0) ) { marci@556: this->graph->next(e.out); } marci@556: } marci@556: } else { marci@556: this->graph->next(e.out); marci@556: while( this->graph->valid(e.out) && !(resCap(e)>0) ) { marci@556: this->graph->next(e.out); } marci@556: } marci@556: return e; marci@556: } marci@556: EdgeIt& next(EdgeIt& e) const { marci@565: if (!e.backward) { marci@556: this->graph->next(e.e); marci@556: while( this->graph->valid(e.e) && !(resCap(e)>0) ) { marci@556: this->graph->next(e.e); } marci@556: if (!this->graph->valid(e.e)) { marci@565: e.backward=true; marci@556: this->graph->first(e.e); marci@556: while( this->graph->valid(e.e) && !(resCap(e)>0) ) { marci@556: this->graph->next(e.e); } marci@556: } marci@556: } else { marci@556: this->graph->next(e.e); marci@556: while( this->graph->valid(e.e) && !(resCap(e)>0) ) { marci@556: this->graph->next(e.e); } marci@556: } marci@556: return e; marci@556: } marci@556: marci@556: Node tail(Edge e) const { marci@565: return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); } marci@556: Node head(Edge e) const { marci@565: return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); } marci@556: marci@556: Node aNode(OutEdgeIt e) const { marci@565: return ((!e.backward) ? this->graph->aNode(e.out) : marci@556: this->graph->aNode(e.in)); } marci@556: Node bNode(OutEdgeIt e) const { marci@565: return ((!e.backward) ? this->graph->bNode(e.out) : marci@556: this->graph->bNode(e.in)); } marci@556: marci@556: Node aNode(InEdgeIt e) const { marci@565: return ((!e.backward) ? this->graph->aNode(e.in) : marci@556: this->graph->aNode(e.out)); } marci@556: Node bNode(InEdgeIt e) const { marci@565: return ((!e.backward) ? this->graph->bNode(e.in) : marci@556: this->graph->bNode(e.out)); } marci@556: marci@556: // int nodeNum() const { return graph->nodeNum(); } marci@556: //FIXME marci@556: void edgeNum() const { } marci@556: //int edgeNum() const { return graph->edgeNum(); } marci@556: marci@556: marci@556: // int id(Node v) const { return graph->id(v); } marci@556: marci@556: bool valid(Node n) const { return GraphWrapper::valid(n); } marci@556: bool valid(Edge e) const { marci@556: return this->graph->valid(e); marci@556: //return e.forward ? graph->valid(e.out) : graph->valid(e.in); marci@556: } marci@556: marci@565: bool forward(const Edge& e) const { return !e.backward; } marci@565: bool backward(const Edge& e) const { return e.backward; } marci@556: marci@556: void augment(const Edge& e, Number a) const { marci@565: if (!e.backward) marci@556: // flow->set(e.out, flow->get(e.out)+a); marci@556: flow->set(e, (*flow)[e]+a); marci@556: else marci@556: // flow->set(e.in, flow->get(e.in)-a); marci@556: flow->set(e, (*flow)[e]-a); marci@556: } marci@556: marci@556: Number resCap(const Edge& e) const { marci@565: if (!e.backward) marci@556: // return (capacity->get(e.out)-flow->get(e.out)); marci@556: return ((*capacity)[e]-(*flow)[e]); marci@556: else marci@556: // return (flow->get(e.in)); marci@556: return ((*flow)[e]); marci@556: } marci@556: marci@556: // Number resCap(typename Graph::OutEdgeIt out) const { marci@556: // // return (capacity->get(out)-flow->get(out)); marci@556: // return ((*capacity)[out]-(*flow)[out]); marci@556: // } marci@556: marci@556: // Number resCap(typename Graph::InEdgeIt in) const { marci@556: // // return (flow->get(in)); marci@556: // return ((*flow)[in]); marci@556: // } marci@556: marci@556: template marci@556: class EdgeMap { marci@556: typename Graph::template EdgeMap forward_map, backward_map; marci@556: public: marci@624: typedef T ValueType; marci@624: typedef Edge KeyType; marci@556: EdgeMap(const ResGraphWrapper& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } marci@556: EdgeMap(const ResGraphWrapper& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } marci@556: void set(Edge e, T a) { marci@565: if (!e.backward) marci@624: forward_map.set(e/*.out*/, a); marci@556: else marci@624: backward_map.set(e/*.in*/, a); marci@556: } marci@556: T operator[](Edge e) const { marci@565: if (!e.backward) marci@624: return forward_map[e/*.out*/]; marci@556: else marci@624: return backward_map[e/*.in*/]; marci@556: } marci@625: void update() { marci@625: forward_map.update(); marci@625: backward_map.update(); marci@625: } marci@556: // T get(Edge e) const { marci@556: // if (e.out_or_in) marci@556: // return forward_map.get(e.out); marci@556: // else marci@556: // return backward_map.get(e.in); marci@556: // } marci@556: }; marci@556: }; marci@556: marci@569: marci@569: marci@612: /// For blocking flows. marci@556: marci@612: /// This graph wrapper is used for Dinits blocking flow computations. marci@612: /// For each node, an out-edge is stored which is used when the marci@612: /// \code marci@612: /// OutEdgeIt& first(OutEdgeIt&, const Node&) marci@612: /// \endcode marci@612: /// is called. marci@556: /// marci@556: ///\author Marton Makai marci@556: template marci@556: class ErasingFirstGraphWrapper : public GraphWrapper { marci@556: protected: marci@556: FirstOutEdgesMap* first_out_edges; marci@556: public: marci@556: ErasingFirstGraphWrapper(Graph& _graph, marci@556: FirstOutEdgesMap& _first_out_edges) : marci@556: GraphWrapper(_graph), first_out_edges(&_first_out_edges) { } marci@556: marci@556: typedef typename GraphWrapper::Node Node; marci@556: // class NodeIt { marci@556: // friend class GraphWrapper; marci@556: // friend class ErasingFirstGraphWrapper; marci@556: // typename Graph::NodeIt n; marci@556: // public: marci@556: // NodeIt() { } marci@556: // NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } marci@556: // NodeIt(const Invalid& i) : n(i) { } marci@556: // NodeIt(const ErasingFirstGraphWrapper& _G) : marci@556: // n(*(_G.graph)) { } marci@556: // operator Node() const { return Node(typename Graph::Node(n)); } marci@556: // }; marci@556: typedef typename GraphWrapper::Edge Edge; marci@556: class OutEdgeIt { marci@556: friend class GraphWrapper; marci@556: friend class ErasingFirstGraphWrapper; marci@556: // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; marci@556: typename Graph::OutEdgeIt e; marci@556: public: marci@556: OutEdgeIt() { } marci@556: OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } marci@556: OutEdgeIt(const Invalid& i) : e(i) { } marci@556: OutEdgeIt(const ErasingFirstGraphWrapper& _G, marci@556: const Node& _n) : marci@556: e((*_G.first_out_edges)[_n]) { } marci@556: operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@556: }; marci@556: class InEdgeIt { marci@556: friend class GraphWrapper; marci@556: friend class ErasingFirstGraphWrapper; marci@556: // typedef typename Graph::InEdgeIt GraphInEdgeIt; marci@556: typename Graph::InEdgeIt e; marci@556: public: marci@556: InEdgeIt() { } marci@556: InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } marci@556: InEdgeIt(const Invalid& i) : e(i) { } marci@556: InEdgeIt(const ErasingFirstGraphWrapper& _G, marci@556: const Node& _n) : marci@556: e(*(_G.graph), typename Graph::Node(_n)) { } marci@556: operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@556: }; marci@556: //typedef typename Graph::SymEdgeIt SymEdgeIt; marci@556: class EdgeIt { marci@556: friend class GraphWrapper; marci@556: friend class ErasingFirstGraphWrapper; marci@556: // typedef typename Graph::EdgeIt GraphEdgeIt; marci@556: typename Graph::EdgeIt e; marci@556: public: marci@556: EdgeIt() { } marci@556: EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } marci@556: EdgeIt(const Invalid& i) : e(i) { } marci@556: EdgeIt(const ErasingFirstGraphWrapper& _G) : marci@556: e(*(_G.graph)) { } marci@556: operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@556: }; marci@556: marci@556: using GraphWrapper::first; marci@556: // NodeIt& first(NodeIt& i) const { marci@556: // i=NodeIt(*this); return i; marci@556: // } marci@556: OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { marci@556: i=OutEdgeIt(*this, p); return i; marci@556: } marci@556: InEdgeIt& first(InEdgeIt& i, const Node& p) const { marci@556: i=InEdgeIt(*this, p); return i; marci@556: } marci@556: EdgeIt& first(EdgeIt& i) const { marci@556: i=EdgeIt(*this); return i; marci@556: } marci@556: marci@556: using GraphWrapper::next; marci@556: // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } marci@556: OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; } marci@556: InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } marci@556: EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; } marci@556: marci@556: Node aNode(const OutEdgeIt& e) const { marci@556: return Node(this->graph->aNode(e.e)); } marci@556: Node aNode(const InEdgeIt& e) const { marci@556: return Node(this->graph->aNode(e.e)); } marci@556: Node bNode(const OutEdgeIt& e) const { marci@556: return Node(this->graph->bNode(e.e)); } marci@556: Node bNode(const InEdgeIt& e) const { marci@556: return Node(this->graph->bNode(e.e)); } marci@556: marci@556: void erase(const OutEdgeIt& e) const { marci@556: OutEdgeIt f=e; marci@556: this->next(f); marci@556: first_out_edges->set(this->tail(e), f.e); marci@556: } marci@556: }; marci@556: marci@556: ///@} marci@556: marci@556: } //namespace hugo marci@556: marci@556: #endif //HUGO_GRAPH_WRAPPER_H marci@556: