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