Changeset 354:80a4d0742e98 in lemon-main
- Timestamp:
- 11/01/08 19:22:18 (16 years ago)
- Branch:
- default
- Phase:
- public
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/full_graph.h
r353 r354 20 20 #define LEMON_FULL_GRAPH_H 21 21 22 #include <lemon/math.h>23 24 22 #include <lemon/core.h> 25 23 #include <lemon/bits/graph_extender.h> … … 27 25 ///\ingroup graphs 28 26 ///\file 29 ///\brief FullDigraph and FullGraph classes. 27 ///\brief FullGraph and FullDigraph classes. 28 30 29 namespace lemon { 31 30 … … 68 67 Node target(Arc arc) const { return arc._id % _node_num; } 69 68 70 71 69 static int id(Node node) { return node._id; } 72 70 static int id(Arc arc) { return arc._id; } 73 71 74 72 static Node nodeFromId(int id) { return Node(id);} 75 76 73 static Arc arcFromId(int id) { return Arc(id);} 77 74 … … 81 78 return prev != INVALID ? arc(s, t) : INVALID; 82 79 } 83 84 80 85 81 class Node { … … 158 154 /// From each node go arcs to each node (including the source node), 159 155 /// therefore the number of the arcs in the digraph is the square of 160 /// the node number. Th e digraph is completely static, so you can161 /// neither add nor delete either arcs or nodes, and it needs just156 /// the node number. This digraph type is completely static, so you 157 /// can neither add nor delete either arcs or nodes, and it needs 162 158 /// constant space in memory. 163 159 /// 164 /// Th us itconforms to the \ref concepts::Digraph "Digraph" concept160 /// This class conforms to the \ref concepts::Digraph "Digraph" concept 165 161 /// and it also has an important extra feature that its maps are 166 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 171 /// \sa FullGraph … … 178 180 /// \brief Constructor 179 181 /// 182 /// Constructor. 180 183 /// \param n The number of the nodes. 181 184 FullDigraph(int n) { construct(n); } 182 185 183 /// \brief Resize the digraph 184 /// 185 /// Resize the digraph. The function will fully destroy and 186 /// rebuild the digraph. This cause that the maps of the digraph 187 /// will reallocated automatically and the previous values will be 188 /// lost. 186 /// \brief Resizes the digraph 187 /// 188 /// Resizes the digraph. The function will fully destroy and 189 /// rebuild the digraph. This cause that the maps of the digraph will 190 /// reallocated automatically and the previous values will be lost. 189 191 void resize(int n) { 190 192 Parent::notifier(Arc()).clear(); … … 197 199 /// \brief Returns the node with the given index. 198 200 /// 199 /// Returns the node with the given index. Because it is a200 /// static size digraph the node's of the digraph can be indexed201 /// in the range <tt>[0..nodeNum()-1]</tt> and the index of202 /// the node can accessed by the \e index() member.201 /// Returns the node with the given index. Since it is a static 202 /// digraph its nodes can be indexed with integers from the range 203 /// <tt>[0..nodeNum()-1]</tt>. 204 /// \sa index() 203 205 Node operator()(int ix) const { return Parent::operator()(ix); } 204 206 205 /// \brief Returns the index of the node.206 /// 207 /// Returns the index of the node. Because it is a208 /// static size digraph the node's of the digraph can be indexed209 /// in the range <tt>[0..nodeNum()-1]</tt> and the index of210 /// the node can accessed by the \e index() member.207 /// \brief Returns the index of the given node. 208 /// 209 /// Returns the index of the given node. Since it is a static 210 /// digraph its nodes can be indexed with integers from the range 211 /// <tt>[0..nodeNum()-1]</tt>. 212 /// \sa operator() 211 213 int index(const Node& node) const { return Parent::index(node); } 212 214 213 /// \brief Returns the arc connect sthe given nodes.214 /// 215 /// Returns the arc connect sthe given nodes.215 /// \brief Returns the arc connecting the given nodes. 216 /// 217 /// Returns the arc connecting the given nodes. 216 218 Arc arc(const Node& u, const Node& v) const { 217 219 return Parent::arc(u, v); … … 280 282 281 283 public: 282 283 284 284 285 Node operator()(int ix) const { return Node(ix); } … … 368 369 class Edge { 369 370 friend class FullGraphBase; 371 friend class Arc; 370 372 371 373 protected: … … 519 521 /// This is a simple and fast undirected full graph 520 522 /// implementation. From each node go edge to each other node, 521 /// therefore the number of edges in the graph is 522 /// <tt>n(n-1)/2</tt>. Itis completely static, so you can neither523 /// add nor delete either edges or nodes, and it needs justconstant523 /// therefore the number of edges in the graph is \f$n(n-1)/2\f$. 524 /// This graph type is completely static, so you can neither 525 /// add nor delete either edges or nodes, and it needs constant 524 526 /// space in memory. 525 527 /// 526 /// The \e FullDigraph and \e FullGraph classes are very similar, 527 /// but there are two differences. While the \e FullDigraph class is 528 /// conform just to the \ref concepts::Digraph "Digraph" concept, 529 /// this class is conform to the \ref concepts::Graph "Graph" 530 /// concept. In addition, the \e FullGraph class does not contain a 531 /// loop arc from each node as the \e FullDigraph does. 532 /// 533 /// It also has an important extra feature that its maps are real 534 /// \ref concepts::ReferenceMap "reference map"s. 528 /// This class conforms to the \ref concepts::Graph "Graph" concept 529 /// and it also has an important extra feature that its maps are 530 /// real \ref concepts::ReferenceMap "reference map"s. 531 /// 532 /// The \c FullGraph and \c FullDigraph classes are very similar, 533 /// but there are two differences. While the \c FullDigraph class 534 /// conforms only to the \ref concepts::Digraph "Digraph" concept, 535 /// this class conforms to the \ref concepts::Graph "Graph" concept, 536 /// moreover \c FullGraph does not contain a loop arc for each 537 /// node as \c FullDigraph does. 535 538 /// 536 539 /// \sa FullDigraph … … 545 548 /// \brief Constructor 546 549 /// 550 /// Constructor. 547 551 /// \param n The number of the nodes. 548 552 FullGraph(int n) { construct(n); } 549 553 550 /// \brief Resize the graph 551 /// 552 /// Resize the graph. The function will fully destroy and rebuild 553 /// the graph. This cause that the maps of the graph will 554 /// reallocated automatically and the previous values will be 555 /// lost. 554 /// \brief Resizes the graph 555 /// 556 /// Resizes the graph. The function will fully destroy and 557 /// rebuild the graph. This cause that the maps of the graph will 558 /// reallocated automatically and the previous values will be lost. 556 559 void resize(int n) { 557 560 Parent::notifier(Arc()).clear(); … … 566 569 /// \brief Returns the node with the given index. 567 570 /// 568 /// Returns the node with the given index. Because it is a static569 /// size graph the node's of the graph can be indexed inthe range570 /// <tt>[0..nodeNum()-1]</tt> and the index of the node can571 /// accessed by the \e index() member.571 /// Returns the node with the given index. Since it is a static 572 /// graph its nodes can be indexed with integers from the range 573 /// <tt>[0..nodeNum()-1]</tt>. 574 /// \sa index() 572 575 Node operator()(int ix) const { return Parent::operator()(ix); } 573 576 574 /// \brief Returns the index of the node.575 /// 576 /// Returns the index of the node. Because it is a static size577 /// graph the node's of the graph can be indexed inthe range578 /// <tt>[0..nodeNum()-1]</tt> and the index of the node can579 /// accessed by the \e index() member.577 /// \brief Returns the index of the given node. 578 /// 579 /// Returns the index of the given node. Since it is a static 580 /// graph its nodes can be indexed with integers from the range 581 /// <tt>[0..nodeNum()-1]</tt>. 582 /// \sa operator() 580 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 599 /// \brief Number of nodes. … … 587 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 -
test/digraph_test.cc
r353 r354 143 143 checkConcept<ClearableDigraphComponent<>, SmartDigraph>(); 144 144 } 145 //{ // Checking FullDigraph146 //checkConcept<Digraph, FullDigraph>();147 //}145 { // Checking FullDigraph 146 checkConcept<Digraph, FullDigraph>(); 147 } 148 148 // { // Checking HyperCubeDigraph 149 149 // checkConcept<Digraph, HyperCubeDigraph>();
Note: See TracChangeset
for help on using the changeset viewer.