150 i=InEdgeIt(*this, p); return i; |
147 i=InEdgeIt(*this, p); return i; |
151 } |
148 } |
152 EdgeIt& first(EdgeIt& i) const { |
149 EdgeIt& first(EdgeIt& i) const { |
153 i=EdgeIt(*this); return i; |
150 i=EdgeIt(*this); return i; |
154 } |
151 } |
155 // template<typename I> I& first(I& i) const { |
152 |
156 // i=I(*this); |
|
157 // return i; |
|
158 // } |
|
159 // template<typename I, typename P> I& first(I& i, const P& p) const { |
|
160 // i=I(*this, p); |
|
161 // return i; |
|
162 // } |
|
163 |
|
164 NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } |
153 NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } |
165 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } |
154 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } |
166 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } |
155 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } |
167 EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } |
156 EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } |
168 // template<typename I> I& next(I &i) const { graph->next(i); return i; } |
|
169 // template< typename It > It first() const { |
|
170 // It e; this->first(e); return e; } |
|
171 |
|
172 // template< typename It > It first(const Node& v) const { |
|
173 // It e; this->first(e, v); return e; } |
|
174 |
157 |
175 Node head(const Edge& e) const { |
158 Node head(const Edge& e) const { |
176 return Node(graph->head(static_cast<typename Graph::Edge>(e))); } |
159 return Node(graph->head(static_cast<typename Graph::Edge>(e))); } |
177 Node tail(const Edge& e) const { |
160 Node tail(const Edge& e) const { |
178 return Node(graph->tail(static_cast<typename Graph::Edge>(e))); } |
161 return Node(graph->tail(static_cast<typename Graph::Edge>(e))); } |
179 |
162 |
180 bool valid(const Node& n) const { |
163 bool valid(const Node& n) const { |
181 return graph->valid(static_cast<typename Graph::Node>(n)); } |
164 return graph->valid(static_cast<typename Graph::Node>(n)); } |
182 bool valid(const Edge& e) const { |
165 bool valid(const Edge& e) const { |
183 return graph->valid(static_cast<typename Graph::Edge>(e)); } |
166 return graph->valid(static_cast<typename Graph::Edge>(e)); } |
184 // template<typename I> bool valid(const I& i) const { |
|
185 // return graph->valid(i); } |
|
186 |
|
187 //template<typename I> void setInvalid(const I &i); |
|
188 //{ return graph->setInvalid(i); } |
|
189 |
167 |
190 int nodeNum() const { return graph->nodeNum(); } |
168 int nodeNum() const { return graph->nodeNum(); } |
191 int edgeNum() const { return graph->edgeNum(); } |
169 int edgeNum() const { return graph->edgeNum(); } |
192 |
170 |
193 Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
171 Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
194 Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
172 Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
195 Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
173 Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
196 Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
174 Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
197 // template<typename I> Node aNode(const I& e) const { |
|
198 // return Node(graph->aNode(e.e)); } |
|
199 // template<typename I> Node bNode(const I& e) const { |
|
200 // return Node(graph->bNode(e.e)); } |
|
201 |
175 |
202 Node addNode() const { return Node(graph->addNode()); } |
176 Node addNode() const { return Node(graph->addNode()); } |
203 Edge addEdge(const Node& tail, const Node& head) const { |
177 Edge addEdge(const Node& tail, const Node& head) const { |
204 return Edge(graph->addEdge(tail, head)); } |
178 return Edge(graph->addEdge(tail, head)); } |
205 |
179 |
206 void erase(const Node& i) const { graph->erase(i); } |
180 void erase(const Node& i) const { graph->erase(i); } |
207 void erase(const Edge& i) const { graph->erase(i); } |
181 void erase(const Edge& i) const { graph->erase(i); } |
208 // template<typename I> void erase(const I& i) const { graph->erase(i); } |
|
209 |
182 |
210 void clear() const { graph->clear(); } |
183 void clear() const { graph->clear(); } |
211 |
184 |
212 template<typename T> class NodeMap : public Graph::NodeMap<T> { |
185 template<typename T> class NodeMap : public Graph::NodeMap<T> { |
213 public: |
186 public: |
224 EdgeMap(const GraphWrapper<Graph>& _G, T a) : |
197 EdgeMap(const GraphWrapper<Graph>& _G, T a) : |
225 Graph::EdgeMap<T>(*(_G.graph), a) { } |
198 Graph::EdgeMap<T>(*(_G.graph), a) { } |
226 }; |
199 }; |
227 }; |
200 }; |
228 |
201 |
229 |
202 /// A graph wrapper which reverses the orientation of the edges. |
230 // template<typename Graph> |
203 |
231 // class RevGraphWrapper |
204 /// A graph wrapper which reverses the orientation of the edges. |
232 // { |
|
233 // protected: |
|
234 // Graph* graph; |
|
235 |
|
236 // public: |
|
237 // typedef Graph ParentGraph; |
|
238 |
|
239 // typedef typename Graph::Node Node; |
|
240 // typedef typename Graph::NodeIt NodeIt; |
|
241 |
|
242 // typedef typename Graph::Edge Edge; |
|
243 // typedef typename Graph::OutEdgeIt InEdgeIt; |
|
244 // typedef typename Graph::InEdgeIt OutEdgeIt; |
|
245 // //typedef typename Graph::SymEdgeIt SymEdgeIt; |
|
246 // typedef typename Graph::EdgeIt EdgeIt; |
|
247 |
|
248 // //RevGraphWrapper() : graph(0) { } |
|
249 // RevGraphWrapper(Graph& _graph) : graph(&_graph) { } |
|
250 |
|
251 // void setGraph(Graph& _graph) { graph = &_graph; } |
|
252 // Graph& getGraph() const { return (*graph); } |
|
253 |
|
254 // template<typename I> I& first(I& i) const { return graph->first(i); } |
|
255 // template<typename I, typename P> I& first(I& i, const P& p) const { |
|
256 // return graph->first(i, p); } |
|
257 |
|
258 // template<typename I> I& next(I &i) const { return graph->next(i); } |
|
259 |
|
260 // template< typename It > It first() const { |
|
261 // It e; first(e); return e; } |
|
262 |
|
263 // template< typename It > It first(const Node& v) const { |
|
264 // It e; first(e, v); return e; } |
|
265 |
|
266 // Node head(const Edge& e) const { return graph->tail(e); } |
|
267 // Node tail(const Edge& e) const { return graph->head(e); } |
|
268 |
|
269 // template<typename I> bool valid(const I& i) const |
|
270 // { return graph->valid(i); } |
|
271 |
|
272 // //template<typename I> void setInvalid(const I &i); |
|
273 // //{ return graph->setInvalid(i); } |
|
274 |
|
275 // template<typename I> Node aNode(const I& e) const { |
|
276 // return graph->aNode(e); } |
|
277 // template<typename I> Node bNode(const I& e) const { |
|
278 // return graph->bNode(e); } |
|
279 |
|
280 // Node addNode() const { return graph->addNode(); } |
|
281 // Edge addEdge(const Node& tail, const Node& head) const { |
|
282 // return graph->addEdge(tail, head); } |
|
283 |
|
284 // int nodeNum() const { return graph->nodeNum(); } |
|
285 // int edgeNum() const { return graph->edgeNum(); } |
|
286 |
|
287 // template<typename I> void erase(const I& i) const { graph->erase(i); } |
|
288 |
|
289 // void clear() const { graph->clear(); } |
|
290 |
|
291 // template<typename T> class NodeMap : public Graph::NodeMap<T> { |
|
292 // public: |
|
293 // NodeMap(const RevGraphWrapper<Graph>& _G) : |
|
294 // Graph::NodeMap<T>(_G.getGraph()) { } |
|
295 // NodeMap(const RevGraphWrapper<Graph>& _G, T a) : |
|
296 // Graph::NodeMap<T>(_G.getGraph(), a) { } |
|
297 // }; |
|
298 |
|
299 // template<typename T> class EdgeMap : public Graph::EdgeMap<T> { |
|
300 // public: |
|
301 // EdgeMap(const RevGraphWrapper<Graph>& _G) : |
|
302 // Graph::EdgeMap<T>(_G.getGraph()) { } |
|
303 // EdgeMap(const RevGraphWrapper<Graph>& _G, T a) : |
|
304 // Graph::EdgeMap<T>(_G.getGraph(), a) { } |
|
305 // }; |
|
306 // }; |
|
307 |
|
308 |
|
309 template<typename Graph> |
205 template<typename Graph> |
310 class RevGraphWrapper : public GraphWrapper<Graph> { |
206 class RevGraphWrapper : public GraphWrapper<Graph> { |
311 public: |
207 public: |
|
208 |
|
209 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } |
|
210 |
312 typedef typename GraphWrapper<Graph>::Node Node; |
211 typedef typename GraphWrapper<Graph>::Node Node; |
313 typedef typename GraphWrapper<Graph>::Edge Edge; |
212 typedef typename GraphWrapper<Graph>::Edge Edge; |
314 //FIXME |
|
315 //If Graph::OutEdgeIt is not defined |
213 //If Graph::OutEdgeIt is not defined |
316 //and we do not want to use RevGraphWrapper::InEdgeIt, |
214 //and we do not want to use RevGraphWrapper::InEdgeIt, |
317 //this won't work, because of typedef |
215 //the typdef techinque does not work. |
318 //OR |
216 //Unfortunately all the typedefs are instantiated in templates. |
319 //graphs have to define their non-existing iterators to void |
217 //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt; |
320 //Unfortunately all the typedefs are instantiated in templates, |
218 //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt; |
321 //unlike other stuff |
219 |
322 typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt; |
220 class OutEdgeIt { |
323 typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt; |
221 friend class GraphWrapper<Graph>; |
324 |
222 friend class RevGraphWrapper<Graph>; |
325 // RevGraphWrapper() : GraphWrapper<Graph>() { } |
223 typename Graph::OutEdgeIt e; |
326 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } |
224 public: |
327 |
225 OutEdgeIt() { } |
328 Node head(const Edge& e) const |
226 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } |
329 { return GraphWrapper<Graph>::tail(e); } |
227 OutEdgeIt(const Invalid& i) : e(i) { } |
330 Node tail(const Edge& e) const |
228 OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : |
331 { return GraphWrapper<Graph>::head(e); } |
229 e(*(_G.graph), typename Graph::Node(_n)) { } |
|
230 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
|
231 }; |
|
232 class InEdgeIt { |
|
233 friend class GraphWrapper<Graph>; |
|
234 friend class RevGraphWrapper<Graph>; |
|
235 typename Graph::InEdgeIt e; |
|
236 public: |
|
237 InEdgeIt() { } |
|
238 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } |
|
239 InEdgeIt(const Invalid& i) : e(i) { } |
|
240 InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : |
|
241 e(*(_G.graph), typename Graph::Node(_n)) { } |
|
242 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
|
243 }; |
|
244 |
|
245 using GraphWrapper<Graph>::first; |
|
246 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
|
247 i=OutEdgeIt(*this, p); return i; |
|
248 } |
|
249 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
|
250 i=InEdgeIt(*this, p); return i; |
|
251 } |
|
252 |
|
253 using GraphWrapper<Graph>::next; |
|
254 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } |
|
255 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } |
|
256 |
|
257 Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
|
258 Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
|
259 Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
|
260 Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
332 }; |
261 }; |
333 |
262 |
334 /// Wrapper for hiding nodes and edges from a graph. |
263 /// Wrapper for hiding nodes and edges from a graph. |
335 |
264 |
336 /// This wrapper shows a graph with filtered node-set and |
265 /// This wrapper shows a graph with filtered node-set and |
542 void unHide(const Node& n) const { node_filter_map->set(n, true); } |
390 void unHide(const Node& n) const { node_filter_map->set(n, true); } |
543 void unHide(const Edge& e) const { edge_filter_map->set(e, true); } |
391 void unHide(const Edge& e) const { edge_filter_map->set(e, true); } |
544 |
392 |
545 bool hidden(const Node& n) const { return (*node_filter_map)[n]; } |
393 bool hidden(const Node& n) const { return (*node_filter_map)[n]; } |
546 bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; } |
394 bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; } |
547 |
|
548 // template< typename It > It first() const { |
|
549 // It e; this->first(e); return e; } |
|
550 |
|
551 // template< typename It > It first(const Node& v) const { |
|
552 // It e; this->first(e, v); return e; } |
|
553 }; |
395 }; |
554 |
396 |
555 // //Subgraph on the same node-set and partial edge-set |
397 /// A wrapper for getting an undirected graph by forgetting the orientation of a directed one. |
556 // template<typename Graph, typename NodeFilterMap, |
398 |
557 // typename EdgeFilterMap> |
399 /// A wrapper for getting an undirected graph by forgetting the orientation of a directed one. |
558 // class SubGraphWrapper : public GraphWrapper<Graph> { |
|
559 // protected: |
|
560 // NodeFilterMap* node_filter_map; |
|
561 // EdgeFilterMap* edge_filter_map; |
|
562 // public: |
|
563 // // SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { } |
|
564 // SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, |
|
565 // EdgeFilterMap& _edge_filter_map) : |
|
566 // GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map), |
|
567 // edge_filter_map(&_edge_filter_map) { } |
|
568 |
|
569 |
|
570 // typedef typename Graph::Node Node; |
|
571 // class NodeIt : public Graph::NodeIt { |
|
572 // // typedef typename Graph::NodeIt GraphNodeIt; |
|
573 // public: |
|
574 // NodeIt() { } |
|
575 // NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } |
|
576 // NodeIt(const Invalid& i) : Graph::NodeIt(i) { } |
|
577 // NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : |
|
578 // Graph::NodeIt(*(_G.graph)) { |
|
579 // while (_G.graph->valid((*this)/*.GraphNodeIt*/) && |
|
580 // !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/]) |
|
581 // _G.graph->next((*this)/*.GraphNodeIt*/); |
|
582 // } |
|
583 // }; |
|
584 // typedef typename Graph::Edge Edge; |
|
585 // class OutEdgeIt : public Graph::OutEdgeIt { |
|
586 // // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; |
|
587 // public: |
|
588 // OutEdgeIt() { } |
|
589 // OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } |
|
590 // OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } |
|
591 // OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& |
|
592 // _G, const Node& n) : |
|
593 // Graph::OutEdgeIt(*(_G.graph), n) { |
|
594 // while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) && |
|
595 // !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/]) |
|
596 // _G.graph->next((*this)/*.GraphOutEdgeIt*/); |
|
597 // } |
|
598 // }; |
|
599 // class InEdgeIt : public Graph::InEdgeIt { |
|
600 // // typedef typename Graph::InEdgeIt GraphInEdgeIt; |
|
601 // public: |
|
602 // InEdgeIt() { } |
|
603 // InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } |
|
604 // InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } |
|
605 // InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, |
|
606 // const Node& n) : |
|
607 // Graph::InEdgeIt(*(_G.graph), n) { |
|
608 // while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) && |
|
609 // !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/]) |
|
610 // _G.graph->next((*this)/*.GraphInEdgeIt*/); |
|
611 // } |
|
612 // }; |
|
613 // // //typedef typename Graph::SymEdgeIt SymEdgeIt; |
|
614 // class EdgeIt : public Graph::EdgeIt { |
|
615 // // typedef typename Graph::EdgeIt GraphEdgeIt; |
|
616 // public: |
|
617 // EdgeIt() { } |
|
618 // EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } |
|
619 // EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } |
|
620 // EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : |
|
621 // Graph::EdgeIt(*(_G.graph)) { |
|
622 // while (_G.graph->valid((*this)/*.GraphEdgeIt*/) && |
|
623 // !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/]) |
|
624 // _G.graph->next((*this)/*.GraphEdgeIt*/); |
|
625 // } |
|
626 // }; |
|
627 |
|
628 // NodeIt& first(NodeIt& i) const { |
|
629 // i=NodeIt(*this); |
|
630 // return i; |
|
631 // } |
|
632 // OutEdgeIt& first(OutEdgeIt& i, const Node& n) const { |
|
633 // i=OutEdgeIt(*this, n); |
|
634 // return i; |
|
635 // } |
|
636 // InEdgeIt& first(InEdgeIt& i, const Node& n) const { |
|
637 // i=InEdgeIt(*this, n); |
|
638 // return i; |
|
639 // } |
|
640 // EdgeIt& first(EdgeIt& i) const { |
|
641 // i=EdgeIt(*this); |
|
642 // return i; |
|
643 // } |
|
644 |
|
645 // // template<typename I> I& first(I& i) const { |
|
646 // // graph->first(i); |
|
647 // // //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } |
|
648 // // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } |
|
649 // // return i; |
|
650 // // } |
|
651 // // template<typename I, typename P> I& first(I& i, const P& p) const { |
|
652 // // graph->first(i, p); |
|
653 // // // while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } |
|
654 // // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } |
|
655 // // return i; |
|
656 // // } |
|
657 |
|
658 // NodeIt& next(NodeIt& i) const { |
|
659 // graph->next(i); |
|
660 // while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); } |
|
661 // return i; |
|
662 // } |
|
663 // OutEdgeIt& next(OutEdgeIt& i) const { |
|
664 // graph->next(i); |
|
665 // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } |
|
666 // return i; |
|
667 // } |
|
668 // InEdgeIt& next(InEdgeIt& i) const { |
|
669 // graph->next(i); |
|
670 // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } |
|
671 // return i; |
|
672 // } |
|
673 // EdgeIt& next(EdgeIt& i) const { |
|
674 // graph->next(i); |
|
675 // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } |
|
676 // return i; |
|
677 // } |
|
678 |
|
679 // // template<typename I> I& next(I &i) const { |
|
680 // // graph->next(i); |
|
681 // // // while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); } |
|
682 // // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } |
|
683 // // return i; |
|
684 // // } |
|
685 |
|
686 // template< typename It > It first() const { |
|
687 // It e; this->first(e); return e; } |
|
688 |
|
689 // template< typename It > It first(const Node& v) const { |
|
690 // It e; this->first(e, v); return e; } |
|
691 // }; |
|
692 |
|
693 template<typename Graph> |
400 template<typename Graph> |
694 class UndirGraphWrapper : public GraphWrapper<Graph> { |
401 class UndirGraphWrapper : public GraphWrapper<Graph> { |
695 // protected: |
|
696 // typedef typename Graph::Edge GraphEdge; |
|
697 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; |
|
698 // typedef typename Graph::InEdgeIt GraphInEdgeIt; |
|
699 public: |
402 public: |
700 typedef typename GraphWrapper<Graph>::Node Node; |
403 typedef typename GraphWrapper<Graph>::Node Node; |
701 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; |
404 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; |
702 typedef typename GraphWrapper<Graph>::Edge Edge; |
405 typedef typename GraphWrapper<Graph>::Edge Edge; |
703 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt; |
406 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt; |
704 |
407 |
705 // UndirGraphWrapper() : GraphWrapper<Graph>() { } |
|
706 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } |
408 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } |
707 |
|
708 |
|
709 // class Edge { |
|
710 // friend class UndirGraphWrapper<Graph>; |
|
711 // protected: |
|
712 // bool out_or_in; //true iff out |
|
713 // GraphOutEdgeIt out; |
|
714 // GraphInEdgeIt in; |
|
715 // public: |
|
716 // Edge() : out_or_in(), out(), in() { } |
|
717 // Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } |
|
718 // operator GraphEdge() const { |
|
719 // if (out_or_in) return(out); else return(in); |
|
720 // } |
|
721 // //FIXME |
|
722 // //2 edges are equal if they "refer" to the same physical edge |
|
723 // //is it good? |
|
724 // friend bool operator==(const Edge& u, const Edge& v) { |
|
725 // if (v.out_or_in) |
|
726 // if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in); |
|
727 // //return (u.out_or_in && u.out==v.out); |
|
728 // else |
|
729 // if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in); |
|
730 // //return (!u.out_or_in && u.in==v.in); |
|
731 // } |
|
732 // friend bool operator!=(const Edge& u, const Edge& v) { |
|
733 // if (v.out_or_in) |
|
734 // if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in); |
|
735 // //return (!u.out_or_in || u.out!=v.out); |
|
736 // else |
|
737 // if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in); |
|
738 // //return (u.out_or_in || u.in!=v.in); |
|
739 // } |
|
740 // }; |
|
741 |
409 |
742 class OutEdgeIt { |
410 class OutEdgeIt { |
743 friend class UndirGraphWrapper<Graph>; |
411 friend class UndirGraphWrapper<Graph>; |
744 bool out_or_in; //true iff out |
412 bool out_or_in; //true iff out |
745 typename Graph::OutEdgeIt out; |
413 typename Graph::OutEdgeIt out; |
753 } |
421 } |
754 operator Edge() const { |
422 operator Edge() const { |
755 if (out_or_in) return Edge(out); else return Edge(in); |
423 if (out_or_in) return Edge(out); else return Edge(in); |
756 } |
424 } |
757 }; |
425 }; |
758 // class OutEdgeIt : public Edge { |
|
759 // friend class UndirGraphWrapper<Graph>; |
|
760 // public: |
|
761 // OutEdgeIt() : Edge() { } |
|
762 // OutEdgeIt(const Invalid& i) : Edge(i) { } |
|
763 // OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n) |
|
764 // : Edge() { |
|
765 // out_or_in=true; _G.graph->first(out, n); |
|
766 // if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); } |
|
767 // } |
|
768 // }; |
|
769 |
426 |
770 //FIXME InEdgeIt |
427 //FIXME InEdgeIt |
771 typedef OutEdgeIt InEdgeIt; |
428 typedef OutEdgeIt InEdgeIt; |
772 |
429 |
773 // class EdgeIt : public Edge { |
430 using GraphWrapper<Graph>::first; |
774 // friend class UndirGraphWrapper<Graph>; |
431 // NodeIt& first(NodeIt& i) const { |
775 // protected: |
432 // i=NodeIt(*this); return i; |
776 // NodeIt v; |
433 // } |
777 // public: |
|
778 // EdgeIt() : Edge() { } |
|
779 // EdgeIt(const Invalid& i) : Edge(i) { } |
|
780 // EdgeIt(const UndirGraphWrapper<Graph>& _G) |
|
781 // : Edge() { |
|
782 // out_or_in=true; |
|
783 // //Node v; |
|
784 // _G.first(v); |
|
785 // if (_G.valid(v)) _G.graph->first(out); else out=INVALID; |
|
786 // while (_G.valid(v) && !_G.graph->valid(out)) { |
|
787 // _G.graph->next(v); |
|
788 // if (_G.valid(v)) _G.graph->first(out); |
|
789 // } |
|
790 // } |
|
791 // }; |
|
792 |
|
793 NodeIt& first(NodeIt& i) const { |
|
794 i=NodeIt(*this); return i; |
|
795 } |
|
796 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
434 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
797 i=OutEdgeIt(*this, p); return i; |
435 i=OutEdgeIt(*this, p); return i; |
798 } |
436 } |
799 //FIXME |
437 //FIXME |
800 // InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
438 // InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
801 // i=InEdgeIt(*this, p); return i; |
439 // i=InEdgeIt(*this, p); return i; |
802 // } |
440 // } |
803 EdgeIt& first(EdgeIt& i) const { |
441 // EdgeIt& first(EdgeIt& i) const { |
804 i=EdgeIt(*this); return i; |
442 // i=EdgeIt(*this); return i; |
805 } |
443 // } |
806 |
444 |
807 // template<typename I> I& first(I& i) const { graph->first(i); return i; } |
445 using GraphWrapper<Graph>::next; |
808 // template<typename I, typename P> I& first(I& i, const P& p) const { |
446 // NodeIt& next(NodeIt& n) const { |
809 // graph->first(i, p); return i; } |
447 // GraphWrapper<Graph>::next(n); |
810 |
448 // return n; |
811 NodeIt& next(NodeIt& n) const { |
449 // } |
812 GraphWrapper<Graph>::next(n); |
|
813 return n; |
|
814 } |
|
815 OutEdgeIt& next(OutEdgeIt& e) const { |
450 OutEdgeIt& next(OutEdgeIt& e) const { |
816 if (e.out_or_in) { |
451 if (e.out_or_in) { |
817 typename Graph::Node n=graph->tail(e.out); |
452 typename Graph::Node n=graph->tail(e.out); |
818 graph->next(e.out); |
453 graph->next(e.out); |
819 if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); } |
454 if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); } |
821 graph->next(e.in); |
456 graph->next(e.in); |
822 } |
457 } |
823 return e; |
458 return e; |
824 } |
459 } |
825 //FIXME InEdgeIt |
460 //FIXME InEdgeIt |
826 EdgeIt& next(EdgeIt& e) const { |
461 // EdgeIt& next(EdgeIt& e) const { |
827 GraphWrapper<Graph>::next(n); |
462 // GraphWrapper<Graph>::next(n); |
828 // graph->next(e.e); |
463 // // graph->next(e.e); |
829 return e; |
464 // return e; |
830 } |
465 // } |
831 |
|
832 // template<typename I> I& next(I &i) const { graph->next(i); return i; } |
|
833 // template< typename It > It first() const { |
|
834 // It e; this->first(e); return e; } |
|
835 |
|
836 // template< typename It > It first(const Node& v) const { |
|
837 // It e; this->first(e, v); return e; } |
|
838 |
|
839 // Node head(const Edge& e) const { return gw.head(e); } |
|
840 // Node tail(const Edge& e) const { return gw.tail(e); } |
|
841 |
|
842 // template<typename I> bool valid(const I& i) const |
|
843 // { return gw.valid(i); } |
|
844 |
|
845 // int nodeNum() const { return gw.nodeNum(); } |
|
846 // int edgeNum() const { return gw.edgeNum(); } |
|
847 |
|
848 // template<typename I> Node aNode(const I& e) const { |
|
849 // return graph->aNode(e); } |
|
850 // template<typename I> Node bNode(const I& e) const { |
|
851 // return graph->bNode(e); } |
|
852 |
466 |
853 Node aNode(const OutEdgeIt& e) const { |
467 Node aNode(const OutEdgeIt& e) const { |
854 if (e.out_or_in) return graph->tail(e); else return graph->head(e); } |
468 if (e.out_or_in) return graph->tail(e); else return graph->head(e); } |
855 Node bNode(const OutEdgeIt& e) const { |
469 Node bNode(const OutEdgeIt& e) const { |
856 if (e.out_or_in) return graph->head(e); else return graph->tail(e); } |
470 if (e.out_or_in) return graph->head(e); else return graph->tail(e); } |
|
471 }; |
857 |
472 |
858 // Node addNode() const { return gw.addNode(); } |
473 /// A wrapper for composing the residual graph for directed flow and circulation problems. |
859 |
474 |
860 // FIXME: ez igy nem jo, mert nem |
475 /// A wrapper for composing the residual graph for directed flow and circulation problems. |
861 // Edge addEdge(const Node& tail, const Node& head) const { |
|
862 // return graph->addEdge(tail, head); } |
|
863 |
|
864 // template<typename I> void erase(const I& i) const { gw.erase(i); } |
|
865 |
|
866 // void clear() const { gw.clear(); } |
|
867 |
|
868 // template<typename T> class NodeMap : public Graph::NodeMap<T> { |
|
869 // public: |
|
870 // NodeMap(const UndirGraphWrapper<Graph>& _G) : |
|
871 // Graph::NodeMap<T>(_G.gw) { } |
|
872 // NodeMap(const UndirGraphWrapper<Graph>& _G, T a) : |
|
873 // Graph::NodeMap<T>(_G.gw, a) { } |
|
874 // }; |
|
875 |
|
876 // template<typename T> class EdgeMap : |
|
877 // public GraphWrapperSkeleton<Graph>::EdgeMap<T> { |
|
878 // public: |
|
879 // EdgeMap(const UndirGraphWrapper<Graph>& _G) : |
|
880 // GraphWrapperSkeleton<Graph>::EdgeMap<T>(_G.gw) { } |
|
881 // EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) : |
|
882 // Graph::EdgeMap<T>(_G.gw, a) { } |
|
883 // }; |
|
884 }; |
|
885 |
|
886 |
|
887 |
|
888 |
|
889 |
|
890 // template<typename Graph> |
|
891 // class SymGraphWrapper |
|
892 // { |
|
893 // Graph* graph; |
|
894 |
|
895 // public: |
|
896 // typedef Graph ParentGraph; |
|
897 |
|
898 // typedef typename Graph::Node Node; |
|
899 // typedef typename Graph::Edge Edge; |
|
900 |
|
901 // typedef typename Graph::NodeIt NodeIt; |
|
902 |
|
903 // //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon |
|
904 // //iranyitatlant, ami van |
|
905 // //mert csak 1 dolgot lehet be typedef-elni |
|
906 // typedef typename Graph::OutEdgeIt SymEdgeIt; |
|
907 // //typedef typename Graph::InEdgeIt SymEdgeIt; |
|
908 // //typedef typename Graph::SymEdgeIt SymEdgeIt; |
|
909 // typedef typename Graph::EdgeIt EdgeIt; |
|
910 |
|
911 // int nodeNum() const { return graph->nodeNum(); } |
|
912 // int edgeNum() const { return graph->edgeNum(); } |
|
913 |
|
914 // template<typename I> I& first(I& i) const { return graph->first(i); } |
|
915 // template<typename I, typename P> I& first(I& i, const P& p) const { |
|
916 // return graph->first(i, p); } |
|
917 // //template<typename I> I next(const I i); { return graph->goNext(i); } |
|
918 // //template<typename I> I &goNext(I &i); { return graph->goNext(i); } |
|
919 |
|
920 // template< typename It > It first() const { |
|
921 // It e; first(e); return e; } |
|
922 |
|
923 // template< typename It > It first(Node v) const { |
|
924 // It e; first(e, v); return e; } |
|
925 |
|
926 // Node head(const Edge& e) const { return graph->head(e); } |
|
927 // Node tail(const Edge& e) const { return graph->tail(e); } |
|
928 |
|
929 // template<typename I> Node aNode(const I& e) const { |
|
930 // return graph->aNode(e); } |
|
931 // template<typename I> Node bNode(const I& e) const { |
|
932 // return graph->bNode(e); } |
|
933 |
|
934 // //template<typename I> bool valid(const I i); |
|
935 // //{ return graph->valid(i); } |
|
936 |
|
937 // //template<typename I> void setInvalid(const I &i); |
|
938 // //{ return graph->setInvalid(i); } |
|
939 |
|
940 // Node addNode() { return graph->addNode(); } |
|
941 // Edge addEdge(const Node& tail, const Node& head) { |
|
942 // return graph->addEdge(tail, head); } |
|
943 |
|
944 // template<typename I> void erase(const I& i) { graph->erase(i); } |
|
945 |
|
946 // void clear() { graph->clear(); } |
|
947 |
|
948 // template<typename T> class NodeMap : public Graph::NodeMap<T> { }; |
|
949 // template<typename T> class EdgeMap : public Graph::EdgeMap<T> { }; |
|
950 |
|
951 // void setGraph(Graph& _graph) { graph = &_graph; } |
|
952 // Graph& getGraph() { return (*graph); } |
|
953 |
|
954 // //SymGraphWrapper() : graph(0) { } |
|
955 // SymGraphWrapper(Graph& _graph) : graph(&_graph) { } |
|
956 // }; |
|
957 |
|
958 |
|
959 |
|
960 |
|
961 template<typename Graph, typename Number, |
476 template<typename Graph, typename Number, |
962 typename CapacityMap, typename FlowMap> |
477 typename CapacityMap, typename FlowMap> |
963 class ResGraphWrapper : public GraphWrapper<Graph> { |
478 class ResGraphWrapper : public GraphWrapper<Graph> { |
964 protected: |
479 protected: |
965 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; |
|
966 // typedef typename Graph::InEdgeIt GraphInEdgeIt; |
|
967 // typedef typename Graph::Edge GraphEdge; |
|
968 const CapacityMap* capacity; |
480 const CapacityMap* capacity; |
969 FlowMap* flow; |
481 FlowMap* flow; |
970 public: |
482 public: |
971 |
483 |
972 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, |
484 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, |
1154 } |
603 } |
1155 operator Edge() const { |
604 operator Edge() const { |
1156 return Edge(e, this->forward); |
605 return Edge(e, this->forward); |
1157 } |
606 } |
1158 }; |
607 }; |
1159 // class EdgeIt : public Edge { |
608 |
1160 // friend class ResGraphWrapper<Graph, Number, FflowMap, CapacityMap>; |
609 using GraphWrapper<Graph>::first; |
1161 // NodeIt v; |
610 // NodeIt& first(NodeIt& i) const { |
1162 // public: |
611 // i=NodeIt(*this); return i; |
1163 // EdgeIt() { } |
612 // } |
1164 // //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } |
|
1165 // EdgeIt(const Invalid& i) : Edge(i) { } |
|
1166 // EdgeIt(const ResGraphWrapper<Graph, Number, FlfowMap, CapacityMap>& resG) : Edge() { |
|
1167 // resG.graph->first(v); |
|
1168 // if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID; |
|
1169 // while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } |
|
1170 // while (resG.graph->valid(v) && !resG.graph->valid(out)) { |
|
1171 // resG.graph->next(v); |
|
1172 // if (resG.graph->valid(v)) resG.graph->first(out, v); |
|
1173 // while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } |
|
1174 // } |
|
1175 // if (!resG.graph->valid(out)) { |
|
1176 // out_or_in=0; |
|
1177 // resG.graph->first(v); |
|
1178 // if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID; |
|
1179 // while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } |
|
1180 // while (resG.graph->valid(v) && !resG.graph->valid(in)) { |
|
1181 // resG.graph->next(v); |
|
1182 // if (resG.graph->valid(v)) resG.graph->first(in, v); |
|
1183 // while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } |
|
1184 // } |
|
1185 // } |
|
1186 // } |
|
1187 // EdgeIt& operator++() { |
|
1188 // if (out_or_in) { |
|
1189 // ++out; |
|
1190 // while (out.valid() && !(Edge::resCap()>0) ) { ++out; } |
|
1191 // while (v.valid() && !out.valid()) { |
|
1192 // ++v; |
|
1193 // if (v.valid()) G->first(out, v); |
|
1194 // while (out.valid() && !(Edge::resCap()>0) ) { ++out; } |
|
1195 // } |
|
1196 // if (!out.valid()) { |
|
1197 // out_or_in=0; |
|
1198 // G->first(v); |
|
1199 // if (v.valid()) G->first(in, v); else in=GraphInEdgeIt(); |
|
1200 // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } |
|
1201 // while (v.valid() && !in.valid()) { |
|
1202 // ++v; |
|
1203 // if (v.valid()) G->first(in, v); |
|
1204 // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } |
|
1205 // } |
|
1206 // } |
|
1207 // } else { |
|
1208 // ++in; |
|
1209 // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } |
|
1210 // while (v.valid() && !in.valid()) { |
|
1211 // ++v; |
|
1212 // if (v.valid()) G->first(in, v); |
|
1213 // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } |
|
1214 // } |
|
1215 // } |
|
1216 // return *this; |
|
1217 // } |
|
1218 // }; |
|
1219 |
|
1220 NodeIt& first(NodeIt& i) const { |
|
1221 i=NodeIt(*this); return i; |
|
1222 } |
|
1223 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
613 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
1224 i=OutEdgeIt(*this, p); return i; |
614 i=OutEdgeIt(*this, p); return i; |
1225 } |
615 } |
1226 // FIXME not tested |
616 // FIXME not tested |
1227 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
617 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
1228 i=InEdgeIt(*this, p); return i; |
618 i=InEdgeIt(*this, p); return i; |
1229 } |
619 } |
1230 EdgeIt& first(EdgeIt& i) const { |
620 EdgeIt& first(EdgeIt& i) const { |
1231 i=EdgeIt(*this); return i; |
621 i=EdgeIt(*this); return i; |
1232 } |
622 } |
1233 |
623 |
1234 NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; } |
624 using GraphWrapper<Graph>::next; |
|
625 // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; } |
1235 OutEdgeIt& next(OutEdgeIt& e) const { |
626 OutEdgeIt& next(OutEdgeIt& e) const { |
1236 if (e.forward) { |
627 if (e.forward) { |
1237 Node v=graph->aNode(e.out); |
628 Node v=graph->aNode(e.out); |
1238 graph->next(e.out); |
629 graph->next(e.out); |
1239 while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); } |
630 while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); } |
1421 // return backward_map.get(e.in); |
749 // return backward_map.get(e.in); |
1422 // } |
750 // } |
1423 }; |
751 }; |
1424 }; |
752 }; |
1425 |
753 |
1426 |
754 /// ErasingFirstGraphWrapper for blocking flows. |
1427 |
755 |
1428 // template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
756 /// ErasingFirstGraphWrapper for blocking flows. |
1429 // class ResGraphWrapper : public GraphWrapper<Graph> { |
|
1430 // protected: |
|
1431 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; |
|
1432 // typedef typename Graph::InEdgeIt GraphInEdgeIt; |
|
1433 // typedef typename Graph::Edge GraphEdge; |
|
1434 // FlowMap* flow; |
|
1435 // const CapacityMap* capacity; |
|
1436 // public: |
|
1437 |
|
1438 // ResGraphWrapper(Graph& _graph, FlowMap& _flow, |
|
1439 // const CapacityMap& _capacity) : |
|
1440 // GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { } |
|
1441 |
|
1442 // class Edge; |
|
1443 // class OutEdgeIt; |
|
1444 // friend class Edge; |
|
1445 // friend class OutEdgeIt; |
|
1446 |
|
1447 // typedef typename GraphWrapper<Graph>::Node Node; |
|
1448 // typedef typename GraphWrapper<Graph>::NodeIt NodeIt; |
|
1449 // class Edge { |
|
1450 // friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; |
|
1451 // protected: |
|
1452 // bool out_or_in; //true, iff out |
|
1453 // GraphOutEdgeIt out; |
|
1454 // GraphInEdgeIt in; |
|
1455 // public: |
|
1456 // Edge() : out_or_in(true) { } |
|
1457 // Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } |
|
1458 // // bool valid() const { |
|
1459 // // return out_or_in && out.valid() || in.valid(); } |
|
1460 // friend bool operator==(const Edge& u, const Edge& v) { |
|
1461 // if (v.out_or_in) |
|
1462 // return (u.out_or_in && u.out==v.out); |
|
1463 // else |
|
1464 // return (!u.out_or_in && u.in==v.in); |
|
1465 // } |
|
1466 // friend bool operator!=(const Edge& u, const Edge& v) { |
|
1467 // if (v.out_or_in) |
|
1468 // return (!u.out_or_in || u.out!=v.out); |
|
1469 // else |
|
1470 // return (u.out_or_in || u.in!=v.in); |
|
1471 // } |
|
1472 // operator GraphEdge() const { |
|
1473 // if (out_or_in) return(out); else return(in); |
|
1474 // } |
|
1475 // }; |
|
1476 // class OutEdgeIt : public Edge { |
|
1477 // friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; |
|
1478 // public: |
|
1479 // OutEdgeIt() { } |
|
1480 // //FIXME |
|
1481 // OutEdgeIt(const Edge& e) : Edge(e) { } |
|
1482 // OutEdgeIt(const Invalid& i) : Edge(i) { } |
|
1483 // OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() { |
|
1484 // resG.graph->first(out, v); |
|
1485 // while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } |
|
1486 // if (!resG.graph->valid(out)) { |
|
1487 // out_or_in=0; |
|
1488 // resG.graph->first(in, v); |
|
1489 // while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } |
|
1490 // } |
|
1491 // } |
|
1492 // // public: |
|
1493 // // OutEdgeIt& operator++() { |
|
1494 // // if (out_or_in) { |
|
1495 // // Node v=/*resG->*/G->aNode(out); |
|
1496 // // ++out; |
|
1497 // // while( out.valid() && !(Edge::resCap()>0) ) { ++out; } |
|
1498 // // if (!out.valid()) { |
|
1499 // // out_or_in=0; |
|
1500 // // G->first(in, v); |
|
1501 // // while( in.valid() && !(Edge::resCap()>0) ) { ++in; } |
|
1502 // // } |
|
1503 // // } else { |
|
1504 // // ++in; |
|
1505 // // while( in.valid() && !(Edge::resCap()>0) ) { ++in; } |
|
1506 // // } |
|
1507 // // return *this; |
|
1508 // // } |
|
1509 // }; |
|
1510 |
|
1511 // //FIXME This is just for having InEdgeIt |
|
1512 // // class InEdgeIt : public Edge { }; |
|
1513 |
|
1514 // class EdgeIt : public Edge { |
|
1515 // friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; |
|
1516 // NodeIt v; |
|
1517 // public: |
|
1518 // EdgeIt() { } |
|
1519 // //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } |
|
1520 // EdgeIt(const Invalid& i) : Edge(i) { } |
|
1521 // EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() { |
|
1522 // resG.graph->first(v); |
|
1523 // if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID; |
|
1524 // while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } |
|
1525 // while (resG.graph->valid(v) && !resG.graph->valid(out)) { |
|
1526 // resG.graph->next(v); |
|
1527 // if (resG.graph->valid(v)) resG.graph->first(out, v); |
|
1528 // while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } |
|
1529 // } |
|
1530 // if (!resG.graph->valid(out)) { |
|
1531 // out_or_in=0; |
|
1532 // resG.graph->first(v); |
|
1533 // if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID; |
|
1534 // while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } |
|
1535 // while (resG.graph->valid(v) && !resG.graph->valid(in)) { |
|
1536 // resG.graph->next(v); |
|
1537 // if (resG.graph->valid(v)) resG.graph->first(in, v); |
|
1538 // while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } |
|
1539 // } |
|
1540 // } |
|
1541 // } |
|
1542 // // EdgeIt& operator++() { |
|
1543 // // if (out_or_in) { |
|
1544 // // ++out; |
|
1545 // // while (out.valid() && !(Edge::resCap()>0) ) { ++out; } |
|
1546 // // while (v.valid() && !out.valid()) { |
|
1547 // // ++v; |
|
1548 // // if (v.valid()) G->first(out, v); |
|
1549 // // while (out.valid() && !(Edge::resCap()>0) ) { ++out; } |
|
1550 // // } |
|
1551 // // if (!out.valid()) { |
|
1552 // // out_or_in=0; |
|
1553 // // G->first(v); |
|
1554 // // if (v.valid()) G->first(in, v); else in=GraphInEdgeIt(); |
|
1555 // // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } |
|
1556 // // while (v.valid() && !in.valid()) { |
|
1557 // // ++v; |
|
1558 // // if (v.valid()) G->first(in, v); |
|
1559 // // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } |
|
1560 // // } |
|
1561 // // } |
|
1562 // // } else { |
|
1563 // // ++in; |
|
1564 // // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } |
|
1565 // // while (v.valid() && !in.valid()) { |
|
1566 // // ++v; |
|
1567 // // if (v.valid()) G->first(in, v); |
|
1568 // // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } |
|
1569 // // } |
|
1570 // // } |
|
1571 // // return *this; |
|
1572 // // } |
|
1573 // }; |
|
1574 |
|
1575 // NodeIt& first(NodeIt& i) const { |
|
1576 // i=NodeIt(*this); |
|
1577 // return i; |
|
1578 // } |
|
1579 // OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
|
1580 // i=OutEdgeIt(*this, p); |
|
1581 // return i; |
|
1582 // } |
|
1583 // //FIXME Not yet implemented |
|
1584 // //InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
|
1585 // //i=InEdgeIt(*this, p); |
|
1586 // // return i; |
|
1587 // //} |
|
1588 // EdgeIt& first(EdgeIt& e) const { |
|
1589 // e=EdgeIt(*this); |
|
1590 // return e; |
|
1591 // } |
|
1592 |
|
1593 // NodeIt& next(NodeIt& n) const { graph->next(n); return n; } |
|
1594 // OutEdgeIt& next(OutEdgeIt& e) const { |
|
1595 // if (e.out_or_in) { |
|
1596 // Node v=graph->aNode(e.out); |
|
1597 // graph->next(e.out); |
|
1598 // while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } |
|
1599 // if (!graph->valid(e.out)) { |
|
1600 // e.out_or_in=0; |
|
1601 // graph->first(e.in, v); |
|
1602 // while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } |
|
1603 // } |
|
1604 // } else { |
|
1605 // graph->next(e.in); |
|
1606 // while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } |
|
1607 // } |
|
1608 // return e; |
|
1609 // } |
|
1610 // //FIXME Not yet implemented |
|
1611 // //InEdgeIt& next(InEdgeIt& e) const { |
|
1612 // // return e; |
|
1613 // //} |
|
1614 // EdgeIt& next(EdgeIt& e) const { |
|
1615 // if (e.out_or_in) { |
|
1616 // graph->next(e.out); |
|
1617 // while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } |
|
1618 // while (graph->valid(e.v) && !graph->valid(e.out)) { |
|
1619 // graph->next(e.v); |
|
1620 // if (graph->valid(e.v)) graph->first(e.out, e.v); |
|
1621 // while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } |
|
1622 // } |
|
1623 // if (!graph->valid(e.out)) { |
|
1624 // e.out_or_in=0; |
|
1625 // graph->first(e.v); |
|
1626 // if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID; |
|
1627 // while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } |
|
1628 // while (graph->valid(e.v) && !graph->valid(e.in)) { |
|
1629 // graph->next(e.v); |
|
1630 // if (graph->valid(e.v)) graph->first(e.in, e.v); |
|
1631 // while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } |
|
1632 // } |
|
1633 // } |
|
1634 // } else { |
|
1635 // graph->next(e.in); |
|
1636 // while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } |
|
1637 // while (graph->valid(e.v) && !graph->valid(e.in)) { |
|
1638 // graph->next(e.v); |
|
1639 // if (graph->valid(e.v)) graph->first(e.in, e.v); |
|
1640 // while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } |
|
1641 // } |
|
1642 // } |
|
1643 // return e; |
|
1644 // } |
|
1645 |
|
1646 |
|
1647 // template< typename It > |
|
1648 // It first() const { |
|
1649 // It e; |
|
1650 // first(e); |
|
1651 // return e; |
|
1652 // } |
|
1653 |
|
1654 // template< typename It > |
|
1655 // It first(Node v) const { |
|
1656 // It e; |
|
1657 // first(e, v); |
|
1658 // return e; |
|
1659 // } |
|
1660 |
|
1661 // Node tail(Edge e) const { |
|
1662 // return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } |
|
1663 // Node head(Edge e) const { |
|
1664 // return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } |
|
1665 |
|
1666 // Node aNode(OutEdgeIt e) const { |
|
1667 // return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } |
|
1668 // Node bNode(OutEdgeIt e) const { |
|
1669 // return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } |
|
1670 |
|
1671 // int nodeNum() const { return graph->nodeNum(); } |
|
1672 // //FIXME |
|
1673 // //int edgeNum() const { return graph->edgeNum(); } |
|
1674 |
|
1675 |
|
1676 // int id(Node v) const { return graph->id(v); } |
|
1677 |
|
1678 // bool valid(Node n) const { return graph->valid(n); } |
|
1679 // bool valid(Edge e) const { |
|
1680 // return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); } |
|
1681 |
|
1682 // void augment(const Edge& e, Number a) const { |
|
1683 // if (e.out_or_in) |
|
1684 // // flow->set(e.out, flow->get(e.out)+a); |
|
1685 // flow->set(e.out, (*flow)[e.out]+a); |
|
1686 // else |
|
1687 // // flow->set(e.in, flow->get(e.in)-a); |
|
1688 // flow->set(e.in, (*flow)[e.in]-a); |
|
1689 // } |
|
1690 |
|
1691 // Number resCap(const Edge& e) const { |
|
1692 // if (e.out_or_in) |
|
1693 // // return (capacity->get(e.out)-flow->get(e.out)); |
|
1694 // return ((*capacity)[e.out]-(*flow)[e.out]); |
|
1695 // else |
|
1696 // // return (flow->get(e.in)); |
|
1697 // return ((*flow)[e.in]); |
|
1698 // } |
|
1699 |
|
1700 // Number resCap(GraphOutEdgeIt out) const { |
|
1701 // // return (capacity->get(out)-flow->get(out)); |
|
1702 // return ((*capacity)[out]-(*flow)[out]); |
|
1703 // } |
|
1704 |
|
1705 // Number resCap(GraphInEdgeIt in) const { |
|
1706 // // return (flow->get(in)); |
|
1707 // return ((*flow)[in]); |
|
1708 // } |
|
1709 |
|
1710 // // template<typename T> class NodeMap : public Graph::NodeMap<T> { |
|
1711 // // public: |
|
1712 // // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) |
|
1713 // // : Graph::NodeMap<T>(_G.gw) { } |
|
1714 // // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, |
|
1715 // // T a) : Graph::NodeMap<T>(_G.gw, a) { } |
|
1716 // // }; |
|
1717 |
|
1718 // // template <typename T> |
|
1719 // // class NodeMap { |
|
1720 // // typename Graph::NodeMap<T> node_map; |
|
1721 // // public: |
|
1722 // // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { } |
|
1723 // // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { } |
|
1724 // // void set(Node nit, T a) { node_map.set(nit, a); } |
|
1725 // // T get(Node nit) const { return node_map.get(nit); } |
|
1726 // // }; |
|
1727 |
|
1728 // template <typename T> |
|
1729 // class EdgeMap { |
|
1730 // typename Graph::EdgeMap<T> forward_map, backward_map; |
|
1731 // public: |
|
1732 // EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } |
|
1733 // EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } |
|
1734 // void set(Edge e, T a) { |
|
1735 // if (e.out_or_in) |
|
1736 // forward_map.set(e.out, a); |
|
1737 // else |
|
1738 // backward_map.set(e.in, a); |
|
1739 // } |
|
1740 // T operator[](Edge e) const { |
|
1741 // if (e.out_or_in) |
|
1742 // return forward_map[e.out]; |
|
1743 // else |
|
1744 // return backward_map[e.in]; |
|
1745 // } |
|
1746 // // T get(Edge e) const { |
|
1747 // // if (e.out_or_in) |
|
1748 // // return forward_map.get(e.out); |
|
1749 // // else |
|
1750 // // return backward_map.get(e.in); |
|
1751 // // } |
|
1752 // }; |
|
1753 // }; |
|
1754 |
|
1755 |
|
1756 //ErasingFirstGraphWrapper for blocking flows |
|
1757 template<typename Graph, typename FirstOutEdgesMap> |
757 template<typename Graph, typename FirstOutEdgesMap> |
1758 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> { |
758 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> { |
1759 protected: |
759 protected: |
1760 FirstOutEdgesMap* first_out_edges; |
760 FirstOutEdgesMap* first_out_edges; |
1761 public: |
761 public: |
1762 ErasingFirstGraphWrapper(Graph& _graph, |
762 ErasingFirstGraphWrapper(Graph& _graph, |
1763 FirstOutEdgesMap& _first_out_edges) : |
763 FirstOutEdgesMap& _first_out_edges) : |
1764 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } |
764 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } |
1765 |
765 |
1766 typedef typename GraphWrapper<Graph>::Node Node; |
766 typedef typename GraphWrapper<Graph>::Node Node; |
1767 class NodeIt { |
767 // class NodeIt { |
1768 friend class GraphWrapper<Graph>; |
768 // friend class GraphWrapper<Graph>; |
1769 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>; |
769 // friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>; |
1770 typename Graph::NodeIt n; |
770 // typename Graph::NodeIt n; |
1771 public: |
771 // public: |
1772 NodeIt() { } |
772 // NodeIt() { } |
1773 NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } |
773 // NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } |
1774 NodeIt(const Invalid& i) : n(i) { } |
774 // NodeIt(const Invalid& i) : n(i) { } |
1775 NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : |
775 // NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : |
1776 n(*(_G.graph)) { } |
776 // n(*(_G.graph)) { } |
1777 operator Node() const { return Node(typename Graph::Node(n)); } |
777 // operator Node() const { return Node(typename Graph::Node(n)); } |
1778 }; |
778 // }; |
1779 typedef typename GraphWrapper<Graph>::Edge Edge; |
779 typedef typename GraphWrapper<Graph>::Edge Edge; |
1780 class OutEdgeIt { |
780 class OutEdgeIt { |
1781 friend class GraphWrapper<Graph>; |
781 friend class GraphWrapper<Graph>; |
1782 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>; |
782 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>; |
1783 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; |
783 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; |
1818 EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : |
818 EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : |
1819 e(*(_G.graph)) { } |
819 e(*(_G.graph)) { } |
1820 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
820 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
1821 }; |
821 }; |
1822 |
822 |
1823 NodeIt& first(NodeIt& i) const { |
823 using GraphWrapper<Graph>::first; |
1824 i=NodeIt(*this); return i; |
824 // NodeIt& first(NodeIt& i) const { |
1825 } |
825 // i=NodeIt(*this); return i; |
|
826 // } |
1826 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
827 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
1827 i=OutEdgeIt(*this, p); return i; |
828 i=OutEdgeIt(*this, p); return i; |
1828 } |
829 } |
1829 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
830 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
1830 i=InEdgeIt(*this, p); return i; |
831 i=InEdgeIt(*this, p); return i; |
1831 } |
832 } |
1832 EdgeIt& first(EdgeIt& i) const { |
833 EdgeIt& first(EdgeIt& i) const { |
1833 i=EdgeIt(*this); return i; |
834 i=EdgeIt(*this); return i; |
1834 } |
835 } |
1835 |
836 |
1836 // template<typename I> I& first(I& i) const { |
837 using GraphWrapper<Graph>::next; |
1837 // graph->first(i); |
838 // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } |
1838 // return i; |
|
1839 // } |
|
1840 // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { |
|
1841 // // e=first_out_edges->get(n); |
|
1842 // e=(*first_out_edges)[n]; |
|
1843 // return e; |
|
1844 // } |
|
1845 // template<typename I, typename P> I& first(I& i, const P& p) const { |
|
1846 // graph->first(i, p); |
|
1847 // return i; |
|
1848 // } |
|
1849 |
|
1850 NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } |
|
1851 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } |
839 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } |
1852 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } |
840 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } |
1853 EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } |
841 EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } |
1854 |
842 |
1855 Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
843 Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
1856 Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
844 Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } |
1857 Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
845 Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
1858 Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
846 Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } |
1859 |
847 |
1860 // template<typename I> I& next(I &i) const { |
|
1861 // graph->next(i); |
|
1862 // return i; |
|
1863 // } |
|
1864 |
|
1865 // template< typename It > It first() const { |
|
1866 // It e; this->first(e); return e; } |
|
1867 |
|
1868 // template< typename It > It first(const Node& v) const { |
|
1869 // It e; this->first(e, v); return e; } |
|
1870 |
|
1871 void erase(const OutEdgeIt& e) const { |
848 void erase(const OutEdgeIt& e) const { |
1872 OutEdgeIt f=e; |
849 OutEdgeIt f=e; |
1873 this->next(f); |
850 this->next(f); |
1874 first_out_edges->set(this->tail(e), f.e); |
851 first_out_edges->set(this->tail(e), f.e); |
1875 } |
852 } |
1876 }; |
853 }; |
1877 |
854 |
1878 // //ErasingFirstGraphWrapper for blocking flows |
|
1879 // template<typename Graph, typename FirstOutEdgesMap> |
|
1880 // class ErasingFirstGraphWrapper : public GraphWrapper<Graph> { |
|
1881 // protected: |
|
1882 // FirstOutEdgesMap* first_out_edges; |
|
1883 // public: |
|
1884 // ErasingFirstGraphWrapper(Graph& _graph, |
|
1885 // FirstOutEdgesMap& _first_out_edges) : |
|
1886 // GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } |
|
1887 |
|
1888 // typedef typename Graph::Node Node; |
|
1889 // class NodeIt : public Graph::NodeIt { |
|
1890 // public: |
|
1891 // NodeIt() { } |
|
1892 // NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } |
|
1893 // NodeIt(const Invalid& i) : Graph::NodeIt(i) { } |
|
1894 // NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : |
|
1895 // Graph::NodeIt(*(_G.graph)) { } |
|
1896 // }; |
|
1897 // typedef typename Graph::Edge Edge; |
|
1898 // class OutEdgeIt : public Graph::OutEdgeIt { |
|
1899 // public: |
|
1900 // OutEdgeIt() { } |
|
1901 // OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } |
|
1902 // OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } |
|
1903 // OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, |
|
1904 // const Node& n) : |
|
1905 // Graph::OutEdgeIt((*_G.first_out_edges)[n]) { } |
|
1906 // }; |
|
1907 // class InEdgeIt : public Graph::InEdgeIt { |
|
1908 // public: |
|
1909 // InEdgeIt() { } |
|
1910 // InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } |
|
1911 // InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } |
|
1912 // InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, |
|
1913 // const Node& n) : |
|
1914 // Graph::InEdgeIt(*(_G.graph), n) { } |
|
1915 // }; |
|
1916 // //typedef typename Graph::SymEdgeIt SymEdgeIt; |
|
1917 // class EdgeIt : public Graph::EdgeIt { |
|
1918 // public: |
|
1919 // EdgeIt() { } |
|
1920 // EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } |
|
1921 // EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } |
|
1922 // EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : |
|
1923 // Graph::EdgeIt(*(_G.graph)) { } |
|
1924 // }; |
|
1925 |
|
1926 // NodeIt& first(NodeIt& i) const { |
|
1927 // i=NodeIt(*this); |
|
1928 // return i; |
|
1929 // } |
|
1930 // OutEdgeIt& first(OutEdgeIt& i, const Node& n) const { |
|
1931 // i=OutEdgeIt(*this, n); |
|
1932 // // i=(*first_out_edges)[n]; |
|
1933 // return i; |
|
1934 // } |
|
1935 // InEdgeIt& first(InEdgeIt& i, const Node& n) const { |
|
1936 // i=InEdgeIt(*this, n); |
|
1937 // return i; |
|
1938 // } |
|
1939 // EdgeIt& first(EdgeIt& i) const { |
|
1940 // i=EdgeIt(*this); |
|
1941 // return i; |
|
1942 // } |
|
1943 |
|
1944 // // template<typename I> I& first(I& i) const { |
|
1945 // // graph->first(i); |
|
1946 // // return i; |
|
1947 // // } |
|
1948 // // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { |
|
1949 // // // e=first_out_edges->get(n); |
|
1950 // // e=(*first_out_edges)[n]; |
|
1951 // // return e; |
|
1952 // // } |
|
1953 // // template<typename I, typename P> I& first(I& i, const P& p) const { |
|
1954 // // graph->first(i, p); |
|
1955 // // return i; |
|
1956 // // } |
|
1957 |
|
1958 // NodeIt& next(NodeIt& i) const { |
|
1959 // graph->next(i); |
|
1960 // return i; |
|
1961 // } |
|
1962 // OutEdgeIt& next(OutEdgeIt& i) const { |
|
1963 // graph->next(i); |
|
1964 // return i; |
|
1965 // } |
|
1966 // InEdgeIt& next(InEdgeIt& i) const { |
|
1967 // graph->next(i); |
|
1968 // return i; |
|
1969 // } |
|
1970 // EdgeIt& next(EdgeIt& i) const { |
|
1971 // graph->next(i); |
|
1972 // return i; |
|
1973 // } |
|
1974 |
|
1975 // // template<typename I> I& next(I &i) const { |
|
1976 // // graph->next(i); |
|
1977 // // return i; |
|
1978 // // } |
|
1979 |
|
1980 // template< typename It > It first() const { |
|
1981 // It e; this->first(e); return e; } |
|
1982 |
|
1983 // template< typename It > It first(const Node& v) const { |
|
1984 // It e; this->first(e, v); return e; } |
|
1985 |
|
1986 // void erase(const OutEdgeIt& e) const { |
|
1987 // OutEdgeIt f=e; |
|
1988 // this->next(f); |
|
1989 // first_out_edges->set(this->tail(e), f); |
|
1990 // } |
|
1991 // }; |
|
1992 |
|
1993 |
|
1994 // // FIXME: comparison should be made better!!! |
|
1995 // template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap> |
|
1996 // class ResGraphWrapper |
|
1997 // { |
|
1998 // Graph* graph; |
|
1999 |
|
2000 // public: |
|
2001 // typedef Graph ParentGraph; |
|
2002 |
|
2003 // typedef typename Graph::Node Node; |
|
2004 // typedef typename Graph::Edge Edge; |
|
2005 |
|
2006 // typedef typename Graph::NodeIt NodeIt; |
|
2007 |
|
2008 // class OutEdgeIt { |
|
2009 // public: |
|
2010 // //Graph::Node n; |
|
2011 // bool out_or_in; |
|
2012 // typename Graph::OutEdgeIt o; |
|
2013 // typename Graph::InEdgeIt i; |
|
2014 // }; |
|
2015 // class InEdgeIt { |
|
2016 // public: |
|
2017 // //Graph::Node n; |
|
2018 // bool out_or_in; |
|
2019 // typename Graph::OutEdgeIt o; |
|
2020 // typename Graph::InEdgeIt i; |
|
2021 // }; |
|
2022 // typedef typename Graph::SymEdgeIt SymEdgeIt; |
|
2023 // typedef typename Graph::EdgeIt EdgeIt; |
|
2024 |
|
2025 // int nodeNum() const { return gw.nodeNum(); } |
|
2026 // int edgeNum() const { return gw.edgeNum(); } |
|
2027 |
|
2028 // Node& first(Node& n) const { return gw.first(n); } |
|
2029 |
|
2030 // // Edge and SymEdge is missing!!!! |
|
2031 // // Edge <-> In/OutEdgeIt conversion is missing!!!! |
|
2032 |
|
2033 // //FIXME |
|
2034 // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const |
|
2035 // { |
|
2036 // e.n=n; |
|
2037 // gw.first(e.o,n); |
|
2038 // while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) |
|
2039 // gw.goNext(e.o); |
|
2040 // if(!gw.valid(e.o)) { |
|
2041 // gw.first(e.i,n); |
|
2042 // while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) |
|
2043 // gw.goNext(e.i); |
|
2044 // } |
|
2045 // return e; |
|
2046 // } |
|
2047 // /* |
|
2048 // OutEdgeIt &goNext(OutEdgeIt &e) |
|
2049 // { |
|
2050 // if(gw.valid(e.o)) { |
|
2051 // while(gw.valid(e.o) && fmap.get(e.o)>=himap.get(e.o)) |
|
2052 // gw.goNext(e.o); |
|
2053 // if(gw.valid(e.o)) return e; |
|
2054 // else gw.first(e.i,e.n); |
|
2055 // } |
|
2056 // else { |
|
2057 // while(gw.valid(e.i) && fmap.get(e.i)<=lomap.get(e.i)) |
|
2058 // gw.goNext(e.i); |
|
2059 // return e; |
|
2060 // } |
|
2061 // } |
|
2062 // OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);} |
|
2063 // */ |
|
2064 // //bool valid(const OutEdgeIt e) { return gw.valid(e.o)||gw.valid(e.i);} |
|
2065 |
|
2066 // //FIXME |
|
2067 // InEdgeIt& first(InEdgeIt& e, const Node& n) const |
|
2068 // { |
|
2069 // e.n=n; |
|
2070 // gw.first(e.i,n); |
|
2071 // while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) |
|
2072 // gw.goNext(e.i); |
|
2073 // if(!gw.valid(e.i)) { |
|
2074 // gw.first(e.o,n); |
|
2075 // while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) |
|
2076 // gw.goNext(e.o); |
|
2077 // } |
|
2078 // return e; |
|
2079 // } |
|
2080 // /* |
|
2081 // InEdgeIt &goNext(InEdgeIt &e) |
|
2082 // { |
|
2083 // if(gw.valid(e.i)) { |
|
2084 // while(gw.valid(e.i) && fmap.get(e.i)>=himap.get(e.i)) |
|
2085 // gw.goNext(e.i); |
|
2086 // if(gw.valid(e.i)) return e; |
|
2087 // else gw.first(e.o,e.n); |
|
2088 // } |
|
2089 // else { |
|
2090 // while(gw.valid(e.o) && fmap.get(e.o)<=lomap.get(e.o)) |
|
2091 // gw.goNext(e.o); |
|
2092 // return e; |
|
2093 // } |
|
2094 // } |
|
2095 // InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);} |
|
2096 // */ |
|
2097 // //bool valid(const InEdgeIt e) { return gw.valid(e.i)||gw.valid(e.o);} |
|
2098 |
|
2099 // //template<typename I> I &goNext(I &i); { return gw.goNext(i); } |
|
2100 // //template<typename I> I next(const I i); { return gw.goNext(i); } |
|
2101 |
|
2102 // template< typename It > It first() const { |
|
2103 // It e; first(e); return e; } |
|
2104 |
|
2105 // template< typename It > It first(Node v) const { |
|
2106 // It e; first(e, v); return e; } |
|
2107 |
|
2108 // Node head(const Edge& e) const { return gw.head(e); } |
|
2109 // Node tail(const Edge& e) const { return gw.tail(e); } |
|
2110 |
|
2111 // template<typename I> Node aNode(const I& e) const { |
|
2112 // return gw.aNode(e); } |
|
2113 // template<typename I> Node bNode(const I& e) const { |
|
2114 // return gw.bNode(e); } |
|
2115 |
|
2116 // //template<typename I> bool valid(const I i); |
|
2117 // //{ return gw.valid(i); } |
|
2118 |
|
2119 // //template<typename I> void setInvalid(const I &i); |
|
2120 // //{ return gw.setInvalid(i); } |
|
2121 |
|
2122 // Node addNode() { return gw.addNode(); } |
|
2123 // Edge addEdge(const Node& tail, const Node& head) { |
|
2124 // return gw.addEdge(tail, head); } |
|
2125 |
|
2126 // template<typename I> void erase(const I& i) { gw.erase(i); } |
|
2127 |
|
2128 // void clear() { gw.clear(); } |
|
2129 |
|
2130 // template<typename S> class NodeMap : public Graph::NodeMap<S> { }; |
|
2131 // template<typename S> class EdgeMap : public Graph::EdgeMap<S> { }; |
|
2132 |
|
2133 // void setGraph(Graph& _graph) { graph = &_graph; } |
|
2134 // Graph& getGraph() { return (*graph); } |
|
2135 |
|
2136 // //ResGraphWrapper() : graph(0) { } |
|
2137 // ResGraphWrapper(Graph& _graph) : graph(&_graph) { } |
|
2138 // }; |
|
2139 |
|
2140 } //namespace hugo |
855 } //namespace hugo |
2141 |
856 |
2142 #endif //HUGO_GRAPH_WRAPPER_H |
857 #endif //HUGO_GRAPH_WRAPPER_H |
2143 |
858 |