00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_GRAPH_ADAPTOR_H
00020 #define LEMON_GRAPH_ADAPTOR_H
00021
00029
00030 #include <lemon/invalid.h>
00031 #include <lemon/maps.h>
00032 #include <lemon/bits/erasable_graph_extender.h>
00033 #include <lemon/bits/clearable_graph_extender.h>
00034 #include <lemon/bits/extendable_graph_extender.h>
00035 #include <lemon/bits/iterable_graph_extender.h>
00036 #include <lemon/bits/alteration_notifier.h>
00037 #include <lemon/bits/default_map.h>
00038 #include <lemon/bits/graph_extender.h>
00039 #include <iostream>
00040
00041 namespace lemon {
00042
00062 template<typename _Graph>
00063 class GraphAdaptorBase {
00064 public:
00065 typedef _Graph Graph;
00066 typedef Graph ParentGraph;
00067
00068 protected:
00069 Graph* graph;
00070 GraphAdaptorBase() : graph(0) { }
00071 void setGraph(Graph& _graph) { graph=&_graph; }
00072
00073 public:
00074 GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
00075
00076 typedef typename Graph::Node Node;
00077 typedef typename Graph::Edge Edge;
00078
00079 void first(Node& i) const { graph->first(i); }
00080 void first(Edge& i) const { graph->first(i); }
00081 void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
00082 void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
00083
00084 void next(Node& i) const { graph->next(i); }
00085 void next(Edge& i) const { graph->next(i); }
00086 void nextIn(Edge& i) const { graph->nextIn(i); }
00087 void nextOut(Edge& i) const { graph->nextOut(i); }
00088
00089 Node source(const Edge& e) const { return graph->source(e); }
00090 Node target(const Edge& e) const { return graph->target(e); }
00091
00092 typedef NodeNumTagIndicator<Graph> NodeNumTag;
00093 int nodeNum() const { return graph->nodeNum(); }
00094
00095 typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
00096 int edgeNum() const { return graph->edgeNum(); }
00097
00098 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
00099 Edge findEdge(const Node& source, const Node& target,
00100 const Edge& prev = INVALID) {
00101 return graph->findEdge(source, target, prev);
00102 }
00103
00104 Node addNode() const {
00105 return Node(graph->addNode());
00106 }
00107
00108 Edge addEdge(const Node& source, const Node& target) const {
00109 return Edge(graph->addEdge(source, target));
00110 }
00111
00112 void erase(const Node& i) const { graph->erase(i); }
00113 void erase(const Edge& i) const { graph->erase(i); }
00114
00115 void clear() const { graph->clear(); }
00116
00117 int id(const Node& v) const { return graph->id(v); }
00118 int id(const Edge& e) const { return graph->id(e); }
00119
00120 Edge oppositeNode(const Edge& e) const {
00121 return Edge(graph->opposite(e));
00122 }
00123
00124 template <typename _Value>
00125 class NodeMap : public _Graph::template NodeMap<_Value> {
00126 public:
00127 typedef typename _Graph::template NodeMap<_Value> Parent;
00128 explicit NodeMap(const GraphAdaptorBase<_Graph>& gw)
00129 : Parent(*gw.graph) { }
00130 NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
00131 : Parent(*gw.graph, value) { }
00132 };
00133
00134 template <typename _Value>
00135 class EdgeMap : public _Graph::template EdgeMap<_Value> {
00136 public:
00137 typedef typename _Graph::template EdgeMap<_Value> Parent;
00138 explicit EdgeMap(const GraphAdaptorBase<_Graph>& gw)
00139 : Parent(*gw.graph) { }
00140 EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
00141 : Parent(*gw.graph, value) { }
00142 };
00143
00144 };
00145
00146 template <typename _Graph>
00147 class GraphAdaptor :
00148 public IterableGraphExtender<GraphAdaptorBase<_Graph> > {
00149 public:
00150 typedef _Graph Graph;
00151 typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
00152 protected:
00153 GraphAdaptor() : Parent() { }
00154
00155 public:
00156 explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); }
00157 };
00158
00159 template <typename _Graph>
00160 class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
00161 public:
00162 typedef _Graph Graph;
00163 typedef GraphAdaptorBase<_Graph> Parent;
00164 protected:
00165 RevGraphAdaptorBase() : Parent() { }
00166 public:
00167 typedef typename Parent::Node Node;
00168 typedef typename Parent::Edge Edge;
00169
00170 void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
00171 void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
00172
00173 void nextIn(Edge& i) const { Parent::nextOut(i); }
00174 void nextOut(Edge& i) const { Parent::nextIn(i); }
00175
00176 Node source(const Edge& e) const { return Parent::target(e); }
00177 Node target(const Edge& e) const { return Parent::source(e); }
00178 };
00179
00180
00198
00199 template<typename _Graph>
00200 class RevGraphAdaptor :
00201 public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
00202 public:
00203 typedef _Graph Graph;
00204 typedef IterableGraphExtender<
00205 RevGraphAdaptorBase<_Graph> > Parent;
00206 protected:
00207 RevGraphAdaptor() { }
00208 public:
00209 explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
00210 };
00211
00212
00213 template <typename _Graph, typename NodeFilterMap,
00214 typename EdgeFilterMap, bool checked = true>
00215 class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
00216 public:
00217 typedef _Graph Graph;
00218 typedef GraphAdaptorBase<_Graph> Parent;
00219 protected:
00220 NodeFilterMap* node_filter_map;
00221 EdgeFilterMap* edge_filter_map;
00222 SubGraphAdaptorBase() : Parent(),
00223 node_filter_map(0), edge_filter_map(0) { }
00224
00225 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
00226 node_filter_map=&_node_filter_map;
00227 }
00228 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
00229 edge_filter_map=&_edge_filter_map;
00230 }
00231
00232 public:
00233
00234 typedef typename Parent::Node Node;
00235 typedef typename Parent::Edge Edge;
00236
00237 void first(Node& i) const {
00238 Parent::first(i);
00239 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
00240 }
00241
00242 void first(Edge& i) const {
00243 Parent::first(i);
00244 while (i!=INVALID && (!(*edge_filter_map)[i]
00245 || !(*node_filter_map)[Parent::source(i)]
00246 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
00247 }
00248
00249 void firstIn(Edge& i, const Node& n) const {
00250 Parent::firstIn(i, n);
00251 while (i!=INVALID && (!(*edge_filter_map)[i]
00252 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
00253 }
00254
00255 void firstOut(Edge& i, const Node& n) const {
00256 Parent::firstOut(i, n);
00257 while (i!=INVALID && (!(*edge_filter_map)[i]
00258 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
00259 }
00260
00261 void next(Node& i) const {
00262 Parent::next(i);
00263 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
00264 }
00265
00266 void next(Edge& i) const {
00267 Parent::next(i);
00268 while (i!=INVALID && (!(*edge_filter_map)[i]
00269 || !(*node_filter_map)[Parent::source(i)]
00270 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
00271 }
00272
00273 void nextIn(Edge& i) const {
00274 Parent::nextIn(i);
00275 while (i!=INVALID && (!(*edge_filter_map)[i]
00276 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
00277 }
00278
00279 void nextOut(Edge& i) const {
00280 Parent::nextOut(i);
00281 while (i!=INVALID && (!(*edge_filter_map)[i]
00282 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
00283 }
00284
00286
00290 void hide(const Node& n) const { node_filter_map->set(n, false); }
00291
00293
00297 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
00298
00300
00304 void unHide(const Node& n) const { node_filter_map->set(n, true); }
00305
00307
00311 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
00312
00314
00317 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
00318
00320
00323 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
00324
00325 typedef False NodeNumTag;
00326 typedef False EdgeNumTag;
00327 };
00328
00329 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
00330 class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
00331 : public GraphAdaptorBase<_Graph> {
00332 public:
00333 typedef _Graph Graph;
00334 typedef GraphAdaptorBase<_Graph> Parent;
00335 protected:
00336 NodeFilterMap* node_filter_map;
00337 EdgeFilterMap* edge_filter_map;
00338 SubGraphAdaptorBase() : Parent(),
00339 node_filter_map(0), edge_filter_map(0) { }
00340
00341 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
00342 node_filter_map=&_node_filter_map;
00343 }
00344 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
00345 edge_filter_map=&_edge_filter_map;
00346 }
00347
00348 public:
00349
00350 typedef typename Parent::Node Node;
00351 typedef typename Parent::Edge Edge;
00352
00353 void first(Node& i) const {
00354 Parent::first(i);
00355 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
00356 }
00357
00358 void first(Edge& i) const {
00359 Parent::first(i);
00360 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
00361 }
00362
00363 void firstIn(Edge& i, const Node& n) const {
00364 Parent::firstIn(i, n);
00365 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
00366 }
00367
00368 void firstOut(Edge& i, const Node& n) const {
00369 Parent::firstOut(i, n);
00370 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
00371 }
00372
00373 void next(Node& i) const {
00374 Parent::next(i);
00375 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
00376 }
00377 void next(Edge& i) const {
00378 Parent::next(i);
00379 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
00380 }
00381 void nextIn(Edge& i) const {
00382 Parent::nextIn(i);
00383 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
00384 }
00385
00386 void nextOut(Edge& i) const {
00387 Parent::nextOut(i);
00388 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
00389 }
00390
00392
00396 void hide(const Node& n) const { node_filter_map->set(n, false); }
00397
00399
00403 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
00404
00406
00410 void unHide(const Node& n) const { node_filter_map->set(n, true); }
00411
00413
00417 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
00418
00420
00423 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
00424
00426
00429 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
00430
00431 typedef False NodeNumTag;
00432 typedef False EdgeNumTag;
00433 };
00434
00495
00496 template<typename _Graph, typename NodeFilterMap,
00497 typename EdgeFilterMap, bool checked = true>
00498 class SubGraphAdaptor :
00499 public IterableGraphExtender<
00500 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
00501 public:
00502 typedef _Graph Graph;
00503 typedef IterableGraphExtender<
00504 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
00505 protected:
00506 SubGraphAdaptor() { }
00507 public:
00508 SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
00509 EdgeFilterMap& _edge_filter_map) {
00510 setGraph(_graph);
00511 setNodeFilterMap(_node_filter_map);
00512 setEdgeFilterMap(_edge_filter_map);
00513 }
00514 };
00515
00516
00517
00532 template<typename Graph, typename NodeFilterMap, bool checked = true>
00533 class NodeSubGraphAdaptor :
00534 public SubGraphAdaptor<Graph, NodeFilterMap,
00535 ConstMap<typename Graph::Edge,bool>, checked> {
00536 public:
00537 typedef SubGraphAdaptor<Graph, NodeFilterMap,
00538 ConstMap<typename Graph::Edge,bool> > Parent;
00539 protected:
00540 ConstMap<typename Graph::Edge, bool> const_true_map;
00541 public:
00542 NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
00543 Parent(), const_true_map(true) {
00544 Parent::setGraph(_graph);
00545 Parent::setNodeFilterMap(_node_filter_map);
00546 Parent::setEdgeFilterMap(const_true_map);
00547 }
00548 };
00549
00550
00687 template<typename Graph, typename EdgeFilterMap>
00688 class EdgeSubGraphAdaptor :
00689 public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
00690 EdgeFilterMap, false> {
00691 public:
00692 typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
00693 EdgeFilterMap, false> Parent;
00694 protected:
00695 ConstMap<typename Graph::Node, bool> const_true_map;
00696 public:
00697 EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
00698 Parent(), const_true_map(true) {
00699 Parent::setGraph(_graph);
00700 Parent::setNodeFilterMap(const_true_map);
00701 Parent::setEdgeFilterMap(_edge_filter_map);
00702 }
00703 };
00704
00705 template <typename _Graph>
00706 class UGraphAdaptorBase :
00707 public UGraphExtender<GraphAdaptorBase<_Graph> > {
00708 public:
00709 typedef _Graph Graph;
00710 typedef UGraphExtender<GraphAdaptorBase<_Graph> > Parent;
00711 protected:
00712 UGraphAdaptorBase() : Parent() { }
00713 public:
00714 typedef typename Parent::UEdge UEdge;
00715 typedef typename Parent::Edge Edge;
00716
00717 template <typename T>
00718 class EdgeMap {
00719 protected:
00720 const UGraphAdaptorBase<_Graph>* g;
00721 template <typename TT> friend class EdgeMap;
00722 typename _Graph::template EdgeMap<T> forward_map, backward_map;
00723 public:
00724 typedef T Value;
00725 typedef Edge Key;
00726
00727 EdgeMap(const UGraphAdaptorBase<_Graph>& _g) : g(&_g),
00728 forward_map(*(g->graph)), backward_map(*(g->graph)) { }
00729
00730 EdgeMap(const UGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
00731 forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
00732
00733 void set(Edge e, T a) {
00734 if (g->direction(e))
00735 forward_map.set(e, a);
00736 else
00737 backward_map.set(e, a);
00738 }
00739
00740 T operator[](Edge e) const {
00741 if (g->direction(e))
00742 return forward_map[e];
00743 else
00744 return backward_map[e];
00745 }
00746 };
00747
00748 template <typename T>
00749 class UEdgeMap {
00750 template <typename TT> friend class UEdgeMap;
00751 typename _Graph::template EdgeMap<T> map;
00752 public:
00753 typedef T Value;
00754 typedef UEdge Key;
00755
00756 UEdgeMap(const UGraphAdaptorBase<_Graph>& g) :
00757 map(*(g.graph)) { }
00758
00759 UEdgeMap(const UGraphAdaptorBase<_Graph>& g, T a) :
00760 map(*(g.graph), a) { }
00761
00762 void set(UEdge e, T a) {
00763 map.set(e, a);
00764 }
00765
00766 T operator[](UEdge e) const {
00767 return map[e];
00768 }
00769 };
00770
00771 };
00772
00780 template<typename _Graph>
00781 class UGraphAdaptor :
00782 public IterableUGraphExtender<
00783 UGraphAdaptorBase<_Graph> > {
00784 public:
00785 typedef _Graph Graph;
00786 typedef IterableUGraphExtender<
00787 UGraphAdaptorBase<_Graph> > Parent;
00788 protected:
00789 UGraphAdaptor() { }
00790 public:
00791 UGraphAdaptor(_Graph& _graph) {
00792 setGraph(_graph);
00793 }
00794 };
00795
00796
00797 template <typename _Graph,
00798 typename ForwardFilterMap, typename BackwardFilterMap>
00799 class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
00800 public:
00801 typedef _Graph Graph;
00802 typedef GraphAdaptorBase<_Graph> Parent;
00803 protected:
00804 ForwardFilterMap* forward_filter;
00805 BackwardFilterMap* backward_filter;
00806 SubBidirGraphAdaptorBase() : Parent(),
00807 forward_filter(0), backward_filter(0) { }
00808
00809 void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
00810 forward_filter=&_forward_filter;
00811 }
00812 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
00813 backward_filter=&_backward_filter;
00814 }
00815
00816 public:
00817
00818
00819
00820
00821
00822
00823
00824 typedef typename Parent::Node Node;
00825 typedef typename _Graph::Edge GraphEdge;
00826 template <typename T> class EdgeMap;
00827
00828
00829
00830
00831 class Edge : public _Graph::Edge {
00832 friend class SubBidirGraphAdaptorBase<
00833 Graph, ForwardFilterMap, BackwardFilterMap>;
00834 template<typename T> friend class EdgeMap;
00835 protected:
00836 bool backward;
00837 public:
00838 Edge() { }
00839
00840
00841
00842 Edge(const typename _Graph::Edge& e, bool _backward) :
00843 _Graph::Edge(e), backward(_backward) { }
00844 Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
00845 bool operator==(const Edge& v) const {
00846 return (this->backward==v.backward &&
00847 static_cast<typename _Graph::Edge>(*this)==
00848 static_cast<typename _Graph::Edge>(v));
00849 }
00850 bool operator!=(const Edge& v) const {
00851 return (this->backward!=v.backward ||
00852 static_cast<typename _Graph::Edge>(*this)!=
00853 static_cast<typename _Graph::Edge>(v));
00854 }
00855 };
00856
00857 void first(Node& i) const {
00858 Parent::first(i);
00859 }
00860
00861 void first(Edge& i) const {
00862 Parent::first(i);
00863 i.backward=false;
00864 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00865 !(*forward_filter)[i]) Parent::next(i);
00866 if (*static_cast<GraphEdge*>(&i)==INVALID) {
00867 Parent::first(i);
00868 i.backward=true;
00869 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00870 !(*backward_filter)[i]) Parent::next(i);
00871 }
00872 }
00873
00874 void firstIn(Edge& i, const Node& n) const {
00875 Parent::firstIn(i, n);
00876 i.backward=false;
00877 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00878 !(*forward_filter)[i]) Parent::nextIn(i);
00879 if (*static_cast<GraphEdge*>(&i)==INVALID) {
00880 Parent::firstOut(i, n);
00881 i.backward=true;
00882 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00883 !(*backward_filter)[i]) Parent::nextOut(i);
00884 }
00885 }
00886
00887 void firstOut(Edge& i, const Node& n) const {
00888 Parent::firstOut(i, n);
00889 i.backward=false;
00890 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00891 !(*forward_filter)[i]) Parent::nextOut(i);
00892 if (*static_cast<GraphEdge*>(&i)==INVALID) {
00893 Parent::firstIn(i, n);
00894 i.backward=true;
00895 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00896 !(*backward_filter)[i]) Parent::nextIn(i);
00897 }
00898 }
00899
00900 void next(Node& i) const {
00901 Parent::next(i);
00902 }
00903
00904 void next(Edge& i) const {
00905 if (!(i.backward)) {
00906 Parent::next(i);
00907 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00908 !(*forward_filter)[i]) Parent::next(i);
00909 if (*static_cast<GraphEdge*>(&i)==INVALID) {
00910 Parent::first(i);
00911 i.backward=true;
00912 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00913 !(*backward_filter)[i]) Parent::next(i);
00914 }
00915 } else {
00916 Parent::next(i);
00917 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00918 !(*backward_filter)[i]) Parent::next(i);
00919 }
00920 }
00921
00922 void nextIn(Edge& i) const {
00923 if (!(i.backward)) {
00924 Node n=Parent::target(i);
00925 Parent::nextIn(i);
00926 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00927 !(*forward_filter)[i]) Parent::nextIn(i);
00928 if (*static_cast<GraphEdge*>(&i)==INVALID) {
00929 Parent::firstOut(i, n);
00930 i.backward=true;
00931 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00932 !(*backward_filter)[i]) Parent::nextOut(i);
00933 }
00934 } else {
00935 Parent::nextOut(i);
00936 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00937 !(*backward_filter)[i]) Parent::nextOut(i);
00938 }
00939 }
00940
00941 void nextOut(Edge& i) const {
00942 if (!(i.backward)) {
00943 Node n=Parent::source(i);
00944 Parent::nextOut(i);
00945 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00946 !(*forward_filter)[i]) Parent::nextOut(i);
00947 if (*static_cast<GraphEdge*>(&i)==INVALID) {
00948 Parent::firstIn(i, n);
00949 i.backward=true;
00950 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00951 !(*backward_filter)[i]) Parent::nextIn(i);
00952 }
00953 } else {
00954 Parent::nextIn(i);
00955 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
00956 !(*backward_filter)[i]) Parent::nextIn(i);
00957 }
00958 }
00959
00960 Node source(Edge e) const {
00961 return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
00962 Node target(Edge e) const {
00963 return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
00964
00966
00969 Edge opposite(const Edge& e) const {
00970 Edge f=e;
00971 f.backward=!f.backward;
00972 return f;
00973 }
00974
00976
00980 int edgeNum() const {
00981 int i=0;
00982 Edge e;
00983 for (first(e); e!=INVALID; next(e)) ++i;
00984 return i;
00985 }
00986
00987 bool forward(const Edge& e) const { return !e.backward; }
00988 bool backward(const Edge& e) const { return e.backward; }
00989
00991
00995 template <typename T>
00996 class EdgeMap {
00997 template <typename TT> friend class EdgeMap;
00998 typename _Graph::template EdgeMap<T> forward_map, backward_map;
00999 public:
01000 typedef T Value;
01001 typedef Edge Key;
01002
01003 EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
01004 ForwardFilterMap, BackwardFilterMap>& g) :
01005 forward_map(*(g.graph)), backward_map(*(g.graph)) { }
01006
01007 EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
01008 ForwardFilterMap, BackwardFilterMap>& g, T a) :
01009 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
01010
01011 void set(Edge e, T a) {
01012 if (!e.backward)
01013 forward_map.set(e, a);
01014 else
01015 backward_map.set(e, a);
01016 }
01017
01018
01019
01020
01021
01022
01023
01024
01025
01026
01027 T operator[](Edge e) const {
01028 if (!e.backward)
01029 return forward_map[e];
01030 else
01031 return backward_map[e];
01032 }
01033
01034 void update() {
01035 forward_map.update();
01036 backward_map.update();
01037 }
01038 };
01039
01040 };
01041
01042
01083 template<typename _Graph,
01084 typename ForwardFilterMap, typename BackwardFilterMap>
01085 class SubBidirGraphAdaptor :
01086 public IterableGraphExtender<
01087 SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
01088 public:
01089 typedef _Graph Graph;
01090 typedef IterableGraphExtender<
01091 SubBidirGraphAdaptorBase<
01092 _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
01093 protected:
01094 SubBidirGraphAdaptor() { }
01095 public:
01096 SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,
01097 BackwardFilterMap& _backward_filter) {
01098 setGraph(_graph);
01099 setForwardFilterMap(_forward_filter);
01100 setBackwardFilterMap(_backward_filter);
01101 }
01102 };
01103
01104
01105
01117 template<typename Graph>
01118 class BidirGraphAdaptor :
01119 public SubBidirGraphAdaptor<
01120 Graph,
01121 ConstMap<typename Graph::Edge, bool>,
01122 ConstMap<typename Graph::Edge, bool> > {
01123 public:
01124 typedef SubBidirGraphAdaptor<
01125 Graph,
01126 ConstMap<typename Graph::Edge, bool>,
01127 ConstMap<typename Graph::Edge, bool> > Parent;
01128 protected:
01129 ConstMap<typename Graph::Edge, bool> cm;
01130
01131 BidirGraphAdaptor() : Parent(), cm(true) {
01132 Parent::setForwardFilterMap(cm);
01133 Parent::setBackwardFilterMap(cm);
01134 }
01135 public:
01136 BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {
01137 Parent::setGraph(_graph);
01138 Parent::setForwardFilterMap(cm);
01139 Parent::setBackwardFilterMap(cm);
01140 }
01141
01142 int edgeNum() const {
01143 return 2*this->graph->edgeNum();
01144 }
01145 };
01146
01147
01148 template<typename Graph, typename Number,
01149 typename CapacityMap, typename FlowMap>
01150 class ResForwardFilter {
01151
01152 const CapacityMap* capacity;
01153 const FlowMap* flow;
01154 public:
01155 ResForwardFilter(
01156 const CapacityMap& _capacity, const FlowMap& _flow) :
01157 capacity(&_capacity), flow(&_flow) { }
01158 ResForwardFilter() : capacity(0), flow(0) { }
01159 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
01160 void setFlow(const FlowMap& _flow) { flow=&_flow; }
01161 bool operator[](const typename Graph::Edge& e) const {
01162 return (Number((*flow)[e]) < Number((*capacity)[e]));
01163 }
01164 };
01165
01166 template<typename Graph, typename Number,
01167 typename CapacityMap, typename FlowMap>
01168 class ResBackwardFilter {
01169 const CapacityMap* capacity;
01170 const FlowMap* flow;
01171 public:
01172 ResBackwardFilter(
01173 const CapacityMap& _capacity, const FlowMap& _flow) :
01174 capacity(&_capacity), flow(&_flow) { }
01175 ResBackwardFilter() : capacity(0), flow(0) { }
01176 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
01177 void setFlow(const FlowMap& _flow) { flow=&_flow; }
01178 bool operator[](const typename Graph::Edge& e) const {
01179 return (Number(0) < Number((*flow)[e]));
01180 }
01181 };
01182
01183
01219 template<typename Graph, typename Number,
01220 typename CapacityMap, typename FlowMap>
01221 class ResGraphAdaptor :
01222 public SubBidirGraphAdaptor<
01223 Graph,
01224 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
01225 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
01226 public:
01227 typedef SubBidirGraphAdaptor<
01228 Graph,
01229 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
01230 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
01231 protected:
01232 const CapacityMap* capacity;
01233 FlowMap* flow;
01234 ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
01235 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
01236 ResGraphAdaptor() : Parent(),
01237 capacity(0), flow(0) { }
01238 void setCapacityMap(const CapacityMap& _capacity) {
01239 capacity=&_capacity;
01240 forward_filter.setCapacity(_capacity);
01241 backward_filter.setCapacity(_capacity);
01242 }
01243 void setFlowMap(FlowMap& _flow) {
01244 flow=&_flow;
01245 forward_filter.setFlow(_flow);
01246 backward_filter.setFlow(_flow);
01247 }
01248 public:
01249 ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
01250 FlowMap& _flow) :
01251 Parent(), capacity(&_capacity), flow(&_flow),
01252 forward_filter( _capacity, _flow),
01253 backward_filter( _capacity, _flow) {
01254 Parent::setGraph(_graph);
01255 Parent::setForwardFilterMap(forward_filter);
01256 Parent::setBackwardFilterMap(backward_filter);
01257 }
01258
01259 typedef typename Parent::Edge Edge;
01260
01261 void augment(const Edge& e, Number a) const {
01262 if (Parent::forward(e))
01263 flow->set(e, (*flow)[e]+a);
01264 else
01265 flow->set(e, (*flow)[e]-a);
01266 }
01267
01272 class ResCap {
01273 protected:
01274 const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
01275 public:
01276 typedef Number Value;
01277 typedef Edge Key;
01278 ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&
01279 _res_graph) : res_graph(&_res_graph) { }
01280 Number operator[](const Edge& e) const {
01281 if (res_graph->forward(e))
01282 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
01283 else
01284 return (*(res_graph->flow))[e];
01285 }
01286 };
01287
01288
01289 };
01290
01291
01292
01293 template <typename _Graph, typename FirstOutEdgesMap>
01294 class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
01295 public:
01296 typedef _Graph Graph;
01297 typedef GraphAdaptorBase<_Graph> Parent;
01298 protected:
01299 FirstOutEdgesMap* first_out_edges;
01300 ErasingFirstGraphAdaptorBase() : Parent(),
01301 first_out_edges(0) { }
01302
01303 void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
01304 first_out_edges=&_first_out_edges;
01305 }
01306
01307 public:
01308
01309 typedef typename Parent::Node Node;
01310 typedef typename Parent::Edge Edge;
01311
01312 void firstOut(Edge& i, const Node& n) const {
01313 i=(*first_out_edges)[n];
01314 }
01315
01316 void erase(const Edge& e) const {
01317 Node n=source(e);
01318 Edge f=e;
01319 Parent::nextOut(f);
01320 first_out_edges->set(n, f);
01321 }
01322 };
01323
01324
01342 template <typename _Graph, typename FirstOutEdgesMap>
01343 class ErasingFirstGraphAdaptor :
01344 public IterableGraphExtender<
01345 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
01346 public:
01347 typedef _Graph Graph;
01348 typedef IterableGraphExtender<
01349 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
01350 ErasingFirstGraphAdaptor(Graph& _graph,
01351 FirstOutEdgesMap& _first_out_edges) {
01352 setGraph(_graph);
01353 setFirstOutEdgesMap(_first_out_edges);
01354 }
01355
01356 };
01357
01358 template <typename _Graph>
01359 class SplitGraphAdaptorBase
01360 : public GraphAdaptorBase<_Graph> {
01361 public:
01362 typedef GraphAdaptorBase<_Graph> Parent;
01363
01364 class Node;
01365 class Edge;
01366 template <typename T> class NodeMap;
01367 template <typename T> class EdgeMap;
01368
01369
01370 class Node : public Parent::Node {
01371 friend class SplitGraphAdaptorBase;
01372 template <typename T> friend class NodeMap;
01373 typedef typename Parent::Node NodeParent;
01374 private:
01375
01376 bool entry;
01377 Node(typename Parent::Node _node, bool _entry)
01378 : Parent::Node(_node), entry(_entry) {}
01379
01380 public:
01381 Node() {}
01382 Node(Invalid) : NodeParent(INVALID), entry(true) {}
01383
01384 bool operator==(const Node& node) const {
01385 return NodeParent::operator==(node) && entry == node.entry;
01386 }
01387
01388 bool operator!=(const Node& node) const {
01389 return !(*this == node);
01390 }
01391
01392 bool operator<(const Node& node) const {
01393 return NodeParent::operator<(node) ||
01394 (NodeParent::operator==(node) && entry < node.entry);
01395 }
01396 };
01397
01399 class Edge : public Parent::Edge {
01400 friend class SplitGraphAdaptorBase;
01401 template <typename T> friend class EdgeMap;
01402 private:
01403 typedef typename Parent::Edge EdgeParent;
01404 typedef typename Parent::Node NodeParent;
01405 NodeParent bind;
01406
01407 Edge(const EdgeParent& edge, const NodeParent& node)
01408 : EdgeParent(edge), bind(node) {}
01409 public:
01410 Edge() {}
01411 Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {}
01412
01413 bool operator==(const Edge& edge) const {
01414 return EdgeParent::operator==(edge) && bind == edge.bind;
01415 }
01416
01417 bool operator!=(const Edge& edge) const {
01418 return !(*this == edge);
01419 }
01420
01421 bool operator<(const Edge& edge) const {
01422 return EdgeParent::operator<(edge) ||
01423 (EdgeParent::operator==(edge) && bind < edge.bind);
01424 }
01425 };
01426
01427 void first(Node& node) const {
01428 Parent::first(node);
01429 node.entry = true;
01430 }
01431
01432 void next(Node& node) const {
01433 if (node.entry) {
01434 node.entry = false;
01435 } else {
01436 node.entry = true;
01437 Parent::next(node);
01438 }
01439 }
01440
01441 void first(Edge& edge) const {
01442 Parent::first(edge);
01443 if ((typename Parent::Edge&)edge == INVALID) {
01444 Parent::first(edge.bind);
01445 } else {
01446 edge.bind = INVALID;
01447 }
01448 }
01449
01450 void next(Edge& edge) const {
01451 if ((typename Parent::Edge&)edge != INVALID) {
01452 Parent::next(edge);
01453 if ((typename Parent::Edge&)edge == INVALID) {
01454 Parent::first(edge.bind);
01455 }
01456 } else {
01457 Parent::next(edge.bind);
01458 }
01459 }
01460
01461 void firstIn(Edge& edge, const Node& node) const {
01462 if (node.entry) {
01463 Parent::firstIn(edge, node);
01464 edge.bind = INVALID;
01465 } else {
01466 (typename Parent::Edge&)edge = INVALID;
01467 edge.bind = node;
01468 }
01469 }
01470
01471 void nextIn(Edge& edge) const {
01472 if ((typename Parent::Edge&)edge != INVALID) {
01473 Parent::nextIn(edge);
01474 } else {
01475 edge.bind = INVALID;
01476 }
01477 }
01478
01479 void firstOut(Edge& edge, const Node& node) const {
01480 if (!node.entry) {
01481 Parent::firstOut(edge, node);
01482 edge.bind = INVALID;
01483 } else {
01484 (typename Parent::Edge&)edge = INVALID;
01485 edge.bind = node;
01486 }
01487 }
01488
01489 void nextOut(Edge& edge) const {
01490 if ((typename Parent::Edge&)edge != INVALID) {
01491 Parent::nextOut(edge);
01492 } else {
01493 edge.bind = INVALID;
01494 }
01495 }
01496
01497 Node source(const Edge& edge) const {
01498 if ((typename Parent::Edge&)edge != INVALID) {
01499 return Node(Parent::source(edge), false);
01500 } else {
01501 return Node(edge.bind, true);
01502 }
01503 }
01504
01505 Node target(const Edge& edge) const {
01506 if ((typename Parent::Edge&)edge != INVALID) {
01507 return Node(Parent::target(edge), true);
01508 } else {
01509 return Node(edge.bind, false);
01510 }
01511 }
01512
01513 static bool entryNode(const Node& node) {
01514 return node.entry;
01515 }
01516
01517 static bool exitNode(const Node& node) {
01518 return !node.entry;
01519 }
01520
01521 static Node getEntry(const typename Parent::Node& node) {
01522 return Node(node, true);
01523 }
01524
01525 static Node getExit(const typename Parent::Node& node) {
01526 return Node(node, false);
01527 }
01528
01529 static bool originalEdge(const Edge& edge) {
01530 return (typename Parent::Edge&)edge != INVALID;
01531 }
01532
01533 static bool bindingEdge(const Edge& edge) {
01534 return edge.bind != INVALID;
01535 }
01536
01537 static Node getBindedNode(const Edge& edge) {
01538 return edge.bind;
01539 }
01540
01541 int nodeNum() const {
01542 return Parent::nodeNum() * 2;
01543 }
01544
01545 typedef CompileTimeAnd<typename Parent::NodeNumTag,
01546 typename Parent::EdgeNumTag> EdgeNumTag;
01547
01548 int edgeNum() const {
01549 return Parent::edgeNum() + Parent::nodeNum();
01550 }
01551
01552 Edge findEdge(const Node& source, const Node& target,
01553 const Edge& prev = INVALID) const {
01554 if (exitNode(source) && entryNode(target)) {
01555 return Parent::findEdge(source, target, prev);
01556 } else {
01557 if (prev == INVALID && entryNode(source) && exitNode(target) &&
01558 (typename Parent::Node&)source == (typename Parent::Node&)target) {
01559 return Edge(INVALID, source);
01560 } else {
01561 return INVALID;
01562 }
01563 }
01564 }
01565
01566 template <typename T>
01567 class NodeMap : public MapBase<Node, T> {
01568 typedef typename Parent::template NodeMap<T> NodeImpl;
01569 public:
01570 NodeMap(const SplitGraphAdaptorBase& _graph)
01571 : entry(_graph), exit(_graph) {}
01572 NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
01573 : entry(_graph, t), exit(_graph, t) {}
01574
01575 void set(const Node& key, const T& val) {
01576 if (key.entry) { entry.set(key, val); }
01577 else {exit.set(key, val); }
01578 }
01579
01580 typename MapTraits<NodeImpl>::ReturnValue
01581 operator[](const Node& key) {
01582 if (key.entry) { return entry[key]; }
01583 else { return exit[key]; }
01584 }
01585
01586 typename MapTraits<NodeImpl>::ConstReturnValue
01587 operator[](const Node& key) const {
01588 if (key.entry) { return entry[key]; }
01589 else { return exit[key]; }
01590 }
01591
01592 private:
01593 NodeImpl entry, exit;
01594 };
01595
01596 template <typename T>
01597 class EdgeMap : public MapBase<Edge, T> {
01598 typedef typename Parent::template NodeMap<T> NodeImpl;
01599 typedef typename Parent::template EdgeMap<T> EdgeImpl;
01600 public:
01601 EdgeMap(const SplitGraphAdaptorBase& _graph)
01602 : bind(_graph), orig(_graph) {}
01603 EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
01604 : bind(_graph, t), orig(_graph, t) {}
01605
01606 void set(const Edge& key, const T& val) {
01607 if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); }
01608 else {bind.set(key.bind, val); }
01609 }
01610
01611 typename MapTraits<EdgeImpl>::ReturnValue
01612 operator[](const Edge& key) {
01613 if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
01614 else {return bind[key.bind]; }
01615 }
01616
01617 typename MapTraits<EdgeImpl>::ConstReturnValue
01618 operator[](const Edge& key) const {
01619 if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
01620 else {return bind[key.bind]; }
01621 }
01622
01623 private:
01624 typename Parent::template NodeMap<T> bind;
01625 typename Parent::template EdgeMap<T> orig;
01626 };
01627
01628 template <typename EntryMap, typename ExitMap>
01629 class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> {
01630 public:
01631 typedef MapBase<Node, typename EntryMap::Value> Parent;
01632
01633 typedef typename Parent::Key Key;
01634 typedef typename Parent::Value Value;
01635
01636 CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap)
01637 : entryMap(_entryMap), exitMap(_exitMap) {}
01638
01639 Value& operator[](const Key& key) {
01640 if (key.entry) {
01641 return entryMap[key];
01642 } else {
01643 return exitMap[key];
01644 }
01645 }
01646
01647 Value operator[](const Key& key) const {
01648 if (key.entry) {
01649 return entryMap[key];
01650 } else {
01651 return exitMap[key];
01652 }
01653 }
01654
01655 void set(const Key& key, const Value& value) {
01656 if (key.entry) {
01657 entryMap.set(key, value);
01658 } else {
01659 exitMap.set(key, value);
01660 }
01661 }
01662
01663 private:
01664
01665 EntryMap& entryMap;
01666 ExitMap& exitMap;
01667
01668 };
01669
01670 template <typename EdgeMap, typename NodeMap>
01671 class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> {
01672 public:
01673 typedef MapBase<Edge, typename EdgeMap::Value> Parent;
01674
01675 typedef typename Parent::Key Key;
01676 typedef typename Parent::Value Value;
01677
01678 CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap)
01679 : edgeMap(_edgeMap), nodeMap(_nodeMap) {}
01680
01681 void set(const Edge& edge, const Value& val) {
01682 if (SplitGraphAdaptorBase::originalEdge(edge)) {
01683 edgeMap.set(edge, val);
01684 } else {
01685 nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val);
01686 }
01687 }
01688
01689 Value operator[](const Key& edge) const {
01690 if (SplitGraphAdaptorBase::originalEdge(edge)) {
01691 return edgeMap[edge];
01692 } else {
01693 return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
01694 }
01695 }
01696
01697 Value& operator[](const Key& edge) {
01698 if (SplitGraphAdaptorBase::originalEdge(edge)) {
01699 return edgeMap[edge];
01700 } else {
01701 return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
01702 }
01703 }
01704
01705 private:
01706 EdgeMap& edgeMap;
01707 NodeMap& nodeMap;
01708 };
01709
01710 };
01711
01712 template <typename _Graph>
01713 class SplitGraphAdaptor
01714 : public IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > {
01715 public:
01716 typedef IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > Parent;
01717
01718 SplitGraphAdaptor(_Graph& graph) {
01719 Parent::setGraph(graph);
01720 }
01721
01722
01723 };
01724
01725 }
01726
01727 #endif //LEMON_GRAPH_ADAPTOR_H
01728