1.1 --- a/lemon/concepts/graph.h Sun Jul 13 16:46:56 2008 +0100
1.2 +++ b/lemon/concepts/graph.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 @@ -65,23 +65,23 @@
1.13 /// OutArcIt iterates on the same edges but with opposite
1.14 /// direction. The IncEdgeIt iterates also on the same edges
1.15 /// as the OutArcIt and InArcIt but it is not convertible to Arc just
1.16 - /// to Edge.
1.17 + /// to Edge.
1.18 class Graph {
1.19 public:
1.20 /// \brief The undirected graph should be tagged by the
1.21 /// UndirectedTag.
1.22 ///
1.23 /// The undirected graph should be tagged by the UndirectedTag. This
1.24 - /// tag helps the enable_if technics to make compile time
1.25 - /// specializations for undirected graphs.
1.26 + /// tag helps the enable_if technics to make compile time
1.27 + /// specializations for undirected graphs.
1.28 typedef True UndirectedTag;
1.29
1.30 - /// \brief The base type of node iterators,
1.31 + /// \brief The base type of node iterators,
1.32 /// or in other words, the trivial node iterator.
1.33 ///
1.34 /// This is the base type of each node iterator,
1.35 /// thus each kind of node iterator converts to this.
1.36 - /// More precisely each kind of node iterator should be inherited
1.37 + /// More precisely each kind of node iterator should be inherited
1.38 /// from the trivial node iterator.
1.39 class Node {
1.40 public:
1.41 @@ -108,23 +108,23 @@
1.42 bool operator==(Node) const { return true; }
1.43
1.44 /// Inequality operator
1.45 -
1.46 +
1.47 /// \sa operator==(Node n)
1.48 ///
1.49 bool operator!=(Node) const { return true; }
1.50
1.51 - /// Artificial ordering operator.
1.52 -
1.53 - /// To allow the use of graph descriptors as key type in std::map or
1.54 - /// similar associative container we require this.
1.55 - ///
1.56 - /// \note This operator only have to define some strict ordering of
1.57 - /// the items; this order has nothing to do with the iteration
1.58 - /// ordering of the items.
1.59 - bool operator<(Node) const { return false; }
1.60 + /// Artificial ordering operator.
1.61 +
1.62 + /// To allow the use of graph descriptors as key type in std::map or
1.63 + /// similar associative container we require this.
1.64 + ///
1.65 + /// \note This operator only have to define some strict ordering of
1.66 + /// the items; this order has nothing to do with the iteration
1.67 + /// ordering of the items.
1.68 + bool operator<(Node) const { return false; }
1.69
1.70 };
1.71 -
1.72 +
1.73 /// This iterator goes through each node.
1.74
1.75 /// This iterator goes through each node.
1.76 @@ -142,7 +142,7 @@
1.77 /// to an undefined value.
1.78 NodeIt() { }
1.79 /// Copy constructor.
1.80 -
1.81 +
1.82 /// Copy constructor.
1.83 ///
1.84 NodeIt(const NodeIt& n) : Node(n) { }
1.85 @@ -158,9 +158,9 @@
1.86 NodeIt(const Graph&) { }
1.87 /// Node -> NodeIt conversion.
1.88
1.89 - /// Sets the iterator to the node of \c the graph pointed by
1.90 - /// the trivial iterator.
1.91 - /// This feature necessitates that each time we
1.92 + /// Sets the iterator to the node of \c the graph pointed by
1.93 + /// the trivial iterator.
1.94 + /// This feature necessitates that each time we
1.95 /// iterate the arc-set, the iteration order is the same.
1.96 NodeIt(const Graph&, const Node&) { }
1.97 /// Next node.
1.98 @@ -169,8 +169,8 @@
1.99 ///
1.100 NodeIt& operator++() { return *this; }
1.101 };
1.102 -
1.103 -
1.104 +
1.105 +
1.106 /// The base type of the edge iterators.
1.107
1.108 /// The base type of the edge iterators.
1.109 @@ -203,15 +203,15 @@
1.110 ///
1.111 bool operator!=(Edge) const { return true; }
1.112
1.113 - /// Artificial ordering operator.
1.114 -
1.115 - /// To allow the use of graph descriptors as key type in std::map or
1.116 - /// similar associative container we require this.
1.117 - ///
1.118 - /// \note This operator only have to define some strict ordering of
1.119 - /// the items; this order has nothing to do with the iteration
1.120 - /// ordering of the items.
1.121 - bool operator<(Edge) const { return false; }
1.122 + /// Artificial ordering operator.
1.123 +
1.124 + /// To allow the use of graph descriptors as key type in std::map or
1.125 + /// similar associative container we require this.
1.126 + ///
1.127 + /// \note This operator only have to define some strict ordering of
1.128 + /// the items; this order has nothing to do with the iteration
1.129 + /// ordering of the items.
1.130 + bool operator<(Edge) const { return false; }
1.131 };
1.132
1.133 /// This iterator goes through each edge.
1.134 @@ -241,32 +241,32 @@
1.135 ///
1.136 EdgeIt(Invalid) { }
1.137 /// This constructor sets the iterator to the first edge.
1.138 -
1.139 +
1.140 /// This constructor sets the iterator to the first edge.
1.141 EdgeIt(const Graph&) { }
1.142 /// Edge -> EdgeIt conversion
1.143
1.144 /// Sets the iterator to the value of the trivial iterator.
1.145 /// This feature necessitates that each time we
1.146 - /// iterate the edge-set, the iteration order is the
1.147 - /// same.
1.148 - EdgeIt(const Graph&, const Edge&) { }
1.149 + /// iterate the edge-set, the iteration order is the
1.150 + /// same.
1.151 + EdgeIt(const Graph&, const Edge&) { }
1.152 /// Next edge
1.153 -
1.154 +
1.155 /// Assign the iterator to the next edge.
1.156 EdgeIt& operator++() { return *this; }
1.157 };
1.158
1.159 - /// \brief This iterator goes trough the incident undirected
1.160 + /// \brief This iterator goes trough the incident undirected
1.161 /// arcs of a node.
1.162 ///
1.163 /// This iterator goes trough the incident edges
1.164 - /// of a certain node of a graph. You should assume that the
1.165 + /// of a certain node of a graph. You should assume that the
1.166 /// loop arcs will be iterated twice.
1.167 - ///
1.168 + ///
1.169 /// Its usage is quite simple, for example you can compute the
1.170 /// degree (i.e. count the number of incident arcs of a node \c n
1.171 - /// in graph \c g of type \c Graph as follows.
1.172 + /// in graph \c g of type \c Graph as follows.
1.173 ///
1.174 ///\code
1.175 /// int count=0;
1.176 @@ -290,20 +290,20 @@
1.177 ///
1.178 IncEdgeIt(Invalid) { }
1.179 /// This constructor sets the iterator to first incident arc.
1.180 -
1.181 +
1.182 /// This constructor set the iterator to the first incident arc of
1.183 /// the node.
1.184 IncEdgeIt(const Graph&, const Node&) { }
1.185 /// Edge -> IncEdgeIt conversion
1.186
1.187 /// Sets the iterator to the value of the trivial iterator \c e.
1.188 - /// This feature necessitates that each time we
1.189 + /// This feature necessitates that each time we
1.190 /// iterate the arc-set, the iteration order is the same.
1.191 IncEdgeIt(const Graph&, const Edge&) { }
1.192 /// Next incident arc
1.193
1.194 /// Assign the iterator to the next incident arc
1.195 - /// of the corresponding node.
1.196 + /// of the corresponding node.
1.197 IncEdgeIt& operator++() { return *this; }
1.198 };
1.199
1.200 @@ -340,17 +340,17 @@
1.201 ///
1.202 bool operator!=(Arc) const { return true; }
1.203
1.204 - /// Artificial ordering operator.
1.205 -
1.206 - /// To allow the use of graph descriptors as key type in std::map or
1.207 - /// similar associative container we require this.
1.208 - ///
1.209 - /// \note This operator only have to define some strict ordering of
1.210 - /// the items; this order has nothing to do with the iteration
1.211 - /// ordering of the items.
1.212 - bool operator<(Arc) const { return false; }
1.213 -
1.214 - };
1.215 + /// Artificial ordering operator.
1.216 +
1.217 + /// To allow the use of graph descriptors as key type in std::map or
1.218 + /// similar associative container we require this.
1.219 + ///
1.220 + /// \note This operator only have to define some strict ordering of
1.221 + /// the items; this order has nothing to do with the iteration
1.222 + /// ordering of the items.
1.223 + bool operator<(Arc) const { return false; }
1.224 +
1.225 + };
1.226 /// This iterator goes through each directed arc.
1.227
1.228 /// This iterator goes through each arc of a graph.
1.229 @@ -378,22 +378,22 @@
1.230 ///
1.231 ArcIt(Invalid) { }
1.232 /// This constructor sets the iterator to the first arc.
1.233 -
1.234 +
1.235 /// This constructor sets the iterator to the first arc of \c g.
1.236 ///@param g the graph
1.237 ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
1.238 /// Arc -> ArcIt conversion
1.239
1.240 /// Sets the iterator to the value of the trivial iterator \c e.
1.241 - /// This feature necessitates that each time we
1.242 + /// This feature necessitates that each time we
1.243 /// iterate the arc-set, the iteration order is the same.
1.244 - ArcIt(const Graph&, const Arc&) { }
1.245 + ArcIt(const Graph&, const Arc&) { }
1.246 ///Next arc
1.247 -
1.248 +
1.249 /// Assign the iterator to the next arc.
1.250 ArcIt& operator++() { return *this; }
1.251 };
1.252 -
1.253 +
1.254 /// This iterator goes trough the outgoing directed arcs of a node.
1.255
1.256 /// This iterator goes trough the \e outgoing arcs of a certain node
1.257 @@ -405,7 +405,7 @@
1.258 /// int count=0;
1.259 /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
1.260 ///\endcode
1.261 -
1.262 +
1.263 class OutArcIt : public Arc {
1.264 public:
1.265 /// Default constructor
1.266 @@ -424,24 +424,24 @@
1.267 ///
1.268 OutArcIt(Invalid) { }
1.269 /// This constructor sets the iterator to the first outgoing arc.
1.270 -
1.271 +
1.272 /// This constructor sets the iterator to the first outgoing arc of
1.273 /// the node.
1.274 ///@param n the node
1.275 ///@param g the graph
1.276 OutArcIt(const Graph& n, const Node& g) {
1.277 - ignore_unused_variable_warning(n);
1.278 - ignore_unused_variable_warning(g);
1.279 - }
1.280 + ignore_unused_variable_warning(n);
1.281 + ignore_unused_variable_warning(g);
1.282 + }
1.283 /// Arc -> OutArcIt conversion
1.284
1.285 /// Sets the iterator to the value of the trivial iterator.
1.286 - /// This feature necessitates that each time we
1.287 + /// This feature necessitates that each time we
1.288 /// iterate the arc-set, the iteration order is the same.
1.289 OutArcIt(const Graph&, const Arc&) { }
1.290 ///Next outgoing arc
1.291 -
1.292 - /// Assign the iterator to the next
1.293 +
1.294 + /// Assign the iterator to the next
1.295 /// outgoing arc of the corresponding node.
1.296 OutArcIt& operator++() { return *this; }
1.297 };
1.298 @@ -476,19 +476,19 @@
1.299 ///
1.300 InArcIt(Invalid) { }
1.301 /// This constructor sets the iterator to first incoming arc.
1.302 -
1.303 +
1.304 /// This constructor set the iterator to the first incoming arc of
1.305 /// the node.
1.306 ///@param n the node
1.307 ///@param g the graph
1.308 - InArcIt(const Graph& g, const Node& n) {
1.309 - ignore_unused_variable_warning(n);
1.310 - ignore_unused_variable_warning(g);
1.311 - }
1.312 + InArcIt(const Graph& g, const Node& n) {
1.313 + ignore_unused_variable_warning(n);
1.314 + ignore_unused_variable_warning(g);
1.315 + }
1.316 /// Arc -> InArcIt conversion
1.317
1.318 /// Sets the iterator to the value of the trivial iterator \c e.
1.319 - /// This feature necessitates that each time we
1.320 + /// This feature necessitates that each time we
1.321 /// iterate the arc-set, the iteration order is the same.
1.322 InArcIt(const Graph&, const Arc&) { }
1.323 /// Next incoming arc
1.324 @@ -499,10 +499,10 @@
1.325 };
1.326
1.327 /// \brief Read write map of the nodes to type \c T.
1.328 - ///
1.329 + ///
1.330 /// ReadWrite map of the nodes to type \c T.
1.331 /// \sa Reference
1.332 - template<class T>
1.333 + template<class T>
1.334 class NodeMap : public ReadWriteMap< Node, T >
1.335 {
1.336 public:
1.337 @@ -516,9 +516,9 @@
1.338 NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
1.339 ///Assignment operator
1.340 template <typename CMap>
1.341 - NodeMap& operator=(const CMap&) {
1.342 + NodeMap& operator=(const CMap&) {
1.343 checkConcept<ReadMap<Node, T>, CMap>();
1.344 - return *this;
1.345 + return *this;
1.346 }
1.347 };
1.348
1.349 @@ -526,7 +526,7 @@
1.350 ///
1.351 /// Reference map of the directed arcs to type \c T.
1.352 /// \sa Reference
1.353 - template<class T>
1.354 + template<class T>
1.355 class ArcMap : public ReadWriteMap<Arc,T>
1.356 {
1.357 public:
1.358 @@ -539,9 +539,9 @@
1.359 ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
1.360 ///Assignment operator
1.361 template <typename CMap>
1.362 - ArcMap& operator=(const CMap&) {
1.363 + ArcMap& operator=(const CMap&) {
1.364 checkConcept<ReadMap<Arc, T>, CMap>();
1.365 - return *this;
1.366 + return *this;
1.367 }
1.368 };
1.369
1.370 @@ -549,7 +549,7 @@
1.371
1.372 /// Reference map of the arcs to type \c T.
1.373 /// \sa Reference
1.374 - template<class T>
1.375 + template<class T>
1.376 class EdgeMap : public ReadWriteMap<Edge,T>
1.377 {
1.378 public:
1.379 @@ -562,9 +562,9 @@
1.380 EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {}
1.381 ///Assignment operator
1.382 template <typename CMap>
1.383 - EdgeMap& operator=(const CMap&) {
1.384 + EdgeMap& operator=(const CMap&) {
1.385 checkConcept<ReadMap<Edge, T>, CMap>();
1.386 - return *this;
1.387 + return *this;
1.388 }
1.389 };
1.390
1.391 @@ -573,7 +573,7 @@
1.392 /// Direct the given edge. The returned arc source
1.393 /// will be the given node.
1.394 Arc direct(const Edge&, const Node&) const {
1.395 - return INVALID;
1.396 + return INVALID;
1.397 }
1.398
1.399 /// \brief Direct the given edge.
1.400 @@ -583,7 +583,7 @@
1.401 /// from the bool parameter. The source of the edge and
1.402 /// the directed arc is the same when the given bool is true.
1.403 Arc direct(const Edge&, bool) const {
1.404 - return INVALID;
1.405 + return INVALID;
1.406 }
1.407
1.408 /// \brief Returns true if the arc has default orientation.
1.409 @@ -625,37 +625,37 @@
1.410 Node target(Arc) const { return INVALID; }
1.411
1.412 /// \brief Returns the id of the node.
1.413 - int id(Node) const { return -1; }
1.414 + int id(Node) const { return -1; }
1.415
1.416 /// \brief Returns the id of the edge.
1.417 - int id(Edge) const { return -1; }
1.418 + int id(Edge) const { return -1; }
1.419
1.420 /// \brief Returns the id of the arc.
1.421 - int id(Arc) const { return -1; }
1.422 + int id(Arc) const { return -1; }
1.423
1.424 /// \brief Returns the node with the given id.
1.425 ///
1.426 /// \pre The argument should be a valid node id in the graph.
1.427 - Node nodeFromId(int) const { return INVALID; }
1.428 + Node nodeFromId(int) const { return INVALID; }
1.429
1.430 /// \brief Returns the edge with the given id.
1.431 ///
1.432 /// \pre The argument should be a valid edge id in the graph.
1.433 - Edge edgeFromId(int) const { return INVALID; }
1.434 + Edge edgeFromId(int) const { return INVALID; }
1.435
1.436 /// \brief Returns the arc with the given id.
1.437 ///
1.438 /// \pre The argument should be a valid arc id in the graph.
1.439 - Arc arcFromId(int) const { return INVALID; }
1.440 + Arc arcFromId(int) const { return INVALID; }
1.441
1.442 /// \brief Returns an upper bound on the node IDs.
1.443 - int maxNodeId() const { return -1; }
1.444 + int maxNodeId() const { return -1; }
1.445
1.446 /// \brief Returns an upper bound on the edge IDs.
1.447 - int maxEdgeId() const { return -1; }
1.448 + int maxEdgeId() const { return -1; }
1.449
1.450 /// \brief Returns an upper bound on the arc IDs.
1.451 - int maxArcId() const { return -1; }
1.452 + int maxArcId() const { return -1; }
1.453
1.454 void first(Node&) const {}
1.455 void next(Node&) const {}
1.456 @@ -683,61 +683,61 @@
1.457 Arc fromId(int, Arc) const { return INVALID; }
1.458
1.459 // Dummy parameter.
1.460 - int maxId(Node) const { return -1; }
1.461 + int maxId(Node) const { return -1; }
1.462 // Dummy parameter.
1.463 - int maxId(Edge) const { return -1; }
1.464 + int maxId(Edge) const { return -1; }
1.465 // Dummy parameter.
1.466 - int maxId(Arc) const { return -1; }
1.467 + int maxId(Arc) const { return -1; }
1.468
1.469 /// \brief Base node of the iterator
1.470 ///
1.471 /// Returns the base node (the source in this case) of the iterator
1.472 Node baseNode(OutArcIt e) const {
1.473 - return source(e);
1.474 + return source(e);
1.475 }
1.476 /// \brief Running node of the iterator
1.477 ///
1.478 /// Returns the running node (the target in this case) of the
1.479 /// iterator
1.480 Node runningNode(OutArcIt e) const {
1.481 - return target(e);
1.482 + return target(e);
1.483 }
1.484
1.485 /// \brief Base node of the iterator
1.486 ///
1.487 /// Returns the base node (the target in this case) of the iterator
1.488 Node baseNode(InArcIt e) const {
1.489 - return target(e);
1.490 + return target(e);
1.491 }
1.492 /// \brief Running node of the iterator
1.493 ///
1.494 /// Returns the running node (the source in this case) of the
1.495 /// iterator
1.496 Node runningNode(InArcIt e) const {
1.497 - return source(e);
1.498 + return source(e);
1.499 }
1.500
1.501 /// \brief Base node of the iterator
1.502 ///
1.503 /// Returns the base node of the iterator
1.504 Node baseNode(IncEdgeIt) const {
1.505 - return INVALID;
1.506 + return INVALID;
1.507 }
1.508 -
1.509 +
1.510 /// \brief Running node of the iterator
1.511 ///
1.512 /// Returns the running node of the iterator
1.513 Node runningNode(IncEdgeIt) const {
1.514 - return INVALID;
1.515 + return INVALID;
1.516 }
1.517
1.518 template <typename _Graph>
1.519 struct Constraints {
1.520 - void constraints() {
1.521 - checkConcept<IterableGraphComponent<>, _Graph>();
1.522 - checkConcept<IDableGraphComponent<>, _Graph>();
1.523 - checkConcept<MappableGraphComponent<>, _Graph>();
1.524 - }
1.525 + void constraints() {
1.526 + checkConcept<IterableGraphComponent<>, _Graph>();
1.527 + checkConcept<IDableGraphComponent<>, _Graph>();
1.528 + checkConcept<MappableGraphComponent<>, _Graph>();
1.529 + }
1.530 };
1.531
1.532 };