1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/grid_ugraph.h Wed Feb 22 18:26:56 2006 +0000
1.3 @@ -0,0 +1,536 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2006
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 GRID_UGRAPH_H
1.23 +#define GRID_UGRAPH_H
1.24 +
1.25 +#include <iostream>
1.26 +#include <lemon/invalid.h>
1.27 +#include <lemon/utility.h>
1.28 +
1.29 +#include <lemon/bits/graph_extender.h>
1.30 +
1.31 +#include <lemon/xy.h>
1.32 +
1.33 +///\ingroup graphs
1.34 +///\file
1.35 +///\brief GridUGraph class.
1.36 +
1.37 +namespace lemon {
1.38 +
1.39 + /// \brief Base graph for GridUGraph.
1.40 + ///
1.41 + /// Base graph for grid graph. It describes some member functions
1.42 + /// which can be used in the GridUGraph.
1.43 + ///
1.44 + /// \warning Always use the GridUGraph instead of this.
1.45 + /// \see GridUGraph
1.46 + class GridUGraphBase {
1.47 +
1.48 + public:
1.49 +
1.50 + typedef GridUGraphBase UGraph;
1.51 +
1.52 + class Node;
1.53 + class Edge;
1.54 +
1.55 + public:
1.56 +
1.57 + GridUGraphBase() {}
1.58 +
1.59 + protected:
1.60 +
1.61 + /// \brief Creates a grid graph with the given size.
1.62 + ///
1.63 + /// Creates a grid graph with the given size.
1.64 + void construct(int width, int height) {
1.65 + _height = height; _width = width;
1.66 + _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height;
1.67 + _edgeLimit = _nodeNum - width;
1.68 + }
1.69 +
1.70 + /// \brief Gives back the edge goes down from the node.
1.71 + ///
1.72 + /// Gives back the edge goes down from the node. If there is not
1.73 + /// outgoing edge then it gives back INVALID.
1.74 + Edge _down(Node n) const {
1.75 + if (n.id < _nodeNum - _width) {
1.76 + return Edge(n.id);
1.77 + } else {
1.78 + return INVALID;
1.79 + }
1.80 + }
1.81 +
1.82 + /// \brief Gives back the edge comes from up into the node.
1.83 + ///
1.84 + /// Gives back the edge comes from up into the node. If there is not
1.85 + /// incoming edge then it gives back INVALID.
1.86 + Edge _up(Node n) const {
1.87 + if (n.id >= _width) {
1.88 + return Edge(n.id - _width);
1.89 + } else {
1.90 + return INVALID;
1.91 + }
1.92 + }
1.93 +
1.94 + /// \brief Gives back the edge goes right from the node.
1.95 + ///
1.96 + /// Gives back the edge goes right from the node. If there is not
1.97 + /// outgoing edge then it gives back INVALID.
1.98 + Edge _right(Node n) const {
1.99 + if (n.id % _width < _width - 1) {
1.100 + return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1);
1.101 + } else {
1.102 + return INVALID;
1.103 + }
1.104 + }
1.105 +
1.106 + /// \brief Gives back the edge comes from left into the node.
1.107 + ///
1.108 + /// Gives back the edge comes left up into the node. If there is not
1.109 + /// incoming edge then it gives back INVALID.
1.110 + Edge _left(Node n) const {
1.111 + if (n.id % _width > 0) {
1.112 + return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1;
1.113 + } else {
1.114 + return INVALID;
1.115 + }
1.116 + }
1.117 +
1.118 + public:
1.119 +
1.120 + class IndexError : public RuntimeError {
1.121 + public:
1.122 + virtual const char* exceptionName() const {
1.123 + return "lemon::GridUGraph::IndexError";
1.124 + }
1.125 + };
1.126 +
1.127 +
1.128 + /// \brief The node on the given position.
1.129 + ///
1.130 + /// Gives back the node on the given position.
1.131 + Node operator()(int i, int j) const {
1.132 + LEMON_ASSERT(0 <= i && i < width() && 0 <= j && j < height(), IndexError());
1.133 + return Node(i + j * _width);
1.134 + }
1.135 +
1.136 + /// \brief Gives back the row index of the node.
1.137 + ///
1.138 + /// Gives back the row index of the node.
1.139 + int row(Node n) const {
1.140 + return n.id / _width;
1.141 + }
1.142 +
1.143 + /// \brief Gives back the coloumn index of the node.
1.144 + ///
1.145 + /// Gives back the coloumn index of the node.
1.146 + int col(Node n) const {
1.147 + return n.id % _width;
1.148 + }
1.149 +
1.150 + /// \brief Gives back the width of the graph.
1.151 + ///
1.152 + /// Gives back the width of the graph.
1.153 + int width() const {
1.154 + return _width;
1.155 + }
1.156 +
1.157 + /// \brief Gives back the height of the graph.
1.158 + ///
1.159 + /// Gives back the height of the graph.
1.160 + int height() const {
1.161 + return _height;
1.162 + }
1.163 +
1.164 + typedef True NodeNumTag;
1.165 + typedef True EdgeNumTag;
1.166 +
1.167 + ///Number of nodes.
1.168 + int nodeNum() const { return _nodeNum; }
1.169 + ///Number of edges.
1.170 + int edgeNum() const { return _edgeNum; }
1.171 +
1.172 + /// Maximum node ID.
1.173 +
1.174 + /// Maximum node ID.
1.175 + ///\sa id(Node)
1.176 + int maxNodeId() const { return nodeNum() - 1; }
1.177 + /// Maximum edge ID.
1.178 +
1.179 + /// Maximum edge ID.
1.180 + ///\sa id(Edge)
1.181 + int maxEdgeId() const { return edgeNum() - 1; }
1.182 +
1.183 + /// \brief Gives back the source node of an edge.
1.184 + ///
1.185 + /// Gives back the source node of an edge.
1.186 + Node source(Edge e) const {
1.187 + if (e.id < _edgeLimit) {
1.188 + return e.id;
1.189 + } else {
1.190 + return (e.id - _edgeLimit) % (_width - 1) +
1.191 + (e.id - _edgeLimit) / (_width - 1) * _width;
1.192 + }
1.193 + }
1.194 +
1.195 + /// \brief Gives back the target node of an edge.
1.196 + ///
1.197 + /// Gives back the target node of an edge.
1.198 + Node target(Edge e) const {
1.199 + if (e.id < _edgeLimit) {
1.200 + return e.id + _width;
1.201 + } else {
1.202 + return (e.id - _edgeLimit) % (_width - 1) +
1.203 + (e.id - _edgeLimit) / (_width - 1) * _width + 1;
1.204 + }
1.205 + }
1.206 +
1.207 + /// Node ID.
1.208 +
1.209 + /// The ID of a valid Node is a nonnegative integer not greater than
1.210 + /// \ref maxNodeId(). The range of the ID's is not surely continuous
1.211 + /// and the greatest node ID can be actually less then \ref maxNodeId().
1.212 + ///
1.213 + /// The ID of the \ref INVALID node is -1.
1.214 + ///\return The ID of the node \c v.
1.215 +
1.216 + static int id(Node v) { return v.id; }
1.217 + /// Edge ID.
1.218 +
1.219 + /// The ID of a valid Edge is a nonnegative integer not greater than
1.220 + /// \ref maxEdgeId(). The range of the ID's is not surely continuous
1.221 + /// and the greatest edge ID can be actually less then \ref maxEdgeId().
1.222 + ///
1.223 + /// The ID of the \ref INVALID edge is -1.
1.224 + ///\return The ID of the edge \c e.
1.225 + static int id(Edge e) { return e.id; }
1.226 +
1.227 + static Node nodeFromId(int id) { return Node(id);}
1.228 +
1.229 + static Edge edgeFromId(int id) { return Edge(id);}
1.230 +
1.231 + typedef True FindEdgeTag;
1.232 +
1.233 + /// Finds an edge between two nodes.
1.234 +
1.235 + /// Finds an edge from node \c u to node \c v.
1.236 + ///
1.237 + /// If \c prev is \ref INVALID (this is the default value), then
1.238 + /// It finds the first edge from \c u to \c v. Otherwise it looks for
1.239 + /// the next edge from \c u to \c v after \c prev.
1.240 + /// \return The found edge or INVALID if there is no such an edge.
1.241 + Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
1.242 + if (prev != INVALID) return INVALID;
1.243 + if (v.id - u.id == _width) return Edge(u.id);
1.244 + if (v.id - u.id == 1 && u.id % _width < _width - 1) {
1.245 + return Edge(u.id / _width * (_width - 1) +
1.246 + u.id % _width + _edgeLimit);
1.247 + }
1.248 + return INVALID;
1.249 + }
1.250 +
1.251 +
1.252 + class Node {
1.253 + friend class GridUGraphBase;
1.254 +
1.255 + protected:
1.256 + int id;
1.257 + Node(int _id) { id = _id;}
1.258 + public:
1.259 + Node() {}
1.260 + Node (Invalid) { id = -1; }
1.261 + bool operator==(const Node node) const {return id == node.id;}
1.262 + bool operator!=(const Node node) const {return id != node.id;}
1.263 + bool operator<(const Node node) const {return id < node.id;}
1.264 + };
1.265 +
1.266 +
1.267 +
1.268 + class Edge {
1.269 + friend class GridUGraphBase;
1.270 +
1.271 + protected:
1.272 + int id;
1.273 +
1.274 + Edge(int _id) : id(_id) {}
1.275 +
1.276 + public:
1.277 + Edge() { }
1.278 + Edge (Invalid) { id = -1; }
1.279 + bool operator==(const Edge edge) const {return id == edge.id;}
1.280 + bool operator!=(const Edge edge) const {return id != edge.id;}
1.281 + bool operator<(const Edge edge) const {return id < edge.id;}
1.282 + };
1.283 +
1.284 + void first(Node& node) const {
1.285 + node.id = nodeNum() - 1;
1.286 + }
1.287 +
1.288 + static void next(Node& node) {
1.289 + --node.id;
1.290 + }
1.291 +
1.292 + void first(Edge& edge) const {
1.293 + edge.id = edgeNum() - 1;
1.294 + }
1.295 +
1.296 + static void next(Edge& edge) {
1.297 + --edge.id;
1.298 + }
1.299 +
1.300 + void firstOut(Edge& edge, const Node& node) const {
1.301 + if (node.id < _nodeNum - _width) {
1.302 + edge.id = node.id;
1.303 + } else if (node.id % _width < _width - 1) {
1.304 + edge.id = _edgeLimit + node.id % _width +
1.305 + (node.id / _width) * (_width - 1);
1.306 + } else {
1.307 + edge.id = -1;
1.308 + }
1.309 + }
1.310 +
1.311 + void nextOut(Edge& edge) const {
1.312 + if (edge.id >= _edgeLimit) {
1.313 + edge.id = -1;
1.314 + } else if (edge.id % _width < _width - 1) {
1.315 + edge.id = _edgeLimit + edge.id % _width +
1.316 + (edge.id / _width) * (_width - 1);
1.317 + } else {
1.318 + edge.id = -1;
1.319 + }
1.320 + }
1.321 +
1.322 + void firstIn(Edge& edge, const Node& node) const {
1.323 + if (node.id >= _width) {
1.324 + edge.id = node.id - _width;
1.325 + } else if (node.id % _width > 0) {
1.326 + edge.id = _edgeLimit + node.id % _width +
1.327 + (node.id / _width) * (_width - 1) - 1;
1.328 + } else {
1.329 + edge.id = -1;
1.330 + }
1.331 + }
1.332 +
1.333 + void nextIn(Edge& edge) const {
1.334 + if (edge.id >= _edgeLimit) {
1.335 + edge.id = -1;
1.336 + } else if (edge.id % _width > 0) {
1.337 + edge.id = _edgeLimit + edge.id % _width +
1.338 + (edge.id / _width + 1) * (_width - 1) - 1;
1.339 + } else {
1.340 + edge.id = -1;
1.341 + }
1.342 + }
1.343 +
1.344 + private:
1.345 + int _width, _height;
1.346 + int _nodeNum, _edgeNum;
1.347 + int _edgeLimit;
1.348 + };
1.349 +
1.350 +
1.351 + typedef UGraphExtender<UGraphBaseExtender<
1.352 + GridUGraphBase> > ExtendedGridUGraphBase;
1.353 +
1.354 + /// \ingroup graphs
1.355 + ///
1.356 + /// \brief Grid graph class
1.357 + ///
1.358 + /// This class implements a special graph type. The nodes of the
1.359 + /// graph can be indiced by two integer \c (i,j) value where \c i
1.360 + /// is in the \c [0,width) range and j is in the [0, height) range.
1.361 + /// Two nodes are connected in the graph if the indices differ only
1.362 + /// on one position and only one is the difference.
1.363 + ///
1.364 + /// The graph can be indiced in the following way:
1.365 + ///\code
1.366 + /// GridUGraph graph(w, h);
1.367 + /// GridUGraph::NodeMap<int> val(graph);
1.368 + /// for (int i = 0; i < graph.width(); ++i) {
1.369 + /// for (int j = 0; j < graph.height(); ++j) {
1.370 + /// val[graph(i, j)] = i + j;
1.371 + /// }
1.372 + /// }
1.373 + ///\endcode
1.374 + ///
1.375 + /// The graph type is fully conform to the \ref concept::UUGraph
1.376 + /// "Undirected UGraph" concept.
1.377 + ///
1.378 + /// \author Balazs Dezso
1.379 + /// \see GridUGraphBase
1.380 + class GridUGraph : public ExtendedGridUGraphBase {
1.381 + public:
1.382 +
1.383 + typedef ExtendedGridUGraphBase Parent;
1.384 +
1.385 + /// \brief Map to get the indices of the nodes as xy<int>.
1.386 + ///
1.387 + /// Map to get the indices of the nodes as xy<int>.
1.388 + class IndexMap {
1.389 + public:
1.390 + /// \brief The key type of the map
1.391 + typedef GridUGraph::Node Key;
1.392 + /// \brief The value type of the map
1.393 + typedef xy<int> Value;
1.394 +
1.395 + /// \brief Constructor
1.396 + ///
1.397 + /// Constructor
1.398 + IndexMap(const GridUGraph& _graph) : graph(_graph) {}
1.399 +
1.400 + /// \brief The subscript operator
1.401 + ///
1.402 + /// The subscript operator.
1.403 + Value operator[](Key key) const {
1.404 + return xy<int>(graph.row(key), graph.col(key));
1.405 + }
1.406 +
1.407 + private:
1.408 + const GridUGraph& graph;
1.409 + };
1.410 +
1.411 + /// \brief Map to get the row of the nodes.
1.412 + ///
1.413 + /// Map to get the row of the nodes.
1.414 + class RowMap {
1.415 + public:
1.416 + /// \brief The key type of the map
1.417 + typedef GridUGraph::Node Key;
1.418 + /// \brief The value type of the map
1.419 + typedef int Value;
1.420 +
1.421 + /// \brief Constructor
1.422 + ///
1.423 + /// Constructor
1.424 + RowMap(const GridUGraph& _graph) : graph(_graph) {}
1.425 +
1.426 + /// \brief The subscript operator
1.427 + ///
1.428 + /// The subscript operator.
1.429 + Value operator[](Key key) const {
1.430 + return graph.row(key);
1.431 + }
1.432 +
1.433 + private:
1.434 + const GridUGraph& graph;
1.435 + };
1.436 +
1.437 + /// \brief Map to get the column of the nodes.
1.438 + ///
1.439 + /// Map to get the column of the nodes.
1.440 + class ColMap {
1.441 + public:
1.442 + /// \brief The key type of the map
1.443 + typedef GridUGraph::Node Key;
1.444 + /// \brief The value type of the map
1.445 + typedef int Value;
1.446 +
1.447 + /// \brief Constructor
1.448 + ///
1.449 + /// Constructor
1.450 + ColMap(const GridUGraph& _graph) : graph(_graph) {}
1.451 +
1.452 + /// \brief The subscript operator
1.453 + ///
1.454 + /// The subscript operator.
1.455 + Value operator[](Key key) const {
1.456 + return graph.col(key);
1.457 + }
1.458 +
1.459 + private:
1.460 + const GridUGraph& graph;
1.461 + };
1.462 +
1.463 + /// \brief Constructor
1.464 + ///
1.465 + ///
1.466 + GridUGraph(int n, int m) { construct(n, m); }
1.467 +
1.468 + /// \brief Resize the graph
1.469 + ///
1.470 + void resize(int n, int m) {
1.471 + Parent::getNotifier(Edge()).clear();
1.472 + Parent::getNotifier(UEdge()).clear();
1.473 + Parent::getNotifier(Node()).clear();
1.474 + construct(n, m);
1.475 + Parent::getNotifier(Node()).build();
1.476 + Parent::getNotifier(UEdge()).build();
1.477 + Parent::getNotifier(Edge()).build();
1.478 + }
1.479 +
1.480 + /// \brief Gives back the edge goes down from the node.
1.481 + ///
1.482 + /// Gives back the edge goes down from the node. If there is not
1.483 + /// outgoing edge then it gives back INVALID.
1.484 + Edge down(Node n) const {
1.485 + UEdge ue = _down(n);
1.486 + return ue != INVALID ? direct(ue, true) : INVALID;
1.487 + }
1.488 +
1.489 + /// \brief Gives back the edge goes up from the node.
1.490 + ///
1.491 + /// Gives back the edge goes up from the node. If there is not
1.492 + /// outgoing edge then it gives back INVALID.
1.493 + Edge up(Node n) const {
1.494 + UEdge ue = _up(n);
1.495 + return ue != INVALID ? direct(ue, false) : INVALID;
1.496 + }
1.497 +
1.498 + /// \brief Gives back the edge goes right from the node.
1.499 + ///
1.500 + /// Gives back the edge goes right from the node. If there is not
1.501 + /// outgoing edge then it gives back INVALID.
1.502 + Edge right(Node n) const {
1.503 + UEdge ue = _right(n);
1.504 + return ue != INVALID ? direct(ue, true) : INVALID;
1.505 + }
1.506 +
1.507 + /// \brief Gives back the edge goes left from the node.
1.508 + ///
1.509 + /// Gives back the edge goes left from the node. If there is not
1.510 + /// outgoing edge then it gives back INVALID.
1.511 + Edge left(Node n) const {
1.512 + UEdge ue = _left(n);
1.513 + return ue != INVALID ? direct(ue, false) : INVALID;
1.514 + }
1.515 +
1.516 + };
1.517 +
1.518 + /// \brief Index map of the grid graph
1.519 + ///
1.520 + /// Just returns an IndexMap for the grid graph.
1.521 + GridUGraph::IndexMap indexMap(const GridUGraph& graph) {
1.522 + return GridUGraph::IndexMap(graph);
1.523 + }
1.524 +
1.525 + /// \brief Row map of the grid graph
1.526 + ///
1.527 + /// Just returns a RowMap for the grid graph.
1.528 + GridUGraph::RowMap rowMap(const GridUGraph& graph) {
1.529 + return GridUGraph::RowMap(graph);
1.530 + }
1.531 +
1.532 + /// \brief Column map of the grid graph
1.533 + ///
1.534 + /// Just returns a ColMap for the grid graph.
1.535 + GridUGraph::ColMap colMap(const GridUGraph& graph) {
1.536 + return GridUGraph::ColMap(graph);
1.537 + }
1.538 +}
1.539 +#endif