1.1 --- a/src/work/marci/graph_concept.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,494 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#ifndef LEMON_GRAPH_H
1.6 -#define LEMON_GRAPH_H
1.7 -
1.8 -///\file
1.9 -///\brief Declaration of GraphConcept.
1.10 -
1.11 -#include <lemon/invalid.h>
1.12 -
1.13 -namespace lemon {
1.14 -
1.15 - /// @defgroup empty_graph The GraphConcept class
1.16 - /// @{
1.17 -
1.18 - /// An empty graph class.
1.19 -
1.20 - /// This class provides all the common features of a graph structure,
1.21 - /// however completely without implementations and real data structures
1.22 - /// behind the interface.
1.23 - /// All graph algorithms should compile with this class, but it will not
1.24 - /// run properly, of course.
1.25 - ///
1.26 - /// It can be used for checking the interface compatibility,
1.27 - /// or it can serve as a skeleton of a new graph structure.
1.28 - ///
1.29 - /// Also, you will find here the full documentation of a certain graph
1.30 - /// feature, the documentation of a real graph imlementation
1.31 - /// like @ref ListGraph or
1.32 - /// @ref SmartGraph will just refer to this structure.
1.33 - class GraphConcept
1.34 - {
1.35 - public:
1.36 - /// Defalult constructor.
1.37 - GraphConcept() { }
1.38 -
1.39 - /// \brief Copy consructor.
1.40 - ///
1.41 - /// \todo It is not clear, what we expect from a copy constructor.
1.42 - /// E.g. How to assign the nodes/edges to each other? What about maps?
1.43 - GraphConcept(const GraphConcept&) { }
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 -
1.56 - // /// Copy constructor.
1.57 - // Node(const Node&) { }
1.58 -
1.59 - /// \brief Invalid constructor \& conversion.
1.60 - ///
1.61 - /// This constructor initializes the iterator to be invalid.
1.62 - /// \sa Invalid for more details.
1.63 - Node(const Invalid&) { }
1.64 -
1.65 - /// Two iterators are equal if and only if they point to the
1.66 - /// same object or both are invalid.
1.67 - bool operator==(Node n) const { return true; }
1.68 -
1.69 - /// \sa \ref operator==(Node n)
1.70 - ///
1.71 - bool operator!=(Node n) const { return true; }
1.72 -
1.73 - bool operator<(Node n) const { return true; }
1.74 - };
1.75 -
1.76 - /// The base type of the edge iterators.
1.77 - class Edge {
1.78 - public:
1.79 - /// @warning The default constructor sets the iterator
1.80 - /// to an undefined value.
1.81 - Edge() { } //FIXME
1.82 -
1.83 - // /// Copy constructor.
1.84 - // Edge(const Edge&) { }
1.85 -
1.86 - /// Initialize the iterator to be invalid
1.87 - Edge(const Invalid&) { }
1.88 - /// Two iterators are equal if and only if they point to the
1.89 - /// same object or both are invalid.
1.90 - bool operator==(Edge n) const { return true; }
1.91 - bool operator!=(Edge n) const { return true; }
1.92 - bool operator<(Edge n) const { return true; }
1.93 - };
1.94 -
1.95 - // class SymEdgeIt : public Edge {};
1.96 -
1.97 -
1.98 - // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
1.99 -
1.100 -// Node getNext(Node) const {}
1.101 -// InEdgeIt getNext(InEdgeIt) const {}
1.102 -// OutEdgeIt getNext(OutEdgeIt) const {}
1.103 -// //SymEdgeIt getNext(SymEdgeIt) const {}
1.104 -// EdgeIt getNext(EdgeIt) const {}
1.105 -
1.106 - //SymEdgeIt &next(SymEdgeIt &) const {}
1.107 -
1.108 -
1.109 - /// Gives back the target node of an edge.
1.110 - Node target(const Edge&) const { return INVALID; }
1.111 - /// Gives back the source node of an edge.
1.112 - Node source(const Edge&) const { return INVALID; }
1.113 -
1.114 - // Node aNode(SymEdgeIt) const {}
1.115 - // Node bNode(SymEdgeIt) const {}
1.116 -
1.117 - /// \brief Checks if a node iterator is valid
1.118 - ///
1.119 - /// \todo Maybe, it would be better if iterator converted to
1.120 - /// bool directly, as Jacint prefers.
1.121 - bool valid(const Node&) const { return true; }
1.122 - /// \brief Checks if an edge iterator is valid
1.123 - ///
1.124 - /// \todo Maybe, it would be better if iterator converted to
1.125 - /// bool directly, as Jacint prefers.
1.126 - bool valid(const Edge&) const { return true; }
1.127 -
1.128 - /// \brief Gives back the \e id of a node.
1.129 - ///
1.130 - /// \warning Not all graph structures provide this feature.
1.131 - ///
1.132 - int id(const Node&) const { return 0; }
1.133 - /// \brief Gives back the \e id of an edge.
1.134 - ///
1.135 - /// \warning Not all graph structures provide this feature.
1.136 - ///
1.137 - int id(const Edge&) const { return 0; }
1.138 -
1.139 - //void setInvalid(Node &) const {};
1.140 - //void setInvalid(Edge &) const {};
1.141 -
1.142 - /// \brief Add a new node to the graph.
1.143 - ///
1.144 - /// \return the new node.
1.145 - Node addNode() { return INVALID; }
1.146 - /// \brief Add a new edge to the graph.
1.147 - ///
1.148 - /// Add a new edge to the graph with source node \c source
1.149 - /// and target node \c target.
1.150 - /// \return the new edge.
1.151 - Edge addEdge(const Node& source, const Node& target) { return INVALID; }
1.152 -
1.153 - /// \brief Resets the graph.
1.154 - ///
1.155 - /// This function deletes all edges and nodes of the graph.
1.156 - /// It also frees the memory allocated to store them.
1.157 - /// \todo What happens with the maps?
1.158 - void clear() { }
1.159 -
1.160 - /// Read/write/reference map of the nodes to type \c T.
1.161 -
1.162 - /// Read/write/reference map of the nodes to type \c T.
1.163 - /// \sa MemoryMapConcept
1.164 - /// \todo We may need copy constructor
1.165 - /// \todo We may need conversion from other nodetype
1.166 - /// \todo We may need operator=
1.167 - /// \warning Making maps that can handle bool type (NodeMap<bool>)
1.168 - /// needs extra attention!
1.169 -
1.170 - template<class T> class NodeMap
1.171 - {
1.172 - public:
1.173 - typedef T Value;
1.174 - typedef Node Key;
1.175 -
1.176 - NodeMap(const GraphConcept& g) { }
1.177 - NodeMap(const GraphConcept& g, T t) { }
1.178 -
1.179 - template<typename TT> NodeMap(const NodeMap<TT>& m) { }
1.180 -
1.181 - /// Sets the value of a node.
1.182 -
1.183 - /// Sets the value associated with node \c i to the value \c t.
1.184 - ///
1.185 - void set(Node i, T t) {}
1.186 - /// Gets the value of a node.
1.187 - T get(Node i) const {return *(T*)0;} //FIXME: Is it necessary
1.188 - T &operator[](Node i) {return *(T*)0;}
1.189 - const T &operator[](Node i) const {return *(T*)0;}
1.190 -
1.191 - /// Updates the map if the graph has been changed
1.192 -
1.193 - /// \todo Do we need this?
1.194 - ///
1.195 - void update() { }
1.196 - //void update(T a) { } //FIXME: Is it necessary
1.197 - };
1.198 -
1.199 - ///Read/write/reference map of the edges to type \c T.
1.200 -
1.201 - /// Read/write/reference map of the edges to type \c T.
1.202 - /// It behaves exactly in the same way as \ref NodeMap.
1.203 - /// \sa NodeMap
1.204 - /// \sa MemoryMapConcept
1.205 - /// \todo We may need copy constructor
1.206 - /// \todo We may need conversion from other edgetype
1.207 - /// \todo We may need operator=
1.208 - template<class T> class EdgeMap
1.209 - {
1.210 - public:
1.211 - typedef T Value;
1.212 - typedef Edge Key;
1.213 -
1.214 - EdgeMap(const GraphConcept& g) {}
1.215 - EdgeMap(const GraphConcept& g, T t) {}
1.216 -
1.217 - void set(Edge i, T t) {}
1.218 - T get(Edge i) const {return *(T*)0;}
1.219 - T &operator[](Edge i) {return *(T*)0;}
1.220 -
1.221 - void update() { }
1.222 - //void update(T a) { } //FIXME: Is it necessary
1.223 - };
1.224 - };
1.225 -
1.226 -
1.227 - /// \brief Node-iterable graph concept.
1.228 - ///
1.229 - /// A graph class which provides functions to
1.230 - /// iterate on its nodes.
1.231 - class NodeIterableGraphConcept : virtual public GraphConcept
1.232 - {
1.233 - public:
1.234 -
1.235 - /// \brief This iterator goes trough the nodes of the graph.
1.236 - ///
1.237 - /// This iterator goes trough the \e nodes of the graph.
1.238 - /// Its usage is quite simple, for example you can count the number
1.239 - /// of nodes in graph \c g of type \c Graph as follows.
1.240 - /// \code
1.241 - /// int count=0;
1.242 - /// for(Graph::NodeIt n(g); g.valid(n); g.next(n)) ++count;
1.243 - /// \endcode
1.244 - class NodeIt : public Node {
1.245 - public:
1.246 - /// @warning The default constructor sets the iterator.
1.247 - /// to an undefined value.
1.248 - NodeIt() { }
1.249 - // /// Copy constructor
1.250 - //NodeIt(const NodeIt& n) { }
1.251 - /// Initialize the iterator to be invalid.
1.252 - NodeIt(const Invalid&) { }
1.253 - /// \brief This constructor sets the iterator to first node.
1.254 - ///
1.255 - /// This constructor set the iterator to the first
1.256 - /// node of the graph \c g.
1.257 - ///
1.258 - ///@param g the graph
1.259 - NodeIt(const GraphConcept& g) { }
1.260 - };
1.261 -
1.262 - /// The first node.
1.263 - NodeIt &first(NodeIt &i) const { return i; }
1.264 -
1.265 - /// Go to the next node.
1.266 - NodeIt &next(NodeIt &i) const { return i; }
1.267 - };
1.268 -
1.269 -
1.270 - /// \brief Edge-iterable graph concept.
1.271 - ///
1.272 - /// A graph class which provides functions to
1.273 - /// iterate on its edges.
1.274 - class EdgeIterableGraphConcept : virtual public GraphConcept
1.275 - {
1.276 - public:
1.277 -
1.278 - /// \brief This iterator goes trough the edges of the graph.
1.279 - ///
1.280 - /// This iterator goes trough the \e edges of the graph.
1.281 - /// Its usage is quite simple, for example you can count the number
1.282 - /// of edges in graph \c g of type \c Graph as follows.
1.283 - /// \code
1.284 - /// int count=0;
1.285 - /// for(Graph::EdgeIt e(g); g.valid(e); g.next(e)) ++count;
1.286 - /// \endcode
1.287 - class EdgeIt : public Edge {
1.288 - public:
1.289 - /// @warning The default constructor sets the iterator.
1.290 - /// to an undefined value.
1.291 - EdgeIt() { }
1.292 - // /// Copy constructor
1.293 - // EdgeIt(const EdgeIt&) { }
1.294 - /// Initialize the iterator to be invalid.
1.295 - EdgeIt(const Invalid&) { }
1.296 - /// \brief This constructor sets the iterator to first edge.
1.297 - ///
1.298 - /// This constructor set the iterator to the first
1.299 - /// edge of the graph \c g.
1.300 - ///
1.301 - ///@param g the graph
1.302 - EdgeIt(const GraphConcept& g) { }
1.303 - };
1.304 -
1.305 - /// The first edge.
1.306 - EdgeIt &first(EdgeIt &i) const { return i; }
1.307 -
1.308 - /// Go to the next edge.
1.309 - EdgeIt &next(EdgeIt &i) const { return i; }
1.310 - };
1.311 -
1.312 -
1.313 - /// \brief Out-edge-iterable graph concept.
1.314 - ///
1.315 - /// A graph class which provides functions to
1.316 - /// iterate on out-edges of any node.
1.317 - class OutEdgeIterableGraphConcept : virtual public GraphConcept
1.318 - {
1.319 - public:
1.320 -
1.321 - /// \brief This iterator goes trough the outgoing edges of a node.
1.322 - ///
1.323 - /// This iterator goes trough the \e outgoing edges of a certain node
1.324 - /// of a graph.
1.325 - /// Its usage is quite simple, for example you can count the number
1.326 - /// of outgoing edges of a node \c n
1.327 - /// in graph \c g of type \c Graph as follows.
1.328 - /// \code
1.329 - /// int count=0;
1.330 - /// for(Graph::OutEdgeIt e(g, n); g.valid(e); g.next(e)) ++count;
1.331 - /// \endcode
1.332 - class OutEdgeIt : public Edge {
1.333 - public:
1.334 - /// @warning The default constructor sets the iterator.
1.335 - /// to an undefined value.
1.336 - OutEdgeIt() { }
1.337 - /// Initialize the iterator to be invalid.
1.338 - OutEdgeIt(const Invalid&) { }
1.339 - /// \brief This constructor sets the iterator to first outgoing edge.
1.340 - ///
1.341 - /// This constructor set the iterator to the first outgoing edge of
1.342 - /// node
1.343 - ///@param n the node
1.344 - ///@param g the graph
1.345 - OutEdgeIt(const GraphConcept& g, const Node& n) { }
1.346 - };
1.347 -
1.348 - /// The first outgoing edge.
1.349 - OutEdgeIt &first(OutEdgeIt &i, const Node& n) const { return i; }
1.350 -
1.351 - /// Go to the next outgoing edge.
1.352 - OutEdgeIt &next(OutEdgeIt &i) const { return i; }
1.353 -
1.354 - Node aNode(const OutEdgeIt&) const { return Node(); }
1.355 - Node bNode(const OutEdgeIt&) const { return Node(); }
1.356 - };
1.357 -
1.358 -
1.359 - /// \brief In-edge-iterable graph concept.
1.360 - ///
1.361 - /// A Graph class which provides a function to
1.362 - /// iterate on in-edges of any node.
1.363 - class InEdgeIterableGraphConcept : virtual public GraphConcept
1.364 - {
1.365 - public:
1.366 -
1.367 - /// \brief This iterator goes trough the incoming edges of a node.
1.368 - ///
1.369 - /// This iterator goes trough the \e incoming edges of a certain node
1.370 - /// of a graph.
1.371 - /// Its usage is quite simple, for example you can count the number
1.372 - /// of incoming edges of a node \c n
1.373 - /// in graph \c g of type \c Graph as follows.
1.374 - /// \code
1.375 - /// int count=0;
1.376 - /// for(Graph::InEdgeIt e(g, n); g.valid(e); g.next(e)) ++count;
1.377 - /// \endcode
1.378 - class InEdgeIt : public Edge {
1.379 - public:
1.380 - /// @warning The default constructor sets the iterator
1.381 - /// to an undefined value.
1.382 - InEdgeIt() { }
1.383 - /// Initialize the iterator to be invalid
1.384 - InEdgeIt(const Invalid&) { }
1.385 - /// \brief This constructor sets the iterator to first incomig edge.
1.386 - ///
1.387 - /// This constructor set the iterator to the first incomig edge of
1.388 - /// node
1.389 - ///@param n the node
1.390 - ///@param g the graph
1.391 - InEdgeIt(const GraphConcept& g, const Node& n) { }
1.392 - };
1.393 -
1.394 - /// The first incoming edge.
1.395 - InEdgeIt &first(InEdgeIt &i, const Node& n) const { return i; }
1.396 -
1.397 - /// Go to the next incoming edge.
1.398 - InEdgeIt &next(InEdgeIt &i) const { return i; }
1.399 -
1.400 - Node aNode(const InEdgeIt&) const { return Node(); }
1.401 - Node bNode(const InEdgeIt&) const { return Node(); }
1.402 - };
1.403 -
1.404 -
1.405 - /// \brief Node-erasable graph concept.
1.406 - ///
1.407 - /// A graph class which provides a function to
1.408 - /// delete any of its nodes.
1.409 - class NodeErasableGraphConcept : virtual public GraphConcept
1.410 - {
1.411 - public:
1.412 - /// Deletes a node.
1.413 - void erase(const Node& n) { }
1.414 - };
1.415 -
1.416 -
1.417 - /// \brief Edge-erasable graph concept.
1.418 - ///
1.419 - /// A graph class which provides a function to delete any
1.420 - /// of its edges.
1.421 - class EdgeErasableGraphConcept : virtual public GraphConcept
1.422 - {
1.423 - public:
1.424 - /// Deletes a node.
1.425 - void erase(const Edge& n) { }
1.426 - };
1.427 -
1.428 -
1.429 - /// \brief An empty graph class which provides a function to
1.430 - /// get the number of its nodes.
1.431 - ///
1.432 - /// This graph class provides a function for getting the number of its
1.433 - /// nodes.
1.434 - /// Clearly, for physical graph structures it can be expected to have such a
1.435 - /// function. For wrappers or graphs which are given in an implicit way,
1.436 - /// the implementation can be circumstantial, that is why this composes a
1.437 - /// separate concept.
1.438 - class NodeCountingGraphConcept : virtual public GraphConcept
1.439 - {
1.440 - public:
1.441 - /// Returns the number of nodes.
1.442 - int nodeNum() const { return 0; }
1.443 - };
1.444 -
1.445 -
1.446 - /// \brief An empty graph class which provides a function to
1.447 - /// get the number of its edges.
1.448 - ///
1.449 - /// This graph class provides a function for getting the number of its
1.450 - /// edges.
1.451 - /// Clearly, for physical graph structures it can be expected to have such a
1.452 - /// function. For wrappers or graphs which are given in an implicit way,
1.453 - /// the implementation can be circumstantial, that is why this composes a
1.454 - /// separate concept.
1.455 - class EdgeCountingGraphConcept : virtual public GraphConcept
1.456 - {
1.457 - public:
1.458 - /// Returns the number of edges.
1.459 - int edgeNum() const { return 0; }
1.460 - };
1.461 -
1.462 - class FullFeatureGraphConcept : virtual public NodeIterableGraphConcept,
1.463 - virtual public EdgeIterableGraphConcept,
1.464 - virtual public OutEdgeIterableGraphConcept,
1.465 - virtual public InEdgeIterableGraphConcept,
1.466 - virtual public NodeCountingGraphConcept {
1.467 - public:
1.468 - FullFeatureGraphConcept() { }
1.469 - using EdgeIterableGraphConcept::next;
1.470 - using NodeIterableGraphConcept::next;
1.471 - using OutEdgeIterableGraphConcept::next;
1.472 - using InEdgeIterableGraphConcept::next;
1.473 - };
1.474 -
1.475 - /// @}
1.476 -
1.477 -} //namespace lemon
1.478 -
1.479 -
1.480 -
1.481 -// class EmptyBipGraph : public Graph Concept
1.482 -// {
1.483 -// class ANode {};
1.484 -// class BNode {};
1.485 -
1.486 -// ANode &next(ANode &) {}
1.487 -// BNode &next(BNode &) {}
1.488 -
1.489 -// ANode &getFirst(ANode &) const {}
1.490 -// BNode &getFirst(BNode &) const {}
1.491 -
1.492 -// enum NodeClass { A = 0, B = 1 };
1.493 -// NodeClass getClass(Node n) {}
1.494 -
1.495 -// }
1.496 -
1.497 -#endif // LEMON_GRAPH_H