1.1 --- a/lemon/bits/graph_extender.h Sun Jul 13 16:46:56 2008 +0100
1.2 +++ b/lemon/bits/graph_extender.h Sun Jul 13 19:51:02 2008 +0100
1.3 @@ -1,6 +1,6 @@
1.4 -/* -*- C++ -*-
1.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.6 *
1.7 - * This file is a part of LEMON, a generic C++ optimization library
1.8 + * This file is a part of LEMON, a generic C++ optimization library.
1.9 *
1.10 * Copyright (C) 2003-2008
1.11 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.12 @@ -66,11 +66,11 @@
1.13
1.14 Node oppositeNode(const Node &node, const Arc &arc) const {
1.15 if (node == Parent::source(arc))
1.16 - return Parent::target(arc);
1.17 + return Parent::target(arc);
1.18 else if(node == Parent::target(arc))
1.19 - return Parent::source(arc);
1.20 + return Parent::source(arc);
1.21 else
1.22 - return INVALID;
1.23 + return INVALID;
1.24 }
1.25
1.26 // Alterable extension
1.27 @@ -89,12 +89,12 @@
1.28 NodeNotifier& notifier(Node) const {
1.29 return node_notifier;
1.30 }
1.31 -
1.32 +
1.33 ArcNotifier& notifier(Arc) const {
1.34 return arc_notifier;
1.35 }
1.36
1.37 - class NodeIt : public Node {
1.38 + class NodeIt : public Node {
1.39 const Digraph* _digraph;
1.40 public:
1.41
1.42 @@ -103,21 +103,21 @@
1.43 NodeIt(Invalid i) : Node(i) { }
1.44
1.45 explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) {
1.46 - _digraph->first(static_cast<Node&>(*this));
1.47 + _digraph->first(static_cast<Node&>(*this));
1.48 }
1.49
1.50 - NodeIt(const Digraph& digraph, const Node& node)
1.51 - : Node(node), _digraph(&digraph) {}
1.52 + NodeIt(const Digraph& digraph, const Node& node)
1.53 + : Node(node), _digraph(&digraph) {}
1.54
1.55 - NodeIt& operator++() {
1.56 - _digraph->next(*this);
1.57 - return *this;
1.58 + NodeIt& operator++() {
1.59 + _digraph->next(*this);
1.60 + return *this;
1.61 }
1.62
1.63 };
1.64
1.65
1.66 - class ArcIt : public Arc {
1.67 + class ArcIt : public Arc {
1.68 const Digraph* _digraph;
1.69 public:
1.70
1.71 @@ -126,21 +126,21 @@
1.72 ArcIt(Invalid i) : Arc(i) { }
1.73
1.74 explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) {
1.75 - _digraph->first(static_cast<Arc&>(*this));
1.76 + _digraph->first(static_cast<Arc&>(*this));
1.77 }
1.78
1.79 - ArcIt(const Digraph& digraph, const Arc& arc) :
1.80 - Arc(arc), _digraph(&digraph) { }
1.81 + ArcIt(const Digraph& digraph, const Arc& arc) :
1.82 + Arc(arc), _digraph(&digraph) { }
1.83
1.84 - ArcIt& operator++() {
1.85 - _digraph->next(*this);
1.86 - return *this;
1.87 + ArcIt& operator++() {
1.88 + _digraph->next(*this);
1.89 + return *this;
1.90 }
1.91
1.92 };
1.93
1.94
1.95 - class OutArcIt : public Arc {
1.96 + class OutArcIt : public Arc {
1.97 const Digraph* _digraph;
1.98 public:
1.99
1.100 @@ -148,23 +148,23 @@
1.101
1.102 OutArcIt(Invalid i) : Arc(i) { }
1.103
1.104 - OutArcIt(const Digraph& digraph, const Node& node)
1.105 - : _digraph(&digraph) {
1.106 - _digraph->firstOut(*this, node);
1.107 + OutArcIt(const Digraph& digraph, const Node& node)
1.108 + : _digraph(&digraph) {
1.109 + _digraph->firstOut(*this, node);
1.110 }
1.111
1.112 - OutArcIt(const Digraph& digraph, const Arc& arc)
1.113 - : Arc(arc), _digraph(&digraph) {}
1.114 + OutArcIt(const Digraph& digraph, const Arc& arc)
1.115 + : Arc(arc), _digraph(&digraph) {}
1.116
1.117 - OutArcIt& operator++() {
1.118 - _digraph->nextOut(*this);
1.119 - return *this;
1.120 + OutArcIt& operator++() {
1.121 + _digraph->nextOut(*this);
1.122 + return *this;
1.123 }
1.124
1.125 };
1.126
1.127
1.128 - class InArcIt : public Arc {
1.129 + class InArcIt : public Arc {
1.130 const Digraph* _digraph;
1.131 public:
1.132
1.133 @@ -172,17 +172,17 @@
1.134
1.135 InArcIt(Invalid i) : Arc(i) { }
1.136
1.137 - InArcIt(const Digraph& digraph, const Node& node)
1.138 - : _digraph(&digraph) {
1.139 - _digraph->firstIn(*this, node);
1.140 + InArcIt(const Digraph& digraph, const Node& node)
1.141 + : _digraph(&digraph) {
1.142 + _digraph->firstIn(*this, node);
1.143 }
1.144
1.145 - InArcIt(const Digraph& digraph, const Arc& arc) :
1.146 - Arc(arc), _digraph(&digraph) {}
1.147 + InArcIt(const Digraph& digraph, const Arc& arc) :
1.148 + Arc(arc), _digraph(&digraph) {}
1.149
1.150 - InArcIt& operator++() {
1.151 - _digraph->nextIn(*this);
1.152 - return *this;
1.153 + InArcIt& operator++() {
1.154 + _digraph->nextIn(*this);
1.155 + return *this;
1.156 }
1.157
1.158 };
1.159 @@ -215,51 +215,51 @@
1.160 return Parent::source(arc);
1.161 }
1.162
1.163 -
1.164 +
1.165 template <typename _Value>
1.166 - class NodeMap
1.167 + class NodeMap
1.168 : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
1.169 public:
1.170 typedef DigraphExtender Digraph;
1.171 typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
1.172
1.173 - explicit NodeMap(const Digraph& digraph)
1.174 - : Parent(digraph) {}
1.175 - NodeMap(const Digraph& digraph, const _Value& value)
1.176 - : Parent(digraph, value) {}
1.177 + explicit NodeMap(const Digraph& digraph)
1.178 + : Parent(digraph) {}
1.179 + NodeMap(const Digraph& digraph, const _Value& value)
1.180 + : Parent(digraph, value) {}
1.181
1.182 NodeMap& operator=(const NodeMap& cmap) {
1.183 - return operator=<NodeMap>(cmap);
1.184 + return operator=<NodeMap>(cmap);
1.185 }
1.186
1.187 template <typename CMap>
1.188 NodeMap& operator=(const CMap& cmap) {
1.189 Parent::operator=(cmap);
1.190 - return *this;
1.191 + return *this;
1.192 }
1.193
1.194 };
1.195
1.196 template <typename _Value>
1.197 - class ArcMap
1.198 + class ArcMap
1.199 : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
1.200 public:
1.201 typedef DigraphExtender Digraph;
1.202 typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
1.203
1.204 - explicit ArcMap(const Digraph& digraph)
1.205 - : Parent(digraph) {}
1.206 - ArcMap(const Digraph& digraph, const _Value& value)
1.207 - : Parent(digraph, value) {}
1.208 + explicit ArcMap(const Digraph& digraph)
1.209 + : Parent(digraph) {}
1.210 + ArcMap(const Digraph& digraph, const _Value& value)
1.211 + : Parent(digraph, value) {}
1.212
1.213 ArcMap& operator=(const ArcMap& cmap) {
1.214 - return operator=<ArcMap>(cmap);
1.215 + return operator=<ArcMap>(cmap);
1.216 }
1.217
1.218 template <typename CMap>
1.219 ArcMap& operator=(const CMap& cmap) {
1.220 Parent::operator=(cmap);
1.221 - return *this;
1.222 + return *this;
1.223 }
1.224 };
1.225
1.226 @@ -269,7 +269,7 @@
1.227 notifier(Node()).add(node);
1.228 return node;
1.229 }
1.230 -
1.231 +
1.232 Arc addArc(const Node& from, const Node& to) {
1.233 Arc arc = Parent::addArc(from, to);
1.234 notifier(Arc()).add(arc);
1.235 @@ -293,20 +293,20 @@
1.236 Arc arc;
1.237 Parent::firstOut(arc, node);
1.238 while (arc != INVALID ) {
1.239 - erase(arc);
1.240 - Parent::firstOut(arc, node);
1.241 - }
1.242 + erase(arc);
1.243 + Parent::firstOut(arc, node);
1.244 + }
1.245
1.246 Parent::firstIn(arc, node);
1.247 while (arc != INVALID ) {
1.248 - erase(arc);
1.249 - Parent::firstIn(arc, node);
1.250 + erase(arc);
1.251 + Parent::firstIn(arc, node);
1.252 }
1.253
1.254 notifier(Node()).erase(node);
1.255 Parent::erase(node);
1.256 }
1.257 -
1.258 +
1.259 void erase(const Arc& arc) {
1.260 notifier(Arc()).erase(arc);
1.261 Parent::erase(arc);
1.262 @@ -315,8 +315,8 @@
1.263 DigraphExtender() {
1.264 node_notifier.setContainer(*this);
1.265 arc_notifier.setContainer(*this);
1.266 - }
1.267 -
1.268 + }
1.269 +
1.270
1.271 ~DigraphExtender() {
1.272 arc_notifier.clear();
1.273 @@ -327,10 +327,10 @@
1.274 /// \ingroup _graphbits
1.275 ///
1.276 /// \brief Extender for the Graphs
1.277 - template <typename Base>
1.278 + template <typename Base>
1.279 class GraphExtender : public Base {
1.280 public:
1.281 -
1.282 +
1.283 typedef Base Parent;
1.284 typedef GraphExtender Graph;
1.285
1.286 @@ -340,7 +340,7 @@
1.287 typedef typename Parent::Arc Arc;
1.288 typedef typename Parent::Edge Edge;
1.289
1.290 - // Graph extension
1.291 + // Graph extension
1.292
1.293 int maxId(Node) const {
1.294 return Parent::maxNodeId();
1.295 @@ -368,11 +368,11 @@
1.296
1.297 Node oppositeNode(const Node &n, const Edge &e) const {
1.298 if( n == Parent::u(e))
1.299 - return Parent::v(e);
1.300 + return Parent::v(e);
1.301 else if( n == Parent::v(e))
1.302 - return Parent::u(e);
1.303 + return Parent::u(e);
1.304 else
1.305 - return INVALID;
1.306 + return INVALID;
1.307 }
1.308
1.309 Arc oppositeArc(const Arc &arc) const {
1.310 @@ -402,7 +402,7 @@
1.311 NodeNotifier& notifier(Node) const {
1.312 return node_notifier;
1.313 }
1.314 -
1.315 +
1.316 ArcNotifier& notifier(Arc) const {
1.317 return arc_notifier;
1.318 }
1.319 @@ -413,7 +413,7 @@
1.320
1.321
1.322
1.323 - class NodeIt : public Node {
1.324 + class NodeIt : public Node {
1.325 const Graph* _graph;
1.326 public:
1.327
1.328 @@ -422,21 +422,21 @@
1.329 NodeIt(Invalid i) : Node(i) { }
1.330
1.331 explicit NodeIt(const Graph& graph) : _graph(&graph) {
1.332 - _graph->first(static_cast<Node&>(*this));
1.333 + _graph->first(static_cast<Node&>(*this));
1.334 }
1.335
1.336 - NodeIt(const Graph& graph, const Node& node)
1.337 - : Node(node), _graph(&graph) {}
1.338 + NodeIt(const Graph& graph, const Node& node)
1.339 + : Node(node), _graph(&graph) {}
1.340
1.341 - NodeIt& operator++() {
1.342 - _graph->next(*this);
1.343 - return *this;
1.344 + NodeIt& operator++() {
1.345 + _graph->next(*this);
1.346 + return *this;
1.347 }
1.348
1.349 };
1.350
1.351
1.352 - class ArcIt : public Arc {
1.353 + class ArcIt : public Arc {
1.354 const Graph* _graph;
1.355 public:
1.356
1.357 @@ -445,21 +445,21 @@
1.358 ArcIt(Invalid i) : Arc(i) { }
1.359
1.360 explicit ArcIt(const Graph& graph) : _graph(&graph) {
1.361 - _graph->first(static_cast<Arc&>(*this));
1.362 + _graph->first(static_cast<Arc&>(*this));
1.363 }
1.364
1.365 - ArcIt(const Graph& graph, const Arc& arc) :
1.366 - Arc(arc), _graph(&graph) { }
1.367 + ArcIt(const Graph& graph, const Arc& arc) :
1.368 + Arc(arc), _graph(&graph) { }
1.369
1.370 - ArcIt& operator++() {
1.371 - _graph->next(*this);
1.372 - return *this;
1.373 + ArcIt& operator++() {
1.374 + _graph->next(*this);
1.375 + return *this;
1.376 }
1.377
1.378 };
1.379
1.380
1.381 - class OutArcIt : public Arc {
1.382 + class OutArcIt : public Arc {
1.383 const Graph* _graph;
1.384 public:
1.385
1.386 @@ -467,23 +467,23 @@
1.387
1.388 OutArcIt(Invalid i) : Arc(i) { }
1.389
1.390 - OutArcIt(const Graph& graph, const Node& node)
1.391 - : _graph(&graph) {
1.392 - _graph->firstOut(*this, node);
1.393 + OutArcIt(const Graph& graph, const Node& node)
1.394 + : _graph(&graph) {
1.395 + _graph->firstOut(*this, node);
1.396 }
1.397
1.398 - OutArcIt(const Graph& graph, const Arc& arc)
1.399 - : Arc(arc), _graph(&graph) {}
1.400 + OutArcIt(const Graph& graph, const Arc& arc)
1.401 + : Arc(arc), _graph(&graph) {}
1.402
1.403 - OutArcIt& operator++() {
1.404 - _graph->nextOut(*this);
1.405 - return *this;
1.406 + OutArcIt& operator++() {
1.407 + _graph->nextOut(*this);
1.408 + return *this;
1.409 }
1.410
1.411 };
1.412
1.413
1.414 - class InArcIt : public Arc {
1.415 + class InArcIt : public Arc {
1.416 const Graph* _graph;
1.417 public:
1.418
1.419 @@ -491,23 +491,23 @@
1.420
1.421 InArcIt(Invalid i) : Arc(i) { }
1.422
1.423 - InArcIt(const Graph& graph, const Node& node)
1.424 - : _graph(&graph) {
1.425 - _graph->firstIn(*this, node);
1.426 + InArcIt(const Graph& graph, const Node& node)
1.427 + : _graph(&graph) {
1.428 + _graph->firstIn(*this, node);
1.429 }
1.430
1.431 - InArcIt(const Graph& graph, const Arc& arc) :
1.432 - Arc(arc), _graph(&graph) {}
1.433 + InArcIt(const Graph& graph, const Arc& arc) :
1.434 + Arc(arc), _graph(&graph) {}
1.435
1.436 - InArcIt& operator++() {
1.437 - _graph->nextIn(*this);
1.438 - return *this;
1.439 + InArcIt& operator++() {
1.440 + _graph->nextIn(*this);
1.441 + return *this;
1.442 }
1.443
1.444 };
1.445
1.446
1.447 - class EdgeIt : public Parent::Edge {
1.448 + class EdgeIt : public Parent::Edge {
1.449 const Graph* _graph;
1.450 public:
1.451
1.452 @@ -516,15 +516,15 @@
1.453 EdgeIt(Invalid i) : Edge(i) { }
1.454
1.455 explicit EdgeIt(const Graph& graph) : _graph(&graph) {
1.456 - _graph->first(static_cast<Edge&>(*this));
1.457 + _graph->first(static_cast<Edge&>(*this));
1.458 }
1.459
1.460 - EdgeIt(const Graph& graph, const Edge& edge) :
1.461 - Edge(edge), _graph(&graph) { }
1.462 + EdgeIt(const Graph& graph, const Edge& edge) :
1.463 + Edge(edge), _graph(&graph) { }
1.464
1.465 - EdgeIt& operator++() {
1.466 - _graph->next(*this);
1.467 - return *this;
1.468 + EdgeIt& operator++() {
1.469 + _graph->next(*this);
1.470 + return *this;
1.471 }
1.472
1.473 };
1.474 @@ -540,17 +540,17 @@
1.475 IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
1.476
1.477 IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
1.478 - _graph->firstInc(*this, _direction, node);
1.479 + _graph->firstInc(*this, _direction, node);
1.480 }
1.481
1.482 IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)
1.483 - : _graph(&graph), Edge(edge) {
1.484 - _direction = (_graph->source(edge) == node);
1.485 + : _graph(&graph), Edge(edge) {
1.486 + _direction = (_graph->source(edge) == node);
1.487 }
1.488
1.489 IncEdgeIt& operator++() {
1.490 - _graph->nextInc(*this, _direction);
1.491 - return *this;
1.492 + _graph->nextInc(*this, _direction);
1.493 + return *this;
1.494 }
1.495 };
1.496
1.497 @@ -598,74 +598,74 @@
1.498 // Mappable extension
1.499
1.500 template <typename _Value>
1.501 - class NodeMap
1.502 + class NodeMap
1.503 : public MapExtender<DefaultMap<Graph, Node, _Value> > {
1.504 public:
1.505 typedef GraphExtender Graph;
1.506 typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
1.507
1.508 - NodeMap(const Graph& graph)
1.509 - : Parent(graph) {}
1.510 - NodeMap(const Graph& graph, const _Value& value)
1.511 - : Parent(graph, value) {}
1.512 + NodeMap(const Graph& graph)
1.513 + : Parent(graph) {}
1.514 + NodeMap(const Graph& graph, const _Value& value)
1.515 + : Parent(graph, value) {}
1.516
1.517 NodeMap& operator=(const NodeMap& cmap) {
1.518 - return operator=<NodeMap>(cmap);
1.519 + return operator=<NodeMap>(cmap);
1.520 }
1.521
1.522 template <typename CMap>
1.523 NodeMap& operator=(const CMap& cmap) {
1.524 Parent::operator=(cmap);
1.525 - return *this;
1.526 + return *this;
1.527 }
1.528
1.529 };
1.530
1.531 template <typename _Value>
1.532 - class ArcMap
1.533 + class ArcMap
1.534 : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
1.535 public:
1.536 typedef GraphExtender Graph;
1.537 typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
1.538
1.539 - ArcMap(const Graph& graph)
1.540 - : Parent(graph) {}
1.541 - ArcMap(const Graph& graph, const _Value& value)
1.542 - : Parent(graph, value) {}
1.543 + ArcMap(const Graph& graph)
1.544 + : Parent(graph) {}
1.545 + ArcMap(const Graph& graph, const _Value& value)
1.546 + : Parent(graph, value) {}
1.547
1.548 ArcMap& operator=(const ArcMap& cmap) {
1.549 - return operator=<ArcMap>(cmap);
1.550 + return operator=<ArcMap>(cmap);
1.551 }
1.552
1.553 template <typename CMap>
1.554 ArcMap& operator=(const CMap& cmap) {
1.555 Parent::operator=(cmap);
1.556 - return *this;
1.557 + return *this;
1.558 }
1.559 };
1.560
1.561
1.562 template <typename _Value>
1.563 - class EdgeMap
1.564 + class EdgeMap
1.565 : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
1.566 public:
1.567 typedef GraphExtender Graph;
1.568 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
1.569
1.570 - EdgeMap(const Graph& graph)
1.571 - : Parent(graph) {}
1.572 + EdgeMap(const Graph& graph)
1.573 + : Parent(graph) {}
1.574
1.575 - EdgeMap(const Graph& graph, const _Value& value)
1.576 - : Parent(graph, value) {}
1.577 + EdgeMap(const Graph& graph, const _Value& value)
1.578 + : Parent(graph, value) {}
1.579
1.580 EdgeMap& operator=(const EdgeMap& cmap) {
1.581 - return operator=<EdgeMap>(cmap);
1.582 + return operator=<EdgeMap>(cmap);
1.583 }
1.584
1.585 template <typename CMap>
1.586 EdgeMap& operator=(const CMap& cmap) {
1.587 Parent::operator=(cmap);
1.588 - return *this;
1.589 + return *this;
1.590 }
1.591
1.592 };
1.593 @@ -683,11 +683,11 @@
1.594 notifier(Edge()).add(edge);
1.595 std::vector<Arc> ev;
1.596 ev.push_back(Parent::direct(edge, true));
1.597 - ev.push_back(Parent::direct(edge, false));
1.598 + ev.push_back(Parent::direct(edge, false));
1.599 notifier(Arc()).add(ev);
1.600 return edge;
1.601 }
1.602 -
1.603 +
1.604 void clear() {
1.605 notifier(Arc()).clear();
1.606 notifier(Edge()).clear();
1.607 @@ -696,7 +696,7 @@
1.608 }
1.609
1.610 template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
1.611 - void build(const Graph& graph, NodeRefMap& nodeRef,
1.612 + void build(const Graph& graph, NodeRefMap& nodeRef,
1.613 EdgeRefMap& edgeRef) {
1.614 Parent::build(graph, nodeRef, edgeRef);
1.615 notifier(Node()).build();
1.616 @@ -708,14 +708,14 @@
1.617 Arc arc;
1.618 Parent::firstOut(arc, node);
1.619 while (arc != INVALID ) {
1.620 - erase(arc);
1.621 - Parent::firstOut(arc, node);
1.622 - }
1.623 + erase(arc);
1.624 + Parent::firstOut(arc, node);
1.625 + }
1.626
1.627 Parent::firstIn(arc, node);
1.628 while (arc != INVALID ) {
1.629 - erase(arc);
1.630 - Parent::firstIn(arc, node);
1.631 + erase(arc);
1.632 + Parent::firstIn(arc, node);
1.633 }
1.634
1.635 notifier(Node()).erase(node);
1.636 @@ -725,23 +725,23 @@
1.637 void erase(const Edge& edge) {
1.638 std::vector<Arc> av;
1.639 av.push_back(Parent::direct(edge, true));
1.640 - av.push_back(Parent::direct(edge, false));
1.641 + av.push_back(Parent::direct(edge, false));
1.642 notifier(Arc()).erase(av);
1.643 notifier(Edge()).erase(edge);
1.644 Parent::erase(edge);
1.645 }
1.646
1.647 GraphExtender() {
1.648 - node_notifier.setContainer(*this);
1.649 + node_notifier.setContainer(*this);
1.650 arc_notifier.setContainer(*this);
1.651 edge_notifier.setContainer(*this);
1.652 - }
1.653 + }
1.654
1.655 ~GraphExtender() {
1.656 edge_notifier.clear();
1.657 arc_notifier.clear();
1.658 - node_notifier.clear();
1.659 - }
1.660 + node_notifier.clear();
1.661 + }
1.662
1.663 };
1.664