/* -*- C++ -*- * lemon/matrix_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 MATRIX_GRAPH_H #define MATRIX_GRAPH_H #include #include #include #include #include #include #include namespace lemon { class MatrixGraphBase { public: typedef MatrixGraphBase Graph; class Node; class Edge; public: MatrixGraphBase() {} ///Creates a full graph with \c n nodes. void construct(int height, int width) { _height = height; _width = width; _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height; _edgeLimit = _nodeNum - width; } Node operator()(int i, int j) const { return Node(i * _width + j); } int width() const { return _width; } 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; } 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; } } 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 MatrixGraphBase; 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 MatrixGraphBase; 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 UndirMatrixGraphBase; typedef AlterableUndirGraphExtender AlterableMatrixGraphBase; typedef IterableUndirGraphExtender IterableMatrixGraphBase; typedef MappableUndirGraphExtender MappableMatrixGraphBase; /// \ingroup graphs /// /// \brief Matrix 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 /// MatrixGraph graph(h, w); /// MatrixGraph::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 MatrixGraph : public MappableMatrixGraphBase { public: MatrixGraph(int m, int n) { construct(m, n); } }; } #endif