# HG changeset patch # User marci # Date 1082120708 0 # Node ID e8725f30dd988f844c9f98f626ae5de33fca5b44 # Parent 6e1b7efa577f6df3d853575b4e8c6ec31ed78ee1 kicsit takaritottam, es szepitettem es, es maga a csuda, de azer nem teljesen mer' meg kell csinalni vele dolgokat. diff -r 6e1b7efa577f -r e8725f30dd98 src/work/marci/graph_wrapper.h --- a/src/work/marci/graph_wrapper.h Fri Apr 16 12:15:17 2004 +0000 +++ b/src/work/marci/graph_wrapper.h Fri Apr 16 13:05:08 2004 +0000 @@ -105,7 +105,6 @@ }; class OutEdgeIt { friend class GraphWrapper; -// typedef typename Graph::OutEdgeIt GraphOutEdgeIt; typename Graph::OutEdgeIt e; public: OutEdgeIt() { } @@ -117,7 +116,6 @@ }; class InEdgeIt { friend class GraphWrapper; -// typedef typename Graph::InEdgeIt GraphInEdgeIt; typename Graph::InEdgeIt e; public: InEdgeIt() { } @@ -130,7 +128,6 @@ //typedef typename Graph::SymEdgeIt SymEdgeIt; class EdgeIt { friend class GraphWrapper; -// typedef typename Graph::EdgeIt GraphEdgeIt; typename Graph::EdgeIt e; public: EdgeIt() { } @@ -152,25 +149,11 @@ EdgeIt& first(EdgeIt& i) const { i=EdgeIt(*this); return i; } -// 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; -// } - + NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } -// template I& next(I &i) const { graph->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 head(const Edge& e) const { return Node(graph->head(static_cast(e))); } @@ -181,11 +164,6 @@ return graph->valid(static_cast(n)); } bool valid(const Edge& e) const { return graph->valid(static_cast(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(); } @@ -194,10 +172,6 @@ Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } -// template Node aNode(const I& e) const { -// return Node(graph->aNode(e.e)); } -// template Node bNode(const I& e) const { -// return Node(graph->bNode(e.e)); } Node addNode() const { return Node(graph->addNode()); } Edge addEdge(const Node& tail, const Node& head) const { @@ -205,7 +179,6 @@ void erase(const Node& i) const { graph->erase(i); } void erase(const Edge& i) const { graph->erase(i); } -// template void erase(const I& i) const { graph->erase(i); } void clear() const { graph->clear(); } @@ -226,109 +199,65 @@ }; }; + /// A graph wrapper which reverses the orientation of the edges. -// template -// class RevGraphWrapper -// { -// protected: -// Graph* graph; - -// public: -// typedef Graph ParentGraph; - -// 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& 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 head(const Edge& e) const { return graph->tail(e); } -// Node tail(const Edge& e) const { return graph->head(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& tail, const Node& head) const { -// return graph->addEdge(tail, head); } - -// 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) { } -// }; -// }; - - + /// A graph wrapper which reverses the orientation of the edges. template class RevGraphWrapper : public GraphWrapper { public: + + RevGraphWrapper(Graph& _graph) : GraphWrapper(_graph) { } + typedef typename GraphWrapper::Node Node; typedef typename GraphWrapper::Edge Edge; - //FIXME //If Graph::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; + //the typdef techinque does not work. + //Unfortunately all the typedefs are instantiated in templates. + //typedef typename GraphWrapper::OutEdgeIt InEdgeIt; + //typedef typename GraphWrapper::InEdgeIt OutEdgeIt; -// RevGraphWrapper() : GraphWrapper() { } - RevGraphWrapper(Graph& _graph) : GraphWrapper(_graph) { } + class OutEdgeIt { + friend class GraphWrapper; + friend class RevGraphWrapper; + typename Graph::OutEdgeIt e; + public: + OutEdgeIt() { } + OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } + OutEdgeIt(const Invalid& i) : e(i) { } + OutEdgeIt(const RevGraphWrapper& _G, const Node& _n) : + e(*(_G.graph), typename Graph::Node(_n)) { } + operator Edge() const { return Edge(typename Graph::Edge(e)); } + }; + class InEdgeIt { + friend class GraphWrapper; + friend class RevGraphWrapper; + typename Graph::InEdgeIt e; + public: + InEdgeIt() { } + InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } + InEdgeIt(const Invalid& i) : e(i) { } + InEdgeIt(const RevGraphWrapper& _G, const Node& _n) : + e(*(_G.graph), typename Graph::Node(_n)) { } + operator Edge() const { return Edge(typename Graph::Edge(e)); } + }; - Node head(const Edge& e) const - { return GraphWrapper::tail(e); } - Node tail(const Edge& e) const - { return GraphWrapper::head(e); } + using GraphWrapper::first; + 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; + } + + using GraphWrapper::next; + OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } + InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } + + Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } + Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } + Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } + Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } }; /// Wrapper for hiding nodes and edges from a graph. @@ -344,7 +273,7 @@ NodeFilterMap* node_filter_map; EdgeFilterMap* edge_filter_map; public: -// SubGraphWrapper() : GraphWrapper(), filter_map(0) { } + SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, EdgeFilterMap& _edge_filter_map) : GraphWrapper(_graph), node_filter_map(&_node_filter_map), @@ -366,24 +295,10 @@ } operator Node() const { return Node(typename Graph::Node(n)); } }; -// class NodeIt : public Graph::NodeIt { -// // typedef typename Graph::NodeIt GraphNodeIt; -// public: -// NodeIt() { } -// NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } -// NodeIt(const Invalid& i) : Graph::NodeIt(i) { } -// NodeIt(const SubGraphWrapper& _G) : -// Graph::NodeIt(*(_G.graph)) { -// while (_G.graph->valid((*this)/*.GraphNodeIt*/) && -// !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/]) -// _G.graph->next((*this)/*.GraphNodeIt*/); -// } -// }; typedef typename GraphWrapper::Edge Edge; class OutEdgeIt { friend class GraphWrapper; friend class SubGraphWrapper; -// typedef typename Graph::OutEdgeIt GraphOutEdgeIt; typename Graph::OutEdgeIt e; public: OutEdgeIt() { } @@ -400,7 +315,6 @@ class InEdgeIt { friend class GraphWrapper; friend class SubGraphWrapper; -// typedef typename Graph::InEdgeIt GraphInEdgeIt; typename Graph::InEdgeIt e; public: InEdgeIt() { } @@ -418,7 +332,6 @@ class EdgeIt { friend class GraphWrapper; friend class SubGraphWrapper; -// typedef typename Graph::EdgeIt GraphEdgeIt; typename Graph::EdgeIt e; public: EdgeIt() { } @@ -431,51 +344,6 @@ } operator Edge() const { return Edge(typename Graph::Edge(e)); } }; -// operator Edge() const { return Edge(typename Graph::Edge(e)); } -// }; -// class OutEdgeIt : public Graph::OutEdgeIt { -// // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; -// public: -// OutEdgeIt() { } -// OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } -// OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } -// OutEdgeIt(const SubGraphWrapper& -// _G, const Node& n) : -// Graph::OutEdgeIt(*(_G.graph), n) { -// while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) && -// !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/]) -// _G.graph->next((*this)/*.GraphOutEdgeIt*/); -// } -// }; -// class InEdgeIt : public Graph::InEdgeIt { -// // typedef typename Graph::InEdgeIt GraphInEdgeIt; -// public: -// InEdgeIt() { } -// InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } -// InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } -// InEdgeIt(const SubGraphWrapper& _G, -// const Node& n) : -// Graph::InEdgeIt(*(_G.graph), n) { -// while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) && -// !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/]) -// _G.graph->next((*this)/*.GraphInEdgeIt*/); -// } -// }; -// // //typedef typename Graph::SymEdgeIt SymEdgeIt; -// class EdgeIt : public Graph::EdgeIt { -// // typedef typename Graph::EdgeIt GraphEdgeIt; -// public: -// EdgeIt() { } -// EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } -// EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } -// EdgeIt(const SubGraphWrapper& _G) : -// Graph::EdgeIt(*(_G.graph)) { -// while (_G.graph->valid((*this)/*.GraphEdgeIt*/) && -// !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/]) -// _G.graph->next((*this)/*.GraphEdgeIt*/); -// } -// }; - NodeIt& first(NodeIt& i) const { i=NodeIt(*this); return i; @@ -490,19 +358,6 @@ i=EdgeIt(*this); return i; } -// template I& first(I& i) const { -// graph->first(i); -// //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } -// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } -// return i; -// } -// template I& first(I& i, const P& p) const { -// graph->first(i, p); -// // while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } -// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } -// return i; -// } - NodeIt& next(NodeIt& i) const { graph->next(i.n); while (graph->valid(i) && !(*node_filter_map)[i.n]) { graph->next(i.n); } @@ -524,13 +379,6 @@ return i; } -// template I& next(I &i) const { -// graph->next(i); -// // while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); } -// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } -// return i; -// } - Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } @@ -544,201 +392,21 @@ bool hidden(const Node& n) const { return (*node_filter_map)[n]; } bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; } - -// 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; } }; -// //Subgraph on the same node-set and partial edge-set -// template -// class SubGraphWrapper : public GraphWrapper { -// protected: -// NodeFilterMap* node_filter_map; -// EdgeFilterMap* edge_filter_map; -// public: -// // SubGraphWrapper() : GraphWrapper(), filter_map(0) { } -// SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, -// EdgeFilterMap& _edge_filter_map) : -// GraphWrapper(_graph), node_filter_map(&_node_filter_map), -// edge_filter_map(&_edge_filter_map) { } + /// A wrapper for getting an undirected graph by forgetting the orientation of a directed one. - -// typedef typename Graph::Node Node; -// class NodeIt : public Graph::NodeIt { -// // typedef typename Graph::NodeIt GraphNodeIt; -// public: -// NodeIt() { } -// NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } -// NodeIt(const Invalid& i) : Graph::NodeIt(i) { } -// NodeIt(const SubGraphWrapper& _G) : -// Graph::NodeIt(*(_G.graph)) { -// while (_G.graph->valid((*this)/*.GraphNodeIt*/) && -// !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/]) -// _G.graph->next((*this)/*.GraphNodeIt*/); -// } -// }; -// typedef typename Graph::Edge Edge; -// class OutEdgeIt : public Graph::OutEdgeIt { -// // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; -// public: -// OutEdgeIt() { } -// OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } -// OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } -// OutEdgeIt(const SubGraphWrapper& -// _G, const Node& n) : -// Graph::OutEdgeIt(*(_G.graph), n) { -// while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) && -// !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/]) -// _G.graph->next((*this)/*.GraphOutEdgeIt*/); -// } -// }; -// class InEdgeIt : public Graph::InEdgeIt { -// // typedef typename Graph::InEdgeIt GraphInEdgeIt; -// public: -// InEdgeIt() { } -// InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } -// InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } -// InEdgeIt(const SubGraphWrapper& _G, -// const Node& n) : -// Graph::InEdgeIt(*(_G.graph), n) { -// while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) && -// !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/]) -// _G.graph->next((*this)/*.GraphInEdgeIt*/); -// } -// }; -// // //typedef typename Graph::SymEdgeIt SymEdgeIt; -// class EdgeIt : public Graph::EdgeIt { -// // typedef typename Graph::EdgeIt GraphEdgeIt; -// public: -// EdgeIt() { } -// EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } -// EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } -// EdgeIt(const SubGraphWrapper& _G) : -// Graph::EdgeIt(*(_G.graph)) { -// while (_G.graph->valid((*this)/*.GraphEdgeIt*/) && -// !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/]) -// _G.graph->next((*this)/*.GraphEdgeIt*/); -// } -// }; - -// NodeIt& first(NodeIt& i) const { -// i=NodeIt(*this); -// return i; -// } -// OutEdgeIt& first(OutEdgeIt& i, const Node& n) const { -// i=OutEdgeIt(*this, n); -// return i; -// } -// InEdgeIt& first(InEdgeIt& i, const Node& n) const { -// i=InEdgeIt(*this, n); -// return i; -// } -// EdgeIt& first(EdgeIt& i) const { -// i=EdgeIt(*this); -// return i; -// } - -// // template I& first(I& i) const { -// // graph->first(i); -// // //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } -// // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } -// // return i; -// // } -// // template I& first(I& i, const P& p) const { -// // graph->first(i, p); -// // // while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } -// // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } -// // return i; -// // } - -// NodeIt& next(NodeIt& i) const { -// graph->next(i); -// while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); } -// return i; -// } -// OutEdgeIt& next(OutEdgeIt& i) const { -// graph->next(i); -// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } -// return i; -// } -// InEdgeIt& next(InEdgeIt& i) const { -// graph->next(i); -// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } -// return i; -// } -// EdgeIt& next(EdgeIt& i) const { -// graph->next(i); -// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } -// return i; -// } - -// // template I& next(I &i) const { -// // graph->next(i); -// // // while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); } -// // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->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; } -// }; - + /// A wrapper for getting an undirected graph by forgetting the orientation of a directed one. template class UndirGraphWrapper : public GraphWrapper { -// protected: -// typedef typename Graph::Edge GraphEdge; -// typedef typename Graph::OutEdgeIt GraphOutEdgeIt; -// typedef typename Graph::InEdgeIt GraphInEdgeIt; public: typedef typename GraphWrapper::Node Node; typedef typename GraphWrapper::NodeIt NodeIt; typedef typename GraphWrapper::Edge Edge; typedef typename GraphWrapper::EdgeIt EdgeIt; -// UndirGraphWrapper() : GraphWrapper() { } UndirGraphWrapper(Graph& _graph) : GraphWrapper(_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 { friend class UndirGraphWrapper; bool out_or_in; //true iff out @@ -755,44 +423,14 @@ if (out_or_in) return Edge(out); else return Edge(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.graph->first(out, n); -// if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); } -// } -// }; //FIXME InEdgeIt 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.graph->first(out); else out=INVALID; -// while (_G.valid(v) && !_G.graph->valid(out)) { -// _G.graph->next(v); -// if (_G.valid(v)) _G.graph->first(out); -// } -// } -// }; - - NodeIt& first(NodeIt& i) const { - i=NodeIt(*this); return i; - } + using GraphWrapper::first; +// NodeIt& first(NodeIt& i) const { +// i=NodeIt(*this); return i; +// } OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { i=OutEdgeIt(*this, p); return i; } @@ -800,18 +438,15 @@ // InEdgeIt& first(InEdgeIt& i, const Node& p) const { // i=InEdgeIt(*this, p); return i; // } - EdgeIt& first(EdgeIt& i) const { - i=EdgeIt(*this); return i; - } +// EdgeIt& first(EdgeIt& i) const { +// i=EdgeIt(*this); return i; +// } -// template I& first(I& i) const { graph->first(i); return i; } -// template I& first(I& i, const P& p) const { -// graph->first(i, p); return i; } - - NodeIt& next(NodeIt& n) const { - GraphWrapper::next(n); - return n; - } + using GraphWrapper::next; +// NodeIt& next(NodeIt& n) const { +// GraphWrapper::next(n); +// return n; +// } OutEdgeIt& next(OutEdgeIt& e) const { if (e.out_or_in) { typename Graph::Node n=graph->tail(e.out); @@ -823,148 +458,25 @@ return e; } //FIXME InEdgeIt - EdgeIt& next(EdgeIt& e) const { - GraphWrapper::next(n); -// graph->next(e.e); - return e; - } - -// template I& next(I &i) const { graph->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 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); } - -// 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); } +// EdgeIt& next(EdgeIt& e) const { +// GraphWrapper::next(n); +// // graph->next(e.e); +// return e; +// } Node aNode(const OutEdgeIt& e) const { if (e.out_or_in) return graph->tail(e); else return graph->head(e); } Node bNode(const OutEdgeIt& e) const { if (e.out_or_in) return graph->head(e); else return graph->tail(e); } + }; -// Node addNode() const { return gw.addNode(); } + /// A wrapper for composing the residual graph for directed flow and circulation problems. -// FIXME: ez igy nem jo, mert nem -// Edge addEdge(const Node& tail, const Node& head) const { -// return graph->addEdge(tail, head); } - -// template void erase(const I& i) const { gw.erase(i); } - -// void clear() const { gw.clear(); } - -// template class NodeMap : public Graph::NodeMap { -// public: -// NodeMap(const UndirGraphWrapper& _G) : -// Graph::NodeMap(_G.gw) { } -// NodeMap(const UndirGraphWrapper& _G, T a) : -// Graph::NodeMap(_G.gw, a) { } -// }; - -// template class EdgeMap : -// public GraphWrapperSkeleton::EdgeMap { -// public: -// EdgeMap(const UndirGraphWrapper& _G) : -// GraphWrapperSkeleton::EdgeMap(_G.gw) { } -// EdgeMap(const UndirGraphWrapper& _G, T a) : -// Graph::EdgeMap(_G.gw, a) { } -// }; - }; - - - - - -// template -// class SymGraphWrapper -// { -// Graph* graph; - -// public: -// typedef Graph ParentGraph; - -// 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 head(const Edge& e) const { return graph->head(e); } -// Node tail(const Edge& e) const { return graph->tail(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& tail, const Node& head) { -// return graph->addEdge(tail, head); } - -// 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) { } -// }; - - - - + /// A wrapper for composing the residual graph for directed flow and circulation problems. template class ResGraphWrapper : public GraphWrapper { protected: -// typedef typename Graph::OutEdgeIt GraphOutEdgeIt; -// typedef typename Graph::InEdgeIt GraphInEdgeIt; -// typedef typename Graph::Edge GraphEdge; const CapacityMap* capacity; FlowMap* flow; public: @@ -1002,33 +514,7 @@ static_cast(v)); } }; -// class Edge { -// friend class ResGraphWrapper; -// protected: -// bool out_or_in; //true, iff out -// GraphOutEdgeIt out; -// GraphInEdgeIt 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); -// } -// operator GraphEdge() const { -// if (out_or_in) return(out); else return(in); -// } -// }; + class OutEdgeIt { friend class ResGraphWrapper; protected: @@ -1062,43 +548,6 @@ return Edge(in, this->forward); } }; -// class OutEdgeIt : public Edge { -// friend class ResGraphWrapper; -// public: -// OutEdgeIt() { } -// //FIXME -// OutEdgeIt(const Edge& e) : Edge(e) { } -// OutEdgeIt(const Invalid& i) : Edge(i) { } -// OutEdgeIt(const ResGraphWrapper& resG, Node v) : Edge() { -// resG.graph->first(out, v); -// while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } -// if (!resG.graph->valid(out)) { -// out_or_in=0; -// resG.graph->first(in, v); -// while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->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 -// class InEdgeIt : public Edge { }; class InEdgeIt { friend class ResGraphWrapper; @@ -1156,70 +605,11 @@ return Edge(e, this->forward); } }; -// 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.graph->first(v); -// if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID; -// while (resG.graph->valid(out) && !(resG.resCap(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->first(out, v); -// while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } -// } -// if (!resG.graph->valid(out)) { -// out_or_in=0; -// resG.graph->first(v); -// if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID; -// while (resG.graph->valid(in) && !(resG.resCap(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->first(in, v); -// while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->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=GraphInEdgeIt(); -// 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& i) const { - i=NodeIt(*this); return i; - } + using GraphWrapper::first; +// NodeIt& first(NodeIt& i) const { +// i=NodeIt(*this); return i; +// } OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { i=OutEdgeIt(*this, p); return i; } @@ -1230,8 +620,9 @@ EdgeIt& first(EdgeIt& i) const { i=EdgeIt(*this); return i; } - - NodeIt& next(NodeIt& n) const { GraphWrapper::next(n); return n; } + + using GraphWrapper::next; +// NodeIt& next(NodeIt& n) const { GraphWrapper::next(n); return n; } OutEdgeIt& next(OutEdgeIt& e) const { if (e.forward) { Node v=graph->aNode(e.out); @@ -1280,52 +671,6 @@ } return e; } -// EdgeIt& next(EdgeIt& e) const { -// if (e.out_or_in) { -// graph->next(e.out); -// while (graph->valid(e.out) && !(resCap(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->first(e.out, e.v); -// while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } -// } -// if (!graph->valid(e.out)) { -// e.out_or_in=0; -// graph->first(e.v); -// if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID; -// while (graph->valid(e.in) && !(resCap(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->first(e.in, e.v); -// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } -// } -// } -// } else { -// graph->next(e.in); -// while (graph->valid(e.in) && !(resCap(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->first(e.in, e.v); -// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->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 tail(Edge e) const { return ((e.forward) ? graph->tail(e) : graph->head(e)); } @@ -1337,8 +682,9 @@ Node bNode(OutEdgeIt e) const { return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); } - int nodeNum() const { return graph->nodeNum(); } +// int nodeNum() const { return graph->nodeNum(); } //FIXME + void edgeNum() const { } //int edgeNum() const { return graph->edgeNum(); } @@ -1378,24 +724,6 @@ // return ((*flow)[in]); // } -// template class NodeMap : public Graph::NodeMap { -// public: -// NodeMap(const ResGraphWrapper& _G) -// : Graph::NodeMap(_G.gw) { } -// NodeMap(const ResGraphWrapper& _G, -// T a) : Graph::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 Graph::EdgeMap forward_map, backward_map; @@ -1423,337 +751,9 @@ }; }; - + /// ErasingFirstGraphWrapper for blocking flows. -// template -// class ResGraphWrapper : public GraphWrapper { -// protected: -// typedef typename Graph::OutEdgeIt GraphOutEdgeIt; -// typedef typename Graph::InEdgeIt GraphInEdgeIt; -// typedef typename Graph::Edge GraphEdge; -// FlowMap* flow; -// const CapacityMap* capacity; -// public: - -// ResGraphWrapper(Graph& _graph, FlowMap& _flow, -// const CapacityMap& _capacity) : -// GraphWrapper(_graph), flow(&_flow), capacity(&_capacity) { } - -// class Edge; -// class OutEdgeIt; -// friend class Edge; -// friend class OutEdgeIt; - -// typedef typename GraphWrapper::Node Node; -// typedef typename GraphWrapper::NodeIt NodeIt; -// class Edge { -// friend class ResGraphWrapper; -// protected: -// bool out_or_in; //true, iff out -// GraphOutEdgeIt out; -// GraphInEdgeIt 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); -// } -// operator GraphEdge() const { -// if (out_or_in) return(out); else return(in); -// } -// }; -// class OutEdgeIt : public Edge { -// friend class ResGraphWrapper; -// public: -// OutEdgeIt() { } -// //FIXME -// OutEdgeIt(const Edge& e) : Edge(e) { } -// OutEdgeIt(const Invalid& i) : Edge(i) { } -// OutEdgeIt(const ResGraphWrapper& resG, Node v) : Edge() { -// resG.graph->first(out, v); -// while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } -// if (!resG.graph->valid(out)) { -// out_or_in=0; -// resG.graph->first(in, v); -// while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->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 -// // class InEdgeIt : public Edge { }; - -// 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.graph->first(v); -// if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID; -// while (resG.graph->valid(out) && !(resG.resCap(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->first(out, v); -// while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } -// } -// if (!resG.graph->valid(out)) { -// out_or_in=0; -// resG.graph->first(v); -// if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID; -// while (resG.graph->valid(in) && !(resG.resCap(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->first(in, v); -// while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->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=GraphInEdgeIt(); -// // 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& i) const { -// i=NodeIt(*this); -// return i; -// } -// OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { -// i=OutEdgeIt(*this, p); -// return i; -// } -// //FIXME Not yet implemented -// //InEdgeIt& first(InEdgeIt& i, const Node& p) const { -// //i=InEdgeIt(*this, p); -// // return i; -// //} -// EdgeIt& first(EdgeIt& e) const { -// e=EdgeIt(*this); -// return e; -// } - -// NodeIt& next(NodeIt& n) const { graph->next(n); return n; } -// OutEdgeIt& next(OutEdgeIt& e) const { -// if (e.out_or_in) { -// Node v=graph->aNode(e.out); -// graph->next(e.out); -// while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } -// if (!graph->valid(e.out)) { -// e.out_or_in=0; -// graph->first(e.in, v); -// while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } -// } -// } else { -// graph->next(e.in); -// while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } -// } -// return e; -// } -// //FIXME Not yet implemented -// //InEdgeIt& next(InEdgeIt& e) const { -// // return e; -// //} -// EdgeIt& next(EdgeIt& e) const { -// if (e.out_or_in) { -// graph->next(e.out); -// while (graph->valid(e.out) && !(resCap(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->first(e.out, e.v); -// while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } -// } -// if (!graph->valid(e.out)) { -// e.out_or_in=0; -// graph->first(e.v); -// if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID; -// while (graph->valid(e.in) && !(resCap(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->first(e.in, e.v); -// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } -// } -// } -// } else { -// graph->next(e.in); -// while (graph->valid(e.in) && !(resCap(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->first(e.in, e.v); -// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->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 tail(Edge e) const { -// return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } -// Node head(Edge e) const { -// return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } - -// Node aNode(OutEdgeIt e) const { -// return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } -// Node bNode(OutEdgeIt e) const { -// return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } - -// int nodeNum() const { return graph->nodeNum(); } -// //FIXME -// //int edgeNum() const { return graph->edgeNum(); } - - -// int id(Node v) const { return graph->id(v); } - -// bool valid(Node n) const { return graph->valid(n); } -// bool valid(Edge e) const { -// return e.out_or_in ? graph->valid(e.out) : graph->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); -// flow->set(e.out, (*flow)[e.out]+a); -// else -// // flow->set(e.in, flow->get(e.in)-a); -// flow->set(e.in, (*flow)[e.in]-a); -// } - -// Number resCap(const Edge& e) const { -// if (e.out_or_in) -// // return (capacity->get(e.out)-flow->get(e.out)); -// return ((*capacity)[e.out]-(*flow)[e.out]); -// else -// // return (flow->get(e.in)); -// return ((*flow)[e.in]); -// } - -// Number resCap(GraphOutEdgeIt out) const { -// // return (capacity->get(out)-flow->get(out)); -// return ((*capacity)[out]-(*flow)[out]); -// } - -// Number resCap(GraphInEdgeIt in) const { -// // return (flow->get(in)); -// return ((*flow)[in]); -// } - -// // template class NodeMap : public Graph::NodeMap { -// // public: -// // NodeMap(const ResGraphWrapper& _G) -// // : Graph::NodeMap(_G.gw) { } -// // NodeMap(const ResGraphWrapper& _G, -// // T a) : Graph::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 Graph::EdgeMap forward_map, backward_map; -// public: -// EdgeMap(const ResGraphWrapper& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } -// EdgeMap(const ResGraphWrapper& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), 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 operator[](Edge e) const { -// if (e.out_or_in) -// return forward_map[e.out]; -// else -// return backward_map[e.in]; -// } -// // T get(Edge e) const { -// // if (e.out_or_in) -// // return forward_map.get(e.out); -// // else -// // return backward_map.get(e.in); -// // } -// }; -// }; - - - //ErasingFirstGraphWrapper for blocking flows + /// ErasingFirstGraphWrapper for blocking flows. template class ErasingFirstGraphWrapper : public GraphWrapper { protected: @@ -1764,18 +764,18 @@ GraphWrapper(_graph), first_out_edges(&_first_out_edges) { } typedef typename GraphWrapper::Node Node; - class NodeIt { - friend class GraphWrapper; - friend class ErasingFirstGraphWrapper; - typename Graph::NodeIt n; - public: - NodeIt() { } - NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } - NodeIt(const Invalid& i) : n(i) { } - NodeIt(const ErasingFirstGraphWrapper& _G) : - n(*(_G.graph)) { } - operator Node() const { return Node(typename Graph::Node(n)); } - }; +// class NodeIt { +// friend class GraphWrapper; +// friend class ErasingFirstGraphWrapper; +// typename Graph::NodeIt n; +// public: +// NodeIt() { } +// NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } +// NodeIt(const Invalid& i) : n(i) { } +// NodeIt(const ErasingFirstGraphWrapper& _G) : +// n(*(_G.graph)) { } +// operator Node() const { return Node(typename Graph::Node(n)); } +// }; typedef typename GraphWrapper::Edge Edge; class OutEdgeIt { friend class GraphWrapper; @@ -1820,9 +820,10 @@ operator Edge() const { return Edge(typename Graph::Edge(e)); } }; - NodeIt& first(NodeIt& i) const { - i=NodeIt(*this); return i; - } + using GraphWrapper::first; +// NodeIt& first(NodeIt& i) const { +// i=NodeIt(*this); return i; +// } OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { i=OutEdgeIt(*this, p); return i; } @@ -1833,21 +834,8 @@ i=EdgeIt(*this); return i; } -// template I& first(I& i) const { -// graph->first(i); -// return i; -// } -// OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { -// // e=first_out_edges->get(n); -// e=(*first_out_edges)[n]; -// return e; -// } -// template I& first(I& i, const P& p) const { -// graph->first(i, p); -// return i; -// } - - NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } + using GraphWrapper::next; +// NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } @@ -1857,17 +845,6 @@ Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } -// template I& next(I &i) const { -// graph->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); @@ -1875,268 +852,6 @@ } }; -// //ErasingFirstGraphWrapper for blocking flows -// template -// class ErasingFirstGraphWrapper : public GraphWrapper { -// protected: -// FirstOutEdgesMap* first_out_edges; -// public: -// ErasingFirstGraphWrapper(Graph& _graph, -// FirstOutEdgesMap& _first_out_edges) : -// GraphWrapper(_graph), first_out_edges(&_first_out_edges) { } - -// 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 ErasingFirstGraphWrapper& _G) : -// Graph::NodeIt(*(_G.graph)) { } -// }; -// typedef typename Graph::Edge Edge; -// 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 ErasingFirstGraphWrapper& _G, -// const Node& n) : -// Graph::OutEdgeIt((*_G.first_out_edges)[n]) { } -// }; -// 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 ErasingFirstGraphWrapper& _G, -// const Node& n) : -// Graph::InEdgeIt(*(_G.graph), n) { } -// }; -// //typedef typename Graph::SymEdgeIt SymEdgeIt; -// 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 ErasingFirstGraphWrapper& _G) : -// Graph::EdgeIt(*(_G.graph)) { } -// }; - -// NodeIt& first(NodeIt& i) const { -// i=NodeIt(*this); -// return i; -// } -// OutEdgeIt& first(OutEdgeIt& i, const Node& n) const { -// i=OutEdgeIt(*this, n); -// // i=(*first_out_edges)[n]; -// return i; -// } -// InEdgeIt& first(InEdgeIt& i, const Node& n) const { -// i=InEdgeIt(*this, n); -// return i; -// } -// EdgeIt& first(EdgeIt& i) const { -// i=EdgeIt(*this); -// return i; -// } - -// // template I& first(I& i) const { -// // graph->first(i); -// // return i; -// // } -// // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { -// // // e=first_out_edges->get(n); -// // e=(*first_out_edges)[n]; -// // return e; -// // } -// // template I& first(I& i, const P& p) const { -// // graph->first(i, p); -// // return i; -// // } - -// NodeIt& next(NodeIt& i) const { -// graph->next(i); -// return i; -// } -// OutEdgeIt& next(OutEdgeIt& i) const { -// graph->next(i); -// return i; -// } -// InEdgeIt& next(InEdgeIt& i) const { -// graph->next(i); -// return i; -// } -// EdgeIt& next(EdgeIt& i) const { -// graph->next(i); -// return i; -// } - -// // template I& next(I &i) const { -// // graph->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->tail(e), f); -// } -// }; - - -// // FIXME: comparison should be made better!!! -// template -// class ResGraphWrapper -// { -// Graph* graph; - -// public: -// typedef Graph ParentGraph; - -// 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 head(const Edge& e) const { return gw.head(e); } -// Node tail(const Edge& e) const { return gw.tail(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& tail, const Node& head) { -// return gw.addEdge(tail, head); } - -// 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 hugo #endif //HUGO_GRAPH_WRAPPER_H