# HG changeset patch # User deba # Date 1123766452 0 # Node ID c3defc3590aab9a11c94f5d48fccac1453f841a7 # Parent 9c98841eda96e65460df41a73ebe59a00f62a77d Matrix graph renamed to grid graph Some usefull function and documentation diff -r 9c98841eda96 -r c3defc3590aa lemon/grid_graph.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lemon/grid_graph.h Thu Aug 11 13:20:52 2005 +0000 @@ -0,0 +1,320 @@ +/* -*- 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 + +namespace lemon { + + 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 height, int width) { + _height = height; _width = width; + _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height; + _edgeLimit = _nodeNum - width; + } + + 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 * _width + j); + } + + /// \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 node) 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 UndirGraphExtender + UndirGridGraphBase; + typedef AlterableUndirGraphExtender + AlterableGridGraphBase; + typedef IterableUndirGraphExtender + IterableGridGraphBase; + typedef MappableUndirGraphExtender + MappableGridGraphBase; + + /// \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 + class GridGraph : public MappableGridGraphBase { + public: + + GridGraph(int m, int n) { construct(m, n); } + }; +} +#endif