# Changeset 735:853fcddcf282 in lemon-1.2 for lemon

Ignore:
Timestamp:
08/23/09 11:09:22 (11 years ago)
Branch:
default
Phase:
public
Message:

Doc improvements, fixes and unifications for graphs (#311)

Location:
lemon
Files:
5 edited

Unmodified
Removed
• ## lemon/full_graph.h

 r617 ///\ingroup graphs ///\file ///\brief FullGraph and FullDigraph classes. ///\brief FullDigraph and FullGraph classes. namespace lemon { /// \ingroup graphs /// /// \brief A full digraph class. /// /// This is a simple and fast directed full graph implementation. /// From each node go arcs to each node (including the source node), /// therefore the number of the arcs in the digraph is the square of /// the node number. This digraph type is completely static, so you /// can neither add nor delete either arcs or nodes, and it needs /// constant space in memory. /// /// This class fully conforms to the \ref concepts::Digraph /// "Digraph concept". /// /// The \c FullDigraph and \c FullGraph classes are very similar, /// \brief A directed full graph class. /// /// FullDigraph is a simple and fast implmenetation of directed full /// (complete) graphs. It contains an arc from each node to each node /// (including a loop for each node), therefore the number of arcs /// is the square of the number of nodes. /// This class is completely static and it needs constant memory space. /// Thus you can neither add nor delete nodes or arcs, however /// the structure can be resized using resize(). /// /// This type fully conforms to the \ref concepts::Digraph "Digraph concept". /// Most of its member functions and nested classes are documented /// only in the concept class. /// /// \note FullDigraph and FullGraph classes are very similar, /// but there are two differences. While this class conforms only /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph /// class conforms to the \ref concepts::Graph "Graph" concept, /// moreover \c FullGraph does not contain a loop arc for each /// node as \c FullDigraph does. /// to the \ref concepts::Digraph "Digraph" concept, FullGraph /// conforms to the \ref concepts::Graph "Graph" concept, /// moreover FullGraph does not contain a loop for each /// node as this class does. /// /// \sa FullGraph public: /// \brief Constructor /// \brief Default constructor. /// /// Default constructor. The number of nodes and arcs will be zero. FullDigraph() { construct(0); } /// \brief Resizes the digraph /// /// Resizes the digraph. The function will fully destroy and /// rebuild the digraph. This cause that the maps of the digraph will /// This function resizes the digraph. It fully destroys and /// rebuilds the structure, therefore the maps of the digraph will be /// reallocated automatically and the previous values will be lost. void resize(int n) { /// \brief Returns the node with the given index. /// /// Returns the node with the given index. Since it is a static /// digraph its nodes can be indexed with integers from the range /// [0..nodeNum()-1]. /// Returns the node with the given index. Since this structure is /// completely static, the nodes can be indexed with integers from /// the range [0..nodeNum()-1]. /// \sa index() Node operator()(int ix) const { return Parent::operator()(ix); } /// \brief Returns the index of the given node. /// /// Returns the index of the given node. Since it is a static /// digraph its nodes can be indexed with integers from the range /// [0..nodeNum()-1]. /// \sa operator() int index(const Node& node) const { return Parent::index(node); } /// Returns the index of the given node. Since this structure is /// completely static, the nodes can be indexed with integers from /// the range [0..nodeNum()-1]. /// \sa operator()() int index(Node node) const { return Parent::index(node); } /// \brief Returns the arc connecting the given nodes. /// /// Returns the arc connecting the given nodes. Arc arc(const Node& u, const Node& v) const { Arc arc(Node u, Node v) const { return Parent::arc(u, v); } /// \brief An undirected full graph class. /// /// This is a simple and fast undirected full graph /// implementation. From each node go edge to each other node, /// therefore the number of edges in the graph is \f$n(n-1)/2\f$. /// This graph type is completely static, so you can neither /// add nor delete either edges or nodes, and it needs constant /// space in memory. /// /// This class fully conforms to the \ref concepts::Graph "Graph concept". /// /// The \c FullGraph and \c FullDigraph classes are very similar, /// but there are two differences. While the \c FullDigraph class /// FullGraph is a simple and fast implmenetation of undirected full /// (complete) graphs. It contains an edge between every distinct pair /// of nodes, therefore the number of edges is n(n-1)/2. /// 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(). /// /// This type fully conforms to the \ref concepts::Graph "Graph concept". /// Most of its member functions and nested classes are documented /// only in the concept class. /// /// \note FullDigraph and FullGraph classes are very similar, /// but there are two differences. While FullDigraph /// conforms only to the \ref concepts::Digraph "Digraph" concept, /// this class conforms to the \ref concepts::Graph "Graph" concept, /// moreover \c FullGraph does not contain a loop arc for each /// node as \c FullDigraph does. /// moreover this class does not contain a loop for each /// node as FullDigraph does. /// /// \sa FullDigraph public: /// \brief Constructor /// \brief Default constructor. /// /// Default constructor. The number of nodes and edges will be zero. FullGraph() { construct(0); } /// \brief Resizes the graph /// /// Resizes the graph. The function will fully destroy and /// rebuild the graph. This cause that the maps of the graph will /// 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. void resize(int n) { /// \brief Returns the node with the given index. /// /// Returns the node with the given index. Since it is a static /// graph its nodes can be indexed with integers from the range /// [0..nodeNum()-1]. /// Returns the node with the given index. Since this structure is /// completely static, the nodes can be indexed with integers from /// the range [0..nodeNum()-1]. /// \sa index() Node operator()(int ix) const { return Parent::operator()(ix); } /// \brief Returns the index of the given node. /// /// Returns the index of the given node. Since it is a static /// graph its nodes can be indexed with integers from the range /// [0..nodeNum()-1]. /// \sa operator() int index(const Node& node) const { return Parent::index(node); } /// Returns the index of the given node. Since this structure is /// completely static, the nodes can be indexed with integers from /// the range [0..nodeNum()-1]. /// \sa operator()() int index(Node node) const { return Parent::index(node); } /// \brief Returns the arc connecting the given nodes. /// /// Returns the arc connecting the given nodes. Arc arc(const Node& s, const Node& t) const { Arc arc(Node s, Node t) const { return Parent::arc(s, t); } /// \brief Returns the edge connects the given nodes. /// /// Returns the edge connects the given nodes. Edge edge(const Node& u, const Node& v) const { /// \brief Returns the edge connecting the given nodes. /// /// Returns the edge connecting the given nodes. Edge edge(Node u, Node v) const { return Parent::edge(u, v); }
• ## lemon/grid_graph.h

 r617 /// \brief Grid graph class /// /// This class implements a special graph type. The nodes of the /// graph can be indexed by two integer \c (i,j) value where \c i is /// in the \c [0..width()-1] range and j is in the \c /// [0..height()-1] range. Two nodes are connected in the graph if /// the indexes differ exactly on one position and exactly one is /// the difference. The nodes of the graph can be indexed by position /// with the \c operator()() function. The positions of the nodes can be /// get with \c pos(), \c col() and \c row() members. The outgoing /// GridGraph implements a special graph type. The nodes of the /// graph can be indexed by two integer values \c (i,j) where \c 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 \c operator()() function and the indices of the nodes can /// be obtained using \c pos(), \c col() and \c row() members. The outgoing /// arcs can be retrieved with the \c right(), \c up(), \c left() /// and \c 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(). /// /// \image html grid_graph.png ///\endcode /// /// This graph type fully conforms to the \ref concepts::Graph /// "Graph concept". /// This type fully conforms to the \ref concepts::Graph "Graph concept". /// Most of its member functions and nested classes are documented /// only in the concept class. class GridGraph : public ExtendedGridGraphBase { typedef ExtendedGridGraphBase Parent; public: /// \brief Map to get the indices of the nodes as dim2::Point. /// /// Map to get the indices of the nodes as dim2::Point. /// \brief Map to get the indices of the nodes as \ref dim2::Point /// "dim2::Point". /// /// Map to get the indices of the nodes as \ref dim2::Point /// "dim2::Point". class IndexMap { public: /// \brief Constructor /// /// Constructor IndexMap(const GridGraph& graph) : _graph(graph) {} /// \brief The subscript operator /// /// The subscript operator. Value operator[](Key key) const { return _graph.pos(key); /// \brief Constructor /// /// Constructor ColMap(const GridGraph& graph) : _graph(graph) {} /// \brief The subscript operator /// /// The subscript operator. Value operator[](Key key) const { return _graph.col(key); /// \brief Constructor /// /// Constructor RowMap(const GridGraph& graph) : _graph(graph) {} /// \brief The subscript operator /// /// The subscript operator. Value operator[](Key key) const { return _graph.row(key); /// \brief Constructor /// /// Construct a grid graph with given size. /// Construct a grid graph with the given size. GridGraph(int width, int height) { construct(width, height); } /// \brief Resize the graph /// /// Resize the graph. The function will fully destroy and rebuild /// the graph.  This cause that the maps of the graph will /// reallocated automatically and the previous values will be /// lost. /// \brief 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. void resize(int width, int height) { Parent::notifier(Arc()).clear(); } /// \brief Gives back the column index of the node. /// \brief The column index of the node. /// /// Gives back the column index of the node. } /// \brief Gives back the row index of the node. /// \brief The row index of the node. /// /// Gives back the row index of the node. } /// \brief Gives back the position of the node. /// \brief The position of the node. /// /// Gives back the position of the node, ie. the (col,row) pair. } /// \brief Gives back the number of the columns. /// \brief The number of the columns. /// /// Gives back the number of the columns. } /// \brief Gives back the number of the rows. /// \brief The number of the rows. /// /// Gives back the number of the rows. } /// \brief Gives back the arc goes right from the node. /// \brief The arc goes right from the node. /// /// Gives back the arc goes right from the node. If there is not } /// \brief Gives back the arc goes left from the node. /// \brief The arc goes left from the node. /// /// Gives back the arc goes left from the node. If there is not } /// \brief Gives back the arc goes up from the node. /// \brief The arc goes up from the node. /// /// Gives back the arc goes up from the node. If there is not } /// \brief Gives back the arc goes down from the node. /// \brief The arc goes down from the node. /// /// Gives back the arc goes down from the node. If there is not
• ## lemon/hypercube_graph.h

 r617 /// \brief Hypercube graph class /// /// This class implements a special graph type. The nodes of the graph /// are indiced with integers with at most \c dim binary digits. /// HypercubeGraph implements a special graph type. The nodes of the /// graph are indexed with integers having at most \c dim binary digits. /// Two nodes are connected in the graph if and only if their indices /// differ only on one position in the binary form. /// This class is completely static and it needs constant memory space. /// Thus you can neither add nor delete nodes or edges. /// /// This type fully conforms to the \ref concepts::Graph "Graph concept". /// Most of its member functions and nested classes are documented /// only in the concept class. /// /// \note The type of the indices is chosen to \c int for efficiency /// reasons. Thus the maximum dimension of this implementation is 26 /// (assuming that the size of \c int is 32 bit). /// /// This graph type fully conforms to the \ref concepts::Graph /// "Graph concept". class HypercubeGraph : public ExtendedHypercubeGraphBase { typedef ExtendedHypercubeGraphBase Parent; /// /// Gives back the dimension id of the given edge. /// It is in the [0..dim-1] range. /// It is in the range [0..dim-1]. int dimension(Edge edge) const { return Parent::dimension(edge); /// /// Gives back the dimension id of the given arc. /// It is in the [0..dim-1] range. /// It is in the range [0..dim-1]. int dimension(Arc arc) const { return Parent::dimension(arc);