1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/doc/images/edge_disjoint.eps Fri May 12 09:56:14 2006 +0000
1.3 @@ -0,0 +1,116 @@
1.4 +%!PS-Adobe-2.0 EPSF-2.0
1.5 +%%Title: edge disjoint path
1.6 +%%Copyright: (C) 2006 LEMON Project
1.7 +%%Creator: LEMON, graphToEps()
1.8 +%%CreationDate: Fri May 12 01:53:21 2006
1.9 +%%BoundingBox: -290 -170 470 230
1.10 +%%EndComments
1.11 +/lb { setlinewidth setrgbcolor newpath moveto
1.12 + 4 2 roll 1 index 1 index curveto stroke } bind def
1.13 +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
1.14 +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
1.15 +/sq { newpath 2 index 1 index add 2 index 2 index add moveto
1.16 + 2 index 1 index sub 2 index 2 index add lineto
1.17 + 2 index 1 index sub 2 index 2 index sub lineto
1.18 + 2 index 1 index add 2 index 2 index sub lineto
1.19 + closepath pop pop pop} bind def
1.20 +/di { newpath 2 index 1 index add 2 index moveto
1.21 + 2 index 2 index 2 index add lineto
1.22 + 2 index 1 index sub 2 index lineto
1.23 + 2 index 2 index 2 index sub lineto
1.24 + closepath pop pop pop} bind def
1.25 +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
1.26 + setrgbcolor 1.1 div c fill
1.27 + } bind def
1.28 +/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
1.29 + setrgbcolor 1.1 div sq fill
1.30 + } bind def
1.31 +/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
1.32 + setrgbcolor 1.1 div di fill
1.33 + } bind def
1.34 +/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
1.35 + newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
1.36 + lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
1.37 + 5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
1.38 + 5 index 5 index 5 index c fill
1.39 + setrgbcolor 1.1 div c fill
1.40 + } bind def
1.41 +/nmale {
1.42 + 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
1.43 + newpath 5 index 5 index moveto
1.44 + 5 index 4 index 1 mul 1.5 mul add
1.45 + 5 index 5 index 3 sqrt 1.5 mul mul add
1.46 + 1 index 1 index lineto
1.47 + 1 index 1 index 7 index sub moveto
1.48 + 1 index 1 index lineto
1.49 + exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
1.50 + stroke
1.51 + 5 index 5 index 5 index c fill
1.52 + setrgbcolor 1.1 div c fill
1.53 + } bind def
1.54 +/arrl 1 def
1.55 +/arrw 0.3 def
1.56 +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
1.57 +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
1.58 + /w exch def /len exch def
1.59 + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
1.60 + len w sub arrl sub dx dy lrl
1.61 + arrw dy dx neg lrl
1.62 + dx arrl w add mul dy w 2 div arrw add mul sub
1.63 + dy arrl w add mul dx w 2 div arrw add mul add rlineto
1.64 + dx arrl w add mul neg dy w 2 div arrw add mul sub
1.65 + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
1.66 + arrw dy dx neg lrl
1.67 + len w sub arrl sub neg dx dy lrl
1.68 + closepath fill } bind def
1.69 +/cshow { 2 index 2 index moveto dup stringwidth pop
1.70 + neg 2 div fosi .35 mul neg rmoveto show pop pop} def
1.71 +
1.72 +gsave
1.73 +10 dup scale
1.74 +%Edges:
1.75 +gsave
1.76 +15.6433 0.3 0.841178 -0.540758 -27 5 1 0 0 arr
1.77 +19.5913 0.3 0.874157 0.485643 -27 5 1 0 0 arr
1.78 +10.1803 0.3 0.98387 -0.178885 -20 17 1 0 0 arr
1.79 +20.587 0.3 0.972806 0.231621 -18 -14 1 0 0 arr
1.80 +15.7631 0.3 0.95448 -0.298275 -13 -4 0 0 0 arr
1.81 +15.9706 0.3 0.707107 -0.707107 -9 15 1 0 0 arr
1.82 +16.4642 0.3 0.916157 0.400819 -13 -4 1 0 0 arr
1.83 +14.5242 0.3 0.966235 -0.257663 -12 7 0 0 0 arr
1.84 +10.6619 0.3 0.857493 0.514496 -9 15 1 0 0 arr
1.85 +22.4094 0.3 0.939793 -0.341743 3 3 1 0 0 arr
1.86 +27.1602 0.3 0.958798 -0.284088 1 21 1 0 0 arr
1.87 +25.9258 0.3 0.928477 0.371391 3 3 1 0 0 arr
1.88 +25.9072 0.3 0.743294 0.668965 25 -15 1 0 0 arr
1.89 +20.5407 0.3 0.928477 0.371391 25 -5 1 0 0 arr
1.90 +18.7231 0.3 0.861934 -0.50702 28 13 1 0 0 arr
1.91 +14.2315 0.3 0.393919 0.919145 39 -11 0 0 0 arr
1.92 +10.6619 0.3 0.514496 -0.857493 39 13 1 0 0 arr
1.93 +20.0238 0.3 0.428086 -0.903738 -27 5 1 0 0 arr
1.94 +21.8035 0.3 0.964764 -0.263117 3 -9 1 0 0 arr
1.95 +14.1328 0.3 0.991228 0.132164 -27 5 0 0 0 arr
1.96 +13.5602 0.3 0.961524 0.274721 25 -15 0 0 0 arr
1.97 +10 0.3 1 0 28 13 1 0 0 arr
1.98 +12.8924 0.3 0.503871 0.863779 -27 5 1 0 0 arr
1.99 +grestore
1.100 +%Nodes:
1.101 +gsave
1.102 +-27 5 1 1 1 1 nc
1.103 +-13 -4 1 1 1 1 nc
1.104 +-9 15 1 1 1 1 nc
1.105 +3 -9 1 1 1 1 nc
1.106 +3 3 1 1 1 1 nc
1.107 +1 21 1 1 1 1 nc
1.108 +25 -5 1 1 1 1 nc
1.109 +28 13 1 1 1 1 nc
1.110 +45 3 1 1 1 1 nc
1.111 +-18 -14 1 1 1 1 nc
1.112 +25 -15 1 1 1 1 nc
1.113 +-12 7 1 1 1 1 nc
1.114 +39 -11 1 1 1 1 nc
1.115 +39 13 1 1 1 1 nc
1.116 +-20 17 1 1 1 1 nc
1.117 +grestore
1.118 +grestore
1.119 +showpage
2.1 Binary file doc/images/edge_disjoint.png has changed
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/doc/images/node_disjoint.eps Fri May 12 09:56:14 2006 +0000
3.3 @@ -0,0 +1,146 @@
3.4 +%!PS-Adobe-2.0 EPSF-2.0
3.5 +%%Title: node disjoint path
3.6 +%%Copyright: (C) 2006 LEMON Project
3.7 +%%Creator: LEMON, graphToEps()
3.8 +%%CreationDate: Fri May 12 01:53:21 2006
3.9 +%%BoundingBox: -290 -170 520 230
3.10 +%%EndComments
3.11 +/lb { setlinewidth setrgbcolor newpath moveto
3.12 + 4 2 roll 1 index 1 index curveto stroke } bind def
3.13 +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
3.14 +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
3.15 +/sq { newpath 2 index 1 index add 2 index 2 index add moveto
3.16 + 2 index 1 index sub 2 index 2 index add lineto
3.17 + 2 index 1 index sub 2 index 2 index sub lineto
3.18 + 2 index 1 index add 2 index 2 index sub lineto
3.19 + closepath pop pop pop} bind def
3.20 +/di { newpath 2 index 1 index add 2 index moveto
3.21 + 2 index 2 index 2 index add lineto
3.22 + 2 index 1 index sub 2 index lineto
3.23 + 2 index 2 index 2 index sub lineto
3.24 + closepath pop pop pop} bind def
3.25 +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
3.26 + setrgbcolor 1.1 div c fill
3.27 + } bind def
3.28 +/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
3.29 + setrgbcolor 1.1 div sq fill
3.30 + } bind def
3.31 +/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
3.32 + setrgbcolor 1.1 div di fill
3.33 + } bind def
3.34 +/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
3.35 + newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
3.36 + lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
3.37 + 5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
3.38 + 5 index 5 index 5 index c fill
3.39 + setrgbcolor 1.1 div c fill
3.40 + } bind def
3.41 +/nmale {
3.42 + 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
3.43 + newpath 5 index 5 index moveto
3.44 + 5 index 4 index 1 mul 1.5 mul add
3.45 + 5 index 5 index 3 sqrt 1.5 mul mul add
3.46 + 1 index 1 index lineto
3.47 + 1 index 1 index 7 index sub moveto
3.48 + 1 index 1 index lineto
3.49 + exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
3.50 + stroke
3.51 + 5 index 5 index 5 index c fill
3.52 + setrgbcolor 1.1 div c fill
3.53 + } bind def
3.54 +/arrl 1 def
3.55 +/arrw 0.3 def
3.56 +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
3.57 +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
3.58 + /w exch def /len exch def
3.59 + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
3.60 + len w sub arrl sub dx dy lrl
3.61 + arrw dy dx neg lrl
3.62 + dx arrl w add mul dy w 2 div arrw add mul sub
3.63 + dy arrl w add mul dx w 2 div arrw add mul add rlineto
3.64 + dx arrl w add mul neg dy w 2 div arrw add mul sub
3.65 + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
3.66 + arrw dy dx neg lrl
3.67 + len w sub arrl sub neg dx dy lrl
3.68 + closepath fill } bind def
3.69 +/cshow { 2 index 2 index moveto dup stringwidth pop
3.70 + neg 2 div fosi .35 mul neg rmoveto show pop pop} def
3.71 +
3.72 +gsave
3.73 +10 dup scale
3.74 +%Edges:
3.75 +gsave
3.76 +4 0.3 1 0 -27 5 0 0 0 arr
3.77 +4 0.3 1 0 -13 -4 1 0 0 arr
3.78 +4 0.3 1 0 -9 15 1 0 0 arr
3.79 +4 0.3 1 0 3 -9 1 0 0 arr
3.80 +4 0.3 1 0 3 3 1 0 0 arr
3.81 +4 0.3 1 0 1 21 1 0 0 arr
3.82 +4 0.3 1 0 25 -5 1 0 0 arr
3.83 +4 0.3 1 0 28 13 1 0 0 arr
3.84 +4 0.3 1 0 45 3 0 0 0 arr
3.85 +4 0.3 1 0 -18 -14 1 0 0 arr
3.86 +4 0.3 1 0 25 -15 1 0 0 arr
3.87 +4 0.3 1 0 -12 7 0 0 0 arr
3.88 +4 0.3 1 0 39 -11 0 0 0 arr
3.89 +4 0.3 1 0 39 13 0 0 0 arr
3.90 +4 0.3 1 0 -20 17 1 0 0 arr
3.91 +11.7279 0.3 0.707107 -0.707107 -22 5 1 0 0 arr
3.92 +15.4012 0.3 0.792624 0.609711 -22 5 0 0 0 arr
3.93 +5.32455 0.3 0.948683 -0.316228 -15 17 1 0 0 arr
3.94 +15.7631 0.3 0.95448 0.298275 -13 -14 1 0 0 arr
3.95 +11.083 0.3 0.910366 -0.413803 -8 -4 0 0 0 arr
3.96 +12.8924 0.3 0.503871 -0.863779 -4 15 0 0 0 arr
3.97 +12.0384 0.3 0.843661 0.536875 -8 -4 1 0 0 arr
3.98 +9.77033 0.3 0.928477 -0.371391 -7 7 0 0 0 arr
3.99 +6.81025 0.3 0.640184 0.768221 -4 15 1 0 0 arr
3.100 +17.7883 0.3 0.904819 -0.425797 8 3 1 0 0 arr
3.101 +22.4094 0.3 0.939793 -0.341743 6 21 1 0 0 arr
3.102 +21.3607 0.3 0.894427 0.447214 8 3 0 0 0 arr
3.103 +22.4307 0.3 0.640184 0.768221 30 -15 1 0 0 arr
3.104 +16 0.3 0.882353 0.470588 30 -5 1 0 0 arr
3.105 +14.6205 0.3 0.768221 -0.640184 33 13 1 0 0 arr
3.106 +13.0357 0.3 0.071247 0.997459 44 -11 0 0 0 arr
3.107 +9.04987 0.3 0.0995037 -0.995037 44 13 0 0 0 arr
3.108 +18.4165 0.3 0.20601 -0.97855 -22 5 1 0 0 arr
3.109 +17.0278 0.3 0.94299 -0.33282 8 -9 1 0 0 arr
3.110 +9.19804 0.3 0.980581 0.196116 -22 5 0 0 0 arr
3.111 +8.84886 0.3 0.913812 0.406138 30 -15 0 0 0 arr
3.112 +5 0.3 1 0 33 13 0 0 0 arr
3.113 +11.1655 0.3 0.164399 0.986394 -22 5 1 0 0 arr
3.114 +grestore
3.115 +%Nodes:
3.116 +gsave
3.117 +-27 5 1 1 1 1 nc
3.118 +-22 5 1 1 1 1 nc
3.119 +-13 -4 1 1 1 1 nc
3.120 +-8 -4 1 1 1 1 nc
3.121 +-9 15 1 1 1 1 nc
3.122 +-4 15 1 1 1 1 nc
3.123 +3 -9 1 1 1 1 nc
3.124 +8 -9 1 1 1 1 nc
3.125 +3 3 1 1 1 1 nc
3.126 +8 3 1 1 1 1 nc
3.127 +1 21 1 1 1 1 nc
3.128 +6 21 1 1 1 1 nc
3.129 +25 -5 1 1 1 1 nc
3.130 +30 -5 1 1 1 1 nc
3.131 +28 13 1 1 1 1 nc
3.132 +33 13 1 1 1 1 nc
3.133 +45 3 1 1 1 1 nc
3.134 +50 3 1 1 1 1 nc
3.135 +-18 -14 1 1 1 1 nc
3.136 +-13 -14 1 1 1 1 nc
3.137 +25 -15 1 1 1 1 nc
3.138 +30 -15 1 1 1 1 nc
3.139 +-12 7 1 1 1 1 nc
3.140 +-7 7 1 1 1 1 nc
3.141 +39 -11 1 1 1 1 nc
3.142 +44 -11 1 1 1 1 nc
3.143 +39 13 1 1 1 1 nc
3.144 +44 13 1 1 1 1 nc
3.145 +-20 17 1 1 1 1 nc
3.146 +-15 17 1 1 1 1 nc
3.147 +grestore
3.148 +grestore
3.149 +showpage
4.1 Binary file doc/images/node_disjoint.png has changed
5.1 --- a/lemon/graph_adaptor.h Fri May 12 09:54:58 2006 +0000
5.2 +++ b/lemon/graph_adaptor.h Fri May 12 09:56:14 2006 +0000
5.3 @@ -36,7 +36,7 @@
5.4
5.5 #include <lemon/tolerance.h>
5.6
5.7 -#include <iostream>
5.8 +#include <algorithm>
5.9
5.10 namespace lemon {
5.11
5.12 @@ -256,9 +256,8 @@
5.13 ///\code
5.14 /// RevGraphAdaptor<ListGraph> ga(g);
5.15 ///\endcode
5.16 - ///implements the graph obtained from \c g by
5.17 + /// implements the graph obtained from \c g by
5.18 /// reversing the orientation of its edges.
5.19 -
5.20 template<typename _Graph>
5.21 class RevGraphAdaptor :
5.22 public GraphAdaptorExtender<RevGraphAdaptorBase<_Graph> > {
5.23 @@ -983,13 +982,13 @@
5.24 return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
5.25 }
5.26
5.27 - template <typename _Graph, typename Enable = void>
5.28 + template <typename _Graph>
5.29 class UndirGraphAdaptorBase :
5.30 - public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
5.31 + public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
5.32 public:
5.33 typedef _Graph Graph;
5.34 typedef UndirGraphAdaptorBase Adaptor;
5.35 - typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
5.36 + typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
5.37
5.38 protected:
5.39
5.40 @@ -1103,38 +1102,50 @@
5.41
5.42 };
5.43
5.44 - template <typename _Graph>
5.45 - class UndirGraphAdaptorBase<
5.46 - _Graph, typename enable_if<
5.47 - typename _Graph::EdgeNotifier::Notifier>::type >
5.48 - : public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
5.49 + template <typename _Graph, typename Enable = void>
5.50 + class AlterableUndirGraphAdaptor
5.51 + : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {
5.52 + public:
5.53 + typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;
5.54 +
5.55 + protected:
5.56 +
5.57 + AlterableUndirGraphAdaptor() : Parent() {}
5.58 +
5.59 public:
5.60
5.61 + typedef typename Parent::EdgeNotifier UEdgeNotifier;
5.62 + typedef InvalidType EdgeNotifier;
5.63 +
5.64 + };
5.65 +
5.66 + template <typename _Graph>
5.67 + class AlterableUndirGraphAdaptor<
5.68 + _Graph,
5.69 + typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type >
5.70 + : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {
5.71 + public:
5.72 +
5.73 + typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;
5.74 typedef _Graph Graph;
5.75 - typedef UndirGraphAdaptorBase Adaptor;
5.76 - typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
5.77 -
5.78 + typedef typename _Graph::Edge GraphEdge;
5.79 +
5.80 protected:
5.81
5.82 - UndirGraphAdaptorBase()
5.83 - : edge_notifier(*this), edge_notifier_proxy(edge_notifier) {}
5.84 + AlterableUndirGraphAdaptor()
5.85 + : Parent(), edge_notifier(*this), edge_notifier_proxy(*this) {}
5.86
5.87 void setGraph(_Graph& graph) {
5.88 Parent::setGraph(graph);
5.89 - edge_notifier_proxy.setUEdgeNotifier(graph.getNotifier(UEdge()));
5.90 + edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge()));
5.91 }
5.92
5.93 public:
5.94
5.95 - ~UndirGraphAdaptorBase() {
5.96 + ~AlterableUndirGraphAdaptor() {
5.97 edge_notifier.clear();
5.98 }
5.99
5.100 - int maxId(typename Parent::Edge) const {
5.101 - return Parent::maxEdgeId();
5.102 - }
5.103 -
5.104 -
5.105 typedef typename Parent::UEdge UEdge;
5.106 typedef typename Parent::Edge Edge;
5.107
5.108 @@ -1142,19 +1153,20 @@
5.109
5.110 using Parent::getNotifier;
5.111
5.112 - typedef AlterationNotifier<UndirGraphAdaptorBase, Edge> EdgeNotifier;
5.113 + typedef AlterationNotifier<AlterableUndirGraphAdaptor,
5.114 + Edge> EdgeNotifier;
5.115 EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
5.116
5.117 protected:
5.118
5.119 - class NotifierProxy : public UEdgeNotifier::ObserverBase {
5.120 + class NotifierProxy : public Graph::EdgeNotifier::ObserverBase {
5.121 public:
5.122
5.123 - typedef typename UEdgeNotifier::ObserverBase Parent;
5.124 - typedef UndirGraphAdaptorBase AdaptorBase;
5.125 + typedef typename Graph::EdgeNotifier::ObserverBase Parent;
5.126 + typedef AlterableUndirGraphAdaptor AdaptorBase;
5.127
5.128 - NotifierProxy(EdgeNotifier& _edge_notifier)
5.129 - : Parent(), edge_notifier(_edge_notifier) {
5.130 + NotifierProxy(const AdaptorBase& _adaptor)
5.131 + : Parent(), adaptor(&_adaptor) {
5.132 }
5.133
5.134 virtual ~NotifierProxy() {
5.135 @@ -1163,173 +1175,70 @@
5.136 }
5.137 }
5.138
5.139 - void setUEdgeNotifier(UEdgeNotifier& _uedge_notifier) {
5.140 - Parent::attach(_uedge_notifier);
5.141 + void setNotifier(typename Graph::EdgeNotifier& notifier) {
5.142 + Parent::attach(notifier);
5.143 }
5.144
5.145
5.146 protected:
5.147
5.148 - virtual void add(const UEdge& uedge) {
5.149 + virtual void add(const GraphEdge& ge) {
5.150 std::vector<Edge> edges;
5.151 - edges.push_back(AdaptorBase::Parent::direct(uedge, true));
5.152 - edges.push_back(AdaptorBase::Parent::direct(uedge, false));
5.153 - edge_notifier.add(edges);
5.154 + edges.push_back(AdaptorBase::Parent::direct(ge, true));
5.155 + edges.push_back(AdaptorBase::Parent::direct(ge, false));
5.156 + adaptor->getNotifier(Edge()).add(edges);
5.157 }
5.158 - virtual void add(const std::vector<UEdge>& uedges) {
5.159 + virtual void add(const std::vector<GraphEdge>& ge) {
5.160 std::vector<Edge> edges;
5.161 - for (int i = 0; i < (int)uedges.size(); ++i) {
5.162 - edges.push_back(AdaptorBase::Parent::direct(uedges[i], true));
5.163 - edges.push_back(AdaptorBase::Parent::direct(uedges[i], false));
5.164 + for (int i = 0; i < (int)ge.size(); ++i) {
5.165 + edges.push_back(AdaptorBase::Parent::direct(ge[i], true));
5.166 + edges.push_back(AdaptorBase::Parent::direct(ge[i], false));
5.167 }
5.168 - edge_notifier.add(edges);
5.169 + adaptor->getNotifier(Edge()).add(edges);
5.170 }
5.171 - virtual void erase(const UEdge& uedge) {
5.172 + virtual void erase(const GraphEdge& ge) {
5.173 std::vector<Edge> edges;
5.174 - edges.push_back(AdaptorBase::Parent::direct(uedge, true));
5.175 - edges.push_back(AdaptorBase::Parent::direct(uedge, false));
5.176 - edge_notifier.erase(edges);
5.177 + edges.push_back(AdaptorBase::Parent::direct(ge, true));
5.178 + edges.push_back(AdaptorBase::Parent::direct(ge, false));
5.179 + adaptor->getNotifier(Edge()).erase(edges);
5.180 }
5.181 - virtual void erase(const std::vector<UEdge>& uedges) {
5.182 + virtual void erase(const std::vector<GraphEdge>& ge) {
5.183 std::vector<Edge> edges;
5.184 - for (int i = 0; i < (int)uedges.size(); ++i) {
5.185 - edges.push_back(AdaptorBase::Parent::direct(uedges[i], true));
5.186 - edges.push_back(AdaptorBase::Parent::direct(uedges[i], false));
5.187 + for (int i = 0; i < (int)ge.size(); ++i) {
5.188 + edges.push_back(AdaptorBase::Parent::direct(ge[i], true));
5.189 + edges.push_back(AdaptorBase::Parent::direct(ge[i], false));
5.190 }
5.191 - edge_notifier.erase(edges);
5.192 + adaptor->getNotifier(Edge()).erase(edges);
5.193 }
5.194 virtual void build() {
5.195 - edge_notifier.build();
5.196 + adaptor->getNotifier(Edge()).build();
5.197 }
5.198 virtual void clear() {
5.199 - edge_notifier.clear();
5.200 + adaptor->getNotifier(Edge()).clear();
5.201 }
5.202
5.203 - EdgeNotifier& edge_notifier;
5.204 + const AdaptorBase* adaptor;
5.205 };
5.206
5.207
5.208 mutable EdgeNotifier edge_notifier;
5.209 NotifierProxy edge_notifier_proxy;
5.210
5.211 - private:
5.212 -
5.213 - template <typename _Value>
5.214 - class EdgeMapBase {
5.215 - private:
5.216 -
5.217 - typedef typename _Graph::template EdgeMap<_Value> MapImpl;
5.218 -
5.219 - public:
5.220 -
5.221 - typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
5.222 -
5.223 - typedef _Value Value;
5.224 - typedef Edge Key;
5.225 -
5.226 - EdgeMapBase(const Adaptor& adaptor) :
5.227 - forward_map(*adaptor.graph), backward_map(*adaptor.graph) {}
5.228 -
5.229 - EdgeMapBase(const Adaptor& adaptor, const Value& v)
5.230 - : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {}
5.231 -
5.232 - void set(const Edge& e, const Value& a) {
5.233 - if (Parent::direction(e)) {
5.234 - forward_map.set(e, a);
5.235 - } else {
5.236 - backward_map.set(e, a);
5.237 - }
5.238 - }
5.239 -
5.240 - typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const {
5.241 - if (Parent::direction(e)) {
5.242 - return forward_map[e];
5.243 - } else {
5.244 - return backward_map[e];
5.245 - }
5.246 - }
5.247 -
5.248 - typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) {
5.249 - if (Parent::direction(e)) {
5.250 - return forward_map[e];
5.251 - } else {
5.252 - return backward_map[e];
5.253 - }
5.254 - }
5.255 -
5.256 - protected:
5.257 -
5.258 - MapImpl forward_map, backward_map;
5.259 -
5.260 - };
5.261 -
5.262 - public:
5.263 -
5.264 - template <typename _Value>
5.265 - class EdgeMap
5.266 - : public SubMapExtender<Adaptor, EdgeMapBase<_Value> >
5.267 - {
5.268 - public:
5.269 - typedef Adaptor Graph;
5.270 - typedef SubMapExtender<Adaptor, EdgeMapBase<_Value> > Parent;
5.271 -
5.272 - EdgeMap(const Graph& graph)
5.273 - : Parent(graph) {}
5.274 - EdgeMap(const Graph& graph, const _Value& value)
5.275 - : Parent(graph, value) {}
5.276 -
5.277 - EdgeMap& operator=(const EdgeMap& cmap) {
5.278 - return operator=<EdgeMap>(cmap);
5.279 - }
5.280 -
5.281 - template <typename CMap>
5.282 - EdgeMap& operator=(const CMap& cmap) {
5.283 - Parent::operator=(cmap);
5.284 - return *this;
5.285 - }
5.286 - };
5.287 -
5.288 - template <typename _Value>
5.289 - class UEdgeMap : public Graph::template EdgeMap<_Value> {
5.290 - public:
5.291 -
5.292 - typedef typename Graph::template EdgeMap<_Value> Parent;
5.293 -
5.294 - explicit UEdgeMap(const Adaptor& ga)
5.295 - : Parent(*ga.graph) {}
5.296 -
5.297 - UEdgeMap(const Adaptor& ga, const _Value& value)
5.298 - : Parent(*ga.graph, value) {}
5.299 -
5.300 - UEdgeMap& operator=(const UEdgeMap& cmap) {
5.301 - return operator=<UEdgeMap>(cmap);
5.302 - }
5.303 -
5.304 - template <typename CMap>
5.305 - UEdgeMap& operator=(const CMap& cmap) {
5.306 - Parent::operator=(cmap);
5.307 - return *this;
5.308 - }
5.309 -
5.310 - };
5.311 -
5.312 };
5.313
5.314 - ///\brief An undirected graph is made from a directed graph by an adaptor
5.315 - ///\ingroup graph_adaptors
5.316 +
5.317 + /// \brief An undirected graph is made from a directed graph by an adaptor
5.318 + /// \ingroup graph_adaptors
5.319 ///
5.320 /// Undocumented, untested!!!
5.321 /// If somebody knows nice demo application, let's polulate it.
5.322 ///
5.323 /// \author Marton Makai
5.324 template<typename _Graph>
5.325 - class UndirGraphAdaptor :
5.326 - public UGraphAdaptorExtender<
5.327 - UndirGraphAdaptorBase<_Graph> > {
5.328 + class UndirGraphAdaptor : public AlterableUndirGraphAdaptor<_Graph> {
5.329 public:
5.330 typedef _Graph Graph;
5.331 - typedef UGraphAdaptorExtender<
5.332 - UndirGraphAdaptorBase<_Graph> > Parent;
5.333 + typedef AlterableUndirGraphAdaptor<_Graph> Parent;
5.334 protected:
5.335 UndirGraphAdaptor() { }
5.336 public:
5.337 @@ -1694,371 +1603,977 @@
5.338
5.339 };
5.340
5.341 -// template <typename _Graph>
5.342 -// class SplitGraphAdaptorBase
5.343 -// : public GraphAdaptorBase<_Graph> {
5.344 -// public:
5.345 -// typedef GraphAdaptorBase<_Graph> Parent;
5.346 + /// \brief Base class for split graph adaptor
5.347 + ///
5.348 + /// Base class of split graph adaptor. In most case you do not need to
5.349 + /// use it directly but the documented member functions of this class can
5.350 + /// be used with the SplitGraphAdaptor class.
5.351 + /// \sa SplitGraphAdaptor
5.352 + template <typename _Graph>
5.353 + class SplitGraphAdaptorBase
5.354 + : public GraphAdaptorBase<const _Graph> {
5.355 + public:
5.356
5.357 -// class Node;
5.358 -// class Edge;
5.359 -// template <typename T> class NodeMap;
5.360 -// template <typename T> class EdgeMap;
5.361 + typedef _Graph Graph;
5.362 +
5.363 + typedef GraphAdaptorBase<const _Graph> Parent;
5.364 +
5.365 + typedef typename Graph::Node GraphNode;
5.366 + typedef typename Graph::Edge GraphEdge;
5.367 +
5.368 + class Node;
5.369 + class Edge;
5.370 +
5.371 + template <typename T> class NodeMap;
5.372 + template <typename T> class EdgeMap;
5.373
5.374
5.375 -// class Node : public Parent::Node {
5.376 -// friend class SplitGraphAdaptorBase;
5.377 -// template <typename T> friend class NodeMap;
5.378 -// typedef typename Parent::Node NodeParent;
5.379 -// private:
5.380 + class Node : public GraphNode {
5.381 + friend class SplitGraphAdaptorBase;
5.382 + template <typename T> friend class NodeMap;
5.383 + private:
5.384
5.385 -// bool entry;
5.386 -// Node(typename Parent::Node _node, bool _entry)
5.387 -// : Parent::Node(_node), entry(_entry) {}
5.388 + bool in_node;
5.389 + Node(GraphNode _node, bool _in_node)
5.390 + : GraphNode(_node), in_node(_in_node) {}
5.391
5.392 -// public:
5.393 -// Node() {}
5.394 -// Node(Invalid) : NodeParent(INVALID), entry(true) {}
5.395 + public:
5.396
5.397 -// bool operator==(const Node& node) const {
5.398 -// return NodeParent::operator==(node) && entry == node.entry;
5.399 -// }
5.400 + Node() {}
5.401 + Node(Invalid) : GraphNode(INVALID), in_node(true) {}
5.402 +
5.403 + bool operator==(const Node& node) const {
5.404 + return GraphNode::operator==(node) && in_node == node.in_node;
5.405 + }
5.406
5.407 -// bool operator!=(const Node& node) const {
5.408 -// return !(*this == node);
5.409 -// }
5.410 + bool operator!=(const Node& node) const {
5.411 + return !(*this == node);
5.412 + }
5.413
5.414 -// bool operator<(const Node& node) const {
5.415 -// return NodeParent::operator<(node) ||
5.416 -// (NodeParent::operator==(node) && entry < node.entry);
5.417 -// }
5.418 -// };
5.419 + bool operator<(const Node& node) const {
5.420 + return GraphNode::operator<(node) ||
5.421 + (GraphNode::operator==(node) && in_node < node.in_node);
5.422 + }
5.423 + };
5.424
5.425 -// /// \todo May we want VARIANT/union type
5.426 -// class Edge : public Parent::Edge {
5.427 -// friend class SplitGraphAdaptorBase;
5.428 -// template <typename T> friend class EdgeMap;
5.429 -// private:
5.430 -// typedef typename Parent::Edge EdgeParent;
5.431 -// typedef typename Parent::Node NodeParent;
5.432 -// NodeParent bind;
5.433 + class Edge {
5.434 + friend class SplitGraphAdaptorBase;
5.435 + template <typename T> friend class EdgeMap;
5.436 + private:
5.437 + typedef BiVariant<GraphEdge, GraphNode> EdgeImpl;
5.438
5.439 -// Edge(const EdgeParent& edge, const NodeParent& node)
5.440 -// : EdgeParent(edge), bind(node) {}
5.441 -// public:
5.442 -// Edge() {}
5.443 -// Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {}
5.444 + explicit Edge(const GraphEdge& edge) : item(edge) {}
5.445 + explicit Edge(const GraphNode& node) : item(node) {}
5.446 +
5.447 + EdgeImpl item;
5.448
5.449 -// bool operator==(const Edge& edge) const {
5.450 -// return EdgeParent::operator==(edge) && bind == edge.bind;
5.451 -// }
5.452 + public:
5.453 + Edge() {}
5.454 + Edge(Invalid) : item(GraphEdge(INVALID)) {}
5.455 +
5.456 + bool operator==(const Edge& edge) const {
5.457 + if (item.firstState()) {
5.458 + if (edge.item.firstState()) {
5.459 + return item.first() == edge.item.first();
5.460 + }
5.461 + } else {
5.462 + if (edge.item.secondState()) {
5.463 + return item.second() == edge.item.second();
5.464 + }
5.465 + }
5.466 + return false;
5.467 + }
5.468
5.469 -// bool operator!=(const Edge& edge) const {
5.470 -// return !(*this == edge);
5.471 -// }
5.472 + bool operator!=(const Edge& edge) const {
5.473 + return !(*this == edge);
5.474 + }
5.475
5.476 -// bool operator<(const Edge& edge) const {
5.477 -// return EdgeParent::operator<(edge) ||
5.478 -// (EdgeParent::operator==(edge) && bind < edge.bind);
5.479 -// }
5.480 -// };
5.481 + bool operator<(const Edge& edge) const {
5.482 + if (item.firstState()) {
5.483 + if (edge.item.firstState()) {
5.484 + return item.first() < edge.item.first();
5.485 + }
5.486 + return false;
5.487 + } else {
5.488 + if (edge.item.secondState()) {
5.489 + return item.second() < edge.item.second();
5.490 + }
5.491 + return true;
5.492 + }
5.493 + }
5.494
5.495 -// void first(Node& node) const {
5.496 -// Parent::first(node);
5.497 -// node.entry = true;
5.498 -// }
5.499 + operator GraphEdge() const { return item.first(); }
5.500 + operator GraphNode() const { return item.second(); }
5.501
5.502 -// void next(Node& node) const {
5.503 -// if (node.entry) {
5.504 -// node.entry = false;
5.505 -// } else {
5.506 -// node.entry = true;
5.507 -// Parent::next(node);
5.508 -// }
5.509 -// }
5.510 + };
5.511
5.512 -// void first(Edge& edge) const {
5.513 -// Parent::first(edge);
5.514 -// if ((typename Parent::Edge&)edge == INVALID) {
5.515 -// Parent::first(edge.bind);
5.516 -// } else {
5.517 -// edge.bind = INVALID;
5.518 -// }
5.519 -// }
5.520 + void first(Node& node) const {
5.521 + Parent::first(node);
5.522 + node.in_node = true;
5.523 + }
5.524
5.525 -// void next(Edge& edge) const {
5.526 -// if ((typename Parent::Edge&)edge != INVALID) {
5.527 -// Parent::next(edge);
5.528 -// if ((typename Parent::Edge&)edge == INVALID) {
5.529 -// Parent::first(edge.bind);
5.530 -// }
5.531 -// } else {
5.532 -// Parent::next(edge.bind);
5.533 -// }
5.534 -// }
5.535 + void next(Node& node) const {
5.536 + if (node.in_node) {
5.537 + node.in_node = false;
5.538 + } else {
5.539 + node.in_node = true;
5.540 + Parent::next(node);
5.541 + }
5.542 + }
5.543
5.544 -// void firstIn(Edge& edge, const Node& node) const {
5.545 -// if (node.entry) {
5.546 -// Parent::firstIn(edge, node);
5.547 -// edge.bind = INVALID;
5.548 -// } else {
5.549 -// (typename Parent::Edge&)edge = INVALID;
5.550 -// edge.bind = node;
5.551 -// }
5.552 -// }
5.553 + void first(Edge& edge) const {
5.554 + edge.item.setSecond();
5.555 + Parent::first(edge.item.second());
5.556 + if (edge.item.second() == INVALID) {
5.557 + edge.item.setFirst();
5.558 + Parent::first(edge.item.first());
5.559 + }
5.560 + }
5.561
5.562 -// void nextIn(Edge& edge) const {
5.563 -// if ((typename Parent::Edge&)edge != INVALID) {
5.564 -// Parent::nextIn(edge);
5.565 -// } else {
5.566 -// edge.bind = INVALID;
5.567 -// }
5.568 -// }
5.569 + void next(Edge& edge) const {
5.570 + if (edge.item.secondState()) {
5.571 + Parent::next(edge.item.second());
5.572 + if (edge.item.second() == INVALID) {
5.573 + edge.item.setFirst();
5.574 + Parent::first(edge.item.first());
5.575 + }
5.576 + } else {
5.577 + Parent::next(edge.item.first());
5.578 + }
5.579 + }
5.580
5.581 -// void firstOut(Edge& edge, const Node& node) const {
5.582 -// if (!node.entry) {
5.583 -// Parent::firstOut(edge, node);
5.584 -// edge.bind = INVALID;
5.585 -// } else {
5.586 -// (typename Parent::Edge&)edge = INVALID;
5.587 -// edge.bind = node;
5.588 -// }
5.589 -// }
5.590 + void firstOut(Edge& edge, const Node& node) const {
5.591 + if (node.in_node) {
5.592 + edge.item.setSecond(node);
5.593 + } else {
5.594 + edge.item.setFirst();
5.595 + Parent::firstOut(edge.item.first(), node);
5.596 + }
5.597 + }
5.598
5.599 -// void nextOut(Edge& edge) const {
5.600 -// if ((typename Parent::Edge&)edge != INVALID) {
5.601 -// Parent::nextOut(edge);
5.602 -// } else {
5.603 -// edge.bind = INVALID;
5.604 -// }
5.605 -// }
5.606 + void nextOut(Edge& edge) const {
5.607 + if (!edge.item.firstState()) {
5.608 + edge.item.setFirst(INVALID);
5.609 + } else {
5.610 + Parent::nextOut(edge.item.first());
5.611 + }
5.612 + }
5.613
5.614 -// Node source(const Edge& edge) const {
5.615 -// if ((typename Parent::Edge&)edge != INVALID) {
5.616 -// return Node(Parent::source(edge), false);
5.617 -// } else {
5.618 -// return Node(edge.bind, true);
5.619 -// }
5.620 -// }
5.621 + void firstIn(Edge& edge, const Node& node) const {
5.622 + if (!node.in_node) {
5.623 + edge.item.setSecond(node);
5.624 + } else {
5.625 + edge.item.setFirst();
5.626 + Parent::firstIn(edge.item.first(), node);
5.627 + }
5.628 + }
5.629
5.630 -// Node target(const Edge& edge) const {
5.631 -// if ((typename Parent::Edge&)edge != INVALID) {
5.632 -// return Node(Parent::target(edge), true);
5.633 -// } else {
5.634 -// return Node(edge.bind, false);
5.635 -// }
5.636 -// }
5.637 + void nextIn(Edge& edge) const {
5.638 + if (!edge.item.firstState()) {
5.639 + edge.item.setFirst(INVALID);
5.640 + } else {
5.641 + Parent::nextIn(edge.item.first());
5.642 + }
5.643 + }
5.644
5.645 -// static bool entryNode(const Node& node) {
5.646 -// return node.entry;
5.647 -// }
5.648 + Node source(const Edge& edge) const {
5.649 + if (edge.item.firstState()) {
5.650 + return Node(Parent::source(edge.item.first()), false);
5.651 + } else {
5.652 + return Node(edge.item.second(), true);
5.653 + }
5.654 + }
5.655
5.656 -// static bool exitNode(const Node& node) {
5.657 -// return !node.entry;
5.658 -// }
5.659 + Node target(const Edge& edge) const {
5.660 + if (edge.item.firstState()) {
5.661 + return Node(Parent::target(edge.item.first()), true);
5.662 + } else {
5.663 + return Node(edge.item.second(), false);
5.664 + }
5.665 + }
5.666
5.667 -// static Node getEntry(const typename Parent::Node& node) {
5.668 -// return Node(node, true);
5.669 -// }
5.670 + int id(const Node& node) const {
5.671 + return (Parent::id(node) << 1) | (node.in_node ? 0 : 1);
5.672 + }
5.673 + Node nodeFromId(int id) const {
5.674 + return Node(Parent::nodeFromId(id >> 1), (id & 1) == 0);
5.675 + }
5.676 + int maxNodeId() const {
5.677 + return 2 * Parent::maxNodeId() + 1;
5.678 + }
5.679
5.680 -// static Node getExit(const typename Parent::Node& node) {
5.681 -// return Node(node, false);
5.682 -// }
5.683 + int id(const Edge& edge) const {
5.684 + if (edge.item.firstState()) {
5.685 + return Parent::id(edge.item.first()) << 1;
5.686 + } else {
5.687 + return (Parent::id(edge.item.second()) << 1) | 1;
5.688 + }
5.689 + }
5.690 + Edge edgeFromId(int id) const {
5.691 + if ((id & 1) == 0) {
5.692 + return Edge(Parent::edgeFromId(id >> 1));
5.693 + } else {
5.694 + return Edge(Parent::nodeFromId(id >> 1));
5.695 + }
5.696 + }
5.697 + int maxEdgeId() const {
5.698 + return std::max(Parent::maxNodeId() << 1,
5.699 + (Parent::maxEdgeId() << 1) | 1);
5.700 + }
5.701
5.702 -// static bool originalEdge(const Edge& edge) {
5.703 -// return (typename Parent::Edge&)edge != INVALID;
5.704 -// }
5.705 + /// \brief Returns true when the node is in-node.
5.706 + ///
5.707 + /// Returns true when the node is in-node.
5.708 + static bool inNode(const Node& node) {
5.709 + return node.in_node;
5.710 + }
5.711
5.712 -// static bool bindingEdge(const Edge& edge) {
5.713 -// return edge.bind != INVALID;
5.714 -// }
5.715 + /// \brief Returns true when the node is out-node.
5.716 + ///
5.717 + /// Returns true when the node is out-node.
5.718 + static bool outNode(const Node& node) {
5.719 + return !node.in_node;
5.720 + }
5.721
5.722 -// static Node getBindedNode(const Edge& edge) {
5.723 -// return edge.bind;
5.724 -// }
5.725 + /// \brief Returns true when the edge is edge in the original graph.
5.726 + ///
5.727 + /// Returns true when the edge is edge in the original graph.
5.728 + static bool origEdge(const Edge& edge) {
5.729 + return edge.item.firstState();
5.730 + }
5.731
5.732 -// int nodeNum() const {
5.733 -// return Parent::nodeNum() * 2;
5.734 -// }
5.735 + /// \brief Returns true when the edge binds an in-node and an out-node.
5.736 + ///
5.737 + /// Returns true when the edge binds an in-node and an out-node.
5.738 + static bool bindEdge(const Edge& edge) {
5.739 + return edge.item.secondState();
5.740 + }
5.741
5.742 -// typedef True EdgeNumTag;
5.743 + /// \brief Gives back the in-node created from the \c node.
5.744 + ///
5.745 + /// Gives back the in-node created from the \c node.
5.746 + static Node inNode(const GraphNode& node) {
5.747 + return Node(node, true);
5.748 + }
5.749 +
5.750 + /// \brief Gives back the out-node created from the \c node.
5.751 + ///
5.752 + /// Gives back the out-node created from the \c node.
5.753 + static Node outNode(const GraphNode& node) {
5.754 + return Node(node, false);
5.755 + }
5.756 +
5.757 + /// \brief Gives back the edge binds the two part of the node.
5.758 + ///
5.759 + /// Gives back the edge binds the two part of the node.
5.760 + static Edge edge(const GraphNode& node) {
5.761 + return Edge(node);
5.762 + }
5.763 +
5.764 + /// \brief Gives back the edge of the original edge.
5.765 + ///
5.766 + /// Gives back the edge of the original edge.
5.767 + static Edge edge(const GraphEdge& edge) {
5.768 + return Edge(edge);
5.769 + }
5.770 +
5.771 + typedef True NodeNumTag;
5.772 +
5.773 + int nodeNum() const {
5.774 + return 2 * countNodes(*Parent::graph);
5.775 + }
5.776 +
5.777 + typedef True EdgeNumTag;
5.778
5.779 -// int edgeNum() const {
5.780 -// return countEdges() + Parent::nodeNum();
5.781 -// }
5.782 + int edgeNum() const {
5.783 + return countEdges(*Parent::graph) + countNodes(*Parent::graph);
5.784 + }
5.785
5.786 -// Edge findEdge(const Node& source, const Node& target,
5.787 -// const Edge& prev = INVALID) const {
5.788 -// if (exitNode(source) && entryNode(target)) {
5.789 -// return Parent::findEdge(source, target, prev);
5.790 -// } else {
5.791 -// if (prev == INVALID && entryNode(source) && exitNode(target) &&
5.792 -// (typename Parent::Node&)source == (typename Parent::Node&)target) {
5.793 -// return Edge(INVALID, source);
5.794 -// } else {
5.795 -// return INVALID;
5.796 -// }
5.797 -// }
5.798 -// }
5.799 + typedef True FindEdgeTag;
5.800 +
5.801 + Edge findEdge(const Node& source, const Node& target,
5.802 + const Edge& prev = INVALID) const {
5.803 + if (inNode(source)) {
5.804 + if (outNode(target)) {
5.805 + if ((GraphNode&)source == (GraphNode&)target && prev == INVALID) {
5.806 + return Edge(source);
5.807 + }
5.808 + }
5.809 + } else {
5.810 + if (inNode(target)) {
5.811 + return Edge(findEdge(*Parent::graph, source, target, prev));
5.812 + }
5.813 + }
5.814 + return INVALID;
5.815 + }
5.816
5.817 -// template <typename T>
5.818 -// class NodeMap : public MapBase<Node, T> {
5.819 -// typedef typename Parent::template NodeMap<T> NodeImpl;
5.820 -// public:
5.821 -// NodeMap(const SplitGraphAdaptorBase& _graph)
5.822 -// : entry(_graph), exit(_graph) {}
5.823 -// NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
5.824 -// : entry(_graph, t), exit(_graph, t) {}
5.825 + template <typename T>
5.826 + class NodeMap : public MapBase<Node, T> {
5.827 + typedef typename Parent::template NodeMap<T> NodeImpl;
5.828 + public:
5.829 + NodeMap(const SplitGraphAdaptorBase& _graph)
5.830 + : inNodeMap(_graph), outNodeMap(_graph) {}
5.831 + NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
5.832 + : inNodeMap(_graph, t), outNodeMap(_graph, t) {}
5.833
5.834 -// void set(const Node& key, const T& val) {
5.835 -// if (key.entry) { entry.set(key, val); }
5.836 -// else {exit.set(key, val); }
5.837 -// }
5.838 + void set(const Node& key, const T& val) {
5.839 + if (SplitGraphAdaptorBase::inNode(key)) { inNodeMap.set(key, val); }
5.840 + else {outNodeMap.set(key, val); }
5.841 + }
5.842
5.843 -// typename MapTraits<NodeImpl>::ReturnValue
5.844 -// operator[](const Node& key) {
5.845 -// if (key.entry) { return entry[key]; }
5.846 -// else { return exit[key]; }
5.847 -// }
5.848 + typename MapTraits<NodeImpl>::ReturnValue
5.849 + operator[](const Node& key) {
5.850 + if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
5.851 + else { return outNodeMap[key]; }
5.852 + }
5.853
5.854 -// typename MapTraits<NodeImpl>::ConstReturnValue
5.855 -// operator[](const Node& key) const {
5.856 -// if (key.entry) { return entry[key]; }
5.857 -// else { return exit[key]; }
5.858 -// }
5.859 + typename MapTraits<NodeImpl>::ConstReturnValue
5.860 + operator[](const Node& key) const {
5.861 + if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
5.862 + else { return outNodeMap[key]; }
5.863 + }
5.864
5.865 -// private:
5.866 -// NodeImpl entry, exit;
5.867 -// };
5.868 + private:
5.869 + NodeImpl inNodeMap, outNodeMap;
5.870 + };
5.871
5.872 -// template <typename T>
5.873 -// class EdgeMap : public MapBase<Edge, T> {
5.874 -// typedef typename Parent::template NodeMap<T> NodeImpl;
5.875 -// typedef typename Parent::template EdgeMap<T> EdgeImpl;
5.876 -// public:
5.877 -// EdgeMap(const SplitGraphAdaptorBase& _graph)
5.878 -// : bind(_graph), orig(_graph) {}
5.879 -// EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
5.880 -// : bind(_graph, t), orig(_graph, t) {}
5.881 + template <typename T>
5.882 + class EdgeMap : public MapBase<Edge, T> {
5.883 + typedef typename Parent::template EdgeMap<T> EdgeMapImpl;
5.884 + typedef typename Parent::template NodeMap<T> NodeMapImpl;
5.885 + public:
5.886 +
5.887 + EdgeMap(const SplitGraphAdaptorBase& _graph)
5.888 + : edge_map(_graph), node_map(_graph) {}
5.889 + EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
5.890 + : edge_map(_graph, t), node_map(_graph, t) {}
5.891
5.892 -// void set(const Edge& key, const T& val) {
5.893 -// if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); }
5.894 -// else {bind.set(key.bind, val); }
5.895 -// }
5.896 + void set(const Edge& key, const T& val) {
5.897 + if (SplitGraphAdaptorBase::origEdge(key)) {
5.898 + edge_map.set(key.item.first(), val);
5.899 + } else {
5.900 + node_map.set(key.item.second(), val);
5.901 + }
5.902 + }
5.903
5.904 -// typename MapTraits<EdgeImpl>::ReturnValue
5.905 -// operator[](const Edge& key) {
5.906 -// if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
5.907 -// else {return bind[key.bind]; }
5.908 -// }
5.909 + typename MapTraits<EdgeMapImpl>::ReturnValue
5.910 + operator[](const Edge& key) {
5.911 + if (SplitGraphAdaptorBase::origEdge(key)) {
5.912 + return edge_map[key.item.first()];
5.913 + } else {
5.914 + return node_map[key.item.second()];
5.915 + }
5.916 + }
5.917
5.918 -// typename MapTraits<EdgeImpl>::ConstReturnValue
5.919 -// operator[](const Edge& key) const {
5.920 -// if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
5.921 -// else {return bind[key.bind]; }
5.922 -// }
5.923 + typename MapTraits<EdgeMapImpl>::ConstReturnValue
5.924 + operator[](const Edge& key) const {
5.925 + if (SplitGraphAdaptorBase::origEdge(key)) {
5.926 + return edge_map[key.item.first()];
5.927 + } else {
5.928 + return node_map[key.item.second()];
5.929 + }
5.930 + }
5.931
5.932 -// private:
5.933 -// typename Parent::template NodeMap<T> bind;
5.934 -// typename Parent::template EdgeMap<T> orig;
5.935 -// };
5.936 + private:
5.937 + typename Parent::template EdgeMap<T> edge_map;
5.938 + typename Parent::template NodeMap<T> node_map;
5.939 + };
5.940
5.941 -// template <typename EntryMap, typename ExitMap>
5.942 -// class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> {
5.943 -// public:
5.944 -// typedef MapBase<Node, typename EntryMap::Value> Parent;
5.945
5.946 -// typedef typename Parent::Key Key;
5.947 -// typedef typename Parent::Value Value;
5.948 + };
5.949
5.950 -// CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap)
5.951 -// : entryMap(_entryMap), exitMap(_exitMap) {}
5.952 + template <typename _Graph, typename NodeEnable = void,
5.953 + typename EdgeEnable = void>
5.954 + class AlterableSplitGraphAdaptor
5.955 + : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
5.956 + public:
5.957
5.958 -// Value& operator[](const Key& key) {
5.959 -// if (key.entry) {
5.960 -// return entryMap[key];
5.961 -// } else {
5.962 -// return exitMap[key];
5.963 -// }
5.964 -// }
5.965 + typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
5.966 + typedef _Graph Graph;
5.967
5.968 -// Value operator[](const Key& key) const {
5.969 -// if (key.entry) {
5.970 -// return entryMap[key];
5.971 -// } else {
5.972 -// return exitMap[key];
5.973 -// }
5.974 -// }
5.975 + typedef typename Graph::Node GraphNode;
5.976 + typedef typename Graph::Node GraphEdge;
5.977
5.978 -// void set(const Key& key, const Value& value) {
5.979 -// if (key.entry) {
5.980 -// entryMap.set(key, value);
5.981 -// } else {
5.982 -// exitMap.set(key, value);
5.983 -// }
5.984 -// }
5.985 + protected:
5.986 +
5.987 + AlterableSplitGraphAdaptor() : Parent() {}
5.988 +
5.989 + public:
5.990 +
5.991 + typedef InvalidType NodeNotifier;
5.992 + typedef InvalidType EdgeNotifier;
5.993 +
5.994 + };
5.995 +
5.996 + template <typename _Graph, typename EdgeEnable>
5.997 + class AlterableSplitGraphAdaptor<
5.998 + _Graph,
5.999 + typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
5.1000 + EdgeEnable>
5.1001 + : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
5.1002 + public:
5.1003 +
5.1004 + typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
5.1005 + typedef _Graph Graph;
5.1006 +
5.1007 + typedef typename Graph::Node GraphNode;
5.1008 + typedef typename Graph::Edge GraphEdge;
5.1009 +
5.1010 + typedef typename Parent::Node Node;
5.1011 + typedef typename Parent::Edge Edge;
5.1012 +
5.1013 + protected:
5.1014 +
5.1015 + AlterableSplitGraphAdaptor()
5.1016 + : Parent(), node_notifier(*this), node_notifier_proxy(*this) {}
5.1017 +
5.1018 + void setGraph(_Graph& graph) {
5.1019 + Parent::setGraph(graph);
5.1020 + node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode()));
5.1021 + }
5.1022 +
5.1023 + public:
5.1024 +
5.1025 + ~AlterableSplitGraphAdaptor() {
5.1026 + node_notifier.clear();
5.1027 + }
5.1028 +
5.1029 + typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
5.1030 + typedef InvalidType EdgeNotifier;
5.1031 +
5.1032 + NodeNotifier& getNotifier(Node) const { return node_notifier; }
5.1033 +
5.1034 + protected:
5.1035 +
5.1036 + class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
5.1037 + public:
5.1038 +
5.1039 + typedef typename Graph::NodeNotifier::ObserverBase Parent;
5.1040 + typedef AlterableSplitGraphAdaptor AdaptorBase;
5.1041
5.1042 -// private:
5.1043 + NodeNotifierProxy(const AdaptorBase& _adaptor)
5.1044 + : Parent(), adaptor(&_adaptor) {
5.1045 + }
5.1046 +
5.1047 + virtual ~NodeNotifierProxy() {
5.1048 + if (Parent::attached()) {
5.1049 + Parent::detach();
5.1050 + }
5.1051 + }
5.1052 +
5.1053 + void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
5.1054 + Parent::attach(graph_notifier);
5.1055 + }
5.1056 +
5.1057
5.1058 -// EntryMap& entryMap;
5.1059 -// ExitMap& exitMap;
5.1060 + protected:
5.1061 +
5.1062 + virtual void add(const GraphNode& gn) {
5.1063 + std::vector<Node> nodes;
5.1064 + nodes.push_back(AdaptorBase::Parent::inNode(gn));
5.1065 + nodes.push_back(AdaptorBase::Parent::outNode(gn));
5.1066 + adaptor->getNotifier(Node()).add(nodes);
5.1067 + }
5.1068 +
5.1069 + virtual void add(const std::vector<GraphNode>& gn) {
5.1070 + std::vector<Node> nodes;
5.1071 + for (int i = 0; i < (int)gn.size(); ++i) {
5.1072 + nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
5.1073 + nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
5.1074 + }
5.1075 + adaptor->getNotifier(Node()).add(nodes);
5.1076 + }
5.1077 +
5.1078 + virtual void erase(const GraphNode& gn) {
5.1079 + std::vector<Node> nodes;
5.1080 + nodes.push_back(AdaptorBase::Parent::inNode(gn));
5.1081 + nodes.push_back(AdaptorBase::Parent::outNode(gn));
5.1082 + adaptor->getNotifier(Node()).erase(nodes);
5.1083 + }
5.1084 +
5.1085 + virtual void erase(const std::vector<GraphNode>& gn) {
5.1086 + std::vector<Node> nodes;
5.1087 + for (int i = 0; i < (int)gn.size(); ++i) {
5.1088 + nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
5.1089 + nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
5.1090 + }
5.1091 + adaptor->getNotifier(Node()).erase(nodes);
5.1092 + }
5.1093 + virtual void build() {
5.1094 + adaptor->getNotifier(Node()).build();
5.1095 + }
5.1096 + virtual void clear() {
5.1097 + adaptor->getNotifier(Node()).clear();
5.1098 + }
5.1099 +
5.1100 + const AdaptorBase* adaptor;
5.1101 + };
5.1102 +
5.1103 +
5.1104 + mutable NodeNotifier node_notifier;
5.1105 +
5.1106 + NodeNotifierProxy node_notifier_proxy;
5.1107 +
5.1108 + };
5.1109 +
5.1110 + template <typename _Graph>
5.1111 + class AlterableSplitGraphAdaptor<
5.1112 + _Graph,
5.1113 + typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
5.1114 + typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type>
5.1115 + : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
5.1116 + public:
5.1117 +
5.1118 + typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
5.1119 + typedef _Graph Graph;
5.1120 +
5.1121 + typedef typename Graph::Node GraphNode;
5.1122 + typedef typename Graph::Edge GraphEdge;
5.1123 +
5.1124 + typedef typename Parent::Node Node;
5.1125 + typedef typename Parent::Edge Edge;
5.1126 +
5.1127 + protected:
5.1128 +
5.1129 + AlterableSplitGraphAdaptor()
5.1130 + : Parent(), node_notifier(*this), edge_notifier(*this),
5.1131 + node_notifier_proxy(*this), edge_notifier_proxy(*this) {}
5.1132 +
5.1133 + void setGraph(_Graph& graph) {
5.1134 + Parent::setGraph(graph);
5.1135 + node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode()));
5.1136 + edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge()));
5.1137 + }
5.1138 +
5.1139 + public:
5.1140 +
5.1141 + ~AlterableSplitGraphAdaptor() {
5.1142 + node_notifier.clear();
5.1143 + edge_notifier.clear();
5.1144 + }
5.1145 +
5.1146 + typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
5.1147 + typedef AlterationNotifier<AlterableSplitGraphAdaptor, Edge> EdgeNotifier;
5.1148 +
5.1149 + NodeNotifier& getNotifier(Node) const { return node_notifier; }
5.1150 + EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
5.1151 +
5.1152 + protected:
5.1153 +
5.1154 + class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
5.1155 + public:
5.1156
5.1157 -// };
5.1158 + typedef typename Graph::NodeNotifier::ObserverBase Parent;
5.1159 + typedef AlterableSplitGraphAdaptor AdaptorBase;
5.1160 +
5.1161 + NodeNotifierProxy(const AdaptorBase& _adaptor)
5.1162 + : Parent(), adaptor(&_adaptor) {
5.1163 + }
5.1164
5.1165 -// template <typename EdgeMap, typename NodeMap>
5.1166 -// class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> {
5.1167 -// public:
5.1168 -// typedef MapBase<Edge, typename EdgeMap::Value> Parent;
5.1169 + virtual ~NodeNotifierProxy() {
5.1170 + if (Parent::attached()) {
5.1171 + Parent::detach();
5.1172 + }
5.1173 + }
5.1174
5.1175 -// typedef typename Parent::Key Key;
5.1176 -// typedef typename Parent::Value Value;
5.1177 + void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
5.1178 + Parent::attach(graph_notifier);
5.1179 + }
5.1180
5.1181 -// CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap)
5.1182 -// : edgeMap(_edgeMap), nodeMap(_nodeMap) {}
5.1183 +
5.1184 + protected:
5.1185
5.1186 -// void set(const Edge& edge, const Value& val) {
5.1187 -// if (SplitGraphAdaptorBase::originalEdge(edge)) {
5.1188 -// edgeMap.set(edge, val);
5.1189 -// } else {
5.1190 -// nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val);
5.1191 -// }
5.1192 -// }
5.1193 + virtual void add(const GraphNode& gn) {
5.1194 + std::vector<Node> nodes;
5.1195 + nodes.push_back(AdaptorBase::Parent::inNode(gn));
5.1196 + nodes.push_back(AdaptorBase::Parent::outNode(gn));
5.1197 + adaptor->getNotifier(Node()).add(nodes);
5.1198 + adaptor->getNotifier(Edge()).add(AdaptorBase::Parent::edge(gn));
5.1199 + }
5.1200 + virtual void add(const std::vector<GraphNode>& gn) {
5.1201 + std::vector<Node> nodes;
5.1202 + std::vector<Edge> edges;
5.1203 + for (int i = 0; i < (int)gn.size(); ++i) {
5.1204 + edges.push_back(AdaptorBase::Parent::edge(gn[i]));
5.1205 + nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
5.1206 + nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
5.1207 + }
5.1208 + adaptor->getNotifier(Node()).add(nodes);
5.1209 + adaptor->getNotifier(Edge()).add(edges);
5.1210 + }
5.1211 + virtual void erase(const GraphNode& gn) {
5.1212 + adaptor->getNotifier(Edge()).erase(AdaptorBase::Parent::edge(gn));
5.1213 + std::vector<Node> nodes;
5.1214 + nodes.push_back(AdaptorBase::Parent::inNode(gn));
5.1215 + nodes.push_back(AdaptorBase::Parent::outNode(gn));
5.1216 + adaptor->getNotifier(Node()).erase(nodes);
5.1217 + }
5.1218 + virtual void erase(const std::vector<GraphNode>& gn) {
5.1219 + std::vector<Node> nodes;
5.1220 + std::vector<Edge> edges;
5.1221 + for (int i = 0; i < (int)gn.size(); ++i) {
5.1222 + edges.push_back(AdaptorBase::Parent::edge(gn[i]));
5.1223 + nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
5.1224 + nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
5.1225 + }
5.1226 + adaptor->getNotifier(Edge()).erase(edges);
5.1227 + adaptor->getNotifier(Node()).erase(nodes);
5.1228 + }
5.1229 + virtual void build() {
5.1230 + std::vector<Edge> edges;
5.1231 + const typename Parent::Notifier* notifier = Parent::getNotifier();
5.1232 + GraphNode it;
5.1233 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
5.1234 + edges.push_back(AdaptorBase::Parent::edge(it));
5.1235 + }
5.1236 + adaptor->getNotifier(Node()).build();
5.1237 + adaptor->getNotifier(Edge()).add(edges);
5.1238 + }
5.1239 + virtual void clear() {
5.1240 + std::vector<Edge> edges;
5.1241 + const typename Parent::Notifier* notifier = Parent::getNotifier();
5.1242 + GraphNode it;
5.1243 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
5.1244 + edges.push_back(AdaptorBase::Parent::edge(it));
5.1245 + }
5.1246 + adaptor->getNotifier(Edge()).erase(edges);
5.1247 + adaptor->getNotifier(Node()).clear();
5.1248 + }
5.1249
5.1250 -// Value operator[](const Key& edge) const {
5.1251 -// if (SplitGraphAdaptorBase::originalEdge(edge)) {
5.1252 -// return edgeMap[edge];
5.1253 -// } else {
5.1254 -// return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
5.1255 -// }
5.1256 -// }
5.1257 + const AdaptorBase* adaptor;
5.1258 + };
5.1259
5.1260 -// Value& operator[](const Key& edge) {
5.1261 -// if (SplitGraphAdaptorBase::originalEdge(edge)) {
5.1262 -// return edgeMap[edge];
5.1263 -// } else {
5.1264 -// return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
5.1265 -// }
5.1266 -// }
5.1267 + class EdgeNotifierProxy : public Graph::EdgeNotifier::ObserverBase {
5.1268 + public:
5.1269 +
5.1270 + typedef typename Graph::EdgeNotifier::ObserverBase Parent;
5.1271 + typedef AlterableSplitGraphAdaptor AdaptorBase;
5.1272
5.1273 -// private:
5.1274 -// EdgeMap& edgeMap;
5.1275 -// NodeMap& nodeMap;
5.1276 -// };
5.1277 + EdgeNotifierProxy(const AdaptorBase& _adaptor)
5.1278 + : Parent(), adaptor(&_adaptor) {
5.1279 + }
5.1280
5.1281 -// };
5.1282 + virtual ~EdgeNotifierProxy() {
5.1283 + if (Parent::attached()) {
5.1284 + Parent::detach();
5.1285 + }
5.1286 + }
5.1287
5.1288 -// template <typename _Graph>
5.1289 -// class SplitGraphAdaptor
5.1290 -// : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
5.1291 -// public:
5.1292 -// typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
5.1293 + void setNotifier(typename Graph::EdgeNotifier& graph_notifier) {
5.1294 + Parent::attach(graph_notifier);
5.1295 + }
5.1296
5.1297 -// SplitGraphAdaptor(_Graph& graph) {
5.1298 -// Parent::setGraph(graph);
5.1299 -// }
5.1300 +
5.1301 + protected:
5.1302
5.1303 + virtual void add(const GraphEdge& ge) {
5.1304 + adaptor->getNotifier(Edge()).add(AdaptorBase::edge(ge));
5.1305 + }
5.1306 + virtual void add(const std::vector<GraphEdge>& ge) {
5.1307 + std::vector<Edge> edges;
5.1308 + for (int i = 0; i < (int)ge.size(); ++i) {
5.1309 + edges.push_back(AdaptorBase::edge(ge[i]));
5.1310 + }
5.1311 + adaptor->getNotifier(Edge()).add(edges);
5.1312 + }
5.1313 + virtual void erase(const GraphEdge& ge) {
5.1314 + adaptor->getNotifier(Edge()).erase(AdaptorBase::edge(ge));
5.1315 + }
5.1316 + virtual void erase(const std::vector<GraphEdge>& ge) {
5.1317 + std::vector<Edge> edges;
5.1318 + for (int i = 0; i < (int)ge.size(); ++i) {
5.1319 + edges.push_back(AdaptorBase::edge(ge[i]));
5.1320 + }
5.1321 + adaptor->getNotifier(Edge()).erase(edges);
5.1322 + }
5.1323 + virtual void build() {
5.1324 + std::vector<Edge> edges;
5.1325 + const typename Parent::Notifier* notifier = Parent::getNotifier();
5.1326 + GraphEdge it;
5.1327 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
5.1328 + edges.push_back(AdaptorBase::Parent::edge(it));
5.1329 + }
5.1330 + adaptor->getNotifier(Edge()).add(edges);
5.1331 + }
5.1332 + virtual void clear() {
5.1333 + std::vector<Edge> edges;
5.1334 + const typename Parent::Notifier* notifier = Parent::getNotifier();
5.1335 + GraphEdge it;
5.1336 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
5.1337 + edges.push_back(AdaptorBase::Parent::edge(it));
5.1338 + }
5.1339 + adaptor->getNotifier(Edge()).erase(edges);
5.1340 + }
5.1341
5.1342 -// };
5.1343 + const AdaptorBase* adaptor;
5.1344 + };
5.1345 +
5.1346 +
5.1347 + mutable NodeNotifier node_notifier;
5.1348 + mutable EdgeNotifier edge_notifier;
5.1349 +
5.1350 + NodeNotifierProxy node_notifier_proxy;
5.1351 + EdgeNotifierProxy edge_notifier_proxy;
5.1352 +
5.1353 + };
5.1354 +
5.1355 + /// \ingroup graph_adaptors
5.1356 + ///
5.1357 + /// \brief SplitGraphAdaptor class
5.1358 + ///
5.1359 + /// This is an graph adaptor which splits all node into an in-node
5.1360 + /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$
5.1361 + /// node in the graph with two node, \f$ u_{in} \f$ node and
5.1362 + /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ edge in the
5.1363 + /// original graph the new target of the edge will be \f$ u_{in} \f$ and
5.1364 + /// similarly the source of the original \f$ (u, v) \f$ edge will be
5.1365 + /// \f$ u_{out} \f$. The adaptor will add for each node in the
5.1366 + /// original graph an additional edge which will connect
5.1367 + /// \f$ (u_{in}, u_{out}) \f$.
5.1368 + ///
5.1369 + /// The aim of this class is to run algorithm with node costs if the
5.1370 + /// algorithm can use directly just edge costs. In this case we should use
5.1371 + /// a \c SplitGraphAdaptor and set the node cost of the graph to the
5.1372 + /// bind edge in the adapted graph.
5.1373 + ///
5.1374 + /// By example a maximum flow algoritm can compute how many edge
5.1375 + /// disjoint paths are in the graph. But we would like to know how
5.1376 + /// many node disjoint paths are in the graph. First we have to
5.1377 + /// adapt the graph with the \c SplitGraphAdaptor. Then run the flow
5.1378 + /// algorithm on the adapted graph. The bottleneck of the flow will
5.1379 + /// be the bind edges which bounds the flow with the count of the
5.1380 + /// node disjoint paths.
5.1381 + ///
5.1382 + ///\code
5.1383 + ///
5.1384 + /// typedef SplitGraphAdaptor<SmartGraph> SGraph;
5.1385 + ///
5.1386 + /// SGraph sgraph(graph);
5.1387 + ///
5.1388 + /// typedef ConstMap<SGraph::Edge, int> SCapacity;
5.1389 + /// SCapacity scapacity(1);
5.1390 + ///
5.1391 + /// SGraph::EdgeMap<int> sflow(sgraph);
5.1392 + ///
5.1393 + /// Preflow<SGraph, int, SCapacity>
5.1394 + /// spreflow(sgraph, SGraph::outNode(source),SGraph::inNode(target),
5.1395 + /// scapacity, sflow);
5.1396 + ///
5.1397 + /// spreflow.run();
5.1398 + ///
5.1399 + ///\endcode
5.1400 + ///
5.1401 + /// The result of the mamixum flow on the original graph
5.1402 + /// shows the next figure:
5.1403 + ///
5.1404 + /// \image html edge_disjoint.png
5.1405 + /// \image latex edge_disjoint.eps "Edge disjoint paths" width=\textwidth
5.1406 + ///
5.1407 + /// And the maximum flow on the adapted graph:
5.1408 + ///
5.1409 + /// \image html node_disjoint.png
5.1410 + /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth
5.1411 + ///
5.1412 + /// The second solution contains just 3 disjoint paths while the first 4.
5.1413 + ///
5.1414 + /// This graph adaptor is fully conform to the
5.1415 + /// \ref concept::StaticGraph "StaticGraph" concept and
5.1416 + /// contains some additional member functions and types. The
5.1417 + /// documentation of some member functions may be found just in the
5.1418 + /// SplitGraphAdaptorBase class.
5.1419 + ///
5.1420 + /// \sa SplitGraphAdaptorBase
5.1421 + template <typename _Graph>
5.1422 + class SplitGraphAdaptor : public AlterableSplitGraphAdaptor<_Graph> {
5.1423 + public:
5.1424 + typedef AlterableSplitGraphAdaptor<_Graph> Parent;
5.1425 +
5.1426 + typedef typename Parent::Node Node;
5.1427 + typedef typename Parent::Edge Edge;
5.1428 +
5.1429 + /// \brief Constructor of the adaptor.
5.1430 + ///
5.1431 + /// Constructor of the adaptor.
5.1432 + SplitGraphAdaptor(_Graph& graph) {
5.1433 + Parent::setGraph(graph);
5.1434 + }
5.1435 +
5.1436 + /// \brief NodeMap combined from two original NodeMap
5.1437 + ///
5.1438 + /// This class adapt two of the original graph NodeMap to
5.1439 + /// get a node map on the adapted graph.
5.1440 + template <typename InNodeMap, typename OutNodeMap>
5.1441 + class CombinedNodeMap {
5.1442 + public:
5.1443 +
5.1444 + typedef Node Key;
5.1445 + typedef typename InNodeMap::Value Value;
5.1446 +
5.1447 + /// \brief Constructor
5.1448 + ///
5.1449 + /// Constructor.
5.1450 + CombinedNodeMap(InNodeMap& _inNodeMap, OutNodeMap& _outNodeMap)
5.1451 + : inNodeMap(_inNodeMap), outNodeMap(_outNodeMap) {}
5.1452 +
5.1453 + /// \brief The subscript operator.
5.1454 + ///
5.1455 + /// The subscript operator.
5.1456 + Value& operator[](const Key& key) {
5.1457 + if (Parent::inNode(key)) {
5.1458 + return inNodeMap[key];
5.1459 + } else {
5.1460 + return outNodeMap[key];
5.1461 + }
5.1462 + }
5.1463 +
5.1464 + /// \brief The const subscript operator.
5.1465 + ///
5.1466 + /// The const subscript operator.
5.1467 + Value operator[](const Key& key) const {
5.1468 + if (Parent::inNode(key)) {
5.1469 + return inNodeMap[key];
5.1470 + } else {
5.1471 + return outNodeMap[key];
5.1472 + }
5.1473 + }
5.1474 +
5.1475 + /// \brief The setter function of the map.
5.1476 + ///
5.1477 + /// The setter function of the map.
5.1478 + void set(const Key& key, const Value& value) {
5.1479 + if (Parent::inNode(key)) {
5.1480 + inNodeMap.set(key, value);
5.1481 + } else {
5.1482 + outNodeMap.set(key, value);
5.1483 + }
5.1484 + }
5.1485 +
5.1486 + private:
5.1487 +
5.1488 + InNodeMap& inNodeMap;
5.1489 + OutNodeMap& outNodeMap;
5.1490 +
5.1491 + };
5.1492 +
5.1493 +
5.1494 + /// \brief Just gives back a combined node map.
5.1495 + ///
5.1496 + /// Just gives back a combined node map.
5.1497 + template <typename InNodeMap, typename OutNodeMap>
5.1498 + static CombinedNodeMap<InNodeMap, OutNodeMap>
5.1499 + combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
5.1500 + return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
5.1501 + }
5.1502 +
5.1503 + template <typename InNodeMap, typename OutNodeMap>
5.1504 + static CombinedNodeMap<const InNodeMap, OutNodeMap>
5.1505 + combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
5.1506 + return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
5.1507 + }
5.1508 +
5.1509 + template <typename InNodeMap, typename OutNodeMap>
5.1510 + static CombinedNodeMap<InNodeMap, const OutNodeMap>
5.1511 + combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
5.1512 + return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
5.1513 + }
5.1514 +
5.1515 + template <typename InNodeMap, typename OutNodeMap>
5.1516 + static CombinedNodeMap<const InNodeMap, const OutNodeMap>
5.1517 + combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
5.1518 + return CombinedNodeMap<const InNodeMap,
5.1519 + const OutNodeMap>(in_map, out_map);
5.1520 + }
5.1521 +
5.1522 + /// \brief EdgeMap combined from an original EdgeMap and NodeMap
5.1523 + ///
5.1524 + /// This class adapt an original graph EdgeMap and NodeMap to
5.1525 + /// get an edge map on the adapted graph.
5.1526 + template <typename GraphEdgeMap, typename GraphNodeMap>
5.1527 + class CombinedEdgeMap
5.1528 + : public MapBase<Edge, typename GraphEdgeMap::Value> {
5.1529 + public:
5.1530 + typedef MapBase<Edge, typename GraphEdgeMap::Value> Parent;
5.1531 +
5.1532 + typedef typename Parent::Key Key;
5.1533 + typedef typename Parent::Value Value;
5.1534 +
5.1535 + /// \brief Constructor
5.1536 + ///
5.1537 + /// Constructor.
5.1538 + CombinedEdgeMap(GraphEdgeMap& _edge_map, GraphNodeMap& _node_map)
5.1539 + : edge_map(_edge_map), node_map(_node_map) {}
5.1540 +
5.1541 + /// \brief The subscript operator.
5.1542 + ///
5.1543 + /// The subscript operator.
5.1544 + void set(const Edge& edge, const Value& val) {
5.1545 + if (Parent::origEdge(edge)) {
5.1546 + edge_map.set(edge, val);
5.1547 + } else {
5.1548 + node_map.set(edge, val);
5.1549 + }
5.1550 + }
5.1551 +
5.1552 + /// \brief The const subscript operator.
5.1553 + ///
5.1554 + /// The const subscript operator.
5.1555 + Value operator[](const Key& edge) const {
5.1556 + if (Parent::origEdge(edge)) {
5.1557 + return edge_map[edge];
5.1558 + } else {
5.1559 + return node_map[edge];
5.1560 + }
5.1561 + }
5.1562 +
5.1563 + /// \brief The const subscript operator.
5.1564 + ///
5.1565 + /// The const subscript operator.
5.1566 + Value& operator[](const Key& edge) {
5.1567 + if (Parent::origEdge(edge)) {
5.1568 + return edge_map[edge];
5.1569 + } else {
5.1570 + return node_map[edge];
5.1571 + }
5.1572 + }
5.1573 +
5.1574 + private:
5.1575 + GraphEdgeMap& edge_map;
5.1576 + GraphNodeMap& node_map;
5.1577 + };
5.1578 +
5.1579 + /// \brief Just gives back a combined edge map.
5.1580 + ///
5.1581 + /// Just gives back a combined edge map.
5.1582 + template <typename GraphEdgeMap, typename GraphNodeMap>
5.1583 + static CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>
5.1584 + combinedEdgeMap(GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
5.1585 + return CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>(edge_map, node_map);
5.1586 + }
5.1587 +
5.1588 + template <typename GraphEdgeMap, typename GraphNodeMap>
5.1589 + static CombinedEdgeMap<const GraphEdgeMap, GraphNodeMap>
5.1590 + combinedEdgeMap(const GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
5.1591 + return CombinedEdgeMap<const GraphEdgeMap,
5.1592 + GraphNodeMap>(edge_map, node_map);
5.1593 + }
5.1594 +
5.1595 + template <typename GraphEdgeMap, typename GraphNodeMap>
5.1596 + static CombinedEdgeMap<GraphEdgeMap, const GraphNodeMap>
5.1597 + combinedEdgeMap(GraphEdgeMap& edge_map, const GraphNodeMap& node_map) {
5.1598 + return CombinedEdgeMap<GraphEdgeMap,
5.1599 + const GraphNodeMap>(edge_map, node_map);
5.1600 + }
5.1601 +
5.1602 + template <typename GraphEdgeMap, typename GraphNodeMap>
5.1603 + static CombinedEdgeMap<const GraphEdgeMap, const GraphNodeMap>
5.1604 + combinedEdgeMap(const GraphEdgeMap& edge_map,
5.1605 + const GraphNodeMap& node_map) {
5.1606 + return CombinedEdgeMap<const GraphEdgeMap,
5.1607 + const GraphNodeMap>(edge_map, node_map);
5.1608 + }
5.1609 +
5.1610 + };
5.1611 +
5.1612
5.1613 } //namespace lemon
5.1614
