lemon/grid_graph.h
changeset 785 9ae88e7c04a7
parent 617 4137ef9aacc6
child 787 c2230649a493
equal deleted inserted replaced
8:d50e532081a7 9:f1dda056d0ff
   468 
   468 
   469   /// \ingroup graphs
   469   /// \ingroup graphs
   470   ///
   470   ///
   471   /// \brief Grid graph class
   471   /// \brief Grid graph class
   472   ///
   472   ///
   473   /// This class implements a special graph type. The nodes of the
   473   /// GridGraph implements a special graph type. The nodes of the
   474   /// graph can be indexed by two integer \c (i,j) value where \c i is
   474   /// graph can be indexed by two integer values \c (i,j) where \c i is
   475   /// in the \c [0..width()-1] range and j is in the \c
   475   /// in the range <tt>[0..width()-1]</tt> and j is in the range
   476   /// [0..height()-1] range.  Two nodes are connected in the graph if
   476   /// <tt>[0..height()-1]</tt>. Two nodes are connected in the graph if
   477   /// the indexes differ exactly on one position and exactly one is
   477   /// the indices differ exactly on one position and the difference is
   478   /// the difference. The nodes of the graph can be indexed by position
   478   /// also exactly one. The nodes of the graph can be obtained by position
   479   /// with the \c operator()() function. The positions of the nodes can be
   479   /// using the \c operator()() function and the indices of the nodes can
   480   /// get with \c pos(), \c col() and \c row() members. The outgoing
   480   /// be obtained using \c pos(), \c col() and \c row() members. The outgoing
   481   /// arcs can be retrieved with the \c right(), \c up(), \c left()
   481   /// arcs can be retrieved with the \c right(), \c up(), \c left()
   482   /// and \c down() functions, where the bottom-left corner is the
   482   /// and \c down() functions, where the bottom-left corner is the
   483   /// origin.
   483   /// origin.
       
   484   ///
       
   485   /// This class is completely static and it needs constant memory space.
       
   486   /// Thus you can neither add nor delete nodes or edges, however
       
   487   /// the structure can be resized using resize().
   484   ///
   488   ///
   485   /// \image html grid_graph.png
   489   /// \image html grid_graph.png
   486   /// \image latex grid_graph.eps "Grid graph" width=\textwidth
   490   /// \image latex grid_graph.eps "Grid graph" width=\textwidth
   487   ///
   491   ///
   488   /// A short example about the basic usage:
   492   /// A short example about the basic usage:
   494   ///     val[graph(i, j)] = i + j;
   498   ///     val[graph(i, j)] = i + j;
   495   ///   }
   499   ///   }
   496   /// }
   500   /// }
   497   ///\endcode
   501   ///\endcode
   498   ///
   502   ///
   499   /// This graph type fully conforms to the \ref concepts::Graph
   503   /// This type fully conforms to the \ref concepts::Graph "Graph concept".
   500   /// "Graph concept".
   504   /// Most of its member functions and nested classes are documented
       
   505   /// only in the concept class.
   501   class GridGraph : public ExtendedGridGraphBase {
   506   class GridGraph : public ExtendedGridGraphBase {
   502     typedef ExtendedGridGraphBase Parent;
   507     typedef ExtendedGridGraphBase Parent;
   503 
   508 
   504   public:
   509   public:
   505 
   510 
   506     /// \brief Map to get the indices of the nodes as dim2::Point<int>.
   511     /// \brief Map to get the indices of the nodes as \ref dim2::Point
   507     ///
   512     /// "dim2::Point<int>".
   508     /// Map to get the indices of the nodes as dim2::Point<int>.
   513     ///
       
   514     /// Map to get the indices of the nodes as \ref dim2::Point
       
   515     /// "dim2::Point<int>".
   509     class IndexMap {
   516     class IndexMap {
   510     public:
   517     public:
   511       /// \brief The key type of the map
   518       /// \brief The key type of the map
   512       typedef GridGraph::Node Key;
   519       typedef GridGraph::Node Key;
   513       /// \brief The value type of the map
   520       /// \brief The value type of the map
   514       typedef dim2::Point<int> Value;
   521       typedef dim2::Point<int> Value;
   515 
   522 
   516       /// \brief Constructor
   523       /// \brief Constructor
   517       ///
       
   518       /// Constructor
       
   519       IndexMap(const GridGraph& graph) : _graph(graph) {}
   524       IndexMap(const GridGraph& graph) : _graph(graph) {}
   520 
   525 
   521       /// \brief The subscript operator
   526       /// \brief The subscript operator
   522       ///
       
   523       /// The subscript operator.
       
   524       Value operator[](Key key) const {
   527       Value operator[](Key key) const {
   525         return _graph.pos(key);
   528         return _graph.pos(key);
   526       }
   529       }
   527 
   530 
   528     private:
   531     private:
   538       typedef GridGraph::Node Key;
   541       typedef GridGraph::Node Key;
   539       /// \brief The value type of the map
   542       /// \brief The value type of the map
   540       typedef int Value;
   543       typedef int Value;
   541 
   544 
   542       /// \brief Constructor
   545       /// \brief Constructor
   543       ///
       
   544       /// Constructor
       
   545       ColMap(const GridGraph& graph) : _graph(graph) {}
   546       ColMap(const GridGraph& graph) : _graph(graph) {}
   546 
   547 
   547       /// \brief The subscript operator
   548       /// \brief The subscript operator
   548       ///
       
   549       /// The subscript operator.
       
   550       Value operator[](Key key) const {
   549       Value operator[](Key key) const {
   551         return _graph.col(key);
   550         return _graph.col(key);
   552       }
   551       }
   553 
   552 
   554     private:
   553     private:
   564       typedef GridGraph::Node Key;
   563       typedef GridGraph::Node Key;
   565       /// \brief The value type of the map
   564       /// \brief The value type of the map
   566       typedef int Value;
   565       typedef int Value;
   567 
   566 
   568       /// \brief Constructor
   567       /// \brief Constructor
   569       ///
       
   570       /// Constructor
       
   571       RowMap(const GridGraph& graph) : _graph(graph) {}
   568       RowMap(const GridGraph& graph) : _graph(graph) {}
   572 
   569 
   573       /// \brief The subscript operator
   570       /// \brief The subscript operator
   574       ///
       
   575       /// The subscript operator.
       
   576       Value operator[](Key key) const {
   571       Value operator[](Key key) const {
   577         return _graph.row(key);
   572         return _graph.row(key);
   578       }
   573       }
   579 
   574 
   580     private:
   575     private:
   581       const GridGraph& _graph;
   576       const GridGraph& _graph;
   582     };
   577     };
   583 
   578 
   584     /// \brief Constructor
   579     /// \brief Constructor
   585     ///
   580     ///
   586     /// Construct a grid graph with given size.
   581     /// Construct a grid graph with the given size.
   587     GridGraph(int width, int height) { construct(width, height); }
   582     GridGraph(int width, int height) { construct(width, height); }
   588 
   583 
   589     /// \brief Resize the graph
   584     /// \brief Resizes the graph
   590     ///
   585     ///
   591     /// Resize the graph. The function will fully destroy and rebuild
   586     /// This function resizes the graph. It fully destroys and
   592     /// the graph.  This cause that the maps of the graph will
   587     /// rebuilds the structure, therefore the maps of the graph will be
   593     /// reallocated automatically and the previous values will be
   588     /// reallocated automatically and the previous values will be lost.
   594     /// lost.
       
   595     void resize(int width, int height) {
   589     void resize(int width, int height) {
   596       Parent::notifier(Arc()).clear();
   590       Parent::notifier(Arc()).clear();
   597       Parent::notifier(Edge()).clear();
   591       Parent::notifier(Edge()).clear();
   598       Parent::notifier(Node()).clear();
   592       Parent::notifier(Node()).clear();
   599       construct(width, height);
   593       construct(width, height);
   607     /// Gives back the node on the given position.
   601     /// Gives back the node on the given position.
   608     Node operator()(int i, int j) const {
   602     Node operator()(int i, int j) const {
   609       return Parent::operator()(i, j);
   603       return Parent::operator()(i, j);
   610     }
   604     }
   611 
   605 
   612     /// \brief Gives back the column index of the node.
   606     /// \brief The column index of the node.
   613     ///
   607     ///
   614     /// Gives back the column index of the node.
   608     /// Gives back the column index of the node.
   615     int col(Node n) const {
   609     int col(Node n) const {
   616       return Parent::col(n);
   610       return Parent::col(n);
   617     }
   611     }
   618 
   612 
   619     /// \brief Gives back the row index of the node.
   613     /// \brief The row index of the node.
   620     ///
   614     ///
   621     /// Gives back the row index of the node.
   615     /// Gives back the row index of the node.
   622     int row(Node n) const {
   616     int row(Node n) const {
   623       return Parent::row(n);
   617       return Parent::row(n);
   624     }
   618     }
   625 
   619 
   626     /// \brief Gives back the position of the node.
   620     /// \brief The position of the node.
   627     ///
   621     ///
   628     /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair.
   622     /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair.
   629     dim2::Point<int> pos(Node n) const {
   623     dim2::Point<int> pos(Node n) const {
   630       return Parent::pos(n);
   624       return Parent::pos(n);
   631     }
   625     }
   632 
   626 
   633     /// \brief Gives back the number of the columns.
   627     /// \brief The number of the columns.
   634     ///
   628     ///
   635     /// Gives back the number of the columns.
   629     /// Gives back the number of the columns.
   636     int width() const {
   630     int width() const {
   637       return Parent::width();
   631       return Parent::width();
   638     }
   632     }
   639 
   633 
   640     /// \brief Gives back the number of the rows.
   634     /// \brief The number of the rows.
   641     ///
   635     ///
   642     /// Gives back the number of the rows.
   636     /// Gives back the number of the rows.
   643     int height() const {
   637     int height() const {
   644       return Parent::height();
   638       return Parent::height();
   645     }
   639     }
   646 
   640 
   647     /// \brief Gives back the arc goes right from the node.
   641     /// \brief The arc goes right from the node.
   648     ///
   642     ///
   649     /// Gives back the arc goes right from the node. If there is not
   643     /// Gives back the arc goes right from the node. If there is not
   650     /// outgoing arc then it gives back INVALID.
   644     /// outgoing arc then it gives back INVALID.
   651     Arc right(Node n) const {
   645     Arc right(Node n) const {
   652       return Parent::right(n);
   646       return Parent::right(n);
   653     }
   647     }
   654 
   648 
   655     /// \brief Gives back the arc goes left from the node.
   649     /// \brief The arc goes left from the node.
   656     ///
   650     ///
   657     /// Gives back the arc goes left from the node. If there is not
   651     /// Gives back the arc goes left from the node. If there is not
   658     /// outgoing arc then it gives back INVALID.
   652     /// outgoing arc then it gives back INVALID.
   659     Arc left(Node n) const {
   653     Arc left(Node n) const {
   660       return Parent::left(n);
   654       return Parent::left(n);
   661     }
   655     }
   662 
   656 
   663     /// \brief Gives back the arc goes up from the node.
   657     /// \brief The arc goes up from the node.
   664     ///
   658     ///
   665     /// Gives back the arc goes up from the node. If there is not
   659     /// Gives back the arc goes up from the node. If there is not
   666     /// outgoing arc then it gives back INVALID.
   660     /// outgoing arc then it gives back INVALID.
   667     Arc up(Node n) const {
   661     Arc up(Node n) const {
   668       return Parent::up(n);
   662       return Parent::up(n);
   669     }
   663     }
   670 
   664 
   671     /// \brief Gives back the arc goes down from the node.
   665     /// \brief The arc goes down from the node.
   672     ///
   666     ///
   673     /// Gives back the arc goes down from the node. If there is not
   667     /// Gives back the arc goes down from the node. If there is not
   674     /// outgoing arc then it gives back INVALID.
   668     /// outgoing arc then it gives back INVALID.
   675     Arc down(Node n) const {
   669     Arc down(Node n) const {
   676       return Parent::down(n);
   670       return Parent::down(n);