1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/full_graph.h Thu Aug 14 21:49:39 2008 +0200
1.3 @@ -0,0 +1,608 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
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_FULL_GRAPH_H
1.23 +#define LEMON_FULL_GRAPH_H
1.24 +
1.25 +#include <lemon/math.h>
1.26 +
1.27 +#include <lemon/core.h>
1.28 +#include <lemon/bits/graph_extender.h>
1.29 +
1.30 +///\ingroup graphs
1.31 +///\file
1.32 +///\brief FullDigraph and FullGraph classes.
1.33 +namespace lemon {
1.34 +
1.35 + class FullDigraphBase {
1.36 + public:
1.37 +
1.38 + typedef FullDigraphBase Graph;
1.39 +
1.40 + class Node;
1.41 + class Arc;
1.42 +
1.43 + protected:
1.44 +
1.45 + int _node_num;
1.46 + int _arc_num;
1.47 +
1.48 + FullDigraphBase() {}
1.49 +
1.50 + void construct(int n) { _node_num = n; _arc_num = n * n; }
1.51 +
1.52 + public:
1.53 +
1.54 + typedef True NodeNumTag;
1.55 + typedef True ArcNumTag;
1.56 +
1.57 + Node operator()(int ix) const { return Node(ix); }
1.58 + int index(const Node& node) const { return node._id; }
1.59 +
1.60 + Arc arc(const Node& s, const Node& t) const {
1.61 + return Arc(s._id * _node_num + t._id);
1.62 + }
1.63 +
1.64 + int nodeNum() const { return _node_num; }
1.65 + int arcNum() const { return _arc_num; }
1.66 +
1.67 + int maxNodeId() const { return _node_num - 1; }
1.68 + int maxArcId() const { return _arc_num - 1; }
1.69 +
1.70 + Node source(Arc arc) const { return arc._id / _node_num; }
1.71 + Node target(Arc arc) const { return arc._id % _node_num; }
1.72 +
1.73 +
1.74 + static int id(Node node) { return node._id; }
1.75 + static int id(Arc arc) { return arc._id; }
1.76 +
1.77 + static Node nodeFromId(int id) { return Node(id);}
1.78 +
1.79 + static Arc arcFromId(int id) { return Arc(id);}
1.80 +
1.81 + typedef True FindArcTag;
1.82 +
1.83 + Arc findArc(Node s, Node t, Arc prev = INVALID) const {
1.84 + return prev != INVALID ? arc(s, t) : INVALID;
1.85 + }
1.86 +
1.87 +
1.88 + class Node {
1.89 + friend class FullDigraphBase;
1.90 +
1.91 + protected:
1.92 + int _id;
1.93 + Node(int id) : _id(id) {}
1.94 + public:
1.95 + Node() {}
1.96 + Node (Invalid) : _id(-1) {}
1.97 + bool operator==(const Node node) const {return _id == node._id;}
1.98 + bool operator!=(const Node node) const {return _id != node._id;}
1.99 + bool operator<(const Node node) const {return _id < node._id;}
1.100 + };
1.101 +
1.102 + class Arc {
1.103 + friend class FullDigraphBase;
1.104 +
1.105 + protected:
1.106 + int _id; // _node_num * source + target;
1.107 +
1.108 + Arc(int id) : _id(id) {}
1.109 +
1.110 + public:
1.111 + Arc() { }
1.112 + Arc (Invalid) { _id = -1; }
1.113 + bool operator==(const Arc arc) const {return _id == arc._id;}
1.114 + bool operator!=(const Arc arc) const {return _id != arc._id;}
1.115 + bool operator<(const Arc arc) const {return _id < arc._id;}
1.116 + };
1.117 +
1.118 + void first(Node& node) const {
1.119 + node._id = _node_num - 1;
1.120 + }
1.121 +
1.122 + static void next(Node& node) {
1.123 + --node._id;
1.124 + }
1.125 +
1.126 + void first(Arc& arc) const {
1.127 + arc._id = _arc_num - 1;
1.128 + }
1.129 +
1.130 + static void next(Arc& arc) {
1.131 + --arc._id;
1.132 + }
1.133 +
1.134 + void firstOut(Arc& arc, const Node& node) const {
1.135 + arc._id = (node._id + 1) * _node_num - 1;
1.136 + }
1.137 +
1.138 + void nextOut(Arc& arc) const {
1.139 + if (arc._id % _node_num == 0) arc._id = 0;
1.140 + --arc._id;
1.141 + }
1.142 +
1.143 + void firstIn(Arc& arc, const Node& node) const {
1.144 + arc._id = _arc_num + node._id - _node_num;
1.145 + }
1.146 +
1.147 + void nextIn(Arc& arc) const {
1.148 + arc._id -= _node_num;
1.149 + if (arc._id < 0) arc._id = -1;
1.150 + }
1.151 +
1.152 + };
1.153 +
1.154 + typedef DigraphExtender<FullDigraphBase> ExtendedFullDigraphBase;
1.155 +
1.156 + /// \ingroup graphs
1.157 + ///
1.158 + /// \brief A full digraph class.
1.159 + ///
1.160 + /// This is a simple and fast directed full graph implementation.
1.161 + /// From each node go arcs to each node (including the source node),
1.162 + /// therefore the number of the arcs in the digraph is the square of
1.163 + /// the node number. The digraph is completely static, so you can
1.164 + /// neither add nor delete either arcs or nodes, and it needs just
1.165 + /// constant space in memory.
1.166 + ///
1.167 + /// Thus it conforms to the \ref concepts::Digraph "Digraph" concept
1.168 + /// and it also has an important extra feature that its maps are
1.169 + /// real \ref concepts::ReferenceMap "reference map"s.
1.170 + /// \sa concepts::Digraph.
1.171 + ///
1.172 + /// \sa FullGraph
1.173 + class FullDigraph : public ExtendedFullDigraphBase {
1.174 + public:
1.175 +
1.176 + typedef ExtendedFullDigraphBase Parent;
1.177 +
1.178 + /// \brief Constructor
1.179 + FullDigraph() { construct(0); }
1.180 +
1.181 + /// \brief Constructor
1.182 + ///
1.183 + /// \param n The number of the nodes.
1.184 + FullDigraph(int n) { construct(n); }
1.185 +
1.186 + /// \brief Resize the digraph
1.187 + ///
1.188 + /// Resize the digraph. The function will fully destroy and
1.189 + /// rebuild the digraph. This cause that the maps of the digraph
1.190 + /// will reallocated automatically and the previous values will be
1.191 + /// lost.
1.192 + void resize(int n) {
1.193 + Parent::notifier(Arc()).clear();
1.194 + Parent::notifier(Node()).clear();
1.195 + construct(n);
1.196 + Parent::notifier(Node()).build();
1.197 + Parent::notifier(Arc()).build();
1.198 + }
1.199 +
1.200 + /// \brief Returns the node with the given index.
1.201 + ///
1.202 + /// Returns the node with the given index. Because it is a
1.203 + /// static size digraph the node's of the digraph can be indexed
1.204 + /// in the range <tt>[0..nodeNum()-1]</tt> and the index of
1.205 + /// the node can accessed by the \e index() member.
1.206 + Node operator()(int ix) const { return Parent::operator()(ix); }
1.207 +
1.208 + /// \brief Returns the index of the node.
1.209 + ///
1.210 + /// Returns the index of the node. Because it is a
1.211 + /// static size digraph the node's of the digraph can be indexed
1.212 + /// in the range <tt>[0..nodeNum()-1]</tt> and the index of
1.213 + /// the node can accessed by the \e index() member.
1.214 + int index(const Node& node) const { return Parent::index(node); }
1.215 +
1.216 + /// \brief Returns the arc connects the given nodes.
1.217 + ///
1.218 + /// Returns the arc connects the given nodes.
1.219 + Arc arc(const Node& u, const Node& v) const {
1.220 + return Parent::arc(u, v);
1.221 + }
1.222 +
1.223 + /// \brief Number of nodes.
1.224 + int nodeNum() const { return Parent::nodeNum(); }
1.225 + /// \brief Number of arcs.
1.226 + int arcNum() const { return Parent::arcNum(); }
1.227 + };
1.228 +
1.229 +
1.230 + class FullGraphBase {
1.231 + int _node_num;
1.232 + int _edge_num;
1.233 + public:
1.234 +
1.235 + typedef FullGraphBase Graph;
1.236 +
1.237 + class Node;
1.238 + class Arc;
1.239 + class Edge;
1.240 +
1.241 + protected:
1.242 +
1.243 + FullGraphBase() {}
1.244 +
1.245 + void construct(int n) { _node_num = n; _edge_num = n * (n - 1) / 2; }
1.246 +
1.247 + int _uid(int e) const {
1.248 + int u = e / _node_num;
1.249 + int v = e % _node_num;
1.250 + return u < v ? u : _node_num - 2 - u;
1.251 + }
1.252 +
1.253 + int _vid(int e) const {
1.254 + int u = e / _node_num;
1.255 + int v = e % _node_num;
1.256 + return u < v ? v : _node_num - 1 - v;
1.257 + }
1.258 +
1.259 + void _uvid(int e, int& u, int& v) const {
1.260 + u = e / _node_num;
1.261 + v = e % _node_num;
1.262 + if (u >= v) {
1.263 + u = _node_num - 2 - u;
1.264 + v = _node_num - 1 - v;
1.265 + }
1.266 + }
1.267 +
1.268 + void _stid(int a, int& s, int& t) const {
1.269 + if ((a & 1) == 1) {
1.270 + _uvid(a >> 1, s, t);
1.271 + } else {
1.272 + _uvid(a >> 1, t, s);
1.273 + }
1.274 + }
1.275 +
1.276 + int _eid(int u, int v) const {
1.277 + if (u < (_node_num - 1) / 2) {
1.278 + return u * _node_num + v;
1.279 + } else {
1.280 + return (_node_num - 1 - u) * _node_num - v - 1;
1.281 + }
1.282 + }
1.283 +
1.284 + public:
1.285 +
1.286 +
1.287 + Node operator()(int ix) const { return Node(ix); }
1.288 + int index(const Node& node) const { return node._id; }
1.289 +
1.290 + Edge edge(const Node& u, const Node& v) const {
1.291 + if (u._id < v._id) {
1.292 + return Edge(_eid(u._id, v._id));
1.293 + } else if (u._id != v._id) {
1.294 + return Edge(_eid(v._id, u._id));
1.295 + } else {
1.296 + return INVALID;
1.297 + }
1.298 + }
1.299 +
1.300 + Arc arc(const Node& s, const Node& t) const {
1.301 + if (s._id < t._id) {
1.302 + return Arc((_eid(s._id, t._id) << 1) | 1);
1.303 + } else if (s._id != t._id) {
1.304 + return Arc(_eid(t._id, s._id) << 1);
1.305 + } else {
1.306 + return INVALID;
1.307 + }
1.308 + }
1.309 +
1.310 + typedef True NodeNumTag;
1.311 + typedef True EdgeNumTag;
1.312 +
1.313 + int nodeNum() const { return _node_num; }
1.314 + int arcNum() const { return 2 * _edge_num; }
1.315 + int edgeNum() const { return _edge_num; }
1.316 +
1.317 + static int id(Node node) { return node._id; }
1.318 + static int id(Arc arc) { return arc._id; }
1.319 + static int id(Edge edge) { return edge._id; }
1.320 +
1.321 + int maxNodeId() const { return _node_num-1; }
1.322 + int maxArcId() const { return 2 * _edge_num-1; }
1.323 + int maxEdgeId() const { return _edge_num-1; }
1.324 +
1.325 + static Node nodeFromId(int id) { return Node(id);}
1.326 + static Arc arcFromId(int id) { return Arc(id);}
1.327 + static Edge edgeFromId(int id) { return Edge(id);}
1.328 +
1.329 + Node u(Edge edge) const {
1.330 + return Node(_uid(edge._id));
1.331 + }
1.332 +
1.333 + Node v(Edge edge) const {
1.334 + return Node(_vid(edge._id));
1.335 + }
1.336 +
1.337 + Node source(Arc arc) const {
1.338 + return Node((arc._id & 1) == 1 ?
1.339 + _uid(arc._id >> 1) : _vid(arc._id >> 1));
1.340 + }
1.341 +
1.342 + Node target(Arc arc) const {
1.343 + return Node((arc._id & 1) == 1 ?
1.344 + _vid(arc._id >> 1) : _uid(arc._id >> 1));
1.345 + }
1.346 +
1.347 + typedef True FindEdgeTag;
1.348 +
1.349 + Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
1.350 + return prev != INVALID ? INVALID : edge(u, v);
1.351 + }
1.352 +
1.353 + Arc findArc(Node s, Node t, Arc prev = INVALID) const {
1.354 + return prev != INVALID ? INVALID : arc(s, t);
1.355 + }
1.356 +
1.357 + class Node {
1.358 + friend class FullGraphBase;
1.359 +
1.360 + protected:
1.361 + int _id;
1.362 + Node(int id) : _id(id) {}
1.363 + public:
1.364 + Node() {}
1.365 + Node (Invalid) { _id = -1; }
1.366 + bool operator==(const Node node) const {return _id == node._id;}
1.367 + bool operator!=(const Node node) const {return _id != node._id;}
1.368 + bool operator<(const Node node) const {return _id < node._id;}
1.369 + };
1.370 +
1.371 + class Edge {
1.372 + friend class FullGraphBase;
1.373 +
1.374 + protected:
1.375 + int _id;
1.376 +
1.377 + Edge(int id) : _id(id) {}
1.378 +
1.379 + public:
1.380 + Edge() { }
1.381 + Edge (Invalid) { _id = -1; }
1.382 +
1.383 + bool operator==(const Edge edge) const {return _id == edge._id;}
1.384 + bool operator!=(const Edge edge) const {return _id != edge._id;}
1.385 + bool operator<(const Edge edge) const {return _id < edge._id;}
1.386 + };
1.387 +
1.388 + class Arc {
1.389 + friend class FullGraphBase;
1.390 +
1.391 + protected:
1.392 + int _id;
1.393 +
1.394 + Arc(int id) : _id(id) {}
1.395 +
1.396 + public:
1.397 + Arc() { }
1.398 + Arc (Invalid) { _id = -1; }
1.399 +
1.400 + operator Edge() const { return Edge(_id != -1 ? (_id >> 1) : -1); }
1.401 +
1.402 + bool operator==(const Arc arc) const {return _id == arc._id;}
1.403 + bool operator!=(const Arc arc) const {return _id != arc._id;}
1.404 + bool operator<(const Arc arc) const {return _id < arc._id;}
1.405 + };
1.406 +
1.407 + static bool direction(Arc arc) {
1.408 + return (arc._id & 1) == 1;
1.409 + }
1.410 +
1.411 + static Arc direct(Edge edge, bool dir) {
1.412 + return Arc((edge._id << 1) | (dir ? 1 : 0));
1.413 + }
1.414 +
1.415 + void first(Node& node) const {
1.416 + node._id = _node_num - 1;
1.417 + }
1.418 +
1.419 + static void next(Node& node) {
1.420 + --node._id;
1.421 + }
1.422 +
1.423 + void first(Arc& arc) const {
1.424 + arc._id = (_edge_num << 1) - 1;
1.425 + }
1.426 +
1.427 + static void next(Arc& arc) {
1.428 + --arc._id;
1.429 + }
1.430 +
1.431 + void first(Edge& edge) const {
1.432 + edge._id = _edge_num - 1;
1.433 + }
1.434 +
1.435 + static void next(Edge& edge) {
1.436 + --edge._id;
1.437 + }
1.438 +
1.439 + void firstOut(Arc& arc, const Node& node) const {
1.440 + int s = node._id, t = _node_num - 1;
1.441 + if (s < t) {
1.442 + arc._id = (_eid(s, t) << 1) | 1;
1.443 + } else {
1.444 + --t;
1.445 + arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
1.446 + }
1.447 + }
1.448 +
1.449 + void nextOut(Arc& arc) const {
1.450 + int s, t;
1.451 + _stid(arc._id, s, t);
1.452 + --t;
1.453 + if (s < t) {
1.454 + arc._id = (_eid(s, t) << 1) | 1;
1.455 + } else {
1.456 + if (s == t) --t;
1.457 + arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
1.458 + }
1.459 + }
1.460 +
1.461 + void firstIn(Arc& arc, const Node& node) const {
1.462 + int s = _node_num - 1, t = node._id;
1.463 + if (s > t) {
1.464 + arc._id = (_eid(t, s) << 1);
1.465 + } else {
1.466 + --s;
1.467 + arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
1.468 + }
1.469 + }
1.470 +
1.471 + void nextIn(Arc& arc) const {
1.472 + int s, t;
1.473 + _stid(arc._id, s, t);
1.474 + --s;
1.475 + if (s > t) {
1.476 + arc._id = (_eid(t, s) << 1);
1.477 + } else {
1.478 + if (s == t) --s;
1.479 + arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
1.480 + }
1.481 + }
1.482 +
1.483 + void firstInc(Edge& edge, bool& dir, const Node& node) const {
1.484 + int u = node._id, v = _node_num - 1;
1.485 + if (u < v) {
1.486 + edge._id = _eid(u, v);
1.487 + dir = true;
1.488 + } else {
1.489 + --v;
1.490 + edge._id = (v != -1 ? _eid(v, u) : -1);
1.491 + dir = false;
1.492 + }
1.493 + }
1.494 +
1.495 + void nextInc(Edge& edge, bool& dir) const {
1.496 + int u, v;
1.497 + if (dir) {
1.498 + _uvid(edge._id, u, v);
1.499 + --v;
1.500 + if (u < v) {
1.501 + edge._id = _eid(u, v);
1.502 + } else {
1.503 + --v;
1.504 + edge._id = (v != -1 ? _eid(v, u) : -1);
1.505 + dir = false;
1.506 + }
1.507 + } else {
1.508 + _uvid(edge._id, v, u);
1.509 + --v;
1.510 + edge._id = (v != -1 ? _eid(v, u) : -1);
1.511 + }
1.512 + }
1.513 +
1.514 + };
1.515 +
1.516 + typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
1.517 +
1.518 + /// \ingroup graphs
1.519 + ///
1.520 + /// \brief An undirected full graph class.
1.521 + ///
1.522 + /// This is a simple and fast undirected full graph
1.523 + /// implementation. From each node go edge to each other node,
1.524 + /// therefore the number of edges in the graph is
1.525 + /// <tt>n(n-1)/2</tt>. It is completely static, so you can neither
1.526 + /// add nor delete either edges or nodes, and it needs just constant
1.527 + /// space in memory.
1.528 + ///
1.529 + /// The \e FullDigraph and \e FullGraph classes are very similar,
1.530 + /// but there are two differences. While the \e FullDigraph class is
1.531 + /// conform just to the \ref concepts::Digraph "Digraph" concept,
1.532 + /// this class is conform to the \ref concepts::Graph "Graph"
1.533 + /// concept. In addition, the \e FullGraph class does not contain a
1.534 + /// loop arc from each node as the \e FullDigraph does.
1.535 + ///
1.536 + /// It also has an important extra feature that its maps are real
1.537 + /// \ref concepts::ReferenceMap "reference map"s.
1.538 + ///
1.539 + /// \sa FullDigraph
1.540 + class FullGraph : public ExtendedFullGraphBase {
1.541 + public:
1.542 +
1.543 + typedef ExtendedFullGraphBase Parent;
1.544 +
1.545 + /// \brief Constructor
1.546 + FullGraph() { construct(0); }
1.547 +
1.548 + /// \brief Constructor
1.549 + ///
1.550 + /// \param n The number of the nodes.
1.551 + FullGraph(int n) { construct(n); }
1.552 +
1.553 + /// \brief Resize the graph
1.554 + ///
1.555 + /// Resize the graph. The function will fully destroy and rebuild
1.556 + /// the graph. This cause that the maps of the graph will
1.557 + /// reallocated automatically and the previous values will be
1.558 + /// lost.
1.559 + void resize(int n) {
1.560 + Parent::notifier(Arc()).clear();
1.561 + Parent::notifier(Edge()).clear();
1.562 + Parent::notifier(Node()).clear();
1.563 + construct(n);
1.564 + Parent::notifier(Node()).build();
1.565 + Parent::notifier(Edge()).build();
1.566 + Parent::notifier(Arc()).build();
1.567 + }
1.568 +
1.569 + /// \brief Returns the node with the given index.
1.570 + ///
1.571 + /// Returns the node with the given index. Because it is a static
1.572 + /// size graph the node's of the graph can be indexed in the range
1.573 + /// <tt>[0..nodeNum()-1]</tt> and the index of the node can
1.574 + /// accessed by the \e index() member.
1.575 + Node operator()(int ix) const { return Parent::operator()(ix); }
1.576 +
1.577 + /// \brief Returns the index of the node.
1.578 + ///
1.579 + /// Returns the index of the node. Because it is a static size
1.580 + /// graph the node's of the graph can be indexed in the range
1.581 + /// <tt>[0..nodeNum()-1]</tt> and the index of the node can
1.582 + /// accessed by the \e index() member.
1.583 + int index(const Node& node) const { return Parent::index(node); }
1.584 +
1.585 + /// \brief Number of nodes.
1.586 + int nodeNum() const { return Parent::nodeNum(); }
1.587 + /// \brief Number of arcs.
1.588 + int arcNum() const { return Parent::arcNum(); }
1.589 + /// \brief Number of edges.
1.590 + int edgeNum() const { return Parent::edgeNum(); }
1.591 +
1.592 + /// \brief Returns the arc connects the given nodes.
1.593 + ///
1.594 + /// Returns the arc connects the given nodes.
1.595 + Arc arc(const Node& s, const Node& t) const {
1.596 + return Parent::arc(s, t);
1.597 + }
1.598 +
1.599 + /// \brief Returns the edge connects the given nodes.
1.600 + ///
1.601 + /// Returns the edge connects the given nodes.
1.602 + Edge edge(const Node& u, const Node& v) const {
1.603 + return Parent::edge(u, v);
1.604 + }
1.605 + };
1.606 +
1.607 +
1.608 +} //namespace lemon
1.609 +
1.610 +
1.611 +#endif //LEMON_FULL_GRAPH_H