146 |
146 |
147 typedef DigraphExtender<FullDigraphBase> ExtendedFullDigraphBase; |
147 typedef DigraphExtender<FullDigraphBase> ExtendedFullDigraphBase; |
148 |
148 |
149 /// \ingroup graphs |
149 /// \ingroup graphs |
150 /// |
150 /// |
151 /// \brief A full digraph class. |
151 /// \brief A directed full graph class. |
152 /// |
152 /// |
153 /// This is a simple and fast directed full graph implementation. |
153 /// FullDigraph is a simple and fast implmenetation of directed full |
154 /// From each node go arcs to each node (including the source node), |
154 /// (complete) graphs. It contains an arc from each node to each node |
155 /// therefore the number of the arcs in the digraph is the square of |
155 /// (including a loop for each node), therefore the number of arcs |
156 /// the node number. This digraph type is completely static, so you |
156 /// is the square of the number of nodes. |
157 /// can neither add nor delete either arcs or nodes, and it needs |
157 /// This class is completely static and it needs constant memory space. |
158 /// constant space in memory. |
158 /// Thus you can neither add nor delete nodes or arcs, however |
159 /// |
159 /// the structure can be resized using resize(). |
160 /// This class fully conforms to the \ref concepts::Digraph |
160 /// |
161 /// "Digraph concept". |
161 /// This type fully conforms to the \ref concepts::Digraph "Digraph concept". |
162 /// |
162 /// Most of its member functions and nested classes are documented |
163 /// The \c FullDigraph and \c FullGraph classes are very similar, |
163 /// only in the concept class. |
|
164 /// |
|
165 /// \note FullDigraph and FullGraph classes are very similar, |
164 /// but there are two differences. While this class conforms only |
166 /// but there are two differences. While this class conforms only |
165 /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph |
167 /// to the \ref concepts::Digraph "Digraph" concept, FullGraph |
166 /// class conforms to the \ref concepts::Graph "Graph" concept, |
168 /// conforms to the \ref concepts::Graph "Graph" concept, |
167 /// moreover \c FullGraph does not contain a loop arc for each |
169 /// moreover FullGraph does not contain a loop for each |
168 /// node as \c FullDigraph does. |
170 /// node as this class does. |
169 /// |
171 /// |
170 /// \sa FullGraph |
172 /// \sa FullGraph |
171 class FullDigraph : public ExtendedFullDigraphBase { |
173 class FullDigraph : public ExtendedFullDigraphBase { |
172 typedef ExtendedFullDigraphBase Parent; |
174 typedef ExtendedFullDigraphBase Parent; |
173 |
175 |
174 public: |
176 public: |
175 |
177 |
176 /// \brief Constructor |
178 /// \brief Default constructor. |
|
179 /// |
|
180 /// Default constructor. The number of nodes and arcs will be zero. |
177 FullDigraph() { construct(0); } |
181 FullDigraph() { construct(0); } |
178 |
182 |
179 /// \brief Constructor |
183 /// \brief Constructor |
180 /// |
184 /// |
181 /// Constructor. |
185 /// Constructor. |
182 /// \param n The number of the nodes. |
186 /// \param n The number of the nodes. |
183 FullDigraph(int n) { construct(n); } |
187 FullDigraph(int n) { construct(n); } |
184 |
188 |
185 /// \brief Resizes the digraph |
189 /// \brief Resizes the digraph |
186 /// |
190 /// |
187 /// Resizes the digraph. The function will fully destroy and |
191 /// This function resizes the digraph. It fully destroys and |
188 /// rebuild the digraph. This cause that the maps of the digraph will |
192 /// rebuilds the structure, therefore the maps of the digraph will be |
189 /// reallocated automatically and the previous values will be lost. |
193 /// reallocated automatically and the previous values will be lost. |
190 void resize(int n) { |
194 void resize(int n) { |
191 Parent::notifier(Arc()).clear(); |
195 Parent::notifier(Arc()).clear(); |
192 Parent::notifier(Node()).clear(); |
196 Parent::notifier(Node()).clear(); |
193 construct(n); |
197 construct(n); |
195 Parent::notifier(Arc()).build(); |
199 Parent::notifier(Arc()).build(); |
196 } |
200 } |
197 |
201 |
198 /// \brief Returns the node with the given index. |
202 /// \brief Returns the node with the given index. |
199 /// |
203 /// |
200 /// Returns the node with the given index. Since it is a static |
204 /// Returns the node with the given index. Since this structure is |
201 /// digraph its nodes can be indexed with integers from the range |
205 /// completely static, the nodes can be indexed with integers from |
202 /// <tt>[0..nodeNum()-1]</tt>. |
206 /// the range <tt>[0..nodeNum()-1]</tt>. |
203 /// \sa index() |
207 /// \sa index() |
204 Node operator()(int ix) const { return Parent::operator()(ix); } |
208 Node operator()(int ix) const { return Parent::operator()(ix); } |
205 |
209 |
206 /// \brief Returns the index of the given node. |
210 /// \brief Returns the index of the given node. |
207 /// |
211 /// |
208 /// Returns the index of the given node. Since it is a static |
212 /// Returns the index of the given node. Since this structure is |
209 /// digraph its nodes can be indexed with integers from the range |
213 /// completely static, the nodes can be indexed with integers from |
210 /// <tt>[0..nodeNum()-1]</tt>. |
214 /// the range <tt>[0..nodeNum()-1]</tt>. |
211 /// \sa operator() |
215 /// \sa operator()() |
212 int index(const Node& node) const { return Parent::index(node); } |
216 int index(Node node) const { return Parent::index(node); } |
213 |
217 |
214 /// \brief Returns the arc connecting the given nodes. |
218 /// \brief Returns the arc connecting the given nodes. |
215 /// |
219 /// |
216 /// Returns the arc connecting the given nodes. |
220 /// Returns the arc connecting the given nodes. |
217 Arc arc(const Node& u, const Node& v) const { |
221 Arc arc(Node u, Node v) const { |
218 return Parent::arc(u, v); |
222 return Parent::arc(u, v); |
219 } |
223 } |
220 |
224 |
221 /// \brief Number of nodes. |
225 /// \brief Number of nodes. |
222 int nodeNum() const { return Parent::nodeNum(); } |
226 int nodeNum() const { return Parent::nodeNum(); } |
518 |
522 |
519 /// \ingroup graphs |
523 /// \ingroup graphs |
520 /// |
524 /// |
521 /// \brief An undirected full graph class. |
525 /// \brief An undirected full graph class. |
522 /// |
526 /// |
523 /// This is a simple and fast undirected full graph |
527 /// FullGraph is a simple and fast implmenetation of undirected full |
524 /// implementation. From each node go edge to each other node, |
528 /// (complete) graphs. It contains an edge between every distinct pair |
525 /// therefore the number of edges in the graph is \f$n(n-1)/2\f$. |
529 /// of nodes, therefore the number of edges is <tt>n(n-1)/2</tt>. |
526 /// This graph type is completely static, so you can neither |
530 /// This class is completely static and it needs constant memory space. |
527 /// add nor delete either edges or nodes, and it needs constant |
531 /// Thus you can neither add nor delete nodes or edges, however |
528 /// space in memory. |
532 /// the structure can be resized using resize(). |
529 /// |
533 /// |
530 /// This class fully conforms to the \ref concepts::Graph "Graph concept". |
534 /// This type fully conforms to the \ref concepts::Graph "Graph concept". |
531 /// |
535 /// Most of its member functions and nested classes are documented |
532 /// The \c FullGraph and \c FullDigraph classes are very similar, |
536 /// only in the concept class. |
533 /// but there are two differences. While the \c FullDigraph class |
537 /// |
|
538 /// \note FullDigraph and FullGraph classes are very similar, |
|
539 /// but there are two differences. While FullDigraph |
534 /// conforms only to the \ref concepts::Digraph "Digraph" concept, |
540 /// conforms only to the \ref concepts::Digraph "Digraph" concept, |
535 /// this class conforms to the \ref concepts::Graph "Graph" concept, |
541 /// this class conforms to the \ref concepts::Graph "Graph" concept, |
536 /// moreover \c FullGraph does not contain a loop arc for each |
542 /// moreover this class does not contain a loop for each |
537 /// node as \c FullDigraph does. |
543 /// node as FullDigraph does. |
538 /// |
544 /// |
539 /// \sa FullDigraph |
545 /// \sa FullDigraph |
540 class FullGraph : public ExtendedFullGraphBase { |
546 class FullGraph : public ExtendedFullGraphBase { |
541 typedef ExtendedFullGraphBase Parent; |
547 typedef ExtendedFullGraphBase Parent; |
542 |
548 |
543 public: |
549 public: |
544 |
550 |
545 /// \brief Constructor |
551 /// \brief Default constructor. |
|
552 /// |
|
553 /// Default constructor. The number of nodes and edges will be zero. |
546 FullGraph() { construct(0); } |
554 FullGraph() { construct(0); } |
547 |
555 |
548 /// \brief Constructor |
556 /// \brief Constructor |
549 /// |
557 /// |
550 /// Constructor. |
558 /// Constructor. |
551 /// \param n The number of the nodes. |
559 /// \param n The number of the nodes. |
552 FullGraph(int n) { construct(n); } |
560 FullGraph(int n) { construct(n); } |
553 |
561 |
554 /// \brief Resizes the graph |
562 /// \brief Resizes the graph |
555 /// |
563 /// |
556 /// Resizes the graph. The function will fully destroy and |
564 /// This function resizes the graph. It fully destroys and |
557 /// rebuild the graph. This cause that the maps of the graph will |
565 /// rebuilds the structure, therefore the maps of the graph will be |
558 /// reallocated automatically and the previous values will be lost. |
566 /// reallocated automatically and the previous values will be lost. |
559 void resize(int n) { |
567 void resize(int n) { |
560 Parent::notifier(Arc()).clear(); |
568 Parent::notifier(Arc()).clear(); |
561 Parent::notifier(Edge()).clear(); |
569 Parent::notifier(Edge()).clear(); |
562 Parent::notifier(Node()).clear(); |
570 Parent::notifier(Node()).clear(); |
566 Parent::notifier(Arc()).build(); |
574 Parent::notifier(Arc()).build(); |
567 } |
575 } |
568 |
576 |
569 /// \brief Returns the node with the given index. |
577 /// \brief Returns the node with the given index. |
570 /// |
578 /// |
571 /// Returns the node with the given index. Since it is a static |
579 /// Returns the node with the given index. Since this structure is |
572 /// graph its nodes can be indexed with integers from the range |
580 /// completely static, the nodes can be indexed with integers from |
573 /// <tt>[0..nodeNum()-1]</tt>. |
581 /// the range <tt>[0..nodeNum()-1]</tt>. |
574 /// \sa index() |
582 /// \sa index() |
575 Node operator()(int ix) const { return Parent::operator()(ix); } |
583 Node operator()(int ix) const { return Parent::operator()(ix); } |
576 |
584 |
577 /// \brief Returns the index of the given node. |
585 /// \brief Returns the index of the given node. |
578 /// |
586 /// |
579 /// Returns the index of the given node. Since it is a static |
587 /// Returns the index of the given node. Since this structure is |
580 /// graph its nodes can be indexed with integers from the range |
588 /// completely static, the nodes can be indexed with integers from |
581 /// <tt>[0..nodeNum()-1]</tt>. |
589 /// the range <tt>[0..nodeNum()-1]</tt>. |
582 /// \sa operator() |
590 /// \sa operator()() |
583 int index(const Node& node) const { return Parent::index(node); } |
591 int index(Node node) const { return Parent::index(node); } |
584 |
592 |
585 /// \brief Returns the arc connecting the given nodes. |
593 /// \brief Returns the arc connecting the given nodes. |
586 /// |
594 /// |
587 /// Returns the arc connecting the given nodes. |
595 /// Returns the arc connecting the given nodes. |
588 Arc arc(const Node& s, const Node& t) const { |
596 Arc arc(Node s, Node t) const { |
589 return Parent::arc(s, t); |
597 return Parent::arc(s, t); |
590 } |
598 } |
591 |
599 |
592 /// \brief Returns the edge connects the given nodes. |
600 /// \brief Returns the edge connecting the given nodes. |
593 /// |
601 /// |
594 /// Returns the edge connects the given nodes. |
602 /// Returns the edge connecting the given nodes. |
595 Edge edge(const Node& u, const Node& v) const { |
603 Edge edge(Node u, Node v) const { |
596 return Parent::edge(u, v); |
604 return Parent::edge(u, v); |
597 } |
605 } |
598 |
606 |
599 /// \brief Number of nodes. |
607 /// \brief Number of nodes. |
600 int nodeNum() const { return Parent::nodeNum(); } |
608 int nodeNum() const { return Parent::nodeNum(); } |