1.1 --- a/lemon/concept/graph.h Mon Jun 26 15:40:35 2006 +0000
1.2 +++ b/lemon/concept/graph.h Wed Jun 28 15:06:24 2006 +0000
1.3 @@ -38,8 +38,8 @@
1.4
1.5 // \brief Modular static graph class.
1.6 //
1.7 - // It should be the same as the \c StaticGraph class.
1.8 - class _StaticGraph
1.9 + // It should be the same as the \c Graph class.
1.10 + class _Graph
1.11 : virtual public BaseGraphComponent,
1.12 public IterableGraphComponent, public MappableGraphComponent {
1.13 public:
1.14 @@ -56,49 +56,10 @@
1.15 };
1.16 };
1.17
1.18 - // \brief Modular extendable graph class.
1.19 - //
1.20 - // It should be the same as the \c ExtendableGraph class.
1.21 - class _ExtendableGraph
1.22 - : virtual public BaseGraphComponent, public _StaticGraph,
1.23 - public ExtendableGraphComponent, public ClearableGraphComponent {
1.24 - public:
1.25 - typedef BaseGraphComponent::Node Node;
1.26 - typedef BaseGraphComponent::Edge Edge;
1.27 -
1.28 - template <typename _Graph>
1.29 - struct Constraints {
1.30 - void constraints() {
1.31 - checkConcept<_StaticGraph, _Graph >();
1.32 - checkConcept<ExtendableGraphComponent, _Graph >();
1.33 - checkConcept<ClearableGraphComponent, _Graph >();
1.34 - }
1.35 - };
1.36 - };
1.37 -
1.38 - // \brief Modular erasable graph class.
1.39 - //
1.40 - // It should be the same as the \c ErasableGraph class.
1.41 - class _ErasableGraph
1.42 - : virtual public BaseGraphComponent, public _ExtendableGraph,
1.43 - public ErasableGraphComponent {
1.44 - public:
1.45 - typedef BaseGraphComponent::Node Node;
1.46 - typedef BaseGraphComponent::Edge Edge;
1.47 -
1.48 - template <typename _Graph>
1.49 - struct Constraints {
1.50 - void constraints() {
1.51 - checkConcept<_ExtendableGraph, _Graph >();
1.52 - checkConcept<ErasableGraphComponent, _Graph >();
1.53 - }
1.54 - };
1.55 - };
1.56 -
1.57 /// \addtogroup graph_concepts
1.58 /// @{
1.59
1.60 - /// An empty static graph class.
1.61 + /// An empty graph class.
1.62
1.63 /// This class provides all the common features of a graph structure,
1.64 /// however completely without implementations and real data structures
1.65 @@ -116,13 +77,7 @@
1.66 ///
1.67 /// \todo A pages describing the concept of concept description would
1.68 /// be nice.
1.69 - class StaticGraph
1.70 - {
1.71 -// ///Copy consructor.
1.72 -
1.73 -// ///\todo It is not clear, what we expect from a copy constructor.
1.74 -// ///E.g. How to assign the nodes/edges to each other? What about maps?
1.75 -// StaticGraph(const StaticGraph& g) { }
1.76 + class Graph {
1.77 public:
1.78 ///\e
1.79
1.80 @@ -130,7 +85,7 @@
1.81
1.82 /// Defalult constructor.
1.83 ///
1.84 - StaticGraph() { }
1.85 + Graph() { }
1.86
1.87 /// The base type of node iterators,
1.88 /// or in other words, the trivial node iterator.
1.89 @@ -213,14 +168,14 @@
1.90
1.91 /// Sets the iterator to the first node of \c g.
1.92 ///
1.93 - NodeIt(const StaticGraph&) { }
1.94 + NodeIt(const Graph&) { }
1.95 /// Node -> NodeIt conversion.
1.96
1.97 /// Sets the iterator to the node of \c the graph pointed by
1.98 /// the trivial iterator.
1.99 /// This feature necessitates that each time we
1.100 /// iterate the edge-set, the iteration order is the same.
1.101 - NodeIt(const StaticGraph&, const Node&) { }
1.102 + NodeIt(const Graph&, const Node&) { }
1.103 /// Next node.
1.104
1.105 /// Assign the iterator to the next node.
1.106 @@ -307,13 +262,13 @@
1.107
1.108 /// This constructor sets the iterator to the first outgoing edge of
1.109 /// the node.
1.110 - OutEdgeIt(const StaticGraph&, const Node&) { }
1.111 + OutEdgeIt(const Graph&, const Node&) { }
1.112 /// Edge -> OutEdgeIt conversion
1.113
1.114 /// Sets the iterator to the value of the trivial iterator.
1.115 /// This feature necessitates that each time we
1.116 /// iterate the edge-set, the iteration order is the same.
1.117 - OutEdgeIt(const StaticGraph&, const Edge&) { }
1.118 + OutEdgeIt(const Graph&, const Edge&) { }
1.119 ///Next outgoing edge
1.120
1.121 /// Assign the iterator to the next
1.122 @@ -354,13 +309,13 @@
1.123
1.124 /// This constructor set the iterator to the first incoming edge of
1.125 /// the node.
1.126 - InEdgeIt(const StaticGraph&, const Node&) { }
1.127 + InEdgeIt(const Graph&, const Node&) { }
1.128 /// Edge -> InEdgeIt conversion
1.129
1.130 /// Sets the iterator to the value of the trivial iterator \c e.
1.131 /// This feature necessitates that each time we
1.132 /// iterate the edge-set, the iteration order is the same.
1.133 - InEdgeIt(const StaticGraph&, const Edge&) { }
1.134 + InEdgeIt(const Graph&, const Edge&) { }
1.135 /// Next incoming edge
1.136
1.137 /// Assign the iterator to the next inedge of the corresponding node.
1.138 @@ -397,13 +352,13 @@
1.139
1.140 /// This constructor sets the iterator to the first edge of \c g.
1.141 ///@param g the graph
1.142 - EdgeIt(const StaticGraph& g) { ignore_unused_variable_warning(g); }
1.143 + EdgeIt(const Graph& g) { ignore_unused_variable_warning(g); }
1.144 /// Edge -> EdgeIt conversion
1.145
1.146 /// Sets the iterator to the value of the trivial iterator \c e.
1.147 /// This feature necessitates that each time we
1.148 /// iterate the edge-set, the iteration order is the same.
1.149 - EdgeIt(const StaticGraph&, const Edge&) { }
1.150 + EdgeIt(const Graph&, const Edge&) { }
1.151 ///Next edge
1.152
1.153 /// Assign the iterator to the next edge.
1.154 @@ -420,53 +375,17 @@
1.155 ///
1.156 Node source(Edge) const { return INVALID; }
1.157
1.158 -// /// Gives back the first Node in the iterating order.
1.159 -
1.160 -// /// Gives back the first Node in the iterating order.
1.161 -// ///
1.162 void first(Node&) const {}
1.163 -
1.164 -// /// Gives back the next Node in the iterating order.
1.165 -
1.166 -// /// Gives back the next Node in the iterating order.
1.167 -// ///
1.168 void next(Node&) const {}
1.169
1.170 -// /// Gives back the first Edge in the iterating order.
1.171 -
1.172 -// /// Gives back the first Edge in the iterating order.
1.173 -// ///
1.174 void first(Edge&) const {}
1.175 -// /// Gives back the next Edge in the iterating order.
1.176 -
1.177 -// /// Gives back the next Edge in the iterating order.
1.178 -// ///
1.179 void next(Edge&) const {}
1.180
1.181
1.182 -// /// Gives back the first of the Edges point to the given Node.
1.183 -
1.184 -// /// Gives back the first of the Edges point to the given Node.
1.185 -// ///
1.186 void firstIn(Edge&, const Node&) const {}
1.187 -
1.188 -// /// Gives back the next of the Edges points to the given Node.
1.189 -
1.190 -
1.191 -// /// Gives back the next of the Edges points to the given Node.
1.192 -// ///
1.193 void nextIn(Edge&) const {}
1.194
1.195 -// /// Gives back the first of the Edges start from the given Node.
1.196 -
1.197 -// /// Gives back the first of the Edges start from the given Node.
1.198 -// ///
1.199 void firstOut(Edge&, const Node&) const {}
1.200 -
1.201 -// /// Gives back the next of the Edges start from the given Node.
1.202 -
1.203 -// /// Gives back the next of the Edges start from the given Node.
1.204 -// ///
1.205 void nextOut(Edge&) const {}
1.206
1.207 /// \brief The base node of the iterator.
1.208 @@ -511,9 +430,9 @@
1.209 public:
1.210
1.211 ///\e
1.212 - NodeMap(const StaticGraph&) { }
1.213 + NodeMap(const Graph&) { }
1.214 ///\e
1.215 - NodeMap(const StaticGraph&, T) { }
1.216 + NodeMap(const Graph&, T) { }
1.217
1.218 ///Copy constructor
1.219 NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
1.220 @@ -535,9 +454,9 @@
1.221 public:
1.222
1.223 ///\e
1.224 - EdgeMap(const StaticGraph&) { }
1.225 + EdgeMap(const Graph&) { }
1.226 ///\e
1.227 - EdgeMap(const StaticGraph&, T) { }
1.228 + EdgeMap(const Graph&, T) { }
1.229 ///Copy constructor
1.230 EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }
1.231 ///Assignment operator
1.232 @@ -545,72 +464,8 @@
1.233 // \todo fix this concept
1.234 };
1.235
1.236 - template <typename _Graph>
1.237 - struct Constraints : public _StaticGraph::Constraints<_Graph> {};
1.238 -
1.239 - };
1.240 -
1.241 - /// An empty non-static graph class.
1.242 -
1.243 - /// This class provides everything that \ref StaticGraph does.
1.244 - /// Additionally it enables building graphs from scratch.
1.245 - class ExtendableGraph : public StaticGraph
1.246 - {
1.247 - public:
1.248 - /// Defalult constructor.
1.249 -
1.250 - /// Defalult constructor.
1.251 - ///
1.252 - ExtendableGraph() { }
1.253 - ///Add a new node to the graph.
1.254 -
1.255 - /// \return the new node.
1.256 - ///
1.257 - Node addNode() { return INVALID; }
1.258 - ///Add a new edge to the graph.
1.259 -
1.260 - ///Add a new edge to the graph with source node \c s
1.261 - ///and target node \c t.
1.262 - ///\return the new edge.
1.263 - Edge addEdge(Node, Node) { return INVALID; }
1.264 -
1.265 - /// Resets the graph.
1.266 -
1.267 - /// This function deletes all edges and nodes of the graph.
1.268 - /// It also frees the memory allocated to store them.
1.269 - /// \todo It might belong to \ref ErasableGraph.
1.270 - void clear() { }
1.271 -
1.272 - template <typename _Graph>
1.273 - struct Constraints : public _ExtendableGraph::Constraints<_Graph> {};
1.274 -
1.275 - };
1.276 -
1.277 - /// An empty erasable graph class.
1.278 -
1.279 - /// This class is an extension of \ref ExtendableGraph. It makes it
1.280 - /// possible to erase edges or nodes.
1.281 - class ErasableGraph : public ExtendableGraph
1.282 - {
1.283 - public:
1.284 - /// Defalult constructor.
1.285 -
1.286 - /// Defalult constructor.
1.287 - ///
1.288 - ErasableGraph() { }
1.289 - /// Deletes a node.
1.290 -
1.291 - /// Deletes node \c n node.
1.292 - ///
1.293 - void erase(Node) { }
1.294 - /// Deletes an edge.
1.295 -
1.296 - /// Deletes edge \c e edge.
1.297 - ///
1.298 - void erase(Edge) { }
1.299 -
1.300 - template <typename _Graph>
1.301 - struct Constraints : public _ErasableGraph::Constraints<_Graph> {};
1.302 + template <typename RGraph>
1.303 + struct Constraints : public _Graph::Constraints<RGraph> {};
1.304
1.305 };
1.306