1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/ugraph_adaptor.h Wed Feb 22 18:26:56 2006 +0000
1.3 @@ -0,0 +1,803 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2006
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_UGRAPH_ADAPTOR_H
1.23 +#define LEMON_UGRAPH_ADAPTOR_H
1.24 +
1.25 +///\ingroup graph_adaptors
1.26 +///\file
1.27 +///\brief Several graph adaptors.
1.28 +///
1.29 +///This file contains several useful ugraph adaptor functions.
1.30 +///
1.31 +///\author Balazs Dezso
1.32 +
1.33 +#include <lemon/invalid.h>
1.34 +#include <lemon/maps.h>
1.35 +
1.36 +#include <lemon/bits/graph_adaptor_extender.h>
1.37 +
1.38 +#include <lemon/traits.h>
1.39 +
1.40 +#include <iostream>
1.41 +
1.42 +namespace lemon {
1.43 +
1.44 + /// \ingroup graph_adaptors
1.45 + ///
1.46 + /// \brief Base type for the Graph Adaptors
1.47 + ///
1.48 + /// \warning Graph adaptors are in even more experimental state than the
1.49 + /// other parts of the lib. Use them at you own risk.
1.50 + ///
1.51 + /// This is the base type for most of LEMON graph adaptors.
1.52 + /// This class implements a trivial graph adaptor i.e. it only wraps the
1.53 + /// functions and types of the graph. The purpose of this class is to
1.54 + /// make easier implementing graph adaptors. E.g. if an adaptor is
1.55 + /// considered which differs from the wrapped graph only in some of its
1.56 + /// functions or types, then it can be derived from GraphAdaptor, and only
1.57 + /// the differences should be implemented.
1.58 + ///
1.59 + /// \author Balazs Dezso
1.60 + template<typename _UGraph>
1.61 + class UGraphAdaptorBase {
1.62 + public:
1.63 + typedef _UGraph Graph;
1.64 + typedef Graph ParentGraph;
1.65 +
1.66 + protected:
1.67 + Graph* graph;
1.68 +
1.69 + UGraphAdaptorBase() : graph(0) {}
1.70 +
1.71 + void setGraph(Graph& _graph) { graph=&_graph; }
1.72 +
1.73 + Graph& getGraph() { return *graph; }
1.74 + const Graph& getGraph() const { return *graph; }
1.75 +
1.76 + public:
1.77 + UGraphAdaptorBase(Graph& _graph) : graph(&_graph) {}
1.78 +
1.79 + typedef typename Graph::Node Node;
1.80 + typedef typename Graph::Edge Edge;
1.81 + typedef typename Graph::UEdge UEdge;
1.82 +
1.83 + void first(Node& i) const { graph->first(i); }
1.84 + void first(Edge& i) const { graph->first(i); }
1.85 + void first(UEdge& i) const { graph->first(i); }
1.86 + void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
1.87 + void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
1.88 + void firstInc(UEdge &i, bool &d, const Node &n) const {
1.89 + graph->firstInc(i, d, n);
1.90 + }
1.91 +
1.92 + void next(Node& i) const { graph->next(i); }
1.93 + void next(Edge& i) const { graph->next(i); }
1.94 + void next(UEdge& i) const { graph->next(i); }
1.95 + void nextIn(Edge& i) const { graph->nextIn(i); }
1.96 + void nextOut(Edge& i) const { graph->nextOut(i); }
1.97 + void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }
1.98 +
1.99 +
1.100 + Node source(const UEdge& e) const { return graph->source(e); }
1.101 + Node target(const UEdge& e) const { return graph->target(e); }
1.102 +
1.103 + Node source(const Edge& e) const { return graph->source(e); }
1.104 + Node target(const Edge& e) const { return graph->target(e); }
1.105 +
1.106 + typedef NodeNumTagIndicator<Graph> NodeNumTag;
1.107 + int nodeNum() const { return graph->nodeNum(); }
1.108 +
1.109 + typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
1.110 + int edgeNum() const { return graph->edgeNum(); }
1.111 +
1.112 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1.113 + Edge findEdge(const Node& source, const Node& target,
1.114 + const Edge& prev = INVALID) {
1.115 + return graph->findEdge(source, target, prev);
1.116 + }
1.117 +
1.118 + UEdge findUEdge(const Node& source, const Node& target,
1.119 + const UEdge& prev = INVALID) {
1.120 + return graph->findUEdge(source, target, prev);
1.121 + }
1.122 +
1.123 + Node addNode() const { return graph->addNode(); }
1.124 + UEdge addEdge(const Node& source, const Node& target) const {
1.125 + return graph->addEdge(source, target);
1.126 + }
1.127 +
1.128 + void erase(const Node& i) const { graph->erase(i); }
1.129 + void erase(const Edge& i) const { graph->erase(i); }
1.130 +
1.131 + void clear() const { graph->clear(); }
1.132 +
1.133 + int id(const Node& v) const { return graph->id(v); }
1.134 + int id(const UEdge& e) const { return graph->id(e); }
1.135 +
1.136 + bool direction(const Edge& e) const { return graph->direction(e); }
1.137 + Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
1.138 + Edge direct(const UEdge& e, const Node& n) const {
1.139 + return graph->direct(e, n);
1.140 + }
1.141 +
1.142 + Node oppositeNode(const Node& n, const Edge& e) const {
1.143 + return graph->oppositeNode(n, e);
1.144 + }
1.145 +
1.146 + Edge oppositeEdge(const Edge& e) const {
1.147 + return graph->oppositeEdge(e);
1.148 + }
1.149 +
1.150 +
1.151 + template <typename _Value>
1.152 + class NodeMap : public Graph::template NodeMap<_Value> {
1.153 + public:
1.154 + typedef typename Graph::template NodeMap<_Value> Parent;
1.155 + explicit NodeMap(const UGraphAdaptorBase<Graph>& ga)
1.156 + : Parent(*ga.graph) {}
1.157 + NodeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
1.158 + : Parent(*ga.graph, value) {}
1.159 +
1.160 + NodeMap& operator=(const NodeMap& cmap) {
1.161 + return operator=<NodeMap>(cmap);
1.162 + }
1.163 +
1.164 + template <typename CMap>
1.165 + NodeMap& operator=(const CMap& cmap) {
1.166 + checkConcept<concept::ReadMap<Node, _Value>, CMap>();
1.167 + const typename Parent::Graph* graph = Parent::getGraph();
1.168 + Node it;
1.169 + for (graph->first(it); it != INVALID; graph->next(it)) {
1.170 + Parent::set(it, cmap[it]);
1.171 + }
1.172 + return *this;
1.173 + }
1.174 + };
1.175 +
1.176 + template <typename _Value>
1.177 + class EdgeMap : public Graph::template EdgeMap<_Value> {
1.178 + public:
1.179 + typedef typename Graph::template EdgeMap<_Value> Parent;
1.180 + explicit EdgeMap(const UGraphAdaptorBase<Graph>& ga)
1.181 + : Parent(*ga.graph) {}
1.182 + EdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
1.183 + : Parent(*ga.graph, value) {}
1.184 +
1.185 + EdgeMap& operator=(const EdgeMap& cmap) {
1.186 + return operator=<EdgeMap>(cmap);
1.187 + }
1.188 +
1.189 + template <typename CMap>
1.190 + EdgeMap& operator=(const CMap& cmap) {
1.191 + checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
1.192 + const typename Parent::Graph* graph = Parent::getGraph();
1.193 + Edge it;
1.194 + for (graph->first(it); it != INVALID; graph->next(it)) {
1.195 + Parent::set(it, cmap[it]);
1.196 + }
1.197 + return *this;
1.198 + }
1.199 + };
1.200 +
1.201 + template <typename _Value>
1.202 + class UEdgeMap : public Graph::template UEdgeMap<_Value> {
1.203 + public:
1.204 + typedef typename Graph::template UEdgeMap<_Value> Parent;
1.205 + explicit UEdgeMap(const UGraphAdaptorBase<Graph>& ga)
1.206 + : Parent(*ga.graph) {}
1.207 + UEdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
1.208 + : Parent(*ga.graph, value) {}
1.209 +
1.210 + UEdgeMap& operator=(const UEdgeMap& cmap) {
1.211 + return operator=<UEdgeMap>(cmap);
1.212 + }
1.213 +
1.214 + template <typename CMap>
1.215 + UEdgeMap& operator=(const CMap& cmap) {
1.216 + checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
1.217 + const typename Parent::Graph* graph = Parent::getGraph();
1.218 + UEdge it;
1.219 + for (graph->first(it); it != INVALID; graph->next(it)) {
1.220 + Parent::set(it, cmap[it]);
1.221 + }
1.222 + return *this;
1.223 + }
1.224 + };
1.225 +
1.226 + };
1.227 +
1.228 + /// \ingroup graph_adaptors
1.229 + template <typename _UGraph>
1.230 + class UGraphAdaptor
1.231 + : public UGraphAdaptorExtender< UGraphAdaptorBase<_UGraph> > {
1.232 + public:
1.233 + typedef _UGraph Graph;
1.234 + typedef UGraphAdaptorExtender<UGraphAdaptorBase<_UGraph> > Parent;
1.235 + protected:
1.236 + UGraphAdaptor() : Parent() {}
1.237 +
1.238 + public:
1.239 + explicit UGraphAdaptor(Graph& _graph) { setGraph(_graph); }
1.240 + };
1.241 +
1.242 + template <typename _UGraph, typename NodeFilterMap,
1.243 + typename UEdgeFilterMap, bool checked = true>
1.244 + class SubUGraphAdaptorBase : public UGraphAdaptorBase<_UGraph> {
1.245 + public:
1.246 + typedef _UGraph Graph;
1.247 + typedef UGraphAdaptorBase<_UGraph> Parent;
1.248 + protected:
1.249 +
1.250 + NodeFilterMap* node_filter_map;
1.251 + UEdgeFilterMap* uedge_filter_map;
1.252 +
1.253 + SubUGraphAdaptorBase()
1.254 + : Parent(), node_filter_map(0), uedge_filter_map(0) { }
1.255 +
1.256 + void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
1.257 + node_filter_map=&_node_filter_map;
1.258 + }
1.259 + void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {
1.260 + uedge_filter_map=&_uedge_filter_map;
1.261 + }
1.262 +
1.263 + public:
1.264 +
1.265 + typedef typename Parent::Node Node;
1.266 + typedef typename Parent::Edge Edge;
1.267 + typedef typename Parent::UEdge UEdge;
1.268 +
1.269 + void first(Node& i) const {
1.270 + Parent::first(i);
1.271 + while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
1.272 + }
1.273 +
1.274 + void first(Edge& i) const {
1.275 + Parent::first(i);
1.276 + while (i!=INVALID && (!(*uedge_filter_map)[i]
1.277 + || !(*node_filter_map)[Parent::source(i)]
1.278 + || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
1.279 + }
1.280 +
1.281 + void first(UEdge& i) const {
1.282 + Parent::first(i);
1.283 + while (i!=INVALID && (!(*uedge_filter_map)[i]
1.284 + || !(*node_filter_map)[Parent::source(i)]
1.285 + || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
1.286 + }
1.287 +
1.288 + void firstIn(Edge& i, const Node& n) const {
1.289 + Parent::firstIn(i, n);
1.290 + while (i!=INVALID && (!(*uedge_filter_map)[i]
1.291 + || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
1.292 + }
1.293 +
1.294 + void firstOut(Edge& i, const Node& n) const {
1.295 + Parent::firstOut(i, n);
1.296 + while (i!=INVALID && (!(*uedge_filter_map)[i]
1.297 + || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
1.298 + }
1.299 +
1.300 + void firstInc(UEdge& i, bool& d, const Node& n) const {
1.301 + Parent::firstInc(i, d, n);
1.302 + while (i!=INVALID && (!(*uedge_filter_map)[i]
1.303 + || !(*node_filter_map)[Parent::target(i)])) Parent::nextInc(i, d);
1.304 + }
1.305 +
1.306 + void next(Node& i) const {
1.307 + Parent::next(i);
1.308 + while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
1.309 + }
1.310 +
1.311 + void next(Edge& i) const {
1.312 + Parent::next(i);
1.313 + while (i!=INVALID && (!(*uedge_filter_map)[i]
1.314 + || !(*node_filter_map)[Parent::source(i)]
1.315 + || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
1.316 + }
1.317 +
1.318 + void next(UEdge& i) const {
1.319 + Parent::next(i);
1.320 + while (i!=INVALID && (!(*uedge_filter_map)[i]
1.321 + || !(*node_filter_map)[Parent::source(i)]
1.322 + || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
1.323 + }
1.324 +
1.325 + void nextIn(Edge& i) const {
1.326 + Parent::nextIn(i);
1.327 + while (i!=INVALID && (!(*uedge_filter_map)[i]
1.328 + || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
1.329 + }
1.330 +
1.331 + void nextOut(Edge& i) const {
1.332 + Parent::nextOut(i);
1.333 + while (i!=INVALID && (!(*uedge_filter_map)[i]
1.334 + || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
1.335 + }
1.336 +
1.337 + void nextInc(UEdge& i, bool& d) const {
1.338 + Parent::nextInc(i, d);
1.339 + while (i!=INVALID && (!(*uedge_filter_map)[i]
1.340 + || !(*node_filter_map)[Parent::source(i)])) Parent::nextInc(i, d);
1.341 + }
1.342 +
1.343 + ///\e
1.344 +
1.345 + /// This function hides \c n in the graph, i.e. the iteration
1.346 + /// jumps over it. This is done by simply setting the value of \c n
1.347 + /// to be false in the corresponding node-map.
1.348 + void hide(const Node& n) const { node_filter_map->set(n, false); }
1.349 +
1.350 + ///\e
1.351 +
1.352 + /// This function hides \c e in the graph, i.e. the iteration
1.353 + /// jumps over it. This is done by simply setting the value of \c e
1.354 + /// to be false in the corresponding edge-map.
1.355 + void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
1.356 +
1.357 + ///\e
1.358 +
1.359 + /// The value of \c n is set to be true in the node-map which stores
1.360 + /// hide information. If \c n was hidden previuosly, then it is shown
1.361 + /// again
1.362 + void unHide(const Node& n) const { node_filter_map->set(n, true); }
1.363 +
1.364 + ///\e
1.365 +
1.366 + /// The value of \c e is set to be true in the edge-map which stores
1.367 + /// hide information. If \c e was hidden previuosly, then it is shown
1.368 + /// again
1.369 + void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
1.370 +
1.371 + /// Returns true if \c n is hidden.
1.372 +
1.373 + ///\e
1.374 + ///
1.375 + bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
1.376 +
1.377 + /// Returns true if \c n is hidden.
1.378 +
1.379 + ///\e
1.380 + ///
1.381 + bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
1.382 +
1.383 + typedef False NodeNumTag;
1.384 + typedef False EdgeNumTag;
1.385 + };
1.386 +
1.387 + template <typename _UGraph, typename NodeFilterMap, typename UEdgeFilterMap>
1.388 + class SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, false>
1.389 + : public UGraphAdaptorBase<_UGraph> {
1.390 + public:
1.391 + typedef _UGraph Graph;
1.392 + typedef UGraphAdaptorBase<_UGraph> Parent;
1.393 + protected:
1.394 + NodeFilterMap* node_filter_map;
1.395 + UEdgeFilterMap* uedge_filter_map;
1.396 + SubUGraphAdaptorBase() : Parent(),
1.397 + node_filter_map(0), uedge_filter_map(0) { }
1.398 +
1.399 + void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
1.400 + node_filter_map=&_node_filter_map;
1.401 + }
1.402 + void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {
1.403 + uedge_filter_map=&_uedge_filter_map;
1.404 + }
1.405 +
1.406 + public:
1.407 +
1.408 + typedef typename Parent::Node Node;
1.409 + typedef typename Parent::Edge Edge;
1.410 + typedef typename Parent::UEdge UEdge;
1.411 +
1.412 + void first(Node& i) const {
1.413 + Parent::first(i);
1.414 + while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
1.415 + }
1.416 +
1.417 + void first(Edge& i) const {
1.418 + Parent::first(i);
1.419 + while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
1.420 + }
1.421 +
1.422 + void first(UEdge& i) const {
1.423 + Parent::first(i);
1.424 + while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
1.425 + }
1.426 +
1.427 + void firstIn(Edge& i, const Node& n) const {
1.428 + Parent::firstIn(i, n);
1.429 + while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i);
1.430 + }
1.431 +
1.432 + void firstOut(Edge& i, const Node& n) const {
1.433 + Parent::firstOut(i, n);
1.434 + while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i);
1.435 + }
1.436 +
1.437 + void firstInc(UEdge& i, bool& d, const Node& n) const {
1.438 + Parent::firstInc(i, d, n);
1.439 + while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d);
1.440 + }
1.441 +
1.442 + void next(Node& i) const {
1.443 + Parent::next(i);
1.444 + while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
1.445 + }
1.446 + void next(Edge& i) const {
1.447 + Parent::next(i);
1.448 + while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
1.449 + }
1.450 + void next(UEdge& i) const {
1.451 + Parent::next(i);
1.452 + while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
1.453 + }
1.454 + void nextIn(Edge& i) const {
1.455 + Parent::nextIn(i);
1.456 + while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i);
1.457 + }
1.458 +
1.459 + void nextOut(Edge& i) const {
1.460 + Parent::nextOut(i);
1.461 + while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i);
1.462 + }
1.463 + void nextInc(UEdge& i, bool& d) const {
1.464 + Parent::nextInc(i, d);
1.465 + while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d);
1.466 + }
1.467 +
1.468 + ///\e
1.469 +
1.470 + /// This function hides \c n in the graph, i.e. the iteration
1.471 + /// jumps over it. This is done by simply setting the value of \c n
1.472 + /// to be false in the corresponding node-map.
1.473 + void hide(const Node& n) const { node_filter_map->set(n, false); }
1.474 +
1.475 + ///\e
1.476 +
1.477 + /// This function hides \c e in the graph, i.e. the iteration
1.478 + /// jumps over it. This is done by simply setting the value of \c e
1.479 + /// to be false in the corresponding edge-map.
1.480 + void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
1.481 +
1.482 + ///\e
1.483 +
1.484 + /// The value of \c n is set to be true in the node-map which stores
1.485 + /// hide information. If \c n was hidden previuosly, then it is shown
1.486 + /// again
1.487 + void unHide(const Node& n) const { node_filter_map->set(n, true); }
1.488 +
1.489 + ///\e
1.490 +
1.491 + /// The value of \c e is set to be true in the edge-map which stores
1.492 + /// hide information. If \c e was hidden previuosly, then it is shown
1.493 + /// again
1.494 + void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
1.495 +
1.496 + /// Returns true if \c n is hidden.
1.497 +
1.498 + ///\e
1.499 + ///
1.500 + bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
1.501 +
1.502 + /// Returns true if \c n is hidden.
1.503 +
1.504 + ///\e
1.505 + ///
1.506 + bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
1.507 +
1.508 + typedef False NodeNumTag;
1.509 + typedef False EdgeNumTag;
1.510 + };
1.511 +
1.512 + /// \ingroup graph_adaptors
1.513 + ///
1.514 + /// \brief A graph adaptor for hiding nodes and edges from an undirected
1.515 + /// graph.
1.516 + ///
1.517 + /// \warning Graph adaptors are in even more experimental state than the
1.518 + /// other parts of the lib. Use them at you own risk.
1.519 + ///
1.520 + /// SubUGraphAdaptor shows the undirected graph with filtered node-set and
1.521 + /// edge-set. If the \c checked parameter is true then it filters the edgeset
1.522 + /// to do not get invalid edges without source or target.
1.523 + ///
1.524 + /// If the \c checked template parameter is false then we have to note that
1.525 + /// the node-iterator cares only the filter on the node-set, and the
1.526 + /// edge-iterator cares only the filter on the edge-set.
1.527 + /// This way the edge-map
1.528 + /// should filter all edges which's source or target is filtered by the
1.529 + /// node-filter.
1.530 + ///
1.531 + /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
1.532 + /// \c Graph::Node that is why \c g.id(n) can be applied.
1.533 + ///
1.534 + /// For examples see also the documentation of NodeSubUGraphAdaptor and
1.535 + /// EdgeSubUGraphAdaptor.
1.536 + ///
1.537 + /// \author Marton Makai
1.538 +
1.539 + template<typename _UGraph, typename NodeFilterMap,
1.540 + typename UEdgeFilterMap, bool checked = true>
1.541 + class SubUGraphAdaptor :
1.542 + public UGraphAdaptorExtender<
1.543 + SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, checked> > {
1.544 + public:
1.545 + typedef _UGraph Graph;
1.546 + typedef UGraphAdaptorExtender<
1.547 + SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap> > Parent;
1.548 + protected:
1.549 + SubUGraphAdaptor() { }
1.550 + public:
1.551 + SubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map,
1.552 + UEdgeFilterMap& _uedge_filter_map) {
1.553 + setGraph(_graph);
1.554 + setNodeFilterMap(_node_filter_map);
1.555 + setUEdgeFilterMap(_uedge_filter_map);
1.556 + }
1.557 + };
1.558 +
1.559 + /// \ingroup graph_adaptors
1.560 + ///
1.561 + /// \brief An adaptor for hiding nodes from an undorected graph.
1.562 + ///
1.563 + /// \warning Graph adaptors are in even more experimental state
1.564 + /// than the other
1.565 + /// parts of the lib. Use them at you own risk.
1.566 + ///
1.567 + /// An adaptor for hiding nodes from an undirected graph.
1.568 + /// This adaptor specializes SubUGraphAdaptor in the way that only
1.569 + /// the node-set
1.570 + /// can be filtered. In usual case the checked parameter is true, we get the
1.571 + /// induced subgraph. But if the checked parameter is false then we can only
1.572 + /// filter only isolated nodes.
1.573 + /// \author Marton Makai
1.574 + template<typename _UGraph, typename NodeFilterMap, bool checked = true>
1.575 + class NodeSubUGraphAdaptor :
1.576 + public SubUGraphAdaptor<_UGraph, NodeFilterMap,
1.577 + ConstMap<typename _UGraph::UEdge, bool>, checked> {
1.578 + public:
1.579 + typedef SubUGraphAdaptor<_UGraph, NodeFilterMap,
1.580 + ConstMap<typename _UGraph::UEdge, bool> > Parent;
1.581 + typedef _UGraph Graph;
1.582 + protected:
1.583 + ConstMap<typename _UGraph::Edge, bool> const_true_map;
1.584 + public:
1.585 + NodeSubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
1.586 + Parent(), const_true_map(true) {
1.587 + Parent::setGraph(_graph);
1.588 + Parent::setNodeFilterMap(_node_filter_map);
1.589 + Parent::setUEdgeFilterMap(const_true_map);
1.590 + }
1.591 + };
1.592 +
1.593 + template<typename UGraph, typename NodeFilterMap>
1.594 + NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>
1.595 + nodeSubUGraphAdaptor(const UGraph& graph, NodeFilterMap& nfm) {
1.596 + return NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>(graph, nfm);
1.597 + }
1.598 +
1.599 + template<typename UGraph, typename NodeFilterMap>
1.600 + NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>
1.601 + nodeSubUGraphAdaptor(const UGraph& graph, const NodeFilterMap& nfm) {
1.602 + return NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>(graph, nfm);
1.603 + }
1.604 +
1.605 +
1.606 + /// \brief An adaptor for hiding undirected edges from an undirected graph.
1.607 + ///
1.608 + /// \warning Graph adaptors are in even more experimental state
1.609 + /// than the other parts of the lib. Use them at you own risk.
1.610 + ///
1.611 + /// An adaptor for hiding undirected edges from an undirected graph.
1.612 + /// This adaptor specializes SubUGraphAdaptor in the way that
1.613 + /// only the edge-set
1.614 + /// can be filtered.
1.615 + ///
1.616 + ///\author Marton Makai
1.617 + template<typename _UGraph, typename UEdgeFilterMap>
1.618 + class EdgeSubUGraphAdaptor :
1.619 + public SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
1.620 + UEdgeFilterMap, false> {
1.621 + public:
1.622 + typedef SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
1.623 + UEdgeFilterMap, false> Parent;
1.624 + typedef _UGraph Graph;
1.625 + protected:
1.626 + ConstMap<typename Graph::Node, bool> const_true_map;
1.627 + public:
1.628 + EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) :
1.629 + Parent(), const_true_map(true) {
1.630 + Parent::setGraph(_graph);
1.631 + Parent::setNodeFilterMap(const_true_map);
1.632 + Parent::setUEdgeFilterMap(_uedge_filter_map);
1.633 + }
1.634 + };
1.635 +
1.636 + template<typename UGraph, typename EdgeFilterMap>
1.637 + EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>
1.638 + edgeSubUGraphAdaptor(const UGraph& graph, EdgeFilterMap& efm) {
1.639 + return EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>(graph, efm);
1.640 + }
1.641 +
1.642 + template<typename UGraph, typename EdgeFilterMap>
1.643 + EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>
1.644 + edgeSubUGraphAdaptor(const UGraph& graph, const EdgeFilterMap& efm) {
1.645 + return EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>(graph, efm);
1.646 + }
1.647 +
1.648 + template <typename _UGraph, typename _DirectionMap>
1.649 + class DirectUGraphAdaptorBase {
1.650 + public:
1.651 +
1.652 + typedef _UGraph Graph;
1.653 + typedef _DirectionMap DirectionMap;
1.654 +
1.655 + typedef typename _UGraph::Node Node;
1.656 + typedef typename _UGraph::UEdge Edge;
1.657 +
1.658 + void first(Node& i) const { graph->first(i); }
1.659 + void first(Edge& i) const { graph->first(i); }
1.660 + void firstIn(Edge& i, const Node& n) const {
1.661 + bool d;
1.662 + graph->firstInc(i, d, n);
1.663 + while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
1.664 + }
1.665 + void firstOut(Edge& i, const Node& n ) const {
1.666 + bool d;
1.667 + graph->firstInc(i, d, n);
1.668 + while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
1.669 + }
1.670 +
1.671 + void next(Node& i) const { graph->next(i); }
1.672 + void next(Edge& i) const { graph->next(i); }
1.673 + void nextIn(Edge& i) const {
1.674 + bool d = !(*direction)[i];
1.675 + graph->nextInc(i, d);
1.676 + while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
1.677 + }
1.678 + void nextOut(Edge& i) const {
1.679 + bool d = (*direction)[i];
1.680 + graph->nextInc(i, d);
1.681 + while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
1.682 + }
1.683 +
1.684 + Node source(const Edge& e) const {
1.685 + return (*direction)[e] ? graph->source(e) : graph->target(e);
1.686 + }
1.687 + Node target(const Edge& e) const {
1.688 + return (*direction)[e] ? graph->target(e) : graph->source(e);
1.689 + }
1.690 +
1.691 + typedef NodeNumTagIndicator<Graph> NodeNumTag;
1.692 + int nodeNum() const { return graph->nodeNum(); }
1.693 +
1.694 + typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
1.695 + int edgeNum() const { return graph->uEdgeNum(); }
1.696 +
1.697 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1.698 + Edge findEdge(const Node& source, const Node& target,
1.699 + const Edge& prev = INVALID) {
1.700 + Edge edge = prev;
1.701 + bool d = edge == INVALID ? true : (*direction)[edge];
1.702 + if (d) {
1.703 + edge = graph->findUEdge(source, target, edge);
1.704 + while (edge != INVALID && !(*direction)[edge]) {
1.705 + graph->findUEdge(source, target, edge);
1.706 + }
1.707 + if (edge != INVALID) return edge;
1.708 + }
1.709 + graph->findUEdge(target, source, edge);
1.710 + while (edge != INVALID && (*direction)[edge]) {
1.711 + graph->findUEdge(source, target, edge);
1.712 + }
1.713 + return edge;
1.714 + }
1.715 +
1.716 + Node addNode() const {
1.717 + return Node(graph->addNode());
1.718 + }
1.719 +
1.720 + Edge addEdge(const Node& source, const Node& target) const {
1.721 + Edge edge = graph->addEdge(source, target);
1.722 + (*direction)[edge] = graph->source(edge) == source;
1.723 + return edge;
1.724 + }
1.725 +
1.726 + void erase(const Node& i) const { graph->erase(i); }
1.727 + void erase(const Edge& i) const { graph->erase(i); }
1.728 +
1.729 + void clear() const { graph->clear(); }
1.730 +
1.731 + int id(const Node& v) const { return graph->id(v); }
1.732 + int id(const Edge& e) const { return graph->id(e); }
1.733 +
1.734 + void reverseEdge(const Edge& edge) {
1.735 + direction->set(edge, !(*direction)[edge]);
1.736 + }
1.737 +
1.738 + template <typename _Value>
1.739 + class NodeMap : public _UGraph::template NodeMap<_Value> {
1.740 + public:
1.741 + typedef typename _UGraph::template NodeMap<_Value> Parent;
1.742 + explicit NodeMap(const DirectUGraphAdaptorBase& ga)
1.743 + : Parent(*ga.graph) { }
1.744 + NodeMap(const DirectUGraphAdaptorBase& ga, const _Value& value)
1.745 + : Parent(*ga.graph, value) { }
1.746 + };
1.747 +
1.748 + template <typename _Value>
1.749 + class EdgeMap : public _UGraph::template UEdgeMap<_Value> {
1.750 + public:
1.751 + typedef typename _UGraph::template EdgeMap<_Value> Parent;
1.752 + explicit EdgeMap(const DirectUGraphAdaptorBase& ga)
1.753 + : Parent(*ga.graph) { }
1.754 + EdgeMap(const DirectUGraphAdaptorBase& ga, const _Value& value)
1.755 + : Parent(*ga.graph, value) { }
1.756 + };
1.757 +
1.758 +
1.759 +
1.760 + protected:
1.761 + Graph* graph;
1.762 + DirectionMap* direction;
1.763 +
1.764 + void setDirectionMap(DirectionMap& _direction) {
1.765 + direction = &_direction;
1.766 + }
1.767 +
1.768 + void setGraph(Graph& _graph) {
1.769 + graph = &_graph;
1.770 + }
1.771 +
1.772 + };
1.773 +
1.774 +
1.775 + template<typename _Graph, typename DirectionMap>
1.776 + class DirectUGraphAdaptor :
1.777 + public GraphAdaptorExtender<
1.778 + DirectUGraphAdaptorBase<_Graph, DirectionMap> > {
1.779 + public:
1.780 + typedef _Graph Graph;
1.781 + typedef GraphAdaptorExtender<
1.782 + DirectUGraphAdaptorBase<_Graph, DirectionMap> > Parent;
1.783 + protected:
1.784 + DirectUGraphAdaptor() { }
1.785 + public:
1.786 + DirectUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) {
1.787 + setGraph(_graph);
1.788 + setDirectionMap(_direction_map);
1.789 + }
1.790 + };
1.791 +
1.792 + template<typename UGraph, typename DirectionMap>
1.793 + DirectUGraphAdaptor<const UGraph, DirectionMap>
1.794 + directUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {
1.795 + return DirectUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);
1.796 + }
1.797 +
1.798 + template<typename UGraph, typename DirectionMap>
1.799 + DirectUGraphAdaptor<const UGraph, const DirectionMap>
1.800 + directUGraphAdaptor(const UGraph& graph, const DirectionMap& dm) {
1.801 + return DirectUGraphAdaptor<const UGraph, const DirectionMap>(graph, dm);
1.802 + }
1.803 +
1.804 +}
1.805 +
1.806 +#endif