The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.
The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.
The ResGraphAdaptor is based on this composition.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
23 #include <lemon/invalid.h>
24 #include <lemon/utility.h>
26 #include <lemon/bits/graph_extender.h>
32 ///\brief GridUGraph class.
36 /// \brief Base graph for GridUGraph.
38 /// Base graph for grid graph. It describes some member functions
39 /// which can be used in the GridUGraph.
41 /// \warning Always use the GridUGraph instead of this.
43 class GridUGraphBase {
47 typedef GridUGraphBase UGraph;
58 /// \brief Creates a grid graph with the given size.
60 /// Creates a grid graph with the given size.
61 void construct(int width, int height) {
62 _height = height; _width = width;
63 _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height;
64 _edgeLimit = _nodeNum - width;
67 /// \brief Gives back the edge goes down from the node.
69 /// Gives back the edge goes down from the node. If there is not
70 /// outgoing edge then it gives back INVALID.
71 Edge _down(Node n) const {
72 if (n.id < _nodeNum - _width) {
79 /// \brief Gives back the edge comes from up into the node.
81 /// Gives back the edge comes from up into the node. If there is not
82 /// incoming edge then it gives back INVALID.
83 Edge _up(Node n) const {
85 return Edge(n.id - _width);
91 /// \brief Gives back the edge goes right from the node.
93 /// Gives back the edge goes right from the node. If there is not
94 /// outgoing edge then it gives back INVALID.
95 Edge _right(Node n) const {
96 if (n.id % _width < _width - 1) {
97 return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1);
103 /// \brief Gives back the edge comes from left into the node.
105 /// Gives back the edge comes left up into the node. If there is not
106 /// incoming edge then it gives back INVALID.
107 Edge _left(Node n) const {
108 if (n.id % _width > 0) {
109 return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1;
117 class IndexError : public RuntimeError {
119 virtual const char* exceptionName() const {
120 return "lemon::GridUGraph::IndexError";
125 /// \brief The node on the given position.
127 /// Gives back the node on the given position.
128 Node operator()(int i, int j) const {
129 LEMON_ASSERT(0 <= i && i < width() && 0 <= j &&
130 j < height(), IndexError());
131 return Node(i + j * _width);
134 /// \brief Gives back the row index of the node.
136 /// Gives back the row index of the node.
137 int row(Node n) const {
138 return n.id / _width;
141 /// \brief Gives back the coloumn index of the node.
143 /// Gives back the coloumn index of the node.
144 int col(Node n) const {
145 return n.id % _width;
148 /// \brief Gives back the width of the graph.
150 /// Gives back the width of the graph.
155 /// \brief Gives back the height of the graph.
157 /// Gives back the height of the graph.
162 typedef True NodeNumTag;
163 typedef True EdgeNumTag;
166 int nodeNum() const { return _nodeNum; }
168 int edgeNum() const { return _edgeNum; }
174 int maxNodeId() const { return nodeNum() - 1; }
179 int maxEdgeId() const { return edgeNum() - 1; }
181 /// \brief Gives back the source node of an edge.
183 /// Gives back the source node of an edge.
184 Node source(Edge e) const {
185 if (e.id < _edgeLimit) {
188 return (e.id - _edgeLimit) % (_width - 1) +
189 (e.id - _edgeLimit) / (_width - 1) * _width;
193 /// \brief Gives back the target node of an edge.
195 /// Gives back the target node of an edge.
196 Node target(Edge e) const {
197 if (e.id < _edgeLimit) {
198 return e.id + _width;
200 return (e.id - _edgeLimit) % (_width - 1) +
201 (e.id - _edgeLimit) / (_width - 1) * _width + 1;
207 /// The ID of a valid Node is a nonnegative integer not greater than
208 /// \ref maxNodeId(). The range of the ID's is not surely continuous
209 /// and the greatest node ID can be actually less then \ref maxNodeId().
211 /// The ID of the \ref INVALID node is -1.
212 ///\return The ID of the node \c v.
214 static int id(Node v) { return v.id; }
217 /// The ID of a valid Edge is a nonnegative integer not greater than
218 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
219 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
221 /// The ID of the \ref INVALID edge is -1.
222 ///\return The ID of the edge \c e.
223 static int id(Edge e) { return e.id; }
225 static Node nodeFromId(int id) { return Node(id);}
227 static Edge edgeFromId(int id) { return Edge(id);}
229 typedef True FindEdgeTag;
231 /// Finds an edge between two nodes.
233 /// Finds an edge from node \c u to node \c v.
235 /// If \c prev is \ref INVALID (this is the default value), then
236 /// It finds the first edge from \c u to \c v. Otherwise it looks for
237 /// the next edge from \c u to \c v after \c prev.
238 /// \return The found edge or INVALID if there is no such an edge.
239 Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
240 if (prev != INVALID) return INVALID;
241 if (v.id - u.id == _width) return Edge(u.id);
242 if (v.id - u.id == 1 && u.id % _width < _width - 1) {
243 return Edge(u.id / _width * (_width - 1) +
244 u.id % _width + _edgeLimit);
251 friend class GridUGraphBase;
255 Node(int _id) { id = _id;}
258 Node (Invalid) { id = -1; }
259 bool operator==(const Node node) const {return id == node.id;}
260 bool operator!=(const Node node) const {return id != node.id;}
261 bool operator<(const Node node) const {return id < node.id;}
267 friend class GridUGraphBase;
272 Edge(int _id) : id(_id) {}
276 Edge (Invalid) { id = -1; }
277 bool operator==(const Edge edge) const {return id == edge.id;}
278 bool operator!=(const Edge edge) const {return id != edge.id;}
279 bool operator<(const Edge edge) const {return id < edge.id;}
282 void first(Node& node) const {
283 node.id = nodeNum() - 1;
286 static void next(Node& node) {
290 void first(Edge& edge) const {
291 edge.id = edgeNum() - 1;
294 static void next(Edge& edge) {
298 void firstOut(Edge& edge, const Node& node) const {
299 if (node.id < _nodeNum - _width) {
301 } else if (node.id % _width < _width - 1) {
302 edge.id = _edgeLimit + node.id % _width +
303 (node.id / _width) * (_width - 1);
309 void nextOut(Edge& edge) const {
310 if (edge.id >= _edgeLimit) {
312 } else if (edge.id % _width < _width - 1) {
313 edge.id = _edgeLimit + edge.id % _width +
314 (edge.id / _width) * (_width - 1);
320 void firstIn(Edge& edge, const Node& node) const {
321 if (node.id >= _width) {
322 edge.id = node.id - _width;
323 } else if (node.id % _width > 0) {
324 edge.id = _edgeLimit + node.id % _width +
325 (node.id / _width) * (_width - 1) - 1;
331 void nextIn(Edge& edge) const {
332 if (edge.id >= _edgeLimit) {
334 } else if (edge.id % _width > 0) {
335 edge.id = _edgeLimit + edge.id % _width +
336 (edge.id / _width + 1) * (_width - 1) - 1;
344 int _nodeNum, _edgeNum;
349 typedef UGraphExtender<UGraphBaseExtender<
350 GridUGraphBase> > ExtendedGridUGraphBase;
354 /// \brief Grid graph class
356 /// This class implements a special graph type. The nodes of the
357 /// graph can be indiced by two integer \c (i,j) value where \c i
358 /// is in the \c [0,width) range and j is in the [0, height) range.
359 /// Two nodes are connected in the graph if the indices differ only
360 /// on one position and only one is the difference.
362 /// The graph can be indiced in the following way:
364 /// GridUGraph graph(w, h);
365 /// GridUGraph::NodeMap<int> val(graph);
366 /// for (int i = 0; i < graph.width(); ++i) {
367 /// for (int j = 0; j < graph.height(); ++j) {
368 /// val[graph(i, j)] = i + j;
373 /// The graph type is fully conform to the \ref concept::UUGraph
374 /// "Undirected UGraph" concept.
376 /// \author Balazs Dezso
377 /// \see GridUGraphBase
378 class GridUGraph : public ExtendedGridUGraphBase {
381 typedef ExtendedGridUGraphBase Parent;
383 /// \brief Map to get the indices of the nodes as xy<int>.
385 /// Map to get the indices of the nodes as xy<int>.
388 /// \brief The key type of the map
389 typedef GridUGraph::Node Key;
390 /// \brief The value type of the map
391 typedef xy<int> Value;
393 /// \brief Constructor
396 IndexMap(const GridUGraph& _graph) : graph(_graph) {}
398 /// \brief The subscript operator
400 /// The subscript operator.
401 Value operator[](Key key) const {
402 return xy<int>(graph.row(key), graph.col(key));
406 const GridUGraph& graph;
409 /// \brief Map to get the row of the nodes.
411 /// Map to get the row of the nodes.
414 /// \brief The key type of the map
415 typedef GridUGraph::Node Key;
416 /// \brief The value type of the map
419 /// \brief Constructor
422 RowMap(const GridUGraph& _graph) : graph(_graph) {}
424 /// \brief The subscript operator
426 /// The subscript operator.
427 Value operator[](Key key) const {
428 return graph.row(key);
432 const GridUGraph& graph;
435 /// \brief Map to get the column of the nodes.
437 /// Map to get the column of the nodes.
440 /// \brief The key type of the map
441 typedef GridUGraph::Node Key;
442 /// \brief The value type of the map
445 /// \brief Constructor
448 ColMap(const GridUGraph& _graph) : graph(_graph) {}
450 /// \brief The subscript operator
452 /// The subscript operator.
453 Value operator[](Key key) const {
454 return graph.col(key);
458 const GridUGraph& graph;
461 /// \brief Constructor
464 GridUGraph(int n, int m) { construct(n, m); }
466 /// \brief Resize the graph
468 void resize(int n, int m) {
469 Parent::getNotifier(Edge()).clear();
470 Parent::getNotifier(UEdge()).clear();
471 Parent::getNotifier(Node()).clear();
473 Parent::getNotifier(Node()).build();
474 Parent::getNotifier(UEdge()).build();
475 Parent::getNotifier(Edge()).build();
478 /// \brief Gives back the edge goes down from the node.
480 /// Gives back the edge goes down from the node. If there is not
481 /// outgoing edge then it gives back INVALID.
482 Edge down(Node n) const {
484 return ue != INVALID ? direct(ue, true) : INVALID;
487 /// \brief Gives back the edge goes up from the node.
489 /// Gives back the edge goes up from the node. If there is not
490 /// outgoing edge then it gives back INVALID.
491 Edge up(Node n) const {
493 return ue != INVALID ? direct(ue, false) : INVALID;
496 /// \brief Gives back the edge goes right from the node.
498 /// Gives back the edge goes right from the node. If there is not
499 /// outgoing edge then it gives back INVALID.
500 Edge right(Node n) const {
501 UEdge ue = _right(n);
502 return ue != INVALID ? direct(ue, true) : INVALID;
505 /// \brief Gives back the edge goes left from the node.
507 /// Gives back the edge goes left from the node. If there is not
508 /// outgoing edge then it gives back INVALID.
509 Edge left(Node n) const {
511 return ue != INVALID ? direct(ue, false) : INVALID;
516 /// \brief Index map of the grid graph
518 /// Just returns an IndexMap for the grid graph.
519 GridUGraph::IndexMap indexMap(const GridUGraph& graph) {
520 return GridUGraph::IndexMap(graph);
523 /// \brief Row map of the grid graph
525 /// Just returns a RowMap for the grid graph.
526 GridUGraph::RowMap rowMap(const GridUGraph& graph) {
527 return GridUGraph::RowMap(graph);
530 /// \brief Column map of the grid graph
532 /// Just returns a ColMap for the grid graph.
533 GridUGraph::ColMap colMap(const GridUGraph& graph) {
534 return GridUGraph::ColMap(graph);