GridGraph

Declared in lemon/grid_graph.h, in the group Graph Structures; the same class on the Doxygen site.

class GridGraph : public GraphExtender< GridGraphBase >

Grid graph class.

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().

../_images/grid_graph.png

A short example about the basic usage:

GridGraph graph( width , height );
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.

Public Functions

inline GridGraph( int width , int height )

Constructor.

Construct a grid graph with the given size.

inline void resize( int width , int height )

Resizes the graph.

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.

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

The node on the given position.

Gives back the node on the given position.

inline int col( Node n ) const

The column index of the node.

Gives back the column index of the node.

inline int row( Node n ) const

The row index of the node.

Gives back the row index of the node.

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

The position of the node.

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

inline int width() const

The number of the columns.

Gives back the number of the columns.

inline int height() const

The number of the rows.

Gives back the number of the rows.

inline Arc right( Node n ) const

The arc goes right from the node.

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

inline Arc left( Node n ) const

The arc goes left from the node.

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

inline Arc up( Node n ) const

The arc goes up from the node.

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

inline Arc down( Node n ) const

The arc goes down from the node.

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

inline IndexMap indexMap() const

Index map of the grid graph.

Just returns an IndexMap for the grid graph.

inline RowMap rowMap() const

Row map of the grid graph.

Just returns a RowMap for the grid graph.

inline ColMap colMap() const

Column map of the grid graph.

Just returns a ColMap for the grid graph.

class IndexMap

Map to get the indices of the nodes as dim2::Point< int >.

Public Types

typedef GridGraph::Node Key

The key type of the map.

typedef dim2::Point< int > Value

The value type of the map.

Public Functions

inline IndexMap( const GridGraph & graph )

Constructor.

inline Value operator[]( Key key ) const

The subscript operator.

class ColMap

Map to get the column of the nodes.

Public Types

typedef GridGraph::Node Key

The key type of the map.

typedef int Value

The value type of the map.

Public Functions

inline ColMap( const GridGraph & graph )

Constructor.

inline Value operator[]( Key key ) const

The subscript operator.

class RowMap

Map to get the row of the nodes.

Public Types

typedef GridGraph::Node Key

The key type of the map.

typedef int Value

The value type of the map.

Public Functions

inline RowMap( const GridGraph & graph )

Constructor.

inline Value operator[]( Key key ) const

The subscript operator.