Change the compilation flag at release make distcheck.
(This setting is probably indifferent, though.)
2 * lemon/graph_adaptor.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_GRAPH_ADAPTOR_H
18 #define LEMON_GRAPH_ADAPTOR_H
20 ///\ingroup graph_adaptors
22 ///\brief Several graph adaptors.
24 ///This file contains several useful graph adaptor functions.
26 ///\author Marton Makai
28 #include <lemon/invalid.h>
29 #include <lemon/maps.h>
30 #include <lemon/bits/erasable_graph_extender.h>
31 #include <lemon/bits/clearable_graph_extender.h>
32 #include <lemon/bits/extendable_graph_extender.h>
33 #include <lemon/bits/iterable_graph_extender.h>
34 #include <lemon/bits/alteration_notifier.h>
35 #include <lemon/bits/default_map.h>
36 #include <lemon/bits/graph_extender.h>
41 ///\brief Base type for the Graph Adaptors
42 ///\ingroup graph_adaptors
44 ///Base type for the Graph Adaptors
46 ///\warning Graph adaptors are in even
47 ///more experimental state than the other
48 ///parts of the lib. Use them at you own risk.
50 ///This is the base type for most of LEMON graph adaptors.
51 ///This class implements a trivial graph adaptor i.e. it only wraps the
52 ///functions and types of the graph. The purpose of this class is to
53 ///make easier implementing graph adaptors. E.g. if an adaptor is
54 ///considered which differs from the wrapped graph only in some of its
55 ///functions or types, then it can be derived from GraphAdaptor,
57 ///differences should be implemented.
59 ///author Marton Makai
60 template<typename _Graph>
61 class GraphAdaptorBase {
64 typedef Graph ParentGraph;
68 GraphAdaptorBase() : graph(0) { }
69 void setGraph(Graph& _graph) { graph=&_graph; }
72 GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
74 typedef typename Graph::Node Node;
75 typedef typename Graph::Edge Edge;
77 void first(Node& i) const { graph->first(i); }
78 void first(Edge& i) const { graph->first(i); }
79 void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
80 void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
82 void next(Node& i) const { graph->next(i); }
83 void next(Edge& i) const { graph->next(i); }
84 void nextIn(Edge& i) const { graph->nextIn(i); }
85 void nextOut(Edge& i) const { graph->nextOut(i); }
87 Node source(const Edge& e) const { return graph->source(e); }
88 Node target(const Edge& e) const { return graph->target(e); }
90 typedef NodeNumTagIndicator<Graph> NodeNumTag;
91 int nodeNum() const { return graph->nodeNum(); }
93 typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
94 int edgeNum() const { return graph->edgeNum(); }
96 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
97 Edge findEdge(const Node& source, const Node& target,
98 const Edge& prev = INVALID) {
99 return graph->findEdge(source, target, prev);
102 Node addNode() const {
103 return Node(graph->addNode());
106 Edge addEdge(const Node& source, const Node& target) const {
107 return Edge(graph->addEdge(source, target));
110 void erase(const Node& i) const { graph->erase(i); }
111 void erase(const Edge& i) const { graph->erase(i); }
113 void clear() const { graph->clear(); }
115 int id(const Node& v) const { return graph->id(v); }
116 int id(const Edge& e) const { return graph->id(e); }
118 Edge oppositeNode(const Edge& e) const {
119 return Edge(graph->opposite(e));
122 template <typename _Value>
123 class NodeMap : public _Graph::template NodeMap<_Value> {
125 typedef typename _Graph::template NodeMap<_Value> Parent;
126 explicit NodeMap(const GraphAdaptorBase<_Graph>& gw)
127 : Parent(*gw.graph) { }
128 NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
129 : Parent(*gw.graph, value) { }
132 template <typename _Value>
133 class EdgeMap : public _Graph::template EdgeMap<_Value> {
135 typedef typename _Graph::template EdgeMap<_Value> Parent;
136 explicit EdgeMap(const GraphAdaptorBase<_Graph>& gw)
137 : Parent(*gw.graph) { }
138 EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
139 : Parent(*gw.graph, value) { }
144 template <typename _Graph>
146 public IterableGraphExtender<GraphAdaptorBase<_Graph> > {
148 typedef _Graph Graph;
149 typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
151 GraphAdaptor() : Parent() { }
154 explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); }
157 template <typename _Graph>
158 class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
160 typedef _Graph Graph;
161 typedef GraphAdaptorBase<_Graph> Parent;
163 RevGraphAdaptorBase() : Parent() { }
165 typedef typename Parent::Node Node;
166 typedef typename Parent::Edge Edge;
168 void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
169 void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
171 void nextIn(Edge& i) const { Parent::nextOut(i); }
172 void nextOut(Edge& i) const { Parent::nextIn(i); }
174 Node source(const Edge& e) const { return Parent::target(e); }
175 Node target(const Edge& e) const { return Parent::source(e); }
179 ///\brief A graph adaptor which reverses the orientation of the edges.
180 ///\ingroup graph_adaptors
182 ///\warning Graph adaptors are in even more experimental
183 ///state than the other
184 ///parts of the lib. Use them at you own risk.
186 /// If \c g is defined as
192 /// RevGraphAdaptor<ListGraph> gw(g);
194 ///implements the graph obtained from \c g by
195 /// reversing the orientation of its edges.
197 template<typename _Graph>
198 class RevGraphAdaptor :
199 public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
201 typedef _Graph Graph;
202 typedef IterableGraphExtender<
203 RevGraphAdaptorBase<_Graph> > Parent;
205 RevGraphAdaptor() { }
207 explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
211 template <typename _Graph, typename NodeFilterMap,
212 typename EdgeFilterMap, bool checked = true>
213 class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
215 typedef _Graph Graph;
216 typedef GraphAdaptorBase<_Graph> Parent;
218 NodeFilterMap* node_filter_map;
219 EdgeFilterMap* edge_filter_map;
220 SubGraphAdaptorBase() : Parent(),
221 node_filter_map(0), edge_filter_map(0) { }
223 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
224 node_filter_map=&_node_filter_map;
226 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
227 edge_filter_map=&_edge_filter_map;
232 typedef typename Parent::Node Node;
233 typedef typename Parent::Edge Edge;
235 void first(Node& i) const {
237 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
240 void first(Edge& i) const {
242 while (i!=INVALID && (!(*edge_filter_map)[i]
243 || !(*node_filter_map)[Parent::source(i)]
244 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
247 void firstIn(Edge& i, const Node& n) const {
248 Parent::firstIn(i, n);
249 while (i!=INVALID && (!(*edge_filter_map)[i]
250 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
253 void firstOut(Edge& i, const Node& n) const {
254 Parent::firstOut(i, n);
255 while (i!=INVALID && (!(*edge_filter_map)[i]
256 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
259 void next(Node& i) const {
261 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
264 void next(Edge& i) const {
266 while (i!=INVALID && (!(*edge_filter_map)[i]
267 || !(*node_filter_map)[Parent::source(i)]
268 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
271 void nextIn(Edge& i) const {
273 while (i!=INVALID && (!(*edge_filter_map)[i]
274 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
277 void nextOut(Edge& i) const {
279 while (i!=INVALID && (!(*edge_filter_map)[i]
280 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
285 /// This function hides \c n in the graph, i.e. the iteration
286 /// jumps over it. This is done by simply setting the value of \c n
287 /// to be false in the corresponding node-map.
288 void hide(const Node& n) const { node_filter_map->set(n, false); }
292 /// This function hides \c e in the graph, i.e. the iteration
293 /// jumps over it. This is done by simply setting the value of \c e
294 /// to be false in the corresponding edge-map.
295 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
299 /// The value of \c n is set to be true in the node-map which stores
300 /// hide information. If \c n was hidden previuosly, then it is shown
302 void unHide(const Node& n) const { node_filter_map->set(n, true); }
306 /// The value of \c e is set to be true in the edge-map which stores
307 /// hide information. If \c e was hidden previuosly, then it is shown
309 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
311 /// Returns true if \c n is hidden.
315 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
317 /// Returns true if \c n is hidden.
321 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
323 typedef False NodeNumTag;
324 typedef False EdgeNumTag;
327 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
328 class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
329 : public GraphAdaptorBase<_Graph> {
331 typedef _Graph Graph;
332 typedef GraphAdaptorBase<_Graph> Parent;
334 NodeFilterMap* node_filter_map;
335 EdgeFilterMap* edge_filter_map;
336 SubGraphAdaptorBase() : Parent(),
337 node_filter_map(0), edge_filter_map(0) { }
339 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
340 node_filter_map=&_node_filter_map;
342 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
343 edge_filter_map=&_edge_filter_map;
348 typedef typename Parent::Node Node;
349 typedef typename Parent::Edge Edge;
351 void first(Node& i) const {
353 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
356 void first(Edge& i) const {
358 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
361 void firstIn(Edge& i, const Node& n) const {
362 Parent::firstIn(i, n);
363 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
366 void firstOut(Edge& i, const Node& n) const {
367 Parent::firstOut(i, n);
368 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
371 void next(Node& i) const {
373 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
375 void next(Edge& i) const {
377 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
379 void nextIn(Edge& i) const {
381 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
384 void nextOut(Edge& i) const {
386 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
391 /// This function hides \c n in the graph, i.e. the iteration
392 /// jumps over it. This is done by simply setting the value of \c n
393 /// to be false in the corresponding node-map.
394 void hide(const Node& n) const { node_filter_map->set(n, false); }
398 /// This function hides \c e in the graph, i.e. the iteration
399 /// jumps over it. This is done by simply setting the value of \c e
400 /// to be false in the corresponding edge-map.
401 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
405 /// The value of \c n is set to be true in the node-map which stores
406 /// hide information. If \c n was hidden previuosly, then it is shown
408 void unHide(const Node& n) const { node_filter_map->set(n, true); }
412 /// The value of \c e is set to be true in the edge-map which stores
413 /// hide information. If \c e was hidden previuosly, then it is shown
415 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
417 /// Returns true if \c n is hidden.
421 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
423 /// Returns true if \c n is hidden.
427 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
429 typedef False NodeNumTag;
430 typedef False EdgeNumTag;
433 /// \brief A graph adaptor for hiding nodes and edges from a graph.
434 /// \ingroup graph_adaptors
436 /// \warning Graph adaptors are in even more experimental state than the
437 /// other parts of the lib. Use them at you own risk.
439 /// SubGraphAdaptor shows the graph with filtered node-set and
440 /// edge-set. If the \c checked parameter is true then it filters the edgeset
441 /// to do not get invalid edges without source or target.
442 /// Let \f$ G=(V, A) \f$ be a directed graph
443 /// and suppose that the graph instance \c g of type ListGraph
444 /// implements \f$ G \f$.
445 /// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp.
446 /// on the node-set and edge-set.
447 /// SubGraphAdaptor<...>::NodeIt iterates
448 /// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and
449 /// SubGraphAdaptor<...>::EdgeIt iterates
450 /// on the edge-set \f$ \{e\in A : b_A(e)=true\} \f$. Similarly,
451 /// SubGraphAdaptor<...>::OutEdgeIt and
452 /// SubGraphAdaptor<...>::InEdgeIt iterates
453 /// only on edges leaving and entering a specific node which have true value.
455 /// If the \c checked template parameter is false then we have to note that
456 /// the node-iterator cares only the filter on the node-set, and the
457 /// edge-iterator cares only the filter on the edge-set.
458 /// This way the edge-map
459 /// should filter all edges which's source or target is filtered by the
462 /// typedef ListGraph Graph;
464 /// typedef Graph::Node Node;
465 /// typedef Graph::Edge Edge;
466 /// Node u=g.addNode(); //node of id 0
467 /// Node v=g.addNode(); //node of id 1
468 /// Node e=g.addEdge(u, v); //edge of id 0
469 /// Node f=g.addEdge(v, u); //edge of id 1
470 /// Graph::NodeMap<bool> nm(g, true);
471 /// nm.set(u, false);
472 /// Graph::EdgeMap<bool> em(g, true);
473 /// em.set(e, false);
474 /// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
475 /// SubGW gw(g, nm, em);
476 /// for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
477 /// std::cout << ":-)" << std::endl;
478 /// for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
480 /// The output of the above code is the following.
486 /// Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
487 /// \c Graph::Node that is why \c g.id(n) can be applied.
489 /// For other examples see also the documentation of NodeSubGraphAdaptor and
490 /// EdgeSubGraphAdaptor.
492 /// \author Marton Makai
494 template<typename _Graph, typename NodeFilterMap,
495 typename EdgeFilterMap, bool checked = true>
496 class SubGraphAdaptor :
497 public IterableGraphExtender<
498 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
500 typedef _Graph Graph;
501 typedef IterableGraphExtender<
502 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
504 SubGraphAdaptor() { }
506 SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
507 EdgeFilterMap& _edge_filter_map) {
509 setNodeFilterMap(_node_filter_map);
510 setEdgeFilterMap(_edge_filter_map);
516 ///\brief An adaptor for hiding nodes from a graph.
517 ///\ingroup graph_adaptors
519 ///\warning Graph adaptors are in even more experimental state
521 ///parts of the lib. Use them at you own risk.
523 ///An adaptor for hiding nodes from a graph.
524 ///This adaptor specializes SubGraphAdaptor in the way that only
526 ///can be filtered. In usual case the checked parameter is true, we get the
527 ///induced subgraph. But if the checked parameter is false then we can only
528 ///filter only isolated nodes.
529 ///\author Marton Makai
530 template<typename Graph, typename NodeFilterMap, bool checked = true>
531 class NodeSubGraphAdaptor :
532 public SubGraphAdaptor<Graph, NodeFilterMap,
533 ConstMap<typename Graph::Edge,bool>, checked> {
535 typedef SubGraphAdaptor<Graph, NodeFilterMap,
536 ConstMap<typename Graph::Edge,bool> > Parent;
538 ConstMap<typename Graph::Edge, bool> const_true_map;
540 NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
541 Parent(), const_true_map(true) {
542 Parent::setGraph(_graph);
543 Parent::setNodeFilterMap(_node_filter_map);
544 Parent::setEdgeFilterMap(const_true_map);
549 ///\brief An adaptor for hiding edges from a graph.
551 ///\warning Graph adaptors are in even more experimental state
552 ///than the other parts of the lib. Use them at you own risk.
554 ///An adaptor for hiding edges from a graph.
555 ///This adaptor specializes SubGraphAdaptor in the way that
557 ///can be filtered. The usefulness of this adaptor is demonstrated in the
558 ///problem of searching a maximum number of edge-disjoint shortest paths
560 ///two nodes \c s and \c t. Shortest here means being shortest w.r.t.
561 ///non-negative edge-lengths. Note that
562 ///the comprehension of the presented solution
563 ///need's some elementary knowledge from combinatorial optimization.
565 ///If a single shortest path is to be
566 ///searched between \c s and \c t, then this can be done easily by
567 ///applying the Dijkstra algorithm. What happens, if a maximum number of
568 ///edge-disjoint shortest paths is to be computed. It can be proved that an
569 ///edge can be in a shortest path if and only
570 ///if it is tight with respect to
571 ///the potential function computed by Dijkstra.
572 ///Moreover, any path containing
573 ///only such edges is a shortest one.
574 ///Thus we have to compute a maximum number
575 ///of edge-disjoint paths between \c s and \c t in
576 ///the graph which has edge-set
577 ///all the tight edges. The computation will be demonstrated
579 ///graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
580 ///The full source code is available in \ref sub_graph_adaptor_demo.cc.
581 ///If you are interested in more demo programs, you can use
582 ///\ref dim_to_dot.cc to generate .dot files from dimacs files.
583 ///The .dot file of the following figure was generated by
584 ///the demo program \ref dim_to_dot.cc.
587 ///digraph lemon_dot_example {
588 ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
589 ///n0 [ label="0 (s)" ];
595 ///n6 [ label="6 (t)" ];
596 ///edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
597 ///n5 -> n6 [ label="9, length:4" ];
598 ///n4 -> n6 [ label="8, length:2" ];
599 ///n3 -> n5 [ label="7, length:1" ];
600 ///n2 -> n5 [ label="6, length:3" ];
601 ///n2 -> n6 [ label="5, length:5" ];
602 ///n2 -> n4 [ label="4, length:2" ];
603 ///n1 -> n4 [ label="3, length:3" ];
604 ///n0 -> n3 [ label="2, length:1" ];
605 ///n0 -> n2 [ label="1, length:2" ];
606 ///n0 -> n1 [ label="0, length:3" ];
613 ///LengthMap length(g);
615 ///readDimacs(std::cin, g, length, s, t);
617 ///cout << "edges with lengths (of form id, source--length->target): " << endl;
618 ///for(EdgeIt e(g); e!=INVALID; ++e)
619 /// cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
620 /// << length[e] << "->" << g.id(g.target(e)) << endl;
622 ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
624 ///Next, the potential function is computed with Dijkstra.
626 ///typedef Dijkstra<Graph, LengthMap> Dijkstra;
627 ///Dijkstra dijkstra(g, length);
630 ///Next, we consrtruct a map which filters the edge-set to the tight edges.
632 ///typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
634 ///TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
636 ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
637 ///SubGW gw(g, tight_edge_filter);
639 ///Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
640 ///with a max flow algorithm Preflow.
642 ///ConstMap<Edge, int> const_1_map(1);
643 ///Graph::EdgeMap<int> flow(g, 0);
645 ///Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
646 /// preflow(gw, s, t, const_1_map, flow);
649 ///Last, the output is:
651 ///cout << "maximum number of edge-disjoint shortest path: "
652 /// << preflow.flowValue() << endl;
653 ///cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
655 ///for(EdgeIt e(g); e!=INVALID; ++e)
657 /// cout << " " << g.id(g.source(e)) << "--"
658 /// << length[e] << "->" << g.id(g.target(e)) << endl;
660 ///The program has the following (expected :-)) output:
662 ///edges with lengths (of form id, source--length->target):
674 ///maximum number of edge-disjoint shortest path: 2
675 ///edges of the maximum number of edge-disjoint shortest s-t paths:
684 ///\author Marton Makai
685 template<typename Graph, typename EdgeFilterMap>
686 class EdgeSubGraphAdaptor :
687 public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
688 EdgeFilterMap, false> {
690 typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
691 EdgeFilterMap, false> Parent;
693 ConstMap<typename Graph::Node, bool> const_true_map;
695 EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
696 Parent(), const_true_map(true) {
697 Parent::setGraph(_graph);
698 Parent::setNodeFilterMap(const_true_map);
699 Parent::setEdgeFilterMap(_edge_filter_map);
703 template <typename _Graph>
704 class UGraphAdaptorBase :
705 public UGraphExtender<GraphAdaptorBase<_Graph> > {
707 typedef _Graph Graph;
708 typedef UGraphExtender<GraphAdaptorBase<_Graph> > Parent;
710 UGraphAdaptorBase() : Parent() { }
712 typedef typename Parent::UEdge UEdge;
713 typedef typename Parent::Edge Edge;
715 template <typename T>
718 const UGraphAdaptorBase<_Graph>* g;
719 template <typename TT> friend class EdgeMap;
720 typename _Graph::template EdgeMap<T> forward_map, backward_map;
725 EdgeMap(const UGraphAdaptorBase<_Graph>& _g) : g(&_g),
726 forward_map(*(g->graph)), backward_map(*(g->graph)) { }
728 EdgeMap(const UGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
729 forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
731 void set(Edge e, T a) {
733 forward_map.set(e, a);
735 backward_map.set(e, a);
738 T operator[](Edge e) const {
740 return forward_map[e];
742 return backward_map[e];
746 template <typename T>
748 template <typename TT> friend class UEdgeMap;
749 typename _Graph::template EdgeMap<T> map;
754 UEdgeMap(const UGraphAdaptorBase<_Graph>& g) :
757 UEdgeMap(const UGraphAdaptorBase<_Graph>& g, T a) :
758 map(*(g.graph), a) { }
760 void set(UEdge e, T a) {
764 T operator[](UEdge e) const {
771 ///\brief An undirected graph is made from a directed graph by an adaptor
772 ///\ingroup graph_adaptors
774 /// Undocumented, untested!!!
775 /// If somebody knows nice demo application, let's polulate it.
777 /// \author Marton Makai
778 template<typename _Graph>
779 class UGraphAdaptor :
780 public IterableUGraphExtender<
781 UGraphAdaptorBase<_Graph> > {
783 typedef _Graph Graph;
784 typedef IterableUGraphExtender<
785 UGraphAdaptorBase<_Graph> > Parent;
789 UGraphAdaptor(_Graph& _graph) {
795 template <typename _Graph,
796 typename ForwardFilterMap, typename BackwardFilterMap>
797 class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
799 typedef _Graph Graph;
800 typedef GraphAdaptorBase<_Graph> Parent;
802 ForwardFilterMap* forward_filter;
803 BackwardFilterMap* backward_filter;
804 SubBidirGraphAdaptorBase() : Parent(),
805 forward_filter(0), backward_filter(0) { }
807 void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
808 forward_filter=&_forward_filter;
810 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
811 backward_filter=&_backward_filter;
815 // SubGraphAdaptorBase(Graph& _graph,
816 // NodeFilterMap& _node_filter_map,
817 // EdgeFilterMap& _edge_filter_map) :
819 // node_filter_map(&node_filter_map),
820 // edge_filter_map(&edge_filter_map) { }
822 typedef typename Parent::Node Node;
823 typedef typename _Graph::Edge GraphEdge;
824 template <typename T> class EdgeMap;
825 // SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
826 // _Graph::Edge. It contains an extra bool flag which is true
827 // if and only if the
828 // edge is the backward version of the original edge.
829 class Edge : public _Graph::Edge {
830 friend class SubBidirGraphAdaptorBase<
831 Graph, ForwardFilterMap, BackwardFilterMap>;
832 template<typename T> friend class EdgeMap;
834 bool backward; //true, iff backward
837 // \todo =false is needed, or causes problems?
838 // If \c _backward is false, then we get an edge corresponding to the
839 // original one, otherwise its oppositely directed pair is obtained.
840 Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
841 _Graph::Edge(e), backward(_backward) { }
842 Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
843 bool operator==(const Edge& v) const {
844 return (this->backward==v.backward &&
845 static_cast<typename _Graph::Edge>(*this)==
846 static_cast<typename _Graph::Edge>(v));
848 bool operator!=(const Edge& v) const {
849 return (this->backward!=v.backward ||
850 static_cast<typename _Graph::Edge>(*this)!=
851 static_cast<typename _Graph::Edge>(v));
855 void first(Node& i) const {
859 void first(Edge& i) const {
862 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
863 !(*forward_filter)[i]) Parent::next(i);
864 if (*static_cast<GraphEdge*>(&i)==INVALID) {
867 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
868 !(*backward_filter)[i]) Parent::next(i);
872 void firstIn(Edge& i, const Node& n) const {
873 Parent::firstIn(i, n);
875 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
876 !(*forward_filter)[i]) Parent::nextIn(i);
877 if (*static_cast<GraphEdge*>(&i)==INVALID) {
878 Parent::firstOut(i, n);
880 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
881 !(*backward_filter)[i]) Parent::nextOut(i);
885 void firstOut(Edge& i, const Node& n) const {
886 Parent::firstOut(i, n);
888 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
889 !(*forward_filter)[i]) Parent::nextOut(i);
890 if (*static_cast<GraphEdge*>(&i)==INVALID) {
891 Parent::firstIn(i, n);
893 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
894 !(*backward_filter)[i]) Parent::nextIn(i);
898 void next(Node& i) const {
902 void next(Edge& i) const {
905 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
906 !(*forward_filter)[i]) Parent::next(i);
907 if (*static_cast<GraphEdge*>(&i)==INVALID) {
910 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
911 !(*backward_filter)[i]) Parent::next(i);
915 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
916 !(*backward_filter)[i]) Parent::next(i);
920 void nextIn(Edge& i) const {
922 Node n=Parent::target(i);
924 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
925 !(*forward_filter)[i]) Parent::nextIn(i);
926 if (*static_cast<GraphEdge*>(&i)==INVALID) {
927 Parent::firstOut(i, n);
929 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
930 !(*backward_filter)[i]) Parent::nextOut(i);
934 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
935 !(*backward_filter)[i]) Parent::nextOut(i);
939 void nextOut(Edge& i) const {
941 Node n=Parent::source(i);
943 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
944 !(*forward_filter)[i]) Parent::nextOut(i);
945 if (*static_cast<GraphEdge*>(&i)==INVALID) {
946 Parent::firstIn(i, n);
948 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
949 !(*backward_filter)[i]) Parent::nextIn(i);
953 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
954 !(*backward_filter)[i]) Parent::nextIn(i);
958 Node source(Edge e) const {
959 return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
960 Node target(Edge e) const {
961 return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
963 /// Gives back the opposite edge.
967 Edge opposite(const Edge& e) const {
969 f.backward=!f.backward;
975 /// \warning This is a linear time operation and works only if
976 /// \c Graph::EdgeIt is defined.
978 int edgeNum() const {
981 for (first(e); e!=INVALID; next(e)) ++i;
985 bool forward(const Edge& e) const { return !e.backward; }
986 bool backward(const Edge& e) const { return e.backward; }
990 /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
991 /// _Graph::EdgeMap one for the forward edges and
992 /// one for the backward edges.
993 template <typename T>
995 template <typename TT> friend class EdgeMap;
996 typename _Graph::template EdgeMap<T> forward_map, backward_map;
1001 EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
1002 ForwardFilterMap, BackwardFilterMap>& g) :
1003 forward_map(*(g.graph)), backward_map(*(g.graph)) { }
1005 EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
1006 ForwardFilterMap, BackwardFilterMap>& g, T a) :
1007 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
1009 void set(Edge e, T a) {
1011 forward_map.set(e, a);
1013 backward_map.set(e, a);
1016 // typename _Graph::template EdgeMap<T>::ConstReference
1017 // operator[](Edge e) const {
1019 // return forward_map[e];
1021 // return backward_map[e];
1024 // typename _Graph::template EdgeMap<T>::Reference
1025 T operator[](Edge e) const {
1027 return forward_map[e];
1029 return backward_map[e];
1033 forward_map.update();
1034 backward_map.update();
1041 ///\brief An adaptor for composing a subgraph of a
1042 /// bidirected graph made from a directed one.
1043 ///\ingroup graph_adaptors
1045 /// An adaptor for composing a subgraph of a
1046 /// bidirected graph made from a directed one.
1048 ///\warning Graph adaptors are in even more experimental state
1050 ///parts of the lib. Use them at you own risk.
1052 /// Let \f$ G=(V, A) \f$ be a directed graph and for each directed edge
1053 ///\f$ e\in A \f$, let \f$ \bar e \f$ denote the edge obtained by
1054 /// reversing its orientation. We are given moreover two bool valued
1055 /// maps on the edge-set,
1056 ///\f$ forward\_filter \f$, and \f$ backward\_filter \f$.
1057 /// SubBidirGraphAdaptor implements the graph structure with node-set
1058 ///\f$ V \f$ and edge-set
1059 ///\f$ \{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\} \f$.
1060 /// The purpose of writing + instead of union is because parallel
1061 /// edges can arise. (Similarly, antiparallel edges also can arise).
1062 /// In other words, a subgraph of the bidirected graph obtained, which
1063 /// is given by orienting the edges of the original graph in both directions.
1064 /// As the oppositely directed edges are logically different,
1065 /// the maps are able to attach different values for them.
1067 /// An example for such a construction is \c RevGraphAdaptor where the
1068 /// forward_filter is everywhere false and the backward_filter is
1069 /// everywhere true. We note that for sake of efficiency,
1070 /// \c RevGraphAdaptor is implemented in a different way.
1071 /// But BidirGraphAdaptor is obtained from
1072 /// SubBidirGraphAdaptor by considering everywhere true
1073 /// valued maps both for forward_filter and backward_filter.
1075 /// The most important application of SubBidirGraphAdaptor
1076 /// is ResGraphAdaptor, which stands for the residual graph in directed
1077 /// flow and circulation problems.
1078 /// As adaptors usually, the SubBidirGraphAdaptor implements the
1079 /// above mentioned graph structure without its physical storage,
1080 /// that is the whole stuff is stored in constant memory.
1081 template<typename _Graph,
1082 typename ForwardFilterMap, typename BackwardFilterMap>
1083 class SubBidirGraphAdaptor :
1084 public IterableGraphExtender<
1085 SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
1087 typedef _Graph Graph;
1088 typedef IterableGraphExtender<
1089 SubBidirGraphAdaptorBase<
1090 _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
1092 SubBidirGraphAdaptor() { }
1094 SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,
1095 BackwardFilterMap& _backward_filter) {
1097 setForwardFilterMap(_forward_filter);
1098 setBackwardFilterMap(_backward_filter);
1104 ///\brief An adaptor for composing bidirected graph from a directed one.
1105 ///\ingroup graph_adaptors
1107 ///\warning Graph adaptors are in even more experimental state
1109 ///parts of the lib. Use them at you own risk.
1111 /// An adaptor for composing bidirected graph from a directed one.
1112 /// A bidirected graph is composed over the directed one without physical
1113 /// storage. As the oppositely directed edges are logically different ones
1114 /// the maps are able to attach different values for them.
1115 template<typename Graph>
1116 class BidirGraphAdaptor :
1117 public SubBidirGraphAdaptor<
1119 ConstMap<typename Graph::Edge, bool>,
1120 ConstMap<typename Graph::Edge, bool> > {
1122 typedef SubBidirGraphAdaptor<
1124 ConstMap<typename Graph::Edge, bool>,
1125 ConstMap<typename Graph::Edge, bool> > Parent;
1127 ConstMap<typename Graph::Edge, bool> cm;
1129 BidirGraphAdaptor() : Parent(), cm(true) {
1130 Parent::setForwardFilterMap(cm);
1131 Parent::setBackwardFilterMap(cm);
1134 BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {
1135 Parent::setGraph(_graph);
1136 Parent::setForwardFilterMap(cm);
1137 Parent::setBackwardFilterMap(cm);
1140 int edgeNum() const {
1141 return 2*this->graph->edgeNum();
1146 template<typename Graph, typename Number,
1147 typename CapacityMap, typename FlowMap>
1148 class ResForwardFilter {
1149 // const Graph* graph;
1150 const CapacityMap* capacity;
1151 const FlowMap* flow;
1153 ResForwardFilter(/*const Graph& _graph, */
1154 const CapacityMap& _capacity, const FlowMap& _flow) :
1155 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1156 ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1157 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1158 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1159 bool operator[](const typename Graph::Edge& e) const {
1160 return (Number((*flow)[e]) < Number((*capacity)[e]));
1164 template<typename Graph, typename Number,
1165 typename CapacityMap, typename FlowMap>
1166 class ResBackwardFilter {
1167 const CapacityMap* capacity;
1168 const FlowMap* flow;
1170 ResBackwardFilter(/*const Graph& _graph,*/
1171 const CapacityMap& _capacity, const FlowMap& _flow) :
1172 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1173 ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1174 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1175 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1176 bool operator[](const typename Graph::Edge& e) const {
1177 return (Number(0) < Number((*flow)[e]));
1182 ///\brief An adaptor for composing the residual
1183 ///graph for directed flow and circulation problems.
1184 ///\ingroup graph_adaptors
1186 ///An adaptor for composing the residual graph for
1187 ///directed flow and circulation problems.
1188 ///Let \f$ G=(V, A) \f$ be a directed graph and let \f$ F \f$ be a
1189 ///number type. Let moreover
1190 ///\f$ f,c:A\to F \f$, be functions on the edge-set.
1191 ///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands for a flow
1192 ///and \f$ c \f$ for a capacity function.
1193 ///Suppose that a graph instange \c g of type
1194 ///\c ListGraph implements \f$ G \f$.
1198 ///Then RevGraphAdaptor implements the graph structure with node-set
1199 ///\f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$, where
1200 ///\f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
1201 ///\f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$,
1202 ///i.e. the so called residual graph.
1203 ///When we take the union \f$ A_{forward}\cup A_{backward} \f$,
1204 ///multilicities are counted, i.e. if an edge is in both
1205 ///\f$ A_{forward} \f$ and \f$ A_{backward} \f$, then in the adaptor it
1207 ///The following code shows how
1208 ///such an instance can be constructed.
1210 ///typedef ListGraph Graph;
1211 ///Graph::EdgeMap<int> f(g);
1212 ///Graph::EdgeMap<int> c(g);
1213 ///ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
1215 ///\author Marton Makai
1217 template<typename Graph, typename Number,
1218 typename CapacityMap, typename FlowMap>
1219 class ResGraphAdaptor :
1220 public SubBidirGraphAdaptor<
1222 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1223 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1225 typedef SubBidirGraphAdaptor<
1227 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1228 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1230 const CapacityMap* capacity;
1232 ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1233 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1234 ResGraphAdaptor() : Parent(),
1235 capacity(0), flow(0) { }
1236 void setCapacityMap(const CapacityMap& _capacity) {
1237 capacity=&_capacity;
1238 forward_filter.setCapacity(_capacity);
1239 backward_filter.setCapacity(_capacity);
1241 void setFlowMap(FlowMap& _flow) {
1243 forward_filter.setFlow(_flow);
1244 backward_filter.setFlow(_flow);
1247 ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
1249 Parent(), capacity(&_capacity), flow(&_flow),
1250 forward_filter(/*_graph,*/ _capacity, _flow),
1251 backward_filter(/*_graph,*/ _capacity, _flow) {
1252 Parent::setGraph(_graph);
1253 Parent::setForwardFilterMap(forward_filter);
1254 Parent::setBackwardFilterMap(backward_filter);
1257 typedef typename Parent::Edge Edge;
1259 void augment(const Edge& e, Number a) const {
1260 if (Parent::forward(e))
1261 flow->set(e, (*flow)[e]+a);
1263 flow->set(e, (*flow)[e]-a);
1266 /// \brief Residual capacity map.
1268 /// In generic residual graphs the residual capacity can be obtained
1272 const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
1274 typedef Number Value;
1276 ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&
1277 _res_graph) : res_graph(&_res_graph) { }
1278 Number operator[](const Edge& e) const {
1279 if (res_graph->forward(e))
1280 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1282 return (*(res_graph->flow))[e];
1286 // KEEP_MAPS(Parent, ResGraphAdaptor);
1291 template <typename _Graph, typename FirstOutEdgesMap>
1292 class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1294 typedef _Graph Graph;
1295 typedef GraphAdaptorBase<_Graph> Parent;
1297 FirstOutEdgesMap* first_out_edges;
1298 ErasingFirstGraphAdaptorBase() : Parent(),
1299 first_out_edges(0) { }
1301 void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1302 first_out_edges=&_first_out_edges;
1307 typedef typename Parent::Node Node;
1308 typedef typename Parent::Edge Edge;
1310 void firstOut(Edge& i, const Node& n) const {
1311 i=(*first_out_edges)[n];
1314 void erase(const Edge& e) const {
1318 first_out_edges->set(n, f);
1323 ///\brief For blocking flows.
1324 ///\ingroup graph_adaptors
1326 ///\warning Graph adaptors are in even more
1327 ///experimental state than the other
1328 ///parts of the lib. Use them at you own risk.
1330 ///This graph adaptor is used for on-the-fly
1331 ///Dinits blocking flow computations.
1332 ///For each node, an out-edge is stored which is used when the
1334 ///OutEdgeIt& first(OutEdgeIt&, const Node&)
1338 ///\author Marton Makai
1340 template <typename _Graph, typename FirstOutEdgesMap>
1341 class ErasingFirstGraphAdaptor :
1342 public IterableGraphExtender<
1343 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
1345 typedef _Graph Graph;
1346 typedef IterableGraphExtender<
1347 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1348 ErasingFirstGraphAdaptor(Graph& _graph,
1349 FirstOutEdgesMap& _first_out_edges) {
1351 setFirstOutEdgesMap(_first_out_edges);
1356 template <typename _Graph>
1357 class SplitGraphAdaptorBase
1358 : public GraphAdaptorBase<_Graph> {
1360 typedef GraphAdaptorBase<_Graph> Parent;
1364 template <typename T> class NodeMap;
1365 template <typename T> class EdgeMap;
1368 class Node : public Parent::Node {
1369 friend class SplitGraphAdaptorBase;
1370 template <typename T> friend class NodeMap;
1371 typedef typename Parent::Node NodeParent;
1375 Node(typename Parent::Node _node, bool _entry)
1376 : Parent::Node(_node), entry(_entry) {}
1380 Node(Invalid) : NodeParent(INVALID), entry(true) {}
1382 bool operator==(const Node& node) const {
1383 return NodeParent::operator==(node) && entry == node.entry;
1386 bool operator!=(const Node& node) const {
1387 return !(*this == node);
1390 bool operator<(const Node& node) const {
1391 return NodeParent::operator<(node) ||
1392 (NodeParent::operator==(node) && entry < node.entry);
1396 /// \todo May we want VARIANT/union type
1397 class Edge : public Parent::Edge {
1398 friend class SplitGraphAdaptorBase;
1399 template <typename T> friend class EdgeMap;
1401 typedef typename Parent::Edge EdgeParent;
1402 typedef typename Parent::Node NodeParent;
1405 Edge(const EdgeParent& edge, const NodeParent& node)
1406 : EdgeParent(edge), bind(node) {}
1409 Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {}
1411 bool operator==(const Edge& edge) const {
1412 return EdgeParent::operator==(edge) && bind == edge.bind;
1415 bool operator!=(const Edge& edge) const {
1416 return !(*this == edge);
1419 bool operator<(const Edge& edge) const {
1420 return EdgeParent::operator<(edge) ||
1421 (EdgeParent::operator==(edge) && bind < edge.bind);
1425 void first(Node& node) const {
1426 Parent::first(node);
1430 void next(Node& node) const {
1439 void first(Edge& edge) const {
1440 Parent::first(edge);
1441 if ((typename Parent::Edge&)edge == INVALID) {
1442 Parent::first(edge.bind);
1444 edge.bind = INVALID;
1448 void next(Edge& edge) const {
1449 if ((typename Parent::Edge&)edge != INVALID) {
1451 if ((typename Parent::Edge&)edge == INVALID) {
1452 Parent::first(edge.bind);
1455 Parent::next(edge.bind);
1459 void firstIn(Edge& edge, const Node& node) const {
1461 Parent::firstIn(edge, node);
1462 edge.bind = INVALID;
1464 (typename Parent::Edge&)edge = INVALID;
1469 void nextIn(Edge& edge) const {
1470 if ((typename Parent::Edge&)edge != INVALID) {
1471 Parent::nextIn(edge);
1473 edge.bind = INVALID;
1477 void firstOut(Edge& edge, const Node& node) const {
1479 Parent::firstOut(edge, node);
1480 edge.bind = INVALID;
1482 (typename Parent::Edge&)edge = INVALID;
1487 void nextOut(Edge& edge) const {
1488 if ((typename Parent::Edge&)edge != INVALID) {
1489 Parent::nextOut(edge);
1491 edge.bind = INVALID;
1495 Node source(const Edge& edge) const {
1496 if ((typename Parent::Edge&)edge != INVALID) {
1497 return Node(Parent::source(edge), false);
1499 return Node(edge.bind, true);
1503 Node target(const Edge& edge) const {
1504 if ((typename Parent::Edge&)edge != INVALID) {
1505 return Node(Parent::target(edge), true);
1507 return Node(edge.bind, false);
1511 static bool entryNode(const Node& node) {
1515 static bool exitNode(const Node& node) {
1519 static Node getEntry(const typename Parent::Node& node) {
1520 return Node(node, true);
1523 static Node getExit(const typename Parent::Node& node) {
1524 return Node(node, false);
1527 static bool originalEdge(const Edge& edge) {
1528 return (typename Parent::Edge&)edge != INVALID;
1531 static bool bindingEdge(const Edge& edge) {
1532 return edge.bind != INVALID;
1535 static Node getBindedNode(const Edge& edge) {
1539 int nodeNum() const {
1540 return Parent::nodeNum() * 2;
1543 typedef CompileTimeAnd<typename Parent::NodeNumTag,
1544 typename Parent::EdgeNumTag> EdgeNumTag;
1546 int edgeNum() const {
1547 return Parent::edgeNum() + Parent::nodeNum();
1550 Edge findEdge(const Node& source, const Node& target,
1551 const Edge& prev = INVALID) const {
1552 if (exitNode(source) && entryNode(target)) {
1553 return Parent::findEdge(source, target, prev);
1555 if (prev == INVALID && entryNode(source) && exitNode(target) &&
1556 (typename Parent::Node&)source == (typename Parent::Node&)target) {
1557 return Edge(INVALID, source);
1564 template <typename T>
1565 class NodeMap : public MapBase<Node, T> {
1566 typedef typename Parent::template NodeMap<T> NodeImpl;
1568 NodeMap(const SplitGraphAdaptorBase& _graph)
1569 : entry(_graph), exit(_graph) {}
1570 NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1571 : entry(_graph, t), exit(_graph, t) {}
1573 void set(const Node& key, const T& val) {
1574 if (key.entry) { entry.set(key, val); }
1575 else {exit.set(key, val); }
1578 typename MapTraits<NodeImpl>::ReturnValue
1579 operator[](const Node& key) {
1580 if (key.entry) { return entry[key]; }
1581 else { return exit[key]; }
1584 typename MapTraits<NodeImpl>::ConstReturnValue
1585 operator[](const Node& key) const {
1586 if (key.entry) { return entry[key]; }
1587 else { return exit[key]; }
1591 NodeImpl entry, exit;
1594 template <typename T>
1595 class EdgeMap : public MapBase<Edge, T> {
1596 typedef typename Parent::template NodeMap<T> NodeImpl;
1597 typedef typename Parent::template EdgeMap<T> EdgeImpl;
1599 EdgeMap(const SplitGraphAdaptorBase& _graph)
1600 : bind(_graph), orig(_graph) {}
1601 EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1602 : bind(_graph, t), orig(_graph, t) {}
1604 void set(const Edge& key, const T& val) {
1605 if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); }
1606 else {bind.set(key.bind, val); }
1609 typename MapTraits<EdgeImpl>::ReturnValue
1610 operator[](const Edge& key) {
1611 if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
1612 else {return bind[key.bind]; }
1615 typename MapTraits<EdgeImpl>::ConstReturnValue
1616 operator[](const Edge& key) const {
1617 if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
1618 else {return bind[key.bind]; }
1622 typename Parent::template NodeMap<T> bind;
1623 typename Parent::template EdgeMap<T> orig;
1626 template <typename EntryMap, typename ExitMap>
1627 class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> {
1629 typedef MapBase<Node, typename EntryMap::Value> Parent;
1631 typedef typename Parent::Key Key;
1632 typedef typename Parent::Value Value;
1634 CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap)
1635 : entryMap(_entryMap), exitMap(_exitMap) {}
1637 Value& operator[](const Key& key) {
1639 return entryMap[key];
1641 return exitMap[key];
1645 Value operator[](const Key& key) const {
1647 return entryMap[key];
1649 return exitMap[key];
1653 void set(const Key& key, const Value& value) {
1655 entryMap.set(key, value);
1657 exitMap.set(key, value);
1668 template <typename EdgeMap, typename NodeMap>
1669 class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> {
1671 typedef MapBase<Edge, typename EdgeMap::Value> Parent;
1673 typedef typename Parent::Key Key;
1674 typedef typename Parent::Value Value;
1676 CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap)
1677 : edgeMap(_edgeMap), nodeMap(_nodeMap) {}
1679 void set(const Edge& edge, const Value& val) {
1680 if (SplitGraphAdaptorBase::originalEdge(edge)) {
1681 edgeMap.set(edge, val);
1683 nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val);
1687 Value operator[](const Key& edge) const {
1688 if (SplitGraphAdaptorBase::originalEdge(edge)) {
1689 return edgeMap[edge];
1691 return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
1695 Value& operator[](const Key& edge) {
1696 if (SplitGraphAdaptorBase::originalEdge(edge)) {
1697 return edgeMap[edge];
1699 return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
1710 template <typename _Graph>
1711 class SplitGraphAdaptor
1712 : public IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > {
1714 typedef IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > Parent;
1716 SplitGraphAdaptor(_Graph& graph) {
1717 Parent::setGraph(graph);
1725 #endif //LEMON_GRAPH_ADAPTOR_H