diff -r 66dd225ca128 -r 86b42ec55f3e src/hugo/graph_wrapper.h --- a/src/hugo/graph_wrapper.h Fri Sep 17 07:02:16 2004 +0000 +++ b/src/hugo/graph_wrapper.h Fri Sep 17 12:23:09 2004 +0000 @@ -97,7 +97,6 @@ GraphWrapper(Graph& _graph) : graph(&_graph) { } GraphWrapper(const GraphWrapper& gw) : graph(gw.graph) { } -// Graph& getGraph() const { return *graph; } typedef typename Graph::Node Node; class NodeIt : public Node { @@ -105,7 +104,6 @@ friend class GraphWrapper; public: NodeIt() { } - // NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { } NodeIt(Invalid i) : Node(i) { } NodeIt(const GraphWrapper& _gw) : Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { } @@ -123,7 +121,6 @@ friend class GraphWrapper; public: OutEdgeIt() { } - //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { } OutEdgeIt(Invalid i) : Edge(i) { } OutEdgeIt(const GraphWrapper& _gw, const Node& n) : Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { } @@ -140,7 +137,6 @@ friend class GraphWrapper; public: InEdgeIt() { } - //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { } InEdgeIt(Invalid i) : Edge(i) { } InEdgeIt(const GraphWrapper& _gw, const Node& n) : Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { } @@ -152,13 +148,11 @@ return *this; } }; - //typedef typename Graph::SymEdgeIt SymEdgeIt; class EdgeIt : public Edge { const GraphWrapper* gw; friend class GraphWrapper; public: EdgeIt() { } - //EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { } EdgeIt(Invalid i) : Edge(i) { } EdgeIt(const GraphWrapper& _gw) : Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { } @@ -184,29 +178,14 @@ i=EdgeIt(*this); 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; } - Node tail(const Edge& e) const { return Node(graph->tail(static_cast(e))); } Node head(const Edge& e) const { return Node(graph->head(static_cast(e))); } -// bool valid(const Node& n) const { -// return graph->valid(static_cast(n)); } -// bool valid(const Edge& e) const { -// return graph->valid(static_cast(e)); } - int nodeNum() const { return graph->nodeNum(); } int edgeNum() const { return graph->edgeNum(); } -// 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)); } - Node addNode() const { return Node(graph->addNode()); } Edge addEdge(const Node& tail, const Node& head) const { return Edge(graph->addEdge(tail, head)); } @@ -260,7 +239,6 @@ friend class GraphWrapper; public: OutEdgeIt() { } - //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { } OutEdgeIt(Invalid i) : Edge(i) { } OutEdgeIt(const RevGraphWrapper& _gw, const Node& n) : Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { } @@ -277,7 +255,6 @@ friend class GraphWrapper; public: InEdgeIt() { } - //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { } InEdgeIt(Invalid i) : Edge(i) { } InEdgeIt(const RevGraphWrapper& _gw, const Node& n) : Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { } @@ -298,19 +275,6 @@ i=InEdgeIt(*this, p); return i; } -// using GraphWrapper::next; -// OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; } -// InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } - -// Node aNode(const OutEdgeIt& e) const { -// return Node(this->graph->aNode(e.e)); } -// Node aNode(const InEdgeIt& e) const { -// return Node(this->graph->aNode(e.e)); } -// Node bNode(const OutEdgeIt& e) const { -// return Node(this->graph->bNode(e.e)); } -// Node bNode(const InEdgeIt& e) const { -// return Node(this->graph->bNode(e.e)); } - Node tail(const Edge& e) const { return GraphWrapper::head(e); } Node head(const Edge& e) const { @@ -363,7 +327,6 @@ friend class SubGraphWrapper; public: NodeIt() { } - // NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { } NodeIt(Invalid i) : Node(i) { } NodeIt(const SubGraphWrapper& _gw) : Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { @@ -391,7 +354,6 @@ friend class SubGraphWrapper; public: OutEdgeIt() { } - // OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { } OutEdgeIt(Invalid i) : Edge(i) { } OutEdgeIt(const SubGraphWrapper& _gw, const Node& n) : Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { @@ -445,7 +407,6 @@ friend class SubGraphWrapper; public: EdgeIt() { } - // EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { } EdgeIt(Invalid i) : Edge(i) { } EdgeIt(const SubGraphWrapper& _gw) : Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { @@ -481,40 +442,6 @@ i=EdgeIt(*this); return i; } -// NodeIt& next(NodeIt& i) const { -// this->graph->next(i.n); -// while (this->graph->valid(i) && !(*node_filter_map)[i.n]) { -// this->graph->next(i.n); } -// return i; -// } -// OutEdgeIt& next(OutEdgeIt& i) const { -// this->graph->next(i.e); -// while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { -// this->graph->next(i.e); } -// return i; -// } -// InEdgeIt& next(InEdgeIt& i) const { -// this->graph->next(i.e); -// while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { -// this->graph->next(i.e); } -// return i; -// } -// EdgeIt& next(EdgeIt& i) const { -// this->graph->next(i.e); -// while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { -// this->graph->next(i.e); } -// return i; -// } - -// Node aNode(const OutEdgeIt& e) const { -// return Node(this->graph->aNode(e.e)); } -// Node aNode(const InEdgeIt& e) const { -// return Node(this->graph->aNode(e.e)); } -// Node bNode(const OutEdgeIt& e) const { -// return Node(this->graph->bNode(e.e)); } -// Node bNode(const InEdgeIt& e) const { -// return Node(this->graph->bNode(e.e)); } - /// This function hides \c n in the graph, i.e. the iteration /// jumps over it. This is done by simply setting the value of \c n /// to be false in the corresponding node-map. @@ -562,13 +489,6 @@ -// /// \brief A wrapper for forgetting the orientation of a graph. -// /// -// /// A wrapper for getting an undirected graph by forgetting -// /// the orientation of a directed one. -// /// -// /// \author Marton Makai -// /// does not work in the new concept. template class UndirGraphWrapper : public GraphWrapper { public: @@ -601,29 +521,15 @@ } }; -//FIXME InEdgeIt typedef OutEdgeIt InEdgeIt; 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; } -//FIXME -// InEdgeIt& first(InEdgeIt& i, const Node& p) const { -// i=InEdgeIt(*this, p); return i; -// } -// EdgeIt& first(EdgeIt& i) const { -// i=EdgeIt(*this); return i; -// } 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=this->graph->tail(e.out); @@ -635,12 +541,6 @@ } return e; } - //FIXME InEdgeIt -// 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 this->graph->tail(e); else @@ -756,17 +656,6 @@ Edge(const typename Graph::Edge& e, bool _backward/*=false*/) : Graph::Edge(e), backward(_backward) { } Edge(Invalid i) : Graph::Edge(i), backward(true) { } -//the unique invalid iterator -// friend bool operator==(const Edge& u, const Edge& v) { -// return (u.backward==v.backward && -// static_cast(u)== -// static_cast(v)); -// } -// friend bool operator!=(const Edge& u, const Edge& v) { -// return (u.backward!=v.backward || -// static_cast(u)!= -// static_cast(v)); -// } bool operator==(const Edge& v) const { return (this->backward==v.backward && static_cast(*this)== @@ -788,7 +677,6 @@ public: OutEdgeIt() { } OutEdgeIt(Invalid i) : Edge(i) { } -//the unique invalid iterator OutEdgeIt(const SubBidirGraphWrapper& _gw, const Node& n) : Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) { @@ -846,7 +734,6 @@ public: InEdgeIt() { } InEdgeIt(Invalid i) : Edge(i) { } -//the unique invalid iterator InEdgeIt(const SubBidirGraphWrapper& _gw, const Node& n) : Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) { @@ -904,7 +791,6 @@ public: EdgeIt() { } EdgeIt(Invalid i) : Edge(i) { } -//the unique invalid iterator EdgeIt(const SubBidirGraphWrapper& _gw) : Edge(typename Graph::OutEdgeIt(*(_gw.graph)), false), gw(&_gw) { @@ -953,9 +839,6 @@ }; 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; } @@ -966,85 +849,12 @@ i=EdgeIt(*this); return i; } -// using GraphWrapper::next; -// // NodeIt& next(NodeIt& n) const { GraphWrapper::next(n); return n; } -// OutEdgeIt& next(OutEdgeIt& e) const { -// if (!e.backward) { -// Node v=this->graph->aNode(e.out); -// this->graph->next(e.out); -// while(this->graph->valid(e.out) && !(*forward_filter)[e]) { -// this->graph->next(e.out); } -// if (!this->graph->valid(e.out)) { -// e.backward=true; -// this->graph->first(e.in, v); -// while(this->graph->valid(e.in) && !(*backward_filter)[e]) { -// this->graph->next(e.in); } -// } -// } else { -// this->graph->next(e.in); -// while(this->graph->valid(e.in) && !(*backward_filter)[e]) { -// this->graph->next(e.in); } -// } -// return e; -// } -// // FIXME Not tested -// InEdgeIt& next(InEdgeIt& e) const { -// if (!e.backward) { -// Node v=this->graph->aNode(e.in); -// this->graph->next(e.in); -// while(this->graph->valid(e.in) && !(*forward_filter)[e]) { -// this->graph->next(e.in); } -// if (!this->graph->valid(e.in)) { -// e.backward=true; -// this->graph->first(e.out, v); -// while(this->graph->valid(e.out) && !(*backward_filter)[e]) { -// this->graph->next(e.out); } -// } -// } else { -// this->graph->next(e.out); -// while(this->graph->valid(e.out) && !(*backward_filter)[e]) { -// this->graph->next(e.out); } -// } -// return e; -// } -// EdgeIt& next(EdgeIt& e) const { -// if (!e.backward) { -// this->graph->next(e.e); -// while(this->graph->valid(e.e) && !(*forward_filter)[e]) { -// this->graph->next(e.e); } -// if (!this->graph->valid(e.e)) { -// e.backward=true; -// this->graph->first(e.e); -// while(this->graph->valid(e.e) && !(*backward_filter)[e]) { -// this->graph->next(e.e); } -// } -// } else { -// this->graph->next(e.e); -// while(this->graph->valid(e.e) && !(*backward_filter)[e]) { -// this->graph->next(e.e); } -// } -// return e; -// } Node tail(Edge e) const { return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); } Node head(Edge e) const { return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); } -// Node aNode(OutEdgeIt e) const { -// return ((!e.backward) ? this->graph->aNode(e.out) : -// this->graph->aNode(e.in)); } -// Node bNode(OutEdgeIt e) const { -// return ((!e.backward) ? this->graph->bNode(e.out) : -// this->graph->bNode(e.in)); } - -// Node aNode(InEdgeIt e) const { -// return ((!e.backward) ? this->graph->aNode(e.in) : -// this->graph->aNode(e.out)); } -// Node bNode(InEdgeIt e) const { -// return ((!e.backward) ? this->graph->bNode(e.in) : -// this->graph->bNode(e.out)); } - /// Gives back the opposite edge. Edge opposite(const Edge& e) const { Edge f=e; @@ -1095,12 +905,6 @@ forward_map.update(); backward_map.update(); } -// T get(Edge e) const { -// if (e.out_or_in) -// return forward_map.get(e.out); -// else -// return backward_map.get(e.in); -// } }; @@ -1182,7 +986,6 @@ const CapacityMap& _capacity, const FlowMap& _flow) : /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { } ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { } - //void setGraph(const Graph& _graph) { graph=&_graph; } void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; } void setFlow(const FlowMap& _flow) { flow=&_flow; } bool operator[](const typename Graph::Edge& e) const { @@ -1193,7 +996,6 @@ template class ResBackwardFilter { - //const Graph* graph; const CapacityMap* capacity; const FlowMap* flow; public: @@ -1201,7 +1003,6 @@ const CapacityMap& _capacity, const FlowMap& _flow) : /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { } ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { } - //void setGraph(const Graph& _graph) { graph=&_graph; } void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; } void setFlow(const FlowMap& _flow) { flow=&_flow; } bool operator[](const typename Graph::Edge& e) const { @@ -1242,12 +1043,6 @@ forward_filter.setFlow(_flow); backward_filter.setFlow(_flow); } -// /// \bug does graph reference needed in filtermaps?? -// void setGraph(const Graph& _graph) { -// Parent::setGraph(_graph); -// forward_filter.setGraph(_graph); -// backward_filter.setGraph(_graph); -// } public: ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, FlowMap& _flow) : @@ -1261,29 +1056,13 @@ typedef typename Parent::Edge Edge; - // bool forward(const Parent::Edge& e) const { return Parent::forward(e); } - //bool backward(const Edge& e) const { return e.backward; } - void augment(const Edge& e, Number a) const { if (Parent::forward(e)) -// flow->set(e.out, flow->get(e.out)+a); flow->set(e, (*flow)[e]+a); else - //flow->set(e.in, flow->get(e.in)-a); flow->set(e, (*flow)[e]-a); } - /// \deprecated - /// - Number resCap(const Edge& e) const { - if (Parent::forward(e)) -// return (capacity->get(e.out)-flow->get(e.out)); - return ((*capacity)[e]-(*flow)[e]); - else -// return (flow->get(e.in)); - return ((*flow)[e]); - } - /// \brief Residual capacity map. /// /// In generic residual graphs the residual capacity can be obtained as a map. Not tested. @@ -1297,14 +1076,10 @@ res_graph(&_res_graph) { } Number operator[](const Edge& e) const { if (res_graph->forward(e)) - // return (capacity->get(e.out)-flow->get(e.out)); return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e]; else - // return (flow->get(e.in)); return (*(res_graph->flow))[e]; } - /// \bug not needed with dynamic maps, or does it? - void update() { } }; KEEP_MAPS(Parent, ResGraphWrapper); @@ -1341,7 +1116,6 @@ const ErasingFirstGraphWrapper* gw; public: OutEdgeIt() { } - //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { } OutEdgeIt(Invalid i) : Edge(i) { } OutEdgeIt(const ErasingFirstGraphWrapper& _gw, const Node& n) : @@ -1355,64 +1129,11 @@ return *this; } }; -// class InEdgeIt { -// friend class GraphWrapper; -// friend class ErasingFirstGraphWrapper; -// // typedef typename Graph::InEdgeIt GraphInEdgeIt; -// typename Graph::InEdgeIt e; -// public: -// InEdgeIt() { } -// InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } -// InEdgeIt(const Invalid& i) : e(i) { } -// InEdgeIt(const ErasingFirstGraphWrapper& _G, -// const Node& _n) : -// e(*(_G.graph), typename Graph::Node(_n)) { } -// operator Edge() const { return Edge(typename Graph::Edge(e)); } -// }; - //typedef typename Graph::SymEdgeIt SymEdgeIt; -// class EdgeIt { -// friend class GraphWrapper; -// friend class ErasingFirstGraphWrapper; -// // typedef typename Graph::EdgeIt GraphEdgeIt; -// typename Graph::EdgeIt e; -// public: -// EdgeIt() { } -// EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } -// EdgeIt(const Invalid& i) : e(i) { } -// EdgeIt(const ErasingFirstGraphWrapper& _G) : -// e(*(_G.graph)) { } -// operator Edge() const { return Edge(typename Graph::Edge(e)); } -// }; 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; } -// InEdgeIt& first(InEdgeIt& i, const Node& p) const { -// i=InEdgeIt(*this, p); return i; -// } -// EdgeIt& first(EdgeIt& i) const { -// i=EdgeIt(*this); return i; -// } - -// using GraphWrapper::next; -// // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } -// OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; } -// InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } -// EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; } - -// Node aNode(const OutEdgeIt& e) const { -// return Node(this->graph->aNode(e.e)); } -// Node aNode(const InEdgeIt& e) const { -// return Node(this->graph->aNode(e.e)); } -// Node bNode(const OutEdgeIt& e) const { -// return Node(this->graph->bNode(e.e)); } -// Node bNode(const InEdgeIt& e) const { -// return Node(this->graph->bNode(e.e)); } - void erase(const Edge& e) const { Node n=tail(e); typename Graph::OutEdgeIt f(*Parent::graph, n);