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