1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/full_graph.h Thu Nov 05 15:50:01 2009 +0100
1.3 @@ -0,0 +1,620 @@
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 FullDigraph and FullGraph 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 + static int index(const Node& node) { 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 directed full graph class.
1.155 + ///
1.156 + /// FullDigraph is a simple and fast implmenetation of directed full
1.157 + /// (complete) graphs. It contains an arc from each node to each node
1.158 + /// (including a loop for each node), therefore the number of arcs
1.159 + /// is the square of the number of nodes.
1.160 + /// This class is completely static and it needs constant memory space.
1.161 + /// Thus you can neither add nor delete nodes or arcs, however
1.162 + /// the structure can be resized using resize().
1.163 + ///
1.164 + /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".
1.165 + /// Most of its member functions and nested classes are documented
1.166 + /// only in the concept class.
1.167 + ///
1.168 + /// \note FullDigraph and FullGraph classes are very similar,
1.169 + /// but there are two differences. While this class conforms only
1.170 + /// to the \ref concepts::Digraph "Digraph" concept, FullGraph
1.171 + /// conforms to the \ref concepts::Graph "Graph" concept,
1.172 + /// moreover FullGraph does not contain a loop for each
1.173 + /// node as this class does.
1.174 + ///
1.175 + /// \sa FullGraph
1.176 + class FullDigraph : public ExtendedFullDigraphBase {
1.177 + typedef ExtendedFullDigraphBase Parent;
1.178 +
1.179 + public:
1.180 +
1.181 + /// \brief Default constructor.
1.182 + ///
1.183 + /// Default constructor. The number of nodes and arcs will be zero.
1.184 + FullDigraph() { construct(0); }
1.185 +
1.186 + /// \brief Constructor
1.187 + ///
1.188 + /// Constructor.
1.189 + /// \param n The number of the nodes.
1.190 + FullDigraph(int n) { construct(n); }
1.191 +
1.192 + /// \brief Resizes the digraph
1.193 + ///
1.194 + /// This function resizes the digraph. It fully destroys and
1.195 + /// rebuilds the structure, therefore the maps of the digraph will be
1.196 + /// reallocated automatically and the previous values will be lost.
1.197 + void resize(int n) {
1.198 + Parent::notifier(Arc()).clear();
1.199 + Parent::notifier(Node()).clear();
1.200 + construct(n);
1.201 + Parent::notifier(Node()).build();
1.202 + Parent::notifier(Arc()).build();
1.203 + }
1.204 +
1.205 + /// \brief Returns the node with the given index.
1.206 + ///
1.207 + /// Returns the node with the given index. Since this structure is
1.208 + /// completely static, the nodes can be indexed with integers from
1.209 + /// the range <tt>[0..nodeNum()-1]</tt>.
1.210 + /// \sa index()
1.211 + Node operator()(int ix) const { return Parent::operator()(ix); }
1.212 +
1.213 + /// \brief Returns the index of the given node.
1.214 + ///
1.215 + /// Returns the index of the given node. Since this structure is
1.216 + /// completely static, the nodes can be indexed with integers from
1.217 + /// the range <tt>[0..nodeNum()-1]</tt>.
1.218 + /// \sa operator()()
1.219 + static int index(const Node& node) { return Parent::index(node); }
1.220 +
1.221 + /// \brief Returns the arc connecting the given nodes.
1.222 + ///
1.223 + /// Returns the arc connecting the given nodes.
1.224 + Arc arc(Node u, Node v) const {
1.225 + return Parent::arc(u, v);
1.226 + }
1.227 +
1.228 + /// \brief Number of nodes.
1.229 + int nodeNum() const { return Parent::nodeNum(); }
1.230 + /// \brief Number of arcs.
1.231 + int arcNum() const { return Parent::arcNum(); }
1.232 + };
1.233 +
1.234 +
1.235 + class FullGraphBase {
1.236 + public:
1.237 +
1.238 + typedef FullGraphBase Graph;
1.239 +
1.240 + class Node;
1.241 + class Arc;
1.242 + class Edge;
1.243 +
1.244 + protected:
1.245 +
1.246 + int _node_num;
1.247 + int _edge_num;
1.248 +
1.249 + FullGraphBase() {}
1.250 +
1.251 + void construct(int n) { _node_num = n; _edge_num = n * (n - 1) / 2; }
1.252 +
1.253 + int _uid(int e) const {
1.254 + int u = e / _node_num;
1.255 + int v = e % _node_num;
1.256 + return u < v ? u : _node_num - 2 - u;
1.257 + }
1.258 +
1.259 + int _vid(int e) const {
1.260 + int u = e / _node_num;
1.261 + int v = e % _node_num;
1.262 + return u < v ? v : _node_num - 1 - v;
1.263 + }
1.264 +
1.265 + void _uvid(int e, int& u, int& v) const {
1.266 + u = e / _node_num;
1.267 + v = e % _node_num;
1.268 + if (u >= v) {
1.269 + u = _node_num - 2 - u;
1.270 + v = _node_num - 1 - v;
1.271 + }
1.272 + }
1.273 +
1.274 + void _stid(int a, int& s, int& t) const {
1.275 + if ((a & 1) == 1) {
1.276 + _uvid(a >> 1, s, t);
1.277 + } else {
1.278 + _uvid(a >> 1, t, s);
1.279 + }
1.280 + }
1.281 +
1.282 + int _eid(int u, int v) const {
1.283 + if (u < (_node_num - 1) / 2) {
1.284 + return u * _node_num + v;
1.285 + } else {
1.286 + return (_node_num - 1 - u) * _node_num - v - 1;
1.287 + }
1.288 + }
1.289 +
1.290 + public:
1.291 +
1.292 + Node operator()(int ix) const { return Node(ix); }
1.293 + static int index(const Node& node) { return node._id; }
1.294 +
1.295 + Edge edge(const Node& u, const Node& v) const {
1.296 + if (u._id < v._id) {
1.297 + return Edge(_eid(u._id, v._id));
1.298 + } else if (u._id != v._id) {
1.299 + return Edge(_eid(v._id, u._id));
1.300 + } else {
1.301 + return INVALID;
1.302 + }
1.303 + }
1.304 +
1.305 + Arc arc(const Node& s, const Node& t) const {
1.306 + if (s._id < t._id) {
1.307 + return Arc((_eid(s._id, t._id) << 1) | 1);
1.308 + } else if (s._id != t._id) {
1.309 + return Arc(_eid(t._id, s._id) << 1);
1.310 + } else {
1.311 + return INVALID;
1.312 + }
1.313 + }
1.314 +
1.315 + typedef True NodeNumTag;
1.316 + typedef True ArcNumTag;
1.317 + typedef True EdgeNumTag;
1.318 +
1.319 + int nodeNum() const { return _node_num; }
1.320 + int arcNum() const { return 2 * _edge_num; }
1.321 + int edgeNum() const { return _edge_num; }
1.322 +
1.323 + static int id(Node node) { return node._id; }
1.324 + static int id(Arc arc) { return arc._id; }
1.325 + static int id(Edge edge) { return edge._id; }
1.326 +
1.327 + int maxNodeId() const { return _node_num-1; }
1.328 + int maxArcId() const { return 2 * _edge_num-1; }
1.329 + int maxEdgeId() const { return _edge_num-1; }
1.330 +
1.331 + static Node nodeFromId(int id) { return Node(id);}
1.332 + static Arc arcFromId(int id) { return Arc(id);}
1.333 + static Edge edgeFromId(int id) { return Edge(id);}
1.334 +
1.335 + Node u(Edge edge) const {
1.336 + return Node(_uid(edge._id));
1.337 + }
1.338 +
1.339 + Node v(Edge edge) const {
1.340 + return Node(_vid(edge._id));
1.341 + }
1.342 +
1.343 + Node source(Arc arc) const {
1.344 + return Node((arc._id & 1) == 1 ?
1.345 + _uid(arc._id >> 1) : _vid(arc._id >> 1));
1.346 + }
1.347 +
1.348 + Node target(Arc arc) const {
1.349 + return Node((arc._id & 1) == 1 ?
1.350 + _vid(arc._id >> 1) : _uid(arc._id >> 1));
1.351 + }
1.352 +
1.353 + typedef True FindEdgeTag;
1.354 + typedef True FindArcTag;
1.355 +
1.356 + Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
1.357 + return prev != INVALID ? INVALID : edge(u, v);
1.358 + }
1.359 +
1.360 + Arc findArc(Node s, Node t, Arc prev = INVALID) const {
1.361 + return prev != INVALID ? INVALID : arc(s, t);
1.362 + }
1.363 +
1.364 + class Node {
1.365 + friend class FullGraphBase;
1.366 +
1.367 + protected:
1.368 + int _id;
1.369 + Node(int id) : _id(id) {}
1.370 + public:
1.371 + Node() {}
1.372 + Node (Invalid) { _id = -1; }
1.373 + bool operator==(const Node node) const {return _id == node._id;}
1.374 + bool operator!=(const Node node) const {return _id != node._id;}
1.375 + bool operator<(const Node node) const {return _id < node._id;}
1.376 + };
1.377 +
1.378 + class Edge {
1.379 + friend class FullGraphBase;
1.380 + friend class Arc;
1.381 +
1.382 + protected:
1.383 + int _id;
1.384 +
1.385 + Edge(int id) : _id(id) {}
1.386 +
1.387 + public:
1.388 + Edge() { }
1.389 + Edge (Invalid) { _id = -1; }
1.390 +
1.391 + bool operator==(const Edge edge) const {return _id == edge._id;}
1.392 + bool operator!=(const Edge edge) const {return _id != edge._id;}
1.393 + bool operator<(const Edge edge) const {return _id < edge._id;}
1.394 + };
1.395 +
1.396 + class Arc {
1.397 + friend class FullGraphBase;
1.398 +
1.399 + protected:
1.400 + int _id;
1.401 +
1.402 + Arc(int id) : _id(id) {}
1.403 +
1.404 + public:
1.405 + Arc() { }
1.406 + Arc (Invalid) { _id = -1; }
1.407 +
1.408 + operator Edge() const { return Edge(_id != -1 ? (_id >> 1) : -1); }
1.409 +
1.410 + bool operator==(const Arc arc) const {return _id == arc._id;}
1.411 + bool operator!=(const Arc arc) const {return _id != arc._id;}
1.412 + bool operator<(const Arc arc) const {return _id < arc._id;}
1.413 + };
1.414 +
1.415 + static bool direction(Arc arc) {
1.416 + return (arc._id & 1) == 1;
1.417 + }
1.418 +
1.419 + static Arc direct(Edge edge, bool dir) {
1.420 + return Arc((edge._id << 1) | (dir ? 1 : 0));
1.421 + }
1.422 +
1.423 + void first(Node& node) const {
1.424 + node._id = _node_num - 1;
1.425 + }
1.426 +
1.427 + static void next(Node& node) {
1.428 + --node._id;
1.429 + }
1.430 +
1.431 + void first(Arc& arc) const {
1.432 + arc._id = (_edge_num << 1) - 1;
1.433 + }
1.434 +
1.435 + static void next(Arc& arc) {
1.436 + --arc._id;
1.437 + }
1.438 +
1.439 + void first(Edge& edge) const {
1.440 + edge._id = _edge_num - 1;
1.441 + }
1.442 +
1.443 + static void next(Edge& edge) {
1.444 + --edge._id;
1.445 + }
1.446 +
1.447 + void firstOut(Arc& arc, const Node& node) const {
1.448 + int s = node._id, t = _node_num - 1;
1.449 + if (s < t) {
1.450 + arc._id = (_eid(s, t) << 1) | 1;
1.451 + } else {
1.452 + --t;
1.453 + arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
1.454 + }
1.455 + }
1.456 +
1.457 + void nextOut(Arc& arc) const {
1.458 + int s, t;
1.459 + _stid(arc._id, s, t);
1.460 + --t;
1.461 + if (s < t) {
1.462 + arc._id = (_eid(s, t) << 1) | 1;
1.463 + } else {
1.464 + if (s == t) --t;
1.465 + arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
1.466 + }
1.467 + }
1.468 +
1.469 + void firstIn(Arc& arc, const Node& node) const {
1.470 + int s = _node_num - 1, t = node._id;
1.471 + if (s > t) {
1.472 + arc._id = (_eid(t, s) << 1);
1.473 + } else {
1.474 + --s;
1.475 + arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
1.476 + }
1.477 + }
1.478 +
1.479 + void nextIn(Arc& arc) const {
1.480 + int s, t;
1.481 + _stid(arc._id, s, t);
1.482 + --s;
1.483 + if (s > t) {
1.484 + arc._id = (_eid(t, s) << 1);
1.485 + } else {
1.486 + if (s == t) --s;
1.487 + arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
1.488 + }
1.489 + }
1.490 +
1.491 + void firstInc(Edge& edge, bool& dir, const Node& node) const {
1.492 + int u = node._id, v = _node_num - 1;
1.493 + if (u < v) {
1.494 + edge._id = _eid(u, v);
1.495 + dir = true;
1.496 + } else {
1.497 + --v;
1.498 + edge._id = (v != -1 ? _eid(v, u) : -1);
1.499 + dir = false;
1.500 + }
1.501 + }
1.502 +
1.503 + void nextInc(Edge& edge, bool& dir) const {
1.504 + int u, v;
1.505 + if (dir) {
1.506 + _uvid(edge._id, u, v);
1.507 + --v;
1.508 + if (u < v) {
1.509 + edge._id = _eid(u, v);
1.510 + } else {
1.511 + --v;
1.512 + edge._id = (v != -1 ? _eid(v, u) : -1);
1.513 + dir = false;
1.514 + }
1.515 + } else {
1.516 + _uvid(edge._id, v, u);
1.517 + --v;
1.518 + edge._id = (v != -1 ? _eid(v, u) : -1);
1.519 + }
1.520 + }
1.521 +
1.522 + };
1.523 +
1.524 + typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
1.525 +
1.526 + /// \ingroup graphs
1.527 + ///
1.528 + /// \brief An undirected full graph class.
1.529 + ///
1.530 + /// FullGraph is a simple and fast implmenetation of undirected full
1.531 + /// (complete) graphs. It contains an edge between every distinct pair
1.532 + /// of nodes, therefore the number of edges is <tt>n(n-1)/2</tt>.
1.533 + /// This class is completely static and it needs constant memory space.
1.534 + /// Thus you can neither add nor delete nodes or edges, however
1.535 + /// the structure can be resized using resize().
1.536 + ///
1.537 + /// This type fully conforms to the \ref concepts::Graph "Graph concept".
1.538 + /// Most of its member functions and nested classes are documented
1.539 + /// only in the concept class.
1.540 + ///
1.541 + /// \note FullDigraph and FullGraph classes are very similar,
1.542 + /// but there are two differences. While FullDigraph
1.543 + /// conforms only to the \ref concepts::Digraph "Digraph" concept,
1.544 + /// this class conforms to the \ref concepts::Graph "Graph" concept,
1.545 + /// moreover this class does not contain a loop for each
1.546 + /// node as FullDigraph does.
1.547 + ///
1.548 + /// \sa FullDigraph
1.549 + class FullGraph : public ExtendedFullGraphBase {
1.550 + typedef ExtendedFullGraphBase Parent;
1.551 +
1.552 + public:
1.553 +
1.554 + /// \brief Default constructor.
1.555 + ///
1.556 + /// Default constructor. The number of nodes and edges will be zero.
1.557 + FullGraph() { construct(0); }
1.558 +
1.559 + /// \brief Constructor
1.560 + ///
1.561 + /// Constructor.
1.562 + /// \param n The number of the nodes.
1.563 + FullGraph(int n) { construct(n); }
1.564 +
1.565 + /// \brief Resizes the graph
1.566 + ///
1.567 + /// This function resizes the graph. It fully destroys and
1.568 + /// rebuilds the structure, therefore the maps of the graph will be
1.569 + /// reallocated automatically and the previous values will be lost.
1.570 + void resize(int n) {
1.571 + Parent::notifier(Arc()).clear();
1.572 + Parent::notifier(Edge()).clear();
1.573 + Parent::notifier(Node()).clear();
1.574 + construct(n);
1.575 + Parent::notifier(Node()).build();
1.576 + Parent::notifier(Edge()).build();
1.577 + Parent::notifier(Arc()).build();
1.578 + }
1.579 +
1.580 + /// \brief Returns the node with the given index.
1.581 + ///
1.582 + /// Returns the node with the given index. Since this structure is
1.583 + /// completely static, the nodes can be indexed with integers from
1.584 + /// the range <tt>[0..nodeNum()-1]</tt>.
1.585 + /// \sa index()
1.586 + Node operator()(int ix) const { return Parent::operator()(ix); }
1.587 +
1.588 + /// \brief Returns the index of the given node.
1.589 + ///
1.590 + /// Returns the index of the given node. Since this structure is
1.591 + /// completely static, the nodes can be indexed with integers from
1.592 + /// the range <tt>[0..nodeNum()-1]</tt>.
1.593 + /// \sa operator()()
1.594 + static int index(const Node& node) { return Parent::index(node); }
1.595 +
1.596 + /// \brief Returns the arc connecting the given nodes.
1.597 + ///
1.598 + /// Returns the arc connecting the given nodes.
1.599 + Arc arc(Node s, Node t) const {
1.600 + return Parent::arc(s, t);
1.601 + }
1.602 +
1.603 + /// \brief Returns the edge connecting the given nodes.
1.604 + ///
1.605 + /// Returns the edge connecting the given nodes.
1.606 + Edge edge(Node u, Node v) const {
1.607 + return Parent::edge(u, v);
1.608 + }
1.609 +
1.610 + /// \brief Number of nodes.
1.611 + int nodeNum() const { return Parent::nodeNum(); }
1.612 + /// \brief Number of arcs.
1.613 + int arcNum() const { return Parent::arcNum(); }
1.614 + /// \brief Number of edges.
1.615 + int edgeNum() const { return Parent::edgeNum(); }
1.616 +
1.617 + };
1.618 +
1.619 +
1.620 +} //namespace lemon
1.621 +
1.622 +
1.623 +#endif //LEMON_FULL_GRAPH_H