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