COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/matrix_graph.h @ 1622:9c98841eda96

Last change on this file since 1622:9c98841eda96 was 1591:03aa0a6c8dca, checked in by Alpar Juttner, 14 years ago

Spellrecheck

File size: 7.4 KB
Line 
1/* -*- C++ -*-
2 * lemon/matrix_graph.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
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.
10 *
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
13 * purpose.
14 *
15 */
16
17#ifndef MATRIX_GRAPH_H
18#define MATRIX_GRAPH_H
19
20#include <iostream>
21#include <lemon/invalid.h>
22#include <lemon/utility.h>
23
24#include <lemon/bits/iterable_graph_extender.h>
25#include <lemon/bits/alteration_notifier.h>
26#include <lemon/bits/default_map.h>
27
28#include <lemon/bits/undir_graph_extender.h>
29
30namespace lemon {
31
32  class MatrixGraphBase {
33
34  public:
35
36    typedef MatrixGraphBase Graph;
37
38    class Node;
39    class Edge;
40
41  public:
42
43    MatrixGraphBase() {}
44
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;
50    }
51   
52    Node operator()(int i, int j) const {
53      return Node(i * _width + j);
54    }
55
56    int width() const {
57      return _width;
58    }
59
60    int height() const {
61      return _height;
62    }
63
64    typedef True NodeNumTag;
65    typedef True EdgeNumTag;
66
67    ///Number of nodes.
68    int nodeNum() const { return _nodeNum; }
69    ///Number of edges.
70    int edgeNum() const { return _edgeNum; }
71
72    /// Maximum node ID.
73   
74    /// Maximum node ID.
75    ///\sa id(Node)
76    int maxId(Node = INVALID) const { return nodeNum() - 1; }
77    /// Maximum edge ID.
78   
79    /// Maximum edge ID.
80    ///\sa id(Edge)
81    int maxId(Edge = INVALID) const { return edgeNum() - 1; }
82
83    Node source(Edge e) const {
84      if (e.id < _edgeLimit) {
85        return e.id;
86      } else {
87        return (e.id - _edgeLimit) % (_width - 1) +
88          (e.id - _edgeLimit) / (_width - 1) * _width;
89      }
90    }
91
92    Node target(Edge e) const {
93      if (e.id < _edgeLimit) {
94        return e.id + _width;
95      } else {
96        return (e.id - _edgeLimit) % (_width - 1) +
97          (e.id - _edgeLimit) / (_width - 1) * _width + 1;
98      }
99    }
100
101    /// Node ID.
102   
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().
106    ///
107    /// The ID of the \ref INVALID node is -1.
108    ///\return The ID of the node \c v.
109
110    static int id(Node v) { return v.id; }
111    /// Edge ID.
112   
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().
116    ///
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; }
120
121    static Node fromId(int id, Node) { return Node(id);}
122   
123    static Edge fromId(int id, Edge) { return Edge(id);}
124
125    typedef True FindEdgeTag;
126
127    /// Finds an edge between two nodes.
128   
129    /// Finds an edge from node \c u to node \c v.
130    ///
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);
141      }
142      return INVALID;
143    }
144   
145     
146    class Node {
147      friend class MatrixGraphBase;
148
149    protected:
150      int id;
151      Node(int _id) { id = _id;}
152    public:
153      Node() {}
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;}
158    };
159   
160
161
162    class Edge {
163      friend class MatrixGraphBase;
164     
165    protected:
166      int id;
167
168      Edge(int _id) : id(_id) {}
169
170    public:
171      Edge() { }
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;}
176    };
177
178    void first(Node& node) const {
179      node.id = nodeNum() - 1;
180    }
181
182    static void next(Node& node) {
183      --node.id;
184    }
185
186    void first(Edge& edge) const {
187      edge.id = edgeNum() - 1;
188    }
189
190    static void next(Edge& edge) {
191      --edge.id;
192    }
193
194    void firstOut(Edge& edge, const Node& node) const {
195      if (node.id < _nodeNum - _width) {
196        edge.id = node.id;
197      } else if (node.id % _width < _width - 1) {
198        edge.id = _edgeLimit + node.id % _width +
199          (node.id / _width) * (_width - 1);
200      } else {
201        edge.id = -1;
202      }
203    }
204
205    void nextOut(Edge& edge) const {
206      if (edge.id >= _edgeLimit) {
207        edge.id = -1;
208      } else if (edge.id % _width < _width - 1) {
209        edge.id = _edgeLimit + edge.id % _width +
210          (edge.id / _width) * (_width - 1);
211      } else {
212        edge.id = -1;
213      }
214    }
215
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;
222      } else {
223        edge.id = -1;
224      }
225    }
226   
227    void nextIn(Edge& edge) const {
228      if (edge.id >= _edgeLimit) {
229        edge.id = -1;
230      } else if (edge.id % _width > 0) {
231        edge.id = _edgeLimit + edge.id % _width +
232          (edge.id / _width + 1) * (_width - 1) - 1;
233      } else {
234        edge.id = -1;
235      }
236    }
237
238  private:
239    int _width, _height;
240    int _nodeNum, _edgeNum;
241    int _edgeLimit;
242  };
243
244
245  typedef UndirGraphExtender<MatrixGraphBase>
246  UndirMatrixGraphBase;
247  typedef AlterableUndirGraphExtender<UndirMatrixGraphBase>
248  AlterableMatrixGraphBase;
249  typedef IterableUndirGraphExtender<AlterableMatrixGraphBase>
250  IterableMatrixGraphBase;
251  typedef MappableUndirGraphExtender<IterableMatrixGraphBase>
252  MappableMatrixGraphBase;
253
254  /// \ingroup graphs
255  ///
256  /// \brief Matrix graph class
257  ///
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.
263  ///
264  /// The graph can be indiced in the following way:
265  /// \code
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;
271  ///   }
272  /// }
273  /// \endcode
274  ///
275  /// The graph type is fully conform to the \ref concept::UndirGraph
276  /// "Undirected Graph" concept.
277  ///
278  /// \author Balazs Dezso
279  class MatrixGraph : public MappableMatrixGraphBase {
280  public:
281   
282    MatrixGraph(int m, int n) { construct(m, n); }
283  };
284}
285#endif
Note: See TracBrowser for help on using the repository browser.