1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/full_graph.h Thu Dec 10 17:05:35 2009 +0100
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-2009
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 Digraph;
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 fully conforms to the \ref concepts::Digraph
1.164 + /// "Digraph concept".
1.165 + ///
1.166 + /// The \c FullDigraph and \c FullGraph classes are very similar,
1.167 + /// but there are two differences. While this class conforms only
1.168 + /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph
1.169 + /// class conforms to the \ref concepts::Graph "Graph" concept,
1.170 + /// moreover \c FullGraph does not contain a loop arc for each
1.171 + /// node as \c FullDigraph does.
1.172 + ///
1.173 + /// \sa FullGraph
1.174 + class FullDigraph : public ExtendedFullDigraphBase {
1.175 + typedef ExtendedFullDigraphBase Parent;
1.176 +
1.177 + public:
1.178 +
1.179 + /// \brief Constructor
1.180 + FullDigraph() { construct(0); }
1.181 +
1.182 + /// \brief Constructor
1.183 + ///
1.184 + /// Constructor.
1.185 + /// \param n The number of the nodes.
1.186 + FullDigraph(int n) { construct(n); }
1.187 +
1.188 + /// \brief Resizes the digraph
1.189 + ///
1.190 + /// Resizes the digraph. The function will fully destroy and
1.191 + /// rebuild the digraph. This cause that the maps of the digraph will
1.192 + /// reallocated automatically and the previous values will be lost.
1.193 + void resize(int n) {
1.194 + Parent::notifier(Arc()).clear();
1.195 + Parent::notifier(Node()).clear();
1.196 + construct(n);
1.197 + Parent::notifier(Node()).build();
1.198 + Parent::notifier(Arc()).build();
1.199 + }
1.200 +
1.201 + /// \brief Returns the node with the given index.
1.202 + ///
1.203 + /// Returns the node with the given index. Since it is a static
1.204 + /// digraph its nodes can be indexed with integers from the range
1.205 + /// <tt>[0..nodeNum()-1]</tt>.
1.206 + /// \sa index()
1.207 + Node operator()(int ix) const { return Parent::operator()(ix); }
1.208 +
1.209 + /// \brief Returns the index of the given node.
1.210 + ///
1.211 + /// Returns the index of the given node. Since it is a static
1.212 + /// digraph its nodes can be indexed with integers from the range
1.213 + /// <tt>[0..nodeNum()-1]</tt>.
1.214 + /// \sa operator()
1.215 + int index(const Node& node) const { return Parent::index(node); }
1.216 +
1.217 + /// \brief Returns the arc connecting the given nodes.
1.218 + ///
1.219 + /// Returns the arc connecting the given nodes.
1.220 + Arc arc(const Node& u, const Node& v) const {
1.221 + return Parent::arc(u, v);
1.222 + }
1.223 +
1.224 + /// \brief Number of nodes.
1.225 + int nodeNum() const { return Parent::nodeNum(); }
1.226 + /// \brief Number of arcs.
1.227 + int arcNum() const { return Parent::arcNum(); }
1.228 + };
1.229 +
1.230 +
1.231 + class FullGraphBase {
1.232 + public:
1.233 +
1.234 + typedef FullGraphBase Graph;
1.235 +
1.236 + class Node;
1.237 + class Arc;
1.238 + class Edge;
1.239 +
1.240 + protected:
1.241 +
1.242 + int _node_num;
1.243 + int _edge_num;
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 ArcNumTag;
1.313 + typedef True EdgeNumTag;
1.314 +
1.315 + int nodeNum() const { return _node_num; }
1.316 + int arcNum() const { return 2 * _edge_num; }
1.317 + int edgeNum() const { return _edge_num; }
1.318 +
1.319 + static int id(Node node) { return node._id; }
1.320 + static int id(Arc arc) { return arc._id; }
1.321 + static int id(Edge edge) { return edge._id; }
1.322 +
1.323 + int maxNodeId() const { return _node_num-1; }
1.324 + int maxArcId() const { return 2 * _edge_num-1; }
1.325 + int maxEdgeId() const { return _edge_num-1; }
1.326 +
1.327 + static Node nodeFromId(int id) { return Node(id);}
1.328 + static Arc arcFromId(int id) { return Arc(id);}
1.329 + static Edge edgeFromId(int id) { return Edge(id);}
1.330 +
1.331 + Node u(Edge edge) const {
1.332 + return Node(_uid(edge._id));
1.333 + }
1.334 +
1.335 + Node v(Edge edge) const {
1.336 + return Node(_vid(edge._id));
1.337 + }
1.338 +
1.339 + Node source(Arc arc) const {
1.340 + return Node((arc._id & 1) == 1 ?
1.341 + _uid(arc._id >> 1) : _vid(arc._id >> 1));
1.342 + }
1.343 +
1.344 + Node target(Arc arc) const {
1.345 + return Node((arc._id & 1) == 1 ?
1.346 + _vid(arc._id >> 1) : _uid(arc._id >> 1));
1.347 + }
1.348 +
1.349 + typedef True FindEdgeTag;
1.350 + typedef True FindArcTag;
1.351 +
1.352 + Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
1.353 + return prev != INVALID ? INVALID : edge(u, v);
1.354 + }
1.355 +
1.356 + Arc findArc(Node s, Node t, Arc prev = INVALID) const {
1.357 + return prev != INVALID ? INVALID : arc(s, t);
1.358 + }
1.359 +
1.360 + class Node {
1.361 + friend class FullGraphBase;
1.362 +
1.363 + protected:
1.364 + int _id;
1.365 + Node(int id) : _id(id) {}
1.366 + public:
1.367 + Node() {}
1.368 + Node (Invalid) { _id = -1; }
1.369 + bool operator==(const Node node) const {return _id == node._id;}
1.370 + bool operator!=(const Node node) const {return _id != node._id;}
1.371 + bool operator<(const Node node) const {return _id < node._id;}
1.372 + };
1.373 +
1.374 + class Edge {
1.375 + friend class FullGraphBase;
1.376 + friend class Arc;
1.377 +
1.378 + protected:
1.379 + int _id;
1.380 +
1.381 + Edge(int id) : _id(id) {}
1.382 +
1.383 + public:
1.384 + Edge() { }
1.385 + Edge (Invalid) { _id = -1; }
1.386 +
1.387 + bool operator==(const Edge edge) const {return _id == edge._id;}
1.388 + bool operator!=(const Edge edge) const {return _id != edge._id;}
1.389 + bool operator<(const Edge edge) const {return _id < edge._id;}
1.390 + };
1.391 +
1.392 + class Arc {
1.393 + friend class FullGraphBase;
1.394 +
1.395 + protected:
1.396 + int _id;
1.397 +
1.398 + Arc(int id) : _id(id) {}
1.399 +
1.400 + public:
1.401 + Arc() { }
1.402 + Arc (Invalid) { _id = -1; }
1.403 +
1.404 + operator Edge() const { return Edge(_id != -1 ? (_id >> 1) : -1); }
1.405 +
1.406 + bool operator==(const Arc arc) const {return _id == arc._id;}
1.407 + bool operator!=(const Arc arc) const {return _id != arc._id;}
1.408 + bool operator<(const Arc arc) const {return _id < arc._id;}
1.409 + };
1.410 +
1.411 + static bool direction(Arc arc) {
1.412 + return (arc._id & 1) == 1;
1.413 + }
1.414 +
1.415 + static Arc direct(Edge edge, bool dir) {
1.416 + return Arc((edge._id << 1) | (dir ? 1 : 0));
1.417 + }
1.418 +
1.419 + void first(Node& node) const {
1.420 + node._id = _node_num - 1;
1.421 + }
1.422 +
1.423 + static void next(Node& node) {
1.424 + --node._id;
1.425 + }
1.426 +
1.427 + void first(Arc& arc) const {
1.428 + arc._id = (_edge_num << 1) - 1;
1.429 + }
1.430 +
1.431 + static void next(Arc& arc) {
1.432 + --arc._id;
1.433 + }
1.434 +
1.435 + void first(Edge& edge) const {
1.436 + edge._id = _edge_num - 1;
1.437 + }
1.438 +
1.439 + static void next(Edge& edge) {
1.440 + --edge._id;
1.441 + }
1.442 +
1.443 + void firstOut(Arc& arc, const Node& node) const {
1.444 + int s = node._id, t = _node_num - 1;
1.445 + if (s < t) {
1.446 + arc._id = (_eid(s, t) << 1) | 1;
1.447 + } else {
1.448 + --t;
1.449 + arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
1.450 + }
1.451 + }
1.452 +
1.453 + void nextOut(Arc& arc) const {
1.454 + int s, t;
1.455 + _stid(arc._id, s, t);
1.456 + --t;
1.457 + if (s < t) {
1.458 + arc._id = (_eid(s, t) << 1) | 1;
1.459 + } else {
1.460 + if (s == t) --t;
1.461 + arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
1.462 + }
1.463 + }
1.464 +
1.465 + void firstIn(Arc& arc, const Node& node) const {
1.466 + int s = _node_num - 1, t = node._id;
1.467 + if (s > t) {
1.468 + arc._id = (_eid(t, s) << 1);
1.469 + } else {
1.470 + --s;
1.471 + arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
1.472 + }
1.473 + }
1.474 +
1.475 + void nextIn(Arc& arc) const {
1.476 + int s, t;
1.477 + _stid(arc._id, s, t);
1.478 + --s;
1.479 + if (s > t) {
1.480 + arc._id = (_eid(t, s) << 1);
1.481 + } else {
1.482 + if (s == t) --s;
1.483 + arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
1.484 + }
1.485 + }
1.486 +
1.487 + void firstInc(Edge& edge, bool& dir, const Node& node) const {
1.488 + int u = node._id, v = _node_num - 1;
1.489 + if (u < v) {
1.490 + edge._id = _eid(u, v);
1.491 + dir = true;
1.492 + } else {
1.493 + --v;
1.494 + edge._id = (v != -1 ? _eid(v, u) : -1);
1.495 + dir = false;
1.496 + }
1.497 + }
1.498 +
1.499 + void nextInc(Edge& edge, bool& dir) const {
1.500 + int u, v;
1.501 + if (dir) {
1.502 + _uvid(edge._id, u, v);
1.503 + --v;
1.504 + if (u < v) {
1.505 + edge._id = _eid(u, v);
1.506 + } else {
1.507 + --v;
1.508 + edge._id = (v != -1 ? _eid(v, u) : -1);
1.509 + dir = false;
1.510 + }
1.511 + } else {
1.512 + _uvid(edge._id, v, u);
1.513 + --v;
1.514 + edge._id = (v != -1 ? _eid(v, u) : -1);
1.515 + }
1.516 + }
1.517 +
1.518 + };
1.519 +
1.520 + typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
1.521 +
1.522 + /// \ingroup graphs
1.523 + ///
1.524 + /// \brief An undirected full graph class.
1.525 + ///
1.526 + /// This is a simple and fast undirected full graph
1.527 + /// implementation. From each node go edge to each other node,
1.528 + /// therefore the number of edges in the graph is \f$n(n-1)/2\f$.
1.529 + /// This graph type is completely static, so you can neither
1.530 + /// add nor delete either edges or nodes, and it needs constant
1.531 + /// space in memory.
1.532 + ///
1.533 + /// This class fully conforms to the \ref concepts::Graph "Graph concept".
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 + typedef ExtendedFullGraphBase Parent;
1.545 +
1.546 + public:
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