# HG changeset patch # User marci # Date 1081976278 0 # Node ID 5fe27632f9ac9d29308af4cc70231f03d1bc6e55 # Parent c8b0ad782bda6299fba82cabb414bbea0397aaf6 kiserletezek a concept-leirassal, skeleton kereteben, ha kesz lesz majd szolok diff -r c8b0ad782bda -r 5fe27632f9ac doc/Doxyfile --- a/doc/Doxyfile Wed Apr 14 16:16:40 2004 +0000 +++ b/doc/Doxyfile Wed Apr 14 20:57:58 2004 +0000 @@ -400,6 +400,7 @@ ../src/include/fib_heap.h \ ../src/work/athos/xy/xy.h \ ../src/work/athos/minlengthpaths.h \ + ../src/work/marci/graph_concept.h \ maps.dox # If the value of the INPUT tag contains directories, you can use the diff -r c8b0ad782bda -r 5fe27632f9ac src/work/marci/graph_concept.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/work/marci/graph_concept.h Wed Apr 14 20:57:58 2004 +0000 @@ -0,0 +1,422 @@ +// -*- c++ -*- +#ifndef HUGO_GRAPH_H +#define HUGO_GRAPH_H + +///\file +///\brief Declaration of GraphSkeleton. + +#include + +/// The namespace of HugoLib +namespace hugo { + + // @defgroup empty_graph The GraphSkeleton class + // @{ + + /// An empty graph class. + + /// This class provides all the common features of a 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. + /// + /// 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 GraphSkeleton + { + public: + /// Defalult constructor. + GraphSkeleton() {} + ///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? + GraphSkeleton(const GraphSkeleton &G) {} + + /// 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. + class Node { + public: + /// @warning The default constructor sets the iterator + /// to an undefined value. + Node() {} //FIXME + /// Invalid constructor \& conversion. + + /// This constructor initializes the iterator to be invalid. + /// \sa Invalid for more details. + + Node(Invalid) {} + //Node(const Node &) {} + + /// 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; } + + /// \sa \ref operator==(Node n) + /// + bool operator!=(Node n) const { return true; } + + 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 GraphSkeleton &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 + /// Initialize the iterator to be invalid + Edge(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; } + bool operator!=(Edge n) const { return true; } + bool operator<(Edge n) const { return true; } + }; + + /// 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. + /// \code + ///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 + /// to an undefined value. + OutEdgeIt() {} + /// Initialize the iterator to be invalid + OutEdgeIt(Invalid) {} + /// 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 GraphSkeleton & G, Node n) {} + }; + + /// 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 outgoing edges of a node \c n + /// 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++; + /// \endcode + + class InEdgeIt : public Edge { + public: + /// @warning The default constructor sets the iterator + /// to an undefined value. + InEdgeIt() {} + /// Initialize the iterator to be invalid + InEdgeIt(Invalid) {} + InEdgeIt(const GraphSkeleton &, Node) {} + }; + // 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 GraphSkeleton &) {} + }; + + /// 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 {} +// OutEdgeIt getNext(OutEdgeIt) const {} +// //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; } + + // 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 + + ///\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. + /// + 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 Edge&) const { return 0;} + + //void setInvalid(Node &) const {}; + //void setInvalid(Edge &) const {}; + + ///Add a new node to the graph. + + /// \return the new node. + /// + 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;} + + /// Resets the graph. + + /// This function deletes all edges and nodes of the graph. + /// It also frees the memory allocated to store them. + void clear() {} + + ///Read/write/reference map of the nodes to type \c T. + + ///Read/write/reference map of the nodes to type \c T. + /// \sa MemoryMapSkeleton + /// \todo We may need copy constructor + /// \todo We may need conversion from other nodetype + /// \todo We may need operator= + /// \warning Making maps that can handle bool type (NodeMap) + /// needs extra attention! + + template class NodeMap + { + public: + typedef T ValueType; + typedef Node KeyType; + + NodeMap(const GraphSkeleton &G) {} + NodeMap(const GraphSkeleton &G, T t) {} + + template NodeMap(const NodeMap &m) {} + + /// Sets the value of a node. + + /// Sets the value associated with node \c i to the value \c t. + /// + void set(Node i, T t) {} + /// Gets the value of a node. + T get(Node i) const {return *(T*)0;} //FIXME: Is it necessary + T &operator[](Node i) {return *(T*)0;} + const T &operator[](Node i) const {return *(T*)0;} + + /// Updates the map if the graph has been changed + + /// \todo Do we need this? + /// + 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. + /// \sa NodeMap + /// \sa MemoryMapSkeleton + /// \todo We may need copy constructor + /// \todo We may need conversion from other edgetype + /// \todo We may need operator= + template class EdgeMap + { + public: + typedef T ValueType; + typedef Edge KeyType; + + EdgeMap(const GraphSkeleton &G) {} + EdgeMap(const GraphSkeleton &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 + }; + }; + + /// 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. + /// + /// \todo This blabla could be replaced by a sepatate description about + /// Skeletons. + /// + /// 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 EraseableGraphSkeleton : public GraphSkeleton + { + public: + /// Deletes a node. + void erase(Node n) {} + /// Deletes an edge. + void erase(Edge e) {} + + /// Defalult constructor. + GraphSkeleton() {} + ///Copy consructor. + GraphSkeleton(const GraphSkeleton &G) {} + }; + + + // @} + + + /// 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 NodeCountingGraphSkeleton + { + public: + /// Returns the number of nodes. + int nodeNum() const { return 0;} + }; + + /// 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 EdgeCountingGraphSkeleton + { + public: + /// Returns the number of edges. + int edgeNum() const { return 0;} + }; + +} //namespace hugo + + +// class EmptyBipGraph : public Graph Skeleton +// { +// class ANode {}; +// class BNode {}; + +// ANode &next(ANode &) {} +// BNode &next(BNode &) {} + +// ANode &getFirst(ANode &) const {} +// BNode &getFirst(BNode &) const {} + +// enum NodeClass { A = 0, B = 1 }; +// NodeClass getClass(Node n) {} + +// } + +#endif // HUGO_GRAPH_H