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@650: #include alpar@774: #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) { } alpar@774: GraphWrapper(const GraphWrapper& gw) : graph(gw.graph) { } marci@556: // Graph& getGraph() const { return *graph; } marci@556: alpar@774: typedef typename Graph::Node Node; alpar@774: class NodeIt : public Node { alpar@774: const GraphWrapper* gw; marci@556: friend class GraphWrapper; marci@556: public: marci@556: NodeIt() { } alpar@774: // NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { } alpar@774: NodeIt(Invalid i) : Node(i) { } alpar@774: NodeIt(const GraphWrapper& _gw) : alpar@774: Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { } alpar@774: NodeIt(const GraphWrapper& _gw, const Node& n) : alpar@774: Node(n), gw(&_gw) { } alpar@774: NodeIt& operator++() { alpar@774: *(static_cast(this))= alpar@774: ++(typename Graph::NodeIt(*(gw->graph), *this)); alpar@774: return *this; alpar@774: } marci@556: }; alpar@774: typedef typename Graph::Edge Edge; alpar@774: class OutEdgeIt : public Edge { alpar@774: const GraphWrapper* gw; marci@556: friend class GraphWrapper; alpar@774: public: alpar@774: OutEdgeIt() { } alpar@774: //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { } alpar@774: OutEdgeIt(Invalid i) : Edge(i) { } alpar@774: OutEdgeIt(const GraphWrapper& _gw, const Node& n) : alpar@774: Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { } alpar@774: OutEdgeIt(const GraphWrapper& _gw, const Edge& e) : alpar@774: Edge(e), gw(&_gw) { } alpar@774: OutEdgeIt& operator++() { alpar@774: *(static_cast(this))= alpar@774: ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); alpar@774: return *this; alpar@774: } marci@556: }; alpar@774: class InEdgeIt : public Edge { alpar@774: const GraphWrapper* gw; marci@556: friend class GraphWrapper; alpar@774: public: marci@556: InEdgeIt() { } alpar@774: //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { } alpar@774: InEdgeIt(Invalid i) : Edge(i) { } alpar@774: InEdgeIt(const GraphWrapper& _gw, const Node& n) : alpar@774: Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { } alpar@774: InEdgeIt(const GraphWrapper& _gw, const Edge& e) : alpar@774: Edge(e), gw(&_gw) { } alpar@774: InEdgeIt& operator++() { alpar@774: *(static_cast(this))= alpar@774: ++(typename Graph::InEdgeIt(*(gw->graph), *this)); alpar@774: return *this; alpar@774: } marci@556: }; marci@556: //typedef typename Graph::SymEdgeIt SymEdgeIt; alpar@774: class EdgeIt : public Edge { alpar@774: const GraphWrapper* gw; marci@556: friend class GraphWrapper; alpar@774: public: marci@556: EdgeIt() { } alpar@774: //EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { } alpar@774: EdgeIt(Invalid i) : Edge(i) { } alpar@774: EdgeIt(const GraphWrapper& _gw) : alpar@774: Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { } alpar@774: EdgeIt(const GraphWrapper& _gw, const Edge& e) : marci@777: Edge(e), gw(&_gw) { } alpar@774: EdgeIt& operator++() { alpar@774: *(static_cast(this))= alpar@774: ++(typename Graph::EdgeIt(*(gw->graph), *this)); alpar@774: return *this; alpar@774: } 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: alpar@774: // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } alpar@774: // OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } alpar@774: // InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } alpar@774: // 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: alpar@774: // bool valid(const Node& n) const { alpar@774: // return graph->valid(static_cast(n)); } alpar@774: // bool valid(const Edge& e) const { alpar@774: // 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: alpar@774: // Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } alpar@774: // Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } alpar@774: // Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } alpar@774: // 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: alpar@736: bool forward(const Edge& e) const { return graph->forward(e); } alpar@736: bool backward(const Edge& e) const { return graph->backward(e); } marci@739: marci@739: int id(const Node& v) const { return graph->id(v); } marci@739: int id(const Edge& e) const { return graph->id(e); } marci@650: marci@738: Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); } marci@650: marci@556: template class NodeMap : public Graph::template NodeMap { marci@556: typedef typename Graph::template NodeMap Parent; marci@556: public: alpar@774: NodeMap(const GraphWrapper& gw) : Parent(*(gw.graph)) { } alpar@774: NodeMap(const GraphWrapper& gw, T a) : Parent(*(gw.graph), a) { } marci@849: // NodeMap(const NodeMap& map) : Parent(map) { } marci@849: // template marci@849: // NodeMap(const Map& map) : Parent(map) { } marci@556: }; marci@556: marci@556: template class EdgeMap : public Graph::template EdgeMap { marci@556: typedef typename Graph::template EdgeMap Parent; marci@556: public: alpar@774: EdgeMap(const GraphWrapper& gw) : Parent(*(gw.graph)) { } alpar@774: EdgeMap(const GraphWrapper& gw, T a) : Parent(*(gw.graph), a) { } marci@849: // EdgeMap(const EdgeMap& map) : Parent(map) { } marci@849: // template marci@849: // EdgeMap(const Map& map) : Parent(map) { } 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@650: public: marci@650: typedef GraphWrapper Parent; marci@556: protected: marci@612: RevGraphWrapper() : GraphWrapper() { } marci@556: public: marci@556: RevGraphWrapper(Graph& _graph) : GraphWrapper(_graph) { } alpar@774: RevGraphWrapper(const RevGraphWrapper& gw) : Parent(gw) { } marci@556: marci@556: typedef typename GraphWrapper::Node Node; marci@556: typedef typename GraphWrapper::Edge Edge; marci@792: //remark: OutEdgeIt and InEdgeIt cannot be typedef-ed to each other marci@792: //because this does not work is some of them are not defined in the marci@792: //original graph. The problem with this is that typedef-ed stuff marci@792: //are instantiated in c++. alpar@774: class OutEdgeIt : public Edge { alpar@774: const RevGraphWrapper* gw; marci@556: friend class GraphWrapper; alpar@774: public: marci@556: OutEdgeIt() { } alpar@774: //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { } alpar@774: OutEdgeIt(Invalid i) : Edge(i) { } alpar@774: OutEdgeIt(const RevGraphWrapper& _gw, const Node& n) : alpar@774: Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { } alpar@774: OutEdgeIt(const RevGraphWrapper& _gw, const Edge& e) : alpar@774: Edge(e), gw(&_gw) { } alpar@774: OutEdgeIt& operator++() { alpar@774: *(static_cast(this))= alpar@774: ++(typename Graph::InEdgeIt(*(gw->graph), *this)); alpar@774: return *this; alpar@774: } marci@556: }; alpar@774: class InEdgeIt : public Edge { alpar@774: const RevGraphWrapper* gw; marci@556: friend class GraphWrapper; alpar@774: public: marci@556: InEdgeIt() { } alpar@774: //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { } alpar@774: InEdgeIt(Invalid i) : Edge(i) { } alpar@774: InEdgeIt(const RevGraphWrapper& _gw, const Node& n) : alpar@774: Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { } alpar@774: InEdgeIt(const RevGraphWrapper& _gw, const Edge& e) : alpar@774: Edge(e), gw(&_gw) { } alpar@774: InEdgeIt& operator++() { alpar@774: *(static_cast(this))= alpar@774: ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); alpar@774: return *this; alpar@774: } 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: alpar@774: // using GraphWrapper::next; alpar@774: // OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; } alpar@774: // InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } marci@556: alpar@774: // Node aNode(const OutEdgeIt& e) const { alpar@774: // return Node(this->graph->aNode(e.e)); } alpar@774: // Node aNode(const InEdgeIt& e) const { alpar@774: // return Node(this->graph->aNode(e.e)); } alpar@774: // Node bNode(const OutEdgeIt& e) const { alpar@774: // return Node(this->graph->bNode(e.e)); } alpar@774: // Node bNode(const InEdgeIt& e) const { alpar@774: // 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@775: marci@775: 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@838: /// edge-set. Given a bool-valued map on the node-set and one on marci@838: /// the edge-set of the graphs, the iterators shows only the objects marci@838: /// having true value. marci@838: /// The quick brown fox iterators jump over marci@838: /// the lazy dog nodes or edges if their values for are false in the marci@838: /// corresponding bool maps. marci@556: /// marci@556: ///\author Marton Makai marci@556: template marci@556: class SubGraphWrapper : public GraphWrapper { marci@650: public: marci@650: typedef GraphWrapper Parent; 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: 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@775: class NodeIt : public Node { marci@775: const SubGraphWrapper* gw; marci@556: friend class SubGraphWrapper; marci@775: public: marci@556: NodeIt() { } marci@775: // NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { } marci@775: NodeIt(Invalid i) : Node(i) { } marci@775: NodeIt(const SubGraphWrapper& _gw) : marci@854: Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { marci@854: while (*static_cast(this)!=INVALID && marci@854: !(*(gw->edge_filter_map))[*this]) marci@854: *(static_cast(this))= marci@854: ++(typename Graph::NodeIt(*(gw->graph), *this)); marci@854: } marci@775: NodeIt(const SubGraphWrapper& _gw, marci@775: const Node& n) : marci@775: Node(n), gw(&_gw) { } marci@775: NodeIt& operator++() { marci@775: *(static_cast(this))= marci@775: ++(typename Graph::NodeIt(*(gw->graph), *this)); marci@775: while (*static_cast(this)!=INVALID && marci@775: !(*(gw->node_filter_map))[*this]) marci@775: *(static_cast(this))= marci@775: ++(typename Graph::NodeIt(*(gw->graph), *this)); marci@775: return *this; marci@556: } marci@556: }; marci@556: typedef typename GraphWrapper::Edge Edge; marci@775: class OutEdgeIt : public Edge { marci@775: const SubGraphWrapper* gw; marci@556: friend class SubGraphWrapper; marci@556: public: marci@556: OutEdgeIt() { } marci@775: // OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { } marci@775: OutEdgeIt(Invalid i) : Edge(i) { } marci@775: OutEdgeIt(const SubGraphWrapper& _gw, const Node& n) : marci@854: Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { marci@854: while (*static_cast(this)!=INVALID && marci@854: !(*(gw->edge_filter_map))[*this]) marci@854: *(static_cast(this))= marci@854: ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); marci@854: } marci@775: OutEdgeIt(const SubGraphWrapper& _gw, marci@775: const Edge& e) : marci@775: Edge(e), gw(&_gw) { } marci@775: OutEdgeIt& operator++() { marci@775: *(static_cast(this))= marci@775: ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); marci@775: while (*static_cast(this)!=INVALID && marci@775: !(*(gw->edge_filter_map))[*this]) marci@775: *(static_cast(this))= marci@775: ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); marci@775: return *this; marci@556: } marci@556: }; marci@775: class InEdgeIt : public Edge { marci@775: const SubGraphWrapper* gw; marci@556: friend class SubGraphWrapper; marci@556: public: marci@556: InEdgeIt() { } marci@775: // InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { } marci@775: InEdgeIt(Invalid i) : Edge(i) { } marci@775: InEdgeIt(const SubGraphWrapper& _gw, const Node& n) : marci@854: Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { marci@854: while (*static_cast(this)!=INVALID && marci@854: !(*(gw->edge_filter_map))[*this]) marci@854: *(static_cast(this))= marci@854: ++(typename Graph::InEdgeIt(*(gw->graph), *this)); marci@854: } marci@775: InEdgeIt(const SubGraphWrapper& _gw, marci@775: const Edge& e) : marci@775: Edge(e), gw(&_gw) { } marci@775: InEdgeIt& operator++() { marci@775: *(static_cast(this))= marci@775: ++(typename Graph::InEdgeIt(*(gw->graph), *this)); marci@775: while (*static_cast(this)!=INVALID && marci@775: !(*(gw->edge_filter_map))[*this]) marci@775: *(static_cast(this))= marci@775: ++(typename Graph::InEdgeIt(*(gw->graph), *this)); marci@775: return *this; marci@556: } marci@556: }; marci@775: class EdgeIt : public Edge { marci@775: const SubGraphWrapper* gw; marci@556: friend class SubGraphWrapper; marci@556: public: marci@556: EdgeIt() { } marci@775: // EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { } marci@775: EdgeIt(Invalid i) : Edge(i) { } marci@775: EdgeIt(const SubGraphWrapper& _gw) : marci@854: Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { marci@854: while (*static_cast(this)!=INVALID && marci@854: !(*(gw->edge_filter_map))[*this]) marci@854: *(static_cast(this))= marci@854: ++(typename Graph::EdgeIt(*(gw->graph), *this)); marci@854: } marci@775: EdgeIt(const SubGraphWrapper& _gw, marci@775: const Edge& e) : marci@775: Edge(e), gw(&_gw) { } marci@775: EdgeIt& operator++() { marci@775: *(static_cast(this))= marci@775: ++(typename Graph::EdgeIt(*(gw->graph), *this)); marci@775: while (*static_cast(this)!=INVALID && marci@775: !(*(gw->edge_filter_map))[*this]) marci@775: *(static_cast(this))= marci@775: ++(typename Graph::EdgeIt(*(gw->graph), *this)); marci@775: return *this; marci@556: } 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@775: // NodeIt& next(NodeIt& i) const { marci@775: // this->graph->next(i.n); marci@775: // while (this->graph->valid(i) && !(*node_filter_map)[i.n]) { marci@775: // this->graph->next(i.n); } marci@775: // return i; marci@775: // } marci@775: // OutEdgeIt& next(OutEdgeIt& i) const { marci@775: // this->graph->next(i.e); marci@775: // while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { marci@775: // this->graph->next(i.e); } marci@775: // return i; marci@775: // } marci@775: // InEdgeIt& next(InEdgeIt& i) const { marci@775: // this->graph->next(i.e); marci@775: // while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { marci@775: // this->graph->next(i.e); } marci@775: // return i; marci@775: // } marci@775: // EdgeIt& next(EdgeIt& i) const { marci@775: // this->graph->next(i.e); marci@775: // while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { marci@775: // this->graph->next(i.e); } marci@775: // return i; marci@775: // } marci@556: marci@775: // Node aNode(const OutEdgeIt& e) const { marci@775: // return Node(this->graph->aNode(e.e)); } marci@775: // Node aNode(const InEdgeIt& e) const { marci@775: // return Node(this->graph->aNode(e.e)); } marci@775: // Node bNode(const OutEdgeIt& e) const { marci@775: // return Node(this->graph->bNode(e.e)); } marci@775: // Node bNode(const InEdgeIt& e) const { marci@775: // 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: marci@792: /// \warning This is a linear time operation and works only if marci@792: /// \c Graph::NodeIt is defined. marci@593: int nodeNum() const { marci@593: int i=0; marci@792: for (NodeIt n(*this); n!=INVALID; ++n) ++i; marci@593: return i; marci@593: } marci@593: marci@792: /// \warning This is a linear time operation and works only if marci@792: /// \c Graph::EdgeIt is defined. marci@593: int edgeNum() const { marci@593: int i=0; marci@792: for (EdgeIt e(*this); e!=INVALID; ++e) ++i; marci@593: return i; marci@593: } marci@593: marci@556: }; marci@556: marci@569: marci@569: marci@838: // /// \brief A wrapper for forgetting the orientation of a graph. marci@838: // /// marci@838: // /// A wrapper for getting an undirected graph by forgetting marci@838: // /// the orientation of a directed one. marci@838: // /// marci@838: // /// \author Marton Makai marci@838: // /// does not work in the new concept. marci@556: template marci@556: class UndirGraphWrapper : public GraphWrapper { marci@650: public: marci@650: typedef GraphWrapper Parent; 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@650: marci@650: ///\brief A wrapper for composing a subgraph of a marci@792: /// bidirected graph made from a directed one. marci@612: /// marci@792: /// Suppose that for a directed graph $G=(V, A)$, marci@792: /// two predicates on the edge-set, $forward_filter$, and $backward_filter$ marci@792: /// is given, and we are dealing with the directed graph marci@792: /// a $G'=(V, \{uv : uv\in A \mbox{ and } forward_filter(uv) \mbox{ is true}\}+\{vu : uv\in A \mbox{ and } backward_filter(uv) \mbox{ is true}\})$. marci@792: /// The purpose of writing + instead of union is because parallel marci@792: /// edges can arose. marci@792: /// In other words, a subgraph of the bidirected graph obtained, which marci@792: /// is given by orienting the edges of the original graph in both directions. marci@792: /// An example for such a construction is the \c RevGraphWrapper where the marci@792: /// forward_filter is everywhere false and the backward_filter is marci@792: /// everywhere true. We note that for sake of efficiency, marci@792: /// \c RevGraphWrapper is implemented in a different way. marci@792: /// But BidirGraphWrapper is obtained from marci@792: /// SubBidirGraphWrapper by considering everywhere true marci@792: /// predicates both forward_filter and backward_filter. marci@792: /// Finally, one of the most important applications of SubBidirGraphWrapper marci@792: /// is ResGraphWrapper, which stands for the residual graph in directed marci@792: /// flow and circulation problems. marci@792: /// As wrappers usually, the SubBidirGraphWrapper implements the marci@792: /// above mentioned graph structure without its physical storage, marci@792: /// that is the whole stuff eats constant memory. marci@792: /// As the oppositely directed edges are logical different, marci@792: /// the maps are able to attach different values for them. marci@650: template marci@650: class SubBidirGraphWrapper : public GraphWrapper { marci@650: public: marci@650: typedef GraphWrapper Parent; marci@569: protected: marci@650: ForwardFilterMap* forward_filter; marci@650: BackwardFilterMap* backward_filter; marci@650: marci@792: SubBidirGraphWrapper() : GraphWrapper() { } marci@650: void setForwardFilterMap(ForwardFilterMap& _forward_filter) { marci@650: forward_filter=&_forward_filter; marci@650: } marci@650: void setBackwardFilterMap(BackwardFilterMap& _backward_filter) { marci@650: backward_filter=&_backward_filter; marci@650: } marci@569: marci@569: public: marci@569: marci@650: SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter, marci@650: BackwardFilterMap& _backward_filter) : marci@650: GraphWrapper(_graph), marci@650: forward_filter(&_forward_filter), backward_filter(&_backward_filter) { } alpar@774: SubBidirGraphWrapper(const SubBidirGraphWrapper& gw) : alpar@774: Parent(gw), alpar@774: forward_filter(gw.forward_filter), alpar@774: backward_filter(gw.backward_filter) { } 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 EdgeMap; marci@621: marci@569: typedef typename GraphWrapper::Node Node; marci@621: alpar@774: typedef typename Graph::Edge GraphEdge; marci@792: /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from marci@792: /// Graph::Edge. It contains an extra bool flag which shows if the marci@792: /// edge is the backward version of the original edge. marci@569: class Edge : public Graph::Edge { marci@650: friend class SubBidirGraphWrapper; marci@621: template friend class EdgeMap; marci@569: protected: marci@569: bool backward; //true, iff backward marci@569: public: marci@569: Edge() { } marci@792: /// \todo =false is needed, or causes problems? marci@792: /// If \c _backward is false, then we get an edge corresponding to the marci@792: /// original one, otherwise its oppositely directed pair is obtained. alpar@774: Edge(const typename Graph::Edge& e, bool _backward/*=false*/) : alpar@774: Graph::Edge(e), backward(_backward) { } alpar@774: Edge(Invalid i) : Graph::Edge(i), backward(true) { } marci@569: //the unique invalid iterator alpar@774: // friend bool operator==(const Edge& u, const Edge& v) { alpar@774: // return (u.backward==v.backward && alpar@774: // static_cast(u)== alpar@774: // static_cast(v)); alpar@774: // } alpar@774: // friend bool operator!=(const Edge& u, const Edge& v) { alpar@774: // return (u.backward!=v.backward || alpar@774: // static_cast(u)!= alpar@774: // static_cast(v)); alpar@774: // } alpar@774: bool operator==(const Edge& v) const { alpar@774: return (this->backward==v.backward && alpar@774: static_cast(*this)== marci@569: static_cast(v)); marci@569: } alpar@774: bool operator!=(const Edge& v) const { alpar@774: return (this->backward!=v.backward || alpar@774: static_cast(*this)!= marci@569: static_cast(v)); alpar@774: } marci@569: }; marci@569: alpar@774: class OutEdgeIt : public Edge { marci@650: friend class SubBidirGraphWrapper; marci@569: protected: alpar@774: const SubBidirGraphWrapper* gw; marci@569: public: marci@569: OutEdgeIt() { } alpar@774: OutEdgeIt(Invalid i) : Edge(i) { } marci@569: //the unique invalid iterator marci@650: OutEdgeIt(const SubBidirGraphWrapper& _gw, const Node& n) : alpar@774: Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) { alpar@774: while (*static_cast(this)!=INVALID && alpar@774: !(*(gw->forward_filter))[*this]) alpar@774: *(static_cast(this))= alpar@774: ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); marci@775: if (*static_cast(this)==INVALID) { alpar@774: *static_cast(this)= alpar@774: Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true); marci@775: while (*static_cast(this)!=INVALID && marci@775: !(*(gw->backward_filter))[*this]) marci@775: *(static_cast(this))= marci@775: ++(typename Graph::InEdgeIt(*(gw->graph), *this)); marci@775: } alpar@774: } alpar@774: OutEdgeIt(const SubBidirGraphWrapper& _gw, const Edge& e) : alpar@774: Edge(e), gw(&_gw) { } alpar@774: OutEdgeIt& operator++() { alpar@774: if (!this->backward) { alpar@774: Node n=gw->tail(*this); alpar@774: *(static_cast(this))= alpar@774: ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); alpar@774: while (*static_cast(this)!=INVALID && alpar@774: !(*(gw->forward_filter))[*this]) alpar@774: *(static_cast(this))= alpar@774: ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); marci@775: if (*static_cast(this)==INVALID) { alpar@774: *static_cast(this)= alpar@774: Edge(typename Graph::InEdgeIt(*(gw->graph), n), true); marci@775: while (*static_cast(this)!=INVALID && marci@775: !(*(gw->backward_filter))[*this]) marci@775: *(static_cast(this))= marci@775: ++(typename Graph::InEdgeIt(*(gw->graph), *this)); marci@775: } alpar@774: } else { alpar@774: *(static_cast(this))= alpar@774: ++(typename Graph::InEdgeIt(*(gw->graph), *this)); alpar@774: while (*static_cast(this)!=INVALID && alpar@774: !(*(gw->backward_filter))[*this]) alpar@774: *(static_cast(this))= alpar@774: ++(typename Graph::InEdgeIt(*(gw->graph), *this)); marci@569: } alpar@774: return *this; marci@569: } marci@569: }; marci@569: alpar@774: class InEdgeIt : public Edge { marci@650: friend class SubBidirGraphWrapper; marci@569: protected: alpar@774: const SubBidirGraphWrapper* gw; marci@569: public: marci@569: InEdgeIt() { } alpar@774: InEdgeIt(Invalid i) : Edge(i) { } marci@569: //the unique invalid iterator marci@650: InEdgeIt(const SubBidirGraphWrapper& _gw, const Node& n) : alpar@774: Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) { alpar@774: while (*static_cast(this)!=INVALID && alpar@774: !(*(gw->forward_filter))[*this]) alpar@774: *(static_cast(this))= alpar@774: ++(typename Graph::InEdgeIt(*(gw->graph), *this)); marci@775: if (*static_cast(this)==INVALID) { alpar@774: *static_cast(this)= alpar@774: Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true); marci@775: while (*static_cast(this)!=INVALID && marci@775: !(*(gw->backward_filter))[*this]) marci@775: *(static_cast(this))= marci@775: ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); marci@775: } alpar@774: } alpar@774: InEdgeIt(const SubBidirGraphWrapper& _gw, const Edge& e) : alpar@774: Edge(e), gw(&_gw) { } alpar@774: InEdgeIt& operator++() { alpar@774: if (!this->backward) { marci@775: Node n=gw->tail(*this); alpar@774: *(static_cast(this))= alpar@774: ++(typename Graph::InEdgeIt(*(gw->graph), *this)); alpar@774: while (*static_cast(this)!=INVALID && alpar@774: !(*(gw->forward_filter))[*this]) alpar@774: *(static_cast(this))= alpar@774: ++(typename Graph::InEdgeIt(*(gw->graph), *this)); marci@775: if (*static_cast(this)==INVALID) { alpar@774: *static_cast(this)= alpar@774: Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true); marci@775: while (*static_cast(this)!=INVALID && marci@775: !(*(gw->backward_filter))[*this]) marci@775: *(static_cast(this))= marci@775: ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); marci@775: } alpar@774: } else { alpar@774: *(static_cast(this))= alpar@774: ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); alpar@774: while (*static_cast(this)!=INVALID && alpar@774: !(*(gw->backward_filter))[*this]) alpar@774: *(static_cast(this))= alpar@774: ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); marci@569: } alpar@774: return *this; marci@569: } marci@569: }; marci@569: alpar@774: class EdgeIt : public Edge { marci@650: friend class SubBidirGraphWrapper; marci@569: protected: alpar@774: const SubBidirGraphWrapper* gw; marci@569: public: marci@569: EdgeIt() { } alpar@774: EdgeIt(Invalid i) : Edge(i) { } alpar@774: //the unique invalid iterator marci@650: EdgeIt(const SubBidirGraphWrapper& _gw) : marci@775: Edge(typename Graph::OutEdgeIt(*(_gw.graph)), false), gw(&_gw) { alpar@774: while (*static_cast(this)!=INVALID && alpar@774: !(*(gw->forward_filter))[*this]) alpar@774: *(static_cast(this))= alpar@774: ++(typename Graph::EdgeIt(*(gw->graph), *this)); marci@775: if (*static_cast(this)==INVALID) { alpar@774: *static_cast(this)= alpar@774: Edge(typename Graph::EdgeIt(*(_gw.graph)), true); marci@775: while (*static_cast(this)!=INVALID && marci@775: !(*(gw->backward_filter))[*this]) marci@775: *(static_cast(this))= marci@775: ++(typename Graph::EdgeIt(*(gw->graph), *this)); marci@775: } alpar@774: } alpar@774: EdgeIt(const SubBidirGraphWrapper& _gw, const Edge& e) : alpar@774: Edge(e), gw(&_gw) { } alpar@774: EdgeIt& operator++() { alpar@774: if (!this->backward) { alpar@774: *(static_cast(this))= alpar@774: ++(typename Graph::EdgeIt(*(gw->graph), *this)); alpar@774: while (*static_cast(this)!=INVALID && alpar@774: !(*(gw->forward_filter))[*this]) alpar@774: *(static_cast(this))= alpar@774: ++(typename Graph::EdgeIt(*(gw->graph), *this)); marci@775: if (*static_cast(this)==INVALID) { alpar@774: *static_cast(this)= alpar@774: Edge(typename Graph::EdgeIt(*(gw->graph)), true); marci@775: while (*static_cast(this)!=INVALID && marci@775: !(*(gw->backward_filter))[*this]) marci@775: *(static_cast(this))= marci@775: ++(typename Graph::EdgeIt(*(gw->graph), *this)); marci@775: } alpar@774: } else { alpar@774: *(static_cast(this))= alpar@774: ++(typename Graph::EdgeIt(*(gw->graph), *this)); alpar@774: while (*static_cast(this)!=INVALID && alpar@774: !(*(gw->backward_filter))[*this]) alpar@774: *(static_cast(this))= alpar@774: ++(typename Graph::EdgeIt(*(gw->graph), *this)); marci@569: } alpar@774: return *this; 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: 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: alpar@774: // using GraphWrapper::next; alpar@774: // // NodeIt& next(NodeIt& n) const { GraphWrapper::next(n); return n; } alpar@774: // OutEdgeIt& next(OutEdgeIt& e) const { alpar@774: // if (!e.backward) { alpar@774: // Node v=this->graph->aNode(e.out); alpar@774: // this->graph->next(e.out); alpar@774: // while(this->graph->valid(e.out) && !(*forward_filter)[e]) { alpar@774: // this->graph->next(e.out); } alpar@774: // if (!this->graph->valid(e.out)) { alpar@774: // e.backward=true; alpar@774: // this->graph->first(e.in, v); alpar@774: // while(this->graph->valid(e.in) && !(*backward_filter)[e]) { alpar@774: // this->graph->next(e.in); } alpar@774: // } alpar@774: // } else { alpar@774: // this->graph->next(e.in); alpar@774: // while(this->graph->valid(e.in) && !(*backward_filter)[e]) { alpar@774: // this->graph->next(e.in); } alpar@774: // } alpar@774: // return e; alpar@774: // } alpar@774: // // FIXME Not tested alpar@774: // InEdgeIt& next(InEdgeIt& e) const { alpar@774: // if (!e.backward) { alpar@774: // Node v=this->graph->aNode(e.in); alpar@774: // this->graph->next(e.in); alpar@774: // while(this->graph->valid(e.in) && !(*forward_filter)[e]) { alpar@774: // this->graph->next(e.in); } alpar@774: // if (!this->graph->valid(e.in)) { alpar@774: // e.backward=true; alpar@774: // this->graph->first(e.out, v); alpar@774: // while(this->graph->valid(e.out) && !(*backward_filter)[e]) { alpar@774: // this->graph->next(e.out); } alpar@774: // } alpar@774: // } else { alpar@774: // this->graph->next(e.out); alpar@774: // while(this->graph->valid(e.out) && !(*backward_filter)[e]) { alpar@774: // this->graph->next(e.out); } alpar@774: // } alpar@774: // return e; alpar@774: // } alpar@774: // EdgeIt& next(EdgeIt& e) const { alpar@774: // if (!e.backward) { alpar@774: // this->graph->next(e.e); alpar@774: // while(this->graph->valid(e.e) && !(*forward_filter)[e]) { alpar@774: // this->graph->next(e.e); } alpar@774: // if (!this->graph->valid(e.e)) { alpar@774: // e.backward=true; alpar@774: // this->graph->first(e.e); alpar@774: // while(this->graph->valid(e.e) && !(*backward_filter)[e]) { alpar@774: // this->graph->next(e.e); } alpar@774: // } alpar@774: // } else { alpar@774: // this->graph->next(e.e); alpar@774: // while(this->graph->valid(e.e) && !(*backward_filter)[e]) { alpar@774: // this->graph->next(e.e); } alpar@774: // } alpar@774: // return e; alpar@774: // } 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: alpar@774: // Node aNode(OutEdgeIt e) const { alpar@774: // return ((!e.backward) ? this->graph->aNode(e.out) : alpar@774: // this->graph->aNode(e.in)); } alpar@774: // Node bNode(OutEdgeIt e) const { alpar@774: // return ((!e.backward) ? this->graph->bNode(e.out) : alpar@774: // this->graph->bNode(e.in)); } marci@569: alpar@774: // Node aNode(InEdgeIt e) const { alpar@774: // return ((!e.backward) ? this->graph->aNode(e.in) : alpar@774: // this->graph->aNode(e.out)); } alpar@774: // Node bNode(InEdgeIt e) const { alpar@774: // return ((!e.backward) ? this->graph->bNode(e.in) : alpar@774: // 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@792: /// \warning This is a linear time operation and works only if marci@792: /// \c Graph::EdgeIt is defined. marci@792: int edgeNum() const { marci@792: int i=0; marci@792: for (EdgeIt e(*this); e!=INVALID; ++e) ++i; marci@792: return i; marci@792: } 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: marci@569: template marci@792: /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two marci@792: /// Graph::EdgeMap one for the forward edges and marci@792: /// one for the backward edges. 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@650: EdgeMap(const SubBidirGraphWrapper& g) : alpar@774: forward_map(*(g.graph)), backward_map(*(g.graph)) { } marci@650: EdgeMap(const SubBidirGraphWrapper& g, T a) : alpar@774: forward_map(*(g.graph), a), backward_map(*(g.graph), a) { } marci@569: void set(Edge e, T a) { marci@569: if (!e.backward) marci@792: forward_map.set(e, a); marci@569: else marci@792: backward_map.set(e, a); marci@569: } marci@569: T operator[](Edge e) const { marci@569: if (!e.backward) marci@792: return forward_map[e]; marci@569: else marci@792: return backward_map[e]; 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@650: marci@650: ///\brief A wrapper for composing bidirected graph from a directed one. marci@650: /// marci@650: /// A wrapper for composing bidirected graph from a directed one. marci@650: /// A bidirected graph is composed over the directed one without physical marci@650: /// storage. As the oppositely directed edges are logically different ones marci@650: /// the maps are able to attach different values for them. marci@650: template marci@650: class BidirGraphWrapper : marci@650: public SubBidirGraphWrapper< marci@650: Graph, marci@650: ConstMap, marci@650: ConstMap > { marci@650: public: marci@650: typedef SubBidirGraphWrapper< marci@650: Graph, marci@650: ConstMap, marci@650: ConstMap > Parent; marci@650: protected: marci@650: ConstMap cm; marci@650: marci@655: BidirGraphWrapper() : Parent(), cm(true) { marci@655: Parent::setForwardFilterMap(cm); marci@655: Parent::setBackwardFilterMap(cm); marci@655: } marci@650: public: marci@650: BidirGraphWrapper(Graph& _graph) : Parent() { marci@650: Parent::setGraph(_graph); marci@650: Parent::setForwardFilterMap(cm); marci@650: Parent::setBackwardFilterMap(cm); marci@650: } marci@738: marci@738: int edgeNum() const { marci@738: return 2*this->graph->edgeNum(); marci@738: } marci@650: }; marci@650: marci@650: 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@650: public: 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@650: marci@650: template marci@658: class ResForwardFilter { marci@658: // const Graph* graph; marci@650: const CapacityMap* capacity; marci@650: const FlowMap* flow; marci@650: public: marci@658: ResForwardFilter(/*const Graph& _graph, */ marci@658: const CapacityMap& _capacity, const FlowMap& _flow) : marci@658: /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { } marci@658: ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { } marci@658: //void setGraph(const Graph& _graph) { graph=&_graph; } marci@656: void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; } marci@656: void setFlow(const FlowMap& _flow) { flow=&_flow; } marci@650: bool operator[](const typename Graph::Edge& e) const { marci@738: return (Number((*flow)[e]) < Number((*capacity)[e])); marci@650: } marci@650: }; marci@650: marci@650: template marci@658: class ResBackwardFilter { marci@658: //const Graph* graph; marci@650: const CapacityMap* capacity; marci@650: const FlowMap* flow; marci@650: public: marci@658: ResBackwardFilter(/*const Graph& _graph,*/ marci@658: const CapacityMap& _capacity, const FlowMap& _flow) : marci@658: /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { } marci@658: ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { } marci@658: //void setGraph(const Graph& _graph) { graph=&_graph; } marci@656: void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; } marci@656: void setFlow(const FlowMap& _flow) { flow=&_flow; } marci@650: bool operator[](const typename Graph::Edge& e) const { marci@738: return (Number(0) < Number((*flow)[e])); marci@650: } marci@650: }; marci@650: marci@653: marci@653: /// A wrapper for composing the residual graph for directed flow and circulation problems. marci@650: marci@653: /// A wrapper for composing the residual graph for directed flow and circulation problems. marci@650: template marci@653: class ResGraphWrapper : marci@650: public SubBidirGraphWrapper< marci@650: Graph, marci@658: ResForwardFilter, marci@658: ResBackwardFilter > { marci@650: public: marci@650: typedef SubBidirGraphWrapper< marci@650: Graph, marci@658: ResForwardFilter, marci@658: ResBackwardFilter > Parent; marci@650: protected: marci@650: const CapacityMap* capacity; marci@650: FlowMap* flow; marci@658: ResForwardFilter forward_filter; marci@658: ResBackwardFilter backward_filter; marci@658: ResGraphWrapper() : Parent(), marci@658: capacity(0), flow(0) { } marci@658: void setCapacityMap(const CapacityMap& _capacity) { marci@658: capacity=&_capacity; marci@658: forward_filter.setCapacity(_capacity); marci@658: backward_filter.setCapacity(_capacity); marci@658: } marci@658: void setFlowMap(FlowMap& _flow) { marci@658: flow=&_flow; marci@658: forward_filter.setFlow(_flow); marci@658: backward_filter.setFlow(_flow); marci@658: } marci@658: // /// \bug does graph reference needed in filtermaps?? marci@658: // void setGraph(const Graph& _graph) { marci@658: // Parent::setGraph(_graph); marci@658: // forward_filter.setGraph(_graph); marci@658: // backward_filter.setGraph(_graph); marci@656: // } marci@650: public: marci@653: ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, marci@650: FlowMap& _flow) : marci@650: Parent(), capacity(&_capacity), flow(&_flow), marci@658: forward_filter(/*_graph,*/ _capacity, _flow), marci@658: backward_filter(/*_graph,*/ _capacity, _flow) { marci@650: Parent::setGraph(_graph); marci@650: Parent::setForwardFilterMap(forward_filter); marci@650: Parent::setBackwardFilterMap(backward_filter); marci@650: } marci@650: marci@660: typedef typename Parent::Edge Edge; marci@660: marci@650: // bool forward(const Parent::Edge& e) const { return Parent::forward(e); } marci@650: //bool backward(const Edge& e) const { return e.backward; } marci@650: marci@660: void augment(const Edge& e, Number a) const { marci@650: if (Parent::forward(e)) marci@650: // flow->set(e.out, flow->get(e.out)+a); marci@650: flow->set(e, (*flow)[e]+a); marci@650: else marci@650: //flow->set(e.in, flow->get(e.in)-a); marci@650: flow->set(e, (*flow)[e]-a); marci@650: } marci@650: marci@660: /// \deprecated marci@660: /// marci@660: Number resCap(const Edge& e) const { marci@650: if (Parent::forward(e)) marci@650: // return (capacity->get(e.out)-flow->get(e.out)); marci@650: return ((*capacity)[e]-(*flow)[e]); marci@650: else marci@650: // return (flow->get(e.in)); marci@650: return ((*flow)[e]); marci@650: } marci@650: marci@660: /// \brief Residual capacity map. marci@660: /// marci@792: /// In generic residual graphs the residual capacity can be obtained as a map. Not tested. marci@660: class ResCap { marci@660: protected: marci@660: const ResGraphWrapper* res_graph; marci@660: public: marci@660: typedef Number ValueType; marci@660: typedef Edge KeyType; marci@660: ResCap(const ResGraphWrapper& _res_graph) : marci@660: res_graph(&_res_graph) { } marci@660: Number operator[](const Edge& e) const { marci@660: if (res_graph->forward(e)) marci@660: // return (capacity->get(e.out)-flow->get(e.out)); marci@660: return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e]; marci@660: else marci@660: // return (flow->get(e.in)); marci@660: return (*(res_graph->flow))[e]; marci@660: } marci@660: /// \bug not needed with dynamic maps, or does it? marci@660: void update() { } marci@660: }; marci@660: marci@650: }; marci@650: marci@650: marci@612: /// For blocking flows. marci@556: marci@792: /// This graph wrapper is used for on-the-fly marci@792: /// 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@792: /// \author Marton Makai marci@556: template marci@556: class ErasingFirstGraphWrapper : public GraphWrapper { marci@650: public: marci@650: typedef GraphWrapper Parent; 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: typedef typename GraphWrapper::Edge Edge; marci@777: class OutEdgeIt : public Edge { marci@556: friend class GraphWrapper; marci@556: friend class ErasingFirstGraphWrapper; marci@777: const ErasingFirstGraphWrapper* gw; marci@556: public: marci@556: OutEdgeIt() { } marci@777: //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { } marci@777: OutEdgeIt(Invalid i) : Edge(i) { } marci@777: OutEdgeIt(const ErasingFirstGraphWrapper& _gw, marci@777: const Node& n) : marci@777: Edge((*(_gw.first_out_edges))[n]), gw(&_gw) { } marci@777: OutEdgeIt(const ErasingFirstGraphWrapper& _gw, marci@777: const Edge& e) : marci@777: Edge(e), gw(&_gw) { } marci@777: OutEdgeIt& operator++() { marci@777: *(static_cast(this))= marci@777: ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); marci@777: return *this; marci@777: } marci@556: }; marci@777: // class InEdgeIt { marci@777: // friend class GraphWrapper; marci@777: // friend class ErasingFirstGraphWrapper; marci@777: // // typedef typename Graph::InEdgeIt GraphInEdgeIt; marci@777: // typename Graph::InEdgeIt e; marci@777: // public: marci@777: // InEdgeIt() { } marci@777: // InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } marci@777: // InEdgeIt(const Invalid& i) : e(i) { } marci@777: // InEdgeIt(const ErasingFirstGraphWrapper& _G, marci@777: // const Node& _n) : marci@777: // e(*(_G.graph), typename Graph::Node(_n)) { } marci@777: // operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@777: // }; marci@556: //typedef typename Graph::SymEdgeIt SymEdgeIt; marci@777: // class EdgeIt { marci@777: // friend class GraphWrapper; marci@777: // friend class ErasingFirstGraphWrapper; marci@777: // // typedef typename Graph::EdgeIt GraphEdgeIt; marci@777: // typename Graph::EdgeIt e; marci@777: // public: marci@777: // EdgeIt() { } marci@777: // EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } marci@777: // EdgeIt(const Invalid& i) : e(i) { } marci@777: // EdgeIt(const ErasingFirstGraphWrapper& _G) : marci@777: // e(*(_G.graph)) { } marci@777: // operator Edge() const { return Edge(typename Graph::Edge(e)); } marci@777: // }; 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@777: // InEdgeIt& first(InEdgeIt& i, const Node& p) const { marci@777: // i=InEdgeIt(*this, p); return i; marci@777: // } marci@777: // EdgeIt& first(EdgeIt& i) const { marci@777: // i=EdgeIt(*this); return i; marci@777: // } marci@556: marci@777: // using GraphWrapper::next; marci@777: // // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } marci@777: // OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; } marci@777: // InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } marci@777: // EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; } marci@556: marci@777: // Node aNode(const OutEdgeIt& e) const { marci@777: // return Node(this->graph->aNode(e.e)); } marci@777: // Node aNode(const InEdgeIt& e) const { marci@777: // return Node(this->graph->aNode(e.e)); } marci@777: // Node bNode(const OutEdgeIt& e) const { marci@777: // return Node(this->graph->bNode(e.e)); } marci@777: // Node bNode(const InEdgeIt& e) const { marci@777: // return Node(this->graph->bNode(e.e)); } marci@556: marci@777: void erase(const Edge& e) const { marci@777: Node n=tail(e); deba@844: typename Graph::OutEdgeIt f(*Parent::graph, n); marci@777: ++f; marci@777: first_out_edges->set(n, f); 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: