1.1 --- a/lemon/full_graph.h Wed Jun 28 16:27:44 2006 +0000
1.2 +++ b/lemon/full_graph.h Fri Jun 30 12:14:36 2006 +0000
1.3 @@ -21,7 +21,6 @@
1.4
1.5 #include <cmath>
1.6
1.7 -#include <lemon/bits/base_extender.h>
1.8 #include <lemon/bits/graph_extender.h>
1.9
1.10 #include <lemon/bits/invalid.h>
1.11 @@ -30,7 +29,7 @@
1.12
1.13 ///\ingroup graphs
1.14 ///\file
1.15 -///\brief FullGraph and FullUGraph classes.
1.16 +///\brief FullGraph class.
1.17
1.18
1.19 namespace lemon {
1.20 @@ -247,473 +246,6 @@
1.21 }
1.22 };
1.23
1.24 -
1.25 - /// \brief Base of the FullUGrpah.
1.26 - ///
1.27 - /// Base of the FullUGrpah.
1.28 - class FullUGraphBase {
1.29 - int _nodeNum;
1.30 - int _edgeNum;
1.31 - public:
1.32 -
1.33 - typedef FullUGraphBase Graph;
1.34 -
1.35 - class Node;
1.36 - class Edge;
1.37 -
1.38 - public:
1.39 -
1.40 - FullUGraphBase() {}
1.41 -
1.42 -
1.43 - ///Creates a full graph with \c n nodes.
1.44 - void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
1.45 -
1.46 - /// \brief Returns the node with the given index.
1.47 - ///
1.48 - /// Returns the node with the given index. Because it is a
1.49 - /// static size graph the node's of the graph can be indiced
1.50 - /// by the range from 0 to \e nodeNum()-1 and the index of
1.51 - /// the node can accessed by the \e index() member.
1.52 - Node operator()(int index) const { return Node(index); }
1.53 -
1.54 - /// \brief Returns the index of the node.
1.55 - ///
1.56 - /// Returns the index of the node. Because it is a
1.57 - /// static size graph the node's of the graph can be indiced
1.58 - /// by the range from 0 to \e nodeNum()-1 and the index of
1.59 - /// the node can accessed by the \e index() member.
1.60 - int index(const Node& node) const { return node.id; }
1.61 -
1.62 - typedef True NodeNumTag;
1.63 - typedef True EdgeNumTag;
1.64 -
1.65 - ///Number of nodes.
1.66 - int nodeNum() const { return _nodeNum; }
1.67 - ///Number of edges.
1.68 - int edgeNum() const { return _edgeNum; }
1.69 -
1.70 - /// Maximum node ID.
1.71 -
1.72 - /// Maximum node ID.
1.73 - ///\sa id(Node)
1.74 - int maxNodeId() const { return _nodeNum-1; }
1.75 - /// Maximum edge ID.
1.76 -
1.77 - /// Maximum edge ID.
1.78 - ///\sa id(Edge)
1.79 - int maxEdgeId() const { return _edgeNum-1; }
1.80 -
1.81 - /// \brief Returns the node from its \c id.
1.82 - ///
1.83 - /// Returns the node from its \c id. If there is not node
1.84 - /// with the given id the effect of the function is undefinied.
1.85 - static Node nodeFromId(int id) { return Node(id);}
1.86 -
1.87 - /// \brief Returns the edge from its \c id.
1.88 - ///
1.89 - /// Returns the edge from its \c id. If there is not edge
1.90 - /// with the given id the effect of the function is undefinied.
1.91 - static Edge edgeFromId(int id) { return Edge(id);}
1.92 -
1.93 - Node source(Edge e) const {
1.94 - /// \todo we may do it faster
1.95 - return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
1.96 - }
1.97 -
1.98 - Node target(Edge e) const {
1.99 - int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
1.100 - return Node(e.id - (source) * (source - 1) / 2);
1.101 - }
1.102 -
1.103 -
1.104 - /// \brief Node ID.
1.105 - ///
1.106 - /// The ID of a valid Node is a nonnegative integer not greater than
1.107 - /// \ref maxNodeId(). The range of the ID's is not surely continuous
1.108 - /// and the greatest node ID can be actually less then \ref maxNodeId().
1.109 - ///
1.110 - /// The ID of the \ref INVALID node is -1.
1.111 - /// \return The ID of the node \c v.
1.112 -
1.113 - static int id(Node v) { return v.id; }
1.114 -
1.115 - /// \brief Edge ID.
1.116 - ///
1.117 - /// The ID of a valid Edge is a nonnegative integer not greater than
1.118 - /// \ref maxEdgeId(). The range of the ID's is not surely continuous
1.119 - /// and the greatest edge ID can be actually less then \ref maxEdgeId().
1.120 - ///
1.121 - /// The ID of the \ref INVALID edge is -1.
1.122 - ///\return The ID of the edge \c e.
1.123 - static int id(Edge e) { return e.id; }
1.124 -
1.125 - /// \brief Finds an edge between two nodes.
1.126 - ///
1.127 - /// Finds an edge from node \c u to node \c v.
1.128 - ///
1.129 - /// If \c prev is \ref INVALID (this is the default value), then
1.130 - /// It finds the first edge from \c u to \c v. Otherwise it looks for
1.131 - /// the next edge from \c u to \c v after \c prev.
1.132 - /// \return The found edge or INVALID if there is no such an edge.
1.133 - Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
1.134 - if (prev.id != -1 || u.id <= v.id) return Edge(-1);
1.135 - return Edge(u.id * (u.id - 1) / 2 + v.id);
1.136 - }
1.137 -
1.138 - typedef True FindEdgeTag;
1.139 -
1.140 -
1.141 - class Node {
1.142 - friend class FullUGraphBase;
1.143 -
1.144 - protected:
1.145 - int id;
1.146 - Node(int _id) { id = _id;}
1.147 - public:
1.148 - Node() {}
1.149 - Node (Invalid) { id = -1; }
1.150 - bool operator==(const Node node) const {return id == node.id;}
1.151 - bool operator!=(const Node node) const {return id != node.id;}
1.152 - bool operator<(const Node node) const {return id < node.id;}
1.153 - };
1.154 -
1.155 -
1.156 -
1.157 - class Edge {
1.158 - friend class FullUGraphBase;
1.159 -
1.160 - protected:
1.161 - int id; // _nodeNum * target + source;
1.162 -
1.163 - Edge(int _id) : id(_id) {}
1.164 -
1.165 - public:
1.166 - Edge() { }
1.167 - Edge (Invalid) { id = -1; }
1.168 - bool operator==(const Edge edge) const {return id == edge.id;}
1.169 - bool operator!=(const Edge edge) const {return id != edge.id;}
1.170 - bool operator<(const Edge edge) const {return id < edge.id;}
1.171 - };
1.172 -
1.173 - void first(Node& node) const {
1.174 - node.id = _nodeNum - 1;
1.175 - }
1.176 -
1.177 - static void next(Node& node) {
1.178 - --node.id;
1.179 - }
1.180 -
1.181 - void first(Edge& edge) const {
1.182 - edge.id = _edgeNum - 1;
1.183 - }
1.184 -
1.185 - static void next(Edge& edge) {
1.186 - --edge.id;
1.187 - }
1.188 -
1.189 - void firstOut(Edge& edge, const Node& node) const {
1.190 - int src = node.id;
1.191 - int trg = 0;
1.192 - edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
1.193 - }
1.194 -
1.195 - /// \todo with specialized iterators we can make faster iterating
1.196 - void nextOut(Edge& edge) const {
1.197 - int src = source(edge).id;
1.198 - int trg = target(edge).id;
1.199 - ++trg;
1.200 - edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
1.201 - }
1.202 -
1.203 - void firstIn(Edge& edge, const Node& node) const {
1.204 - int src = node.id + 1;
1.205 - int trg = node.id;
1.206 - edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
1.207 - }
1.208 -
1.209 - void nextIn(Edge& edge) const {
1.210 - int src = source(edge).id;
1.211 - int trg = target(edge).id;
1.212 - ++src;
1.213 - edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
1.214 - }
1.215 -
1.216 - };
1.217 -
1.218 - typedef UGraphExtender<UndirGraphExtender<FullUGraphBase> >
1.219 - ExtendedFullUGraphBase;
1.220 -
1.221 - /// \ingroup graphs
1.222 - ///
1.223 - /// \brief An undirected full graph class.
1.224 - ///
1.225 - /// This is a simple and fast undirected full graph implementation.
1.226 - /// It is completely static, so you can neither add nor delete either
1.227 - /// edges or nodes.
1.228 - ///
1.229 - /// The main difference beetween the \e FullGraph and \e FullUGraph class
1.230 - /// is that this class conforms to the undirected graph concept and
1.231 - /// it does not contain the loop edges.
1.232 - ///
1.233 - /// \sa FullUGraphBase
1.234 - /// \sa FullGraph
1.235 - ///
1.236 - /// \author Balazs Dezso
1.237 - class FullUGraph : public ExtendedFullUGraphBase {
1.238 - public:
1.239 -
1.240 - typedef ExtendedFullUGraphBase Parent;
1.241 -
1.242 - /// \brief Constructor
1.243 - FullUGraph() { construct(0); }
1.244 -
1.245 - /// \brief Constructor
1.246 - FullUGraph(int n) { construct(n); }
1.247 -
1.248 - /// \brief Resize the graph
1.249 - ///
1.250 - /// Resize the graph. The function will fully destroy and build the graph.
1.251 - /// This cause that the maps of the graph will reallocated
1.252 - /// automatically and the previous values will be lost.
1.253 - void resize(int n) {
1.254 - Parent::getNotifier(Edge()).clear();
1.255 - Parent::getNotifier(UEdge()).clear();
1.256 - Parent::getNotifier(Node()).clear();
1.257 - construct(n);
1.258 - Parent::getNotifier(Node()).build();
1.259 - Parent::getNotifier(UEdge()).build();
1.260 - Parent::getNotifier(Edge()).build();
1.261 - }
1.262 - };
1.263 -
1.264 -
1.265 - class FullBpUGraphBase {
1.266 - protected:
1.267 -
1.268 - int _aNodeNum;
1.269 - int _bNodeNum;
1.270 -
1.271 - int _edgeNum;
1.272 -
1.273 - public:
1.274 -
1.275 - class NodeSetError : public LogicError {
1.276 - virtual const char* exceptionName() const {
1.277 - return "lemon::FullBpUGraph::NodeSetError";
1.278 - }
1.279 - };
1.280 -
1.281 - class Node {
1.282 - friend class FullBpUGraphBase;
1.283 - protected:
1.284 - int id;
1.285 -
1.286 - Node(int _id) : id(_id) {}
1.287 - public:
1.288 - Node() {}
1.289 - Node(Invalid) { id = -1; }
1.290 - bool operator==(const Node i) const {return id==i.id;}
1.291 - bool operator!=(const Node i) const {return id!=i.id;}
1.292 - bool operator<(const Node i) const {return id<i.id;}
1.293 - };
1.294 -
1.295 - class UEdge {
1.296 - friend class FullBpUGraphBase;
1.297 - protected:
1.298 - int id;
1.299 -
1.300 - UEdge(int _id) { id = _id;}
1.301 - public:
1.302 - UEdge() {}
1.303 - UEdge (Invalid) { id = -1; }
1.304 - bool operator==(const UEdge i) const {return id==i.id;}
1.305 - bool operator!=(const UEdge i) const {return id!=i.id;}
1.306 - bool operator<(const UEdge i) const {return id<i.id;}
1.307 - };
1.308 -
1.309 - void construct(int aNodeNum, int bNodeNum) {
1.310 - _aNodeNum = aNodeNum;
1.311 - _bNodeNum = bNodeNum;
1.312 - _edgeNum = aNodeNum * bNodeNum;
1.313 - }
1.314 -
1.315 - void firstANode(Node& node) const {
1.316 - node.id = 2 * _aNodeNum - 2;
1.317 - if (node.id < 0) node.id = -1;
1.318 - }
1.319 - void nextANode(Node& node) const {
1.320 - node.id -= 2;
1.321 - if (node.id < 0) node.id = -1;
1.322 - }
1.323 -
1.324 - void firstBNode(Node& node) const {
1.325 - node.id = 2 * _bNodeNum - 1;
1.326 - }
1.327 - void nextBNode(Node& node) const {
1.328 - node.id -= 2;
1.329 - }
1.330 -
1.331 - void first(Node& node) const {
1.332 - if (_aNodeNum > 0) {
1.333 - node.id = 2 * _aNodeNum - 2;
1.334 - } else {
1.335 - node.id = 2 * _bNodeNum - 1;
1.336 - }
1.337 - }
1.338 - void next(Node& node) const {
1.339 - node.id -= 2;
1.340 - if (node.id == -2) {
1.341 - node.id = 2 * _bNodeNum - 1;
1.342 - }
1.343 - }
1.344 -
1.345 - void first(UEdge& edge) const {
1.346 - edge.id = _edgeNum - 1;
1.347 - }
1.348 - void next(UEdge& edge) const {
1.349 - --edge.id;
1.350 - }
1.351 -
1.352 - void firstFromANode(UEdge& edge, const Node& node) const {
1.353 - LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
1.354 - edge.id = (node.id >> 1) * _bNodeNum;
1.355 - }
1.356 - void nextFromANode(UEdge& edge) const {
1.357 - ++(edge.id);
1.358 - if (edge.id % _bNodeNum == 0) edge.id = -1;
1.359 - }
1.360 -
1.361 - void firstFromBNode(UEdge& edge, const Node& node) const {
1.362 - LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
1.363 - edge.id = (node.id >> 1);
1.364 - }
1.365 - void nextFromBNode(UEdge& edge) const {
1.366 - edge.id += _bNodeNum;
1.367 - if (edge.id >= _edgeNum) edge.id = -1;
1.368 - }
1.369 -
1.370 - static int id(const Node& node) {
1.371 - return node.id;
1.372 - }
1.373 - static Node nodeFromId(int id) {
1.374 - return Node(id);
1.375 - }
1.376 - int maxNodeId() const {
1.377 - return _aNodeNum > _bNodeNum ?
1.378 - _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
1.379 - }
1.380 -
1.381 - static int id(const UEdge& edge) {
1.382 - return edge.id;
1.383 - }
1.384 - static UEdge uEdgeFromId(int id) {
1.385 - return UEdge(id);
1.386 - }
1.387 - int maxUEdgeId() const {
1.388 - return _edgeNum - 1;
1.389 - }
1.390 -
1.391 - static int aNodeId(const Node& node) {
1.392 - return node.id >> 1;
1.393 - }
1.394 - static Node fromANodeId(int id) {
1.395 - return Node(id << 1);
1.396 - }
1.397 - int maxANodeId() const {
1.398 - return _aNodeNum;
1.399 - }
1.400 -
1.401 - static int bNodeId(const Node& node) {
1.402 - return node.id >> 1;
1.403 - }
1.404 - static Node fromBNodeId(int id) {
1.405 - return Node((id << 1) + 1);
1.406 - }
1.407 - int maxBNodeId() const {
1.408 - return _bNodeNum;
1.409 - }
1.410 -
1.411 - Node aNode(const UEdge& edge) const {
1.412 - return Node((edge.id / _bNodeNum) << 1);
1.413 - }
1.414 - Node bNode(const UEdge& edge) const {
1.415 - return Node(((edge.id % _bNodeNum) << 1) + 1);
1.416 - }
1.417 -
1.418 - static bool aNode(const Node& node) {
1.419 - return (node.id & 1) == 0;
1.420 - }
1.421 -
1.422 - static bool bNode(const Node& node) {
1.423 - return (node.id & 1) == 1;
1.424 - }
1.425 -
1.426 - static Node aNode(int index) {
1.427 - return Node(index << 1);
1.428 - }
1.429 -
1.430 - static Node bNode(int index) {
1.431 - return Node((index << 1) + 1);
1.432 - }
1.433 -
1.434 - typedef True NodeNumTag;
1.435 - int nodeNum() const { return _aNodeNum + _bNodeNum; }
1.436 - int aNodeNum() const { return _aNodeNum; }
1.437 - int bNodeNum() const { return _bNodeNum; }
1.438 -
1.439 - typedef True EdgeNumTag;
1.440 - int uEdgeNum() const { return _edgeNum; }
1.441 -
1.442 - };
1.443 -
1.444 -
1.445 - typedef BpUGraphExtender<FullBpUGraphBase> ExtendedFullBpUGraphBase;
1.446 -
1.447 -
1.448 - /// \ingroup graphs
1.449 - ///
1.450 - /// \brief An undirected full bipartite graph class.
1.451 - ///
1.452 - /// This is a simple and fast bipartite undirected full graph implementation.
1.453 - /// It is completely static, so you can neither add nor delete either
1.454 - /// edges or nodes.
1.455 - ///
1.456 - /// \sa FullUGraphBase
1.457 - /// \sa FullGraph
1.458 - ///
1.459 - /// \author Balazs Dezso
1.460 - class FullBpUGraph :
1.461 - public ExtendedFullBpUGraphBase {
1.462 - public:
1.463 -
1.464 - typedef ExtendedFullBpUGraphBase Parent;
1.465 -
1.466 - FullBpUGraph() {
1.467 - Parent::construct(0, 0);
1.468 - }
1.469 -
1.470 - FullBpUGraph(int aNodeNum, int bNodeNum) {
1.471 - Parent::construct(aNodeNum, bNodeNum);
1.472 - }
1.473 -
1.474 - /// \brief Resize the graph
1.475 - ///
1.476 - void resize(int n, int m) {
1.477 - Parent::getNotifier(Edge()).clear();
1.478 - Parent::getNotifier(UEdge()).clear();
1.479 - Parent::getNotifier(Node()).clear();
1.480 - Parent::getNotifier(ANode()).clear();
1.481 - Parent::getNotifier(BNode()).clear();
1.482 - construct(n, m);
1.483 - Parent::getNotifier(ANode()).build();
1.484 - Parent::getNotifier(BNode()).build();
1.485 - Parent::getNotifier(Node()).build();
1.486 - Parent::getNotifier(UEdge()).build();
1.487 - Parent::getNotifier(Edge()).build();
1.488 - }
1.489 - };
1.490 -
1.491 } //namespace lemon
1.492
1.493