# HG changeset patch # User marci # Date 1079781540 0 # Node ID c07e4dd324387de745fce2c839dd1f1ae39c977b # Parent 9222a9b8b323ae70b209610427319c8f81ccf04b . diff -r 9222a9b8b323 -r c07e4dd32438 src/work/list_graph.h --- a/src/work/list_graph.h Fri Mar 19 22:16:05 2004 +0000 +++ b/src/work/list_graph.h Sat Mar 20 11:19:00 2004 +0000 @@ -428,7 +428,7 @@ friend class ListGraph; //protected: public: //for alpar - EdgeIt(const ListGraph&) { + EdgeIt(const ListGraph& G) { node_item* v=G._first_node; if (v) edge=v->_first_out_edge; else edge=0; while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; } diff -r 9222a9b8b323 -r c07e4dd32438 src/work/marci/graph_wrapper.h --- a/src/work/marci/graph_wrapper.h Fri Mar 19 22:16:05 2004 +0000 +++ b/src/work/marci/graph_wrapper.h Sat Mar 20 11:19:00 2004 +0000 @@ -29,19 +29,19 @@ void setGraph(Graph& _graph) { graph = &_graph; } Graph& getGraph() const { return (*graph); } - template I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } - template I& /*getF*/first(I& i, const P& p) const { - return graph->/*getF*/first(i, p); } + 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; /*getF*/first(e); return e; } + It e; first(e); return e; } template< typename It > It first(const Node& v) const { - It e; /*getF*/first(e, v); return e; } + It e; first(e, v); return e; } Node head(const Edge& e) const { return graph->head(e); } Node tail(const Edge& e) const { return graph->tail(e); } @@ -85,6 +85,81 @@ }; }; + template + class GraphWrapperSkeleton { + 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; + + //GraphWrapperSkeleton() : gw() { } + GraphWrapperSkeleton(GraphWrapper& _gw) : gw(_gw) { } + + void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); } + BaseGraph& getGraph() const { return gw.getGraph(); } + + 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; this->first(e); return e; } + + template< typename It > It first(const Node& v) const { + It e; this->first(e, v); return e; } + + Node head(const Edge& e) const { return gw.head(e); } + Node tail(const Edge& e) const { return gw.tail(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& tail, const Node& head) const { + return gw.addEdge(tail, head); } + + template void erase(const I& i) const { gw.erase(i); } + + void clear() const { gw.clear(); } + + template class NodeMap : public GraphWrapper::NodeMap { + public: + NodeMap(const GraphWrapperSkeleton& _G) : + GraphWrapper::NodeMap(_G.gw) { } + NodeMap(const GraphWrapperSkeleton& _G, T a) : + GraphWrapper::NodeMap(_G.gw, a) { } + }; + + template class EdgeMap : public GraphWrapper::EdgeMap { + public: + EdgeMap(const GraphWrapperSkeleton& _G) : + GraphWrapper::EdgeMap(_G.gw) { } + EdgeMap(const GraphWrapperSkeleton& _G, T a) : + GraphWrapper::EdgeMap(_G.gw, a) { } + }; + }; + template class RevGraphWrapper { @@ -109,19 +184,19 @@ void setGraph(Graph& _graph) { graph = &_graph; } Graph& getGraph() const { return (*graph); } - template I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } - template I& /*getF*/first(I& i, const P& p) const { - return graph->/*getF*/first(i, p); } + 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; /*getF*/first(e); return e; } + It e; first(e); return e; } template< typename It > It first(const Node& v) const { - It e; /*getF*/first(e, v); return e; } + It e; first(e, v); return e; } Node head(const Edge& e) const { return graph->tail(e); } Node tail(const Edge& e) const { return graph->head(e); } @@ -227,20 +302,20 @@ OutEdgeIt(const Invalid& i) : Edge(i) { } OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) : Edge() { out_or_in=true; - _G.graph->/*getF*/first(out, n); + _G.graph->first(out, n); if (!(_G.graph->valid(out))) { out_or_in=false; - _G.graph->/*getF*/first(in, n); + _G.graph->first(in, n); } } }; - OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const { + OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { e.out_or_in=true; - graph->/*getF*/first(e.out, n); + graph->first(e.out, n); if (!(graph->valid(e.out))) { e.out_or_in=false; - graph->/*getF*/first(e.in, n); + graph->first(e.in, n); } return e; } @@ -251,7 +326,7 @@ graph->next(e.out); if (!graph->valid(e.out)) { e.out_or_in=false; - graph->/*getF*/first(e.in, n); + graph->first(e.in, n); } } else { graph->next(e.in); @@ -266,19 +341,19 @@ typedef OutEdgeIt InEdgeIt; - template I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } -// template I& /*getF*/first(I& i, const P& p) const { -// return graph->/*getF*/first(i, p); } + 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; /*getF*/first(e); return e; } + It e; first(e); return e; } template< typename It > It first(const Node& v) const { - It e; /*getF*/first(e, v); return e; } + It e; first(e, v); return e; } Node head(const Edge& e) const { return graph->head(e); } Node tail(const Edge& e) const { return graph->tail(e); } @@ -348,17 +423,17 @@ // int nodeNum() const { return graph->nodeNum(); } // int edgeNum() const { return graph->edgeNum(); } -// template I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } -// template I& /*getF*/first(I& i, const P& p) const { -// return graph->/*getF*/first(i, p); } +// 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; /*getF*/first(e); return e; } +// It e; first(e); return e; } // template< typename It > It first(Node v) const { -// It e; /*getF*/first(e, v); return e; } +// It e; first(e, v); return e; } // Node head(const Edge& e) const { return graph->head(e); } // Node tail(const Edge& e) const { return graph->tail(e); } @@ -455,11 +530,11 @@ OutEdgeIt(const Invalid& i) : Edge(i) { } private: OutEdgeIt(const ResGraphWrapper& resG, Node v) : Edge() { - resG.graph->/*getF*/first(out, v); + resG.graph->first(out, v); while( resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); } if (!resG.graph->valid(out)) { out_or_in=0; - resG.graph->/*getF*/first(in, v); + resG.graph->first(in, v); while( resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); } } } @@ -471,7 +546,7 @@ // while( out.valid() && !(Edge::free()>0) ) { ++out; } // if (!out.valid()) { // out_or_in=0; -// G->/*getF*/first(in, v); +// G->first(in, v); // while( in.valid() && !(Edge::free()>0) ) { ++in; } // } // } else { @@ -490,22 +565,22 @@ //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } EdgeIt(const Invalid& i) : Edge(i) { } EdgeIt(const ResGraphWrapper& resG) : Edge() { - resG.graph->/*getF*/first(v); - if (resG.graph->valid(v)) resG.graph->/*getF*/first(out, v); else out=OldOutEdgeIt(INVALID); + resG.graph->first(v); + if (resG.graph->valid(v)) resG.graph->first(out, v); else out=OldOutEdgeIt(INVALID); while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); } while (resG.graph->valid(v) && !resG.graph->valid(out)) { resG.graph->next(v); - if (resG.graph->valid(v)) resG.graph->/*getF*/first(out, v); + if (resG.graph->valid(v)) resG.graph->first(out, v); while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); } } if (!resG.graph->valid(out)) { out_or_in=0; - resG.graph->/*getF*/first(v); - if (resG.graph->valid(v)) resG.graph->/*getF*/first(in, v); else in=OldInEdgeIt(INVALID); + resG.graph->first(v); + if (resG.graph->valid(v)) resG.graph->first(in, v); else in=OldInEdgeIt(INVALID); while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); } while (resG.graph->valid(v) && !resG.graph->valid(in)) { resG.graph->next(v); - if (resG.graph->valid(v)) resG.graph->/*getF*/first(in, v); + if (resG.graph->valid(v)) resG.graph->first(in, v); while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); } } } @@ -516,17 +591,17 @@ // while (out.valid() && !(Edge::free()>0) ) { ++out; } // while (v.valid() && !out.valid()) { // ++v; -// if (v.valid()) G->/*getF*/first(out, v); +// if (v.valid()) G->first(out, v); // while (out.valid() && !(Edge::free()>0) ) { ++out; } // } // if (!out.valid()) { // out_or_in=0; -// G->/*getF*/first(v); -// if (v.valid()) G->/*getF*/first(in, v); else in=OldInEdgeIt(); +// G->first(v); +// if (v.valid()) G->first(in, v); else in=OldInEdgeIt(); // while (in.valid() && !(Edge::free()>0) ) { ++in; } // while (v.valid() && !in.valid()) { // ++v; -// if (v.valid()) G->/*getF*/first(in, v); +// if (v.valid()) G->first(in, v); // while (in.valid() && !(Edge::free()>0) ) { ++in; } // } // } @@ -535,7 +610,7 @@ // while (in.valid() && !(Edge::free()>0) ) { ++in; } // while (v.valid() && !in.valid()) { // ++v; -// if (v.valid()) G->/*getF*/first(in, v); +// if (v.valid()) G->first(in, v); // while (in.valid() && !(Edge::free()>0) ) { ++in; } // } // } @@ -543,12 +618,12 @@ // } }; - NodeIt& /*getF*/first(NodeIt& v) const { return graph->/*getF*/first(v); } - OutEdgeIt& /*getF*/first(OutEdgeIt& e, Node v) const { + NodeIt& first(NodeIt& v) const { return graph->first(v); } + OutEdgeIt& first(OutEdgeIt& e, Node v) const { e=OutEdgeIt(*this, v); return e; } - EdgeIt& /*getF*/first(EdgeIt& e) const { + EdgeIt& first(EdgeIt& e) const { e=EdgeIt(*this); return e; } @@ -562,7 +637,7 @@ while( graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); } if (!graph->valid(e.out)) { e.out_or_in=0; - graph->/*getF*/first(e.in, v); + graph->first(e.in, v); while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } } } else { @@ -578,17 +653,17 @@ while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); } while (graph->valid(e.v) && !graph->valid(e.out)) { graph->next(e.v); - if (graph->valid(e.v)) graph->/*getF*/first(e.out, e.v); + if (graph->valid(e.v)) graph->first(e.out, e.v); while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); } } if (!graph->valid(e.out)) { e.out_or_in=0; - graph->/*getF*/first(e.v); - if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v); else e.in=OldInEdgeIt(INVALID); + graph->first(e.v); + if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=OldInEdgeIt(INVALID); while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } while (graph->valid(e.v) && !graph->valid(e.in)) { graph->next(e.v); - if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v); + if (graph->valid(e.v)) graph->first(e.in, e.v); while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } } } @@ -597,7 +672,7 @@ while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } while (graph->valid(e.v) && !graph->valid(e.in)) { graph->next(e.v); - if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v); + if (graph->valid(e.v)) graph->first(e.in, e.v); while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); } } } @@ -608,14 +683,14 @@ template< typename It > It first() const { It e; - /*getF*/first(e); + first(e); return e; } template< typename It > It first(Node v) const { It e; - /*getF*/first(e, v); + first(e, v); return e; } @@ -708,7 +783,7 @@ first_out_edges(*this) /*, dist(*this)*/ { for(NodeIt n=this->template first(); this->valid(n); this->next(n)) { OutEdgeIt e; - ResGraphWrapper::/*getF*/first(e, n); + ResGraphWrapper::first(e, n); first_out_edges.set(n, e); } } @@ -739,28 +814,28 @@ //typedef typename Graph::SymEdgeIt SymEdgeIt; //typedef typename ResGraphWrapper::EdgeIt EdgeIt; - NodeIt& /*getF*/first(NodeIt& n) const { - return ResGraphWrapper::/*getF*/first(n); + NodeIt& first(NodeIt& n) const { + return ResGraphWrapper::first(n); } - OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const { + OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { e=first_out_edges.get(n); return e; } - //ROSSZ template I& /*getF*/first(I& i) const { return /*getF*/first(i); } - //ROSSZ template I& /*getF*/first(I& i, const P& p) const { - // return /*getF*/first(i, p); } + //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 graph->getNext(i); } //template I& next(I &i) const { return graph->next(i); } template< typename It > It first() const { - It e; /*getF*/first(e); return e; } + It e; first(e); return e; } template< typename It > It first(const Node& v) const { - It e; /*getF*/first(e, v); return e; } + It e; first(e, v); return e; } //Node head(const Edge& e) const { return graph->head(e); } //Node tail(const Edge& e) const { return graph->tail(e); } @@ -838,8 +913,8 @@ ErasingResGraphWrapper(_G, _flow, _capacity), dist(*this, graph->nodeNum()) { } - OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const { - ErasingResGraphWrapper::/*getF*/first(e, n); + OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { + ErasingResGraphWrapper::first(e, n); while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e)))) ErasingResGraphWrapper::next(e); return e; @@ -856,8 +931,8 @@ return e; } - NodeIt& /*getF*/first(NodeIt& n) const { - return ErasingResGraphWrapper::/*getF*/first(n); + NodeIt& first(NodeIt& n) const { + return ErasingResGraphWrapper::first(n); } void erase(const Edge& e) { @@ -874,19 +949,19 @@ //void setGraph(Graph& _graph) { graph = &_graph; } //Graph& getGraph() const { return (*graph); } - //template I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); } - //template I& /*getF*/first(I& i, const P& p) const { - // return graph->/*getF*/first(i, p); } + //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; /*getF*/first(e); return e; } + It e; first(e); return e; } template< typename It > It first(const Node& v) const { - It e; /*getF*/first(e, v); return e; } + It e; first(e, v); return e; } //Node head(const Edge& e) const { return graph->head(e); } //Node tail(const Edge& e) const { return graph->tail(e); } @@ -970,20 +1045,20 @@ // int nodeNum() const { return graph->nodeNum(); } // int edgeNum() const { return graph->edgeNum(); } -// Node& /*getF*/first(Node& n) const { return graph->/*getF*/first(n); } +// Node& first(Node& n) const { return graph->first(n); } // // Edge and SymEdge is missing!!!! // // Edge <-> In/OutEdgeIt conversion is missing!!!! // //FIXME -// OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const +// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const // { // e.n=n; -// graph->/*getF*/first(e.o,n); +// graph->first(e.o,n); // while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) // graph->goNext(e.o); // if(!graph->valid(e.o)) { -// graph->/*getF*/first(e.i,n); +// graph->first(e.i,n); // while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) // graph->goNext(e.i); // } @@ -996,7 +1071,7 @@ // while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) // graph->goNext(e.o); // if(graph->valid(e.o)) return e; -// else graph->/*getF*/first(e.i,e.n); +// else graph->first(e.i,e.n); // } // else { // while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) @@ -1009,14 +1084,14 @@ // //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);} // //FIXME -// InEdgeIt& /*getF*/first(InEdgeIt& e, const Node& n) const +// InEdgeIt& first(InEdgeIt& e, const Node& n) const // { // e.n=n; -// graph->/*getF*/first(e.i,n); +// graph->first(e.i,n); // while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) // graph->goNext(e.i); // if(!graph->valid(e.i)) { -// graph->/*getF*/first(e.o,n); +// graph->first(e.o,n); // while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) // graph->goNext(e.o); // } @@ -1029,7 +1104,7 @@ // while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) // graph->goNext(e.i); // if(graph->valid(e.i)) return e; -// else graph->/*getF*/first(e.o,e.n); +// else graph->first(e.o,e.n); // } // else { // while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) @@ -1045,10 +1120,10 @@ // //template I next(const I i); { return graph->goNext(i); } // template< typename It > It first() const { -// It e; /*getF*/first(e); return e; } +// It e; first(e); return e; } // template< typename It > It first(Node v) const { -// It e; /*getF*/first(e, v); return e; } +// It e; first(e, v); return e; } // Node head(const Edge& e) const { return graph->head(e); } // Node tail(const Edge& e) const { return graph->tail(e); }