1.1 --- a/lemon/Makefile.am Mon Aug 04 22:00:36 2008 +0200
1.2 +++ b/lemon/Makefile.am Thu Aug 14 21:49:39 2008 +0200
1.3 @@ -29,6 +29,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/kruskal.h \
1.10 lemon/lgf_reader.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/full_graph.h Thu Aug 14 21:49:39 2008 +0200
2.3 @@ -0,0 +1,608 @@
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/math.h>
2.26 +
2.27 +#include <lemon/core.h>
2.28 +#include <lemon/bits/graph_extender.h>
2.29 +
2.30 +///\ingroup graphs
2.31 +///\file
2.32 +///\brief FullDigraph and FullGraph classes.
2.33 +namespace lemon {
2.34 +
2.35 + class FullDigraphBase {
2.36 + public:
2.37 +
2.38 + typedef FullDigraphBase Graph;
2.39 +
2.40 + class Node;
2.41 + class Arc;
2.42 +
2.43 + protected:
2.44 +
2.45 + int _node_num;
2.46 + int _arc_num;
2.47 +
2.48 + FullDigraphBase() {}
2.49 +
2.50 + void construct(int n) { _node_num = n; _arc_num = n * n; }
2.51 +
2.52 + public:
2.53 +
2.54 + typedef True NodeNumTag;
2.55 + typedef True ArcNumTag;
2.56 +
2.57 + Node operator()(int ix) const { return Node(ix); }
2.58 + int index(const Node& node) const { return node._id; }
2.59 +
2.60 + Arc arc(const Node& s, const Node& t) const {
2.61 + return Arc(s._id * _node_num + t._id);
2.62 + }
2.63 +
2.64 + int nodeNum() const { return _node_num; }
2.65 + int arcNum() const { return _arc_num; }
2.66 +
2.67 + int maxNodeId() const { return _node_num - 1; }
2.68 + int maxArcId() const { return _arc_num - 1; }
2.69 +
2.70 + Node source(Arc arc) const { return arc._id / _node_num; }
2.71 + Node target(Arc arc) const { return arc._id % _node_num; }
2.72 +
2.73 +
2.74 + static int id(Node node) { return node._id; }
2.75 + static int id(Arc arc) { return arc._id; }
2.76 +
2.77 + static Node nodeFromId(int id) { return Node(id);}
2.78 +
2.79 + static Arc arcFromId(int id) { return Arc(id);}
2.80 +
2.81 + typedef True FindArcTag;
2.82 +
2.83 + Arc findArc(Node s, Node t, Arc prev = INVALID) const {
2.84 + return prev != INVALID ? arc(s, t) : INVALID;
2.85 + }
2.86 +
2.87 +
2.88 + class Node {
2.89 + friend class FullDigraphBase;
2.90 +
2.91 + protected:
2.92 + int _id;
2.93 + Node(int id) : _id(id) {}
2.94 + public:
2.95 + Node() {}
2.96 + Node (Invalid) : _id(-1) {}
2.97 + bool operator==(const Node node) const {return _id == node._id;}
2.98 + bool operator!=(const Node node) const {return _id != node._id;}
2.99 + bool operator<(const Node node) const {return _id < node._id;}
2.100 + };
2.101 +
2.102 + class Arc {
2.103 + friend class FullDigraphBase;
2.104 +
2.105 + protected:
2.106 + int _id; // _node_num * source + target;
2.107 +
2.108 + Arc(int id) : _id(id) {}
2.109 +
2.110 + public:
2.111 + Arc() { }
2.112 + Arc (Invalid) { _id = -1; }
2.113 + bool operator==(const Arc arc) const {return _id == arc._id;}
2.114 + bool operator!=(const Arc arc) const {return _id != arc._id;}
2.115 + bool operator<(const Arc arc) const {return _id < arc._id;}
2.116 + };
2.117 +
2.118 + void first(Node& node) const {
2.119 + node._id = _node_num - 1;
2.120 + }
2.121 +
2.122 + static void next(Node& node) {
2.123 + --node._id;
2.124 + }
2.125 +
2.126 + void first(Arc& arc) const {
2.127 + arc._id = _arc_num - 1;
2.128 + }
2.129 +
2.130 + static void next(Arc& arc) {
2.131 + --arc._id;
2.132 + }
2.133 +
2.134 + void firstOut(Arc& arc, const Node& node) const {
2.135 + arc._id = (node._id + 1) * _node_num - 1;
2.136 + }
2.137 +
2.138 + void nextOut(Arc& arc) const {
2.139 + if (arc._id % _node_num == 0) arc._id = 0;
2.140 + --arc._id;
2.141 + }
2.142 +
2.143 + void firstIn(Arc& arc, const Node& node) const {
2.144 + arc._id = _arc_num + node._id - _node_num;
2.145 + }
2.146 +
2.147 + void nextIn(Arc& arc) const {
2.148 + arc._id -= _node_num;
2.149 + if (arc._id < 0) arc._id = -1;
2.150 + }
2.151 +
2.152 + };
2.153 +
2.154 + typedef DigraphExtender<FullDigraphBase> ExtendedFullDigraphBase;
2.155 +
2.156 + /// \ingroup graphs
2.157 + ///
2.158 + /// \brief A full digraph class.
2.159 + ///
2.160 + /// This is a simple and fast directed full graph implementation.
2.161 + /// From each node go arcs to each node (including the source node),
2.162 + /// therefore the number of the arcs in the digraph is the square of
2.163 + /// the node number. The digraph is completely static, so you can
2.164 + /// neither add nor delete either arcs or nodes, and it needs just
2.165 + /// constant space in memory.
2.166 + ///
2.167 + /// Thus it conforms to the \ref concepts::Digraph "Digraph" concept
2.168 + /// and it also has an important extra feature that its maps are
2.169 + /// real \ref concepts::ReferenceMap "reference map"s.
2.170 + /// \sa concepts::Digraph.
2.171 + ///
2.172 + /// \sa FullGraph
2.173 + class FullDigraph : public ExtendedFullDigraphBase {
2.174 + public:
2.175 +
2.176 + typedef ExtendedFullDigraphBase Parent;
2.177 +
2.178 + /// \brief Constructor
2.179 + FullDigraph() { construct(0); }
2.180 +
2.181 + /// \brief Constructor
2.182 + ///
2.183 + /// \param n The number of the nodes.
2.184 + FullDigraph(int n) { construct(n); }
2.185 +
2.186 + /// \brief Resize the digraph
2.187 + ///
2.188 + /// Resize the digraph. The function will fully destroy and
2.189 + /// rebuild the digraph. This cause that the maps of the digraph
2.190 + /// will reallocated automatically and the previous values will be
2.191 + /// lost.
2.192 + void resize(int n) {
2.193 + Parent::notifier(Arc()).clear();
2.194 + Parent::notifier(Node()).clear();
2.195 + construct(n);
2.196 + Parent::notifier(Node()).build();
2.197 + Parent::notifier(Arc()).build();
2.198 + }
2.199 +
2.200 + /// \brief Returns the node with the given index.
2.201 + ///
2.202 + /// Returns the node with the given index. Because it is a
2.203 + /// static size digraph the node's of the digraph can be indexed
2.204 + /// in the range <tt>[0..nodeNum()-1]</tt> and the index of
2.205 + /// the node can accessed by the \e index() member.
2.206 + Node operator()(int ix) const { return Parent::operator()(ix); }
2.207 +
2.208 + /// \brief Returns the index of the node.
2.209 + ///
2.210 + /// Returns the index of the node. Because it is a
2.211 + /// static size digraph the node's of the digraph can be indexed
2.212 + /// in the range <tt>[0..nodeNum()-1]</tt> and the index of
2.213 + /// the node can accessed by the \e index() member.
2.214 + int index(const Node& node) const { return Parent::index(node); }
2.215 +
2.216 + /// \brief Returns the arc connects the given nodes.
2.217 + ///
2.218 + /// Returns the arc connects the given nodes.
2.219 + Arc arc(const Node& u, const Node& v) const {
2.220 + return Parent::arc(u, v);
2.221 + }
2.222 +
2.223 + /// \brief Number of nodes.
2.224 + int nodeNum() const { return Parent::nodeNum(); }
2.225 + /// \brief Number of arcs.
2.226 + int arcNum() const { return Parent::arcNum(); }
2.227 + };
2.228 +
2.229 +
2.230 + class FullGraphBase {
2.231 + int _node_num;
2.232 + int _edge_num;
2.233 + public:
2.234 +
2.235 + typedef FullGraphBase Graph;
2.236 +
2.237 + class Node;
2.238 + class Arc;
2.239 + class Edge;
2.240 +
2.241 + protected:
2.242 +
2.243 + FullGraphBase() {}
2.244 +
2.245 + void construct(int n) { _node_num = n; _edge_num = n * (n - 1) / 2; }
2.246 +
2.247 + int _uid(int e) const {
2.248 + int u = e / _node_num;
2.249 + int v = e % _node_num;
2.250 + return u < v ? u : _node_num - 2 - u;
2.251 + }
2.252 +
2.253 + int _vid(int e) const {
2.254 + int u = e / _node_num;
2.255 + int v = e % _node_num;
2.256 + return u < v ? v : _node_num - 1 - v;
2.257 + }
2.258 +
2.259 + void _uvid(int e, int& u, int& v) const {
2.260 + u = e / _node_num;
2.261 + v = e % _node_num;
2.262 + if (u >= v) {
2.263 + u = _node_num - 2 - u;
2.264 + v = _node_num - 1 - v;
2.265 + }
2.266 + }
2.267 +
2.268 + void _stid(int a, int& s, int& t) const {
2.269 + if ((a & 1) == 1) {
2.270 + _uvid(a >> 1, s, t);
2.271 + } else {
2.272 + _uvid(a >> 1, t, s);
2.273 + }
2.274 + }
2.275 +
2.276 + int _eid(int u, int v) const {
2.277 + if (u < (_node_num - 1) / 2) {
2.278 + return u * _node_num + v;
2.279 + } else {
2.280 + return (_node_num - 1 - u) * _node_num - v - 1;
2.281 + }
2.282 + }
2.283 +
2.284 + public:
2.285 +
2.286 +
2.287 + Node operator()(int ix) const { return Node(ix); }
2.288 + int index(const Node& node) const { return node._id; }
2.289 +
2.290 + Edge edge(const Node& u, const Node& v) const {
2.291 + if (u._id < v._id) {
2.292 + return Edge(_eid(u._id, v._id));
2.293 + } else if (u._id != v._id) {
2.294 + return Edge(_eid(v._id, u._id));
2.295 + } else {
2.296 + return INVALID;
2.297 + }
2.298 + }
2.299 +
2.300 + Arc arc(const Node& s, const Node& t) const {
2.301 + if (s._id < t._id) {
2.302 + return Arc((_eid(s._id, t._id) << 1) | 1);
2.303 + } else if (s._id != t._id) {
2.304 + return Arc(_eid(t._id, s._id) << 1);
2.305 + } else {
2.306 + return INVALID;
2.307 + }
2.308 + }
2.309 +
2.310 + typedef True NodeNumTag;
2.311 + typedef True EdgeNumTag;
2.312 +
2.313 + int nodeNum() const { return _node_num; }
2.314 + int arcNum() const { return 2 * _edge_num; }
2.315 + int edgeNum() const { return _edge_num; }
2.316 +
2.317 + static int id(Node node) { return node._id; }
2.318 + static int id(Arc arc) { return arc._id; }
2.319 + static int id(Edge edge) { return edge._id; }
2.320 +
2.321 + int maxNodeId() const { return _node_num-1; }
2.322 + int maxArcId() const { return 2 * _edge_num-1; }
2.323 + int maxEdgeId() const { return _edge_num-1; }
2.324 +
2.325 + static Node nodeFromId(int id) { return Node(id);}
2.326 + static Arc arcFromId(int id) { return Arc(id);}
2.327 + static Edge edgeFromId(int id) { return Edge(id);}
2.328 +
2.329 + Node u(Edge edge) const {
2.330 + return Node(_uid(edge._id));
2.331 + }
2.332 +
2.333 + Node v(Edge edge) const {
2.334 + return Node(_vid(edge._id));
2.335 + }
2.336 +
2.337 + Node source(Arc arc) const {
2.338 + return Node((arc._id & 1) == 1 ?
2.339 + _uid(arc._id >> 1) : _vid(arc._id >> 1));
2.340 + }
2.341 +
2.342 + Node target(Arc arc) const {
2.343 + return Node((arc._id & 1) == 1 ?
2.344 + _vid(arc._id >> 1) : _uid(arc._id >> 1));
2.345 + }
2.346 +
2.347 + typedef True FindEdgeTag;
2.348 +
2.349 + Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
2.350 + return prev != INVALID ? INVALID : edge(u, v);
2.351 + }
2.352 +
2.353 + Arc findArc(Node s, Node t, Arc prev = INVALID) const {
2.354 + return prev != INVALID ? INVALID : arc(s, t);
2.355 + }
2.356 +
2.357 + class Node {
2.358 + friend class FullGraphBase;
2.359 +
2.360 + protected:
2.361 + int _id;
2.362 + Node(int id) : _id(id) {}
2.363 + public:
2.364 + Node() {}
2.365 + Node (Invalid) { _id = -1; }
2.366 + bool operator==(const Node node) const {return _id == node._id;}
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 + };
2.370 +
2.371 + class Edge {
2.372 + friend class FullGraphBase;
2.373 +
2.374 + protected:
2.375 + int _id;
2.376 +
2.377 + Edge(int id) : _id(id) {}
2.378 +
2.379 + public:
2.380 + Edge() { }
2.381 + Edge (Invalid) { _id = -1; }
2.382 +
2.383 + bool operator==(const Edge edge) const {return _id == edge._id;}
2.384 + bool operator!=(const Edge edge) const {return _id != edge._id;}
2.385 + bool operator<(const Edge edge) const {return _id < edge._id;}
2.386 + };
2.387 +
2.388 + class Arc {
2.389 + friend class FullGraphBase;
2.390 +
2.391 + protected:
2.392 + int _id;
2.393 +
2.394 + Arc(int id) : _id(id) {}
2.395 +
2.396 + public:
2.397 + Arc() { }
2.398 + Arc (Invalid) { _id = -1; }
2.399 +
2.400 + operator Edge() const { return Edge(_id != -1 ? (_id >> 1) : -1); }
2.401 +
2.402 + bool operator==(const Arc arc) const {return _id == arc._id;}
2.403 + bool operator!=(const Arc arc) const {return _id != arc._id;}
2.404 + bool operator<(const Arc arc) const {return _id < arc._id;}
2.405 + };
2.406 +
2.407 + static bool direction(Arc arc) {
2.408 + return (arc._id & 1) == 1;
2.409 + }
2.410 +
2.411 + static Arc direct(Edge edge, bool dir) {
2.412 + return Arc((edge._id << 1) | (dir ? 1 : 0));
2.413 + }
2.414 +
2.415 + void first(Node& node) const {
2.416 + node._id = _node_num - 1;
2.417 + }
2.418 +
2.419 + static void next(Node& node) {
2.420 + --node._id;
2.421 + }
2.422 +
2.423 + void first(Arc& arc) const {
2.424 + arc._id = (_edge_num << 1) - 1;
2.425 + }
2.426 +
2.427 + static void next(Arc& arc) {
2.428 + --arc._id;
2.429 + }
2.430 +
2.431 + void first(Edge& edge) const {
2.432 + edge._id = _edge_num - 1;
2.433 + }
2.434 +
2.435 + static void next(Edge& edge) {
2.436 + --edge._id;
2.437 + }
2.438 +
2.439 + void firstOut(Arc& arc, const Node& node) const {
2.440 + int s = node._id, t = _node_num - 1;
2.441 + if (s < t) {
2.442 + arc._id = (_eid(s, t) << 1) | 1;
2.443 + } else {
2.444 + --t;
2.445 + arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
2.446 + }
2.447 + }
2.448 +
2.449 + void nextOut(Arc& arc) const {
2.450 + int s, t;
2.451 + _stid(arc._id, s, t);
2.452 + --t;
2.453 + if (s < t) {
2.454 + arc._id = (_eid(s, t) << 1) | 1;
2.455 + } else {
2.456 + if (s == t) --t;
2.457 + arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
2.458 + }
2.459 + }
2.460 +
2.461 + void firstIn(Arc& arc, const Node& node) const {
2.462 + int s = _node_num - 1, t = node._id;
2.463 + if (s > t) {
2.464 + arc._id = (_eid(t, s) << 1);
2.465 + } else {
2.466 + --s;
2.467 + arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
2.468 + }
2.469 + }
2.470 +
2.471 + void nextIn(Arc& arc) const {
2.472 + int s, t;
2.473 + _stid(arc._id, s, t);
2.474 + --s;
2.475 + if (s > t) {
2.476 + arc._id = (_eid(t, s) << 1);
2.477 + } else {
2.478 + if (s == t) --s;
2.479 + arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
2.480 + }
2.481 + }
2.482 +
2.483 + void firstInc(Edge& edge, bool& dir, const Node& node) const {
2.484 + int u = node._id, v = _node_num - 1;
2.485 + if (u < v) {
2.486 + edge._id = _eid(u, v);
2.487 + dir = true;
2.488 + } else {
2.489 + --v;
2.490 + edge._id = (v != -1 ? _eid(v, u) : -1);
2.491 + dir = false;
2.492 + }
2.493 + }
2.494 +
2.495 + void nextInc(Edge& edge, bool& dir) const {
2.496 + int u, v;
2.497 + if (dir) {
2.498 + _uvid(edge._id, u, v);
2.499 + --v;
2.500 + if (u < v) {
2.501 + edge._id = _eid(u, v);
2.502 + } else {
2.503 + --v;
2.504 + edge._id = (v != -1 ? _eid(v, u) : -1);
2.505 + dir = false;
2.506 + }
2.507 + } else {
2.508 + _uvid(edge._id, v, u);
2.509 + --v;
2.510 + edge._id = (v != -1 ? _eid(v, u) : -1);
2.511 + }
2.512 + }
2.513 +
2.514 + };
2.515 +
2.516 + typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
2.517 +
2.518 + /// \ingroup graphs
2.519 + ///
2.520 + /// \brief An undirected full graph class.
2.521 + ///
2.522 + /// This is a simple and fast undirected full graph
2.523 + /// implementation. From each node go edge to each other node,
2.524 + /// therefore the number of edges in the graph is
2.525 + /// <tt>n(n-1)/2</tt>. It is completely static, so you can neither
2.526 + /// add nor delete either edges or nodes, and it needs just constant
2.527 + /// space in memory.
2.528 + ///
2.529 + /// The \e FullDigraph and \e FullGraph classes are very similar,
2.530 + /// but there are two differences. While the \e FullDigraph class is
2.531 + /// conform just to the \ref concepts::Digraph "Digraph" concept,
2.532 + /// this class is conform to the \ref concepts::Graph "Graph"
2.533 + /// concept. In addition, the \e FullGraph class does not contain a
2.534 + /// loop arc from each node as the \e FullDigraph does.
2.535 + ///
2.536 + /// It also has an important extra feature that its maps are real
2.537 + /// \ref concepts::ReferenceMap "reference map"s.
2.538 + ///
2.539 + /// \sa FullDigraph
2.540 + class FullGraph : public ExtendedFullGraphBase {
2.541 + public:
2.542 +
2.543 + typedef ExtendedFullGraphBase Parent;
2.544 +
2.545 + /// \brief Constructor
2.546 + FullGraph() { construct(0); }
2.547 +
2.548 + /// \brief Constructor
2.549 + ///
2.550 + /// \param n The number of the nodes.
2.551 + FullGraph(int n) { construct(n); }
2.552 +
2.553 + /// \brief Resize the graph
2.554 + ///
2.555 + /// Resize the graph. The function will fully destroy and rebuild
2.556 + /// the graph. This cause that the maps of the graph will
2.557 + /// reallocated automatically and the previous values will be
2.558 + /// lost.
2.559 + void resize(int n) {
2.560 + Parent::notifier(Arc()).clear();
2.561 + Parent::notifier(Edge()).clear();
2.562 + Parent::notifier(Node()).clear();
2.563 + construct(n);
2.564 + Parent::notifier(Node()).build();
2.565 + Parent::notifier(Edge()).build();
2.566 + Parent::notifier(Arc()).build();
2.567 + }
2.568 +
2.569 + /// \brief Returns the node with the given index.
2.570 + ///
2.571 + /// Returns the node with the given index. Because it is a static
2.572 + /// size graph the node's of the graph can be indexed in the range
2.573 + /// <tt>[0..nodeNum()-1]</tt> and the index of the node can
2.574 + /// accessed by the \e index() member.
2.575 + Node operator()(int ix) const { return Parent::operator()(ix); }
2.576 +
2.577 + /// \brief Returns the index of the node.
2.578 + ///
2.579 + /// Returns the index of the node. Because it is a static size
2.580 + /// graph the node's of the graph can be indexed in the range
2.581 + /// <tt>[0..nodeNum()-1]</tt> and the index of the node can
2.582 + /// accessed by the \e index() member.
2.583 + int index(const Node& node) const { return Parent::index(node); }
2.584 +
2.585 + /// \brief Number of nodes.
2.586 + int nodeNum() const { return Parent::nodeNum(); }
2.587 + /// \brief Number of arcs.
2.588 + int arcNum() const { return Parent::arcNum(); }
2.589 + /// \brief Number of edges.
2.590 + int edgeNum() const { return Parent::edgeNum(); }
2.591 +
2.592 + /// \brief Returns the arc connects the given nodes.
2.593 + ///
2.594 + /// Returns the arc connects the given nodes.
2.595 + Arc arc(const Node& s, const Node& t) const {
2.596 + return Parent::arc(s, t);
2.597 + }
2.598 +
2.599 + /// \brief Returns the edge connects the given nodes.
2.600 + ///
2.601 + /// Returns the edge connects the given nodes.
2.602 + Edge edge(const Node& u, const Node& v) const {
2.603 + return Parent::edge(u, v);
2.604 + }
2.605 + };
2.606 +
2.607 +
2.608 +} //namespace lemon
2.609 +
2.610 +
2.611 +#endif //LEMON_FULL_GRAPH_H
3.1 --- a/test/digraph_test.cc Mon Aug 04 22:00:36 2008 +0200
3.2 +++ b/test/digraph_test.cc Thu Aug 14 21:49:39 2008 +0200
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 @@ -176,6 +209,9 @@
3.53 checkDigraph<SmartDigraph>();
3.54 checkDigraphValidity<SmartDigraph>();
3.55 }
3.56 + { // Checking FullDigraph
3.57 + checkFullDigraph(8);
3.58 + }
3.59 }
3.60
3.61 int main() {
4.1 --- a/test/graph_test.cc Mon Aug 04 22:00:36 2008 +0200
4.2 +++ b/test/graph_test.cc Thu Aug 14 21:49:39 2008 +0200
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,14 +171,12 @@
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 GridGraph
4.75 -// checkConcept<Graph, GridGraph>();
4.76 -// checkGraphIterators<GridGraph>();
4.77 -// }
4.78 + { // Checking FullGraph
4.79 + checkConcept<Graph, FullGraph>();
4.80 + }
4.81 +// { // Checking GridGraph
4.82 +// checkConcept<Graph, GridGraph>();
4.83 +// }
4.84 }
4.85
4.86 template <typename Graph>
4.87 @@ -241,11 +286,10 @@
4.88 checkGraph<SmartGraph>();
4.89 checkGraphValidity<SmartGraph>();
4.90 }
4.91 -// { // Checking FullGraph
4.92 -// FullGraph g(5);
4.93 -// checkGraphNodeList(g, 5);
4.94 -// checkGraphEdgeList(g, 10);
4.95 -// }
4.96 + { // Checking FullGraph
4.97 + checkFullGraph(7);
4.98 + checkFullGraph(8);
4.99 + }
4.100 // { // Checking GridGraph
4.101 // GridGraph g(5, 6);
4.102 // checkGraphNodeList(g, 30);