ResGraphWrapper running time comparison test.
2 #ifndef HUGO_GRAPH_WRAPPER_H
3 #define HUGO_GRAPH_WRAPPER_H
12 /// A main parts of HUGOlib are the different graph structures,
13 /// generic graph algorithms, graph concepts which couple these, and
14 /// graph wrappers. While the previous ones are more or less clear, the
15 /// latter notion needs further explanation.
16 /// Graph wrappers are graph classes which serve for considering graph
17 /// structures in different ways. A short example makes the notion much
19 /// Suppose that we have an instance \c g of a directed graph
20 /// type say \c ListGraph and an algorithm
21 /// \code template<typename Graph> int algorithm(const Graph&); \endcode
22 /// is needed to run on the reversely oriented graph.
23 /// It may be expensive (in time or in memory usage) to copy
24 /// \c g with the reverse orientation.
25 /// Thus, a wrapper class
26 /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.
27 /// The code looks as follows
30 /// RevGraphWrapper<ListGraph> rgw(g);
31 /// int result=algorithm(rgw);
33 /// After running the algorithm, the original graph \c g
34 /// remains untouched. Thus the graph wrapper used above is to consider the
35 /// original graph with reverse orientation.
36 /// This techniques gives rise to an elegant code, and
37 /// based on stable graph wrappers, complex algorithms can be
38 /// implemented easily.
39 /// In flow, circulation and bipartite matching problems, the residual
40 /// graph is of particular importance. Combining a wrapper implementing
41 /// this, shortest path algorithms and minimum mean cycle algorithms,
42 /// a range of weighted and cardinality optimization algorithms can be
43 /// obtained. For lack of space, for other examples,
44 /// the interested user is referred to the detailed documentation of graph
46 /// The behavior of graph wrappers can be very different. Some of them keep
47 /// capabilities of the original graph while in other cases this would be
48 /// meaningless. This means that the concepts that they are a model of depend
49 /// on the graph wrapper, and the wrapped graph(s).
50 /// If an edge of \c rgw is deleted, this is carried out by
51 /// deleting the corresponding edge of \c g. But for a residual
52 /// graph, this operation has no sense.
53 /// Let we stand one more example here to simplify your work.
55 /// \code template<typename Graph> class RevGraphWrapper; \endcode
57 /// <tt> RevGraphWrapper(Graph& _g)</tt>.
58 /// This means that in a situation,
59 /// when a <tt> const ListGraph& </tt> reference to a graph is given,
60 /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
62 /// int algorithm1(const ListGraph& g) {
63 /// RevGraphWrapper<const ListGraph> rgw(g);
64 /// return algorithm2(rgw);
67 template<typename Graph>
73 typedef Graph BaseGraph;
74 typedef Graph ParentGraph;
76 // GraphWrapper() : graph(0) { }
77 GraphWrapper(Graph& _graph) : graph(&_graph) { }
78 // void setGraph(Graph& _graph) { graph=&_graph; }
79 // Graph& getGraph() const { return *graph; }
81 // typedef typename Graph::Node Node;
82 class Node : public Graph::Node {
83 friend class GraphWrapper<Graph>;
86 Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
87 Node(const Invalid& i) : Graph::Node(i) { }
90 friend class GraphWrapper<Graph>;
91 typename Graph::NodeIt n;
94 NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
95 NodeIt(const Invalid& i) : n(i) { }
96 NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
97 operator Node() const { return Node(typename Graph::Node(n)); }
99 // typedef typename Graph::Edge Edge;
100 class Edge : public Graph::Edge {
101 friend class GraphWrapper<Graph>;
104 Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
105 Edge(const Invalid& i) : Graph::Edge(i) { }
108 friend class GraphWrapper<Graph>;
109 typename Graph::OutEdgeIt e;
112 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
113 OutEdgeIt(const Invalid& i) : e(i) { }
114 OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
115 e(*(_G.graph), typename Graph::Node(_n)) { }
116 operator Edge() const { return Edge(typename Graph::Edge(e)); }
119 friend class GraphWrapper<Graph>;
120 typename Graph::InEdgeIt e;
123 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
124 InEdgeIt(const Invalid& i) : e(i) { }
125 InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
126 e(*(_G.graph), typename Graph::Node(_n)) { }
127 operator Edge() const { return Edge(typename Graph::Edge(e)); }
129 //typedef typename Graph::SymEdgeIt SymEdgeIt;
131 friend class GraphWrapper<Graph>;
132 typename Graph::EdgeIt e;
135 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
136 EdgeIt(const Invalid& i) : e(i) { }
137 EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
138 operator Edge() const { return Edge(typename Graph::Edge(e)); }
141 NodeIt& first(NodeIt& i) const {
142 i=NodeIt(*this); return i;
144 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
145 i=OutEdgeIt(*this, p); return i;
147 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
148 i=InEdgeIt(*this, p); return i;
150 EdgeIt& first(EdgeIt& i) const {
151 i=EdgeIt(*this); return i;
154 NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
155 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
156 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
157 EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
159 Node tail(const Edge& e) const {
160 return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
161 Node head(const Edge& e) const {
162 return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
164 bool valid(const Node& n) const {
165 return graph->valid(static_cast<typename Graph::Node>(n)); }
166 bool valid(const Edge& e) const {
167 return graph->valid(static_cast<typename Graph::Edge>(e)); }
169 int nodeNum() const { return graph->nodeNum(); }
170 int edgeNum() const { return graph->edgeNum(); }
172 Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
173 Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
174 Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
175 Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
177 Node addNode() const { return Node(graph->addNode()); }
178 Edge addEdge(const Node& tail, const Node& head) const {
179 return Edge(graph->addEdge(tail, head)); }
181 void erase(const Node& i) const { graph->erase(i); }
182 void erase(const Edge& i) const { graph->erase(i); }
184 void clear() const { graph->clear(); }
186 template<typename T> class NodeMap : public Graph::NodeMap<T> {
188 NodeMap(const GraphWrapper<Graph>& _G) :
189 Graph::NodeMap<T>(*(_G.graph)) { }
190 NodeMap(const GraphWrapper<Graph>& _G, T a) :
191 Graph::NodeMap<T>(*(_G.graph), a) { }
194 template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
196 EdgeMap(const GraphWrapper<Graph>& _G) :
197 Graph::EdgeMap<T>(*(_G.graph)) { }
198 EdgeMap(const GraphWrapper<Graph>& _G, T a) :
199 Graph::EdgeMap<T>(*(_G.graph), a) { }
203 /// A graph wrapper which reverses the orientation of the edges.
205 /// A graph wrapper which reverses the orientation of the edges.
206 template<typename Graph>
207 class RevGraphWrapper : public GraphWrapper<Graph> {
210 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
212 typedef typename GraphWrapper<Graph>::Node Node;
213 typedef typename GraphWrapper<Graph>::Edge Edge;
214 //If Graph::OutEdgeIt is not defined
215 //and we do not want to use RevGraphWrapper::InEdgeIt,
216 //the typdef techinque does not work.
217 //Unfortunately all the typedefs are instantiated in templates.
218 //typedef typename GraphWrapper<Graph>::OutEdgeIt InEdgeIt;
219 //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
222 friend class GraphWrapper<Graph>;
223 friend class RevGraphWrapper<Graph>;
224 typename Graph::InEdgeIt e;
227 OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
228 OutEdgeIt(const Invalid& i) : e(i) { }
229 OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
230 e(*(_G.graph), typename Graph::Node(_n)) { }
231 operator Edge() const { return Edge(typename Graph::Edge(e)); }
234 friend class GraphWrapper<Graph>;
235 friend class RevGraphWrapper<Graph>;
236 typename Graph::OutEdgeIt e;
239 InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
240 InEdgeIt(const Invalid& i) : e(i) { }
241 InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
242 e(*(_G.graph), typename Graph::Node(_n)) { }
243 operator Edge() const { return Edge(typename Graph::Edge(e)); }
246 using GraphWrapper<Graph>::first;
247 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
248 i=OutEdgeIt(*this, p); return i;
250 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
251 i=InEdgeIt(*this, p); return i;
254 using GraphWrapper<Graph>::next;
255 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
256 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
258 Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
259 Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
260 Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
261 Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
263 Node tail(const Edge& e) const {
264 return GraphWrapper<Graph>::head(e); }
265 Node head(const Edge& e) const {
266 return GraphWrapper<Graph>::tail(e); }
270 /// Wrapper for hiding nodes and edges from a graph.
272 /// This wrapper shows a graph with filtered node-set and
273 /// edge-set. The quick brown fox iterator jumps over
274 /// the lazy dog nodes or edges if the values for them are false
275 /// in the bool maps.
276 template<typename Graph, typename NodeFilterMap,
277 typename EdgeFilterMap>
278 class SubGraphWrapper : public GraphWrapper<Graph> {
280 NodeFilterMap* node_filter_map;
281 EdgeFilterMap* edge_filter_map;
284 SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
285 EdgeFilterMap& _edge_filter_map) :
286 GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
287 edge_filter_map(&_edge_filter_map) { }
289 typedef typename GraphWrapper<Graph>::Node Node;
291 friend class GraphWrapper<Graph>;
292 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
293 typename Graph::NodeIt n;
296 NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
297 NodeIt(const Invalid& i) : n(i) { }
298 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
300 while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
303 operator Node() const { return Node(typename Graph::Node(n)); }
305 typedef typename GraphWrapper<Graph>::Edge Edge;
307 friend class GraphWrapper<Graph>;
308 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
309 typename Graph::OutEdgeIt e;
312 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
313 OutEdgeIt(const Invalid& i) : e(i) { }
314 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
316 e(*(_G.graph), typename Graph::Node(_n)) {
317 while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
320 operator Edge() const { return Edge(typename Graph::Edge(e)); }
323 friend class GraphWrapper<Graph>;
324 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
325 typename Graph::InEdgeIt e;
328 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
329 InEdgeIt(const Invalid& i) : e(i) { }
330 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
332 e(*(_G.graph), typename Graph::Node(_n)) {
333 while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
336 operator Edge() const { return Edge(typename Graph::Edge(e)); }
338 //typedef typename Graph::SymEdgeIt SymEdgeIt;
340 friend class GraphWrapper<Graph>;
341 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
342 typename Graph::EdgeIt e;
345 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
346 EdgeIt(const Invalid& i) : e(i) { }
347 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
349 while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
352 operator Edge() const { return Edge(typename Graph::Edge(e)); }
355 NodeIt& first(NodeIt& i) const {
356 i=NodeIt(*this); return i;
358 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
359 i=OutEdgeIt(*this, p); return i;
361 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
362 i=InEdgeIt(*this, p); return i;
364 EdgeIt& first(EdgeIt& i) const {
365 i=EdgeIt(*this); return i;
368 NodeIt& next(NodeIt& i) const {
370 while (graph->valid(i) && !(*node_filter_map)[i.n]) { graph->next(i.n); }
373 OutEdgeIt& next(OutEdgeIt& i) const {
375 while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
378 InEdgeIt& next(InEdgeIt& i) const {
380 while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
383 EdgeIt& next(EdgeIt& i) const {
385 while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
389 Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
390 Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
391 Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
392 Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
395 ///Some doki, please.
396 void hide(const Node& n) const { node_filter_map->set(n, false); }
398 ///Some doki, please.
399 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
402 ///Some doki, please.
403 void unHide(const Node& n) const { node_filter_map->set(n, true); }
405 ///Some doki, please.
406 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
409 ///Some doki, please.
410 bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
412 ///Some doki, please.
413 bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
416 /// A wrapper for forgetting the orientation of a graph.
418 /// A wrapper for getting an undirected graph by forgetting
419 /// the orientation of a directed one.
420 template<typename Graph>
421 class UndirGraphWrapper : public GraphWrapper<Graph> {
423 typedef typename GraphWrapper<Graph>::Node Node;
424 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
425 typedef typename GraphWrapper<Graph>::Edge Edge;
426 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
428 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
431 friend class UndirGraphWrapper<Graph>;
432 bool out_or_in; //true iff out
433 typename Graph::OutEdgeIt out;
434 typename Graph::InEdgeIt in;
437 OutEdgeIt(const Invalid& i) : Edge(i) { }
438 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
439 out_or_in=true; _G.graph->first(out, _n);
440 if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
442 operator Edge() const {
443 if (out_or_in) return Edge(out); else return Edge(in);
448 typedef OutEdgeIt InEdgeIt;
450 using GraphWrapper<Graph>::first;
451 // NodeIt& first(NodeIt& i) const {
452 // i=NodeIt(*this); return i;
454 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
455 i=OutEdgeIt(*this, p); return i;
458 // InEdgeIt& first(InEdgeIt& i, const Node& p) const {
459 // i=InEdgeIt(*this, p); return i;
461 // EdgeIt& first(EdgeIt& i) const {
462 // i=EdgeIt(*this); return i;
465 using GraphWrapper<Graph>::next;
466 // NodeIt& next(NodeIt& n) const {
467 // GraphWrapper<Graph>::next(n);
470 OutEdgeIt& next(OutEdgeIt& e) const {
472 typename Graph::Node n=graph->tail(e.out);
474 if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }
481 // EdgeIt& next(EdgeIt& e) const {
482 // GraphWrapper<Graph>::next(n);
483 // // graph->next(e.e);
487 Node aNode(const OutEdgeIt& e) const {
488 if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
489 Node bNode(const OutEdgeIt& e) const {
490 if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
493 /// A wrapper for composing the residual graph for directed flow and circulation problems.
495 /// A wrapper for composing the residual graph for directed flow and circulation problems.
496 template<typename Graph, typename Number,
497 typename CapacityMap, typename FlowMap>
498 class ResGraphWrapper : public GraphWrapper<Graph> {
500 const CapacityMap* capacity;
504 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
506 GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
511 friend class OutEdgeIt;
513 typedef typename GraphWrapper<Graph>::Node Node;
514 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
515 class Edge : public Graph::Edge {
516 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
518 bool forward; //true, iff forward
519 // typename Graph::Edge e;
522 Edge(const typename Graph::Edge& _e, bool _forward) :
523 Graph::Edge(_e), forward(_forward) { }
524 Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
525 //the unique invalid iterator
526 friend bool operator==(const Edge& u, const Edge& v) {
527 return (v.forward==u.forward &&
528 static_cast<typename Graph::Edge>(u)==
529 static_cast<typename Graph::Edge>(v));
531 friend bool operator!=(const Edge& u, const Edge& v) {
532 return (v.forward!=u.forward ||
533 static_cast<typename Graph::Edge>(u)!=
534 static_cast<typename Graph::Edge>(v));
539 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
541 typename Graph::OutEdgeIt out;
542 typename Graph::InEdgeIt in;
547 // OutEdgeIt(const Edge& e) : Edge(e) { }
548 OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
549 //the unique invalid iterator
550 OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
552 resG.graph->first(out, v);
553 while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
554 if (!resG.graph->valid(out)) {
556 resG.graph->first(in, v);
557 while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
560 operator Edge() const {
562 // e.forward=this->forward;
563 // if (this->forward) e=out; else e=in;
566 return Edge(out, this->forward);
568 return Edge(in, this->forward);
573 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
575 typename Graph::OutEdgeIt out;
576 typename Graph::InEdgeIt in;
581 // OutEdgeIt(const Edge& e) : Edge(e) { }
582 InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
583 //the unique invalid iterator
584 InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) {
586 resG.graph->first(in, v);
587 while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
588 if (!resG.graph->valid(in)) {
590 resG.graph->first(out, v);
591 while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
594 operator Edge() const {
596 // e.forward=this->forward;
597 // if (this->forward) e=out; else e=in;
600 return Edge(in, this->forward);
602 return Edge(out, this->forward);
607 friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
609 typename Graph::EdgeIt e;
613 EdgeIt(const Invalid& i) : e(i), forward(false) { }
614 EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) {
616 resG.graph->first(e);
617 while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
618 if (!resG.graph->valid(e)) {
620 resG.graph->first(e);
621 while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
624 operator Edge() const {
625 return Edge(e, this->forward);
629 using GraphWrapper<Graph>::first;
630 // NodeIt& first(NodeIt& i) const {
631 // i=NodeIt(*this); return i;
633 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
634 i=OutEdgeIt(*this, p); return i;
637 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
638 i=InEdgeIt(*this, p); return i;
640 EdgeIt& first(EdgeIt& i) const {
641 i=EdgeIt(*this); return i;
644 using GraphWrapper<Graph>::next;
645 // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
646 OutEdgeIt& next(OutEdgeIt& e) const {
648 Node v=graph->aNode(e.out);
650 while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
651 if (!graph->valid(e.out)) {
653 graph->first(e.in, v);
654 while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
658 while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
663 InEdgeIt& next(InEdgeIt& e) const {
665 Node v=graph->aNode(e.in);
667 while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
668 if (!graph->valid(e.in)) {
670 graph->first(e.out, v);
671 while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
675 while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
679 EdgeIt& next(EdgeIt& e) const {
682 while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
683 if (!graph->valid(e.e)) {
686 while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
690 while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
695 Node tail(Edge e) const {
696 return ((e.forward) ? graph->tail(e) : graph->head(e)); }
697 Node head(Edge e) const {
698 return ((e.forward) ? graph->head(e) : graph->tail(e)); }
700 Node aNode(OutEdgeIt e) const {
701 return ((e.forward) ? graph->aNode(e.out) : graph->aNode(e.in)); }
702 Node bNode(OutEdgeIt e) const {
703 return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); }
705 Node aNode(InEdgeIt e) const {
706 return ((e.forward) ? graph->aNode(e.in) : graph->aNode(e.out)); }
707 Node bNode(InEdgeIt e) const {
708 return ((e.forward) ? graph->bNode(e.in) : graph->bNode(e.out)); }
710 // int nodeNum() const { return graph->nodeNum(); }
712 void edgeNum() const { }
713 //int edgeNum() const { return graph->edgeNum(); }
716 // int id(Node v) const { return graph->id(v); }
718 bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
719 bool valid(Edge e) const {
720 return graph->valid(e);
721 //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
724 void augment(const Edge& e, Number a) const {
726 // flow->set(e.out, flow->get(e.out)+a);
727 flow->set(e, (*flow)[e]+a);
729 // flow->set(e.in, flow->get(e.in)-a);
730 flow->set(e, (*flow)[e]-a);
733 Number resCap(const Edge& e) const {
735 // return (capacity->get(e.out)-flow->get(e.out));
736 return ((*capacity)[e]-(*flow)[e]);
738 // return (flow->get(e.in));
742 // Number resCap(typename Graph::OutEdgeIt out) const {
743 // // return (capacity->get(out)-flow->get(out));
744 // return ((*capacity)[out]-(*flow)[out]);
747 // Number resCap(typename Graph::InEdgeIt in) const {
748 // // return (flow->get(in));
749 // return ((*flow)[in]);
752 template <typename T>
754 typename Graph::EdgeMap<T> forward_map, backward_map;
756 EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
757 EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
758 void set(Edge e, T a) {
760 forward_map.set(e.out, a);
762 backward_map.set(e.in, a);
764 T operator[](Edge e) const {
766 return forward_map[e.out];
768 return backward_map[e.in];
770 // T get(Edge e) const {
772 // return forward_map.get(e.out);
774 // return backward_map.get(e.in);
779 /// ErasingFirstGraphWrapper for blocking flows.
781 /// ErasingFirstGraphWrapper for blocking flows.
782 template<typename Graph, typename FirstOutEdgesMap>
783 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
785 FirstOutEdgesMap* first_out_edges;
787 ErasingFirstGraphWrapper(Graph& _graph,
788 FirstOutEdgesMap& _first_out_edges) :
789 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
791 typedef typename GraphWrapper<Graph>::Node Node;
793 // friend class GraphWrapper<Graph>;
794 // friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
795 // typename Graph::NodeIt n;
798 // NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
799 // NodeIt(const Invalid& i) : n(i) { }
800 // NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
801 // n(*(_G.graph)) { }
802 // operator Node() const { return Node(typename Graph::Node(n)); }
804 typedef typename GraphWrapper<Graph>::Edge Edge;
806 friend class GraphWrapper<Graph>;
807 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
808 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
809 typename Graph::OutEdgeIt e;
812 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
813 OutEdgeIt(const Invalid& i) : e(i) { }
814 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
816 e((*_G.first_out_edges)[_n]) { }
817 operator Edge() const { return Edge(typename Graph::Edge(e)); }
820 friend class GraphWrapper<Graph>;
821 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
822 // typedef typename Graph::InEdgeIt GraphInEdgeIt;
823 typename Graph::InEdgeIt e;
826 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
827 InEdgeIt(const Invalid& i) : e(i) { }
828 InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
830 e(*(_G.graph), typename Graph::Node(_n)) { }
831 operator Edge() const { return Edge(typename Graph::Edge(e)); }
833 //typedef typename Graph::SymEdgeIt SymEdgeIt;
835 friend class GraphWrapper<Graph>;
836 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
837 // typedef typename Graph::EdgeIt GraphEdgeIt;
838 typename Graph::EdgeIt e;
841 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
842 EdgeIt(const Invalid& i) : e(i) { }
843 EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
845 operator Edge() const { return Edge(typename Graph::Edge(e)); }
848 using GraphWrapper<Graph>::first;
849 // NodeIt& first(NodeIt& i) const {
850 // i=NodeIt(*this); return i;
852 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
853 i=OutEdgeIt(*this, p); return i;
855 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
856 i=InEdgeIt(*this, p); return i;
858 EdgeIt& first(EdgeIt& i) const {
859 i=EdgeIt(*this); return i;
862 using GraphWrapper<Graph>::next;
863 // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
864 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
865 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
866 EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
868 Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
869 Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
870 Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
871 Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
873 void erase(const OutEdgeIt& e) const {
876 first_out_edges->set(this->tail(e), f.e);
880 /// A wrapper for composing a bipartite graph.
881 /// \c _graph have to be a reference to a graph of type \c Graph
882 /// and \c _s_false_t_true_map is an \c IterableBoolMap
883 /// reference containing the elements for the
884 /// color classes S and T. \c _graph is to be referred to an undirected
885 /// graph or a directed graph with edges oriented from S to T.
886 template<typename Graph>
887 class BipartiteGraphWrapper : public GraphWrapper<Graph> {
888 typedef IterableBoolMap< typename Graph::NodeMap<int> > SFalseTTrueMap;
889 SFalseTTrueMap* s_false_t_true_map;
892 static const bool S_CLASS=false;
893 static const bool T_CLASS=true;
895 BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map)
896 : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map) {
898 typedef typename GraphWrapper<Graph>::Node Node;
899 //using GraphWrapper<Graph>::NodeIt;
900 typedef typename GraphWrapper<Graph>::Edge Edge;
901 //using GraphWrapper<Graph>::EdgeIt;
906 ClassNodeIt(const Invalid& i) : n(i) { }
907 ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) {
908 _G.s_false_t_true_map->first(n, _class);
910 //FIXME needed in new concept, important here
911 ClassNodeIt(const Node& _n) : n(_n) { }
912 operator Node() const { return n; }
918 // SNodeIt(const Invalid& i) : n(i) { }
919 // SNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
920 // _G.s_false_t_true_map->first(n, false);
922 // operator Node() const { return n; }
928 // TNodeIt(const Invalid& i) : n(i) { }
929 // TNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
930 // _G.s_false_t_true_map->first(n, true);
932 // operator Node() const { return n; }
937 typename Graph::OutEdgeIt e;
940 OutEdgeIt(const Invalid& i) : e(i) { }
941 OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
942 if (!(*(_G.s_false_t_true_map))[_n])
943 e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
947 operator Edge() const { return Edge(typename Graph::Edge(e)); }
951 typename Graph::InEdgeIt e;
954 InEdgeIt(const Invalid& i) : e(i) { }
955 InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
956 if ((*(_G.s_false_t_true_map))[_n])
957 e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));
961 operator Edge() const { return Edge(typename Graph::Edge(e)); }
964 using GraphWrapper<Graph>::first;
965 ClassNodeIt& first(ClassNodeIt& n, bool _class) const {
966 n=SNodeIt(*this, _class) ; return n; }
967 // SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
968 // TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
969 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
970 i=OutEdgeIt(*this, p); return i;
972 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
973 i=InEdgeIt(*this, p); return i;
976 using GraphWrapper<Graph>::next;
977 ClassNodeIt& next(ClassNodeIt& n) const {
978 this->s_false_t_true_map->next(n); return n;
980 // SNodeIt& next(SNodeIt& n) const {
981 // this->s_false_t_true_map->next(n); return n;
983 // TNodeIt& next(TNodeIt& n) const {
984 // this->s_false_t_true_map->next(n); return n;
986 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
987 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
989 Node tail(const Edge& e) {
990 if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
991 return Node(this->graph->tail(e));
993 return Node(this->graph->head(e));
995 Node head(const Edge& e) {
996 if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
997 return Node(this->graph->head(e));
999 return Node(this->graph->tail(e));
1002 Node aNode(const OutEdgeIt& e) const {
1003 return Node(this->graph->aNode(e.e));
1005 Node aNode(const InEdgeIt& e) const {
1006 return Node(this->graph->aNode(e.e));
1008 Node bNode(const OutEdgeIt& e) const {
1009 return Node(this->graph->bNode(e.e));
1011 Node bNode(const InEdgeIt& e) const {
1012 return Node(this->graph->bNode(e.e));
1015 bool inSClass(const Node& n) const {
1016 return !(*(this->s_false_t_true_map))[n];
1018 bool inTClass(const Node& n) const {
1019 return (*(this->s_false_t_true_map))[n];
1024 /// experimentral, do not try it.
1025 /// It eats a bipartite graph, oriented from S to T.
1026 /// Such one can be made e.g. by the above wrapper.
1027 template<typename Graph>
1028 class stGraphWrapper : public GraphWrapper<Graph> {
1033 //0 normalis, 1 s, 2, true, ez az iteralasi sorrend,
1034 //es a vege a false azaz (invalid, 3)
1036 friend class NodeIt;
1041 //0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend,
1042 //invalid: (invalid, 3, invalid)
1044 friend class OutEdgeIt;
1046 //normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid)
1047 //s-bol (invalid, 1, first), ... (invalid, 3, invalid)
1048 //t-bol (invalid, 3, invalid)
1050 friend class InEdgeIt;
1052 //normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid)
1053 //s-be (invalid, 3, invalid)
1054 //t-be (invalid, 2, first), ... (invalid, 3, invalid)
1056 friend class EdgeIt;
1057 //(first, 0, invalid) ...
1060 //invalid, 3, invalid)
1061 template <typename T> class NodeMap;
1062 template <typename T> class EdgeMap;
1064 // template <typename T> friend class NodeMap;
1065 // template <typename T> friend class EdgeMap;
1070 static const bool S_CLASS=false;
1071 static const bool T_CLASS=true;
1073 stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) ,
1075 T_NODE(INVALID, 2) { }
1077 class Node : public Graph::Node {
1079 friend class GraphWrapper<Graph>;
1080 friend class stGraphWrapper<Graph>;
1081 template <typename T> friend class stGraphWrapper<Graph>::NodeMap;
1083 friend class OutEdgeIt;
1084 friend class InEdgeIt;
1085 friend class EdgeIt;
1089 Node(const typename Graph::Node& _n, int _spec=0) :
1090 Graph::Node(_n), spec(_spec) { }
1091 Node(const Invalid& i) : Graph::Node(i), spec(3) { }
1092 friend bool operator==(const Node& u, const Node& v) {
1093 return (u.spec==v.spec &&
1094 static_cast<typename Graph::Node>(u)==
1095 static_cast<typename Graph::Node>(v));
1097 friend bool operator!=(const Node& u, const Node& v) {
1098 return (v.spec!=u.spec ||
1099 static_cast<typename Graph::Node>(u)!=
1100 static_cast<typename Graph::Node>(v));
1102 int getSpec() const { return spec; }
1105 friend class GraphWrapper<Graph>;
1106 friend class stGraphWrapper<Graph>;
1107 typename Graph::NodeIt n;
1111 NodeIt(const typename Graph::NodeIt& _n, int _spec) :
1112 n(_n), spec(_spec) { }
1113 NodeIt(const Invalid& i) : n(i), spec(3) { }
1114 NodeIt(const stGraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) {
1115 if (!_G->valid(n)) spec=1;
1117 operator Node() const { return Node(n, spec); }
1119 class Edge : public Graph::Edge {
1120 friend class GraphWrapper<Graph>;
1121 friend class stGraphWrapper<Graph>;
1122 template <typename T> friend class stGraphWrapper<Graph>::EdgeMap;
1124 typename Graph::Node n;
1127 Edge(const typename Graph::Edge& _e, int _spec,
1128 const typename Graph::Node& _n) :
1129 Graph::Edge(_e), spec(_spec), n(_n) {
1131 Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { }
1132 friend bool operator==(const Edge& u, const Edge& v) {
1133 return (u.spec==v.spec &&
1134 static_cast<typename Graph::Edge>(u)==
1135 static_cast<typename Graph::Edge>(v) &&
1138 friend bool operator!=(const Edge& u, const Edge& v) {
1139 return (v.spec!=u.spec ||
1140 static_cast<typename Graph::Edge>(u)!=
1141 static_cast<typename Graph::Edge>(v) ||
1144 int getSpec() const { return spec; }
1147 friend class GraphWrapper<Graph>;
1148 friend class stGraphWrapper<Graph>;
1149 typename Graph::OutEdgeIt e;
1151 typename Graph::ClassNodeIt n;
1154 OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec,
1155 const typename Graph::ClassNodeIt& _n) :
1156 e(_e), spec(_spec), n(_n) {
1158 OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
1159 OutEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
1162 if (_G.graph->inSClass(_n)) { //S, van normalis kiel
1163 e=typename Graph::OutEdgeIt(*(_G.graph),
1164 typename Graph::Node(_n));
1167 if (!_G.graph->valid(e)) spec=3;
1168 } else { //T, specko kiel van
1177 _G.graph->first(n, S_CLASS); //s->vmi;
1178 if (!_G.graph->valid(n)) spec=3; //Ha S ures
1187 operator Edge() const { return Edge(e, spec, n); }
1190 friend class GraphWrapper<Graph>;
1191 friend class stGraphWrapper<Graph>;
1192 typename Graph::InEdgeIt e;
1194 typename Graph::ClassNodeIt n;
1197 InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec,
1198 const typename Graph::ClassNodeIt& _n) :
1199 e(_e), spec(_spec), n(_n) {
1201 InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
1202 InEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
1205 if (_G.graph->inTClass(_n)) { //T, van normalis beel
1206 e=typename Graph::InEdgeIt(*(_G.graph),
1207 typename Graph::Node(_n));
1210 if (!_G.graph->valid(e)) spec=3;
1211 } else { //S, specko beel van
1224 _G.graph->first(n, T_CLASS); //vmi->t;
1225 if (!_G.graph->valid(n)) spec=3; //Ha T ures
1229 operator Edge() const { return Edge(e, spec, n); }
1232 friend class GraphWrapper<Graph>;
1233 friend class stGraphWrapper<Graph>;
1234 typename Graph::EdgeIt e;
1236 typename Graph::ClassNodeIt n;
1239 EdgeIt(const typename Graph::EdgeIt& _e, int _spec,
1240 const typename Graph::ClassNodeIt& _n) :
1241 e(_e), spec(_spec), n(_n) { }
1242 EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
1243 EdgeIt(const stGraphWrapper<Graph>& _G) :
1244 e(*(_G.graph)), spec(0), n(INVALID) {
1245 if (!_G.graph->valid(e)) {
1247 _G.graph->first(n, S_CLASS);
1248 if (!_G.graph->valid(n)) { //Ha S ures
1250 _G.graph->first(n, T_CLASS);
1251 if (!_G.graph->valid(n)) { //Ha T ures
1257 operator Edge() const { return Edge(e, spec, n); }
1260 NodeIt& first(NodeIt& i) const {
1261 i=NodeIt(*this); return i;
1263 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
1264 i=OutEdgeIt(*this, p); return i;
1266 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
1267 i=InEdgeIt(*this, p); return i;
1269 EdgeIt& first(EdgeIt& i) const {
1270 i=EdgeIt(*this); return i;
1273 NodeIt& next(NodeIt& i) const {
1277 if (!graph->valid(i.n)) {
1290 OutEdgeIt& next(OutEdgeIt& i) const {
1292 case 0: //normal edge
1293 typename Graph::Node v=graph->aNode(i.e);
1295 if (!graph->valid(i.e)) { //Az igazi elek vegere ertunk
1296 if (graph->inSClass(v)) { //S, nincs kiel
1299 } else { //T, van kiel
1307 if (!graph->valid(i.n)) i.spec=3;
1316 InEdgeIt& next(InEdgeIt& i) const {
1318 case 0: //normal edge
1319 typename Graph::Node v=graph->aNode(i.e);
1321 if (!graph->valid(i.e)) { //Az igazi elek vegere ertunk
1322 if (graph->inTClass(v)) { //S, nincs beel
1325 } else { //S, van beel
1337 if (!graph->valid(i.n)) i.spec=3;
1343 EdgeIt& next(EdgeIt& i) const {
1347 if (!graph->valid(i.e)) {
1349 graph->first(n, S_CLASS);
1350 if (!graph->valid(i.n)) {
1352 graph->first(n, T_CLASS);
1353 if (!graph->valid(i.n)) spec=3;
1359 if (!graph->valid(i.n)) {
1361 graph->first(n, T_CLASS);
1362 if (!graph->valid(i.n)) spec=3;
1367 if (!graph->valid(i.n)) i.spec=3;
1373 Node tail(const Edge& e) const {
1376 return Node(graph->tail(e));
1386 Node head(const Edge& e) const {
1389 return Node(graph->head(e));
1400 bool valid(const Node& n) const { return (n.spec<3); }
1401 bool valid(const Edge& e) const { return (e.spec<3); }
1403 // int nodeNum() const { return graph->nodeNum(); }
1404 // int edgeNum() const { return graph->edgeNum(); }
1406 Node aNode(const OutEdgeIt& e) const { return tail(e); }
1407 Node aNode(const InEdgeIt& e) const { return head(e); }
1408 Node bNode(const OutEdgeIt& e) const { return head(e); }
1409 Node bNode(const InEdgeIt& e) const { return tail(e); }
1411 // Node addNode() const { return Node(graph->addNode()); }
1412 // Edge addEdge(const Node& tail, const Node& head) const {
1413 // return Edge(graph->addEdge(tail, head)); }
1415 // void erase(const Node& i) const { graph->erase(i); }
1416 // void erase(const Edge& i) const { graph->erase(i); }
1418 // void clear() const { graph->clear(); }
1420 template<typename T> class NodeMap : public GraphWrapper<Graph>::NodeMap<T> {
1423 NodeMap(const stGraphWrapper<Graph>& _G) :
1424 GraphWrapper<Graph>::NodeMap<T>(_G) { }
1425 NodeMap(const stGraphWrapper<Graph>& _G, T a) :
1426 GraphWrapper<Graph>::NodeMap<T>(_G, a), s_value(a), t_value(a) { }
1427 T operator[](const Node& n) const {
1440 void set(const Node& n, T t) {
1443 GraphWrapper<Graph>::NodeMap<T>::set(n, t);
1455 template<typename T> class EdgeMap : public GraphWrapper<Graph>::EdgeMap<T> {
1456 typename GraphWrapper<Graph>::NodeMap<T> node_value;
1458 EdgeMap(const stGraphWrapper<Graph>& _G) :
1459 GraphWrapper<Graph>::EdgeMap<T>(_G), node_value(_G) { }
1460 EdgeMap(const stGraphWrapper<Graph>& _G, T a) :
1461 GraphWrapper<Graph>::EdgeMap<T>(_G, a), node_value(_G, a) { }
1462 T operator[](const Edge& e) const {
1468 return node_value[e.n];
1471 return node_value[e.n];
1475 void set(const Edge& e, T t) {
1478 GraphWrapper<Graph>::set(e, t);
1481 node_value.set(e, t);
1484 node_value.set(e, t);
1494 #endif //HUGO_GRAPH_WRAPPER_H