Added copyright header and description.
2 * lemon/matrix_graph.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef MATRIX_GRAPH_H
18 #define MATRIX_GRAPH_H
21 #include <lemon/invalid.h>
22 #include <lemon/utility.h>
24 #include <lemon/bits/iterable_graph_extender.h>
25 #include <lemon/bits/alteration_notifier.h>
26 #include <lemon/bits/default_map.h>
28 #include <lemon/bits/undir_graph_extender.h>
32 class MatrixGraphBase {
36 typedef MatrixGraphBase Graph;
45 ///Creates a full graph with \c n nodes.
46 void construct(int height, int width) {
47 _height = height; _width = width;
48 _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height;
49 _edgeLimit = _nodeNum - width;
52 Node operator()(int i, int j) const {
53 return Node(i * _width + j);
64 typedef True NodeNumTag;
65 typedef True EdgeNumTag;
68 int nodeNum() const { return _nodeNum; }
70 int edgeNum() const { return _edgeNum; }
76 int maxId(Node = INVALID) const { return nodeNum() - 1; }
81 int maxId(Edge = INVALID) const { return edgeNum() - 1; }
83 Node source(Edge e) const {
84 if (e.id < _edgeLimit) {
87 return (e.id - _edgeLimit) % (_width - 1) +
88 (e.id - _edgeLimit) / (_width - 1) * _width;
92 Node target(Edge e) const {
93 if (e.id < _edgeLimit) {
96 return (e.id - _edgeLimit) % (_width - 1) +
97 (e.id - _edgeLimit) / (_width - 1) * _width + 1;
103 /// The ID of a valid Node is a nonnegative integer not greater than
104 /// \ref maxNodeId(). The range of the ID's is not surely continuous
105 /// and the greatest node ID can be actually less then \ref maxNodeId().
107 /// The ID of the \ref INVALID node is -1.
108 ///\return The ID of the node \c v.
110 static int id(Node v) { return v.id; }
113 /// The ID of a valid Edge is a nonnegative integer not greater than
114 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
115 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
117 /// The ID of the \ref INVALID edge is -1.
118 ///\return The ID of the edge \c e.
119 static int id(Edge e) { return e.id; }
121 static Node fromId(int id, Node) { return Node(id);}
123 static Edge fromId(int id, Edge) { return Edge(id);}
125 typedef True FindEdgeTag;
127 /// Finds an edge between two nodes.
129 /// Finds an edge from node \c u to node \c v.
131 /// If \c prev is \ref INVALID (this is the default value), then
132 /// It finds the first edge from \c u to \c v. Otherwise it looks for
133 /// the next edge from \c u to \c v after \c prev.
134 /// \return The found edge or INVALID if there is no such an edge.
135 Edge findEdge(Node u, Node v, Edge prev = INVALID) {
136 if (prev != INVALID) return INVALID;
137 if (v.id - u.id == _width) return Edge(u.id);
138 if (v.id - u.id == 1 && u.id % _width < _width - 1) {
139 return Edge(u.id / _width * (_width - 1) +
140 u.id % _width + _edgeLimit);
147 friend class MatrixGraphBase;
151 Node(int _id) { id = _id;}
154 Node (Invalid) { id = -1; }
155 bool operator==(const Node node) const {return id == node.id;}
156 bool operator!=(const Node node) const {return id != node.id;}
157 bool operator<(const Node node) const {return id < node.id;}
163 friend class MatrixGraphBase;
168 Edge(int _id) : id(_id) {}
172 Edge (Invalid) { id = -1; }
173 bool operator==(const Edge edge) const {return id == edge.id;}
174 bool operator!=(const Edge edge) const {return id != edge.id;}
175 bool operator<(const Edge edge) const {return id < edge.id;}
178 void first(Node& node) const {
179 node.id = nodeNum() - 1;
182 static void next(Node& node) {
186 void first(Edge& edge) const {
187 edge.id = edgeNum() - 1;
190 static void next(Edge& edge) {
194 void firstOut(Edge& edge, const Node& node) const {
195 if (node.id < _nodeNum - _width) {
197 } else if (node.id % _width < _width - 1) {
198 edge.id = _edgeLimit + node.id % _width +
199 (node.id / _width) * (_width - 1);
205 void nextOut(Edge& edge) const {
206 if (edge.id >= _edgeLimit) {
208 } else if (edge.id % _width < _width - 1) {
209 edge.id = _edgeLimit + edge.id % _width +
210 (edge.id / _width) * (_width - 1);
216 void firstIn(Edge& edge, const Node& node) const {
217 if (node.id >= _width) {
218 edge.id = node.id - _width;
219 } else if (node.id % _width > 0) {
220 edge.id = _edgeLimit + node.id % _width +
221 (node.id / _width) * (_width - 1) - 1;
227 void nextIn(Edge& edge) const {
228 if (edge.id >= _edgeLimit) {
230 } else if (edge.id % _width > 0) {
231 edge.id = _edgeLimit + edge.id % _width +
232 (edge.id / _width + 1) * (_width - 1) - 1;
240 int _nodeNum, _edgeNum;
245 typedef UndirGraphExtender<MatrixGraphBase>
246 UndirMatrixGraphBase;
247 typedef AlterableUndirGraphExtender<UndirMatrixGraphBase>
248 AlterableMatrixGraphBase;
249 typedef IterableUndirGraphExtender<AlterableMatrixGraphBase>
250 IterableMatrixGraphBase;
251 typedef MappableUndirGraphExtender<IterableMatrixGraphBase>
252 MappableMatrixGraphBase;
256 /// \brief Matrix graph class
258 /// This class implements a special graph type. The nodes of the
259 /// graph can be indiced by two integer \c (i,j) value where \c i
260 /// is in the \c [0,height) range and j is in the [0, width) range.
261 /// Two nodes are connected in the graph if the indices differ only
262 /// on one position and only one is the difference.
264 /// The graph can be indiced in the following way:
266 /// MatrixGraph graph(h, w);
267 /// MatrixGraph::NodeMap<int> val(graph);
268 /// for (int i = 0; i < graph.height(); ++i) {
269 /// for (int j = 0; j < graph.width(); ++j) {
270 /// val[graph(i, j)] = i + j;
275 /// The graph type is fully conform to the \ref concept::UndirGraph
276 /// "Undirected Graph" concept.
278 /// \author Balazs Dezso
279 class MatrixGraph : public MappableMatrixGraphBase {
282 MatrixGraph(int m, int n) { construct(m, n); }