1.1 --- a/lemon/Makefile.am Wed Oct 29 15:29:34 2008 +0100
1.2 +++ b/lemon/Makefile.am Tue Nov 04 10:21:22 2008 +0000
1.3 @@ -28,6 +28,7 @@
1.4 lemon/dijkstra.h \
1.5 lemon/dim2.h \
1.6 lemon/error.h \
1.7 + lemon/full_graph.h \
1.8 lemon/graph_to_eps.h \
1.9 lemon/grid_graph.h \
1.10 lemon/kruskal.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/full_graph.h Tue Nov 04 10:21:22 2008 +0000
2.3 @@ -0,0 +1,612 @@
2.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library.
2.7 + *
2.8 + * Copyright (C) 2003-2008
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +#ifndef LEMON_FULL_GRAPH_H
2.23 +#define LEMON_FULL_GRAPH_H
2.24 +
2.25 +#include <lemon/core.h>
2.26 +#include <lemon/bits/graph_extender.h>
2.27 +
2.28 +///\ingroup graphs
2.29 +///\file
2.30 +///\brief FullGraph and FullDigraph classes.
2.31 +
2.32 +namespace lemon {
2.33 +
2.34 + class FullDigraphBase {
2.35 + public:
2.36 +
2.37 + typedef FullDigraphBase Graph;
2.38 +
2.39 + class Node;
2.40 + class Arc;
2.41 +
2.42 + protected:
2.43 +
2.44 + int _node_num;
2.45 + int _arc_num;
2.46 +
2.47 + FullDigraphBase() {}
2.48 +
2.49 + void construct(int n) { _node_num = n; _arc_num = n * n; }
2.50 +
2.51 + public:
2.52 +
2.53 + typedef True NodeNumTag;
2.54 + typedef True ArcNumTag;
2.55 +
2.56 + Node operator()(int ix) const { return Node(ix); }
2.57 + int index(const Node& node) const { return node._id; }
2.58 +
2.59 + Arc arc(const Node& s, const Node& t) const {
2.60 + return Arc(s._id * _node_num + t._id);
2.61 + }
2.62 +
2.63 + int nodeNum() const { return _node_num; }
2.64 + int arcNum() const { return _arc_num; }
2.65 +
2.66 + int maxNodeId() const { return _node_num - 1; }
2.67 + int maxArcId() const { return _arc_num - 1; }
2.68 +
2.69 + Node source(Arc arc) const { return arc._id / _node_num; }
2.70 + Node target(Arc arc) const { return arc._id % _node_num; }
2.71 +
2.72 + static int id(Node node) { return node._id; }
2.73 + static int id(Arc arc) { return arc._id; }
2.74 +
2.75 + static Node nodeFromId(int id) { return Node(id);}
2.76 + static Arc arcFromId(int id) { return Arc(id);}
2.77 +
2.78 + typedef True FindArcTag;
2.79 +
2.80 + Arc findArc(Node s, Node t, Arc prev = INVALID) const {
2.81 + return prev == INVALID ? arc(s, t) : INVALID;
2.82 + }
2.83 +
2.84 + class Node {
2.85 + friend class FullDigraphBase;
2.86 +
2.87 + protected:
2.88 + int _id;
2.89 + Node(int id) : _id(id) {}
2.90 + public:
2.91 + Node() {}
2.92 + Node (Invalid) : _id(-1) {}
2.93 + bool operator==(const Node node) const {return _id == node._id;}
2.94 + bool operator!=(const Node node) const {return _id != node._id;}
2.95 + bool operator<(const Node node) const {return _id < node._id;}
2.96 + };
2.97 +
2.98 + class Arc {
2.99 + friend class FullDigraphBase;
2.100 +
2.101 + protected:
2.102 + int _id; // _node_num * source + target;
2.103 +
2.104 + Arc(int id) : _id(id) {}
2.105 +
2.106 + public:
2.107 + Arc() { }
2.108 + Arc (Invalid) { _id = -1; }
2.109 + bool operator==(const Arc arc) const {return _id == arc._id;}
2.110 + bool operator!=(const Arc arc) const {return _id != arc._id;}
2.111 + bool operator<(const Arc arc) const {return _id < arc._id;}
2.112 + };
2.113 +
2.114 + void first(Node& node) const {
2.115 + node._id = _node_num - 1;
2.116 + }
2.117 +
2.118 + static void next(Node& node) {
2.119 + --node._id;
2.120 + }
2.121 +
2.122 + void first(Arc& arc) const {
2.123 + arc._id = _arc_num - 1;
2.124 + }
2.125 +
2.126 + static void next(Arc& arc) {
2.127 + --arc._id;
2.128 + }
2.129 +
2.130 + void firstOut(Arc& arc, const Node& node) const {
2.131 + arc._id = (node._id + 1) * _node_num - 1;
2.132 + }
2.133 +
2.134 + void nextOut(Arc& arc) const {
2.135 + if (arc._id % _node_num == 0) arc._id = 0;
2.136 + --arc._id;
2.137 + }
2.138 +
2.139 + void firstIn(Arc& arc, const Node& node) const {
2.140 + arc._id = _arc_num + node._id - _node_num;
2.141 + }
2.142 +
2.143 + void nextIn(Arc& arc) const {
2.144 + arc._id -= _node_num;
2.145 + if (arc._id < 0) arc._id = -1;
2.146 + }
2.147 +
2.148 + };
2.149 +
2.150 + typedef DigraphExtender<FullDigraphBase> ExtendedFullDigraphBase;
2.151 +
2.152 + /// \ingroup graphs
2.153 + ///
2.154 + /// \brief A full digraph class.
2.155 + ///
2.156 + /// This is a simple and fast directed full graph implementation.
2.157 + /// From each node go arcs to each node (including the source node),
2.158 + /// therefore the number of the arcs in the digraph is the square of
2.159 + /// the node number. This digraph type is completely static, so you
2.160 + /// can neither add nor delete either arcs or nodes, and it needs
2.161 + /// constant space in memory.
2.162 + ///
2.163 + /// This class conforms to the \ref concepts::Digraph "Digraph" concept
2.164 + /// and it also has an important extra feature that its maps are
2.165 + /// real \ref concepts::ReferenceMap "reference map"s.
2.166 + ///
2.167 + /// The \c FullDigraph and \c FullGraph classes are very similar,
2.168 + /// but there are two differences. While this class conforms only
2.169 + /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph
2.170 + /// class conforms to the \ref concepts::Graph "Graph" concept,
2.171 + /// moreover \c FullGraph does not contain a loop arc for each
2.172 + /// node as \c FullDigraph does.
2.173 + ///
2.174 + /// \sa FullGraph
2.175 + class FullDigraph : public ExtendedFullDigraphBase {
2.176 + public:
2.177 +
2.178 + typedef ExtendedFullDigraphBase Parent;
2.179 +
2.180 + /// \brief Constructor
2.181 + FullDigraph() { construct(0); }
2.182 +
2.183 + /// \brief Constructor
2.184 + ///
2.185 + /// Constructor.
2.186 + /// \param n The number of the nodes.
2.187 + FullDigraph(int n) { construct(n); }
2.188 +
2.189 + /// \brief Resizes the digraph
2.190 + ///
2.191 + /// Resizes the digraph. The function will fully destroy and
2.192 + /// rebuild the digraph. This cause that the maps of the digraph will
2.193 + /// reallocated automatically and the previous values will be lost.
2.194 + void resize(int n) {
2.195 + Parent::notifier(Arc()).clear();
2.196 + Parent::notifier(Node()).clear();
2.197 + construct(n);
2.198 + Parent::notifier(Node()).build();
2.199 + Parent::notifier(Arc()).build();
2.200 + }
2.201 +
2.202 + /// \brief Returns the node with the given index.
2.203 + ///
2.204 + /// Returns the node with the given index. Since it is a static
2.205 + /// digraph its nodes can be indexed with integers from the range
2.206 + /// <tt>[0..nodeNum()-1]</tt>.
2.207 + /// \sa index()
2.208 + Node operator()(int ix) const { return Parent::operator()(ix); }
2.209 +
2.210 + /// \brief Returns the index of the given node.
2.211 + ///
2.212 + /// Returns the index of the given node. Since it is a static
2.213 + /// digraph its nodes can be indexed with integers from the range
2.214 + /// <tt>[0..nodeNum()-1]</tt>.
2.215 + /// \sa operator()
2.216 + int index(const Node& node) const { return Parent::index(node); }
2.217 +
2.218 + /// \brief Returns the arc connecting the given nodes.
2.219 + ///
2.220 + /// Returns the arc connecting the given nodes.
2.221 + Arc arc(const Node& u, const Node& v) const {
2.222 + return Parent::arc(u, v);
2.223 + }
2.224 +
2.225 + /// \brief Number of nodes.
2.226 + int nodeNum() const { return Parent::nodeNum(); }
2.227 + /// \brief Number of arcs.
2.228 + int arcNum() const { return Parent::arcNum(); }
2.229 + };
2.230 +
2.231 +
2.232 + class FullGraphBase {
2.233 + int _node_num;
2.234 + int _edge_num;
2.235 + public:
2.236 +
2.237 + typedef FullGraphBase Graph;
2.238 +
2.239 + class Node;
2.240 + class Arc;
2.241 + class Edge;
2.242 +
2.243 + protected:
2.244 +
2.245 + FullGraphBase() {}
2.246 +
2.247 + void construct(int n) { _node_num = n; _edge_num = n * (n - 1) / 2; }
2.248 +
2.249 + int _uid(int e) const {
2.250 + int u = e / _node_num;
2.251 + int v = e % _node_num;
2.252 + return u < v ? u : _node_num - 2 - u;
2.253 + }
2.254 +
2.255 + int _vid(int e) const {
2.256 + int u = e / _node_num;
2.257 + int v = e % _node_num;
2.258 + return u < v ? v : _node_num - 1 - v;
2.259 + }
2.260 +
2.261 + void _uvid(int e, int& u, int& v) const {
2.262 + u = e / _node_num;
2.263 + v = e % _node_num;
2.264 + if (u >= v) {
2.265 + u = _node_num - 2 - u;
2.266 + v = _node_num - 1 - v;
2.267 + }
2.268 + }
2.269 +
2.270 + void _stid(int a, int& s, int& t) const {
2.271 + if ((a & 1) == 1) {
2.272 + _uvid(a >> 1, s, t);
2.273 + } else {
2.274 + _uvid(a >> 1, t, s);
2.275 + }
2.276 + }
2.277 +
2.278 + int _eid(int u, int v) const {
2.279 + if (u < (_node_num - 1) / 2) {
2.280 + return u * _node_num + v;
2.281 + } else {
2.282 + return (_node_num - 1 - u) * _node_num - v - 1;
2.283 + }
2.284 + }
2.285 +
2.286 + public:
2.287 +
2.288 + Node operator()(int ix) const { return Node(ix); }
2.289 + int index(const Node& node) const { return node._id; }
2.290 +
2.291 + Edge edge(const Node& u, const Node& v) const {
2.292 + if (u._id < v._id) {
2.293 + return Edge(_eid(u._id, v._id));
2.294 + } else if (u._id != v._id) {
2.295 + return Edge(_eid(v._id, u._id));
2.296 + } else {
2.297 + return INVALID;
2.298 + }
2.299 + }
2.300 +
2.301 + Arc arc(const Node& s, const Node& t) const {
2.302 + if (s._id < t._id) {
2.303 + return Arc((_eid(s._id, t._id) << 1) | 1);
2.304 + } else if (s._id != t._id) {
2.305 + return Arc(_eid(t._id, s._id) << 1);
2.306 + } else {
2.307 + return INVALID;
2.308 + }
2.309 + }
2.310 +
2.311 + typedef True NodeNumTag;
2.312 + typedef True EdgeNumTag;
2.313 +
2.314 + int nodeNum() const { return _node_num; }
2.315 + int arcNum() const { return 2 * _edge_num; }
2.316 + int edgeNum() const { return _edge_num; }
2.317 +
2.318 + static int id(Node node) { return node._id; }
2.319 + static int id(Arc arc) { return arc._id; }
2.320 + static int id(Edge edge) { return edge._id; }
2.321 +
2.322 + int maxNodeId() const { return _node_num-1; }
2.323 + int maxArcId() const { return 2 * _edge_num-1; }
2.324 + int maxEdgeId() const { return _edge_num-1; }
2.325 +
2.326 + static Node nodeFromId(int id) { return Node(id);}
2.327 + static Arc arcFromId(int id) { return Arc(id);}
2.328 + static Edge edgeFromId(int id) { return Edge(id);}
2.329 +
2.330 + Node u(Edge edge) const {
2.331 + return Node(_uid(edge._id));
2.332 + }
2.333 +
2.334 + Node v(Edge edge) const {
2.335 + return Node(_vid(edge._id));
2.336 + }
2.337 +
2.338 + Node source(Arc arc) const {
2.339 + return Node((arc._id & 1) == 1 ?
2.340 + _uid(arc._id >> 1) : _vid(arc._id >> 1));
2.341 + }
2.342 +
2.343 + Node target(Arc arc) const {
2.344 + return Node((arc._id & 1) == 1 ?
2.345 + _vid(arc._id >> 1) : _uid(arc._id >> 1));
2.346 + }
2.347 +
2.348 + typedef True FindEdgeTag;
2.349 +
2.350 + Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
2.351 + return prev != INVALID ? INVALID : edge(u, v);
2.352 + }
2.353 +
2.354 + Arc findArc(Node s, Node t, Arc prev = INVALID) const {
2.355 + return prev != INVALID ? INVALID : arc(s, t);
2.356 + }
2.357 +
2.358 + class Node {
2.359 + friend class FullGraphBase;
2.360 +
2.361 + protected:
2.362 + int _id;
2.363 + Node(int id) : _id(id) {}
2.364 + public:
2.365 + Node() {}
2.366 + Node (Invalid) { _id = -1; }
2.367 + bool operator==(const Node node) const {return _id == node._id;}
2.368 + bool operator!=(const Node node) const {return _id != node._id;}
2.369 + bool operator<(const Node node) const {return _id < node._id;}
2.370 + };
2.371 +
2.372 + class Edge {
2.373 + friend class FullGraphBase;
2.374 + friend class Arc;
2.375 +
2.376 + protected:
2.377 + int _id;
2.378 +
2.379 + Edge(int id) : _id(id) {}
2.380 +
2.381 + public:
2.382 + Edge() { }
2.383 + Edge (Invalid) { _id = -1; }
2.384 +
2.385 + bool operator==(const Edge edge) const {return _id == edge._id;}
2.386 + bool operator!=(const Edge edge) const {return _id != edge._id;}
2.387 + bool operator<(const Edge edge) const {return _id < edge._id;}
2.388 + };
2.389 +
2.390 + class Arc {
2.391 + friend class FullGraphBase;
2.392 +
2.393 + protected:
2.394 + int _id;
2.395 +
2.396 + Arc(int id) : _id(id) {}
2.397 +
2.398 + public:
2.399 + Arc() { }
2.400 + Arc (Invalid) { _id = -1; }
2.401 +
2.402 + operator Edge() const { return Edge(_id != -1 ? (_id >> 1) : -1); }
2.403 +
2.404 + bool operator==(const Arc arc) const {return _id == arc._id;}
2.405 + bool operator!=(const Arc arc) const {return _id != arc._id;}
2.406 + bool operator<(const Arc arc) const {return _id < arc._id;}
2.407 + };
2.408 +
2.409 + static bool direction(Arc arc) {
2.410 + return (arc._id & 1) == 1;
2.411 + }
2.412 +
2.413 + static Arc direct(Edge edge, bool dir) {
2.414 + return Arc((edge._id << 1) | (dir ? 1 : 0));
2.415 + }
2.416 +
2.417 + void first(Node& node) const {
2.418 + node._id = _node_num - 1;
2.419 + }
2.420 +
2.421 + static void next(Node& node) {
2.422 + --node._id;
2.423 + }
2.424 +
2.425 + void first(Arc& arc) const {
2.426 + arc._id = (_edge_num << 1) - 1;
2.427 + }
2.428 +
2.429 + static void next(Arc& arc) {
2.430 + --arc._id;
2.431 + }
2.432 +
2.433 + void first(Edge& edge) const {
2.434 + edge._id = _edge_num - 1;
2.435 + }
2.436 +
2.437 + static void next(Edge& edge) {
2.438 + --edge._id;
2.439 + }
2.440 +
2.441 + void firstOut(Arc& arc, const Node& node) const {
2.442 + int s = node._id, t = _node_num - 1;
2.443 + if (s < t) {
2.444 + arc._id = (_eid(s, t) << 1) | 1;
2.445 + } else {
2.446 + --t;
2.447 + arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
2.448 + }
2.449 + }
2.450 +
2.451 + void nextOut(Arc& arc) const {
2.452 + int s, t;
2.453 + _stid(arc._id, s, t);
2.454 + --t;
2.455 + if (s < t) {
2.456 + arc._id = (_eid(s, t) << 1) | 1;
2.457 + } else {
2.458 + if (s == t) --t;
2.459 + arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
2.460 + }
2.461 + }
2.462 +
2.463 + void firstIn(Arc& arc, const Node& node) const {
2.464 + int s = _node_num - 1, t = node._id;
2.465 + if (s > t) {
2.466 + arc._id = (_eid(t, s) << 1);
2.467 + } else {
2.468 + --s;
2.469 + arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
2.470 + }
2.471 + }
2.472 +
2.473 + void nextIn(Arc& arc) const {
2.474 + int s, t;
2.475 + _stid(arc._id, s, t);
2.476 + --s;
2.477 + if (s > t) {
2.478 + arc._id = (_eid(t, s) << 1);
2.479 + } else {
2.480 + if (s == t) --s;
2.481 + arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
2.482 + }
2.483 + }
2.484 +
2.485 + void firstInc(Edge& edge, bool& dir, const Node& node) const {
2.486 + int u = node._id, v = _node_num - 1;
2.487 + if (u < v) {
2.488 + edge._id = _eid(u, v);
2.489 + dir = true;
2.490 + } else {
2.491 + --v;
2.492 + edge._id = (v != -1 ? _eid(v, u) : -1);
2.493 + dir = false;
2.494 + }
2.495 + }
2.496 +
2.497 + void nextInc(Edge& edge, bool& dir) const {
2.498 + int u, v;
2.499 + if (dir) {
2.500 + _uvid(edge._id, u, v);
2.501 + --v;
2.502 + if (u < v) {
2.503 + edge._id = _eid(u, v);
2.504 + } else {
2.505 + --v;
2.506 + edge._id = (v != -1 ? _eid(v, u) : -1);
2.507 + dir = false;
2.508 + }
2.509 + } else {
2.510 + _uvid(edge._id, v, u);
2.511 + --v;
2.512 + edge._id = (v != -1 ? _eid(v, u) : -1);
2.513 + }
2.514 + }
2.515 +
2.516 + };
2.517 +
2.518 + typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
2.519 +
2.520 + /// \ingroup graphs
2.521 + ///
2.522 + /// \brief An undirected full graph class.
2.523 + ///
2.524 + /// This is a simple and fast undirected full graph
2.525 + /// implementation. From each node go edge to each other node,
2.526 + /// therefore the number of edges in the graph is \f$n(n-1)/2\f$.
2.527 + /// This graph type is completely static, so you can neither
2.528 + /// add nor delete either edges or nodes, and it needs constant
2.529 + /// space in memory.
2.530 + ///
2.531 + /// This class conforms to the \ref concepts::Graph "Graph" concept
2.532 + /// and it also has an important extra feature that its maps are
2.533 + /// real \ref concepts::ReferenceMap "reference map"s.
2.534 + ///
2.535 + /// The \c FullGraph and \c FullDigraph classes are very similar,
2.536 + /// but there are two differences. While the \c FullDigraph class
2.537 + /// conforms only to the \ref concepts::Digraph "Digraph" concept,
2.538 + /// this class conforms to the \ref concepts::Graph "Graph" concept,
2.539 + /// moreover \c FullGraph does not contain a loop arc for each
2.540 + /// node as \c FullDigraph does.
2.541 + ///
2.542 + /// \sa FullDigraph
2.543 + class FullGraph : public ExtendedFullGraphBase {
2.544 + public:
2.545 +
2.546 + typedef ExtendedFullGraphBase Parent;
2.547 +
2.548 + /// \brief Constructor
2.549 + FullGraph() { construct(0); }
2.550 +
2.551 + /// \brief Constructor
2.552 + ///
2.553 + /// Constructor.
2.554 + /// \param n The number of the nodes.
2.555 + FullGraph(int n) { construct(n); }
2.556 +
2.557 + /// \brief Resizes the graph
2.558 + ///
2.559 + /// Resizes the graph. The function will fully destroy and
2.560 + /// rebuild the graph. This cause that the maps of the graph will
2.561 + /// reallocated automatically and the previous values will be lost.
2.562 + void resize(int n) {
2.563 + Parent::notifier(Arc()).clear();
2.564 + Parent::notifier(Edge()).clear();
2.565 + Parent::notifier(Node()).clear();
2.566 + construct(n);
2.567 + Parent::notifier(Node()).build();
2.568 + Parent::notifier(Edge()).build();
2.569 + Parent::notifier(Arc()).build();
2.570 + }
2.571 +
2.572 + /// \brief Returns the node with the given index.
2.573 + ///
2.574 + /// Returns the node with the given index. Since it is a static
2.575 + /// graph its nodes can be indexed with integers from the range
2.576 + /// <tt>[0..nodeNum()-1]</tt>.
2.577 + /// \sa index()
2.578 + Node operator()(int ix) const { return Parent::operator()(ix); }
2.579 +
2.580 + /// \brief Returns the index of the given node.
2.581 + ///
2.582 + /// Returns the index of the given node. Since it is a static
2.583 + /// graph its nodes can be indexed with integers from the range
2.584 + /// <tt>[0..nodeNum()-1]</tt>.
2.585 + /// \sa operator()
2.586 + int index(const Node& node) const { return Parent::index(node); }
2.587 +
2.588 + /// \brief Returns the arc connecting the given nodes.
2.589 + ///
2.590 + /// Returns the arc connecting the given nodes.
2.591 + Arc arc(const Node& s, const Node& t) const {
2.592 + return Parent::arc(s, t);
2.593 + }
2.594 +
2.595 + /// \brief Returns the edge connects the given nodes.
2.596 + ///
2.597 + /// Returns the edge connects the given nodes.
2.598 + Edge edge(const Node& u, const Node& v) const {
2.599 + return Parent::edge(u, v);
2.600 + }
2.601 +
2.602 + /// \brief Number of nodes.
2.603 + int nodeNum() const { return Parent::nodeNum(); }
2.604 + /// \brief Number of arcs.
2.605 + int arcNum() const { return Parent::arcNum(); }
2.606 + /// \brief Number of edges.
2.607 + int edgeNum() const { return Parent::edgeNum(); }
2.608 +
2.609 + };
2.610 +
2.611 +
2.612 +} //namespace lemon
2.613 +
2.614 +
2.615 +#endif //LEMON_FULL_GRAPH_H
3.1 --- a/test/digraph_test.cc Wed Oct 29 15:29:34 2008 +0100
3.2 +++ b/test/digraph_test.cc Tue Nov 04 10:21:22 2008 +0000
3.3 @@ -19,7 +19,7 @@
3.4 #include <lemon/concepts/digraph.h>
3.5 #include <lemon/list_graph.h>
3.6 #include <lemon/smart_graph.h>
3.7 -//#include <lemon/full_graph.h>
3.8 +#include <lemon/full_graph.h>
3.9 //#include <lemon/hypercube_graph.h>
3.10
3.11 #include "test_tools.h"
3.12 @@ -79,6 +79,39 @@
3.13
3.14 }
3.15
3.16 +void checkFullDigraph(int num) {
3.17 + typedef FullDigraph Digraph;
3.18 + DIGRAPH_TYPEDEFS(Digraph);
3.19 + Digraph G(num);
3.20 +
3.21 + checkGraphNodeList(G, num);
3.22 + checkGraphArcList(G, num * num);
3.23 +
3.24 + for (NodeIt n(G); n != INVALID; ++n) {
3.25 + checkGraphOutArcList(G, n, num);
3.26 + checkGraphInArcList(G, n, num);
3.27 + }
3.28 +
3.29 + checkGraphConArcList(G, num * num);
3.30 +
3.31 + checkNodeIds(G);
3.32 + checkArcIds(G);
3.33 + checkGraphNodeMap(G);
3.34 + checkGraphArcMap(G);
3.35 +
3.36 + for (int i = 0; i < G.nodeNum(); ++i) {
3.37 + check(G.index(G(i)) == i, "Wrong index");
3.38 + }
3.39 +
3.40 + for (NodeIt s(G); s != INVALID; ++s) {
3.41 + for (NodeIt t(G); t != INVALID; ++t) {
3.42 + Arc a = G.arc(s, t);
3.43 + check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
3.44 + }
3.45 + }
3.46 +
3.47 +}
3.48 +
3.49
3.50 void checkConcepts() {
3.51 { // Checking digraph components
3.52 @@ -109,9 +142,9 @@
3.53 checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
3.54 checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
3.55 }
3.56 -// { // Checking FullDigraph
3.57 -// checkConcept<Digraph, FullDigraph>();
3.58 -// }
3.59 + { // Checking FullDigraph
3.60 + checkConcept<Digraph, FullDigraph>();
3.61 + }
3.62 // { // Checking HyperCubeDigraph
3.63 // checkConcept<Digraph, HyperCubeDigraph>();
3.64 // }
3.65 @@ -176,6 +209,9 @@
3.66 checkDigraph<SmartDigraph>();
3.67 checkDigraphValidity<SmartDigraph>();
3.68 }
3.69 + { // Checking FullDigraph
3.70 + checkFullDigraph(8);
3.71 + }
3.72 }
3.73
3.74 int main() {
4.1 --- a/test/graph_test.cc Wed Oct 29 15:29:34 2008 +0100
4.2 +++ b/test/graph_test.cc Tue Nov 04 10:21:22 2008 +0000
4.3 @@ -19,7 +19,7 @@
4.4 #include <lemon/concepts/graph.h>
4.5 #include <lemon/list_graph.h>
4.6 #include <lemon/smart_graph.h>
4.7 -// #include <lemon/full_graph.h>
4.8 +#include <lemon/full_graph.h>
4.9 #include <lemon/grid_graph.h>
4.10
4.11 #include "test_tools.h"
4.12 @@ -95,6 +95,53 @@
4.13 checkGraphEdgeMap(G);
4.14 }
4.15
4.16 +void checkFullGraph(int num) {
4.17 + typedef FullGraph Graph;
4.18 + GRAPH_TYPEDEFS(Graph);
4.19 +
4.20 + Graph G(num);
4.21 + checkGraphNodeList(G, num);
4.22 + checkGraphEdgeList(G, num * (num - 1) / 2);
4.23 +
4.24 + for (NodeIt n(G); n != INVALID; ++n) {
4.25 + checkGraphOutArcList(G, n, num - 1);
4.26 + checkGraphInArcList(G, n, num - 1);
4.27 + checkGraphIncEdgeList(G, n, num - 1);
4.28 + }
4.29 +
4.30 + checkGraphConArcList(G, num * (num - 1));
4.31 + checkGraphConEdgeList(G, num * (num - 1) / 2);
4.32 +
4.33 + checkArcDirections(G);
4.34 +
4.35 + checkNodeIds(G);
4.36 + checkArcIds(G);
4.37 + checkEdgeIds(G);
4.38 + checkGraphNodeMap(G);
4.39 + checkGraphArcMap(G);
4.40 + checkGraphEdgeMap(G);
4.41 +
4.42 +
4.43 + for (int i = 0; i < G.nodeNum(); ++i) {
4.44 + check(G.index(G(i)) == i, "Wrong index");
4.45 + }
4.46 +
4.47 + for (NodeIt u(G); u != INVALID; ++u) {
4.48 + for (NodeIt v(G); v != INVALID; ++v) {
4.49 + Edge e = G.edge(u, v);
4.50 + Arc a = G.arc(u, v);
4.51 + if (u == v) {
4.52 + check(e == INVALID, "Wrong edge lookup");
4.53 + check(a == INVALID, "Wrong arc lookup");
4.54 + } else {
4.55 + check((G.u(e) == u && G.v(e) == v) ||
4.56 + (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");
4.57 + check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");
4.58 + }
4.59 + }
4.60 + }
4.61 +}
4.62 +
4.63 void checkConcepts() {
4.64 { // Checking graph components
4.65 checkConcept<BaseGraphComponent, BaseGraphComponent >();
4.66 @@ -124,10 +171,9 @@
4.67 checkConcept<ExtendableGraphComponent<>, SmartGraph>();
4.68 checkConcept<ClearableGraphComponent<>, SmartGraph>();
4.69 }
4.70 -// { // Checking FullGraph
4.71 -// checkConcept<Graph, FullGraph>();
4.72 -// checkGraphIterators<FullGraph>();
4.73 -// }
4.74 + { // Checking FullGraph
4.75 + checkConcept<Graph, FullGraph>();
4.76 + }
4.77 { // Checking GridGraph
4.78 checkConcept<Graph, GridGraph>();
4.79 }
4.80 @@ -275,11 +321,10 @@
4.81 checkGraph<SmartGraph>();
4.82 checkGraphValidity<SmartGraph>();
4.83 }
4.84 -// { // Checking FullGraph
4.85 -// FullGraph g(5);
4.86 -// checkGraphNodeList(g, 5);
4.87 -// checkGraphEdgeList(g, 10);
4.88 -// }
4.89 + { // Checking FullGraph
4.90 + checkFullGraph(7);
4.91 + checkFullGraph(8);
4.92 + }
4.93 { // Checking GridGraph
4.94 checkGridGraph(5, 8);
4.95 checkGridGraph(8, 5);