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