1.1 --- a/src/work/marci/graph_concept.h Thu May 20 15:40:59 2004 +0000
1.2 +++ b/src/work/marci/graph_concept.h Thu May 20 16:57:18 2004 +0000
1.3 @@ -3,14 +3,13 @@
1.4 #define HUGO_GRAPH_H
1.5
1.6 ///\file
1.7 -///\brief Declaration of GraphSkeleturo.
1.8 +///\brief Declaration of GraphConcept.
1.9
1.10 -#include <invalid.h>
1.11 +#include <hugo/invalid.h>
1.12
1.13 -/// The namespace of HugoLib
1.14 namespace hugo {
1.15
1.16 - /// @defgroup empty_graph The GraphSkeleturo class
1.17 + /// @defgroup empty_graph The GraphConcept class
1.18 /// @{
1.19
1.20 /// An empty graph class.
1.21 @@ -28,34 +27,38 @@
1.22 /// feature, the documentation of a real graph imlementation
1.23 /// like @ref ListGraph or
1.24 /// @ref SmartGraph will just refer to this structure.
1.25 - class GraphSkeleturo
1.26 + class GraphConcept
1.27 {
1.28 public:
1.29 /// Defalult constructor.
1.30 - GraphSkeleturo() {}
1.31 - ///Copy consructor.
1.32 + GraphConcept() { }
1.33
1.34 - ///\todo It is not clear, what we expect from a copy constructor.
1.35 - ///E.g. How to assign the nodes/edges to each other? What about maps?
1.36 - GraphSkeleturo(const GraphSkeleturo &G) {}
1.37 + /// \brief Copy consructor.
1.38 + ///
1.39 + /// \todo It is not clear, what we expect from a copy constructor.
1.40 + /// E.g. How to assign the nodes/edges to each other? What about maps?
1.41 + GraphConcept(const GraphConcept&) { }
1.42
1.43 - /// The base type of the node iterators.
1.44 -
1.45 + /// \brief The base type of the node iterators.
1.46 + ///
1.47 /// This is the base type of each node iterators,
1.48 /// thus each kind of node iterator will convert to this.
1.49 + /// Sometimes it is said to be a trivial iterator.
1.50 class Node {
1.51 public:
1.52 /// @warning The default constructor sets the iterator
1.53 /// to an undefined value.
1.54 - Node() {} //FIXME
1.55 - /// Invalid constructor \& conversion.
1.56 + Node() { } //FIXME
1.57
1.58 + // /// Copy constructor.
1.59 + // Node(const Node&) { }
1.60 +
1.61 + /// \brief Invalid constructor \& conversion.
1.62 + ///
1.63 /// This constructor initializes the iterator to be invalid.
1.64 /// \sa Invalid for more details.
1.65 -
1.66 - Node(Invalid) {}
1.67 - //Node(const Node &) {}
1.68 -
1.69 + Node(const Invalid&) { }
1.70 +
1.71 /// Two iterators are equal if and only if they point to the
1.72 /// same object or both are invalid.
1.73 bool operator==(Node n) const { return true; }
1.74 @@ -67,41 +70,18 @@
1.75 bool operator<(Node n) const { return true; }
1.76 };
1.77
1.78 - /// This iterator goes through each node.
1.79 -
1.80 - /// This iterator goes through each node.
1.81 - /// Its usage is quite simple, for example you can count the number
1.82 - /// of nodes in graph \c G of type \c Graph like this:
1.83 - /// \code
1.84 - ///int count=0;
1.85 - ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
1.86 - /// \endcode
1.87 - class NodeIt : public Node {
1.88 - public:
1.89 - /// @warning The default constructor sets the iterator
1.90 - /// to an undefined value.
1.91 - NodeIt() {} //FIXME
1.92 - /// Invalid constructor \& conversion.
1.93 -
1.94 - /// Initialize the iterator to be invalid
1.95 - /// \sa Invalid for more details.
1.96 - NodeIt(Invalid) {}
1.97 - /// Sets the iterator to the first node of \c G.
1.98 - NodeIt(const GraphSkeleturo &G) {}
1.99 - /// @warning The default constructor sets the iterator
1.100 - /// to an undefined value.
1.101 - NodeIt(const NodeIt &) {}
1.102 - };
1.103 -
1.104 -
1.105 /// The base type of the edge iterators.
1.106 class Edge {
1.107 public:
1.108 /// @warning The default constructor sets the iterator
1.109 /// to an undefined value.
1.110 - Edge() {} //FIXME
1.111 + Edge() { } //FIXME
1.112 +
1.113 + // /// Copy constructor.
1.114 + // Edge(const Edge&) { }
1.115 +
1.116 /// Initialize the iterator to be invalid
1.117 - Edge(Invalid) {}
1.118 + Edge(const Invalid&) { }
1.119 /// Two iterators are equal if and only if they point to the
1.120 /// same object or both are invalid.
1.121 bool operator==(Edge n) const { return true; }
1.122 @@ -111,38 +91,8 @@
1.123
1.124 // class SymEdgeIt : public Edge {};
1.125
1.126 - /// This iterator goes through each edge.
1.127
1.128 - /// This iterator goes through each edge of a graph.
1.129 - /// Its usage is quite simple, for example you can count the number
1.130 - /// of edges in a graph \c G of type \c Graph as follows:
1.131 - /// \code
1.132 - ///int count=0;
1.133 - ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
1.134 - /// \endcode
1.135 - class EdgeIt : public Edge {
1.136 - public:
1.137 - /// @warning The default constructor sets the iterator
1.138 - /// to an undefined value.
1.139 - EdgeIt() {}
1.140 - /// Initialize the iterator to be invalid
1.141 - EdgeIt(Invalid) {}
1.142 - EdgeIt(const GraphSkeleturo &) {}
1.143 - };
1.144 -
1.145 - /// First node of the graph.
1.146 -
1.147 - /// \post \c i and the return value will be the first node.
1.148 - ///
1.149 - NodeIt &first(NodeIt &i) const { return i;}
1.150 -
1.151 - /// The first incoming edge.
1.152 - InEdgeIt &first(InEdgeIt &i, Node n) const { return i;}
1.153 - /// The first outgoing edge.
1.154 - OutEdgeIt &first(OutEdgeIt &i, Node n) const { return i;}
1.155 // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
1.156 - /// The first edge of the Graph.
1.157 - EdgeIt &first(EdgeIt &i) const { return i;}
1.158
1.159 // Node getNext(Node) const {}
1.160 // InEdgeIt getNext(InEdgeIt) const {}
1.161 @@ -150,76 +100,64 @@
1.162 // //SymEdgeIt getNext(SymEdgeIt) const {}
1.163 // EdgeIt getNext(EdgeIt) const {}
1.164
1.165 - /// Go to the next node.
1.166 - NodeIt &next(NodeIt &i) const { return i;}
1.167 - /// Go to the next incoming edge.
1.168 - InEdgeIt &next(InEdgeIt &i) const { return i;}
1.169 - /// Go to the next outgoing edge.
1.170 - OutEdgeIt &next(OutEdgeIt &i) const { return i;}
1.171 //SymEdgeIt &next(SymEdgeIt &) const {}
1.172 - /// Go to the next edge.
1.173 - EdgeIt &next(EdgeIt &i) const { return i;}
1.174
1.175 - ///Gives back the head node of an edge.
1.176 - Node head(Edge) const { return INVALID; }
1.177 - ///Gives back the tail node of an edge.
1.178 - Node tail(Edge) const { return INVALID; }
1.179 +
1.180 + /// Gives back the head node of an edge.
1.181 + Node head(const Edge&) const { return INVALID; }
1.182 + /// Gives back the tail node of an edge.
1.183 + Node tail(const Edge&) const { return INVALID; }
1.184
1.185 - // Node aNode(InEdgeIt) const {}
1.186 - // Node aNode(OutEdgeIt) const {}
1.187 // Node aNode(SymEdgeIt) const {}
1.188 -
1.189 - // Node bNode(InEdgeIt) const {}
1.190 - // Node bNode(OutEdgeIt) const {}
1.191 // Node bNode(SymEdgeIt) const {}
1.192
1.193 - /// Checks if a node iterator is valid
1.194 + /// \brief Checks if a node iterator is valid
1.195 + ///
1.196 + /// \todo Maybe, it would be better if iterator converted to
1.197 + /// bool directly, as Jacint prefers.
1.198 + bool valid(const Node&) const { return true; }
1.199 + /// \brief Checks if an edge iterator is valid
1.200 + ///
1.201 + /// \todo Maybe, it would be better if iterator converted to
1.202 + /// bool directly, as Jacint prefers.
1.203 + bool valid(const Edge&) const { return true; }
1.204
1.205 - ///\todo Maybe, it would be better if iterator converted to
1.206 - ///bool directly, as Jacint prefers.
1.207 - bool valid(const Node&) const { return true;}
1.208 - /// Checks if an edge iterator is valid
1.209 -
1.210 - ///\todo Maybe, it would be better if iterator converted to
1.211 - ///bool directly, as Jacint prefers.
1.212 - bool valid(const Edge&) const { return true;}
1.213 -
1.214 - ///Gives back the \e id of a node.
1.215 -
1.216 - ///\warning Not all graph structures provide this feature.
1.217 + /// \brief Gives back the \e id of a node.
1.218 + ///
1.219 + /// \warning Not all graph structures provide this feature.
1.220 ///
1.221 - int id(const Node&) const { return 0;}
1.222 - ///Gives back the \e id of an edge.
1.223 -
1.224 - ///\warning Not all graph structures provide this feature.
1.225 + int id(const Node&) const { return 0; }
1.226 + /// \brief Gives back the \e id of an edge.
1.227 ///
1.228 - int id(const Edge&) const { return 0;}
1.229 + /// \warning Not all graph structures provide this feature.
1.230 + ///
1.231 + int id(const Edge&) const { return 0; }
1.232
1.233 //void setInvalid(Node &) const {};
1.234 //void setInvalid(Edge &) const {};
1.235
1.236 - ///Add a new node to the graph.
1.237 -
1.238 + /// \brief Add a new node to the graph.
1.239 + ///
1.240 /// \return the new node.
1.241 + Node addNode() { return INVALID; }
1.242 + /// \brief Add a new edge to the graph.
1.243 ///
1.244 - Node addNode() { return INVALID;}
1.245 - ///Add a new edge to the graph.
1.246 -
1.247 - ///Add a new edge to the graph with tail node \c tail
1.248 - ///and head node \c head.
1.249 - ///\return the new edge.
1.250 - Edge addEdge(Node tail, Node head) { return INVALID;}
1.251 + /// Add a new edge to the graph with tail node \c tail
1.252 + /// and head node \c head.
1.253 + /// \return the new edge.
1.254 + Edge addEdge(const Node& tail, const Node& head) { return INVALID; }
1.255
1.256 - /// Resets the graph.
1.257 -
1.258 + /// \brief Resets the graph.
1.259 + ///
1.260 /// This function deletes all edges and nodes of the graph.
1.261 /// It also frees the memory allocated to store them.
1.262 - void clear() {}
1.263 + /// \todo What happens with the maps?
1.264 + void clear() { }
1.265
1.266 - ///Read/write/reference map of the nodes to type \c T.
1.267 + /// Read/write/reference map of the nodes to type \c T.
1.268
1.269 - ///Read/write/reference map of the nodes to type \c T.
1.270 - /// \sa MemoryMapSkeleturo
1.271 + /// Read/write/reference map of the nodes to type \c T.
1.272 + /// \sa MemoryMapConcept
1.273 /// \todo We may need copy constructor
1.274 /// \todo We may need conversion from other nodetype
1.275 /// \todo We may need operator=
1.276 @@ -232,10 +170,10 @@
1.277 typedef T ValueType;
1.278 typedef Node KeyType;
1.279
1.280 - NodeMap(const GraphSkeleturo &G) {}
1.281 - NodeMap(const GraphSkeleturo &G, T t) {}
1.282 + NodeMap(const GraphConcept& g) { }
1.283 + NodeMap(const GraphConcept& g, T t) { }
1.284
1.285 - template<typename TT> NodeMap(const NodeMap<TT> &m) {}
1.286 + template<typename TT> NodeMap(const NodeMap<TT>& m) { }
1.287
1.288 /// Sets the value of a node.
1.289
1.290 @@ -251,16 +189,16 @@
1.291
1.292 /// \todo Do we need this?
1.293 ///
1.294 - void update() {}
1.295 - void update(T a) {} //FIXME: Is it necessary
1.296 + void update() { }
1.297 + //void update(T a) { } //FIXME: Is it necessary
1.298 };
1.299
1.300 ///Read/write/reference map of the edges to type \c T.
1.301
1.302 - ///Read/write/reference map of the edges to type \c T.
1.303 - ///It behaves exactly in the same way as \ref NodeMap.
1.304 + /// Read/write/reference map of the edges to type \c T.
1.305 + /// It behaves exactly in the same way as \ref NodeMap.
1.306 /// \sa NodeMap
1.307 - /// \sa MemoryMapSkeleturo
1.308 + /// \sa MemoryMapConcept
1.309 /// \todo We may need copy constructor
1.310 /// \todo We may need conversion from other edgetype
1.311 /// \todo We may need operator=
1.312 @@ -270,174 +208,260 @@
1.313 typedef T ValueType;
1.314 typedef Edge KeyType;
1.315
1.316 - EdgeMap(const GraphSkeleturo &G) {}
1.317 - EdgeMap(const GraphSkeleturo &G, T t) {}
1.318 + EdgeMap(const GraphConcept& g) {}
1.319 + EdgeMap(const GraphConcept& g, T t) {}
1.320
1.321 void set(Edge i, T t) {}
1.322 T get(Edge i) const {return *(T*)0;}
1.323 T &operator[](Edge i) {return *(T*)0;}
1.324
1.325 - void update() {}
1.326 - void update(T a) {} //FIXME: Is it necessary
1.327 + void update() { }
1.328 + //void update(T a) { } //FIXME: Is it necessary
1.329 };
1.330 };
1.331
1.332 - /// An empty eraseable graph class.
1.333 -
1.334 - /// This class provides all the common features of an \e eraseable graph
1.335 - /// structure,
1.336 - /// however completely without implementations and real data structures
1.337 - /// behind the interface.
1.338 - /// All graph algorithms should compile with this class, but it will not
1.339 - /// run properly, of course.
1.340 +
1.341 + /// \brief Node-iterable graph concept.
1.342 ///
1.343 - /// \todo This blabla could be replaced by a sepatate description about
1.344 - /// Skeleturos.
1.345 - ///
1.346 - /// It can be used for checking the interface compatibility,
1.347 - /// or it can serve as a skeleton of a new graph structure.
1.348 - ///
1.349 - /// Also, you will find here the full documentation of a certain graph
1.350 - /// feature, the documentation of a real graph imlementation
1.351 - /// like @ref ListGraph or
1.352 - /// @ref SmartGraph will just refer to this structure.
1.353 - class EraseableGraphSkeleturo : public GraphSkeleturo
1.354 - {
1.355 - public:
1.356 - /// Deletes a node.
1.357 - void erase(Node n) {}
1.358 - /// Deletes an edge.
1.359 - void erase(Edge e) {}
1.360 -
1.361 - /// Defalult constructor.
1.362 - GraphSkeleturo() {}
1.363 - ///Copy consructor.
1.364 - GraphSkeleturo(const GraphSkeleturo &G) {}
1.365 - };
1.366 -
1.367 - /// An empty out-edge-iterable graph class.
1.368 -
1.369 - /// An empty graph class which provides a function to
1.370 - /// iterate on out-edges of any node.
1.371 - class OutEdgeIterableGraphSkeleturo : public GraphSkeleturo
1.372 + /// A graph class which provides functions to
1.373 + /// iterate on its nodes.
1.374 + class NodeIterableGraphConcept : virtual public GraphConcept
1.375 {
1.376 public:
1.377
1.378 - /// This iterator goes trough the outgoing edges of a node.
1.379 + /// \brief This iterator goes trough the nodes of the graph.
1.380 + ///
1.381 + /// This iterator goes trough the \e nodes of the graph.
1.382 + /// Its usage is quite simple, for example you can count the number
1.383 + /// of nodes in graph \c g of type \c Graph as follows.
1.384 + /// \code
1.385 + /// int count=0;
1.386 + /// for(Graph::NodeIt n(g); g.valid(n); g.next(n)) ++count;
1.387 + /// \endcode
1.388 + class NodeIt : public Node {
1.389 + public:
1.390 + /// @warning The default constructor sets the iterator.
1.391 + /// to an undefined value.
1.392 + NodeIt() { }
1.393 + // /// Copy constructor
1.394 + //NodeIt(const NodeIt& n) { }
1.395 + /// Initialize the iterator to be invalid.
1.396 + NodeIt(const Invalid&) { }
1.397 + /// \brief This constructor sets the iterator to first node.
1.398 + ///
1.399 + /// This constructor set the iterator to the first
1.400 + /// node of the graph \c g.
1.401 + ///
1.402 + ///@param g the graph
1.403 + NodeIt(const GraphConcept& g) { }
1.404 + };
1.405
1.406 + /// The first node.
1.407 + NodeIt &first(NodeIt &i) const { return i; }
1.408 +
1.409 + /// Go to the next node.
1.410 + NodeIt &next(NodeIt &i) const { return i; }
1.411 + };
1.412 +
1.413 +
1.414 + /// \brief Edge-iterable graph concept.
1.415 + ///
1.416 + /// A graph class which provides functions to
1.417 + /// iterate on its edges.
1.418 + class EdgeIterableGraphConcept : virtual public GraphConcept
1.419 + {
1.420 + public:
1.421 +
1.422 + /// \brief This iterator goes trough the edges of the graph.
1.423 + ///
1.424 + /// This iterator goes trough the \e edges of the graph.
1.425 + /// Its usage is quite simple, for example you can count the number
1.426 + /// of edges in graph \c g of type \c Graph as follows.
1.427 + /// \code
1.428 + /// int count=0;
1.429 + /// for(Graph::EdgeIt e(g); g.valid(e); g.next(e)) ++count;
1.430 + /// \endcode
1.431 + class EdgeIt : public Edge {
1.432 + public:
1.433 + /// @warning The default constructor sets the iterator.
1.434 + /// to an undefined value.
1.435 + EdgeIt() { }
1.436 + // /// Copy constructor
1.437 + // EdgeIt(const EdgeIt&) { }
1.438 + /// Initialize the iterator to be invalid.
1.439 + EdgeIt(const Invalid&) { }
1.440 + /// \brief This constructor sets the iterator to first edge.
1.441 + ///
1.442 + /// This constructor set the iterator to the first
1.443 + /// edge of the graph \c g.
1.444 + ///
1.445 + ///@param g the graph
1.446 + EdgeIt(const GraphConcept& g) { }
1.447 + };
1.448 +
1.449 + /// The first edge.
1.450 + EdgeIt &first(EdgeIt &i) const { return i; }
1.451 +
1.452 + /// Go to the next edge.
1.453 + EdgeIt &next(EdgeIt &i) const { return i; }
1.454 + };
1.455 +
1.456 +
1.457 + /// \brief Out-edge-iterable graph concept.
1.458 + ///
1.459 + /// A graph class which provides functions to
1.460 + /// iterate on out-edges of any node.
1.461 + class OutEdgeIterableGraphConcept : virtual public GraphConcept
1.462 + {
1.463 + public:
1.464 +
1.465 + /// \brief This iterator goes trough the outgoing edges of a node.
1.466 + ///
1.467 /// This iterator goes trough the \e outgoing edges of a certain node
1.468 /// of a graph.
1.469 /// Its usage is quite simple, for example you can count the number
1.470 /// of outgoing edges of a node \c n
1.471 - /// in graph \c G of type \c Graph as follows.
1.472 + /// in graph \c g of type \c Graph as follows.
1.473 /// \code
1.474 - ///int count=0;
1.475 - ///for(Graph::OutEdgeIt e(G,n); G.valid(e); G.next(e)) ++count;
1.476 + /// int count=0;
1.477 + /// for(Graph::OutEdgeIt e(g, n); g.valid(e); g.next(e)) ++count;
1.478 /// \endcode
1.479 class OutEdgeIt : public Edge {
1.480 public:
1.481 - /// @warning The default constructor sets the iterator
1.482 + /// @warning The default constructor sets the iterator.
1.483 /// to an undefined value.
1.484 - OutEdgeIt() {}
1.485 - /// Initialize the iterator to be invalid
1.486 - OutEdgeIt(Invalid) {}
1.487 - /// This constructor sets the iterator to first outgoing edge.
1.488 -
1.489 + OutEdgeIt() { }
1.490 + /// Initialize the iterator to be invalid.
1.491 + OutEdgeIt(const Invalid&) { }
1.492 + /// \brief This constructor sets the iterator to first outgoing edge.
1.493 + ///
1.494 /// This constructor set the iterator to the first outgoing edge of
1.495 /// node
1.496 ///@param n the node
1.497 - ///@param G the graph
1.498 - OutEdgeIt(const GraphSkeleturo & G, Node n) {}
1.499 + ///@param g the graph
1.500 + OutEdgeIt(const GraphConcept& g, const Node& n) { }
1.501 };
1.502 +
1.503 + /// The first outgoing edge.
1.504 + OutEdgeIt &first(OutEdgeIt &i, const Node& n) const { return i; }
1.505 +
1.506 + /// Go to the next outgoing edge.
1.507 + OutEdgeIt &next(OutEdgeIt &i) const { return i; }
1.508 +
1.509 + Node aNode(const OutEdgeIt&) const { return Node(); }
1.510 + Node bNode(const OutEdgeIt&) const { return Node(); }
1.511 };
1.512
1.513 - /// An empty in-edge-iterable graph class.
1.514 -
1.515 - /// An empty graph class which provides a function to
1.516 +
1.517 + /// \brief In-edge-iterable graph concept.
1.518 + ///
1.519 + /// A Graph class which provides a function to
1.520 /// iterate on in-edges of any node.
1.521 - class InEdgeIterableGraphSkeleturo : public GraphSkeleturo
1.522 + class InEdgeIterableGraphConcept : virtual public GraphConcept
1.523 {
1.524 public:
1.525
1.526 - /// This iterator goes trough the incoming edges of a node.
1.527 -
1.528 + /// \brief This iterator goes trough the incoming edges of a node.
1.529 + ///
1.530 /// This iterator goes trough the \e incoming edges of a certain node
1.531 /// of a graph.
1.532 /// Its usage is quite simple, for example you can count the number
1.533 /// of incoming edges of a node \c n
1.534 - /// in graph \c G of type \c Graph as follows.
1.535 + /// in graph \c g of type \c Graph as follows.
1.536 /// \code
1.537 - ///int count=0;
1.538 - ///for(Graph::InEdgeIt e(G,n); G.valid(e); G.next(e)) ++count;
1.539 + /// int count=0;
1.540 + /// for(Graph::InEdgeIt e(g, n); g.valid(e); g.next(e)) ++count;
1.541 /// \endcode
1.542 class InEdgeIt : public Edge {
1.543 public:
1.544 /// @warning The default constructor sets the iterator
1.545 /// to an undefined value.
1.546 - InEdgeIt() {}
1.547 + InEdgeIt() { }
1.548 /// Initialize the iterator to be invalid
1.549 - InEdgeIt(Invalid) {}
1.550 - /// This constructor sets the iterator to first incomig edge.
1.551 -
1.552 + InEdgeIt(const Invalid&) { }
1.553 + /// \brief This constructor sets the iterator to first incomig edge.
1.554 + ///
1.555 /// This constructor set the iterator to the first incomig edge of
1.556 /// node
1.557 ///@param n the node
1.558 - ///@param G the graph
1.559 - InEdgeIt(const GraphSkeleturo & G, Node n) {}
1.560 + ///@param g the graph
1.561 + InEdgeIt(const GraphConcept& g, const Node& n) { }
1.562 };
1.563 +
1.564 + /// The first incoming edge.
1.565 + InEdgeIt &first(InEdgeIt &i, const Node& n) const { return i; }
1.566 +
1.567 + /// Go to the next incoming edge.
1.568 + InEdgeIt &next(InEdgeIt &i) const { return i; }
1.569 +
1.570 + Node aNode(const InEdgeIt&) const { return Node(); }
1.571 + Node bNode(const InEdgeIt&) const { return Node(); }
1.572 };
1.573
1.574
1.575 - /// An empty node-eraseable graph class.
1.576 -
1.577 - /// An empty graph class which provides a function to
1.578 + /// \brief Node-eraseable graph concept.
1.579 + ///
1.580 + /// A graph class which provides a function to
1.581 /// delete any of its nodes.
1.582 - class NodeEraseableGraphSkeleturo : public GraphSkeleturo
1.583 + class NodeEraseableGraphConcept : virtual public GraphConcept
1.584 {
1.585 public:
1.586 /// Deletes a node.
1.587 - void erase(Node n) {}
1.588 + void erase(const Node& n) { }
1.589 };
1.590
1.591 - /// An empty edge-eraseable graph class.
1.592 -
1.593 - /// An empty graph class which provides a function to delete any
1.594 +
1.595 + /// \brief Edge-eraseable graph concept.
1.596 + ///
1.597 + /// A graph class which provides a function to delete any
1.598 /// of its edges.
1.599 - class EdgeEraseableGraphSkeleturo : public GraphSkeleturo
1.600 + class EdgeEraseableGraphConcept : virtual public GraphConcept
1.601 {
1.602 public:
1.603 /// Deletes a node.
1.604 - void erase(Edge n) {}
1.605 + void erase(const Edge& n) { }
1.606 };
1.607
1.608 - /// An empty graph class which provides a function to get the number of its nodes.
1.609 -
1.610 +
1.611 + /// \brief An empty graph class which provides a function to
1.612 + /// get the number of its nodes.
1.613 + ///
1.614 /// This graph class provides a function for getting the number of its
1.615 /// nodes.
1.616 /// Clearly, for physical graph structures it can be expected to have such a
1.617 /// function. For wrappers or graphs which are given in an implicit way,
1.618 /// the implementation can be circumstantial, that is why this composes a
1.619 /// separate concept.
1.620 - class NodeCountingGraphSkeleturo : public GraphSkeleturo
1.621 + class NodeCountingGraphConcept : virtual public GraphConcept
1.622 {
1.623 public:
1.624 /// Returns the number of nodes.
1.625 - int nodeNum() const { return 0;}
1.626 + int nodeNum() const { return 0; }
1.627 };
1.628
1.629 - /// An empty graph class which provides a function to get the number of its edges.
1.630 -
1.631 +
1.632 + /// \brief An empty graph class which provides a function to
1.633 + /// get the number of its edges.
1.634 + ///
1.635 /// This graph class provides a function for getting the number of its
1.636 /// edges.
1.637 /// Clearly, for physical graph structures it can be expected to have such a
1.638 /// function. For wrappers or graphs which are given in an implicit way,
1.639 /// the implementation can be circumstantial, that is why this composes a
1.640 /// separate concept.
1.641 - class EdgeCountingGraphSkeleturo : public GraphSkeleturo
1.642 + class EdgeCountingGraphConcept : virtual public GraphConcept
1.643 {
1.644 public:
1.645 /// Returns the number of edges.
1.646 - int edgeNum() const { return 0;}
1.647 + int edgeNum() const { return 0; }
1.648 + };
1.649 +
1.650 + class FullFeatureGraphConcept : public NodeIterableGraphConcept,
1.651 + public EdgeIterableGraphConcept,
1.652 + public OutEdgeIterableGraphConcept,
1.653 + public InEdgeIterableGraphConcept {
1.654 + public:
1.655 + FullFeatureGraphConcept() { }
1.656 };
1.657
1.658 /// @}
1.659 @@ -446,7 +470,7 @@
1.660
1.661
1.662
1.663 -// class EmptyBipGraph : public Graph Skeleturo
1.664 +// class EmptyBipGraph : public Graph Concept
1.665 // {
1.666 // class ANode {};
1.667 // class BNode {};
2.1 --- a/src/work/marci/makefile Thu May 20 15:40:59 2004 +0000
2.2 +++ b/src/work/marci/makefile Thu May 20 16:57:18 2004 +0000
2.3 @@ -4,7 +4,7 @@
2.4 INCLUDEDIRS ?= -I../.. -I.. -I../{marci,jacint,alpar,klao,akos,athos} -I$(BOOSTROOT)
2.5
2.6 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
2.7 -BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_3 top_sort_test max_flow_1
2.8 +BINARIES = proba6 max_flow_demo iterator_bfs_demo macro_test lg_vs_sg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_3 top_sort_test max_flow_1
2.9 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
2.10
2.11 include ../makefile
3.1 --- a/src/work/marci/max_flow_demo.cc Thu May 20 15:40:59 2004 +0000
3.2 +++ b/src/work/marci/max_flow_demo.cc Thu May 20 16:57:18 2004 +0000
3.3 @@ -10,6 +10,7 @@
3.4 #include <max_flow.h>
3.5 //#include <preflow_res.h>
3.6 #include <hugo/for_each_macros.h>
3.7 +#include <graph_concept.h>
3.8
3.9 using namespace hugo;
3.10
3.11 @@ -36,6 +37,7 @@
3.12
3.13 typedef SageGraph MutableGraph;
3.14
3.15 + //typedef FullFeatureGraphConcept Graph;
3.16 typedef SmartGraph Graph;
3.17 // typedef SageGraph Graph;
3.18 typedef Graph::Node Node;