GridGraph Class Reference

Detailed Description

GridGraph implements a special graph type. The nodes of the graph can be indexed by two integer values (i,j) where i is in the range [0..width()-1] and j is in the range [0..height()-1]. Two nodes are connected in the graph if the indices differ exactly on one position and the difference is also exactly one. The nodes of the graph can be obtained by position using the operator()() function and the indices of the nodes can be obtained using pos(), col() and row() members. The outgoing arcs can be retrieved with the right(), up(), left() and down() functions, where the bottom-left corner is the origin.

This class is completely static and it needs constant memory space. Thus you can neither add nor delete nodes or edges, however the structure can be resized using resize().

A short example about the basic usage:

GridGraph graph(rows, cols);
GridGraph::NodeMap<int> val(graph);
for (int i = 0; i < graph.width(); ++i) {
  for (int j = 0; j < graph.height(); ++j) {
    val[graph(i, j)] = i + j;
  }
}

This type fully conforms to the Graph concept. Most of its member functions and nested classes are documented only in the concept class.

This class provides constant time counting for nodes, edges and arcs.

#include <lemon/grid_graph.h>

Inherits GraphExtender< Base >.

Classes
class	ColMap
class	IndexMap
class	RowMap

Public Member Functions
	GridGraph (int width, int height)
	Constructor.
void	resize (int width, int height)
	Resizes the graph.
Node	operator() (int i, int j) const
	The node on the given position.
int	col (Node n) const
	The column index of the node.
int	row (Node n) const
	The row index of the node.
dim2::Point< int >	pos (Node n) const
	The position of the node.
int	width () const
	The number of the columns.
int	height () const
	The number of the rows.
Arc	right (Node n) const
	The arc goes right from the node.
Arc	left (Node n) const
	The arc goes left from the node.
Arc	up (Node n) const
	The arc goes up from the node.
Arc	down (Node n) const
	The arc goes down from the node.
IndexMap	indexMap () const
	Index map of the grid graph.
RowMap	rowMap () const
	Row map of the grid graph.
ColMap	colMap () const
	Column map of the grid graph.

Constructor & Destructor Documentation

GridGraph ( int  width, int  height  )

inline

Construct a grid graph with the given size.

Member Function Documentation

void resize ( int  width, int  height  )

inline

This function resizes the graph. It fully destroys and rebuilds the structure, therefore the maps of the graph will be reallocated automatically and the previous values will be lost.

Node operator() ( int  i, int  j  ) const

inline

Gives back the node on the given position.

int col ( Node  n ) const

inline

Gives back the column index of the node.

int row ( Node  n ) const

inline

Gives back the row index of the node.

dim2::Point<int> pos ( Node  n ) const

inline

Gives back the position of the node, ie. the (col,row) pair.

int width ( ) const

inline

Gives back the number of the columns.

int height ( ) const

inline

Gives back the number of the rows.

Arc right ( Node  n ) const

inline

Gives back the arc goes right from the node. If there is not outgoing arc then it gives back INVALID.

Arc left ( Node  n ) const

inline

Gives back the arc goes left from the node. If there is not outgoing arc then it gives back INVALID.

Arc up ( Node  n ) const

inline

Gives back the arc goes up from the node. If there is not outgoing arc then it gives back INVALID.

Arc down ( Node  n ) const

inline

Gives back the arc goes down from the node. If there is not outgoing arc then it gives back INVALID.

IndexMap indexMap ( ) const

inline

Just returns an IndexMap for the grid graph.

RowMap rowMap ( ) const

inline

Just returns a RowMap for the grid graph.

ColMap colMap ( ) const

inline

Just returns a ColMap for the grid graph.