marci@325: // -*- c++ -*- marci@325: #ifndef HUGO_GRAPH_H marci@325: #define HUGO_GRAPH_H marci@325: marci@325: ///\file marci@332: ///\brief Declaration of GraphSkeleturo. marci@325: marci@325: #include marci@325: marci@325: /// The namespace of HugoLib marci@325: namespace hugo { marci@325: marci@332: /// @defgroup empty_graph The GraphSkeleturo class marci@332: /// @{ marci@325: marci@325: /// An empty graph class. marci@325: marci@325: /// This class provides all the common features of a graph structure, marci@325: /// however completely without implementations and real data structures marci@325: /// behind the interface. marci@325: /// All graph algorithms should compile with this class, but it will not marci@325: /// run properly, of course. marci@325: /// marci@325: /// It can be used for checking the interface compatibility, marci@325: /// or it can serve as a skeleton of a new graph structure. marci@325: /// marci@325: /// Also, you will find here the full documentation of a certain graph marci@325: /// feature, the documentation of a real graph imlementation marci@325: /// like @ref ListGraph or marci@325: /// @ref SmartGraph will just refer to this structure. marci@332: class GraphSkeleturo marci@325: { marci@325: public: marci@325: /// Defalult constructor. marci@332: GraphSkeleturo() {} marci@325: ///Copy consructor. marci@325: marci@325: ///\todo It is not clear, what we expect from a copy constructor. marci@325: ///E.g. How to assign the nodes/edges to each other? What about maps? marci@332: GraphSkeleturo(const GraphSkeleturo &G) {} marci@325: marci@325: /// The base type of the node iterators. marci@325: marci@325: /// This is the base type of each node iterators, marci@325: /// thus each kind of node iterator will convert to this. marci@325: class Node { marci@325: public: marci@325: /// @warning The default constructor sets the iterator marci@325: /// to an undefined value. marci@325: Node() {} //FIXME marci@325: /// Invalid constructor \& conversion. marci@325: marci@325: /// This constructor initializes the iterator to be invalid. marci@325: /// \sa Invalid for more details. marci@325: marci@325: Node(Invalid) {} marci@325: //Node(const Node &) {} marci@325: marci@325: /// Two iterators are equal if and only if they point to the marci@325: /// same object or both are invalid. marci@325: bool operator==(Node n) const { return true; } marci@325: marci@325: /// \sa \ref operator==(Node n) marci@325: /// marci@325: bool operator!=(Node n) const { return true; } marci@325: marci@325: bool operator<(Node n) const { return true; } marci@325: }; marci@325: marci@325: /// This iterator goes through each node. marci@325: marci@325: /// This iterator goes through each node. marci@325: /// Its usage is quite simple, for example you can count the number marci@325: /// of nodes in graph \c G of type \c Graph like this: marci@325: /// \code marci@325: ///int count=0; marci@325: ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++; marci@325: /// \endcode marci@325: class NodeIt : public Node { marci@325: public: marci@325: /// @warning The default constructor sets the iterator marci@325: /// to an undefined value. marci@325: NodeIt() {} //FIXME marci@325: /// Invalid constructor \& conversion. marci@325: marci@325: /// Initialize the iterator to be invalid marci@325: /// \sa Invalid for more details. marci@325: NodeIt(Invalid) {} marci@325: /// Sets the iterator to the first node of \c G. marci@332: NodeIt(const GraphSkeleturo &G) {} marci@325: /// @warning The default constructor sets the iterator marci@325: /// to an undefined value. marci@325: NodeIt(const NodeIt &) {} marci@325: }; marci@325: marci@325: marci@325: /// The base type of the edge iterators. marci@325: class Edge { marci@325: public: marci@325: /// @warning The default constructor sets the iterator marci@325: /// to an undefined value. marci@325: Edge() {} //FIXME marci@325: /// Initialize the iterator to be invalid marci@325: Edge(Invalid) {} marci@325: /// Two iterators are equal if and only if they point to the marci@325: /// same object or both are invalid. marci@325: bool operator==(Edge n) const { return true; } marci@325: bool operator!=(Edge n) const { return true; } marci@325: bool operator<(Edge n) const { return true; } marci@325: }; marci@325: marci@325: // class SymEdgeIt : public Edge {}; marci@325: marci@325: /// This iterator goes through each edge. marci@325: marci@325: /// This iterator goes through each edge of a graph. marci@325: /// Its usage is quite simple, for example you can count the number marci@325: /// of edges in a graph \c G of type \c Graph as follows: marci@325: /// \code marci@325: ///int count=0; marci@325: ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++; marci@325: /// \endcode marci@325: class EdgeIt : public Edge { marci@325: public: marci@325: /// @warning The default constructor sets the iterator marci@325: /// to an undefined value. marci@325: EdgeIt() {} marci@325: /// Initialize the iterator to be invalid marci@325: EdgeIt(Invalid) {} marci@332: EdgeIt(const GraphSkeleturo &) {} marci@325: }; marci@325: marci@325: /// First node of the graph. marci@325: marci@325: /// \post \c i and the return value will be the first node. marci@325: /// marci@325: NodeIt &first(NodeIt &i) const { return i;} marci@325: marci@325: /// The first incoming edge. marci@325: InEdgeIt &first(InEdgeIt &i, Node n) const { return i;} marci@325: /// The first outgoing edge. marci@325: OutEdgeIt &first(OutEdgeIt &i, Node n) const { return i;} marci@325: // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;} marci@325: /// The first edge of the Graph. marci@325: EdgeIt &first(EdgeIt &i) const { return i;} marci@325: marci@325: // Node getNext(Node) const {} marci@325: // InEdgeIt getNext(InEdgeIt) const {} marci@325: // OutEdgeIt getNext(OutEdgeIt) const {} marci@325: // //SymEdgeIt getNext(SymEdgeIt) const {} marci@325: // EdgeIt getNext(EdgeIt) const {} marci@325: marci@325: /// Go to the next node. marci@325: NodeIt &next(NodeIt &i) const { return i;} marci@325: /// Go to the next incoming edge. marci@325: InEdgeIt &next(InEdgeIt &i) const { return i;} marci@325: /// Go to the next outgoing edge. marci@325: OutEdgeIt &next(OutEdgeIt &i) const { return i;} marci@325: //SymEdgeIt &next(SymEdgeIt &) const {} marci@325: /// Go to the next edge. marci@325: EdgeIt &next(EdgeIt &i) const { return i;} marci@325: marci@325: ///Gives back the head node of an edge. marci@325: Node head(Edge) const { return INVALID; } marci@325: ///Gives back the tail node of an edge. marci@325: Node tail(Edge) const { return INVALID; } marci@325: marci@325: // Node aNode(InEdgeIt) const {} marci@325: // Node aNode(OutEdgeIt) const {} marci@325: // Node aNode(SymEdgeIt) const {} marci@325: marci@325: // Node bNode(InEdgeIt) const {} marci@325: // Node bNode(OutEdgeIt) const {} marci@325: // Node bNode(SymEdgeIt) const {} marci@325: marci@325: /// Checks if a node iterator is valid marci@325: marci@325: ///\todo Maybe, it would be better if iterator converted to marci@325: ///bool directly, as Jacint prefers. marci@325: bool valid(const Node&) const { return true;} marci@325: /// Checks if an edge iterator is valid marci@325: marci@325: ///\todo Maybe, it would be better if iterator converted to marci@325: ///bool directly, as Jacint prefers. marci@325: bool valid(const Edge&) const { return true;} marci@325: marci@325: ///Gives back the \e id of a node. marci@325: marci@325: ///\warning Not all graph structures provide this feature. marci@325: /// marci@325: int id(const Node&) const { return 0;} marci@325: ///Gives back the \e id of an edge. marci@325: marci@325: ///\warning Not all graph structures provide this feature. marci@325: /// marci@325: int id(const Edge&) const { return 0;} marci@325: marci@325: //void setInvalid(Node &) const {}; marci@325: //void setInvalid(Edge &) const {}; marci@325: marci@325: ///Add a new node to the graph. marci@325: marci@325: /// \return the new node. marci@325: /// marci@325: Node addNode() { return INVALID;} marci@325: ///Add a new edge to the graph. marci@325: marci@325: ///Add a new edge to the graph with tail node \c tail marci@325: ///and head node \c head. marci@325: ///\return the new edge. marci@325: Edge addEdge(Node tail, Node head) { return INVALID;} marci@325: marci@325: /// Resets the graph. marci@325: marci@325: /// This function deletes all edges and nodes of the graph. marci@325: /// It also frees the memory allocated to store them. marci@325: void clear() {} marci@325: marci@325: ///Read/write/reference map of the nodes to type \c T. marci@325: marci@325: ///Read/write/reference map of the nodes to type \c T. marci@332: /// \sa MemoryMapSkeleturo marci@325: /// \todo We may need copy constructor marci@325: /// \todo We may need conversion from other nodetype marci@325: /// \todo We may need operator= marci@325: /// \warning Making maps that can handle bool type (NodeMap) marci@325: /// needs extra attention! marci@325: marci@325: template class NodeMap marci@325: { marci@325: public: marci@325: typedef T ValueType; marci@325: typedef Node KeyType; marci@325: marci@332: NodeMap(const GraphSkeleturo &G) {} marci@332: NodeMap(const GraphSkeleturo &G, T t) {} marci@325: marci@325: template NodeMap(const NodeMap &m) {} marci@325: marci@325: /// Sets the value of a node. marci@325: marci@325: /// Sets the value associated with node \c i to the value \c t. marci@325: /// marci@325: void set(Node i, T t) {} marci@325: /// Gets the value of a node. marci@325: T get(Node i) const {return *(T*)0;} //FIXME: Is it necessary marci@325: T &operator[](Node i) {return *(T*)0;} marci@325: const T &operator[](Node i) const {return *(T*)0;} marci@325: marci@325: /// Updates the map if the graph has been changed marci@325: marci@325: /// \todo Do we need this? marci@325: /// marci@325: void update() {} marci@325: void update(T a) {} //FIXME: Is it necessary marci@325: }; marci@325: marci@325: ///Read/write/reference map of the edges to type \c T. marci@325: marci@325: ///Read/write/reference map of the edges to type \c T. marci@325: ///It behaves exactly in the same way as \ref NodeMap. marci@325: /// \sa NodeMap marci@332: /// \sa MemoryMapSkeleturo marci@325: /// \todo We may need copy constructor marci@325: /// \todo We may need conversion from other edgetype marci@325: /// \todo We may need operator= marci@325: template class EdgeMap marci@325: { marci@325: public: marci@325: typedef T ValueType; marci@325: typedef Edge KeyType; marci@325: marci@332: EdgeMap(const GraphSkeleturo &G) {} marci@332: EdgeMap(const GraphSkeleturo &G, T t) {} marci@325: marci@325: void set(Edge i, T t) {} marci@325: T get(Edge i) const {return *(T*)0;} marci@325: T &operator[](Edge i) {return *(T*)0;} marci@325: marci@325: void update() {} marci@325: void update(T a) {} //FIXME: Is it necessary marci@325: }; marci@325: }; marci@325: marci@325: /// An empty eraseable graph class. marci@325: marci@325: /// This class provides all the common features of an \e eraseable graph marci@325: /// structure, marci@325: /// however completely without implementations and real data structures marci@325: /// behind the interface. marci@325: /// All graph algorithms should compile with this class, but it will not marci@325: /// run properly, of course. marci@325: /// marci@325: /// \todo This blabla could be replaced by a sepatate description about marci@332: /// Skeleturos. marci@325: /// marci@325: /// It can be used for checking the interface compatibility, marci@325: /// or it can serve as a skeleton of a new graph structure. marci@325: /// marci@325: /// Also, you will find here the full documentation of a certain graph marci@325: /// feature, the documentation of a real graph imlementation marci@325: /// like @ref ListGraph or marci@325: /// @ref SmartGraph will just refer to this structure. marci@332: class EraseableGraphSkeleturo : public GraphSkeleturo marci@325: { marci@325: public: marci@325: /// Deletes a node. marci@325: void erase(Node n) {} marci@325: /// Deletes an edge. marci@325: void erase(Edge e) {} marci@325: marci@325: /// Defalult constructor. marci@332: GraphSkeleturo() {} marci@325: ///Copy consructor. marci@332: GraphSkeleturo(const GraphSkeleturo &G) {} marci@325: }; marci@325: marci@334: /// An empty out-edge-iterable graph class. marci@334: marci@334: /// An empty graph class which provides a function to marci@334: /// iterate on out-edges of any node. marci@334: class OutEdgeIterableGraphSkeleturo : public GraphSkeleturo marci@334: { marci@334: public: marci@334: marci@334: /// This iterator goes trough the outgoing edges of a node. marci@334: marci@334: /// This iterator goes trough the \e outgoing edges of a certain node marci@334: /// of a graph. marci@334: /// Its usage is quite simple, for example you can count the number marci@334: /// of outgoing edges of a node \c n marci@334: /// in graph \c G of type \c Graph as follows. marci@334: /// \code marci@334: ///int count=0; marci@334: ///for(Graph::OutEdgeIt e(G,n); G.valid(e); G.next(e)) ++count; marci@334: /// \endcode marci@334: class OutEdgeIt : public Edge { marci@334: public: marci@334: /// @warning The default constructor sets the iterator marci@334: /// to an undefined value. marci@334: OutEdgeIt() {} marci@334: /// Initialize the iterator to be invalid marci@334: OutEdgeIt(Invalid) {} marci@334: /// This constructor sets the iterator to first outgoing edge. marci@334: marci@334: /// This constructor set the iterator to the first outgoing edge of marci@334: /// node marci@334: ///@param n the node marci@334: ///@param G the graph marci@334: OutEdgeIt(const GraphSkeleturo & G, Node n) {} marci@334: }; marci@334: }; marci@334: marci@334: /// An empty in-edge-iterable graph class. marci@334: marci@334: /// An empty graph class which provides a function to marci@334: /// iterate on in-edges of any node. marci@334: class InEdgeIterableGraphSkeleturo : public GraphSkeleturo marci@334: { marci@334: public: marci@334: marci@334: /// This iterator goes trough the incoming edges of a node. marci@334: marci@334: /// This iterator goes trough the \e incoming edges of a certain node marci@334: /// of a graph. marci@334: /// Its usage is quite simple, for example you can count the number marci@334: /// of incoming edges of a node \c n marci@334: /// in graph \c G of type \c Graph as follows. marci@334: /// \code marci@334: ///int count=0; marci@334: ///for(Graph::InEdgeIt e(G,n); G.valid(e); G.next(e)) ++count; marci@334: /// \endcode marci@334: class InEdgeIt : public Edge { marci@334: public: marci@334: /// @warning The default constructor sets the iterator marci@334: /// to an undefined value. marci@334: InEdgeIt() {} marci@334: /// Initialize the iterator to be invalid marci@334: InEdgeIt(Invalid) {} marci@334: /// This constructor sets the iterator to first incomig edge. marci@334: marci@334: /// This constructor set the iterator to the first incomig edge of marci@334: /// node marci@334: ///@param n the node marci@334: ///@param G the graph marci@334: InEdgeIt(const GraphSkeleturo & G, Node n) {} marci@334: }; marci@334: }; marci@334: marci@334: marci@333: /// An empty node-eraseable graph class. marci@333: marci@333: /// An empty graph class which provides a function to marci@333: /// delete any of its nodes. marci@333: class NodeEraseableGraphSkeleturo : public GraphSkeleturo marci@333: { marci@333: public: marci@333: /// Deletes a node. marci@333: void erase(Node n) {} marci@333: }; marci@333: marci@333: /// An empty edge-eraseable graph class. marci@333: marci@333: /// An empty graph class which provides a function to delete any marci@333: /// of its edges. marci@333: class EdgeEraseableGraphSkeleturo : public GraphSkeleturo marci@333: { marci@333: public: marci@333: /// Deletes a node. marci@333: void erase(Edge n) {} marci@333: }; marci@333: marci@333: /// An empty graph class which provides a function to get the number of its nodes. marci@325: marci@325: /// This graph class provides a function for getting the number of its marci@325: /// nodes. marci@325: /// Clearly, for physical graph structures it can be expected to have such a marci@325: /// function. For wrappers or graphs which are given in an implicit way, marci@325: /// the implementation can be circumstantial, that is why this composes a marci@325: /// separate concept. marci@333: class NodeCountingGraphSkeleturo : public GraphSkeleturo marci@325: { marci@325: public: marci@325: /// Returns the number of nodes. marci@325: int nodeNum() const { return 0;} marci@325: }; marci@325: marci@333: /// An empty graph class which provides a function to get the number of its edges. marci@325: marci@325: /// This graph class provides a function for getting the number of its marci@325: /// edges. marci@325: /// Clearly, for physical graph structures it can be expected to have such a marci@325: /// function. For wrappers or graphs which are given in an implicit way, marci@325: /// the implementation can be circumstantial, that is why this composes a marci@325: /// separate concept. marci@333: class EdgeCountingGraphSkeleturo : public GraphSkeleturo marci@325: { marci@325: public: marci@325: /// Returns the number of edges. marci@325: int edgeNum() const { return 0;} marci@325: }; marci@332: marci@332: /// @} marci@325: marci@325: } //namespace hugo marci@325: marci@325: marci@332: marci@332: // class EmptyBipGraph : public Graph Skeleturo marci@325: // { marci@325: // class ANode {}; marci@325: // class BNode {}; marci@325: marci@325: // ANode &next(ANode &) {} marci@325: // BNode &next(BNode &) {} marci@325: marci@325: // ANode &getFirst(ANode &) const {} marci@325: // BNode &getFirst(BNode &) const {} marci@325: marci@325: // enum NodeClass { A = 0, B = 1 }; marci@325: // NodeClass getClass(Node n) {} marci@325: marci@325: // } marci@325: marci@325: #endif // HUGO_GRAPH_H