marci@281: // -*- c++ -*- alpar@921: #ifndef LEMON_GRAPH_WRAPPER_H alpar@921: #define LEMON_GRAPH_WRAPPER_H marci@281: marci@281: #include marci@281: alpar@921: namespace lemon { marci@281: marci@281: template marci@281: class TrivGraphWrapper { marci@281: protected: marci@281: Graph* graph; marci@281: marci@281: public: marci@281: typedef Graph BaseGraph; marci@281: marci@298: // TrivGraphWrapper() : graph(0) { } marci@298: TrivGraphWrapper(Graph& _graph) : graph(&_graph) { } marci@298: // void setGraph(Graph& _graph) { graph = &_graph; } marci@298: // Graph& getGraph() const { return *graph; } marci@298: marci@281: typedef typename Graph::Node Node; marci@281: class NodeIt : public Graph::NodeIt { marci@281: public: marci@281: NodeIt() { } marci@281: NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } marci@281: NodeIt(const Invalid& i) : Graph::NodeIt(i) { } marci@281: NodeIt(const TrivGraphWrapper& _G) : marci@281: Graph::NodeIt(*(_G.graph)) { } marci@281: }; marci@281: typedef typename Graph::Edge Edge; marci@281: class OutEdgeIt : public Graph::OutEdgeIt { marci@281: public: marci@281: OutEdgeIt() { } marci@281: OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } marci@281: OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } marci@281: OutEdgeIt(const TrivGraphWrapper& _G, const Node& n) : marci@281: Graph::OutEdgeIt(*(_G.graph), n) { } marci@281: }; marci@281: class InEdgeIt : public Graph::InEdgeIt { marci@281: public: marci@281: InEdgeIt() { } marci@281: InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } marci@281: InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } marci@281: InEdgeIt(const TrivGraphWrapper& _G, const Node& n) : marci@281: Graph::InEdgeIt(*(_G.graph), n) { } marci@281: }; marci@281: //typedef typename Graph::SymEdgeIt SymEdgeIt; marci@281: class EdgeIt : public Graph::EdgeIt { marci@281: public: marci@281: EdgeIt() { } marci@281: EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } marci@281: EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } marci@281: EdgeIt(const TrivGraphWrapper& _G) : marci@281: Graph::EdgeIt(*(_G.graph)) { } marci@281: }; marci@281: marci@281: NodeIt& first(NodeIt& i) const { marci@281: i=NodeIt(*this); marci@281: return i; marci@281: } marci@281: EdgeIt& first(EdgeIt& i) const { marci@281: i=EdgeIt(*this); marci@281: return i; marci@281: } marci@281: // template I& first(I& i) const { marci@281: // i=I(*this); marci@281: // return i; marci@281: // } marci@281: OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { marci@281: i=OutEdgeIt(*this, p); marci@281: return i; marci@281: } marci@281: InEdgeIt& first(InEdgeIt& i, const Node& p) const { marci@281: i=InEdgeIt(*this, p); marci@281: return i; marci@281: } marci@281: // template I& first(I& i, const P& p) const { marci@281: // i=I(*this, p); marci@281: // return i; marci@281: // } marci@281: marci@281: // template I getNext(const I& i) const { marci@281: // return graph->getNext(i); } marci@281: template I& next(I &i) const { graph->next(i); return i; } marci@281: marci@281: template< typename It > It first() const { marci@298: It e; this->first(e); return e; } marci@281: marci@281: template< typename It > It first(const Node& v) const { marci@298: It e; this->first(e, v); return e; } marci@281: alpar@986: Node target(const Edge& e) const { return graph->target(e); } alpar@986: Node source(const Edge& e) const { return graph->source(e); } marci@281: marci@298: template bool valid(const I& i) const { marci@298: return graph->valid(i); } marci@281: marci@281: //template void setInvalid(const I &i); marci@281: //{ return graph->setInvalid(i); } marci@281: marci@281: int nodeNum() const { return graph->nodeNum(); } marci@281: int edgeNum() const { return graph->edgeNum(); } marci@281: marci@281: template Node aNode(const I& e) const { marci@281: return graph->aNode(e); } marci@281: template Node bNode(const I& e) const { marci@281: return graph->bNode(e); } marci@281: marci@281: Node addNode() const { return graph->addNode(); } alpar@986: Edge addEdge(const Node& source, const Node& target) const { alpar@986: return graph->addEdge(source, target); } marci@281: marci@281: template void erase(const I& i) const { graph->erase(i); } marci@281: marci@281: void clear() const { graph->clear(); } marci@281: marci@281: template class NodeMap : public Graph::NodeMap { marci@281: public: marci@281: NodeMap(const TrivGraphWrapper& _G) : marci@281: Graph::NodeMap(*(_G.graph)) { } marci@281: NodeMap(const TrivGraphWrapper& _G, T a) : marci@281: Graph::NodeMap(*(_G.graph), a) { } marci@281: }; marci@281: marci@281: template class EdgeMap : public Graph::EdgeMap { marci@281: public: marci@281: EdgeMap(const TrivGraphWrapper& _G) : marci@281: Graph::EdgeMap(*(_G.graph)) { } marci@281: EdgeMap(const TrivGraphWrapper& _G, T a) : marci@281: Graph::EdgeMap(*(_G.graph), a) { } marci@281: }; marci@281: marci@281: template class NodeMapWrapper { marci@281: protected: marci@281: Map* map; marci@281: public: marci@281: NodeMapWrapper(Map& _map) : map(&_map) { } marci@281: void set(Node n, T a) { map->set(n, a); } marci@281: T get(Node n) const { return map->get(n); } marci@281: }; marci@281: marci@281: template class EdgeMapWrapper { marci@281: protected: marci@281: Map* map; marci@281: public: marci@281: EdgeMapWrapper(Map& _map) : map(&_map) { } marci@281: void set(Edge n, T a) { map->set(n, a); } marci@281: T get(Edge n) const { return map->get(n); } marci@281: }; marci@281: }; marci@281: marci@298: marci@298: template marci@298: class GraphWrapper { marci@281: protected: marci@298: Graph* graph; marci@281: marci@281: public: marci@298: typedef Graph BaseGraph; marci@281: marci@298: // GraphWrapper() : graph(0) { } marci@298: GraphWrapper(Graph& _graph) : graph(&_graph) { } marci@298: // void setGraph(Graph& _graph) { graph=&_graph; } marci@298: // Graph& getGraph() const { return *graph; } marci@298: marci@298: typedef typename Graph::Node Node; marci@298: class NodeIt : public Graph::NodeIt { marci@281: public: marci@281: NodeIt() { } marci@298: NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } marci@298: NodeIt(const Invalid& i) : Graph::NodeIt(i) { } marci@298: NodeIt(const GraphWrapper& _G) : marci@298: Graph::NodeIt(*(_G.graph)) { } marci@281: }; marci@298: typedef typename Graph::Edge Edge; marci@298: class OutEdgeIt : public Graph::OutEdgeIt { marci@281: public: marci@281: OutEdgeIt() { } marci@298: OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } marci@298: OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } marci@298: OutEdgeIt(const GraphWrapper& _G, const Node& n) : marci@298: Graph::OutEdgeIt(*(_G.graph), n) { } marci@281: }; marci@298: class InEdgeIt : public Graph::InEdgeIt { marci@281: public: marci@281: InEdgeIt() { } marci@298: InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } marci@298: InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } marci@298: InEdgeIt(const GraphWrapper& _G, const Node& n) : marci@298: Graph::InEdgeIt(*(_G.graph), n) { } marci@281: }; marci@298: //typedef typename Graph::SymEdgeIt SymEdgeIt; marci@298: class EdgeIt : public Graph::EdgeIt { marci@281: public: marci@281: EdgeIt() { } marci@298: EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } marci@298: EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } marci@298: EdgeIt(const GraphWrapper& _G) : marci@298: Graph::EdgeIt(*(_G.graph)) { } marci@281: }; marci@298: marci@298: NodeIt& first(NodeIt& i) const { marci@298: i=NodeIt(*this); marci@281: return i; marci@281: } marci@298: EdgeIt& first(EdgeIt& i) const { marci@298: i=EdgeIt(*this); marci@298: return i; marci@281: } marci@298: // template I& first(I& i) const { marci@298: // i=I(*this); marci@298: // return i; marci@298: // } marci@298: OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { marci@298: i=OutEdgeIt(*this, p); marci@298: return i; marci@298: } marci@298: InEdgeIt& first(InEdgeIt& i, const Node& p) const { marci@298: i=InEdgeIt(*this, p); marci@298: return i; marci@298: } marci@298: // template I& first(I& i, const P& p) const { marci@298: // i=I(*this, p); marci@298: // return i; marci@298: // } marci@281: marci@298: // template I getNext(const I& i) const { marci@298: // return gw.getNext(i); } marci@298: template I& next(I &i) const { graph->next(i); return i; } marci@281: marci@281: template< typename It > It first() const { marci@281: It e; this->first(e); return e; } marci@281: marci@281: template< typename It > It first(const Node& v) const { marci@281: It e; this->first(e, v); return e; } marci@281: alpar@986: Node target(const Edge& e) const { return graph->target(e); } alpar@986: Node source(const Edge& e) const { return graph->source(e); } marci@281: marci@298: template bool valid(const I& i) const { marci@298: return graph->valid(i); } marci@281: marci@281: //template void setInvalid(const I &i); marci@281: //{ return graph->setInvalid(i); } marci@281: marci@298: int nodeNum() const { return graph->nodeNum(); } marci@298: int edgeNum() const { return graph->edgeNum(); } marci@281: marci@298: template Node aNode(const I& e) const { marci@298: return graph->aNode(e); } marci@298: template Node bNode(const I& e) const { marci@298: return graph->bNode(e); } marci@281: marci@298: Node addNode() const { return graph->addNode(); } alpar@986: Edge addEdge(const Node& source, const Node& target) const { alpar@986: return graph->addEdge(source, target); } marci@281: marci@298: template void erase(const I& i) const { graph->erase(i); } marci@281: marci@298: void clear() const { graph->clear(); } marci@281: marci@298: template class NodeMap : public Graph::NodeMap { marci@281: public: marci@298: NodeMap(const GraphWrapper& _G) : marci@298: Graph::NodeMap(*(_G.graph)) { } marci@298: NodeMap(const GraphWrapper& _G, T a) : marci@298: Graph::NodeMap(*(_G.graph), a) { } marci@281: }; marci@281: marci@298: template class EdgeMap : public Graph::EdgeMap { marci@281: public: marci@298: EdgeMap(const GraphWrapper& _G) : marci@298: Graph::EdgeMap(*(_G.graph)) { } marci@298: EdgeMap(const GraphWrapper& _G, T a) : marci@298: Graph::EdgeMap(*(_G.graph), a) { } marci@281: }; marci@281: }; marci@281: marci@281: marci@281: // template marci@281: // class RevGraphWrapper marci@281: // { marci@281: // protected: marci@281: // Graph* graph; marci@281: marci@281: // public: marci@281: // typedef Graph BaseGraph; marci@281: marci@281: // typedef typename Graph::Node Node; marci@281: // typedef typename Graph::NodeIt NodeIt; marci@281: marci@281: // typedef typename Graph::Edge Edge; marci@281: // typedef typename Graph::OutEdgeIt InEdgeIt; marci@281: // typedef typename Graph::InEdgeIt OutEdgeIt; marci@281: // //typedef typename Graph::SymEdgeIt SymEdgeIt; marci@281: // typedef typename Graph::EdgeIt EdgeIt; marci@281: marci@281: // //RevGraphWrapper() : graph(0) { } marci@281: // RevGraphWrapper(Graph& _graph) : graph(&_graph) { } marci@281: marci@281: // void setGraph(Graph& _graph) { graph = &_graph; } marci@281: // Graph& getGraph() const { return (*graph); } marci@281: marci@281: // template I& first(I& i) const { return graph->first(i); } marci@281: // template I& first(I& i, const P& p) const { marci@281: // return graph->first(i, p); } marci@281: marci@281: // template I getNext(const I& i) const { marci@281: // return graph->getNext(i); } marci@281: // template I& next(I &i) const { return graph->next(i); } marci@281: marci@281: // template< typename It > It first() const { marci@281: // It e; first(e); return e; } marci@281: marci@281: // template< typename It > It first(const Node& v) const { marci@281: // It e; first(e, v); return e; } marci@281: alpar@986: // Node target(const Edge& e) const { return graph->source(e); } alpar@986: // Node source(const Edge& e) const { return graph->target(e); } marci@281: marci@281: // template bool valid(const I& i) const marci@281: // { return graph->valid(i); } marci@281: marci@281: // //template void setInvalid(const I &i); marci@281: // //{ return graph->setInvalid(i); } marci@281: marci@281: // template Node aNode(const I& e) const { marci@281: // return graph->aNode(e); } marci@281: // template Node bNode(const I& e) const { marci@281: // return graph->bNode(e); } marci@281: marci@281: // Node addNode() const { return graph->addNode(); } alpar@986: // Edge addEdge(const Node& source, const Node& target) const { alpar@986: // return graph->addEdge(source, target); } marci@281: marci@281: // int nodeNum() const { return graph->nodeNum(); } marci@281: // int edgeNum() const { return graph->edgeNum(); } marci@281: marci@281: // template void erase(const I& i) const { graph->erase(i); } marci@281: marci@281: // void clear() const { graph->clear(); } marci@281: marci@281: // template class NodeMap : public Graph::NodeMap { marci@281: // public: marci@281: // NodeMap(const RevGraphWrapper& _G) : marci@281: // Graph::NodeMap(_G.getGraph()) { } marci@281: // NodeMap(const RevGraphWrapper& _G, T a) : marci@281: // Graph::NodeMap(_G.getGraph(), a) { } marci@281: // }; marci@281: marci@281: // template class EdgeMap : public Graph::EdgeMap { marci@281: // public: marci@281: // EdgeMap(const RevGraphWrapper& _G) : marci@281: // Graph::EdgeMap(_G.getGraph()) { } marci@281: // EdgeMap(const RevGraphWrapper& _G, T a) : marci@281: // Graph::EdgeMap(_G.getGraph(), a) { } marci@281: // }; marci@281: // }; marci@281: marci@281: marci@298: template marci@298: class RevGraphWrapper : public GraphWrapper { marci@281: public: marci@298: typedef typename GraphWrapper::Node Node; marci@298: typedef typename GraphWrapper::Edge Edge; marci@281: //FIXME marci@298: //If Graph::OutEdgeIt is not defined marci@281: //and we do not want to use RevGraphWrapper::InEdgeIt, marci@281: //this won't work, because of typedef marci@281: //OR marci@281: //graphs have to define their non-existing iterators to void marci@281: //Unfortunately all the typedefs are instantiated in templates, marci@281: //unlike other stuff marci@298: typedef typename GraphWrapper::OutEdgeIt InEdgeIt; marci@298: typedef typename GraphWrapper::InEdgeIt OutEdgeIt; marci@281: marci@298: // RevGraphWrapper() : GraphWrapper() { } marci@298: RevGraphWrapper(Graph& _graph) : GraphWrapper(_graph) { } marci@281: alpar@986: Node target(const Edge& e) const alpar@986: { return GraphWrapper::source(e); } alpar@986: Node source(const Edge& e) const alpar@986: { return GraphWrapper::target(e); } marci@281: }; marci@281: marci@281: //Subgraph on the same node-set and partial edge-set marci@298: template marci@298: class SubGraphWrapper : public GraphWrapper { marci@281: protected: marci@281: EdgeFilterMap* filter_map; marci@281: public: marci@298: typedef typename GraphWrapper::Node Node; marci@298: typedef typename GraphWrapper::NodeIt NodeIt; marci@298: typedef typename GraphWrapper::Edge Edge; marci@298: typedef typename GraphWrapper::EdgeIt EdgeIt; marci@298: typedef typename GraphWrapper::InEdgeIt InEdgeIt; marci@298: typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; marci@281: marci@298: // SubGraphWrapper() : GraphWrapper(), filter_map(0) { } marci@298: SubGraphWrapper(Graph& _graph, EdgeFilterMap& _filter_map) : marci@298: GraphWrapper(_graph), filter_map(&_filter_map) { } marci@281: marci@281: template I& first(I& i) const { marci@298: graph->first(i); marci@298: while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } marci@281: return i; marci@281: } marci@281: template I& first(I& i, const P& p) const { marci@298: graph->first(i, p); marci@298: while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } marci@281: return i; marci@281: } marci@281: marci@281: //template I getNext(const I& i) const { marci@281: // return gw.getNext(i); marci@281: //} marci@281: template I& next(I &i) const { marci@298: graph->next(i); marci@298: while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } marci@281: return i; marci@281: } marci@281: marci@281: template< typename It > It first() const { marci@281: It e; this->first(e); return e; } marci@281: marci@281: template< typename It > It first(const Node& v) const { marci@281: It e; this->first(e, v); return e; } marci@281: }; marci@281: marci@281: // template marci@281: // class UndirGraphWrapper { marci@281: // protected: marci@281: // //Graph* graph; marci@281: // GraphWrapper gw; marci@281: marci@281: // public: marci@281: // typedef GraphWrapper BaseGraph; marci@281: marci@281: // typedef typename GraphWrapper::Node Node; marci@281: // typedef typename GraphWrapper::NodeIt NodeIt; marci@281: marci@281: // //typedef typename Graph::Edge Edge; marci@281: // //typedef typename Graph::OutEdgeIt OutEdgeIt; marci@281: // //typedef typename Graph::InEdgeIt InEdgeIt; marci@281: // //typedef typename Graph::SymEdgeIt SymEdgeIt; marci@281: // //typedef typename Graph::EdgeIt EdgeIt; marci@281: marci@281: // //private: marci@281: // typedef typename GraphWrapper::Edge GraphEdge; marci@281: // typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt; marci@281: // typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt; marci@281: // //public: marci@281: marci@281: // //UndirGraphWrapper() : graph(0) { } marci@281: // UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { } marci@281: marci@281: // //void setGraph(Graph& _graph) { graph = &_graph; } marci@281: // //Graph& getGraph() const { return (*graph); } marci@281: marci@281: // class Edge { marci@281: // friend class UndirGraphWrapper; marci@281: // bool out_or_in; //true iff out marci@281: // GraphOutEdgeIt out; marci@281: // GraphInEdgeIt in; marci@281: // public: marci@281: // Edge() : out_or_in(), out(), in() { } marci@281: // Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } marci@281: // operator GraphEdge() const { marci@281: // if (out_or_in) return(out); else return(in); marci@281: // } marci@281: // friend bool operator==(const Edge& u, const Edge& v) { marci@281: // if (v.out_or_in) marci@281: // return (u.out_or_in && u.out==v.out); marci@281: // else marci@281: // return (!u.out_or_in && u.in==v.in); marci@281: // } marci@281: // friend bool operator!=(const Edge& u, const Edge& v) { marci@281: // if (v.out_or_in) marci@281: // return (!u.out_or_in || u.out!=v.out); marci@281: // else marci@281: // return (u.out_or_in || u.in!=v.in); marci@281: // } marci@281: // }; marci@281: marci@281: // class OutEdgeIt : public Edge { marci@281: // friend class UndirGraphWrapper; marci@281: // public: marci@281: // OutEdgeIt() : Edge() { } marci@281: // OutEdgeIt(const Invalid& i) : Edge(i) { } marci@281: // OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) marci@281: // : Edge() { marci@281: // out_or_in=true; marci@281: // _G.gw.first(out, n); marci@281: // if (!(_G.gw.valid(out))) { marci@281: // out_or_in=false; marci@281: // _G.gw.first(in, n); marci@281: // } marci@281: // } marci@281: // }; marci@281: marci@281: // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { marci@281: // e.out_or_in=true; marci@281: // gw.first(e.out, n); marci@281: // if (!(gw.valid(e.out))) { marci@281: // e.out_or_in=false; marci@281: // gw.first(e.in, n); marci@281: // } marci@281: // return e; marci@281: // } marci@281: marci@281: // OutEdgeIt& next(OutEdgeIt& e) const { marci@281: // if (e.out_or_in) { alpar@986: // Node n=gw.source(e.out); marci@281: // gw.next(e.out); marci@281: // if (!gw.valid(e.out)) { marci@281: // e.out_or_in=false; marci@281: // gw.first(e.in, n); marci@281: // } marci@281: // } else { marci@281: // gw.next(e.in); marci@281: // } marci@281: // return e; marci@281: // } marci@281: marci@281: // Node aNode(const OutEdgeIt& e) const { alpar@986: // if (e.out_or_in) return gw.source(e); else return gw.target(e); } marci@281: // Node bNode(const OutEdgeIt& e) const { alpar@986: // if (e.out_or_in) return gw.target(e); else return gw.source(e); } marci@281: marci@281: // typedef OutEdgeIt InEdgeIt; marci@281: marci@281: // template I& first(I& i) const { return gw.first(i); } marci@281: // // template I& first(I& i, const P& p) const { marci@281: // // return graph->first(i, p); } marci@281: marci@281: // template I getNext(const I& i) const { marci@281: // return gw.getNext(i); } marci@281: // template I& next(I &i) const { return gw.next(i); } marci@281: marci@281: // template< typename It > It first() const { marci@281: // It e; first(e); return e; } marci@281: marci@281: // template< typename It > It first(const Node& v) const { marci@281: // It e; first(e, v); return e; } marci@281: alpar@986: // Node target(const Edge& e) const { return gw.target(e); } alpar@986: // Node source(const Edge& e) const { return gw.source(e); } marci@281: marci@281: // template bool valid(const I& i) const marci@281: // { return gw.valid(i); } marci@281: marci@281: // //template void setInvalid(const I &i); marci@281: // //{ return graph->setInvalid(i); } marci@281: marci@281: // int nodeNum() const { return gw.nodeNum(); } marci@281: // int edgeNum() const { return gw.edgeNum(); } marci@281: marci@281: // // template Node aNode(const I& e) const { marci@281: // // return graph->aNode(e); } marci@281: // // template Node bNode(const I& e) const { marci@281: // // return graph->bNode(e); } marci@281: marci@281: // Node addNode() const { return gw.addNode(); } marci@281: // // FIXME: ez igy nem jo, mert nem alpar@986: // // Edge addEdge(const Node& source, const Node& target) const { alpar@986: // // return graph->addEdge(source, target); } marci@281: marci@281: // template void erase(const I& i) const { gw.erase(i); } marci@281: marci@281: // void clear() const { gw.clear(); } marci@281: marci@281: // template class NodeMap : public GraphWrapper::NodeMap { marci@281: // public: marci@281: // NodeMap(const UndirGraphWrapper& _G) : marci@281: // GraphWrapper::NodeMap(_G.gw) { } marci@281: // NodeMap(const UndirGraphWrapper& _G, T a) : marci@281: // GraphWrapper::NodeMap(_G.gw, a) { } marci@281: // }; marci@281: marci@281: // template class EdgeMap : public GraphWrapper::EdgeMap { marci@281: // public: marci@281: // EdgeMap(const UndirGraphWrapper& _G) : marci@281: // GraphWrapper::EdgeMap(_G.gw) { } marci@281: // EdgeMap(const UndirGraphWrapper& _G, T a) : marci@281: // GraphWrapper::EdgeMap(_G.gw, a) { } marci@281: // }; marci@281: // }; marci@281: marci@281: marci@298: template marci@298: class UndirGraphWrapper : public GraphWrapper { marci@281: protected: marci@298: typedef typename Graph::Edge GraphEdge; marci@298: typedef typename Graph::OutEdgeIt GraphOutEdgeIt; marci@298: typedef typename Graph::InEdgeIt GraphInEdgeIt; marci@298: public: marci@298: typedef typename GraphWrapper::Node Node; marci@298: typedef typename GraphWrapper::NodeIt NodeIt; marci@281: marci@298: // UndirGraphWrapper() : GraphWrapper() { } marci@298: UndirGraphWrapper(Graph& _graph) : GraphWrapper(_graph) { } marci@281: marci@281: class Edge { marci@298: friend class UndirGraphWrapper; marci@281: protected: marci@281: bool out_or_in; //true iff out marci@281: GraphOutEdgeIt out; marci@281: GraphInEdgeIt in; marci@281: public: marci@281: Edge() : out_or_in(), out(), in() { } marci@281: Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } marci@281: operator GraphEdge() const { marci@281: if (out_or_in) return(out); else return(in); marci@281: } marci@281: //FIXME marci@281: //2 edges are equal if they "refer" to the same physical edge marci@281: //is it good? marci@281: friend bool operator==(const Edge& u, const Edge& v) { marci@281: if (v.out_or_in) marci@281: if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in); marci@281: //return (u.out_or_in && u.out==v.out); marci@281: else marci@281: if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in); marci@281: //return (!u.out_or_in && u.in==v.in); marci@281: } marci@281: friend bool operator!=(const Edge& u, const Edge& v) { marci@281: if (v.out_or_in) marci@281: if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in); marci@281: //return (!u.out_or_in || u.out!=v.out); marci@281: else marci@281: if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in); marci@281: //return (u.out_or_in || u.in!=v.in); marci@281: } marci@281: }; marci@281: marci@281: class OutEdgeIt : public Edge { marci@298: friend class UndirGraphWrapper; marci@281: public: marci@281: OutEdgeIt() : Edge() { } marci@281: OutEdgeIt(const Invalid& i) : Edge(i) { } marci@298: OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) marci@281: : Edge() { marci@298: out_or_in=true; _G.graph->first(out, n); marci@298: if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); } marci@281: } marci@281: }; marci@281: marci@281: typedef OutEdgeIt InEdgeIt; marci@281: marci@281: class EdgeIt : public Edge { marci@298: friend class UndirGraphWrapper; marci@281: protected: marci@281: NodeIt v; marci@281: public: marci@281: EdgeIt() : Edge() { } marci@281: EdgeIt(const Invalid& i) : Edge(i) { } marci@298: EdgeIt(const UndirGraphWrapper& _G) marci@281: : Edge() { marci@281: out_or_in=true; marci@281: //Node v; marci@281: _G.first(v); marci@298: if (_G.valid(v)) _G.graph->first(out); else out=INVALID; marci@298: while (_G.valid(v) && !_G.graph->valid(out)) { marci@298: _G.graph->next(v); marci@298: if (_G.valid(v)) _G.graph->first(out); marci@281: } marci@281: } marci@281: }; marci@281: marci@281: OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { marci@298: e.out_or_in=true; graph->first(e.out, n); marci@298: if (!(graph->valid(e.out))) { e.out_or_in=false; graph->first(e.in, n); } marci@281: return e; marci@281: } marci@281: marci@281: EdgeIt& first(EdgeIt& e) const { marci@281: e.out_or_in=true; marci@281: //NodeIt v; marci@281: first(e.v); marci@298: if (valid(e.v)) graph->first(e.out, e.v); else e.out=INVALID; marci@298: while (valid(e.v) && !graph->valid(e.out)) { marci@298: graph->next(e.v); marci@298: if (valid(e.v)) graph->first(e.out, e.v); marci@281: } marci@281: return e; marci@281: } marci@281: marci@298: template I& first(I& i) const { graph->first(i); return i; } marci@281: template I& first(I& i, const P& p) const { marci@298: graph->first(i, p); return i; } marci@281: marci@281: OutEdgeIt& next(OutEdgeIt& e) const { marci@281: if (e.out_or_in) { alpar@986: Node n=graph->source(e.out); marci@298: graph->next(e.out); marci@298: if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); } marci@281: } else { marci@298: graph->next(e.in); marci@281: } marci@281: return e; marci@281: } marci@281: marci@281: EdgeIt& next(EdgeIt& e) const { alpar@986: //NodeIt v=source(e); marci@298: graph->next(e.out); marci@298: while (valid(e.v) && !graph->valid(e.out)) { marci@281: next(e.v); marci@298: if (valid(e.v)) graph->first(e.out, e.v); marci@281: } marci@281: return e; marci@281: } marci@281: marci@298: template I& next(I &i) const { return graph->next(i); } marci@281: // template I getNext(const I& i) const { return gw.getNext(i); } marci@281: marci@281: template< typename It > It first() const { marci@298: It e; this->first(e); return e; } marci@281: marci@281: template< typename It > It first(const Node& v) const { marci@298: It e; this->first(e, v); return e; } marci@281: alpar@986: // Node target(const Edge& e) const { return gw.target(e); } alpar@986: // Node source(const Edge& e) const { return gw.source(e); } marci@281: marci@281: // template bool valid(const I& i) const marci@281: // { return gw.valid(i); } marci@281: marci@281: // int nodeNum() const { return gw.nodeNum(); } marci@281: // int edgeNum() const { return gw.edgeNum(); } marci@281: marci@281: // template Node aNode(const I& e) const { marci@281: // return graph->aNode(e); } marci@281: // template Node bNode(const I& e) const { marci@281: // return graph->bNode(e); } marci@281: marci@281: Node aNode(const OutEdgeIt& e) const { alpar@986: if (e.out_or_in) return graph->source(e); else return graph->target(e); } marci@281: Node bNode(const OutEdgeIt& e) const { alpar@986: if (e.out_or_in) return graph->target(e); else return graph->source(e); } marci@281: marci@281: // Node addNode() const { return gw.addNode(); } marci@281: marci@281: // FIXME: ez igy nem jo, mert nem alpar@986: // Edge addEdge(const Node& source, const Node& target) const { alpar@986: // return graph->addEdge(source, target); } marci@281: marci@281: // template void erase(const I& i) const { gw.erase(i); } marci@281: marci@281: // void clear() const { gw.clear(); } marci@281: marci@298: // template class NodeMap : public Graph::NodeMap { marci@281: // public: marci@298: // NodeMap(const UndirGraphWrapper& _G) : marci@298: // Graph::NodeMap(_G.gw) { } marci@298: // NodeMap(const UndirGraphWrapper& _G, T a) : marci@298: // Graph::NodeMap(_G.gw, a) { } marci@281: // }; marci@281: marci@281: // template class EdgeMap : alpar@880: // public GraphWrapper::EdgeMap { marci@281: // public: marci@298: // EdgeMap(const UndirGraphWrapper& _G) : alpar@880: // GraphWrapper::EdgeMap(_G.gw) { } marci@298: // EdgeMap(const UndirGraphWrapper& _G, T a) : marci@298: // Graph::EdgeMap(_G.gw, a) { } marci@281: // }; marci@281: }; marci@281: marci@281: marci@281: marci@281: marci@281: marci@281: // template marci@281: // class SymGraphWrapper marci@281: // { marci@281: // Graph* graph; marci@281: marci@281: // public: marci@281: // typedef Graph BaseGraph; marci@281: marci@281: // typedef typename Graph::Node Node; marci@281: // typedef typename Graph::Edge Edge; marci@281: marci@281: // typedef typename Graph::NodeIt NodeIt; marci@281: marci@281: // //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon marci@281: // //iranyitatlant, ami van marci@281: // //mert csak 1 dolgot lehet be typedef-elni marci@281: // typedef typename Graph::OutEdgeIt SymEdgeIt; marci@281: // //typedef typename Graph::InEdgeIt SymEdgeIt; marci@281: // //typedef typename Graph::SymEdgeIt SymEdgeIt; marci@281: // typedef typename Graph::EdgeIt EdgeIt; marci@281: marci@281: // int nodeNum() const { return graph->nodeNum(); } marci@281: // int edgeNum() const { return graph->edgeNum(); } marci@281: marci@281: // template I& first(I& i) const { return graph->first(i); } marci@281: // template I& first(I& i, const P& p) const { marci@281: // return graph->first(i, p); } marci@281: // //template I next(const I i); { return graph->goNext(i); } marci@281: // //template I &goNext(I &i); { return graph->goNext(i); } marci@281: marci@281: // template< typename It > It first() const { marci@281: // It e; first(e); return e; } marci@281: marci@281: // template< typename It > It first(Node v) const { marci@281: // It e; first(e, v); return e; } marci@281: alpar@986: // Node target(const Edge& e) const { return graph->target(e); } alpar@986: // Node source(const Edge& e) const { return graph->source(e); } marci@281: marci@281: // template Node aNode(const I& e) const { marci@281: // return graph->aNode(e); } marci@281: // template Node bNode(const I& e) const { marci@281: // return graph->bNode(e); } marci@281: marci@281: // //template bool valid(const I i); marci@281: // //{ return graph->valid(i); } marci@281: marci@281: // //template void setInvalid(const I &i); marci@281: // //{ return graph->setInvalid(i); } marci@281: marci@281: // Node addNode() { return graph->addNode(); } alpar@986: // Edge addEdge(const Node& source, const Node& target) { alpar@986: // return graph->addEdge(source, target); } marci@281: marci@281: // template void erase(const I& i) { graph->erase(i); } marci@281: marci@281: // void clear() { graph->clear(); } marci@281: marci@281: // template class NodeMap : public Graph::NodeMap { }; marci@281: // template class EdgeMap : public Graph::EdgeMap { }; marci@281: marci@281: // void setGraph(Graph& _graph) { graph = &_graph; } marci@281: // Graph& getGraph() { return (*graph); } marci@281: marci@281: // //SymGraphWrapper() : graph(0) { } marci@281: // SymGraphWrapper(Graph& _graph) : graph(&_graph) { } marci@281: // }; marci@281: marci@281: marci@298: template marci@298: class ResGraphWrapper : public GraphWrapper{ marci@281: public: marci@298: typedef typename GraphWrapper::Node Node; marci@298: typedef typename GraphWrapper::NodeIt NodeIt; marci@281: protected: marci@298: typedef typename Graph::OutEdgeIt OldOutEdgeIt; marci@298: typedef typename Graph::InEdgeIt OldInEdgeIt; marci@281: FlowMap* flow; marci@281: const CapacityMap* capacity; marci@281: public: marci@281: marci@298: ResGraphWrapper(Graph& _graph, FlowMap& _flow, marci@281: const CapacityMap& _capacity) : marci@298: GraphWrapper(_graph), flow(&_flow), capacity(&_capacity) { } marci@281: marci@281: class Edge; marci@281: class OutEdgeIt; marci@281: friend class Edge; marci@281: friend class OutEdgeIt; marci@281: marci@281: class Edge { marci@298: friend class ResGraphWrapper; marci@281: protected: marci@281: bool out_or_in; //true, iff out marci@281: OldOutEdgeIt out; marci@281: OldInEdgeIt in; marci@281: public: marci@281: Edge() : out_or_in(true) { } marci@281: Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } marci@281: // bool valid() const { marci@281: // return out_or_in && out.valid() || in.valid(); } marci@281: friend bool operator==(const Edge& u, const Edge& v) { marci@281: if (v.out_or_in) marci@281: return (u.out_or_in && u.out==v.out); marci@281: else marci@281: return (!u.out_or_in && u.in==v.in); marci@281: } marci@281: friend bool operator!=(const Edge& u, const Edge& v) { marci@281: if (v.out_or_in) marci@281: return (!u.out_or_in || u.out!=v.out); marci@281: else marci@281: return (u.out_or_in || u.in!=v.in); marci@281: } marci@281: }; marci@281: marci@281: marci@281: class OutEdgeIt : public Edge { marci@298: friend class ResGraphWrapper; marci@281: public: marci@281: OutEdgeIt() { } marci@281: //FIXME marci@281: OutEdgeIt(const Edge& e) : Edge(e) { } marci@281: OutEdgeIt(const Invalid& i) : Edge(i) { } marci@281: protected: marci@298: OutEdgeIt(const ResGraphWrapper& resG, Node v) : Edge() { marci@298: resG.graph->first(out, v); marci@298: while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } marci@298: if (!resG.graph->valid(out)) { marci@281: out_or_in=0; marci@298: resG.graph->first(in, v); marci@298: while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } marci@281: } marci@281: } marci@281: // public: marci@281: // OutEdgeIt& operator++() { marci@281: // if (out_or_in) { marci@281: // Node v=/*resG->*/G->aNode(out); marci@281: // ++out; marci@281: // while( out.valid() && !(Edge::resCap()>0) ) { ++out; } marci@281: // if (!out.valid()) { marci@281: // out_or_in=0; marci@281: // G->first(in, v); marci@281: // while( in.valid() && !(Edge::resCap()>0) ) { ++in; } marci@281: // } marci@281: // } else { marci@281: // ++in; marci@281: // while( in.valid() && !(Edge::resCap()>0) ) { ++in; } marci@281: // } marci@281: // return *this; marci@281: // } marci@281: }; marci@281: marci@281: //FIXME This is just for having InEdgeIt marci@281: typedef void InEdgeIt; marci@281: marci@281: class EdgeIt : public Edge { marci@298: friend class ResGraphWrapper; marci@281: NodeIt v; marci@281: public: marci@281: EdgeIt() { } marci@281: //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } marci@281: EdgeIt(const Invalid& i) : Edge(i) { } marci@298: EdgeIt(const ResGraphWrapper& resG) : Edge() { marci@298: resG.graph->first(v); marci@298: if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID; marci@298: while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } marci@298: while (resG.graph->valid(v) && !resG.graph->valid(out)) { marci@298: resG.graph->next(v); marci@298: if (resG.graph->valid(v)) resG.graph->first(out, v); marci@298: while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } marci@281: } marci@298: if (!resG.graph->valid(out)) { marci@281: out_or_in=0; marci@298: resG.graph->first(v); marci@298: if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID; marci@298: while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } marci@298: while (resG.graph->valid(v) && !resG.graph->valid(in)) { marci@298: resG.graph->next(v); marci@298: if (resG.graph->valid(v)) resG.graph->first(in, v); marci@298: while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } marci@281: } marci@281: } marci@281: } marci@281: // EdgeIt& operator++() { marci@281: // if (out_or_in) { marci@281: // ++out; marci@281: // while (out.valid() && !(Edge::resCap()>0) ) { ++out; } marci@281: // while (v.valid() && !out.valid()) { marci@281: // ++v; marci@281: // if (v.valid()) G->first(out, v); marci@281: // while (out.valid() && !(Edge::resCap()>0) ) { ++out; } marci@281: // } marci@281: // if (!out.valid()) { marci@281: // out_or_in=0; marci@281: // G->first(v); marci@281: // if (v.valid()) G->first(in, v); else in=OldInEdgeIt(); marci@281: // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } marci@281: // while (v.valid() && !in.valid()) { marci@281: // ++v; marci@281: // if (v.valid()) G->first(in, v); marci@281: // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } marci@281: // } marci@281: // } marci@281: // } else { marci@281: // ++in; marci@281: // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } marci@281: // while (v.valid() && !in.valid()) { marci@281: // ++v; marci@281: // if (v.valid()) G->first(in, v); marci@281: // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } marci@281: // } marci@281: // } marci@281: // return *this; marci@281: // } marci@281: }; marci@281: marci@298: NodeIt& first(NodeIt& v) const { graph->first(v); return v; } marci@281: OutEdgeIt& first(OutEdgeIt& e, Node v) const { marci@281: e=OutEdgeIt(*this, v); marci@281: return e; marci@281: } marci@281: EdgeIt& first(EdgeIt& e) const { marci@281: e=EdgeIt(*this); marci@281: return e; marci@281: } marci@281: marci@298: NodeIt& next(NodeIt& n) const { return graph->next(n); } marci@281: marci@281: OutEdgeIt& next(OutEdgeIt& e) const { marci@281: if (e.out_or_in) { marci@298: Node v=graph->aNode(e.out); marci@298: graph->next(e.out); marci@298: while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } marci@298: if (!graph->valid(e.out)) { marci@281: e.out_or_in=0; marci@298: graph->first(e.in, v); marci@298: while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } marci@281: } marci@281: } else { marci@298: graph->next(e.in); marci@298: while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } marci@281: } marci@281: return e; marci@281: } marci@281: marci@281: EdgeIt& next(EdgeIt& e) const { marci@281: if (e.out_or_in) { marci@298: graph->next(e.out); marci@298: while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } marci@298: while (graph->valid(e.v) && !graph->valid(e.out)) { marci@298: graph->next(e.v); marci@298: if (graph->valid(e.v)) graph->first(e.out, e.v); marci@298: while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } marci@281: } marci@298: if (!graph->valid(e.out)) { marci@281: e.out_or_in=0; marci@298: graph->first(e.v); marci@298: if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID; marci@298: while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } marci@298: while (graph->valid(e.v) && !graph->valid(e.in)) { marci@298: graph->next(e.v); marci@298: if (graph->valid(e.v)) graph->first(e.in, e.v); marci@298: while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } marci@281: } marci@281: } marci@281: } else { marci@298: graph->next(e.in); marci@298: while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } marci@298: while (graph->valid(e.v) && !graph->valid(e.in)) { marci@298: graph->next(e.v); marci@298: if (graph->valid(e.v)) graph->first(e.in, e.v); marci@298: while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } marci@281: } marci@281: } marci@281: return e; marci@281: } marci@281: marci@281: marci@281: template< typename It > marci@281: It first() const { marci@281: It e; marci@281: first(e); marci@281: return e; marci@281: } marci@281: marci@281: template< typename It > marci@281: It first(Node v) const { marci@281: It e; marci@281: first(e, v); marci@281: return e; marci@281: } marci@281: alpar@986: Node source(Edge e) const { marci@298: return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } alpar@986: Node target(Edge e) const { marci@298: return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } marci@281: marci@281: Node aNode(OutEdgeIt e) const { marci@298: return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } marci@281: Node bNode(OutEdgeIt e) const { marci@298: return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } marci@281: marci@298: int nodeNum() const { return graph->nodeNum(); } marci@281: //FIXME marci@298: //int edgeNum() const { return graph->edgeNum(); } marci@281: marci@281: marci@298: int id(Node v) const { return graph->id(v); } marci@281: marci@298: bool valid(Node n) const { return graph->valid(n); } marci@281: bool valid(Edge e) const { marci@298: return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); } marci@281: marci@281: void augment(const Edge& e, Number a) const { marci@281: if (e.out_or_in) marci@281: flow->set(e.out, flow->get(e.out)+a); marci@281: else marci@281: flow->set(e.in, flow->get(e.in)-a); marci@281: } marci@281: marci@281: Number resCap(const Edge& e) const { marci@281: if (e.out_or_in) marci@281: return (capacity->get(e.out)-flow->get(e.out)); marci@281: else marci@281: return (flow->get(e.in)); marci@281: } marci@281: marci@281: Number resCap(OldOutEdgeIt out) const { marci@281: return (capacity->get(out)-flow->get(out)); marci@281: } marci@281: marci@281: Number resCap(OldInEdgeIt in) const { marci@281: return (flow->get(in)); marci@281: } marci@281: marci@298: // template class NodeMap : public Graph::NodeMap { marci@281: // public: marci@298: // NodeMap(const ResGraphWrapper& _G) marci@298: // : Graph::NodeMap(_G.gw) { } marci@298: // NodeMap(const ResGraphWrapper& _G, marci@298: // T a) : Graph::NodeMap(_G.gw, a) { } marci@281: // }; marci@281: marci@281: // template marci@281: // class NodeMap { marci@281: // typename Graph::NodeMap node_map; marci@281: // public: marci@281: // NodeMap(const ResGraphWrapper& _G) : node_map(*(_G.graph)) { } marci@281: // NodeMap(const ResGraphWrapper& _G, T a) : node_map(*(_G.graph), a) { } marci@281: // void set(Node nit, T a) { node_map.set(nit, a); } marci@281: // T get(Node nit) const { return node_map.get(nit); } marci@281: // }; marci@281: marci@281: template marci@281: class EdgeMap { marci@298: typename Graph::EdgeMap forward_map, backward_map; marci@281: public: marci@298: EdgeMap(const ResGraphWrapper& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } marci@298: EdgeMap(const ResGraphWrapper& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } marci@281: void set(Edge e, T a) { marci@281: if (e.out_or_in) marci@281: forward_map.set(e.out, a); marci@281: else marci@281: backward_map.set(e.in, a); marci@281: } marci@281: T get(Edge e) { marci@281: if (e.out_or_in) marci@281: return forward_map.get(e.out); marci@281: else marci@281: return backward_map.get(e.in); marci@281: } marci@281: }; marci@281: }; marci@281: marci@298: //ErasingFirstGraphWrapper for blocking flows marci@298: template marci@298: class ErasingFirstGraphWrapper : public GraphWrapper { marci@281: protected: marci@281: FirstOutEdgesMap* first_out_edges; marci@281: public: marci@298: typedef typename GraphWrapper::Node Node; marci@298: typedef typename GraphWrapper::NodeIt NodeIt; marci@298: typedef typename GraphWrapper::Edge Edge; marci@298: typedef typename GraphWrapper::EdgeIt EdgeIt; marci@298: typedef typename GraphWrapper::InEdgeIt InEdgeIt; marci@298: typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; marci@281: marci@298: ErasingFirstGraphWrapper(Graph& _graph, marci@298: FirstOutEdgesMap& _first_out_edges) : marci@298: GraphWrapper(_graph), first_out_edges(&_first_out_edges) { } marci@281: marci@281: template I& first(I& i) const { marci@298: graph->first(i); marci@281: return i; marci@281: } marci@281: OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { marci@281: e=first_out_edges->get(n); marci@281: return e; marci@281: } marci@281: template I& first(I& i, const P& p) const { marci@298: graph->first(i, p); marci@281: return i; marci@281: } marci@281: marci@281: //template I getNext(const I& i) const { marci@281: // return gw.getNext(i); marci@281: //} marci@281: template I& next(I &i) const { marci@298: graph->next(i); marci@281: return i; marci@281: } marci@281: marci@281: template< typename It > It first() const { marci@281: It e; this->first(e); return e; } marci@281: marci@281: template< typename It > It first(const Node& v) const { marci@281: It e; this->first(e, v); return e; } marci@281: marci@281: void erase(const OutEdgeIt& e) const { marci@281: OutEdgeIt f=e; marci@281: this->next(f); alpar@986: first_out_edges->set(this->source(e), f); marci@281: } marci@281: }; marci@281: marci@281: // // FIXME: comparison should be made better!!! marci@281: // template marci@281: // class ResGraphWrapper marci@281: // { marci@281: // Graph* graph; marci@281: marci@281: // public: marci@281: // typedef Graph BaseGraph; marci@281: marci@281: // typedef typename Graph::Node Node; marci@281: // typedef typename Graph::Edge Edge; marci@281: marci@281: // typedef typename Graph::NodeIt NodeIt; marci@281: marci@281: // class OutEdgeIt { marci@281: // public: marci@281: // //Graph::Node n; marci@281: // bool out_or_in; marci@281: // typename Graph::OutEdgeIt o; marci@281: // typename Graph::InEdgeIt i; marci@281: // }; marci@281: // class InEdgeIt { marci@281: // public: marci@281: // //Graph::Node n; marci@281: // bool out_or_in; marci@281: // typename Graph::OutEdgeIt o; marci@281: // typename Graph::InEdgeIt i; marci@281: // }; marci@281: // typedef typename Graph::SymEdgeIt SymEdgeIt; marci@281: // typedef typename Graph::EdgeIt EdgeIt; marci@281: marci@281: // int nodeNum() const { return gw.nodeNum(); } marci@281: // int edgeNum() const { return gw.edgeNum(); } marci@281: marci@281: // Node& first(Node& n) const { return gw.first(n); } marci@281: marci@281: // // Edge and SymEdge is missing!!!! marci@281: // // Edge <-> In/OutEdgeIt conversion is missing!!!! marci@281: marci@281: // //FIXME marci@281: // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const marci@281: // { marci@281: // e.n=n; marci@281: // gw.first(e.o,n); marci@281: // while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) marci@281: // gw.goNext(e.o); marci@281: // if(!gw.valid(e.o)) { marci@281: // gw.first(e.i,n); marci@281: // while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) marci@281: // gw.goNext(e.i); marci@281: // } marci@281: // return e; marci@281: // } marci@281: // /* marci@281: // OutEdgeIt &goNext(OutEdgeIt &e) marci@281: // { marci@281: // if(gw.valid(e.o)) { marci@281: // while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) marci@281: // gw.goNext(e.o); marci@281: // if(gw.valid(e.o)) return e; marci@281: // else gw.first(e.i,e.n); marci@281: // } marci@281: // else { marci@281: // while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) marci@281: // gw.goNext(e.i); marci@281: // return e; marci@281: // } marci@281: // } marci@281: // OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);} marci@281: // */ marci@281: // //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);} marci@281: marci@281: // //FIXME marci@281: // InEdgeIt& first(InEdgeIt& e, const Node& n) const marci@281: // { marci@281: // e.n=n; marci@281: // gw.first(e.i,n); marci@281: // while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) marci@281: // gw.goNext(e.i); marci@281: // if(!gw.valid(e.i)) { marci@281: // gw.first(e.o,n); marci@281: // while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) marci@281: // gw.goNext(e.o); marci@281: // } marci@281: // return e; marci@281: // } marci@281: // /* marci@281: // InEdgeIt &goNext(InEdgeIt &e) marci@281: // { marci@281: // if(gw.valid(e.i)) { marci@281: // while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) marci@281: // gw.goNext(e.i); marci@281: // if(gw.valid(e.i)) return e; marci@281: // else gw.first(e.o,e.n); marci@281: // } marci@281: // else { marci@281: // while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) marci@281: // gw.goNext(e.o); marci@281: // return e; marci@281: // } marci@281: // } marci@281: // InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);} marci@281: // */ marci@281: // //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);} marci@281: marci@281: // //template I &goNext(I &i); { return gw.goNext(i); } marci@281: // //template I next(const I i); { return gw.goNext(i); } marci@281: marci@281: // template< typename It > It first() const { marci@281: // It e; first(e); return e; } marci@281: marci@281: // template< typename It > It first(Node v) const { marci@281: // It e; first(e, v); return e; } marci@281: alpar@986: // Node target(const Edge& e) const { return gw.target(e); } alpar@986: // Node source(const Edge& e) const { return gw.source(e); } marci@281: marci@281: // template Node aNode(const I& e) const { marci@281: // return gw.aNode(e); } marci@281: // template Node bNode(const I& e) const { marci@281: // return gw.bNode(e); } marci@281: marci@281: // //template bool valid(const I i); marci@281: // //{ return gw.valid(i); } marci@281: marci@281: // //template void setInvalid(const I &i); marci@281: // //{ return gw.setInvalid(i); } marci@281: marci@281: // Node addNode() { return gw.addNode(); } alpar@986: // Edge addEdge(const Node& source, const Node& target) { alpar@986: // return gw.addEdge(source, target); } marci@281: marci@281: // template void erase(const I& i) { gw.erase(i); } marci@281: marci@281: // void clear() { gw.clear(); } marci@281: marci@281: // template class NodeMap : public Graph::NodeMap { }; marci@281: // template class EdgeMap : public Graph::EdgeMap { }; marci@281: marci@281: // void setGraph(Graph& _graph) { graph = &_graph; } marci@281: // Graph& getGraph() { return (*graph); } marci@281: marci@281: // //ResGraphWrapper() : graph(0) { } marci@281: // ResGraphWrapper(Graph& _graph) : graph(&_graph) { } marci@281: // }; marci@281: alpar@921: } //namespace lemon marci@281: alpar@921: #endif //LEMON_GRAPH_WRAPPER_H marci@281: