1.1 --- a/src/hugo/skeletons/graph.h Fri Sep 03 17:34:22 2004 +0000
1.2 +++ b/src/hugo/skeletons/graph.h Sun Sep 05 20:06:08 2004 +0000
1.3 @@ -35,40 +35,60 @@
1.4 {
1.5 public:
1.6 /// Defalult constructor.
1.7 +
1.8 + /// Defalult constructor.
1.9 + ///
1.10 StaticGraphSkeleton() { }
1.11 ///Copy consructor.
1.12
1.13 - ///\todo It is not clear, what we expect from a copy constructor.
1.14 - ///E.g. How to assign the nodes/edges to each other? What about maps?
1.15 - StaticGraphSkeleton(const StaticGraphSkeleton& g) { }
1.16 +// ///\todo It is not clear, what we expect from a copy constructor.
1.17 +// ///E.g. How to assign the nodes/edges to each other? What about maps?
1.18 +// StaticGraphSkeleton(const StaticGraphSkeleton& g) { }
1.19
1.20 /// The base type of node iterators,
1.21 /// or in other words, the trivial node iterator.
1.22
1.23 /// This is the base type of each node iterator,
1.24 /// thus each kind of node iterator converts to this.
1.25 - /// More precisely each kind of node iterator have to be inherited
1.26 + /// More precisely each kind of node iterator should be inherited
1.27 /// from the trivial node iterator.
1.28 class Node {
1.29 public:
1.30 + /// Default constructor
1.31 +
1.32 /// @warning The default constructor sets the iterator
1.33 /// to an undefined value.
1.34 Node() { }
1.35 /// Copy constructor.
1.36 +
1.37 + /// Copy constructor.
1.38 + ///
1.39 Node(const Node&) { }
1.40 +
1.41 /// Invalid constructor \& conversion.
1.42
1.43 /// This constructor initializes the iterator to be invalid.
1.44 /// \sa Invalid for more details.
1.45 Node(Invalid) { }
1.46 + /// Equality operator
1.47 +
1.48 /// Two iterators are equal if and only if they point to the
1.49 /// same object or both are invalid.
1.50 bool operator==(Node) const { return true; }
1.51
1.52 + /// Inequality operator
1.53 +
1.54 /// \sa \ref operator==(Node n)
1.55 ///
1.56 bool operator!=(Node) const { return true; }
1.57
1.58 + ///Comparison operator.
1.59 +
1.60 + ///This is a strict ordering between the nodes.
1.61 + ///
1.62 + ///This ordering can be different from the order in which NodeIt
1.63 + ///goes through the nodes.
1.64 + ///\todo Possibly we don't need it.
1.65 bool operator<(Node) const { return true; }
1.66 };
1.67
1.68 @@ -79,46 +99,84 @@
1.69 /// of nodes in graph \c g of type \c Graph like this:
1.70 /// \code
1.71 /// int count=0;
1.72 - /// for (Graph::NodeIt n(g); g.valid(n); ++n) ++count;
1.73 + /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
1.74 /// \endcode
1.75 class NodeIt : public Node {
1.76 public:
1.77 + /// Default constructor
1.78 +
1.79 /// @warning The default constructor sets the iterator
1.80 /// to an undefined value.
1.81 NodeIt() { }
1.82 /// Copy constructor.
1.83 +
1.84 + /// Copy constructor.
1.85 + ///
1.86 NodeIt(const NodeIt&) { }
1.87 /// Invalid constructor \& conversion.
1.88
1.89 /// Initialize the iterator to be invalid.
1.90 /// \sa Invalid for more details.
1.91 NodeIt(Invalid) { }
1.92 + /// Sets the iterator to the first node.
1.93 +
1.94 /// Sets the iterator to the first node of \c g.
1.95 + ///
1.96 NodeIt(const StaticGraphSkeleton& g) { }
1.97 + /// Node -> NodeIt conversion.
1.98 +
1.99 /// Sets the iterator to the node of \c g pointed by the trivial
1.100 - /// iterator n. This feature necessitates that each time we
1.101 - /// iterate the node-set, the iteration order is the same.
1.102 + /// iterator n.
1.103 + /// This feature necessitates that each time we
1.104 + /// iterate the edge-set, the iteration order is the same.
1.105 NodeIt(const StaticGraphSkeleton& g, const Node& n) { }
1.106 + /// Next node.
1.107 +
1.108 /// Assign the iterator to the next node.
1.109 + ///
1.110 NodeIt& operator++() { return *this; }
1.111 };
1.112
1.113
1.114 /// The base type of the edge iterators.
1.115 +
1.116 + /// The base type of the edge iterators.
1.117 + ///
1.118 class Edge {
1.119 public:
1.120 + /// Default constructor
1.121 +
1.122 /// @warning The default constructor sets the iterator
1.123 /// to an undefined value.
1.124 Edge() { }
1.125 /// Copy constructor.
1.126 +
1.127 + /// Copy constructor.
1.128 + ///
1.129 Edge(const Edge&) { }
1.130 /// Initialize the iterator to be invalid.
1.131 +
1.132 + /// Initialize the iterator to be invalid.
1.133 + ///
1.134 Edge(Invalid) { }
1.135 + /// Equality operator
1.136 +
1.137 /// Two iterators are equal if and only if they point to the
1.138 /// same object or both are invalid.
1.139 bool operator==(Edge) const { return true; }
1.140 + /// Inequality operator
1.141 +
1.142 + /// \sa \ref operator==(Node n)
1.143 + ///
1.144 bool operator!=(Edge) const { return true; }
1.145 - bool operator<(Edge) const { return true; }
1.146 + ///Comparison operator.
1.147 +
1.148 + ///This is a strict ordering between the nodes.
1.149 + ///
1.150 + ///This ordering can be different from the order in which NodeIt
1.151 + ///goes through the nodes.
1.152 + ///\todo Possibly we don't need it.
1.153 + bool operator<(Edge) const { return true; }
1.154 };
1.155
1.156 /// This iterator goes trough the outgoing edges of a node.
1.157 @@ -130,17 +188,25 @@
1.158 /// in graph \c g of type \c Graph as follows.
1.159 /// \code
1.160 /// int count=0;
1.161 - /// for (Graph::OutEdgeIt e(g, n); g.valid(e); ++e) ++count;
1.162 + /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.163 /// \endcode
1.164
1.165 class OutEdgeIt : public Edge {
1.166 public:
1.167 + /// Default constructor
1.168 +
1.169 /// @warning The default constructor sets the iterator
1.170 /// to an undefined value.
1.171 OutEdgeIt() { }
1.172 /// Copy constructor.
1.173 +
1.174 + /// Copy constructor.
1.175 + ///
1.176 OutEdgeIt(const OutEdgeIt&) { }
1.177 /// Initialize the iterator to be invalid.
1.178 +
1.179 + /// Initialize the iterator to be invalid.
1.180 + ///
1.181 OutEdgeIt(Invalid) { }
1.182 /// This constructor sets the iterator to first outgoing edge.
1.183
1.184 @@ -149,11 +215,16 @@
1.185 ///@param n the node
1.186 ///@param g the graph
1.187 OutEdgeIt(const StaticGraphSkeleton& g, const Node& n) { }
1.188 + /// Edge -> OutEdgeIt conversion
1.189 +
1.190 /// Sets the iterator to the value of the trivial iterator \c e.
1.191 /// This feature necessitates that each time we
1.192 /// iterate the edge-set, the iteration order is the same.
1.193 OutEdgeIt(const StaticGraphSkeleton& g, const Edge& e) { }
1.194 - /// Assign the iterator to the next outedge of the corresponding node.
1.195 + ///Next outgoing edge
1.196 +
1.197 + /// Assign the iterator to the next
1.198 + /// outgoing edge of the corresponding node.
1.199 OutEdgeIt& operator++() { return *this; }
1.200 };
1.201
1.202 @@ -166,27 +237,45 @@
1.203 /// in graph \c g of type \c Graph as follows.
1.204 /// \code
1.205 /// int count=0;
1.206 - /// for(Graph::InEdgeIt e(g, n); g.valid(e); ++) ++count;
1.207 + /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
1.208 /// \endcode
1.209
1.210 class InEdgeIt : public Edge {
1.211 public:
1.212 + /// Default constructor
1.213 +
1.214 /// @warning The default constructor sets the iterator
1.215 /// to an undefined value.
1.216 InEdgeIt() { }
1.217 /// Copy constructor.
1.218 +
1.219 + /// Copy constructor.
1.220 + ///
1.221 InEdgeIt(const InEdgeIt&) { }
1.222 /// Initialize the iterator to be invalid.
1.223 +
1.224 + /// Initialize the iterator to be invalid.
1.225 + ///
1.226 InEdgeIt(Invalid) { }
1.227 - /// .
1.228 - InEdgeIt(const StaticGraphSkeleton&, const Node&) { }
1.229 - /// .
1.230 - InEdgeIt(const StaticGraphSkeleton&, const Edge&) { }
1.231 + /// This constructor sets the iterator to first incoming edge.
1.232 +
1.233 + /// This constructor set the iterator to the first incoming edge of
1.234 + /// node
1.235 + ///@param n the node
1.236 + ///@param g the graph
1.237 + InEdgeIt(const StaticGraphSkeleton& g, const Node& n) { }
1.238 + /// Edge -> InEdgeIt conversion
1.239 +
1.240 + /// Sets the iterator to the value of the trivial iterator \c e.
1.241 + /// This feature necessitates that each time we
1.242 + /// iterate the edge-set, the iteration order is the same.
1.243 + InEdgeIt(const StaticGraphSkeleton& g, const Edge& n) { }
1.244 + /// Next incoming edge
1.245 +
1.246 /// Assign the iterator to the next inedge of the corresponding node.
1.247 + ///
1.248 InEdgeIt& operator++() { return *this; }
1.249 };
1.250 - // class SymEdgeIt : public Edge {};
1.251 -
1.252 /// This iterator goes through each edge.
1.253
1.254 /// This iterator goes through each edge of a graph.
1.255 @@ -194,21 +283,41 @@
1.256 /// of edges in a graph \c g of type \c Graph as follows:
1.257 /// \code
1.258 /// int count=0;
1.259 - /// for(Graph::EdgeIt e(g); g.valid(e); ++e) ++count;
1.260 + /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
1.261 /// \endcode
1.262 class EdgeIt : public Edge {
1.263 public:
1.264 + /// Default constructor
1.265 +
1.266 /// @warning The default constructor sets the iterator
1.267 /// to an undefined value.
1.268 EdgeIt() { }
1.269 /// Copy constructor.
1.270 +
1.271 + /// Copy constructor.
1.272 + ///
1.273 EdgeIt(const EdgeIt&) { }
1.274 /// Initialize the iterator to be invalid.
1.275 +
1.276 + /// Initialize the iterator to be invalid.
1.277 + ///
1.278 EdgeIt(Invalid) { }
1.279 - /// .
1.280 - EdgeIt(const StaticGraphSkeleton&) { }
1.281 - /// .
1.282 + /// This constructor sets the iterator to first edge.
1.283 +
1.284 + /// This constructor set the iterator to the first edge of
1.285 + /// node
1.286 + ///@param g the graph
1.287 + EdgeIt(const StaticGraphSkeleton& g) { }
1.288 + /// Edge -> EdgeIt conversion
1.289 +
1.290 + /// Sets the iterator to the value of the trivial iterator \c e.
1.291 + /// This feature necessitates that each time we
1.292 + /// iterate the edge-set, the iteration order is the same.
1.293 EdgeIt(const StaticGraphSkeleton&, const Edge&) { }
1.294 + ///Next edge
1.295 +
1.296 + /// Assign the iterator to the next
1.297 + /// edge of the corresponding node.
1.298 EdgeIt& operator++() { return *this; }
1.299 };
1.300
1.301 @@ -220,71 +329,53 @@
1.302 NodeIt& first(NodeIt& i) const { return i; }
1.303
1.304 /// The first incoming edge.
1.305 +
1.306 + /// The first incoming edge.
1.307 + ///
1.308 InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
1.309 /// The first outgoing edge.
1.310 +
1.311 + /// The first outgoing edge.
1.312 + ///
1.313 OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
1.314 - // SymEdgeIt& first(SymEdgeIt&, Node) const { return i; }
1.315 /// The first edge of the Graph.
1.316 +
1.317 + /// The first edge of the Graph.
1.318 + ///
1.319 EdgeIt& first(EdgeIt& i) const { return i; }
1.320
1.321 - // Node getNext(Node) const {}
1.322 - // InEdgeIt getNext(InEdgeIt) const {}
1.323 - // OutEdgeIt getNext(OutEdgeIt) const {}
1.324 - // //SymEdgeIt getNext(SymEdgeIt) const {}
1.325 - // EdgeIt getNext(EdgeIt) const {}
1.326 -
1.327 - /// Go to the next node.
1.328 - NodeIt& next(NodeIt& i) const { return i; }
1.329 - /// Go to the next incoming edge.
1.330 - InEdgeIt& next(InEdgeIt& i) const { return i; }
1.331 - /// Go to the next outgoing edge.
1.332 - OutEdgeIt& next(OutEdgeIt& i) const { return i; }
1.333 - //SymEdgeIt& next(SymEdgeIt&) const { }
1.334 - /// Go to the next edge.
1.335 - EdgeIt& next(EdgeIt& i) const { return i; }
1.336 + ///Gives back the head node of an edge.
1.337
1.338 ///Gives back the head node of an edge.
1.339 + ///
1.340 Node head(Edge) const { return INVALID; }
1.341 ///Gives back the tail node of an edge.
1.342 +
1.343 + ///Gives back the tail node of an edge.
1.344 + ///
1.345 Node tail(Edge) const { return INVALID; }
1.346
1.347 - // Node aNode(InEdgeIt) const {}
1.348 - // Node aNode(OutEdgeIt) const {}
1.349 - // Node aNode(SymEdgeIt) const {}
1.350 -
1.351 - // Node bNode(InEdgeIt) const {}
1.352 - // Node bNode(OutEdgeIt) const {}
1.353 - // Node bNode(SymEdgeIt) const {}
1.354 -
1.355 - /// Checks if a node iterator is valid
1.356 -
1.357 - ///\todo Maybe, it would be better if iterator converted to
1.358 - ///bool directly, as Jacint prefers.
1.359 - bool valid(const Node&) const { return true; }
1.360 - /// Checks if an edge iterator is valid
1.361 -
1.362 - ///\todo Maybe, it would be better if iterator converted to
1.363 - ///bool directly, as Jacint prefers.
1.364 - bool valid(const Edge&) const { return true; }
1.365 -
1.366 ///Gives back the \e id of a node.
1.367
1.368 ///\warning Not all graph structures provide this feature.
1.369 ///
1.370 + ///\todo Should each graph provide \c id?
1.371 int id(const Node&) const { return 0; }
1.372 ///Gives back the \e id of an edge.
1.373
1.374 ///\warning Not all graph structures provide this feature.
1.375 ///
1.376 + ///\todo Should each graph provide \c id?
1.377 int id(const Edge&) const { return 0; }
1.378
1.379 - /// Resets the graph.
1.380 -
1.381 - /// This function deletes all edges and nodes of the graph.
1.382 - /// It also frees the memory allocated to store them.
1.383 - void clear() { }
1.384 -
1.385 + /// .
1.386 +
1.387 + ///\todo What is this?
1.388 + ///
1.389 int nodeNum() const { return 0; }
1.390 + /// .
1.391 + ///\todo What is this?
1.392 + ///
1.393 int edgeNum() const { return 0; }
1.394
1.395
1.396 @@ -293,14 +384,14 @@
1.397 ///Reference map of the nodes to type \c T.
1.398 /// \sa ReferenceSkeleton
1.399 /// \warning Making maps that can handle bool type (NodeMap<bool>)
1.400 - /// needs extra attention!
1.401 -
1.402 - template<class T> class NodeMap
1.403 - : public ReferenceMap< Node, T >
1.404 + /// needs some extra attention!
1.405 + template<class T> class NodeMap: public ReferenceMap< Node, T >
1.406 {
1.407 public:
1.408
1.409 + /// .
1.410 NodeMap(const StaticGraphSkeleton&) { }
1.411 + /// .
1.412 NodeMap(const StaticGraphSkeleton&, T) { }
1.413
1.414 ///Copy constructor
1.415 @@ -315,15 +406,15 @@
1.416 ///Reference map of the edges to type \c T.
1.417 /// \sa ReferenceSkeleton
1.418 /// \warning Making maps that can handle bool type (EdgeMap<bool>)
1.419 - /// needs extra attention!
1.420 + /// needs some extra attention!
1.421 template<class T> class EdgeMap
1.422 : public ReferenceMap<Edge,T>
1.423 {
1.424 public:
1.425 - typedef T ValueType;
1.426 - typedef Edge KeyType;
1.427
1.428 + /// .
1.429 EdgeMap(const StaticGraphSkeleton&) { }
1.430 + /// .
1.431 EdgeMap(const StaticGraphSkeleton&, T) { }
1.432
1.433 ///Copy constructor
1.434 @@ -336,7 +427,7 @@
1.435
1.436
1.437
1.438 - /// An empty graph class.
1.439 + /// An empty non-static graph class.
1.440
1.441 /// This class provides everything that \c StaticGraphSkeleton
1.442 /// with additional functionality which enables to build a
1.443 @@ -345,13 +436,10 @@
1.444 {
1.445 public:
1.446 /// Defalult constructor.
1.447 +
1.448 + /// Defalult constructor.
1.449 + ///
1.450 GraphSkeleton() { }
1.451 - ///Copy consructor.
1.452 -
1.453 - ///\todo It is not clear, what we expect from a copy constructor.
1.454 - ///E.g. How to assign the nodes/edges to each other? What about maps?
1.455 - GraphSkeleton(const GraphSkeleton&) { }
1.456 -
1.457 ///Add a new node to the graph.
1.458
1.459 /// \return the new node.
1.460 @@ -379,38 +467,27 @@
1.461 class EraseableGraphSkeleton : public GraphSkeleton
1.462 {
1.463 public:
1.464 + /// Defalult constructor.
1.465 +
1.466 + /// Defalult constructor.
1.467 + ///
1.468 + EraseableGraphSkeleton() { }
1.469 /// Deletes a node.
1.470 +
1.471 + /// Deletes node \c n node.
1.472 + ///
1.473 void erase(Node n) { }
1.474 /// Deletes an edge.
1.475 +
1.476 + /// Deletes edge \c e edge.
1.477 + ///
1.478 void erase(Edge e) { }
1.479 -
1.480 - /// Defalult constructor.
1.481 - EraseableGraphSkeleton() { }
1.482 - ///Copy consructor.
1.483 - EraseableGraphSkeleton(const GraphSkeleton&) { }
1.484 };
1.485
1.486 // @}
1.487 - } //namespace skeleton
1.488 -
1.489 + } //namespace skeleton
1.490 } //namespace hugo
1.491
1.492
1.493
1.494 -// class EmptyBipGraph : public Graph Skeleton
1.495 -// {
1.496 -// class ANode {};
1.497 -// class BNode {};
1.498 -
1.499 -// ANode &next(ANode &) {}
1.500 -// BNode &next(BNode &) {}
1.501 -
1.502 -// ANode &getFirst(ANode &) const {}
1.503 -// BNode &getFirst(BNode &) const {}
1.504 -
1.505 -// enum NodeClass { A = 0, B = 1 };
1.506 -// NodeClass getClass(Node n) {}
1.507 -
1.508 -// }
1.509 -
1.510 #endif // HUGO_SKELETON_GRAPH_H