as you see...
2 #ifndef HUGO_GRAPH_WRAPPER_H
3 #define HUGO_GRAPH_WRAPPER_H
10 /// \addtogroup gwrappers
15 /// A main parts of HUGOlib are the different graph structures,
16 /// generic graph algorithms, graph concepts which couple these, and
17 /// graph wrappers. While the previous ones are more or less clear, the
18 /// latter notion needs further explanation.
19 /// Graph wrappers are graph classes which serve for considering graph
20 /// structures in different ways. A short example makes the notion much
22 /// Suppose that we have an instance \c g of a directed graph
23 /// type say \c ListGraph and an algorithm
24 /// \code template<typename Graph> int algorithm(const Graph&); \endcode
25 /// is needed to run on the reversely oriented graph.
26 /// It may be expensive (in time or in memory usage) to copy
27 /// \c g with the reverse orientation.
28 /// Thus, a wrapper class
29 /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.
30 /// The code looks as follows
33 /// RevGraphWrapper<ListGraph> rgw(g);
34 /// int result=algorithm(rgw);
36 /// After running the algorithm, the original graph \c g
37 /// remains untouched. Thus the graph wrapper used above is to consider the
38 /// original graph with reverse orientation.
39 /// This techniques gives rise to an elegant code, and
40 /// based on stable graph wrappers, complex algorithms can be
41 /// implemented easily.
42 /// In flow, circulation and bipartite matching problems, the residual
43 /// graph is of particular importance. Combining a wrapper implementing
44 /// this, shortest path algorithms and minimum mean cycle algorithms,
45 /// a range of weighted and cardinality optimization algorithms can be
46 /// obtained. For lack of space, for other examples,
47 /// the interested user is referred to the detailed documentation of graph
49 /// The behavior of graph wrappers can be very different. Some of them keep
50 /// capabilities of the original graph while in other cases this would be
51 /// meaningless. This means that the concepts that they are a model of depend
52 /// on the graph wrapper, and the wrapped graph(s).
53 /// If an edge of \c rgw is deleted, this is carried out by
54 /// deleting the corresponding edge of \c g. But for a residual
55 /// graph, this operation has no sense.
56 /// Let we stand one more example here to simplify your work.
58 /// \code template<typename Graph> class RevGraphWrapper; \endcode
60 /// <tt> RevGraphWrapper(Graph& _g)</tt>.
61 /// This means that in a situation,
62 /// when a <tt> const ListGraph& </tt> reference to a graph is given,
63 /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
65 /// int algorithm1(const ListGraph& g) {
66 /// RevGraphWrapper<const ListGraph> rgw(g);
67 /// return algorithm2(rgw);
70 template<typename Graph>
76 typedef Graph BaseGraph;
77 typedef Graph ParentGraph;
79 // GraphWrapper() : graph(0) { }
80 GraphWrapper(Graph& _graph) : graph(&_graph) { }
81 // void setGraph(Graph& _graph) { graph=&_graph; }
82 // Graph& getGraph() const { return *graph; }
84 // typedef typename Graph::Node Node;
85 class Node : public Graph::Node {
86 friend class GraphWrapper<Graph>;
89 Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
90 Node(const Invalid& i) : Graph::Node(i) { }
93 friend class GraphWrapper<Graph>;
94 typename Graph::NodeIt n;
97 NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
98 NodeIt(const Invalid& i) : n(i) { }
99 NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
100 operator Node() const { return Node(typename Graph::Node(n)); }
102 // typedef typename Graph::Edge Edge;
103 class Edge : public Graph::Edge {
104 friend class GraphWrapper<Graph>;
107 Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
108 Edge(const Invalid& i) : Graph::Edge(i) { }
111 friend class GraphWrapper<Graph>;
112 typename Graph::OutEdgeIt e;
115 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
116 OutEdgeIt(const Invalid& i) : e(i) { }
117 OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
118 e(*(_G.graph), typename Graph::Node(_n)) { }
119 operator Edge() const { return Edge(typename Graph::Edge(e)); }
122 friend class GraphWrapper<Graph>;
123 typename Graph::InEdgeIt e;
126 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
127 InEdgeIt(const Invalid& i) : e(i) { }
128 InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
129 e(*(_G.graph), typename Graph::Node(_n)) { }
130 operator Edge() const { return Edge(typename Graph::Edge(e)); }
132 //typedef typename Graph::SymEdgeIt SymEdgeIt;
134 friend class GraphWrapper<Graph>;
135 typename Graph::EdgeIt e;
138 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
139 EdgeIt(const Invalid& i) : e(i) { }
140 EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
141 operator Edge() const { return Edge(typename Graph::Edge(e)); }
144 NodeIt& first(NodeIt& i) const {
145 i=NodeIt(*this); return i;
147 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
148 i=OutEdgeIt(*this, p); return i;
150 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
151 i=InEdgeIt(*this, p); return i;
153 EdgeIt& first(EdgeIt& i) const {
154 i=EdgeIt(*this); return i;
157 NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
158 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
159 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
160 EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
162 Node tail(const Edge& e) const {
163 return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
164 Node head(const Edge& e) const {
165 return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
167 bool valid(const Node& n) const {
168 return graph->valid(static_cast<typename Graph::Node>(n)); }
169 bool valid(const Edge& e) const {
170 return graph->valid(static_cast<typename Graph::Edge>(e)); }
172 int nodeNum() const { return graph->nodeNum(); }
173 int edgeNum() const { return graph->edgeNum(); }
175 Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
176 Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
177 Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
178 Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
180 Node addNode() const { return Node(graph->addNode()); }
181 Edge addEdge(const Node& tail, const Node& head) const {
182 return Edge(graph->addEdge(tail, head)); }
184 void erase(const Node& i) const { graph->erase(i); }
185 void erase(const Edge& i) const { graph->erase(i); }
187 void clear() const { graph->clear(); }
189 template<typename T> class NodeMap : public Graph::template NodeMap<T> {
190 typedef typename Graph::template NodeMap<T> Parent;
192 NodeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
193 NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
196 template<typename T> class EdgeMap : public Graph::template EdgeMap<T> {
197 typedef typename Graph::template EdgeMap<T> Parent;
199 EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
200 EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
204 /// A graph wrapper which reverses the orientation of the edges.
206 /// A graph wrapper which reverses the orientation of the edges.
207 template<typename Graph>
208 class RevGraphWrapper : public GraphWrapper<Graph> {
211 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
213 typedef typename GraphWrapper<Graph>::Node Node;
214 typedef typename GraphWrapper<Graph>::Edge Edge;
215 //If Graph::OutEdgeIt is not defined
216 //and we do not want to use RevGraphWrapper::InEdgeIt,
217 //the typdef techinque does not work.
218 //Unfortunately all the typedefs are instantiated in templates.
219 //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
220 //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
223 friend class GraphWrapper<Graph>;
224 friend class RevGraphWrapper<Graph>;
225 typename Graph::InEdgeIt e;
228 OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
229 OutEdgeIt(const Invalid& i) : e(i) { }
230 OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
231 e(*(_G.graph), typename Graph::Node(_n)) { }
232 operator Edge() const { return Edge(typename Graph::Edge(e)); }
235 friend class GraphWrapper<Graph>;
236 friend class RevGraphWrapper<Graph>;
237 typename Graph::OutEdgeIt e;
240 InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
241 InEdgeIt(const Invalid& i) : e(i) { }
242 InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
243 e(*(_G.graph), typename Graph::Node(_n)) { }
244 operator Edge() const { return Edge(typename Graph::Edge(e)); }
247 using GraphWrapper<Graph>::first;
248 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
249 i=OutEdgeIt(*this, p); return i;
251 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
252 i=InEdgeIt(*this, p); return i;
255 using GraphWrapper<Graph>::next;
256 OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
257 InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
259 Node aNode(const OutEdgeIt& e) const {
260 return Node(this->graph->aNode(e.e)); }
261 Node aNode(const InEdgeIt& e) const {
262 return Node(this->graph->aNode(e.e)); }
263 Node bNode(const OutEdgeIt& e) const {
264 return Node(this->graph->bNode(e.e)); }
265 Node bNode(const InEdgeIt& e) const {
266 return Node(this->graph->bNode(e.e)); }
268 Node tail(const Edge& e) const {
269 return GraphWrapper<Graph>::head(e); }
270 Node head(const Edge& e) const {
271 return GraphWrapper<Graph>::tail(e); }
275 /// Wrapper for hiding nodes and edges from a graph.
277 /// This wrapper shows a graph with filtered node-set and
278 /// edge-set. The quick brown fox iterator jumps over
279 /// the lazy dog nodes or edges if the values for them are false
280 /// in the bool maps.
281 template<typename Graph, typename NodeFilterMap,
282 typename EdgeFilterMap>
283 class SubGraphWrapper : public GraphWrapper<Graph> {
285 NodeFilterMap* node_filter_map;
286 EdgeFilterMap* edge_filter_map;
289 SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
290 EdgeFilterMap& _edge_filter_map) :
291 GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
292 edge_filter_map(&_edge_filter_map) { }
294 typedef typename GraphWrapper<Graph>::Node Node;
296 friend class GraphWrapper<Graph>;
297 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
298 typename Graph::NodeIt n;
301 NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
302 NodeIt(const Invalid& i) : n(i) { }
303 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
305 while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
308 operator Node() const { return Node(typename Graph::Node(n)); }
310 typedef typename GraphWrapper<Graph>::Edge Edge;
312 friend class GraphWrapper<Graph>;
313 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
314 typename Graph::OutEdgeIt e;
317 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
318 OutEdgeIt(const Invalid& i) : e(i) { }
319 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
321 e(*(_G.graph), typename Graph::Node(_n)) {
322 while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
325 operator Edge() const { return Edge(typename Graph::Edge(e)); }
328 friend class GraphWrapper<Graph>;
329 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
330 typename Graph::InEdgeIt e;
333 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
334 InEdgeIt(const Invalid& i) : e(i) { }
335 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
337 e(*(_G.graph), typename Graph::Node(_n)) {
338 while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
341 operator Edge() const { return Edge(typename Graph::Edge(e)); }
343 //typedef typename Graph::SymEdgeIt SymEdgeIt;
345 friend class GraphWrapper<Graph>;
346 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
347 typename Graph::EdgeIt e;
350 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
351 EdgeIt(const Invalid& i) : e(i) { }
352 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
354 while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
357 operator Edge() const { return Edge(typename Graph::Edge(e)); }
360 NodeIt& first(NodeIt& i) const {
361 i=NodeIt(*this); return i;
363 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
364 i=OutEdgeIt(*this, p); return i;
366 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
367 i=InEdgeIt(*this, p); return i;
369 EdgeIt& first(EdgeIt& i) const {
370 i=EdgeIt(*this); return i;
373 NodeIt& next(NodeIt& i) const {
374 this->graph->next(i.n);
375 while (this->graph->valid(i) && !(*node_filter_map)[i.n]) {
376 this->graph->next(i.n); }
379 OutEdgeIt& next(OutEdgeIt& i) const {
380 this->graph->next(i.e);
381 while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
382 this->graph->next(i.e); }
385 InEdgeIt& next(InEdgeIt& i) const {
386 this->graph->next(i.e);
387 while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
388 this->graph->next(i.e); }
391 EdgeIt& next(EdgeIt& i) const {
392 this->graph->next(i.e);
393 while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
394 this->graph->next(i.e); }
398 Node aNode(const OutEdgeIt& e) const {
399 return Node(this->graph->aNode(e.e)); }
400 Node aNode(const InEdgeIt& e) const {
401 return Node(this->graph->aNode(e.e)); }
402 Node bNode(const OutEdgeIt& e) const {
403 return Node(this->graph->bNode(e.e)); }
404 Node bNode(const InEdgeIt& e) const {
405 return Node(this->graph->bNode(e.e)); }
408 ///Some doki, please.
409 void hide(const Node& n) const { node_filter_map->set(n, false); }
411 ///Some doki, please.
412 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
415 ///Some doki, please.
416 void unHide(const Node& n) const { node_filter_map->set(n, true); }
418 ///Some doki, please.
419 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
422 ///Some doki, please.
423 bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
425 ///Some doki, please.
426 bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
429 /// A wrapper for forgetting the orientation of a graph.
431 /// A wrapper for getting an undirected graph by forgetting
432 /// the orientation of a directed one.
433 template<typename Graph>
434 class UndirGraphWrapper : public GraphWrapper<Graph> {
436 typedef typename GraphWrapper<Graph>::Node Node;
437 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
438 typedef typename GraphWrapper<Graph>::Edge Edge;
439 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
441 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
444 friend class UndirGraphWrapper<Graph>;
445 bool out_or_in; //true iff out
446 typename Graph::OutEdgeIt out;
447 typename Graph::InEdgeIt in;
450 OutEdgeIt(const Invalid& i) : Edge(i) { }
451 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
452 out_or_in=true; _G.graph->first(out, _n);
453 if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
455 operator Edge() const {
456 if (out_or_in) return Edge(out); else return Edge(in);
461 typedef OutEdgeIt InEdgeIt;
463 using GraphWrapper<Graph>::first;
464 // NodeIt& first(NodeIt& i) const {
465 // i=NodeIt(*this); return i;
467 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
468 i=OutEdgeIt(*this, p); return i;
471 // InEdgeIt& first(InEdgeIt& i, const Node& p) const {
472 // i=InEdgeIt(*this, p); return i;
474 // EdgeIt& first(EdgeIt& i) const {
475 // i=EdgeIt(*this); return i;
478 using GraphWrapper<Graph>::next;
479 // NodeIt& next(NodeIt& n) const {
480 // GraphWrapper<Graph>::next(n);
483 OutEdgeIt& next(OutEdgeIt& e) const {
485 typename Graph::Node n=this->graph->tail(e.out);
486 this->graph->next(e.out);
487 if (!this->graph->valid(e.out)) {
488 e.out_or_in=false; this->graph->first(e.in, n); }
490 this->graph->next(e.in);
495 // EdgeIt& next(EdgeIt& e) const {
496 // GraphWrapper<Graph>::next(n);
497 // // graph->next(e.e);
501 Node aNode(const OutEdgeIt& e) const {
502 if (e.out_or_in) return this->graph->tail(e); else
503 return this->graph->head(e); }
504 Node bNode(const OutEdgeIt& e) const {
505 if (e.out_or_in) return this->graph->head(e); else
506 return this->graph->tail(e); }
509 /// A wrapper for composing the residual graph for directed flow and circulation problems.
511 /// A wrapper for composing the residual graph for directed flow and circulation problems.
512 template<typename Graph, typename Number,
513 typename CapacityMap, typename FlowMap>
514 class ResGraphWrapper : public GraphWrapper<Graph> {
516 const CapacityMap* capacity;
520 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
522 GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
527 friend class OutEdgeIt;
529 typedef typename GraphWrapper<Graph>::Node Node;
530 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
531 class Edge : public Graph::Edge {
532 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
534 bool forward; //true, iff forward
535 // typename Graph::Edge e;
538 Edge(const typename Graph::Edge& _e, bool _forward) :
539 Graph::Edge(_e), forward(_forward) { }
540 Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
541 //the unique invalid iterator
542 friend bool operator==(const Edge& u, const Edge& v) {
543 return (v.forward==u.forward &&
544 static_cast<typename Graph::Edge>(u)==
545 static_cast<typename Graph::Edge>(v));
547 friend bool operator!=(const Edge& u, const Edge& v) {
548 return (v.forward!=u.forward ||
549 static_cast<typename Graph::Edge>(u)!=
550 static_cast<typename Graph::Edge>(v));
555 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
557 typename Graph::OutEdgeIt out;
558 typename Graph::InEdgeIt in;
563 // OutEdgeIt(const Edge& e) : Edge(e) { }
564 OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
565 //the unique invalid iterator
566 OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
568 resG.graph->first(out, v);
569 while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
570 if (!resG.graph->valid(out)) {
572 resG.graph->first(in, v);
573 while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
576 operator Edge() const {
578 // e.forward=this->forward;
579 // if (this->forward) e=out; else e=in;
582 return Edge(out, this->forward);
584 return Edge(in, this->forward);
589 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
591 typename Graph::OutEdgeIt out;
592 typename Graph::InEdgeIt in;
597 // OutEdgeIt(const Edge& e) : Edge(e) { }
598 InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
599 //the unique invalid iterator
600 InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
602 resG.graph->first(in, v);
603 while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
604 if (!resG.graph->valid(in)) {
606 resG.graph->first(out, v);
607 while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
610 operator Edge() const {
612 // e.forward=this->forward;
613 // if (this->forward) e=out; else e=in;
616 return Edge(in, this->forward);
618 return Edge(out, this->forward);
623 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
625 typename Graph::EdgeIt e;
629 EdgeIt(const Invalid& i) : e(i), forward(false) { }
630 EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {
632 resG.graph->first(e);
633 while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
634 if (!resG.graph->valid(e)) {
636 resG.graph->first(e);
637 while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
640 operator Edge() const {
641 return Edge(e, this->forward);
645 using GraphWrapper<Graph>::first;
646 // NodeIt& first(NodeIt& i) const {
647 // i=NodeIt(*this); return i;
649 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
650 i=OutEdgeIt(*this, p); return i;
653 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
654 i=InEdgeIt(*this, p); return i;
656 EdgeIt& first(EdgeIt& i) const {
657 i=EdgeIt(*this); return i;
660 using GraphWrapper<Graph>::next;
661 // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
662 OutEdgeIt& next(OutEdgeIt& e) const {
664 Node v=this->graph->aNode(e.out);
665 this->graph->next(e.out);
666 while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
667 this->graph->next(e.out); }
668 if (!this->graph->valid(e.out)) {
670 this->graph->first(e.in, v);
671 while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
672 this->graph->next(e.in); }
675 this->graph->next(e.in);
676 while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
677 this->graph->next(e.in); }
682 InEdgeIt& next(InEdgeIt& e) const {
684 Node v=this->graph->aNode(e.in);
685 this->graph->next(e.in);
686 while( this->graph->valid(e.in) && !(resCap(e)>0) ) {
687 this->graph->next(e.in); }
688 if (!this->graph->valid(e.in)) {
690 this->graph->first(e.out, v);
691 while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
692 this->graph->next(e.out); }
695 this->graph->next(e.out);
696 while( this->graph->valid(e.out) && !(resCap(e)>0) ) {
697 this->graph->next(e.out); }
701 EdgeIt& next(EdgeIt& e) const {
703 this->graph->next(e.e);
704 while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
705 this->graph->next(e.e); }
706 if (!this->graph->valid(e.e)) {
708 this->graph->first(e.e);
709 while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
710 this->graph->next(e.e); }
713 this->graph->next(e.e);
714 while( this->graph->valid(e.e) && !(resCap(e)>0) ) {
715 this->graph->next(e.e); }
720 Node tail(Edge e) const {
721 return ((e.forward) ? this->graph->tail(e) : this->graph->head(e)); }
722 Node head(Edge e) const {
723 return ((e.forward) ? this->graph->head(e) : this->graph->tail(e)); }
725 Node aNode(OutEdgeIt e) const {
726 return ((e.forward) ? this->graph->aNode(e.out) :
727 this->graph->aNode(e.in)); }
728 Node bNode(OutEdgeIt e) const {
729 return ((e.forward) ? this->graph->bNode(e.out) :
730 this->graph->bNode(e.in)); }
732 Node aNode(InEdgeIt e) const {
733 return ((e.forward) ? this->graph->aNode(e.in) :
734 this->graph->aNode(e.out)); }
735 Node bNode(InEdgeIt e) const {
736 return ((e.forward) ? this->graph->bNode(e.in) :
737 this->graph->bNode(e.out)); }
739 // int nodeNum() const { return graph->nodeNum(); }
741 void edgeNum() const { }
742 //int edgeNum() const { return graph->edgeNum(); }
745 // int id(Node v) const { return graph->id(v); }
747 bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
748 bool valid(Edge e) const {
749 return this->graph->valid(e);
750 //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
753 void augment(const Edge& e, Number a) const {
755 // flow->set(e.out, flow->get(e.out)+a);
756 flow->set(e, (*flow)[e]+a);
758 // flow->set(e.in, flow->get(e.in)-a);
759 flow->set(e, (*flow)[e]-a);
762 Number resCap(const Edge& e) const {
764 // return (capacity->get(e.out)-flow->get(e.out));
765 return ((*capacity)[e]-(*flow)[e]);
767 // return (flow->get(e.in));
771 // Number resCap(typename Graph::OutEdgeIt out) const {
772 // // return (capacity->get(out)-flow->get(out));
773 // return ((*capacity)[out]-(*flow)[out]);
776 // Number resCap(typename Graph::InEdgeIt in) const {
777 // // return (flow->get(in));
778 // return ((*flow)[in]);
781 template <typename T>
783 typename Graph::template EdgeMap<T> forward_map, backward_map;
785 EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
786 EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
787 void set(Edge e, T a) {
789 forward_map.set(e.out, a);
791 backward_map.set(e.in, a);
793 T operator[](Edge e) const {
795 return forward_map[e.out];
797 return backward_map[e.in];
799 // T get(Edge e) const {
801 // return forward_map.get(e.out);
803 // return backward_map.get(e.in);
808 /// ErasingFirstGraphWrapper for blocking flows.
810 /// ErasingFirstGraphWrapper for blocking flows.
811 template<typename Graph, typename FirstOutEdgesMap>
812 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
814 FirstOutEdgesMap* first_out_edges;
816 ErasingFirstGraphWrapper(Graph& _graph,
817 FirstOutEdgesMap& _first_out_edges) :
818 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
820 typedef typename GraphWrapper<Graph>::Node Node;
822 // friend class GraphWrapper<Graph>;
823 // friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
824 // typename Graph::NodeIt n;
827 // NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
828 // NodeIt(const Invalid& i) : n(i) { }
829 // NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
830 // n(*(_G.graph)) { }
831 // operator Node() const { return Node(typename Graph::Node(n)); }
833 typedef typename GraphWrapper<Graph>::Edge Edge;
835 friend class GraphWrapper<Graph>;
836 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
837 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
838 typename Graph::OutEdgeIt e;
841 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
842 OutEdgeIt(const Invalid& i) : e(i) { }
843 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
845 e((*_G.first_out_edges)[_n]) { }
846 operator Edge() const { return Edge(typename Graph::Edge(e)); }
849 friend class GraphWrapper<Graph>;
850 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
851 // typedef typename Graph::InEdgeIt GraphInEdgeIt;
852 typename Graph::InEdgeIt e;
855 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
856 InEdgeIt(const Invalid& i) : e(i) { }
857 InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
859 e(*(_G.graph), typename Graph::Node(_n)) { }
860 operator Edge() const { return Edge(typename Graph::Edge(e)); }
862 //typedef typename Graph::SymEdgeIt SymEdgeIt;
864 friend class GraphWrapper<Graph>;
865 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
866 // typedef typename Graph::EdgeIt GraphEdgeIt;
867 typename Graph::EdgeIt e;
870 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
871 EdgeIt(const Invalid& i) : e(i) { }
872 EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
874 operator Edge() const { return Edge(typename Graph::Edge(e)); }
877 using GraphWrapper<Graph>::first;
878 // NodeIt& first(NodeIt& i) const {
879 // i=NodeIt(*this); return i;
881 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
882 i=OutEdgeIt(*this, p); return i;
884 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
885 i=InEdgeIt(*this, p); return i;
887 EdgeIt& first(EdgeIt& i) const {
888 i=EdgeIt(*this); return i;
891 using GraphWrapper<Graph>::next;
892 // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
893 OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
894 InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
895 EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }
897 Node aNode(const OutEdgeIt& e) const {
898 return Node(this->graph->aNode(e.e)); }
899 Node aNode(const InEdgeIt& e) const {
900 return Node(this->graph->aNode(e.e)); }
901 Node bNode(const OutEdgeIt& e) const {
902 return Node(this->graph->bNode(e.e)); }
903 Node bNode(const InEdgeIt& e) const {
904 return Node(this->graph->bNode(e.e)); }
906 void erase(const OutEdgeIt& e) const {
909 first_out_edges->set(this->tail(e), f.e);
913 /// A wrapper for composing a bipartite graph.
914 /// \c _graph have to be a reference to a graph of type \c Graph
915 /// and \c _s_false_t_true_map is an \c IterableBoolMap
916 /// reference containing the elements for the
917 /// color classes S and T. \c _graph is to be referred to an undirected
918 /// graph or a directed graph with edges oriented from S to T.
919 template<typename Graph>
920 class BipartiteGraphWrapper : public GraphWrapper<Graph> {
921 typedef IterableBoolMap< typename Graph::template NodeMap<int> >
923 SFalseTTrueMap* s_false_t_true_map;
927 //FIXME vhogy igy kellene, csak az en forditom nem eszi meg
928 //static const bool S_CLASS=false;
929 //static const bool T_CLASS=true;
934 BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map)
935 : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map),
936 S_CLASS(false), T_CLASS(true) { }
937 typedef typename GraphWrapper<Graph>::Node Node;
938 //using GraphWrapper<Graph>::NodeIt;
939 typedef typename GraphWrapper<Graph>::Edge Edge;
940 //using GraphWrapper<Graph>::EdgeIt;
942 friend class ClassNodeIt;
944 friend class OutEdgeIt;
946 friend class InEdgeIt;
948 friend class BipartiteGraphWrapper<Graph>;
953 ClassNodeIt(const Invalid& i) : n(i) { }
954 ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) {
955 _G.s_false_t_true_map->first(n, _class);
957 //FIXME needed in new concept, important here
958 ClassNodeIt(const Node& _n) : n(_n) { }
959 operator Node() const { return n; }
965 // SNodeIt(const Invalid& i) : n(i) { }
966 // SNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
967 // _G.s_false_t_true_map->first(n, false);
969 // operator Node() const { return n; }
975 // TNodeIt(const Invalid& i) : n(i) { }
976 // TNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
977 // _G.s_false_t_true_map->first(n, true);
979 // operator Node() const { return n; }
982 friend class BipartiteGraphWrapper<Graph>;
984 typename Graph::OutEdgeIt e;
987 OutEdgeIt(const Invalid& i) : e(i) { }
988 OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
989 if (!(*(_G.s_false_t_true_map))[_n])
990 e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
994 operator Edge() const { return Edge(typename Graph::Edge(e)); }
997 friend class BipartiteGraphWrapper<Graph>;
999 typename Graph::InEdgeIt e;
1002 InEdgeIt(const Invalid& i) : e(i) { }
1003 InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
1004 if ((*(_G.s_false_t_true_map))[_n])
1005 e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));
1009 operator Edge() const { return Edge(typename Graph::Edge(e)); }
1012 using GraphWrapper<Graph>::first;
1013 ClassNodeIt& first(ClassNodeIt& n, bool _class) const {
1014 n=ClassNodeIt(*this, _class) ; return n; }
1015 // SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
1016 // TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
1017 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1018 i=OutEdgeIt(*this, p); return i;
1020 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1021 i=InEdgeIt(*this, p); return i;
1024 using GraphWrapper<Graph>::next;
1025 ClassNodeIt& next(ClassNodeIt& n) const {
1026 this->s_false_t_true_map->next(n.n); return n;
1028 // SNodeIt& next(SNodeIt& n) const {
1029 // this->s_false_t_true_map->next(n); return n;
1031 // TNodeIt& next(TNodeIt& n) const {
1032 // this->s_false_t_true_map->next(n); return n;
1034 OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
1035 InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
1037 Node tail(const Edge& e) {
1038 if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
1039 return Node(this->graph->tail(e));
1041 return Node(this->graph->head(e));
1043 Node head(const Edge& e) {
1044 if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
1045 return Node(this->graph->head(e));
1047 return Node(this->graph->tail(e));
1050 Node aNode(const OutEdgeIt& e) const {
1051 return Node(this->graph->aNode(e.e));
1053 Node aNode(const InEdgeIt& e) const {
1054 return Node(this->graph->aNode(e.e));
1056 Node bNode(const OutEdgeIt& e) const {
1057 return Node(this->graph->bNode(e.e));
1059 Node bNode(const InEdgeIt& e) const {
1060 return Node(this->graph->bNode(e.e));
1063 bool inSClass(const Node& n) const {
1064 return !(*(this->s_false_t_true_map))[n];
1066 bool inTClass(const Node& n) const {
1067 return (*(this->s_false_t_true_map))[n];
1072 /// experimentral, do not try it.
1073 /// It eats a bipartite graph, oriented from S to T.
1074 /// Such one can be made e.g. by the above wrapper.
1075 template<typename Graph>
1076 class stGraphWrapper : public GraphWrapper<Graph> {
1081 //0 normalis, 1 s, 2, true, ez az iteralasi sorrend,
1082 //es a vege a false azaz (invalid, 3)
1084 friend class NodeIt;
1089 //0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend,
1090 //invalid: (invalid, 3, invalid)
1092 friend class OutEdgeIt;
1094 //normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid)
1095 //s-bol (invalid, 1, first), ... (invalid, 3, invalid)
1096 //t-bol (invalid, 3, invalid)
1098 friend class InEdgeIt;
1100 //normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid)
1101 //s-be (invalid, 3, invalid)
1102 //t-be (invalid, 2, first), ... (invalid, 3, invalid)
1104 friend class EdgeIt;
1105 //(first, 0, invalid) ...
1108 //invalid, 3, invalid)
1109 template <typename T> class NodeMap;
1110 template <typename T, typename Parent> class EdgeMap;
1112 // template <typename T> friend class NodeMap;
1113 // template <typename T> friend class EdgeMap;
1118 static const bool S_CLASS=false;
1119 static const bool T_CLASS=true;
1121 stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) ,
1123 T_NODE(INVALID, 2) { }
1125 class Node : public Graph::Node {
1127 friend class GraphWrapper<Graph>;
1128 friend class stGraphWrapper<Graph>;
1129 template <typename T> friend class NodeMap;
1131 friend class OutEdgeIt;
1132 friend class InEdgeIt;
1133 friend class EdgeIt;
1137 Node(const typename Graph::Node& _n, int _spec=0) :
1138 Graph::Node(_n), spec(_spec) { }
1139 Node(const Invalid& i) : Graph::Node(i), spec(3) { }
1140 friend bool operator==(const Node& u, const Node& v) {
1141 return (u.spec==v.spec &&
1142 static_cast<typename Graph::Node>(u)==
1143 static_cast<typename Graph::Node>(v));
1145 friend bool operator!=(const Node& u, const Node& v) {
1146 return (v.spec!=u.spec ||
1147 static_cast<typename Graph::Node>(u)!=
1148 static_cast<typename Graph::Node>(v));
1150 friend std::ostream& operator<<(std::ostream& os, const Node& i);
1151 int getSpec() const { return spec; }
1155 friend class GraphWrapper<Graph>;
1156 friend class stGraphWrapper<Graph>;
1157 typename Graph::NodeIt n;
1161 NodeIt(const typename Graph::NodeIt& _n, int _spec) :
1162 n(_n), spec(_spec) { }
1163 NodeIt(const Invalid& i) : n(i), spec(3) { }
1164 NodeIt(const stGraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) {
1165 if (!_G.graph->valid(n)) spec=1;
1167 operator Node() const { return Node(n, spec); }
1170 class Edge : public Graph::Edge {
1171 friend class GraphWrapper<Graph>;
1172 friend class stGraphWrapper<Graph>;
1173 template <typename T, typename Parent> friend class EdgeMap;
1175 typename Graph::Node n;
1178 Edge(const typename Graph::Edge& _e, int _spec,
1179 const typename Graph::Node& _n) :
1180 Graph::Edge(_e), spec(_spec), n(_n) {
1182 Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { }
1183 friend bool operator==(const Edge& u, const Edge& v) {
1184 return (u.spec==v.spec &&
1185 static_cast<typename Graph::Edge>(u)==
1186 static_cast<typename Graph::Edge>(v) &&
1189 friend bool operator!=(const Edge& u, const Edge& v) {
1190 return (v.spec!=u.spec ||
1191 static_cast<typename Graph::Edge>(u)!=
1192 static_cast<typename Graph::Edge>(v) ||
1195 friend std::ostream& operator<<(std::ostream& os, const Edge& i);
1196 int getSpec() const { return spec; }
1200 friend class GraphWrapper<Graph>;
1201 friend class stGraphWrapper<Graph>;
1202 typename Graph::OutEdgeIt e;
1204 typename Graph::ClassNodeIt n;
1207 OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec,
1208 const typename Graph::ClassNodeIt& _n) :
1209 e(_e), spec(_spec), n(_n) {
1211 OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
1212 OutEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
1215 if (_G.graph->inSClass(_n)) { //S, van normalis kiel
1216 e=typename Graph::OutEdgeIt(*(_G.graph),
1217 typename Graph::Node(_n));
1220 if (!_G.graph->valid(e)) spec=3;
1221 } else { //T, specko kiel van
1230 _G.graph->first(n, S_CLASS); //s->vmi;
1231 if (!_G.graph->valid(n)) spec=3; //Ha S ures
1240 operator Edge() const { return Edge(e, spec, n); }
1244 friend class GraphWrapper<Graph>;
1245 friend class stGraphWrapper<Graph>;
1246 typename Graph::InEdgeIt e;
1248 typename Graph::ClassNodeIt n;
1251 InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec,
1252 const typename Graph::ClassNodeIt& _n) :
1253 e(_e), spec(_spec), n(_n) {
1255 InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
1256 InEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
1259 if (_G.graph->inTClass(_n)) { //T, van normalis beel
1260 e=typename Graph::InEdgeIt(*(_G.graph),
1261 typename Graph::Node(_n));
1264 if (!_G.graph->valid(e)) spec=3;
1265 } else { //S, specko beel van
1279 _G.graph->first(n, T_CLASS); //vmi->t;
1280 if (!_G.graph->valid(n)) spec=3; //Ha T ures
1284 operator Edge() const { return Edge(e, spec, n); }
1288 friend class GraphWrapper<Graph>;
1289 friend class stGraphWrapper<Graph>;
1290 typename Graph::EdgeIt e;
1292 typename Graph::ClassNodeIt n;
1295 EdgeIt(const typename Graph::EdgeIt& _e, int _spec,
1296 const typename Graph::ClassNodeIt& _n) :
1297 e(_e), spec(_spec), n(_n) { }
1298 EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
1299 EdgeIt(const stGraphWrapper<Graph>& _G) :
1300 e(*(_G.graph)), spec(0), n(INVALID) {
1301 if (!_G.graph->valid(e)) {
1303 _G.graph->first(n, S_CLASS);
1304 if (!_G.graph->valid(n)) { //Ha S ures
1306 _G.graph->first(n, T_CLASS);
1307 if (!_G.graph->valid(n)) { //Ha T ures
1313 operator Edge() const { return Edge(e, spec, n); }
1316 NodeIt& first(NodeIt& i) const {
1317 i=NodeIt(*this); return i;
1319 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1320 i=OutEdgeIt(*this, p); return i;
1322 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1323 i=InEdgeIt(*this, p); return i;
1325 EdgeIt& first(EdgeIt& i) const {
1326 i=EdgeIt(*this); return i;
1329 NodeIt& next(NodeIt& i) const {
1332 this->graph->next(i.n);
1333 if (!this->graph->valid(i.n)) {
1346 OutEdgeIt& next(OutEdgeIt& i) const {
1347 typename Graph::Node v;
1349 case 0: //normal edge
1350 v=this->graph->aNode(i.e);
1351 this->graph->next(i.e);
1352 if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
1353 if (this->graph->inSClass(v)) { //S, nincs kiel
1356 } else { //T, van kiel
1363 this->graph->next(i.n);
1364 if (!this->graph->valid(i.n)) i.spec=3;
1373 InEdgeIt& next(InEdgeIt& i) const {
1374 typename Graph::Node v;
1376 case 0: //normal edge
1377 v=this->graph->aNode(i.e);
1378 this->graph->next(i.e);
1379 if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
1380 if (this->graph->inTClass(v)) { //S, nincs beel
1383 } else { //S, van beel
1394 this->graph->next(i.n);
1395 if (!this->graph->valid(i.n)) i.spec=3;
1401 EdgeIt& next(EdgeIt& i) const {
1404 this->graph->next(i.e);
1405 if (!this->graph->valid(i.e)) {
1407 this->graph->first(i.n, S_CLASS);
1408 if (!this->graph->valid(i.n)) {
1410 this->graph->first(i.n, T_CLASS);
1411 if (!this->graph->valid(i.n)) i.spec=3;
1416 this->graph->next(i.n);
1417 if (!this->graph->valid(i.n)) {
1419 this->graph->first(i.n, T_CLASS);
1420 if (!this->graph->valid(i.n)) i.spec=3;
1424 this->graph->next(i.n);
1425 if (!this->graph->valid(i.n)) i.spec=3;
1431 Node tail(const Edge& e) const {
1434 return Node(this->graph->tail(e));
1445 Node head(const Edge& e) const {
1448 return Node(this->graph->head(e));
1460 bool valid(const Node& n) const { return (n.spec<3); }
1461 bool valid(const Edge& e) const { return (e.spec<3); }
1463 int nodeNum() const { return this->graph->nodeNum()+2; }
1464 int edgeNum() const {
1465 return this->graph->edgeNum()+this->graph->nodeNum();
1468 Node aNode(const OutEdgeIt& e) const { return tail(e); }
1469 Node aNode(const InEdgeIt& e) const { return head(e); }
1470 Node bNode(const OutEdgeIt& e) const { return head(e); }
1471 Node bNode(const InEdgeIt& e) const { return tail(e); }
1473 void addNode() const { }
1474 void addEdge() const { }
1476 // Node addNode() const { return Node(this->graph->addNode()); }
1477 // Edge addEdge(const Node& tail, const Node& head) const {
1478 // return Edge(this->graph->addEdge(tail, head)); }
1480 // void erase(const Node& i) const { this->graph->erase(i); }
1481 // void erase(const Edge& i) const { this->graph->erase(i); }
1483 // void clear() const { this->graph->clear(); }
1485 template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> {
1486 typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;
1489 NodeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
1492 NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
1495 T operator[](const Node& n) const {
1498 return Parent::operator[](n);
1509 void set(const Node& n, T t) {
1512 GraphWrapper<Graph>::template NodeMap<T>::set(n, t);
1525 template<typename T,
1527 typename GraphWrapper<Graph>::template EdgeMap<T> >
1528 class EdgeMap : public Parent {
1529 //typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
1530 typename GraphWrapper<Graph>::template NodeMap<T> node_value;
1532 EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
1534 EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
1535 node_value(_G, a) { }
1536 T operator[](const Edge& e) const {
1539 return Parent::operator[](e);
1542 return node_value[e.n];
1546 return node_value[e.n];
1550 void set(const Edge& e, T t) {
1556 node_value.set(e.n, t);
1560 node_value.set(e.n, t);
1566 // template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> {
1567 // typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
1568 // typename GraphWrapper<Graph>::template NodeMap<T> node_value;
1570 // EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
1571 // node_value(_G) { }
1572 // EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
1573 // node_value(_G, a) { }
1574 // T operator[](const Edge& e) const {
1575 // switch (e.spec) {
1577 // return Parent::operator[](e);
1580 // return node_value[e.n];
1584 // return node_value[e.n];
1588 // void set(const Edge& e, T t) {
1589 // switch (e.spec) {
1591 // GraphWrapper<Graph>::template EdgeMap<T>::set(e, t);
1594 // node_value.set(e.n, t);
1598 // node_value.set(e.n, t);
1604 friend std::ostream& operator<<(std::ostream& os, const Node& i) {
1605 os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")";
1608 friend std::ostream& operator<<(std::ostream& os, const Edge& i) {
1609 os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec <<
1610 " node: " << i.n << ")";
1621 #endif //HUGO_GRAPH_WRAPPER_H