diff -r 588ff2ca55bd -r a56e043aeab1 src/work/marci/graph_concept.h --- a/src/work/marci/graph_concept.h Thu May 20 15:40:59 2004 +0000 +++ b/src/work/marci/graph_concept.h Thu May 20 16:57:18 2004 +0000 @@ -3,14 +3,13 @@ #define HUGO_GRAPH_H ///\file -///\brief Declaration of GraphSkeleturo. +///\brief Declaration of GraphConcept. -#include +#include -/// The namespace of HugoLib namespace hugo { - /// @defgroup empty_graph The GraphSkeleturo class + /// @defgroup empty_graph The GraphConcept class /// @{ /// An empty graph class. @@ -28,34 +27,38 @@ /// feature, the documentation of a real graph imlementation /// like @ref ListGraph or /// @ref SmartGraph will just refer to this structure. - class GraphSkeleturo + class GraphConcept { public: /// Defalult constructor. - GraphSkeleturo() {} - ///Copy consructor. + GraphConcept() { } - ///\todo It is not clear, what we expect from a copy constructor. - ///E.g. How to assign the nodes/edges to each other? What about maps? - GraphSkeleturo(const GraphSkeleturo &G) {} + /// \brief Copy consructor. + /// + /// \todo It is not clear, what we expect from a copy constructor. + /// E.g. How to assign the nodes/edges to each other? What about maps? + GraphConcept(const GraphConcept&) { } - /// The base type of the node iterators. - + /// \brief The base type of the node iterators. + /// /// This is the base type of each node iterators, /// thus each kind of node iterator will convert to this. + /// Sometimes it is said to be a trivial iterator. class Node { public: /// @warning The default constructor sets the iterator /// to an undefined value. - Node() {} //FIXME - /// Invalid constructor \& conversion. + Node() { } //FIXME + // /// Copy constructor. + // Node(const Node&) { } + + /// \brief Invalid constructor \& conversion. + /// /// This constructor initializes the iterator to be invalid. /// \sa Invalid for more details. - - Node(Invalid) {} - //Node(const Node &) {} - + Node(const Invalid&) { } + /// Two iterators are equal if and only if they point to the /// same object or both are invalid. bool operator==(Node n) const { return true; } @@ -67,41 +70,18 @@ bool operator<(Node n) const { return true; } }; - /// This iterator goes through each node. - - /// This iterator goes through each node. - /// Its usage is quite simple, for example you can count the number - /// of nodes in graph \c G of type \c Graph like this: - /// \code - ///int count=0; - ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++; - /// \endcode - class NodeIt : public Node { - public: - /// @warning The default constructor sets the iterator - /// to an undefined value. - NodeIt() {} //FIXME - /// Invalid constructor \& conversion. - - /// Initialize the iterator to be invalid - /// \sa Invalid for more details. - NodeIt(Invalid) {} - /// Sets the iterator to the first node of \c G. - NodeIt(const GraphSkeleturo &G) {} - /// @warning The default constructor sets the iterator - /// to an undefined value. - NodeIt(const NodeIt &) {} - }; - - /// The base type of the edge iterators. class Edge { public: /// @warning The default constructor sets the iterator /// to an undefined value. - Edge() {} //FIXME + Edge() { } //FIXME + + // /// Copy constructor. + // Edge(const Edge&) { } + /// Initialize the iterator to be invalid - Edge(Invalid) {} + Edge(const Invalid&) { } /// Two iterators are equal if and only if they point to the /// same object or both are invalid. bool operator==(Edge n) const { return true; } @@ -111,38 +91,8 @@ // class SymEdgeIt : public Edge {}; - /// This iterator goes through each edge. - /// This iterator goes through each edge of a graph. - /// Its usage is quite simple, for example you can count the number - /// of edges in a graph \c G of type \c Graph as follows: - /// \code - ///int count=0; - ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++; - /// \endcode - class EdgeIt : public Edge { - public: - /// @warning The default constructor sets the iterator - /// to an undefined value. - EdgeIt() {} - /// Initialize the iterator to be invalid - EdgeIt(Invalid) {} - EdgeIt(const GraphSkeleturo &) {} - }; - - /// First node of the graph. - - /// \post \c i and the return value will be the first node. - /// - NodeIt &first(NodeIt &i) const { return i;} - - /// The first incoming edge. - InEdgeIt &first(InEdgeIt &i, Node n) const { return i;} - /// The first outgoing edge. - OutEdgeIt &first(OutEdgeIt &i, Node n) const { return i;} // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;} - /// The first edge of the Graph. - EdgeIt &first(EdgeIt &i) const { return i;} // Node getNext(Node) const {} // InEdgeIt getNext(InEdgeIt) const {} @@ -150,76 +100,64 @@ // //SymEdgeIt getNext(SymEdgeIt) const {} // EdgeIt getNext(EdgeIt) const {} - /// Go to the next node. - NodeIt &next(NodeIt &i) const { return i;} - /// Go to the next incoming edge. - InEdgeIt &next(InEdgeIt &i) const { return i;} - /// Go to the next outgoing edge. - OutEdgeIt &next(OutEdgeIt &i) const { return i;} //SymEdgeIt &next(SymEdgeIt &) const {} - /// Go to the next edge. - EdgeIt &next(EdgeIt &i) const { return i;} - ///Gives back the head node of an edge. - Node head(Edge) const { return INVALID; } - ///Gives back the tail node of an edge. - Node tail(Edge) const { return INVALID; } + + /// Gives back the head node of an edge. + Node head(const Edge&) const { return INVALID; } + /// Gives back the tail node of an edge. + Node tail(const Edge&) const { return INVALID; } - // Node aNode(InEdgeIt) const {} - // Node aNode(OutEdgeIt) const {} // Node aNode(SymEdgeIt) const {} - - // Node bNode(InEdgeIt) const {} - // Node bNode(OutEdgeIt) const {} // Node bNode(SymEdgeIt) const {} - /// Checks if a node iterator is valid + /// \brief Checks if a node iterator is valid + /// + /// \todo Maybe, it would be better if iterator converted to + /// bool directly, as Jacint prefers. + bool valid(const Node&) const { return true; } + /// \brief Checks if an edge iterator is valid + /// + /// \todo Maybe, it would be better if iterator converted to + /// bool directly, as Jacint prefers. + bool valid(const Edge&) const { return true; } - ///\todo Maybe, it would be better if iterator converted to - ///bool directly, as Jacint prefers. - bool valid(const Node&) const { return true;} - /// Checks if an edge iterator is valid - - ///\todo Maybe, it would be better if iterator converted to - ///bool directly, as Jacint prefers. - bool valid(const Edge&) const { return true;} - - ///Gives back the \e id of a node. - - ///\warning Not all graph structures provide this feature. + /// \brief Gives back the \e id of a node. + /// + /// \warning Not all graph structures provide this feature. /// - int id(const Node&) const { return 0;} - ///Gives back the \e id of an edge. - - ///\warning Not all graph structures provide this feature. + int id(const Node&) const { return 0; } + /// \brief Gives back the \e id of an edge. /// - int id(const Edge&) const { return 0;} + /// \warning Not all graph structures provide this feature. + /// + int id(const Edge&) const { return 0; } //void setInvalid(Node &) const {}; //void setInvalid(Edge &) const {}; - ///Add a new node to the graph. - + /// \brief Add a new node to the graph. + /// /// \return the new node. + Node addNode() { return INVALID; } + /// \brief Add a new edge to the graph. /// - Node addNode() { return INVALID;} - ///Add a new edge to the graph. - - ///Add a new edge to the graph with tail node \c tail - ///and head node \c head. - ///\return the new edge. - Edge addEdge(Node tail, Node head) { return INVALID;} + /// Add a new edge to the graph with tail node \c tail + /// and head node \c head. + /// \return the new edge. + Edge addEdge(const Node& tail, const Node& head) { return INVALID; } - /// Resets the graph. - + /// \brief Resets the graph. + /// /// This function deletes all edges and nodes of the graph. /// It also frees the memory allocated to store them. - void clear() {} + /// \todo What happens with the maps? + void clear() { } - ///Read/write/reference map of the nodes to type \c T. + /// Read/write/reference map of the nodes to type \c T. - ///Read/write/reference map of the nodes to type \c T. - /// \sa MemoryMapSkeleturo + /// Read/write/reference map of the nodes to type \c T. + /// \sa MemoryMapConcept /// \todo We may need copy constructor /// \todo We may need conversion from other nodetype /// \todo We may need operator= @@ -232,10 +170,10 @@ typedef T ValueType; typedef Node KeyType; - NodeMap(const GraphSkeleturo &G) {} - NodeMap(const GraphSkeleturo &G, T t) {} + NodeMap(const GraphConcept& g) { } + NodeMap(const GraphConcept& g, T t) { } - template NodeMap(const NodeMap &m) {} + template NodeMap(const NodeMap& m) { } /// Sets the value of a node. @@ -251,16 +189,16 @@ /// \todo Do we need this? /// - void update() {} - void update(T a) {} //FIXME: Is it necessary + void update() { } + //void update(T a) { } //FIXME: Is it necessary }; ///Read/write/reference map of the edges to type \c T. - ///Read/write/reference map of the edges to type \c T. - ///It behaves exactly in the same way as \ref NodeMap. + /// Read/write/reference map of the edges to type \c T. + /// It behaves exactly in the same way as \ref NodeMap. /// \sa NodeMap - /// \sa MemoryMapSkeleturo + /// \sa MemoryMapConcept /// \todo We may need copy constructor /// \todo We may need conversion from other edgetype /// \todo We may need operator= @@ -270,174 +208,260 @@ typedef T ValueType; typedef Edge KeyType; - EdgeMap(const GraphSkeleturo &G) {} - EdgeMap(const GraphSkeleturo &G, T t) {} + EdgeMap(const GraphConcept& g) {} + EdgeMap(const GraphConcept& g, T t) {} void set(Edge i, T t) {} T get(Edge i) const {return *(T*)0;} T &operator[](Edge i) {return *(T*)0;} - void update() {} - void update(T a) {} //FIXME: Is it necessary + void update() { } + //void update(T a) { } //FIXME: Is it necessary }; }; - /// An empty eraseable graph class. - - /// This class provides all the common features of an \e eraseable graph - /// structure, - /// however completely without implementations and real data structures - /// behind the interface. - /// All graph algorithms should compile with this class, but it will not - /// run properly, of course. + + /// \brief Node-iterable graph concept. /// - /// \todo This blabla could be replaced by a sepatate description about - /// Skeleturos. - /// - /// It can be used for checking the interface compatibility, - /// or it can serve as a skeleton of a new graph structure. - /// - /// Also, you will find here the full documentation of a certain graph - /// feature, the documentation of a real graph imlementation - /// like @ref ListGraph or - /// @ref SmartGraph will just refer to this structure. - class EraseableGraphSkeleturo : public GraphSkeleturo - { - public: - /// Deletes a node. - void erase(Node n) {} - /// Deletes an edge. - void erase(Edge e) {} - - /// Defalult constructor. - GraphSkeleturo() {} - ///Copy consructor. - GraphSkeleturo(const GraphSkeleturo &G) {} - }; - - /// An empty out-edge-iterable graph class. - - /// An empty graph class which provides a function to - /// iterate on out-edges of any node. - class OutEdgeIterableGraphSkeleturo : public GraphSkeleturo + /// A graph class which provides functions to + /// iterate on its nodes. + class NodeIterableGraphConcept : virtual public GraphConcept { public: - /// This iterator goes trough the outgoing edges of a node. + /// \brief This iterator goes trough the nodes of the graph. + /// + /// This iterator goes trough the \e nodes of the graph. + /// Its usage is quite simple, for example you can count the number + /// of nodes in graph \c g of type \c Graph as follows. + /// \code + /// int count=0; + /// for(Graph::NodeIt n(g); g.valid(n); g.next(n)) ++count; + /// \endcode + class NodeIt : public Node { + public: + /// @warning The default constructor sets the iterator. + /// to an undefined value. + NodeIt() { } + // /// Copy constructor + //NodeIt(const NodeIt& n) { } + /// Initialize the iterator to be invalid. + NodeIt(const Invalid&) { } + /// \brief This constructor sets the iterator to first node. + /// + /// This constructor set the iterator to the first + /// node of the graph \c g. + /// + ///@param g the graph + NodeIt(const GraphConcept& g) { } + }; + /// The first node. + NodeIt &first(NodeIt &i) const { return i; } + + /// Go to the next node. + NodeIt &next(NodeIt &i) const { return i; } + }; + + + /// \brief Edge-iterable graph concept. + /// + /// A graph class which provides functions to + /// iterate on its edges. + class EdgeIterableGraphConcept : virtual public GraphConcept + { + public: + + /// \brief This iterator goes trough the edges of the graph. + /// + /// This iterator goes trough the \e edges of the graph. + /// Its usage is quite simple, for example you can count the number + /// of edges in graph \c g of type \c Graph as follows. + /// \code + /// int count=0; + /// for(Graph::EdgeIt e(g); g.valid(e); g.next(e)) ++count; + /// \endcode + class EdgeIt : public Edge { + public: + /// @warning The default constructor sets the iterator. + /// to an undefined value. + EdgeIt() { } + // /// Copy constructor + // EdgeIt(const EdgeIt&) { } + /// Initialize the iterator to be invalid. + EdgeIt(const Invalid&) { } + /// \brief This constructor sets the iterator to first edge. + /// + /// This constructor set the iterator to the first + /// edge of the graph \c g. + /// + ///@param g the graph + EdgeIt(const GraphConcept& g) { } + }; + + /// The first edge. + EdgeIt &first(EdgeIt &i) const { return i; } + + /// Go to the next edge. + EdgeIt &next(EdgeIt &i) const { return i; } + }; + + + /// \brief Out-edge-iterable graph concept. + /// + /// A graph class which provides functions to + /// iterate on out-edges of any node. + class OutEdgeIterableGraphConcept : virtual public GraphConcept + { + public: + + /// \brief This iterator goes trough the outgoing edges of a node. + /// /// This iterator goes trough the \e outgoing edges of a certain node /// of a graph. /// Its usage is quite simple, for example you can count the number /// of outgoing edges of a node \c n - /// in graph \c G of type \c Graph as follows. + /// in graph \c g of type \c Graph as follows. /// \code - ///int count=0; - ///for(Graph::OutEdgeIt e(G,n); G.valid(e); G.next(e)) ++count; + /// int count=0; + /// for(Graph::OutEdgeIt e(g, n); g.valid(e); g.next(e)) ++count; /// \endcode class OutEdgeIt : public Edge { public: - /// @warning The default constructor sets the iterator + /// @warning The default constructor sets the iterator. /// to an undefined value. - OutEdgeIt() {} - /// Initialize the iterator to be invalid - OutEdgeIt(Invalid) {} - /// This constructor sets the iterator to first outgoing edge. - + OutEdgeIt() { } + /// Initialize the iterator to be invalid. + OutEdgeIt(const Invalid&) { } + /// \brief This constructor sets the iterator to first outgoing edge. + /// /// This constructor set the iterator to the first outgoing edge of /// node ///@param n the node - ///@param G the graph - OutEdgeIt(const GraphSkeleturo & G, Node n) {} + ///@param g the graph + OutEdgeIt(const GraphConcept& g, const Node& n) { } }; + + /// The first outgoing edge. + OutEdgeIt &first(OutEdgeIt &i, const Node& n) const { return i; } + + /// Go to the next outgoing edge. + OutEdgeIt &next(OutEdgeIt &i) const { return i; } + + Node aNode(const OutEdgeIt&) const { return Node(); } + Node bNode(const OutEdgeIt&) const { return Node(); } }; - /// An empty in-edge-iterable graph class. - - /// An empty graph class which provides a function to + + /// \brief In-edge-iterable graph concept. + /// + /// A Graph class which provides a function to /// iterate on in-edges of any node. - class InEdgeIterableGraphSkeleturo : public GraphSkeleturo + class InEdgeIterableGraphConcept : virtual public GraphConcept { public: - /// This iterator goes trough the incoming edges of a node. - + /// \brief This iterator goes trough the incoming edges of a node. + /// /// This iterator goes trough the \e incoming edges of a certain node /// of a graph. /// Its usage is quite simple, for example you can count the number /// of incoming edges of a node \c n - /// in graph \c G of type \c Graph as follows. + /// in graph \c g of type \c Graph as follows. /// \code - ///int count=0; - ///for(Graph::InEdgeIt e(G,n); G.valid(e); G.next(e)) ++count; + /// int count=0; + /// for(Graph::InEdgeIt e(g, n); g.valid(e); g.next(e)) ++count; /// \endcode class InEdgeIt : public Edge { public: /// @warning The default constructor sets the iterator /// to an undefined value. - InEdgeIt() {} + InEdgeIt() { } /// Initialize the iterator to be invalid - InEdgeIt(Invalid) {} - /// This constructor sets the iterator to first incomig edge. - + InEdgeIt(const Invalid&) { } + /// \brief This constructor sets the iterator to first incomig edge. + /// /// This constructor set the iterator to the first incomig edge of /// node ///@param n the node - ///@param G the graph - InEdgeIt(const GraphSkeleturo & G, Node n) {} + ///@param g the graph + InEdgeIt(const GraphConcept& g, const Node& n) { } }; + + /// The first incoming edge. + InEdgeIt &first(InEdgeIt &i, const Node& n) const { return i; } + + /// Go to the next incoming edge. + InEdgeIt &next(InEdgeIt &i) const { return i; } + + Node aNode(const InEdgeIt&) const { return Node(); } + Node bNode(const InEdgeIt&) const { return Node(); } }; - /// An empty node-eraseable graph class. - - /// An empty graph class which provides a function to + /// \brief Node-eraseable graph concept. + /// + /// A graph class which provides a function to /// delete any of its nodes. - class NodeEraseableGraphSkeleturo : public GraphSkeleturo + class NodeEraseableGraphConcept : virtual public GraphConcept { public: /// Deletes a node. - void erase(Node n) {} + void erase(const Node& n) { } }; - /// An empty edge-eraseable graph class. - - /// An empty graph class which provides a function to delete any + + /// \brief Edge-eraseable graph concept. + /// + /// A graph class which provides a function to delete any /// of its edges. - class EdgeEraseableGraphSkeleturo : public GraphSkeleturo + class EdgeEraseableGraphConcept : virtual public GraphConcept { public: /// Deletes a node. - void erase(Edge n) {} + void erase(const Edge& n) { } }; - /// An empty graph class which provides a function to get the number of its nodes. - + + /// \brief An empty graph class which provides a function to + /// get the number of its nodes. + /// /// This graph class provides a function for getting the number of its /// nodes. /// Clearly, for physical graph structures it can be expected to have such a /// function. For wrappers or graphs which are given in an implicit way, /// the implementation can be circumstantial, that is why this composes a /// separate concept. - class NodeCountingGraphSkeleturo : public GraphSkeleturo + class NodeCountingGraphConcept : virtual public GraphConcept { public: /// Returns the number of nodes. - int nodeNum() const { return 0;} + int nodeNum() const { return 0; } }; - /// An empty graph class which provides a function to get the number of its edges. - + + /// \brief An empty graph class which provides a function to + /// get the number of its edges. + /// /// This graph class provides a function for getting the number of its /// edges. /// Clearly, for physical graph structures it can be expected to have such a /// function. For wrappers or graphs which are given in an implicit way, /// the implementation can be circumstantial, that is why this composes a /// separate concept. - class EdgeCountingGraphSkeleturo : public GraphSkeleturo + class EdgeCountingGraphConcept : virtual public GraphConcept { public: /// Returns the number of edges. - int edgeNum() const { return 0;} + int edgeNum() const { return 0; } + }; + + class FullFeatureGraphConcept : public NodeIterableGraphConcept, + public EdgeIterableGraphConcept, + public OutEdgeIterableGraphConcept, + public InEdgeIterableGraphConcept { + public: + FullFeatureGraphConcept() { } }; /// @} @@ -446,7 +470,7 @@ -// class EmptyBipGraph : public Graph Skeleturo +// class EmptyBipGraph : public Graph Concept // { // class ANode {}; // class BNode {};