/* -*- C++ -*- * lemon/grid_graph.h - Part of LEMON, a generic C++ optimization library * * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * * Permission to use, modify and distribute this software is granted * provided that this copyright notice appears in all copies. For * precise terms see the accompanying LICENSE file. * * This software is provided "AS IS" with no warranty of any kind, * express or implied, and with no claim as to its suitability for any * purpose. * */ #ifndef GRID_GRAPH_H #define GRID_GRAPH_H #include #include #include #include #include #include #include #include ///\ingroup graphs ///\file ///\brief GridGraph class. namespace lemon { /// \brief Base graph for GridGraph. /// /// Base graph for grid graph. It describes some member functions /// which can be used in the GridGraph. /// /// \warning Always use the GridGraph instead of this. /// \see GridGraph class GridGraphBase { public: typedef GridGraphBase Graph; class Node; class Edge; public: GridGraphBase() {} protected: /// \brief Creates a grid graph with the given size. /// /// Creates a grid graph with the given size. void construct(int width, int height) { _height = height; _width = width; _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height; _edgeLimit = _nodeNum - width; } /// \brief Gives back the edge goes down from the node. /// /// Gives back the edge goes down from the node. If there is not /// outgoing edge then it gives back INVALID. Edge _down(Node n) const { if (n.id < _nodeNum - _width) { return Edge(n.id); } else { return INVALID; } } /// \brief Gives back the edge comes from up into the node. /// /// Gives back the edge comes from up into the node. If there is not /// incoming edge then it gives back INVALID. Edge _up(Node n) const { if (n.id >= _width) { return Edge(n.id - _width); } else { return INVALID; } } /// \brief Gives back the edge goes right from the node. /// /// Gives back the edge goes right from the node. If there is not /// outgoing edge then it gives back INVALID. Edge _right(Node n) const { if (n.id % _width < _width - 1) { return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1); } else { return INVALID; } } /// \brief Gives back the edge comes from left into the node. /// /// Gives back the edge comes left up into the node. If there is not /// incoming edge then it gives back INVALID. Edge _left(Node n) const { if (n.id % _width > 0) { return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1; } else { return INVALID; } } public: /// \brief The node on the given position. /// /// Gives back the node on the given position. Node operator()(int i, int j) const { return Node(i + j * _width); } /// \brief Gives back the row index of the node. /// /// Gives back the row index of the node. int row(Node n) const { return n.id / _width; } /// \brief Gives back the coloumn index of the node. /// /// Gives back the coloumn index of the node. int col(Node n) const { return n.id % _width; } /// \brief Gives back the width of the graph. /// /// Gives back the width of the graph. int width() const { return _width; } /// \brief Gives back the height of the graph. /// /// Gives back the height of the graph. int height() const { return _height; } typedef True NodeNumTag; typedef True EdgeNumTag; ///Number of nodes. int nodeNum() const { return _nodeNum; } ///Number of edges. int edgeNum() const { return _edgeNum; } /// Maximum node ID. /// Maximum node ID. ///\sa id(Node) int maxId(Node = INVALID) const { return nodeNum() - 1; } /// Maximum edge ID. /// Maximum edge ID. ///\sa id(Edge) int maxId(Edge = INVALID) const { return edgeNum() - 1; } /// \brief Gives back the source node of an edge. /// /// Gives back the source node of an edge. Node source(Edge e) const { if (e.id < _edgeLimit) { return e.id; } else { return (e.id - _edgeLimit) % (_width - 1) + (e.id - _edgeLimit) / (_width - 1) * _width; } } /// \brief Gives back the target node of an edge. /// /// Gives back the target node of an edge. Node target(Edge e) const { if (e.id < _edgeLimit) { return e.id + _width; } else { return (e.id - _edgeLimit) % (_width - 1) + (e.id - _edgeLimit) / (_width - 1) * _width + 1; } } /// Node ID. /// The ID of a valid Node is a nonnegative integer not greater than /// \ref maxNodeId(). The range of the ID's is not surely continuous /// and the greatest node ID can be actually less then \ref maxNodeId(). /// /// The ID of the \ref INVALID node is -1. ///\return The ID of the node \c v. static int id(Node v) { return v.id; } /// Edge ID. /// The ID of a valid Edge is a nonnegative integer not greater than /// \ref maxEdgeId(). The range of the ID's is not surely continuous /// and the greatest edge ID can be actually less then \ref maxEdgeId(). /// /// The ID of the \ref INVALID edge is -1. ///\return The ID of the edge \c e. static int id(Edge e) { return e.id; } static Node fromId(int id, Node) { return Node(id);} static Edge fromId(int id, Edge) { return Edge(id);} typedef True FindEdgeTag; /// Finds an edge between two nodes. /// Finds an edge from node \c u to node \c v. /// /// If \c prev is \ref INVALID (this is the default value), then /// It finds the first edge from \c u to \c v. Otherwise it looks for /// the next edge from \c u to \c v after \c prev. /// \return The found edge or INVALID if there is no such an edge. Edge findEdge(Node u, Node v, Edge prev = INVALID) { if (prev != INVALID) return INVALID; if (v.id - u.id == _width) return Edge(u.id); if (v.id - u.id == 1 && u.id % _width < _width - 1) { return Edge(u.id / _width * (_width - 1) + u.id % _width + _edgeLimit); } return INVALID; } class Node { friend class GridGraphBase; protected: int id; Node(int _id) { id = _id;} public: Node() {} Node (Invalid) { id = -1; } bool operator==(const Node node) const {return id == node.id;} bool operator!=(const Node node) const {return id != node.id;} bool operator<(const Node node) const {return id < node.id;} }; class Edge { friend class GridGraphBase; protected: int id; Edge(int _id) : id(_id) {} public: Edge() { } Edge (Invalid) { id = -1; } bool operator==(const Edge edge) const {return id == edge.id;} bool operator!=(const Edge edge) const {return id != edge.id;} bool operator<(const Edge edge) const {return id < edge.id;} }; void first(Node& node) const { node.id = nodeNum() - 1; } static void next(Node& node) { --node.id; } void first(Edge& edge) const { edge.id = edgeNum() - 1; } static void next(Edge& edge) { --edge.id; } void firstOut(Edge& edge, const Node& node) const { if (node.id < _nodeNum - _width) { edge.id = node.id; } else if (node.id % _width < _width - 1) { edge.id = _edgeLimit + node.id % _width + (node.id / _width) * (_width - 1); } else { edge.id = -1; } } void nextOut(Edge& edge) const { if (edge.id >= _edgeLimit) { edge.id = -1; } else if (edge.id % _width < _width - 1) { edge.id = _edgeLimit + edge.id % _width + (edge.id / _width) * (_width - 1); } else { edge.id = -1; } } void firstIn(Edge& edge, const Node& node) const { if (node.id >= _width) { edge.id = node.id - _width; } else if (node.id % _width > 0) { edge.id = _edgeLimit + node.id % _width + (node.id / _width) * (_width - 1) - 1; } else { edge.id = -1; } } void nextIn(Edge& edge) const { if (edge.id >= _edgeLimit) { edge.id = -1; } else if (edge.id % _width > 0) { edge.id = _edgeLimit + edge.id % _width + (edge.id / _width + 1) * (_width - 1) - 1; } else { edge.id = -1; } } private: int _width, _height; int _nodeNum, _edgeNum; int _edgeLimit; }; typedef StaticMappableUndirGraphExtender< IterableUndirGraphExtender< AlterableUndirGraphExtender< UndirGraphExtender > > > ExtendedGridGraphBase; /// \ingroup graphs /// /// \brief Grid graph class /// /// This class implements a special graph type. The nodes of the /// graph can be indiced by two integer \c (i,j) value where \c i /// is in the \c [0,height) range and j is in the [0, width) range. /// Two nodes are connected in the graph if the indices differ only /// on one position and only one is the difference. /// /// The graph can be indiced in the following way: /// \code /// GridGraph graph(h, w); /// GridGraph::NodeMap val(graph); /// for (int i = 0; i < graph.height(); ++i) { /// for (int j = 0; j < graph.width(); ++j) { /// val[graph(i, j)] = i + j; /// } /// } /// \endcode /// /// The graph type is fully conform to the \ref concept::UndirGraph /// "Undirected Graph" concept. /// /// \author Balazs Dezso /// \see GridGraphBase class GridGraph : public ExtendedGridGraphBase { public: /// \brief Map to get the indices of the nodes as xy. /// /// Map to get the indices of the nodes as xy. class IndexMap { public: typedef True NeedCopy; /// \brief The key type of the map typedef GridGraph::Node Key; /// \brief The value type of the map typedef xy Value; /// \brief Constructor /// /// Constructor IndexMap(const GridGraph& _graph) : graph(_graph) {} /// \brief The subscript operator /// /// The subscript operator. Value operator[](Key key) const { return xy(graph.row(key), graph.col(key)); } private: const GridGraph& graph; }; /// \brief Map to get the row of the nodes. /// /// Map to get the row of the nodes. class RowMap { public: typedef True NeedCopy; /// \brief The key type of the map typedef GridGraph::Node Key; /// \brief The value type of the map typedef int Value; /// \brief Constructor /// /// Constructor RowMap(const GridGraph& _graph) : graph(_graph) {} /// \brief The subscript operator /// /// The subscript operator. Value operator[](Key key) const { return graph.row(key); } private: const GridGraph& graph; }; /// \brief Map to get the column of the nodes. /// /// Map to get the column of the nodes. class ColMap { public: typedef True NeedCopy; /// \brief The key type of the map typedef GridGraph::Node Key; /// \brief The value type of the map typedef int Value; /// \brief Constructor /// /// Constructor ColMap(const GridGraph& _graph) : graph(_graph) {} /// \brief The subscript operator /// /// The subscript operator. Value operator[](Key key) const { return graph.col(key); } private: const GridGraph& graph; }; GridGraph(int n, int m) { construct(n, m); } /// \brief Gives back the edge goes down from the node. /// /// Gives back the edge goes down from the node. If there is not /// outgoing edge then it gives back INVALID. Edge down(Node n) const { UndirEdge ue = _down(n); return ue != INVALID ? direct(ue, true) : INVALID; } /// \brief Gives back the edge goes up from the node. /// /// Gives back the edge goes up from the node. If there is not /// outgoing edge then it gives back INVALID. Edge up(Node n) const { UndirEdge ue = _up(n); return ue != INVALID ? direct(ue, false) : INVALID; } /// \brief Gives back the edge goes right from the node. /// /// Gives back the edge goes right from the node. If there is not /// outgoing edge then it gives back INVALID. Edge right(Node n) const { UndirEdge ue = _right(n); return ue != INVALID ? direct(ue, true) : INVALID; } /// \brief Gives back the edge goes left from the node. /// /// Gives back the edge goes left from the node. If there is not /// outgoing edge then it gives back INVALID. Edge left(Node n) const { UndirEdge ue = _left(n); return ue != INVALID ? direct(ue, false) : INVALID; } }; /// \brief Index map of the grid graph /// /// Just returns an IndexMap for the grid graph. GridGraph::IndexMap indexMap(const GridGraph& graph) { return GridGraph::IndexMap(graph); } /// \brief Row map of the grid graph /// /// Just returns an RowMap for the grid graph. GridGraph::RowMap rowMap(const GridGraph& graph) { return GridGraph::RowMap(graph); } /// \brief Coloumn map of the grid graph /// /// Just returns an ColMap for the grid graph. GridGraph::ColMap colMap(const GridGraph& graph) { return GridGraph::ColMap(graph); } } #endif