# Changeset 354:80a4d0742e98 in lemon-1.2

Ignore:
Timestamp:
11/01/08 19:22:18 (12 years ago)
Branch:
default
Phase:
public
Message:

Improvements related to full graphs (#57)

Files:
2 edited

### Legend:

Unmodified
 r353 #define LEMON_FULL_GRAPH_H #include #include #include ///\ingroup graphs ///\file ///\brief FullDigraph and FullGraph classes. ///\brief FullGraph and FullDigraph classes. namespace lemon { Node target(Arc arc) const { return arc._id % _node_num; } static int id(Node node) { return node._id; } static int id(Arc arc) { return arc._id; } static Node nodeFromId(int id) { return Node(id);} static Arc arcFromId(int id) { return Arc(id);} return prev != INVALID ? arc(s, t) : INVALID; } class Node { /// 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. The digraph is completely static, so you can /// neither add nor delete either arcs or nodes, and it needs just /// 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. /// /// Thus it conforms to the \ref concepts::Digraph "Digraph" concept /// This class conforms to the \ref concepts::Digraph "Digraph" concept /// and it also has an important extra feature that its maps are /// real \ref concepts::ReferenceMap "reference map"s. /// \sa concepts::Digraph. /// /// The \c FullDigraph and \c 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. /// /// \sa FullGraph /// \brief Constructor /// /// Constructor. /// \param n The number of the nodes. FullDigraph(int n) { construct(n); } /// \brief Resize the digraph /// /// Resize the digraph. The function will fully destroy and /// rebuild the digraph.  This cause that the maps of the digraph /// will reallocated automatically and the previous values will be /// lost. /// \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 /// reallocated automatically and the previous values will be lost. void resize(int n) { Parent::notifier(Arc()).clear(); /// \brief Returns the node with the given index. /// /// Returns the node with the given index. Because it is a /// static size digraph the node's of the digraph can be indexed /// in the range [0..nodeNum()-1] and the index of /// the node can accessed by the \e index() member. /// 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]. /// \sa index() Node operator()(int ix) const { return Parent::operator()(ix); } /// \brief Returns the index of the node. /// /// Returns the index of the node. Because it is a /// static size digraph the node's of the digraph can be indexed /// in the range [0..nodeNum()-1] and the index of /// the node can accessed by the \e index() member. /// \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); } /// \brief Returns the arc connects the given nodes. /// /// Returns the arc connects the given nodes. /// \brief Returns the arc connecting the given nodes. /// /// Returns the arc connecting the given nodes. Arc arc(const Node& u, const Node& v) const { return Parent::arc(u, v); public: Node operator()(int ix) const { return Node(ix); } class Edge { friend class FullGraphBase; friend class Arc; protected: /// 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 /// n(n-1)/2. It is completely static, so you can neither /// add nor delete either edges or nodes, and it needs just constant /// 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. /// /// The \e FullDigraph and \e FullGraph classes are very similar, /// but there are two differences. While the \e FullDigraph class is /// conform just to the \ref concepts::Digraph "Digraph" concept, /// this class is conform to the \ref concepts::Graph "Graph" /// concept. In addition, the \e FullGraph class does not contain a /// loop arc from each node as the \e FullDigraph does. /// /// It also has an important extra feature that its maps are real /// \ref concepts::ReferenceMap "reference map"s. /// This class conforms to the \ref concepts::Graph "Graph" concept /// and it also has an important extra feature that its maps are /// real \ref concepts::ReferenceMap "reference map"s. /// /// The \c FullGraph and \c FullDigraph classes are very similar, /// but there are two differences. While the \c FullDigraph class /// 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. /// /// \sa FullDigraph /// \brief Constructor /// /// Constructor. /// \param n The number of the nodes. FullGraph(int n) { construct(n); } /// \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 /// /// Resizes 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. void resize(int n) { Parent::notifier(Arc()).clear(); /// \brief Returns the node with the given index. /// /// Returns the node with the given index. Because it is a static /// size graph the node's of the graph can be indexed in the range /// [0..nodeNum()-1] and the index of the node can /// accessed by the \e index() member. /// 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]. /// \sa index() Node operator()(int ix) const { return Parent::operator()(ix); } /// \brief Returns the index of the node. /// /// Returns the index of the node. Because it is a static size /// graph the node's of the graph can be indexed in the range /// [0..nodeNum()-1] and the index of the node can /// accessed by the \e index() member. /// \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); } /// \brief Returns the arc connecting the given nodes. /// /// Returns the arc connecting the given nodes. Arc arc(const Node& s, const 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 { return Parent::edge(u, v); } /// \brief Number of nodes. int edgeNum() const { return Parent::edgeNum(); } /// \brief Returns the arc connects the given nodes. /// /// Returns the arc connects the given nodes. Arc arc(const Node& s, const 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 { return Parent::edge(u, v); } };