1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/graph_adaptor.h Sun Nov 30 18:57:18 2008 +0100
1.3 @@ -0,0 +1,1136 @@
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-2008
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_GRAPH_ADAPTOR_H
1.23 +#define LEMON_GRAPH_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 undirected graph adaptor classes.
1.30 +
1.31 +#include <lemon/core.h>
1.32 +#include <lemon/maps.h>
1.33 +#include <lemon/bits/graph_adaptor_extender.h>
1.34 +
1.35 +namespace lemon {
1.36 +
1.37 + /// \brief Base type for the Graph Adaptors
1.38 + ///
1.39 + /// This is the base type for most of LEMON graph adaptors.
1.40 + /// This class implements a trivial graph adaptor i.e. it only wraps the
1.41 + /// functions and types of the graph. The purpose of this class is to
1.42 + /// make easier implementing graph adaptors. E.g. if an adaptor is
1.43 + /// considered which differs from the wrapped graph only in some of its
1.44 + /// functions or types, then it can be derived from GraphAdaptor, and only
1.45 + /// the differences should be implemented.
1.46 + template<typename _Graph>
1.47 + class GraphAdaptorBase {
1.48 + public:
1.49 + typedef _Graph Graph;
1.50 + typedef Graph ParentGraph;
1.51 +
1.52 + protected:
1.53 + Graph* _graph;
1.54 +
1.55 + GraphAdaptorBase() : _graph(0) {}
1.56 +
1.57 + void setGraph(Graph& graph) { _graph = &graph; }
1.58 +
1.59 + public:
1.60 + GraphAdaptorBase(Graph& graph) : _graph(&graph) {}
1.61 +
1.62 + typedef typename Graph::Node Node;
1.63 + typedef typename Graph::Arc Arc;
1.64 + typedef typename Graph::Edge Edge;
1.65 +
1.66 + void first(Node& i) const { _graph->first(i); }
1.67 + void first(Arc& i) const { _graph->first(i); }
1.68 + void first(Edge& i) const { _graph->first(i); }
1.69 + void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); }
1.70 + void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); }
1.71 + void firstInc(Edge &i, bool &d, const Node &n) const {
1.72 + _graph->firstInc(i, d, n);
1.73 + }
1.74 +
1.75 + void next(Node& i) const { _graph->next(i); }
1.76 + void next(Arc& i) const { _graph->next(i); }
1.77 + void next(Edge& i) const { _graph->next(i); }
1.78 + void nextIn(Arc& i) const { _graph->nextIn(i); }
1.79 + void nextOut(Arc& i) const { _graph->nextOut(i); }
1.80 + void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); }
1.81 +
1.82 + Node u(const Edge& e) const { return _graph->u(e); }
1.83 + Node v(const Edge& e) const { return _graph->v(e); }
1.84 +
1.85 + Node source(const Arc& a) const { return _graph->source(a); }
1.86 + Node target(const Arc& a) const { return _graph->target(a); }
1.87 +
1.88 + typedef NodeNumTagIndicator<Graph> NodeNumTag;
1.89 + int nodeNum() const { return _graph->nodeNum(); }
1.90 +
1.91 + typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
1.92 + int arcNum() const { return _graph->arcNum(); }
1.93 + int edgeNum() const { return _graph->edgeNum(); }
1.94 +
1.95 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1.96 + Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {
1.97 + return _graph->findArc(u, v, prev);
1.98 + }
1.99 + Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) {
1.100 + return _graph->findEdge(u, v, prev);
1.101 + }
1.102 +
1.103 + Node addNode() { return _graph->addNode(); }
1.104 + Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); }
1.105 +
1.106 + void erase(const Node& i) { _graph->erase(i); }
1.107 + void erase(const Edge& i) { _graph->erase(i); }
1.108 +
1.109 + void clear() { _graph->clear(); }
1.110 +
1.111 + bool direction(const Arc& a) const { return _graph->direction(a); }
1.112 + Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); }
1.113 +
1.114 + int id(const Node& v) const { return _graph->id(v); }
1.115 + int id(const Arc& a) const { return _graph->id(a); }
1.116 + int id(const Edge& e) const { return _graph->id(e); }
1.117 +
1.118 + Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
1.119 + Arc arcFromId(int ix) const { return _graph->arcFromId(ix); }
1.120 + Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); }
1.121 +
1.122 + int maxNodeId() const { return _graph->maxNodeId(); }
1.123 + int maxArcId() const { return _graph->maxArcId(); }
1.124 + int maxEdgeId() const { return _graph->maxEdgeId(); }
1.125 +
1.126 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
1.127 + NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
1.128 +
1.129 + typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
1.130 + ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
1.131 +
1.132 + typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
1.133 + EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
1.134 +
1.135 + template <typename _Value>
1.136 + class NodeMap : public Graph::template NodeMap<_Value> {
1.137 + public:
1.138 + typedef typename Graph::template NodeMap<_Value> Parent;
1.139 + explicit NodeMap(const GraphAdaptorBase<Graph>& adapter)
1.140 + : Parent(*adapter._graph) {}
1.141 + NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
1.142 + : Parent(*adapter._graph, value) {}
1.143 +
1.144 + private:
1.145 + NodeMap& operator=(const NodeMap& cmap) {
1.146 + return operator=<NodeMap>(cmap);
1.147 + }
1.148 +
1.149 + template <typename CMap>
1.150 + NodeMap& operator=(const CMap& cmap) {
1.151 + Parent::operator=(cmap);
1.152 + return *this;
1.153 + }
1.154 +
1.155 + };
1.156 +
1.157 + template <typename _Value>
1.158 + class ArcMap : public Graph::template ArcMap<_Value> {
1.159 + public:
1.160 + typedef typename Graph::template ArcMap<_Value> Parent;
1.161 + explicit ArcMap(const GraphAdaptorBase<Graph>& adapter)
1.162 + : Parent(*adapter._graph) {}
1.163 + ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
1.164 + : Parent(*adapter._graph, value) {}
1.165 +
1.166 + private:
1.167 + ArcMap& operator=(const ArcMap& cmap) {
1.168 + return operator=<ArcMap>(cmap);
1.169 + }
1.170 +
1.171 + template <typename CMap>
1.172 + ArcMap& operator=(const CMap& cmap) {
1.173 + Parent::operator=(cmap);
1.174 + return *this;
1.175 + }
1.176 + };
1.177 +
1.178 + template <typename _Value>
1.179 + class EdgeMap : public Graph::template EdgeMap<_Value> {
1.180 + public:
1.181 + typedef typename Graph::template EdgeMap<_Value> Parent;
1.182 + explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter)
1.183 + : Parent(*adapter._graph) {}
1.184 + EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value)
1.185 + : Parent(*adapter._graph, value) {}
1.186 +
1.187 + private:
1.188 + EdgeMap& operator=(const EdgeMap& cmap) {
1.189 + return operator=<EdgeMap>(cmap);
1.190 + }
1.191 +
1.192 + template <typename CMap>
1.193 + EdgeMap& operator=(const CMap& cmap) {
1.194 + Parent::operator=(cmap);
1.195 + return *this;
1.196 + }
1.197 + };
1.198 +
1.199 + };
1.200 +
1.201 + /// \ingroup graph_adaptors
1.202 + ///
1.203 + /// \brief Trivial graph adaptor
1.204 + ///
1.205 + /// This class is an adaptor which does not change the adapted undirected
1.206 + /// graph. It can be used only to test the graph adaptors.
1.207 + template <typename _Graph>
1.208 + class GraphAdaptor
1.209 + : public GraphAdaptorExtender< GraphAdaptorBase<_Graph> > {
1.210 + public:
1.211 + typedef _Graph Graph;
1.212 + typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;
1.213 + protected:
1.214 + GraphAdaptor() : Parent() {}
1.215 +
1.216 + public:
1.217 + explicit GraphAdaptor(Graph& graph) { setGraph(graph); }
1.218 + };
1.219 +
1.220 + template <typename _Graph, typename NodeFilterMap,
1.221 + typename EdgeFilterMap, bool checked = true>
1.222 + class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1.223 + public:
1.224 + typedef _Graph Graph;
1.225 + typedef SubGraphAdaptorBase Adaptor;
1.226 + typedef GraphAdaptorBase<_Graph> Parent;
1.227 + protected:
1.228 +
1.229 + NodeFilterMap* _node_filter_map;
1.230 + EdgeFilterMap* _edge_filter_map;
1.231 +
1.232 + SubGraphAdaptorBase()
1.233 + : Parent(), _node_filter_map(0), _edge_filter_map(0) { }
1.234 +
1.235 + void setNodeFilterMap(NodeFilterMap& node_filter_map) {
1.236 + _node_filter_map=&node_filter_map;
1.237 + }
1.238 + void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
1.239 + _edge_filter_map=&edge_filter_map;
1.240 + }
1.241 +
1.242 + public:
1.243 +
1.244 + typedef typename Parent::Node Node;
1.245 + typedef typename Parent::Arc Arc;
1.246 + typedef typename Parent::Edge Edge;
1.247 +
1.248 + void first(Node& i) const {
1.249 + Parent::first(i);
1.250 + while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
1.251 + }
1.252 +
1.253 + void first(Arc& i) const {
1.254 + Parent::first(i);
1.255 + while (i!=INVALID && (!(*_edge_filter_map)[i]
1.256 + || !(*_node_filter_map)[Parent::source(i)]
1.257 + || !(*_node_filter_map)[Parent::target(i)])) Parent::next(i);
1.258 + }
1.259 +
1.260 + void first(Edge& i) const {
1.261 + Parent::first(i);
1.262 + while (i!=INVALID && (!(*_edge_filter_map)[i]
1.263 + || !(*_node_filter_map)[Parent::u(i)]
1.264 + || !(*_node_filter_map)[Parent::v(i)])) Parent::next(i);
1.265 + }
1.266 +
1.267 + void firstIn(Arc& i, const Node& n) const {
1.268 + Parent::firstIn(i, n);
1.269 + while (i!=INVALID && (!(*_edge_filter_map)[i]
1.270 + || !(*_node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
1.271 + }
1.272 +
1.273 + void firstOut(Arc& i, const Node& n) const {
1.274 + Parent::firstOut(i, n);
1.275 + while (i!=INVALID && (!(*_edge_filter_map)[i]
1.276 + || !(*_node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
1.277 + }
1.278 +
1.279 + void firstInc(Edge& i, bool& d, const Node& n) const {
1.280 + Parent::firstInc(i, d, n);
1.281 + while (i!=INVALID && (!(*_edge_filter_map)[i]
1.282 + || !(*_node_filter_map)[Parent::u(i)]
1.283 + || !(*_node_filter_map)[Parent::v(i)])) Parent::nextInc(i, d);
1.284 + }
1.285 +
1.286 + void next(Node& i) const {
1.287 + Parent::next(i);
1.288 + while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
1.289 + }
1.290 +
1.291 + void next(Arc& i) const {
1.292 + Parent::next(i);
1.293 + while (i!=INVALID && (!(*_edge_filter_map)[i]
1.294 + || !(*_node_filter_map)[Parent::source(i)]
1.295 + || !(*_node_filter_map)[Parent::target(i)])) Parent::next(i);
1.296 + }
1.297 +
1.298 + void next(Edge& i) const {
1.299 + Parent::next(i);
1.300 + while (i!=INVALID && (!(*_edge_filter_map)[i]
1.301 + || !(*_node_filter_map)[Parent::u(i)]
1.302 + || !(*_node_filter_map)[Parent::v(i)])) Parent::next(i);
1.303 + }
1.304 +
1.305 + void nextIn(Arc& i) const {
1.306 + Parent::nextIn(i);
1.307 + while (i!=INVALID && (!(*_edge_filter_map)[i]
1.308 + || !(*_node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
1.309 + }
1.310 +
1.311 + void nextOut(Arc& i) const {
1.312 + Parent::nextOut(i);
1.313 + while (i!=INVALID && (!(*_edge_filter_map)[i]
1.314 + || !(*_node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
1.315 + }
1.316 +
1.317 + void nextInc(Edge& i, bool& d) const {
1.318 + Parent::nextInc(i, d);
1.319 + while (i!=INVALID && (!(*_edge_filter_map)[i]
1.320 + || !(*_node_filter_map)[Parent::u(i)]
1.321 + || !(*_node_filter_map)[Parent::v(i)])) Parent::nextInc(i, d);
1.322 + }
1.323 +
1.324 + /// \brief Hide the given node in the graph.
1.325 + ///
1.326 + /// This function hides \c n in the graph, i.e. the iteration
1.327 + /// jumps over it. This is done by simply setting the value of \c n
1.328 + /// to be false in the corresponding node-map.
1.329 + void hide(const Node& n) const { _node_filter_map->set(n, false); }
1.330 +
1.331 + /// \brief Hide the given edge in the graph.
1.332 + ///
1.333 + /// This function hides \c e in the graph, i.e. the iteration
1.334 + /// jumps over it. This is done by simply setting the value of \c e
1.335 + /// to be false in the corresponding edge-map.
1.336 + void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
1.337 +
1.338 + /// \brief Unhide the given node in the graph.
1.339 + ///
1.340 + /// The value of \c n is set to be true in the node-map which stores
1.341 + /// hide information. If \c n was hidden previuosly, then it is shown
1.342 + /// again
1.343 + void unHide(const Node& n) const { _node_filter_map->set(n, true); }
1.344 +
1.345 + /// \brief Hide the given edge in the graph.
1.346 + ///
1.347 + /// The value of \c e is set to be true in the edge-map which stores
1.348 + /// hide information. If \c e was hidden previuosly, then it is shown
1.349 + /// again
1.350 + void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
1.351 +
1.352 + /// \brief Returns true if \c n is hidden.
1.353 + ///
1.354 + /// Returns true if \c n is hidden.
1.355 + bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
1.356 +
1.357 + /// \brief Returns true if \c e is hidden.
1.358 + ///
1.359 + /// Returns true if \c e is hidden.
1.360 + bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
1.361 +
1.362 + typedef False NodeNumTag;
1.363 + typedef False EdgeNumTag;
1.364 +
1.365 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1.366 + Arc findArc(const Node& u, const Node& v,
1.367 + const Arc& prev = INVALID) {
1.368 + if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
1.369 + return INVALID;
1.370 + }
1.371 + Arc arc = Parent::findArc(u, v, prev);
1.372 + while (arc != INVALID && !(*_edge_filter_map)[arc]) {
1.373 + arc = Parent::findArc(u, v, arc);
1.374 + }
1.375 + return arc;
1.376 + }
1.377 + Edge findEdge(const Node& u, const Node& v,
1.378 + const Edge& prev = INVALID) {
1.379 + if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) {
1.380 + return INVALID;
1.381 + }
1.382 + Edge edge = Parent::findEdge(u, v, prev);
1.383 + while (edge != INVALID && !(*_edge_filter_map)[edge]) {
1.384 + edge = Parent::findEdge(u, v, edge);
1.385 + }
1.386 + return edge;
1.387 + }
1.388 +
1.389 + template <typename _Value>
1.390 + class NodeMap : public SubMapExtender<Adaptor,
1.391 + typename Parent::template NodeMap<_Value> > {
1.392 + public:
1.393 + typedef _Value Value;
1.394 + typedef SubMapExtender<Adaptor, typename Parent::
1.395 + template NodeMap<Value> > MapParent;
1.396 +
1.397 + NodeMap(const Adaptor& adaptor)
1.398 + : MapParent(adaptor) {}
1.399 + NodeMap(const Adaptor& adaptor, const Value& value)
1.400 + : MapParent(adaptor, value) {}
1.401 +
1.402 + private:
1.403 + NodeMap& operator=(const NodeMap& cmap) {
1.404 + return operator=<NodeMap>(cmap);
1.405 + }
1.406 +
1.407 + template <typename CMap>
1.408 + NodeMap& operator=(const CMap& cmap) {
1.409 + MapParent::operator=(cmap);
1.410 + return *this;
1.411 + }
1.412 + };
1.413 +
1.414 + template <typename _Value>
1.415 + class ArcMap : public SubMapExtender<Adaptor,
1.416 + typename Parent::template ArcMap<_Value> > {
1.417 + public:
1.418 + typedef _Value Value;
1.419 + typedef SubMapExtender<Adaptor, typename Parent::
1.420 + template ArcMap<Value> > MapParent;
1.421 +
1.422 + ArcMap(const Adaptor& adaptor)
1.423 + : MapParent(adaptor) {}
1.424 + ArcMap(const Adaptor& adaptor, const Value& value)
1.425 + : MapParent(adaptor, value) {}
1.426 +
1.427 + private:
1.428 + ArcMap& operator=(const ArcMap& cmap) {
1.429 + return operator=<ArcMap>(cmap);
1.430 + }
1.431 +
1.432 + template <typename CMap>
1.433 + ArcMap& operator=(const CMap& cmap) {
1.434 + MapParent::operator=(cmap);
1.435 + return *this;
1.436 + }
1.437 + };
1.438 +
1.439 + template <typename _Value>
1.440 + class EdgeMap : public SubMapExtender<Adaptor,
1.441 + typename Parent::template EdgeMap<_Value> > {
1.442 + public:
1.443 + typedef _Value Value;
1.444 + typedef SubMapExtender<Adaptor, typename Parent::
1.445 + template EdgeMap<Value> > MapParent;
1.446 +
1.447 + EdgeMap(const Adaptor& adaptor)
1.448 + : MapParent(adaptor) {}
1.449 +
1.450 + EdgeMap(const Adaptor& adaptor, const Value& value)
1.451 + : MapParent(adaptor, value) {}
1.452 +
1.453 + private:
1.454 + EdgeMap& operator=(const EdgeMap& cmap) {
1.455 + return operator=<EdgeMap>(cmap);
1.456 + }
1.457 +
1.458 + template <typename CMap>
1.459 + EdgeMap& operator=(const CMap& cmap) {
1.460 + MapParent::operator=(cmap);
1.461 + return *this;
1.462 + }
1.463 + };
1.464 +
1.465 + };
1.466 +
1.467 + template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
1.468 + class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
1.469 + : public GraphAdaptorBase<_Graph> {
1.470 + public:
1.471 + typedef _Graph Graph;
1.472 + typedef SubGraphAdaptorBase Adaptor;
1.473 + typedef GraphAdaptorBase<_Graph> Parent;
1.474 + protected:
1.475 + NodeFilterMap* _node_filter_map;
1.476 + EdgeFilterMap* _edge_filter_map;
1.477 + SubGraphAdaptorBase() : Parent(),
1.478 + _node_filter_map(0), _edge_filter_map(0) { }
1.479 +
1.480 + void setNodeFilterMap(NodeFilterMap& node_filter_map) {
1.481 + _node_filter_map=&node_filter_map;
1.482 + }
1.483 + void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) {
1.484 + _edge_filter_map=&edge_filter_map;
1.485 + }
1.486 +
1.487 + public:
1.488 +
1.489 + typedef typename Parent::Node Node;
1.490 + typedef typename Parent::Arc Arc;
1.491 + typedef typename Parent::Edge Edge;
1.492 +
1.493 + void first(Node& i) const {
1.494 + Parent::first(i);
1.495 + while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
1.496 + }
1.497 +
1.498 + void first(Arc& i) const {
1.499 + Parent::first(i);
1.500 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1.501 + }
1.502 +
1.503 + void first(Edge& i) const {
1.504 + Parent::first(i);
1.505 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1.506 + }
1.507 +
1.508 + void firstIn(Arc& i, const Node& n) const {
1.509 + Parent::firstIn(i, n);
1.510 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
1.511 + }
1.512 +
1.513 + void firstOut(Arc& i, const Node& n) const {
1.514 + Parent::firstOut(i, n);
1.515 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
1.516 + }
1.517 +
1.518 + void firstInc(Edge& i, bool& d, const Node& n) const {
1.519 + Parent::firstInc(i, d, n);
1.520 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
1.521 + }
1.522 +
1.523 + void next(Node& i) const {
1.524 + Parent::next(i);
1.525 + while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i);
1.526 + }
1.527 + void next(Arc& i) const {
1.528 + Parent::next(i);
1.529 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1.530 + }
1.531 + void next(Edge& i) const {
1.532 + Parent::next(i);
1.533 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i);
1.534 + }
1.535 + void nextIn(Arc& i) const {
1.536 + Parent::nextIn(i);
1.537 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i);
1.538 + }
1.539 +
1.540 + void nextOut(Arc& i) const {
1.541 + Parent::nextOut(i);
1.542 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i);
1.543 + }
1.544 + void nextInc(Edge& i, bool& d) const {
1.545 + Parent::nextInc(i, d);
1.546 + while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
1.547 + }
1.548 +
1.549 + /// \brief Hide the given node in the graph.
1.550 + ///
1.551 + /// This function hides \c n in the graph, i.e. the iteration
1.552 + /// jumps over it. This is done by simply setting the value of \c n
1.553 + /// to be false in the corresponding node-map.
1.554 + void hide(const Node& n) const { _node_filter_map->set(n, false); }
1.555 +
1.556 + /// \brief Hide the given edge in the graph.
1.557 + ///
1.558 + /// This function hides \c e in the graph, i.e. the iteration
1.559 + /// jumps over it. This is done by simply setting the value of \c e
1.560 + /// to be false in the corresponding edge-map.
1.561 + void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
1.562 +
1.563 + /// \brief Unhide the given node in the graph.
1.564 + ///
1.565 + /// The value of \c n is set to be true in the node-map which stores
1.566 + /// hide information. If \c n was hidden previuosly, then it is shown
1.567 + /// again
1.568 + void unHide(const Node& n) const { _node_filter_map->set(n, true); }
1.569 +
1.570 + /// \brief Hide the given edge in the graph.
1.571 + ///
1.572 + /// The value of \c e is set to be true in the edge-map which stores
1.573 + /// hide information. If \c e was hidden previuosly, then it is shown
1.574 + /// again
1.575 + void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
1.576 +
1.577 + /// \brief Returns true if \c n is hidden.
1.578 + ///
1.579 + /// Returns true if \c n is hidden.
1.580 + bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
1.581 +
1.582 + /// \brief Returns true if \c e is hidden.
1.583 + ///
1.584 + /// Returns true if \c e is hidden.
1.585 + bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
1.586 +
1.587 + typedef False NodeNumTag;
1.588 + typedef False EdgeNumTag;
1.589 +
1.590 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1.591 + Arc findArc(const Node& u, const Node& v,
1.592 + const Arc& prev = INVALID) {
1.593 + Arc arc = Parent::findArc(u, v, prev);
1.594 + while (arc != INVALID && !(*_edge_filter_map)[arc]) {
1.595 + arc = Parent::findArc(u, v, arc);
1.596 + }
1.597 + return arc;
1.598 + }
1.599 + Edge findEdge(const Node& u, const Node& v,
1.600 + const Edge& prev = INVALID) {
1.601 + Edge edge = Parent::findEdge(u, v, prev);
1.602 + while (edge != INVALID && !(*_edge_filter_map)[edge]) {
1.603 + edge = Parent::findEdge(u, v, edge);
1.604 + }
1.605 + return edge;
1.606 + }
1.607 +
1.608 + template <typename _Value>
1.609 + class NodeMap : public SubMapExtender<Adaptor,
1.610 + typename Parent::template NodeMap<_Value> > {
1.611 + public:
1.612 + typedef _Value Value;
1.613 + typedef SubMapExtender<Adaptor, typename Parent::
1.614 + template NodeMap<Value> > MapParent;
1.615 +
1.616 + NodeMap(const Adaptor& adaptor)
1.617 + : MapParent(adaptor) {}
1.618 + NodeMap(const Adaptor& adaptor, const Value& value)
1.619 + : MapParent(adaptor, value) {}
1.620 +
1.621 + private:
1.622 + NodeMap& operator=(const NodeMap& cmap) {
1.623 + return operator=<NodeMap>(cmap);
1.624 + }
1.625 +
1.626 + template <typename CMap>
1.627 + NodeMap& operator=(const CMap& cmap) {
1.628 + MapParent::operator=(cmap);
1.629 + return *this;
1.630 + }
1.631 + };
1.632 +
1.633 + template <typename _Value>
1.634 + class ArcMap : public SubMapExtender<Adaptor,
1.635 + typename Parent::template ArcMap<_Value> > {
1.636 + public:
1.637 + typedef _Value Value;
1.638 + typedef SubMapExtender<Adaptor, typename Parent::
1.639 + template ArcMap<Value> > MapParent;
1.640 +
1.641 + ArcMap(const Adaptor& adaptor)
1.642 + : MapParent(adaptor) {}
1.643 + ArcMap(const Adaptor& adaptor, const Value& value)
1.644 + : MapParent(adaptor, value) {}
1.645 +
1.646 + private:
1.647 + ArcMap& operator=(const ArcMap& cmap) {
1.648 + return operator=<ArcMap>(cmap);
1.649 + }
1.650 +
1.651 + template <typename CMap>
1.652 + ArcMap& operator=(const CMap& cmap) {
1.653 + MapParent::operator=(cmap);
1.654 + return *this;
1.655 + }
1.656 + };
1.657 +
1.658 + template <typename _Value>
1.659 + class EdgeMap : public SubMapExtender<Adaptor,
1.660 + typename Parent::template EdgeMap<_Value> > {
1.661 + public:
1.662 + typedef _Value Value;
1.663 + typedef SubMapExtender<Adaptor, typename Parent::
1.664 + template EdgeMap<Value> > MapParent;
1.665 +
1.666 + EdgeMap(const Adaptor& adaptor)
1.667 + : MapParent(adaptor) {}
1.668 +
1.669 + EdgeMap(const Adaptor& adaptor, const _Value& value)
1.670 + : MapParent(adaptor, value) {}
1.671 +
1.672 + private:
1.673 + EdgeMap& operator=(const EdgeMap& cmap) {
1.674 + return operator=<EdgeMap>(cmap);
1.675 + }
1.676 +
1.677 + template <typename CMap>
1.678 + EdgeMap& operator=(const CMap& cmap) {
1.679 + MapParent::operator=(cmap);
1.680 + return *this;
1.681 + }
1.682 + };
1.683 +
1.684 + };
1.685 +
1.686 + /// \ingroup graph_adaptors
1.687 + ///
1.688 + /// \brief A graph adaptor for hiding nodes and arcs from an
1.689 + /// undirected graph.
1.690 + ///
1.691 + /// SubGraphAdaptor shows the graph with filtered node-set and
1.692 + /// edge-set. If the \c checked parameter is true then it filters
1.693 + /// the edge-set to do not get invalid edges which incident node is
1.694 + /// filtered.
1.695 + ///
1.696 + /// If the \c checked template parameter is false then we have to
1.697 + /// note that the node-iterator cares only the filter on the
1.698 + /// node-set, and the edge-iterator cares only the filter on the
1.699 + /// edge-set. This way the edge-map should filter all arcs which
1.700 + /// has filtered end node.
1.701 + template<typename _Graph, typename NodeFilterMap,
1.702 + typename EdgeFilterMap, bool checked = true>
1.703 + class SubGraphAdaptor :
1.704 + public GraphAdaptorExtender<
1.705 + SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
1.706 + public:
1.707 + typedef _Graph Graph;
1.708 + typedef GraphAdaptorExtender<
1.709 + SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
1.710 + protected:
1.711 + SubGraphAdaptor() { }
1.712 + public:
1.713 + SubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map,
1.714 + EdgeFilterMap& edge_filter_map) {
1.715 + setGraph(_graph);
1.716 + setNodeFilterMap(node_filter_map);
1.717 + setEdgeFilterMap(edge_filter_map);
1.718 + }
1.719 + };
1.720 +
1.721 + template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1.722 + SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap>
1.723 + subGraphAdaptor(const Graph& graph,
1.724 + NodeFilterMap& nfm, ArcFilterMap& efm) {
1.725 + return SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap>
1.726 + (graph, nfm, efm);
1.727 + }
1.728 +
1.729 + template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1.730 + SubGraphAdaptor<const Graph, const NodeFilterMap, ArcFilterMap>
1.731 + subGraphAdaptor(const Graph& graph,
1.732 + NodeFilterMap& nfm, ArcFilterMap& efm) {
1.733 + return SubGraphAdaptor<const Graph, const NodeFilterMap, ArcFilterMap>
1.734 + (graph, nfm, efm);
1.735 + }
1.736 +
1.737 + template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1.738 + SubGraphAdaptor<const Graph, NodeFilterMap, const ArcFilterMap>
1.739 + subGraphAdaptor(const Graph& graph,
1.740 + NodeFilterMap& nfm, ArcFilterMap& efm) {
1.741 + return SubGraphAdaptor<const Graph, NodeFilterMap, const ArcFilterMap>
1.742 + (graph, nfm, efm);
1.743 + }
1.744 +
1.745 + template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1.746 + SubGraphAdaptor<const Graph, const NodeFilterMap, const ArcFilterMap>
1.747 + subGraphAdaptor(const Graph& graph,
1.748 + NodeFilterMap& nfm, ArcFilterMap& efm) {
1.749 + return SubGraphAdaptor<const Graph, const NodeFilterMap,
1.750 + const ArcFilterMap>(graph, nfm, efm);
1.751 + }
1.752 +
1.753 + /// \ingroup graph_adaptors
1.754 + ///
1.755 + /// \brief An adaptor for hiding nodes from an graph.
1.756 + ///
1.757 + /// An adaptor for hiding nodes from an graph. This
1.758 + /// adaptor specializes SubGraphAdaptor in the way that only the
1.759 + /// node-set can be filtered. In usual case the checked parameter is
1.760 + /// true, we get the induced subgraph. But if the checked parameter
1.761 + /// is false then we can filter only isolated nodes.
1.762 + template<typename _Graph, typename _NodeFilterMap, bool checked = true>
1.763 + class NodeSubGraphAdaptor :
1.764 + public SubGraphAdaptor<_Graph, _NodeFilterMap,
1.765 + ConstMap<typename _Graph::Edge, bool>, checked> {
1.766 + public:
1.767 + typedef _Graph Graph;
1.768 + typedef _NodeFilterMap NodeFilterMap;
1.769 + typedef SubGraphAdaptor<Graph, NodeFilterMap,
1.770 + ConstMap<typename Graph::Edge, bool> > Parent;
1.771 + protected:
1.772 + ConstMap<typename Graph::Edge, bool> const_true_map;
1.773 +
1.774 + NodeSubGraphAdaptor() : const_true_map(true) {
1.775 + Parent::setEdgeFilterMap(const_true_map);
1.776 + }
1.777 +
1.778 + public:
1.779 + NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map) :
1.780 + Parent(), const_true_map(true) {
1.781 + Parent::setGraph(_graph);
1.782 + Parent::setNodeFilterMap(node_filter_map);
1.783 + Parent::setEdgeFilterMap(const_true_map);
1.784 + }
1.785 + };
1.786 +
1.787 + template<typename Graph, typename NodeFilterMap>
1.788 + NodeSubGraphAdaptor<const Graph, NodeFilterMap>
1.789 + nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {
1.790 + return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);
1.791 + }
1.792 +
1.793 + template<typename Graph, typename NodeFilterMap>
1.794 + NodeSubGraphAdaptor<const Graph, const NodeFilterMap>
1.795 + nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) {
1.796 + return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);
1.797 + }
1.798 +
1.799 + /// \ingroup graph_adaptors
1.800 + ///
1.801 + /// \brief An adaptor for hiding edges from an graph.
1.802 + ///
1.803 + /// \warning Graph adaptors are in even more experimental state
1.804 + /// than the other parts of the lib. Use them at you own risk.
1.805 + ///
1.806 + /// An adaptor for hiding edges from an graph.
1.807 + /// This adaptor specializes SubGraphAdaptor in the way that
1.808 + /// only the arc-set
1.809 + /// can be filtered.
1.810 + template<typename _Graph, typename _EdgeFilterMap>
1.811 + class EdgeSubGraphAdaptor :
1.812 + public SubGraphAdaptor<_Graph, ConstMap<typename _Graph::Node,bool>,
1.813 + _EdgeFilterMap, false> {
1.814 + public:
1.815 + typedef _Graph Graph;
1.816 + typedef _EdgeFilterMap EdgeFilterMap;
1.817 + typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
1.818 + EdgeFilterMap, false> Parent;
1.819 + protected:
1.820 + ConstMap<typename Graph::Node, bool> const_true_map;
1.821 +
1.822 + EdgeSubGraphAdaptor() : const_true_map(true) {
1.823 + Parent::setNodeFilterMap(const_true_map);
1.824 + }
1.825 +
1.826 + public:
1.827 +
1.828 + EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& edge_filter_map) :
1.829 + Parent(), const_true_map(true) {
1.830 + Parent::setGraph(_graph);
1.831 + Parent::setNodeFilterMap(const_true_map);
1.832 + Parent::setEdgeFilterMap(edge_filter_map);
1.833 + }
1.834 +
1.835 + };
1.836 +
1.837 + template<typename Graph, typename EdgeFilterMap>
1.838 + EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>
1.839 + edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {
1.840 + return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm);
1.841 + }
1.842 +
1.843 + template<typename Graph, typename EdgeFilterMap>
1.844 + EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>
1.845 + edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) {
1.846 + return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
1.847 + }
1.848 +
1.849 + /// \brief Base of direct graph adaptor
1.850 + ///
1.851 + /// Base class of the direct graph adaptor. All public member
1.852 + /// of this class can be used with the DirGraphAdaptor too.
1.853 + /// \sa DirGraphAdaptor
1.854 + template <typename _Graph, typename _DirectionMap>
1.855 + class DirGraphAdaptorBase {
1.856 + public:
1.857 +
1.858 + typedef _Graph Graph;
1.859 + typedef _DirectionMap DirectionMap;
1.860 +
1.861 + typedef typename Graph::Node Node;
1.862 + typedef typename Graph::Edge Arc;
1.863 +
1.864 + /// \brief Reverse arc
1.865 + ///
1.866 + /// It reverse the given arc. It simply negate the direction in the map.
1.867 + void reverseArc(const Arc& arc) {
1.868 + _direction->set(arc, !(*_direction)[arc]);
1.869 + }
1.870 +
1.871 + void first(Node& i) const { _graph->first(i); }
1.872 + void first(Arc& i) const { _graph->first(i); }
1.873 + void firstIn(Arc& i, const Node& n) const {
1.874 + bool d;
1.875 + _graph->firstInc(i, d, n);
1.876 + while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
1.877 + }
1.878 + void firstOut(Arc& i, const Node& n ) const {
1.879 + bool d;
1.880 + _graph->firstInc(i, d, n);
1.881 + while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
1.882 + }
1.883 +
1.884 + void next(Node& i) const { _graph->next(i); }
1.885 + void next(Arc& i) const { _graph->next(i); }
1.886 + void nextIn(Arc& i) const {
1.887 + bool d = !(*_direction)[i];
1.888 + _graph->nextInc(i, d);
1.889 + while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
1.890 + }
1.891 + void nextOut(Arc& i) const {
1.892 + bool d = (*_direction)[i];
1.893 + _graph->nextInc(i, d);
1.894 + while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
1.895 + }
1.896 +
1.897 + Node source(const Arc& e) const {
1.898 + return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
1.899 + }
1.900 + Node target(const Arc& e) const {
1.901 + return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
1.902 + }
1.903 +
1.904 + typedef NodeNumTagIndicator<Graph> NodeNumTag;
1.905 + int nodeNum() const { return _graph->nodeNum(); }
1.906 +
1.907 + typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
1.908 + int arcNum() const { return _graph->edgeNum(); }
1.909 +
1.910 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1.911 + Arc findArc(const Node& u, const Node& v,
1.912 + const Arc& prev = INVALID) {
1.913 + Arc arc = prev;
1.914 + bool d = arc == INVALID ? true : (*_direction)[arc];
1.915 + if (d) {
1.916 + arc = _graph->findEdge(u, v, arc);
1.917 + while (arc != INVALID && !(*_direction)[arc]) {
1.918 + _graph->findEdge(u, v, arc);
1.919 + }
1.920 + if (arc != INVALID) return arc;
1.921 + }
1.922 + _graph->findEdge(v, u, arc);
1.923 + while (arc != INVALID && (*_direction)[arc]) {
1.924 + _graph->findEdge(u, v, arc);
1.925 + }
1.926 + return arc;
1.927 + }
1.928 +
1.929 + Node addNode() {
1.930 + return Node(_graph->addNode());
1.931 + }
1.932 +
1.933 + Arc addArc(const Node& u, const Node& v) {
1.934 + Arc arc = _graph->addArc(u, v);
1.935 + _direction->set(arc, _graph->source(arc) == u);
1.936 + return arc;
1.937 + }
1.938 +
1.939 + void erase(const Node& i) { _graph->erase(i); }
1.940 + void erase(const Arc& i) { _graph->erase(i); }
1.941 +
1.942 + void clear() { _graph->clear(); }
1.943 +
1.944 + int id(const Node& v) const { return _graph->id(v); }
1.945 + int id(const Arc& e) const { return _graph->id(e); }
1.946 +
1.947 + Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
1.948 + Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
1.949 +
1.950 + int maxNodeId() const { return _graph->maxNodeId(); }
1.951 + int maxArcId() const { return _graph->maxEdgeId(); }
1.952 +
1.953 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
1.954 + NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
1.955 +
1.956 + typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier;
1.957 + ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
1.958 +
1.959 + template <typename _Value>
1.960 + class NodeMap : public _Graph::template NodeMap<_Value> {
1.961 + public:
1.962 +
1.963 + typedef typename _Graph::template NodeMap<_Value> Parent;
1.964 +
1.965 + explicit NodeMap(const DirGraphAdaptorBase& adapter)
1.966 + : Parent(*adapter._graph) {}
1.967 +
1.968 + NodeMap(const DirGraphAdaptorBase& adapter, const _Value& value)
1.969 + : Parent(*adapter._graph, value) {}
1.970 +
1.971 + private:
1.972 + NodeMap& operator=(const NodeMap& cmap) {
1.973 + return operator=<NodeMap>(cmap);
1.974 + }
1.975 +
1.976 + template <typename CMap>
1.977 + NodeMap& operator=(const CMap& cmap) {
1.978 + Parent::operator=(cmap);
1.979 + return *this;
1.980 + }
1.981 +
1.982 + };
1.983 +
1.984 + template <typename _Value>
1.985 + class ArcMap : public _Graph::template EdgeMap<_Value> {
1.986 + public:
1.987 +
1.988 + typedef typename Graph::template EdgeMap<_Value> Parent;
1.989 +
1.990 + explicit ArcMap(const DirGraphAdaptorBase& adapter)
1.991 + : Parent(*adapter._graph) { }
1.992 +
1.993 + ArcMap(const DirGraphAdaptorBase& adapter, const _Value& value)
1.994 + : Parent(*adapter._graph, value) { }
1.995 +
1.996 + private:
1.997 + ArcMap& operator=(const ArcMap& cmap) {
1.998 + return operator=<ArcMap>(cmap);
1.999 + }
1.1000 +
1.1001 + template <typename CMap>
1.1002 + ArcMap& operator=(const CMap& cmap) {
1.1003 + Parent::operator=(cmap);
1.1004 + return *this;
1.1005 + }
1.1006 + };
1.1007 +
1.1008 +
1.1009 +
1.1010 + protected:
1.1011 + Graph* _graph;
1.1012 + DirectionMap* _direction;
1.1013 +
1.1014 + void setDirectionMap(DirectionMap& direction) {
1.1015 + _direction = &direction;
1.1016 + }
1.1017 +
1.1018 + void setGraph(Graph& graph) {
1.1019 + _graph = &graph;
1.1020 + }
1.1021 +
1.1022 + };
1.1023 +
1.1024 +
1.1025 + /// \ingroup graph_adaptors
1.1026 + ///
1.1027 + /// \brief A directed graph is made from an graph by an adaptor
1.1028 + ///
1.1029 + /// This adaptor gives a direction for each edge in the undirected
1.1030 + /// graph. The direction of the arcs stored in the
1.1031 + /// DirectionMap. This map is a bool map on the edges. If
1.1032 + /// the edge is mapped to true then the direction of the directed
1.1033 + /// arc will be the same as the default direction of the edge. The
1.1034 + /// arcs can be easily reverted by the \ref
1.1035 + /// DirGraphAdaptorBase::reverseArc "reverseArc()" member in the
1.1036 + /// adaptor.
1.1037 + ///
1.1038 + /// It can be used to solve orientation problems on directed graphs.
1.1039 + /// For example how can we orient an graph to get the minimum
1.1040 + /// number of strongly connected components. If we orient the arcs with
1.1041 + /// the dfs algorithm out from the source then we will get such an
1.1042 + /// orientation.
1.1043 + ///
1.1044 + /// We use the \ref DfsVisitor "visitor" interface of the
1.1045 + /// \ref DfsVisit "dfs" algorithm:
1.1046 + ///\code
1.1047 + /// template <typename DirMap>
1.1048 + /// class OrientVisitor : public DfsVisitor<Graph> {
1.1049 + /// public:
1.1050 + ///
1.1051 + /// OrientVisitor(const Graph& graph, DirMap& dirMap)
1.1052 + /// : _graph(graph), _dirMap(dirMap), _processed(graph, false) {}
1.1053 + ///
1.1054 + /// void discover(const Arc& arc) {
1.1055 + /// _processed.set(arc, true);
1.1056 + /// _dirMap.set(arc, _graph.direction(arc));
1.1057 + /// }
1.1058 + ///
1.1059 + /// void examine(const Arc& arc) {
1.1060 + /// if (_processed[arc]) return;
1.1061 + /// _processed.set(arc, true);
1.1062 + /// _dirMap.set(arc, _graph.direction(arc));
1.1063 + /// }
1.1064 + ///
1.1065 + /// private:
1.1066 + /// const Graph& _graph;
1.1067 + /// DirMap& _dirMap;
1.1068 + /// Graph::EdgeMap<bool> _processed;
1.1069 + /// };
1.1070 + ///\endcode
1.1071 + ///
1.1072 + /// And now we can use the orientation:
1.1073 + ///\code
1.1074 + /// Graph::EdgeMap<bool> dmap(graph);
1.1075 + ///
1.1076 + /// typedef OrientVisitor<Graph::EdgeMap<bool> > Visitor;
1.1077 + /// Visitor visitor(graph, dmap);
1.1078 + ///
1.1079 + /// DfsVisit<Graph, Visitor> dfs(graph, visitor);
1.1080 + ///
1.1081 + /// dfs.run();
1.1082 + ///
1.1083 + /// typedef DirGraphAdaptor<Graph> DGraph;
1.1084 + /// DGraph dgraph(graph, dmap);
1.1085 + ///
1.1086 + /// LEMON_ASSERT(countStronglyConnectedComponents(dgraph) ==
1.1087 + /// countBiArcConnectedComponents(graph), "Wrong Orientation");
1.1088 + ///\endcode
1.1089 + ///
1.1090 + /// The number of the bi-connected components is a lower bound for
1.1091 + /// the number of the strongly connected components in the directed
1.1092 + /// graph because if we contract the bi-connected components to
1.1093 + /// nodes we will get a tree therefore we cannot orient arcs in
1.1094 + /// both direction between bi-connected components. In the other way
1.1095 + /// the algorithm will orient one component to be strongly
1.1096 + /// connected. The two relations proof that the assertion will
1.1097 + /// be always true and the found solution is optimal.
1.1098 + ///
1.1099 + /// \sa DirGraphAdaptorBase
1.1100 + /// \sa dirGraphAdaptor
1.1101 + template<typename _Graph,
1.1102 + typename DirectionMap = typename _Graph::template EdgeMap<bool> >
1.1103 + class DirGraphAdaptor :
1.1104 + public DigraphAdaptorExtender<DirGraphAdaptorBase<_Graph, DirectionMap> > {
1.1105 + public:
1.1106 + typedef _Graph Graph;
1.1107 + typedef DigraphAdaptorExtender<
1.1108 + DirGraphAdaptorBase<_Graph, DirectionMap> > Parent;
1.1109 + protected:
1.1110 + DirGraphAdaptor() { }
1.1111 + public:
1.1112 +
1.1113 + /// \brief Constructor of the adaptor
1.1114 + ///
1.1115 + /// Constructor of the adaptor
1.1116 + DirGraphAdaptor(Graph& graph, DirectionMap& direction) {
1.1117 + setGraph(graph);
1.1118 + setDirectionMap(direction);
1.1119 + }
1.1120 + };
1.1121 +
1.1122 + /// \brief Just gives back a DirGraphAdaptor
1.1123 + ///
1.1124 + /// Just gives back a DirGraphAdaptor
1.1125 + template<typename Graph, typename DirectionMap>
1.1126 + DirGraphAdaptor<const Graph, DirectionMap>
1.1127 + dirGraphAdaptor(const Graph& graph, DirectionMap& dm) {
1.1128 + return DirGraphAdaptor<const Graph, DirectionMap>(graph, dm);
1.1129 + }
1.1130 +
1.1131 + template<typename Graph, typename DirectionMap>
1.1132 + DirGraphAdaptor<const Graph, const DirectionMap>
1.1133 + dirGraphAdaptor(const Graph& graph, const DirectionMap& dm) {
1.1134 + return DirGraphAdaptor<const Graph, const DirectionMap>(graph, dm);
1.1135 + }
1.1136 +
1.1137 +}
1.1138 +
1.1139 +#endif