The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.
The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.
The ResGraphAdaptor is based on this composition.
1.1 --- a/lemon/bits/edge_set_extender.h Wed Mar 01 10:17:25 2006 +0000
1.2 +++ b/lemon/bits/edge_set_extender.h Wed Mar 01 10:25:30 2006 +0000
1.3 @@ -68,6 +68,8 @@
1.4
1.5 public:
1.6
1.7 + using Parent::getNotifier;
1.8 +
1.9 /// \brief Gives back the edge alteration notifier.
1.10 ///
1.11 /// Gives back the edge alteration notifier.
1.12 @@ -322,6 +324,8 @@
1.13 mutable UEdgeNotifier uedge_notifier;
1.14
1.15 public:
1.16 +
1.17 + using Parent::getNotifier;
1.18
1.19 EdgeNotifier& getNotifier(Edge) const {
1.20 return edge_notifier;
2.1 --- a/lemon/bits/graph_extender.h Wed Mar 01 10:17:25 2006 +0000
2.2 +++ b/lemon/bits/graph_extender.h Wed Mar 01 10:25:30 2006 +0000
2.3 @@ -1568,7 +1568,7 @@
2.4 protected:
2.5
2.6 template <typename _Value>
2.7 - class NodeMapBase : public NodeNotifier::ObserverBase {
2.8 + class NodeMapBase {
2.9 public:
2.10 typedef BpUGraphExtender Graph;
2.11
2.12 @@ -1590,21 +1590,10 @@
2.13 typedef True ReferenceMapTag;
2.14
2.15 NodeMapBase(const Graph& _g)
2.16 - : graph(&_g), bNodeMap(_g), aNodeMap(_g) {
2.17 - NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
2.18 - }
2.19 + : aNodeMap(_g), bNodeMap(_g) {}
2.20 NodeMapBase(const Graph& _g, const _Value& _v)
2.21 - : graph(&_g), bNodeMap(_g, _v),
2.22 - aNodeMap(_g, _v) {
2.23 - NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
2.24 - }
2.25 + : aNodeMap(_g, _v), bNodeMap(_g, _v) {}
2.26
2.27 - virtual ~NodeMapBase() {
2.28 - if (NodeNotifier::ObserverBase::attached()) {
2.29 - NodeNotifier::ObserverBase::detach();
2.30 - }
2.31 - }
2.32 -
2.33 ConstReference operator[](const Key& node) const {
2.34 if (Parent::aNode(node)) {
2.35 return aNodeMap[node];
2.36 @@ -1629,21 +1618,13 @@
2.37 }
2.38 }
2.39
2.40 - protected:
2.41 -
2.42 - virtual void add(const Node&) {}
2.43 - virtual void add(const std::vector<Node>&) {}
2.44 - virtual void erase(const Node&) {}
2.45 - virtual void erase(const std::vector<Node>&) {}
2.46 - virtual void clear() {}
2.47 - virtual void build() {}
2.48 + const Graph* getGraph() const {
2.49 + return aNodeMap.getGraph();
2.50 + }
2.51
2.52 - const Graph* getGraph() const { return graph; }
2.53 -
2.54 private:
2.55 - const Graph* graph;
2.56 + ANodeMap<_Value> aNodeMap;
2.57 BNodeMap<_Value> bNodeMap;
2.58 - ANodeMap<_Value> aNodeMap;
2.59 };
2.60
2.61 public:
3.1 --- a/lemon/graph_adaptor.h Wed Mar 01 10:17:25 2006 +0000
3.2 +++ b/lemon/graph_adaptor.h Wed Mar 01 10:25:30 2006 +0000
3.3 @@ -113,25 +113,45 @@
3.4
3.5 int id(const Node& v) const { return graph->id(v); }
3.6 int id(const Edge& e) const { return graph->id(e); }
3.7 +
3.8 + int maxNodeId() const {
3.9 + return graph->maxNodeId();
3.10 + }
3.11 +
3.12 + int maxEdgeId() const {
3.13 + return graph->maxEdgeId();
3.14 + }
3.15 +
3.16 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
3.17 +
3.18 + NodeNotifier& getNotifier(Node) const {
3.19 + return graph->getNotifier(Node());
3.20 + }
3.21 +
3.22 + typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
3.23 +
3.24 + EdgeNotifier& getNotifier(Edge) const {
3.25 + return graph->getNotifier(Edge());
3.26 + }
3.27
3.28 template <typename _Value>
3.29 class NodeMap : public _Graph::template NodeMap<_Value> {
3.30 public:
3.31 typedef typename _Graph::template NodeMap<_Value> Parent;
3.32 - explicit NodeMap(const GraphAdaptorBase<_Graph>& gw)
3.33 - : Parent(*gw.graph) { }
3.34 - NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
3.35 - : Parent(*gw.graph, value) { }
3.36 + explicit NodeMap(const GraphAdaptorBase<_Graph>& ga)
3.37 + : Parent(*ga.graph) { }
3.38 + NodeMap(const GraphAdaptorBase<_Graph>& ga, const _Value& value)
3.39 + : Parent(*ga.graph, value) { }
3.40 };
3.41
3.42 template <typename _Value>
3.43 class EdgeMap : public _Graph::template EdgeMap<_Value> {
3.44 public:
3.45 typedef typename _Graph::template EdgeMap<_Value> Parent;
3.46 - explicit EdgeMap(const GraphAdaptorBase<_Graph>& gw)
3.47 - : Parent(*gw.graph) { }
3.48 - EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
3.49 - : Parent(*gw.graph, value) { }
3.50 + explicit EdgeMap(const GraphAdaptorBase<_Graph>& ga)
3.51 + : Parent(*ga.graph) { }
3.52 + EdgeMap(const GraphAdaptorBase<_Graph>& ga, const _Value& value)
3.53 + : Parent(*ga.graph, value) { }
3.54 };
3.55
3.56 };
3.57 @@ -149,6 +169,17 @@
3.58 explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); }
3.59 };
3.60
3.61 + /// \brief Just gives back a graph adaptor
3.62 + ///
3.63 + /// Just gives back a graph adaptor which
3.64 + /// should be provide original graph
3.65 + template<typename Graph>
3.66 + GraphAdaptor<const Graph>
3.67 + graphAdaptor(const Graph& graph) {
3.68 + return GraphAdaptor<const Graph>(graph);
3.69 + }
3.70 +
3.71 +
3.72 template <typename _Graph>
3.73 class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
3.74 public:
3.75 @@ -168,6 +199,13 @@
3.76
3.77 Node source(const Edge& e) const { return Parent::target(e); }
3.78 Node target(const Edge& e) const { return Parent::source(e); }
3.79 +
3.80 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
3.81 + Edge findEdge(const Node& source, const Node& target,
3.82 + const Edge& prev = INVALID) {
3.83 + return Parent::findEdge(target, source, prev);
3.84 + }
3.85 +
3.86 };
3.87
3.88
3.89 @@ -184,7 +222,7 @@
3.90 ///\endcode
3.91 /// then
3.92 ///\code
3.93 - /// RevGraphAdaptor<ListGraph> gw(g);
3.94 + /// RevGraphAdaptor<ListGraph> ga(g);
3.95 ///\endcode
3.96 ///implements the graph obtained from \c g by
3.97 /// reversing the orientation of its edges.
3.98 @@ -202,7 +240,15 @@
3.99 explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
3.100 };
3.101
3.102 -
3.103 + /// \brief Just gives back a reverse graph adaptor
3.104 + ///
3.105 + /// Just gives back a reverse graph adaptor
3.106 + template<typename Graph>
3.107 + RevGraphAdaptor<const Graph>
3.108 + revGraphAdaptor(const Graph& graph) {
3.109 + return RevGraphAdaptor<const Graph>(graph);
3.110 + }
3.111 +
3.112 template <typename _Graph, typename NodeFilterMap,
3.113 typename EdgeFilterMap, bool checked = true>
3.114 class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
3.115 @@ -315,9 +361,21 @@
3.116 ///
3.117 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
3.118
3.119 - typedef False FindEdgeTag;
3.120 typedef False NodeNumTag;
3.121 typedef False EdgeNumTag;
3.122 +
3.123 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
3.124 + Edge findEdge(const Node& source, const Node& target,
3.125 + const Edge& prev = INVALID) {
3.126 + if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
3.127 + return INVALID;
3.128 + }
3.129 + Edge edge = Parent::findEdge(source, target, prev);
3.130 + while (edge != INVALID && !(*edge_filter_map)[edge]) {
3.131 + edge = Parent::findEdge(source, target, edge);
3.132 + }
3.133 + return edge;
3.134 + }
3.135 };
3.136
3.137 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
3.138 @@ -422,9 +480,21 @@
3.139 ///
3.140 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
3.141
3.142 - typedef False FindEdgeTag;
3.143 typedef False NodeNumTag;
3.144 typedef False EdgeNumTag;
3.145 +
3.146 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
3.147 + Edge findEdge(const Node& source, const Node& target,
3.148 + const Edge& prev = INVALID) {
3.149 + if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
3.150 + return INVALID;
3.151 + }
3.152 + Edge edge = Parent::findEdge(source, target, prev);
3.153 + while (edge != INVALID && !(*edge_filter_map)[edge]) {
3.154 + edge = Parent::findEdge(source, target, edge);
3.155 + }
3.156 + return edge;
3.157 + }
3.158 };
3.159
3.160 /// \brief A graph adaptor for hiding nodes and edges from a graph.
3.161 @@ -468,11 +538,11 @@
3.162 /// nm.set(u, false);
3.163 /// Graph::EdgeMap<bool> em(g, true);
3.164 /// em.set(e, false);
3.165 - /// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
3.166 - /// SubGW gw(g, nm, em);
3.167 - /// for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
3.168 + /// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGA;
3.169 + /// SubGA ga(g, nm, em);
3.170 + /// for (SubGA::NodeIt n(ga); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
3.171 /// std::cout << ":-)" << std::endl;
3.172 - /// for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
3.173 + /// for (SubGA::EdgeIt e(ga); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
3.174 ///\endcode
3.175 /// The output of the above code is the following.
3.176 ///\code
3.177 @@ -480,7 +550,7 @@
3.178 /// :-)
3.179 /// 1
3.180 ///\endcode
3.181 - /// Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
3.182 + /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
3.183 /// \c Graph::Node that is why \c g.id(n) can be applied.
3.184 ///
3.185 /// For other examples see also the documentation of NodeSubGraphAdaptor and
3.186 @@ -508,6 +578,41 @@
3.187 }
3.188 };
3.189
3.190 + /// \brief Just gives back a sub graph adaptor
3.191 + ///
3.192 + /// Just gives back a sub graph adaptor
3.193 + template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
3.194 + SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
3.195 + subGraphAdaptor(const Graph& graph,
3.196 + NodeFilterMap& nfm, EdgeFilterMap& efm) {
3.197 + return SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
3.198 + (graph, nfm, efm);
3.199 + }
3.200 +
3.201 + template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
3.202 + SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
3.203 + subGraphAdaptor(const Graph& graph,
3.204 + NodeFilterMap& nfm, EdgeFilterMap& efm) {
3.205 + return SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
3.206 + (graph, nfm, efm);
3.207 + }
3.208 +
3.209 + template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
3.210 + SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
3.211 + subGraphAdaptor(const Graph& graph,
3.212 + NodeFilterMap& nfm, EdgeFilterMap& efm) {
3.213 + return SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
3.214 + (graph, nfm, efm);
3.215 + }
3.216 +
3.217 + template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
3.218 + SubGraphAdaptor<const Graph, const NodeFilterMap, const EdgeFilterMap>
3.219 + subGraphAdaptor(const Graph& graph,
3.220 + NodeFilterMap& nfm, EdgeFilterMap& efm) {
3.221 + return SubGraphAdaptor<const Graph, const NodeFilterMap,
3.222 + const EdgeFilterMap>(graph, nfm, efm);
3.223 + }
3.224 +
3.225
3.226
3.227 ///\brief An adaptor for hiding nodes from a graph.
3.228 @@ -533,6 +638,11 @@
3.229 ConstMap<typename Graph::Edge,bool> > Parent;
3.230 protected:
3.231 ConstMap<typename Graph::Edge, bool> const_true_map;
3.232 +
3.233 + NodeSubGraphAdaptor() : const_true_map(true) {
3.234 + Parent::setEdgeFilterMap(const_true_map);
3.235 + }
3.236 +
3.237 public:
3.238 NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
3.239 Parent(), const_true_map(true) {
3.240 @@ -543,6 +653,21 @@
3.241 };
3.242
3.243
3.244 + /// \brief Just gives back a node sub graph adaptor
3.245 + ///
3.246 + /// Just gives back a node sub graph adaptor
3.247 + template<typename Graph, typename NodeFilterMap>
3.248 + NodeSubGraphAdaptor<const Graph, NodeFilterMap>
3.249 + nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {
3.250 + return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);
3.251 + }
3.252 +
3.253 + template<typename Graph, typename NodeFilterMap>
3.254 + NodeSubGraphAdaptor<const Graph, const NodeFilterMap>
3.255 + nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) {
3.256 + return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);
3.257 + }
3.258 +
3.259 ///\brief An adaptor for hiding edges from a graph.
3.260 ///
3.261 ///\warning Graph adaptors are in even more experimental state
3.262 @@ -630,8 +755,8 @@
3.263 /// TightEdgeFilter;
3.264 ///TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
3.265 ///
3.266 - ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
3.267 - ///SubGW gw(g, tight_edge_filter);
3.268 + ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGA;
3.269 + ///SubGA ga(g, tight_edge_filter);
3.270 ///\endcode
3.271 ///Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
3.272 ///with a max flow algorithm Preflow.
3.273 @@ -639,8 +764,8 @@
3.274 ///ConstMap<Edge, int> const_1_map(1);
3.275 ///Graph::EdgeMap<int> flow(g, 0);
3.276 ///
3.277 - ///Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
3.278 - /// preflow(gw, s, t, const_1_map, flow);
3.279 + ///Preflow<SubGA, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
3.280 + /// preflow(ga, s, t, const_1_map, flow);
3.281 ///preflow.run();
3.282 ///\endcode
3.283 ///Last, the output is:
3.284 @@ -688,6 +813,11 @@
3.285 EdgeFilterMap, false> Parent;
3.286 protected:
3.287 ConstMap<typename Graph::Node, bool> const_true_map;
3.288 +
3.289 + EdgeSubGraphAdaptor() : const_true_map(true) {
3.290 + Parent::setNodeFilterMap(const_true_map);
3.291 + }
3.292 +
3.293 public:
3.294 EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
3.295 Parent(), const_true_map(true) {
3.296 @@ -697,70 +827,273 @@
3.297 }
3.298 };
3.299
3.300 - template <typename _Graph>
3.301 + /// \brief Just gives back an edge sub graph adaptor
3.302 + ///
3.303 + /// Just gives back an edge sub graph adaptor
3.304 + template<typename Graph, typename EdgeFilterMap>
3.305 + EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>
3.306 + edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {
3.307 + return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm);
3.308 + }
3.309 +
3.310 + template<typename Graph, typename EdgeFilterMap>
3.311 + EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>
3.312 + edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) {
3.313 + return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
3.314 + }
3.315 +
3.316 + template <typename _Graph, typename Enable = void>
3.317 class UndirGraphAdaptorBase :
3.318 public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
3.319 public:
3.320 typedef _Graph Graph;
3.321 typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
3.322 +
3.323 protected:
3.324 - UndirGraphAdaptorBase() : Parent() { }
3.325 +
3.326 + UndirGraphAdaptorBase() : Parent() {}
3.327 +
3.328 public:
3.329 +
3.330 typedef typename Parent::UEdge UEdge;
3.331 typedef typename Parent::Edge Edge;
3.332 +
3.333
3.334 - template <typename T>
3.335 + template <typename _Value>
3.336 class EdgeMap {
3.337 - protected:
3.338 - const UndirGraphAdaptorBase<_Graph>* g;
3.339 - template <typename TT> friend class EdgeMap;
3.340 - typename _Graph::template EdgeMap<T> forward_map, backward_map;
3.341 + private:
3.342 +
3.343 + typedef typename _Graph::template EdgeMap<_Value> MapImpl;
3.344 +
3.345 public:
3.346 - typedef T Value;
3.347 +
3.348 + typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
3.349 +
3.350 + typedef _Value Value;
3.351 typedef Edge Key;
3.352
3.353 - EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g),
3.354 - forward_map(*(g->graph)), backward_map(*(g->graph)) { }
3.355 + EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) :
3.356 + forward_map(*(_g.graph)), backward_map(*(_g.graph)) {}
3.357
3.358 - EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
3.359 - forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
3.360 + EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, const Value& a)
3.361 + : forward_map(*(_g.graph), a), backward_map(*(_g.graph), a) {}
3.362
3.363 - void set(Edge e, T a) {
3.364 - if (g->direction(e))
3.365 + void set(const Edge& e, const Value& a) {
3.366 + if (Parent::direction(e)) {
3.367 forward_map.set(e, a);
3.368 - else
3.369 - backward_map.set(e, a);
3.370 + } else {
3.371 + backward_map.set(e, a);
3.372 + }
3.373 }
3.374
3.375 - T operator[](Edge e) const {
3.376 - if (g->direction(e))
3.377 + typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const {
3.378 + if (Parent::direction(e)) {
3.379 return forward_map[e];
3.380 - else
3.381 + } else {
3.382 return backward_map[e];
3.383 + }
3.384 }
3.385 +
3.386 + typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) {
3.387 + if (Parent::direction(e)) {
3.388 + return forward_map[e];
3.389 + } else {
3.390 + return backward_map[e];
3.391 + }
3.392 + }
3.393 +
3.394 + protected:
3.395 +
3.396 + MapImpl forward_map, backward_map;
3.397 +
3.398 };
3.399
3.400 - template <typename T>
3.401 - class UEdgeMap {
3.402 - template <typename TT> friend class UEdgeMap;
3.403 - typename _Graph::template EdgeMap<T> map;
3.404 + template <typename _Value>
3.405 + class UEdgeMap : public _Graph::template EdgeMap<_Value> {
3.406 public:
3.407 - typedef T Value;
3.408 - typedef UEdge Key;
3.409 +
3.410 + typedef typename _Graph::template EdgeMap<_Value> Parent;
3.411 +
3.412 + UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g)
3.413 + : Parent(*(g.graph)) {}
3.414 +
3.415 + UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, const _Value& a)
3.416 + : Parent(*(g.graph), a) {}
3.417
3.418 - UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) :
3.419 - map(*(g.graph)) { }
3.420 + };
3.421 +
3.422 + };
3.423
3.424 - UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) :
3.425 - map(*(g.graph), a) { }
3.426 + template <typename _Graph>
3.427 + class UndirGraphAdaptorBase<
3.428 + _Graph, typename enable_if<
3.429 + typename _Graph::EdgeNotifier::Notifier>::type >
3.430 + : public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
3.431 + public:
3.432 +
3.433 + typedef _Graph Graph;
3.434 + typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
3.435 +
3.436 + protected:
3.437 +
3.438 + UndirGraphAdaptorBase()
3.439 + : Parent(), edge_notifier(), edge_notifier_proxy(edge_notifier) {}
3.440 +
3.441 + void setGraph(_Graph& graph) {
3.442 + Parent::setGraph(graph);
3.443 + edge_notifier_proxy.setUEdgeNotifier(graph.getNotifier(UEdge()));
3.444 + }
3.445 +
3.446 + public:
3.447 +
3.448 + ~UndirGraphAdaptorBase() {
3.449 + getNotifier(Edge()).clear();
3.450 + }
3.451 +
3.452 +
3.453 + typedef typename Parent::UEdge UEdge;
3.454 + typedef typename Parent::Edge Edge;
3.455 +
3.456 + typedef typename Parent::EdgeNotifier UEdgeNotifier;
3.457 +
3.458 + using Parent::getNotifier;
3.459 +
3.460 + typedef AlterationNotifier<Edge> EdgeNotifier;
3.461 + EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
3.462 +
3.463 + protected:
3.464 +
3.465 + class NotifierProxy : public UEdgeNotifier::ObserverBase {
3.466 + public:
3.467 +
3.468 + typedef typename UEdgeNotifier::ObserverBase Parent;
3.469 + typedef UndirGraphAdaptorBase AdaptorBase;
3.470
3.471 - void set(UEdge e, T a) {
3.472 - map.set(e, a);
3.473 + NotifierProxy(EdgeNotifier& _edge_notifier)
3.474 + : Parent(), edge_notifier(_edge_notifier) {
3.475 }
3.476
3.477 - T operator[](UEdge e) const {
3.478 - return map[e];
3.479 + virtual ~NotifierProxy() {
3.480 + if (Parent::attached()) {
3.481 + Parent::detach();
3.482 + }
3.483 }
3.484 +
3.485 + void setUEdgeNotifier(UEdgeNotifier& _uedge_notifier) {
3.486 + Parent::attach(_uedge_notifier);
3.487 + }
3.488 +
3.489 +
3.490 + protected:
3.491 +
3.492 + virtual void add(const UEdge& uedge) {
3.493 + std::vector<Edge> edges;
3.494 + edges.push_back(AdaptorBase::Parent::direct(uedge, true));
3.495 + edges.push_back(AdaptorBase::Parent::direct(uedge, false));
3.496 + edge_notifier.add(edges);
3.497 + }
3.498 + virtual void add(const std::vector<UEdge>& uedges) {
3.499 + std::vector<Edge> edges;
3.500 + for (int i = 0; i < (int)uedges.size(); ++i) {
3.501 + edges.push_back(AdaptorBase::Parent::direct(uedges[i], true));
3.502 + edges.push_back(AdaptorBase::Parent::direct(uedges[i], false));
3.503 + }
3.504 + edge_notifier.add(edges);
3.505 + }
3.506 + virtual void erase(const UEdge& uedge) {
3.507 + std::vector<Edge> edges;
3.508 + edges.push_back(AdaptorBase::Parent::direct(uedge, true));
3.509 + edges.push_back(AdaptorBase::Parent::direct(uedge, false));
3.510 + edge_notifier.erase(edges);
3.511 + }
3.512 + virtual void erase(const std::vector<UEdge>& uedges) {
3.513 + std::vector<Edge> edges;
3.514 + for (int i = 0; i < (int)uedges.size(); ++i) {
3.515 + edges.push_back(AdaptorBase::Parent::direct(uedges[i], true));
3.516 + edges.push_back(AdaptorBase::Parent::direct(uedges[i], false));
3.517 + }
3.518 + edge_notifier.erase(edges);
3.519 + }
3.520 + virtual void build() {
3.521 + edge_notifier.build();
3.522 + }
3.523 + virtual void clear() {
3.524 + edge_notifier.clear();
3.525 + }
3.526 +
3.527 + EdgeNotifier& edge_notifier;
3.528 + };
3.529 +
3.530 +
3.531 + mutable EdgeNotifier edge_notifier;
3.532 + NotifierProxy edge_notifier_proxy;
3.533 +
3.534 + public:
3.535 +
3.536 +
3.537 + template <typename _Value>
3.538 + class EdgeMap {
3.539 + private:
3.540 +
3.541 + typedef typename _Graph::template EdgeMap<_Value> MapImpl;
3.542 +
3.543 + public:
3.544 +
3.545 + typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
3.546 +
3.547 + typedef _Value Value;
3.548 + typedef Edge Key;
3.549 +
3.550 + EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) :
3.551 + forward_map(*(_g.graph)), backward_map(*(_g.graph)) {}
3.552 +
3.553 + EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, const Value& a)
3.554 + : forward_map(*(_g.graph), a), backward_map(*(_g.graph), a) {}
3.555 +
3.556 + void set(const Edge& e, const Value& a) {
3.557 + if (Parent::direction(e)) {
3.558 + forward_map.set(e, a);
3.559 + } else {
3.560 + backward_map.set(e, a);
3.561 + }
3.562 + }
3.563 +
3.564 + typename MapTraits<MapImpl>::ConstReturnValue
3.565 + operator[](const Edge& e) const {
3.566 + if (Parent::direction(e)) {
3.567 + return forward_map[e];
3.568 + } else {
3.569 + return backward_map[e];
3.570 + }
3.571 + }
3.572 +
3.573 + typename MapTraits<MapImpl>::ReturnValue
3.574 + operator[](const Edge& e) {
3.575 + if (Parent::direction(e)) {
3.576 + return forward_map[e];
3.577 + } else {
3.578 + return backward_map[e];
3.579 + }
3.580 + }
3.581 +
3.582 + protected:
3.583 +
3.584 + MapImpl forward_map, backward_map;
3.585 +
3.586 + };
3.587 +
3.588 + template <typename _Value>
3.589 + class UEdgeMap : public _Graph::template EdgeMap<_Value> {
3.590 + public:
3.591 +
3.592 + typedef typename _Graph::template EdgeMap<_Value> Parent;
3.593 +
3.594 + UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g)
3.595 + : Parent(*(g.graph)) {}
3.596 +
3.597 + UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, const _Value& a)
3.598 + : Parent(*(g.graph), a) {}
3.599 +
3.600 };
3.601
3.602 };
3.603 @@ -786,373 +1119,90 @@
3.604 UndirGraphAdaptor(_Graph& _graph) {
3.605 setGraph(_graph);
3.606 }
3.607 - };
3.608
3.609 -
3.610 - template <typename _Graph,
3.611 - typename ForwardFilterMap, typename BackwardFilterMap>
3.612 - class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
3.613 - public:
3.614 - typedef _Graph Graph;
3.615 - typedef GraphAdaptorBase<_Graph> Parent;
3.616 - protected:
3.617 - ForwardFilterMap* forward_filter;
3.618 - BackwardFilterMap* backward_filter;
3.619 - SubBidirGraphAdaptorBase() : Parent(),
3.620 - forward_filter(0), backward_filter(0) { }
3.621 + template <typename _ForwardMap, typename _BackwardMap>
3.622 + class CombinedEdgeMap {
3.623 + public:
3.624 +
3.625 + typedef _ForwardMap ForwardMap;
3.626 + typedef _BackwardMap BackwardMap;
3.627
3.628 - void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
3.629 - forward_filter=&_forward_filter;
3.630 - }
3.631 - void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
3.632 - backward_filter=&_backward_filter;
3.633 - }
3.634 + typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
3.635
3.636 - public:
3.637 -// SubGraphAdaptorBase(Graph& _graph,
3.638 -// NodeFilterMap& _node_filter_map,
3.639 -// EdgeFilterMap& _edge_filter_map) :
3.640 -// Parent(&_graph),
3.641 -// node_filter_map(&node_filter_map),
3.642 -// edge_filter_map(&edge_filter_map) { }
3.643 + typedef typename ForwardMap::Value Value;
3.644 + typedef typename Parent::Edge Key;
3.645 +
3.646 + CombinedEdgeMap() : forward_map(0), backward_map(0) {}
3.647
3.648 - typedef typename Parent::Node Node;
3.649 - typedef typename _Graph::Edge GraphEdge;
3.650 - template <typename T> class EdgeMap;
3.651 - // SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
3.652 - // _Graph::Edge. It contains an extra bool flag which is true
3.653 - // if and only if the
3.654 - // edge is the backward version of the original edge.
3.655 - class Edge : public _Graph::Edge {
3.656 - friend class SubBidirGraphAdaptorBase<
3.657 - Graph, ForwardFilterMap, BackwardFilterMap>;
3.658 - template<typename T> friend class EdgeMap;
3.659 - protected:
3.660 - bool backward; //true, iff backward
3.661 - public:
3.662 - Edge() { }
3.663 - // \todo =false is needed, or causes problems?
3.664 - // If \c _backward is false, then we get an edge corresponding to the
3.665 - // original one, otherwise its oppositely directed pair is obtained.
3.666 - Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
3.667 - _Graph::Edge(e), backward(_backward) { }
3.668 - Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
3.669 - bool operator==(const Edge& v) const {
3.670 - return (this->backward==v.backward &&
3.671 - static_cast<typename _Graph::Edge>(*this)==
3.672 - static_cast<typename _Graph::Edge>(v));
3.673 - }
3.674 - bool operator!=(const Edge& v) const {
3.675 - return (this->backward!=v.backward ||
3.676 - static_cast<typename _Graph::Edge>(*this)!=
3.677 - static_cast<typename _Graph::Edge>(v));
3.678 - }
3.679 - };
3.680 -
3.681 - void first(Node& i) const {
3.682 - Parent::first(i);
3.683 - }
3.684 -
3.685 - void first(Edge& i) const {
3.686 - Parent::first(i);
3.687 - i.backward=false;
3.688 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
3.689 - !(*forward_filter)[i]) Parent::next(i);
3.690 - if (*static_cast<GraphEdge*>(&i)==INVALID) {
3.691 - Parent::first(i);
3.692 - i.backward=true;
3.693 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
3.694 - !(*backward_filter)[i]) Parent::next(i);
3.695 - }
3.696 - }
3.697 -
3.698 - void firstIn(Edge& i, const Node& n) const {
3.699 - Parent::firstIn(i, n);
3.700 - i.backward=false;
3.701 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
3.702 - !(*forward_filter)[i]) Parent::nextIn(i);
3.703 - if (*static_cast<GraphEdge*>(&i)==INVALID) {
3.704 - Parent::firstOut(i, n);
3.705 - i.backward=true;
3.706 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
3.707 - !(*backward_filter)[i]) Parent::nextOut(i);
3.708 - }
3.709 - }
3.710 -
3.711 - void firstOut(Edge& i, const Node& n) const {
3.712 - Parent::firstOut(i, n);
3.713 - i.backward=false;
3.714 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
3.715 - !(*forward_filter)[i]) Parent::nextOut(i);
3.716 - if (*static_cast<GraphEdge*>(&i)==INVALID) {
3.717 - Parent::firstIn(i, n);
3.718 - i.backward=true;
3.719 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
3.720 - !(*backward_filter)[i]) Parent::nextIn(i);
3.721 - }
3.722 - }
3.723 -
3.724 - void next(Node& i) const {
3.725 - Parent::next(i);
3.726 - }
3.727 -
3.728 - void next(Edge& i) const {
3.729 - if (!(i.backward)) {
3.730 - Parent::next(i);
3.731 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
3.732 - !(*forward_filter)[i]) Parent::next(i);
3.733 - if (*static_cast<GraphEdge*>(&i)==INVALID) {
3.734 - Parent::first(i);
3.735 - i.backward=true;
3.736 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
3.737 - !(*backward_filter)[i]) Parent::next(i);
3.738 - }
3.739 - } else {
3.740 - Parent::next(i);
3.741 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
3.742 - !(*backward_filter)[i]) Parent::next(i);
3.743 - }
3.744 - }
3.745 -
3.746 - void nextIn(Edge& i) const {
3.747 - if (!(i.backward)) {
3.748 - Node n=Parent::target(i);
3.749 - Parent::nextIn(i);
3.750 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
3.751 - !(*forward_filter)[i]) Parent::nextIn(i);
3.752 - if (*static_cast<GraphEdge*>(&i)==INVALID) {
3.753 - Parent::firstOut(i, n);
3.754 - i.backward=true;
3.755 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
3.756 - !(*backward_filter)[i]) Parent::nextOut(i);
3.757 - }
3.758 - } else {
3.759 - Parent::nextOut(i);
3.760 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
3.761 - !(*backward_filter)[i]) Parent::nextOut(i);
3.762 - }
3.763 - }
3.764 -
3.765 - void nextOut(Edge& i) const {
3.766 - if (!(i.backward)) {
3.767 - Node n=Parent::source(i);
3.768 - Parent::nextOut(i);
3.769 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
3.770 - !(*forward_filter)[i]) Parent::nextOut(i);
3.771 - if (*static_cast<GraphEdge*>(&i)==INVALID) {
3.772 - Parent::firstIn(i, n);
3.773 - i.backward=true;
3.774 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
3.775 - !(*backward_filter)[i]) Parent::nextIn(i);
3.776 - }
3.777 - } else {
3.778 - Parent::nextIn(i);
3.779 - while (*static_cast<GraphEdge*>(&i)!=INVALID &&
3.780 - !(*backward_filter)[i]) Parent::nextIn(i);
3.781 - }
3.782 - }
3.783 -
3.784 - Node source(Edge e) const {
3.785 - return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
3.786 - Node target(Edge e) const {
3.787 - return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
3.788 -
3.789 - /// Gives back the opposite edge.
3.790 -
3.791 - ///\e
3.792 - ///
3.793 - Edge opposite(const Edge& e) const {
3.794 - Edge f=e;
3.795 - f.backward=!f.backward;
3.796 - return f;
3.797 - }
3.798 -
3.799 - ///\e
3.800 -
3.801 - /// \warning This is a linear time operation and works only if
3.802 - /// \c Graph::EdgeIt is defined.
3.803 - /// \todo hmm
3.804 - int edgeNum() const {
3.805 - int i=0;
3.806 - Edge e;
3.807 - for (first(e); e!=INVALID; next(e)) ++i;
3.808 - return i;
3.809 - }
3.810 -
3.811 - bool forward(const Edge& e) const { return !e.backward; }
3.812 - bool backward(const Edge& e) const { return e.backward; }
3.813 -
3.814 - ///\e
3.815 -
3.816 - /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
3.817 - /// _Graph::EdgeMap one for the forward edges and
3.818 - /// one for the backward edges.
3.819 - template <typename T>
3.820 - class EdgeMap {
3.821 - template <typename TT> friend class EdgeMap;
3.822 - typename _Graph::template EdgeMap<T> forward_map, backward_map;
3.823 - public:
3.824 - typedef T Value;
3.825 - typedef Edge Key;
3.826 -
3.827 - EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
3.828 - ForwardFilterMap, BackwardFilterMap>& g) :
3.829 - forward_map(*(g.graph)), backward_map(*(g.graph)) { }
3.830 -
3.831 - EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
3.832 - ForwardFilterMap, BackwardFilterMap>& g, T a) :
3.833 - forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
3.834 + CombinedEdgeMap(ForwardMap& _forward_map, BackwardMap& _backward_map)
3.835 + : forward_map(&_forward_map), backward_map(&_backward_map) {}
3.836
3.837 - void set(Edge e, T a) {
3.838 - if (!e.backward)
3.839 - forward_map.set(e, a);
3.840 - else
3.841 - backward_map.set(e, a);
3.842 + void set(const Key& e, const Value& a) {
3.843 + if (Parent::direction(e)) {
3.844 + forward_map->set(e, a);
3.845 + } else {
3.846 + backward_map->set(e, a);
3.847 + }
3.848 }
3.849
3.850 -// typename _Graph::template EdgeMap<T>::ConstReference
3.851 -// operator[](Edge e) const {
3.852 -// if (!e.backward)
3.853 -// return forward_map[e];
3.854 -// else
3.855 -// return backward_map[e];
3.856 -// }
3.857 -
3.858 -// typename _Graph::template EdgeMap<T>::Reference
3.859 - T operator[](Edge e) const {
3.860 - if (!e.backward)
3.861 - return forward_map[e];
3.862 - else
3.863 - return backward_map[e];
3.864 + typename MapTraits<ForwardMap>::ConstReturnValue
3.865 + operator[](const Key& e) const {
3.866 + if (Parent::direction(e)) {
3.867 + return (*forward_map)[e];
3.868 + } else {
3.869 + return (*backward_map)[e];
3.870 + }
3.871 }
3.872
3.873 - void update() {
3.874 - forward_map.update();
3.875 - backward_map.update();
3.876 + typename MapTraits<ForwardMap>::ReturnValue
3.877 + operator[](const Key& e) {
3.878 + if (Parent::direction(e)) {
3.879 + return (*forward_map)[e];
3.880 + } else {
3.881 + return (*backward_map)[e];
3.882 + }
3.883 }
3.884 +
3.885 + void setForwardMap(ForwardMap& _forward_map) {
3.886 + forward_map = &_forward_map;
3.887 + }
3.888 +
3.889 + void setBackwardMap(BackwardMap& _backward_map) {
3.890 + backward_map = &_backward_map;
3.891 + }
3.892 +
3.893 + protected:
3.894 +
3.895 + ForwardMap* forward_map;
3.896 + BackwardMap* backward_map;
3.897 +
3.898 };
3.899
3.900 };
3.901
3.902 -
3.903 - ///\brief An adaptor for composing a subgraph of a
3.904 - /// bidirected graph made from a directed one.
3.905 - ///\ingroup graph_adaptors
3.906 + /// \brief Just gives back an undir graph adaptor
3.907 ///
3.908 - /// An adaptor for composing a subgraph of a
3.909 - /// bidirected graph made from a directed one.
3.910 - ///
3.911 - ///\warning Graph adaptors are in even more experimental state
3.912 - ///than the other
3.913 - ///parts of the lib. Use them at you own risk.
3.914 - ///
3.915 - /// Let \f$ G=(V, A) \f$ be a directed graph and for each directed edge
3.916 - ///\f$ e\in A \f$, let \f$ \bar e \f$ denote the edge obtained by
3.917 - /// reversing its orientation. We are given moreover two bool valued
3.918 - /// maps on the edge-set,
3.919 - ///\f$ forward\_filter \f$, and \f$ backward\_filter \f$.
3.920 - /// SubBidirGraphAdaptor implements the graph structure with node-set
3.921 - ///\f$ V \f$ and edge-set
3.922 - ///\f$ \{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\} \f$.
3.923 - /// The purpose of writing + instead of union is because parallel
3.924 - /// edges can arise. (Similarly, antiparallel edges also can arise).
3.925 - /// In other words, a subgraph of the bidirected graph obtained, which
3.926 - /// is given by orienting the edges of the original graph in both directions.
3.927 - /// As the oppositely directed edges are logically different,
3.928 - /// the maps are able to attach different values for them.
3.929 - ///
3.930 - /// An example for such a construction is \c RevGraphAdaptor where the
3.931 - /// forward_filter is everywhere false and the backward_filter is
3.932 - /// everywhere true. We note that for sake of efficiency,
3.933 - /// \c RevGraphAdaptor is implemented in a different way.
3.934 - /// But BidirGraphAdaptor is obtained from
3.935 - /// SubBidirGraphAdaptor by considering everywhere true
3.936 - /// valued maps both for forward_filter and backward_filter.
3.937 - ///
3.938 - /// The most important application of SubBidirGraphAdaptor
3.939 - /// is ResGraphAdaptor, which stands for the residual graph in directed
3.940 - /// flow and circulation problems.
3.941 - /// As adaptors usually, the SubBidirGraphAdaptor implements the
3.942 - /// above mentioned graph structure without its physical storage,
3.943 - /// that is the whole stuff is stored in constant memory.
3.944 - template<typename _Graph,
3.945 - typename ForwardFilterMap, typename BackwardFilterMap>
3.946 - class SubBidirGraphAdaptor :
3.947 - public GraphAdaptorExtender<
3.948 - SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
3.949 - public:
3.950 - typedef _Graph Graph;
3.951 - typedef GraphAdaptorExtender<
3.952 - SubBidirGraphAdaptorBase<
3.953 - _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
3.954 - protected:
3.955 - SubBidirGraphAdaptor() { }
3.956 - public:
3.957 - SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,
3.958 - BackwardFilterMap& _backward_filter) {
3.959 - setGraph(_graph);
3.960 - setForwardFilterMap(_forward_filter);
3.961 - setBackwardFilterMap(_backward_filter);
3.962 - }
3.963 - };
3.964 -
3.965 -
3.966 -
3.967 - ///\brief An adaptor for composing bidirected graph from a directed one.
3.968 - ///\ingroup graph_adaptors
3.969 - ///
3.970 - ///\warning Graph adaptors are in even more experimental state
3.971 - ///than the other
3.972 - ///parts of the lib. Use them at you own risk.
3.973 - ///
3.974 - /// An adaptor for composing bidirected graph from a directed one.
3.975 - /// A bidirected graph is composed over the directed one without physical
3.976 - /// storage. As the oppositely directed edges are logically different ones
3.977 - /// the maps are able to attach different values for them.
3.978 + /// Just gives back an undir graph adaptor
3.979 template<typename Graph>
3.980 - class BidirGraphAdaptor :
3.981 - public SubBidirGraphAdaptor<
3.982 - Graph,
3.983 - ConstMap<typename Graph::Edge, bool>,
3.984 - ConstMap<typename Graph::Edge, bool> > {
3.985 - public:
3.986 - typedef SubBidirGraphAdaptor<
3.987 - Graph,
3.988 - ConstMap<typename Graph::Edge, bool>,
3.989 - ConstMap<typename Graph::Edge, bool> > Parent;
3.990 - protected:
3.991 - ConstMap<typename Graph::Edge, bool> cm;
3.992 -
3.993 - BidirGraphAdaptor() : Parent(), cm(true) {
3.994 - Parent::setForwardFilterMap(cm);
3.995 - Parent::setBackwardFilterMap(cm);
3.996 - }
3.997 - public:
3.998 - BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {
3.999 - Parent::setGraph(_graph);
3.1000 - Parent::setForwardFilterMap(cm);
3.1001 - Parent::setBackwardFilterMap(cm);
3.1002 - }
3.1003 -
3.1004 - int edgeNum() const {
3.1005 - return 2*this->graph->edgeNum();
3.1006 - }
3.1007 - };
3.1008 -
3.1009 + UndirGraphAdaptor<const Graph>
3.1010 + undirGraphAdaptor(const Graph& graph) {
3.1011 + return UndirGraphAdaptor<const Graph>(graph);
3.1012 + }
3.1013
3.1014 template<typename Graph, typename Number,
3.1015 typename CapacityMap, typename FlowMap>
3.1016 class ResForwardFilter {
3.1017 - // const Graph* graph;
3.1018 const CapacityMap* capacity;
3.1019 const FlowMap* flow;
3.1020 public:
3.1021 - ResForwardFilter(/*const Graph& _graph, */
3.1022 - const CapacityMap& _capacity, const FlowMap& _flow) :
3.1023 - /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
3.1024 - ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
3.1025 - void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
3.1026 - void setFlow(const FlowMap& _flow) { flow=&_flow; }
3.1027 + typedef typename Graph::Edge Key;
3.1028 + typedef bool Value;
3.1029 +
3.1030 + ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow)
3.1031 + : capacity(&_capacity), flow(&_flow) { }
3.1032 + ResForwardFilter() : capacity(0), flow(0) { }
3.1033 + void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
3.1034 + void setFlow(const FlowMap& _flow) { flow = &_flow; }
3.1035 bool operator[](const typename Graph::Edge& e) const {
3.1036 return (Number((*flow)[e]) < Number((*capacity)[e]));
3.1037 }
3.1038 @@ -1164,12 +1214,14 @@
3.1039 const CapacityMap* capacity;
3.1040 const FlowMap* flow;
3.1041 public:
3.1042 - ResBackwardFilter(/*const Graph& _graph,*/
3.1043 - const CapacityMap& _capacity, const FlowMap& _flow) :
3.1044 - /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
3.1045 - ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
3.1046 - void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
3.1047 - void setFlow(const FlowMap& _flow) { flow=&_flow; }
3.1048 + typedef typename Graph::Edge Key;
3.1049 + typedef bool Value;
3.1050 +
3.1051 + ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow)
3.1052 + : capacity(&_capacity), flow(&_flow) { }
3.1053 + ResBackwardFilter() : capacity(0), flow(0) { }
3.1054 + void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
3.1055 + void setFlow(const FlowMap& _flow) { flow = &_flow; }
3.1056 bool operator[](const typename Graph::Edge& e) const {
3.1057 return (Number(0) < Number((*flow)[e]));
3.1058 }
3.1059 @@ -1207,80 +1259,118 @@
3.1060 ///typedef ListGraph Graph;
3.1061 ///Graph::EdgeMap<int> f(g);
3.1062 ///Graph::EdgeMap<int> c(g);
3.1063 - ///ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
3.1064 + ///ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > ga(g);
3.1065 ///\endcode
3.1066 ///\author Marton Makai
3.1067 ///
3.1068 template<typename Graph, typename Number,
3.1069 typename CapacityMap, typename FlowMap>
3.1070 class ResGraphAdaptor :
3.1071 - public SubBidirGraphAdaptor<
3.1072 - Graph,
3.1073 + public EdgeSubGraphAdaptor<
3.1074 + UndirGraphAdaptor<Graph>,
3.1075 + typename UndirGraphAdaptor<Graph>::template CombinedEdgeMap<
3.1076 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
3.1077 - ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
3.1078 + ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > > {
3.1079 public:
3.1080 - typedef SubBidirGraphAdaptor<
3.1081 - Graph,
3.1082 - ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
3.1083 - ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
3.1084 +
3.1085 + typedef UndirGraphAdaptor<Graph> UGraph;
3.1086 +
3.1087 + typedef ResForwardFilter<Graph, Number, CapacityMap, FlowMap>
3.1088 + ForwardFilter;
3.1089 +
3.1090 + typedef ResBackwardFilter<Graph, Number, CapacityMap, FlowMap>
3.1091 + BackwardFilter;
3.1092 +
3.1093 + typedef typename UGraph::
3.1094 + template CombinedEdgeMap<ForwardFilter, BackwardFilter>
3.1095 + EdgeFilter;
3.1096 +
3.1097 + typedef EdgeSubGraphAdaptor<UGraph, EdgeFilter> Parent;
3.1098 +
3.1099 protected:
3.1100 +
3.1101 const CapacityMap* capacity;
3.1102 FlowMap* flow;
3.1103 - ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
3.1104 - ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
3.1105 - ResGraphAdaptor() : Parent(),
3.1106 - capacity(0), flow(0) { }
3.1107 +
3.1108 + UGraph ugraph;
3.1109 + ForwardFilter forward_filter;
3.1110 + BackwardFilter backward_filter;
3.1111 + EdgeFilter edge_filter;
3.1112 +
3.1113 void setCapacityMap(const CapacityMap& _capacity) {
3.1114 capacity=&_capacity;
3.1115 forward_filter.setCapacity(_capacity);
3.1116 backward_filter.setCapacity(_capacity);
3.1117 }
3.1118 +
3.1119 void setFlowMap(FlowMap& _flow) {
3.1120 flow=&_flow;
3.1121 forward_filter.setFlow(_flow);
3.1122 backward_filter.setFlow(_flow);
3.1123 }
3.1124 +
3.1125 public:
3.1126 +
3.1127 ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
3.1128 - FlowMap& _flow) :
3.1129 - Parent(), capacity(&_capacity), flow(&_flow),
3.1130 - forward_filter(/*_graph,*/ _capacity, _flow),
3.1131 - backward_filter(/*_graph,*/ _capacity, _flow) {
3.1132 - Parent::setGraph(_graph);
3.1133 - Parent::setForwardFilterMap(forward_filter);
3.1134 - Parent::setBackwardFilterMap(backward_filter);
3.1135 + FlowMap& _flow)
3.1136 + : Parent(), capacity(&_capacity), flow(&_flow),
3.1137 + ugraph(_graph),
3.1138 + forward_filter(_capacity, _flow),
3.1139 + backward_filter(_capacity, _flow),
3.1140 + edge_filter(forward_filter, backward_filter) {
3.1141 + Parent::setGraph(ugraph);
3.1142 + Parent::setEdgeFilterMap(edge_filter);
3.1143 }
3.1144
3.1145 typedef typename Parent::Edge Edge;
3.1146
3.1147 void augment(const Edge& e, Number a) const {
3.1148 - if (Parent::forward(e))
3.1149 + if (UGraph::direction(e)) {
3.1150 flow->set(e, (*flow)[e]+a);
3.1151 - else
3.1152 + } else {
3.1153 flow->set(e, (*flow)[e]-a);
3.1154 + }
3.1155 }
3.1156
3.1157 + static bool forward(const Edge& e) {
3.1158 + return UGraph::direction(e);
3.1159 + }
3.1160 +
3.1161 + static bool backward(const Edge& e) {
3.1162 + return !UGraph::direction(e);
3.1163 + }
3.1164 +
3.1165 + static Edge forward(const typename Graph::Edge& e) {
3.1166 + return UGraph::direct(e, true);
3.1167 + }
3.1168 +
3.1169 + static Edge backward(const typename Graph::Edge& e) {
3.1170 + return UGraph::direct(e, false);
3.1171 + }
3.1172 +
3.1173 +
3.1174 /// \brief Residual capacity map.
3.1175 ///
3.1176 /// In generic residual graphs the residual capacity can be obtained
3.1177 /// as a map.
3.1178 class ResCap {
3.1179 protected:
3.1180 - const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
3.1181 + const ResGraphAdaptor* res_graph;
3.1182 public:
3.1183 typedef Number Value;
3.1184 typedef Edge Key;
3.1185 - ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&
3.1186 - _res_graph) : res_graph(&_res_graph) { }
3.1187 + ResCap(const ResGraphAdaptor& _res_graph)
3.1188 + : res_graph(&_res_graph) {}
3.1189 +
3.1190 Number operator[](const Edge& e) const {
3.1191 - if (res_graph->forward(e))
3.1192 + if (ResGraphAdaptor::direction(e))
3.1193 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
3.1194 else
3.1195 return (*(res_graph->flow))[e];
3.1196 }
3.1197 +
3.1198 };
3.1199
3.1200 - // KEEP_MAPS(Parent, ResGraphAdaptor);
3.1201 };
3.1202
3.1203
4.1 --- a/lemon/list_graph.h Wed Mar 01 10:17:25 2006 +0000
4.2 +++ b/lemon/list_graph.h Wed Mar 01 10:25:30 2006 +0000
4.3 @@ -962,8 +962,8 @@
4.4 /// \brief A smart bipartite undirected graph class.
4.5 ///
4.6 /// This is a bipartite undirected graph implementation.
4.7 - /// Except from this it conforms to
4.8 - /// the \ref concept::BpUGraph "BpUGraph" concept.
4.9 + /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph"
4.10 + /// concept.
4.11 /// \sa concept::BpUGraph.
4.12 ///
4.13 class ListBpUGraph : public ExtendedListBpUGraphBase {};
5.1 --- a/lemon/ugraph_adaptor.h Wed Mar 01 10:17:25 2006 +0000
5.2 +++ b/lemon/ugraph_adaptor.h Wed Mar 01 10:25:30 2006 +0000
5.3 @@ -42,9 +42,6 @@
5.4 ///
5.5 /// \brief Base type for the Graph Adaptors
5.6 ///
5.7 - /// \warning Graph adaptors are in even more experimental state than the
5.8 - /// other parts of the lib. Use them at you own risk.
5.9 - ///
5.10 /// This is the base type for most of LEMON graph adaptors.
5.11 /// This class implements a trivial graph adaptor i.e. it only wraps the
5.12 /// functions and types of the graph. The purpose of this class is to
5.13 @@ -93,7 +90,6 @@
5.14 void nextOut(Edge& i) const { graph->nextOut(i); }
5.15 void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }
5.16
5.17 -
5.18 Node source(const UEdge& e) const { return graph->source(e); }
5.19 Node target(const UEdge& e) const { return graph->target(e); }
5.20
5.21 @@ -111,7 +107,6 @@
5.22 const Edge& prev = INVALID) {
5.23 return graph->findEdge(source, target, prev);
5.24 }
5.25 -
5.26 UEdge findUEdge(const Node& source, const Node& target,
5.27 const UEdge& prev = INVALID) {
5.28 return graph->findUEdge(source, target, prev);
5.29 @@ -132,18 +127,36 @@
5.30
5.31 bool direction(const Edge& e) const { return graph->direction(e); }
5.32 Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
5.33 - Edge direct(const UEdge& e, const Node& n) const {
5.34 - return graph->direct(e, n);
5.35 +
5.36 + int maxNodeId() const {
5.37 + return graph->maxNodeId();
5.38 }
5.39
5.40 - Node oppositeNode(const Node& n, const Edge& e) const {
5.41 - return graph->oppositeNode(n, e);
5.42 + int maxEdgeId() const {
5.43 + return graph->maxEdgeId();
5.44 }
5.45
5.46 - Edge oppositeEdge(const Edge& e) const {
5.47 - return graph->oppositeEdge(e);
5.48 + int maxUEdgeId() const {
5.49 + return graph->maxEdgeId();
5.50 }
5.51
5.52 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
5.53 +
5.54 + NodeNotifier& getNotifier(Node) const {
5.55 + return graph->getNotifier(Node());
5.56 + }
5.57 +
5.58 + typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
5.59 +
5.60 + EdgeNotifier& getNotifier(Edge) const {
5.61 + return graph->getNotifier(Edge());
5.62 + }
5.63 +
5.64 + typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;
5.65 +
5.66 + UEdgeNotifier& getNotifier(UEdge) const {
5.67 + return graph->getNotifier(UEdge());
5.68 + }
5.69
5.70 template <typename _Value>
5.71 class NodeMap : public Graph::template NodeMap<_Value> {
5.72 @@ -379,6 +392,30 @@
5.73
5.74 typedef False NodeNumTag;
5.75 typedef False EdgeNumTag;
5.76 +
5.77 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
5.78 + Edge findEdge(const Node& source, const Node& target,
5.79 + const Edge& prev = INVALID) {
5.80 + if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
5.81 + return INVALID;
5.82 + }
5.83 + Edge edge = Parent::findEdge(source, target, prev);
5.84 + while (edge != INVALID && !(*uedge_filter_map)[edge]) {
5.85 + edge = Parent::findEdge(source, target, edge);
5.86 + }
5.87 + return edge;
5.88 + }
5.89 + UEdge findUEdge(const Node& source, const Node& target,
5.90 + const UEdge& prev = INVALID) {
5.91 + if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
5.92 + return INVALID;
5.93 + }
5.94 + UEdge uedge = Parent::findUEdge(source, target, prev);
5.95 + while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
5.96 + uedge = Parent::findUEdge(source, target, uedge);
5.97 + }
5.98 + return uedge;
5.99 + }
5.100 };
5.101
5.102 template <typename _UGraph, typename NodeFilterMap, typename UEdgeFilterMap>
5.103 @@ -504,6 +541,24 @@
5.104
5.105 typedef False NodeNumTag;
5.106 typedef False EdgeNumTag;
5.107 +
5.108 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
5.109 + Edge findEdge(const Node& source, const Node& target,
5.110 + const Edge& prev = INVALID) {
5.111 + Edge edge = Parent::findEdge(source, target, prev);
5.112 + while (edge != INVALID && !(*uedge_filter_map)[edge]) {
5.113 + edge = Parent::findEdge(source, target, edge);
5.114 + }
5.115 + return edge;
5.116 + }
5.117 + UEdge findUEdge(const Node& source, const Node& target,
5.118 + const UEdge& prev = INVALID) {
5.119 + UEdge uedge = Parent::findUEdge(source, target, prev);
5.120 + while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
5.121 + uedge = Parent::findUEdge(source, target, uedge);
5.122 + }
5.123 + return uedge;
5.124 + }
5.125 };
5.126
5.127 /// \ingroup graph_adaptors
5.128 @@ -581,7 +636,6 @@
5.129 ///
5.130 /// \brief An adaptor for hiding nodes from an undirected graph.
5.131 ///
5.132 - ///
5.133 /// An adaptor for hiding nodes from an undirected graph.
5.134 /// This adaptor specializes SubUGraphAdaptor in the way that only
5.135 /// the node-set
5.136 @@ -598,6 +652,11 @@
5.137 typedef _UGraph Graph;
5.138 protected:
5.139 ConstMap<typename _UGraph::UEdge, bool> const_true_map;
5.140 +
5.141 + NodeSubUGraphAdaptor() : const_true_map(true) {
5.142 + Parent::setUEdgeFilterMap(const_true_map);
5.143 + }
5.144 +
5.145 public:
5.146 NodeSubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
5.147 Parent(), const_true_map(true) {
5.148 @@ -639,6 +698,11 @@
5.149 typedef _UGraph Graph;
5.150 protected:
5.151 ConstMap<typename Graph::Node, bool> const_true_map;
5.152 +
5.153 + EdgeSubUGraphAdaptor() : const_true_map(true) {
5.154 + Parent::setNodeFilterMap(const_true_map);
5.155 + }
5.156 +
5.157 public:
5.158 EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) :
5.159 Parent(), const_true_map(true) {
5.160 @@ -670,6 +734,10 @@
5.161 typedef typename _UGraph::Node Node;
5.162 typedef typename _UGraph::UEdge Edge;
5.163
5.164 + void reverseEdge(const Edge& edge) {
5.165 + direction->set(edge, !(*direction)[edge]);
5.166 + }
5.167 +
5.168 void first(Node& i) const { graph->first(i); }
5.169 void first(Edge& i) const { graph->first(i); }
5.170 void firstIn(Edge& i, const Node& n) const {
5.171 @@ -746,10 +814,26 @@
5.172 int id(const Node& v) const { return graph->id(v); }
5.173 int id(const Edge& e) const { return graph->id(e); }
5.174
5.175 - void reverseEdge(const Edge& edge) {
5.176 - direction->set(edge, !(*direction)[edge]);
5.177 + int maxNodeId() const {
5.178 + return graph->maxNodeId();
5.179 }
5.180
5.181 + int maxEdgeId() const {
5.182 + return graph->maxEdgeId();
5.183 + }
5.184 +
5.185 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
5.186 +
5.187 + NodeNotifier& getNotifier(Node) const {
5.188 + return graph->getNotifier(Node());
5.189 + }
5.190 +
5.191 + typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
5.192 +
5.193 + EdgeNotifier& getNotifier(Edge) const {
5.194 + return graph->getNotifier(Edge());
5.195 + }
5.196 +
5.197 template <typename _Value>
5.198 class NodeMap : public _UGraph::template NodeMap<_Value> {
5.199 public:
5.200 @@ -788,7 +872,8 @@
5.201
5.202
5.203 /// \ingroup graph_adaptors
5.204 - /// \brief A directed graph is made from a undirected graph by an adaptor
5.205 + ///
5.206 + /// \brief A directed graph is made from an undirected graph by an adaptor
5.207 ///
5.208 /// This adaptor gives a direction for each uedge in the undirected graph.
5.209 /// The direction of the edges stored in the DirectionMap. This map is
6.1 --- a/test/graph_adaptor_test.cc Wed Mar 01 10:17:25 2006 +0000
6.2 +++ b/test/graph_adaptor_test.cc Wed Mar 01 10:25:30 2006 +0000
6.3 @@ -58,9 +58,6 @@
6.4 checkConcept<StaticGraph, EdgeSubGraphAdaptor<Graph,
6.5 Graph::EdgeMap<bool> > >();
6.6
6.7 - checkConcept<StaticGraph, SubBidirGraphAdaptor<Graph,
6.8 - Graph::EdgeMap<bool>, Graph::EdgeMap<bool> > >();
6.9 - // checkConcept<StaticGraph, BidirGraph<Graph> >();
6.10 checkConcept<StaticGraph, ResGraphAdaptor<Graph, int,
6.11 Graph::EdgeMap<int>, Graph::EdgeMap<int> > >();
6.12