65 int maxArcId() const { return _arc_num - 1; } |
64 int maxArcId() const { return _arc_num - 1; } |
66 |
65 |
67 Node source(Arc arc) const { return arc._id / _node_num; } |
66 Node source(Arc arc) const { return arc._id / _node_num; } |
68 Node target(Arc arc) const { return arc._id % _node_num; } |
67 Node target(Arc arc) const { return arc._id % _node_num; } |
69 |
68 |
70 |
|
71 static int id(Node node) { return node._id; } |
69 static int id(Node node) { return node._id; } |
72 static int id(Arc arc) { return arc._id; } |
70 static int id(Arc arc) { return arc._id; } |
73 |
71 |
74 static Node nodeFromId(int id) { return Node(id);} |
72 static Node nodeFromId(int id) { return Node(id);} |
75 |
|
76 static Arc arcFromId(int id) { return Arc(id);} |
73 static Arc arcFromId(int id) { return Arc(id);} |
77 |
74 |
78 typedef True FindArcTag; |
75 typedef True FindArcTag; |
79 |
76 |
80 Arc findArc(Node s, Node t, Arc prev = INVALID) const { |
77 Arc findArc(Node s, Node t, Arc prev = INVALID) const { |
81 return prev != INVALID ? arc(s, t) : INVALID; |
78 return prev != INVALID ? arc(s, t) : INVALID; |
82 } |
79 } |
83 |
|
84 |
80 |
85 class Node { |
81 class Node { |
86 friend class FullDigraphBase; |
82 friend class FullDigraphBase; |
87 |
83 |
88 protected: |
84 protected: |
155 /// \brief A full digraph class. |
151 /// \brief A full digraph class. |
156 /// |
152 /// |
157 /// This is a simple and fast directed full graph implementation. |
153 /// This is a simple and fast directed full graph implementation. |
158 /// From each node go arcs to each node (including the source node), |
154 /// From each node go arcs to each node (including the source node), |
159 /// therefore the number of the arcs in the digraph is the square of |
155 /// therefore the number of the arcs in the digraph is the square of |
160 /// the node number. The digraph is completely static, so you can |
156 /// the node number. This digraph type is completely static, so you |
161 /// neither add nor delete either arcs or nodes, and it needs just |
157 /// can neither add nor delete either arcs or nodes, and it needs |
162 /// constant space in memory. |
158 /// constant space in memory. |
163 /// |
159 /// |
164 /// Thus it conforms to the \ref concepts::Digraph "Digraph" concept |
160 /// This class conforms to the \ref concepts::Digraph "Digraph" concept |
165 /// and it also has an important extra feature that its maps are |
161 /// and it also has an important extra feature that its maps are |
166 /// real \ref concepts::ReferenceMap "reference map"s. |
162 /// real \ref concepts::ReferenceMap "reference map"s. |
167 /// \sa concepts::Digraph. |
163 /// |
|
164 /// The \c FullDigraph and \c FullGraph classes are very similar, |
|
165 /// but there are two differences. While this class conforms only |
|
166 /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph |
|
167 /// class conforms to the \ref concepts::Graph "Graph" concept, |
|
168 /// moreover \c FullGraph does not contain a loop arc for each |
|
169 /// node as \c FullDigraph does. |
168 /// |
170 /// |
169 /// \sa FullGraph |
171 /// \sa FullGraph |
170 class FullDigraph : public ExtendedFullDigraphBase { |
172 class FullDigraph : public ExtendedFullDigraphBase { |
171 public: |
173 public: |
172 |
174 |
175 /// \brief Constructor |
177 /// \brief Constructor |
176 FullDigraph() { construct(0); } |
178 FullDigraph() { construct(0); } |
177 |
179 |
178 /// \brief Constructor |
180 /// \brief Constructor |
179 /// |
181 /// |
|
182 /// Constructor. |
180 /// \param n The number of the nodes. |
183 /// \param n The number of the nodes. |
181 FullDigraph(int n) { construct(n); } |
184 FullDigraph(int n) { construct(n); } |
182 |
185 |
183 /// \brief Resize the digraph |
186 /// \brief Resizes the digraph |
184 /// |
187 /// |
185 /// Resize the digraph. The function will fully destroy and |
188 /// Resizes the digraph. The function will fully destroy and |
186 /// rebuild the digraph. This cause that the maps of the digraph |
189 /// rebuild the digraph. This cause that the maps of the digraph will |
187 /// will reallocated automatically and the previous values will be |
190 /// reallocated automatically and the previous values will be lost. |
188 /// lost. |
|
189 void resize(int n) { |
191 void resize(int n) { |
190 Parent::notifier(Arc()).clear(); |
192 Parent::notifier(Arc()).clear(); |
191 Parent::notifier(Node()).clear(); |
193 Parent::notifier(Node()).clear(); |
192 construct(n); |
194 construct(n); |
193 Parent::notifier(Node()).build(); |
195 Parent::notifier(Node()).build(); |
194 Parent::notifier(Arc()).build(); |
196 Parent::notifier(Arc()).build(); |
195 } |
197 } |
196 |
198 |
197 /// \brief Returns the node with the given index. |
199 /// \brief Returns the node with the given index. |
198 /// |
200 /// |
199 /// Returns the node with the given index. Because it is a |
201 /// Returns the node with the given index. Since it is a static |
200 /// static size digraph the node's of the digraph can be indexed |
202 /// digraph its nodes can be indexed with integers from the range |
201 /// in the range <tt>[0..nodeNum()-1]</tt> and the index of |
203 /// <tt>[0..nodeNum()-1]</tt>. |
202 /// the node can accessed by the \e index() member. |
204 /// \sa index() |
203 Node operator()(int ix) const { return Parent::operator()(ix); } |
205 Node operator()(int ix) const { return Parent::operator()(ix); } |
204 |
206 |
205 /// \brief Returns the index of the node. |
207 /// \brief Returns the index of the given node. |
206 /// |
208 /// |
207 /// Returns the index of the node. Because it is a |
209 /// Returns the index of the given node. Since it is a static |
208 /// static size digraph the node's of the digraph can be indexed |
210 /// digraph its nodes can be indexed with integers from the range |
209 /// in the range <tt>[0..nodeNum()-1]</tt> and the index of |
211 /// <tt>[0..nodeNum()-1]</tt>. |
210 /// the node can accessed by the \e index() member. |
212 /// \sa operator() |
211 int index(const Node& node) const { return Parent::index(node); } |
213 int index(const Node& node) const { return Parent::index(node); } |
212 |
214 |
213 /// \brief Returns the arc connects the given nodes. |
215 /// \brief Returns the arc connecting the given nodes. |
214 /// |
216 /// |
215 /// Returns the arc connects the given nodes. |
217 /// Returns the arc connecting the given nodes. |
216 Arc arc(const Node& u, const Node& v) const { |
218 Arc arc(const Node& u, const Node& v) const { |
217 return Parent::arc(u, v); |
219 return Parent::arc(u, v); |
218 } |
220 } |
219 |
221 |
220 /// \brief Number of nodes. |
222 /// \brief Number of nodes. |
516 /// |
518 /// |
517 /// \brief An undirected full graph class. |
519 /// \brief An undirected full graph class. |
518 /// |
520 /// |
519 /// This is a simple and fast undirected full graph |
521 /// This is a simple and fast undirected full graph |
520 /// implementation. From each node go edge to each other node, |
522 /// implementation. From each node go edge to each other node, |
521 /// therefore the number of edges in the graph is |
523 /// therefore the number of edges in the graph is \f$n(n-1)/2\f$. |
522 /// <tt>n(n-1)/2</tt>. It is completely static, so you can neither |
524 /// This graph type is completely static, so you can neither |
523 /// add nor delete either edges or nodes, and it needs just constant |
525 /// add nor delete either edges or nodes, and it needs constant |
524 /// space in memory. |
526 /// space in memory. |
525 /// |
527 /// |
526 /// The \e FullDigraph and \e FullGraph classes are very similar, |
528 /// This class conforms to the \ref concepts::Graph "Graph" concept |
527 /// but there are two differences. While the \e FullDigraph class is |
529 /// and it also has an important extra feature that its maps are |
528 /// conform just to the \ref concepts::Digraph "Digraph" concept, |
530 /// real \ref concepts::ReferenceMap "reference map"s. |
529 /// this class is conform to the \ref concepts::Graph "Graph" |
531 /// |
530 /// concept. In addition, the \e FullGraph class does not contain a |
532 /// The \c FullGraph and \c FullDigraph classes are very similar, |
531 /// loop arc from each node as the \e FullDigraph does. |
533 /// but there are two differences. While the \c FullDigraph class |
532 /// |
534 /// conforms only to the \ref concepts::Digraph "Digraph" concept, |
533 /// It also has an important extra feature that its maps are real |
535 /// this class conforms to the \ref concepts::Graph "Graph" concept, |
534 /// \ref concepts::ReferenceMap "reference map"s. |
536 /// moreover \c FullGraph does not contain a loop arc for each |
|
537 /// node as \c FullDigraph does. |
535 /// |
538 /// |
536 /// \sa FullDigraph |
539 /// \sa FullDigraph |
537 class FullGraph : public ExtendedFullGraphBase { |
540 class FullGraph : public ExtendedFullGraphBase { |
538 public: |
541 public: |
539 |
542 |
542 /// \brief Constructor |
545 /// \brief Constructor |
543 FullGraph() { construct(0); } |
546 FullGraph() { construct(0); } |
544 |
547 |
545 /// \brief Constructor |
548 /// \brief Constructor |
546 /// |
549 /// |
|
550 /// Constructor. |
547 /// \param n The number of the nodes. |
551 /// \param n The number of the nodes. |
548 FullGraph(int n) { construct(n); } |
552 FullGraph(int n) { construct(n); } |
549 |
553 |
550 /// \brief Resize the graph |
554 /// \brief Resizes the graph |
551 /// |
555 /// |
552 /// Resize the graph. The function will fully destroy and rebuild |
556 /// Resizes the graph. The function will fully destroy and |
553 /// the graph. This cause that the maps of the graph will |
557 /// rebuild the graph. This cause that the maps of the graph will |
554 /// reallocated automatically and the previous values will be |
558 /// reallocated automatically and the previous values will be lost. |
555 /// lost. |
|
556 void resize(int n) { |
559 void resize(int n) { |
557 Parent::notifier(Arc()).clear(); |
560 Parent::notifier(Arc()).clear(); |
558 Parent::notifier(Edge()).clear(); |
561 Parent::notifier(Edge()).clear(); |
559 Parent::notifier(Node()).clear(); |
562 Parent::notifier(Node()).clear(); |
560 construct(n); |
563 construct(n); |
563 Parent::notifier(Arc()).build(); |
566 Parent::notifier(Arc()).build(); |
564 } |
567 } |
565 |
568 |
566 /// \brief Returns the node with the given index. |
569 /// \brief Returns the node with the given index. |
567 /// |
570 /// |
568 /// Returns the node with the given index. Because it is a static |
571 /// Returns the node with the given index. Since it is a static |
569 /// size graph the node's of the graph can be indexed in the range |
572 /// graph its nodes can be indexed with integers from the range |
570 /// <tt>[0..nodeNum()-1]</tt> and the index of the node can |
573 /// <tt>[0..nodeNum()-1]</tt>. |
571 /// accessed by the \e index() member. |
574 /// \sa index() |
572 Node operator()(int ix) const { return Parent::operator()(ix); } |
575 Node operator()(int ix) const { return Parent::operator()(ix); } |
573 |
576 |
574 /// \brief Returns the index of the node. |
577 /// \brief Returns the index of the given node. |
575 /// |
578 /// |
576 /// Returns the index of the node. Because it is a static size |
579 /// Returns the index of the given node. Since it is a static |
577 /// graph the node's of the graph can be indexed in the range |
580 /// graph its nodes can be indexed with integers from the range |
578 /// <tt>[0..nodeNum()-1]</tt> and the index of the node can |
581 /// <tt>[0..nodeNum()-1]</tt>. |
579 /// accessed by the \e index() member. |
582 /// \sa operator() |
580 int index(const Node& node) const { return Parent::index(node); } |
583 int index(const Node& node) const { return Parent::index(node); } |
|
584 |
|
585 /// \brief Returns the arc connecting the given nodes. |
|
586 /// |
|
587 /// Returns the arc connecting the given nodes. |
|
588 Arc arc(const Node& s, const Node& t) const { |
|
589 return Parent::arc(s, t); |
|
590 } |
|
591 |
|
592 /// \brief Returns the edge connects the given nodes. |
|
593 /// |
|
594 /// Returns the edge connects the given nodes. |
|
595 Edge edge(const Node& u, const Node& v) const { |
|
596 return Parent::edge(u, v); |
|
597 } |
581 |
598 |
582 /// \brief Number of nodes. |
599 /// \brief Number of nodes. |
583 int nodeNum() const { return Parent::nodeNum(); } |
600 int nodeNum() const { return Parent::nodeNum(); } |
584 /// \brief Number of arcs. |
601 /// \brief Number of arcs. |
585 int arcNum() const { return Parent::arcNum(); } |
602 int arcNum() const { return Parent::arcNum(); } |
586 /// \brief Number of edges. |
603 /// \brief Number of edges. |
587 int edgeNum() const { return Parent::edgeNum(); } |
604 int edgeNum() const { return Parent::edgeNum(); } |
588 |
605 |
589 /// \brief Returns the arc connects the given nodes. |
|
590 /// |
|
591 /// Returns the arc connects the given nodes. |
|
592 Arc arc(const Node& s, const Node& t) const { |
|
593 return Parent::arc(s, t); |
|
594 } |
|
595 |
|
596 /// \brief Returns the edge connects the given nodes. |
|
597 /// |
|
598 /// Returns the edge connects the given nodes. |
|
599 Edge edge(const Node& u, const Node& v) const { |
|
600 return Parent::edge(u, v); |
|
601 } |
|
602 }; |
606 }; |
603 |
607 |
604 |
608 |
605 } //namespace lemon |
609 } //namespace lemon |
606 |
610 |