marci@174: // -*- c++ -*- alpar@503: #ifndef HUGO_SKELETON_GRAPH_H alpar@503: #define HUGO_SKELETON_GRAPH_H alpar@52: alpar@242: ///\file alpar@242: ///\brief Declaration of GraphSkeleton. alpar@242: ladanyi@542: #include alpar@732: #include alpar@145: alpar@163: /// The namespace of HugoLib alpar@163: namespace hugo { alpar@732: namespace skeleton { alpar@732: alpar@732: // @defgroup empty_graph The GraphSkeleton class alpar@732: // @{ alpar@163: alpar@732: /// An empty static graph class. alpar@732: alpar@732: /// This class provides all the common features of a graph structure, alpar@732: /// however completely without implementations and real data structures alpar@732: /// behind the interface. alpar@732: /// All graph algorithms should compile with this class, but it will not alpar@732: /// run properly, of course. alpar@732: /// alpar@732: /// It can be used for checking the interface compatibility, alpar@732: /// or it can serve as a skeleton of a new graph structure. alpar@732: /// alpar@732: /// Also, you will find here the full documentation of a certain graph alpar@732: /// feature, the documentation of a real graph imlementation alpar@732: /// like @ref ListGraph or alpar@732: /// @ref SmartGraph will just refer to this structure. alpar@732: class StaticGraphSkeleton alpar@732: { alpar@732: public: alpar@732: /// Defalult constructor. alpar@774: StaticGraphSkeleton() { } alpar@732: ///Copy consructor. alpar@163: alpar@732: ///\todo It is not clear, what we expect from a copy constructor. alpar@732: ///E.g. How to assign the nodes/edges to each other? What about maps? alpar@774: StaticGraphSkeleton(const StaticGraphSkeleton& g) { } alpar@732: alpar@774: /// The base type of node iterators, alpar@774: /// or in other words, the trivial node iterator. alpar@732: alpar@774: /// This is the base type of each node iterator, alpar@774: /// thus each kind of node iterator converts to this. alpar@774: /// More precisely each kind of node iterator have to be inherited alpar@774: /// from the trivial node iterator. alpar@732: class Node { alpar@732: public: alpar@732: /// @warning The default constructor sets the iterator alpar@732: /// to an undefined value. alpar@774: Node() { } alpar@774: /// Copy constructor. alpar@774: Node(const Node&) { } alpar@732: /// Invalid constructor \& conversion. alpar@732: alpar@732: /// This constructor initializes the iterator to be invalid. alpar@732: /// \sa Invalid for more details. alpar@774: Node(Invalid) { } alpar@732: /// Two iterators are equal if and only if they point to the alpar@732: /// same object or both are invalid. alpar@732: bool operator==(Node) const { return true; } alpar@732: alpar@732: /// \sa \ref operator==(Node n) alpar@732: /// alpar@732: bool operator!=(Node) const { return true; } alpar@732: alpar@732: bool operator<(Node) const { return true; } alpar@732: }; alpar@732: alpar@732: /// This iterator goes through each node. alpar@732: alpar@732: /// This iterator goes through each node. alpar@732: /// Its usage is quite simple, for example you can count the number alpar@774: /// of nodes in graph \c g of type \c Graph like this: alpar@732: /// \code alpar@774: /// int count=0; alpar@774: /// for (Graph::NodeIt n(g); g.valid(n); ++n) ++count; alpar@732: /// \endcode alpar@732: class NodeIt : public Node { alpar@732: public: alpar@732: /// @warning The default constructor sets the iterator alpar@732: /// to an undefined value. alpar@774: NodeIt() { } alpar@774: /// Copy constructor. alpar@774: NodeIt(const NodeIt&) { } alpar@732: /// Invalid constructor \& conversion. alpar@732: alpar@774: /// Initialize the iterator to be invalid. alpar@732: /// \sa Invalid for more details. alpar@774: NodeIt(Invalid) { } alpar@774: /// Sets the iterator to the first node of \c g. alpar@774: NodeIt(const StaticGraphSkeleton& g) { } alpar@774: /// Sets the iterator to the node of \c g pointed by the trivial alpar@774: /// iterator n. This feature necessitates that each time we alpar@774: /// iterate the node-set, the iteration order is the same. alpar@774: NodeIt(const StaticGraphSkeleton& g, const Node& n) { } alpar@774: /// Assign the iterator to the next node. alpar@774: NodeIt& operator++() { return *this; } alpar@732: }; alpar@732: alpar@732: alpar@732: /// The base type of the edge iterators. alpar@732: class Edge { alpar@732: public: alpar@732: /// @warning The default constructor sets the iterator alpar@732: /// to an undefined value. alpar@774: Edge() { } alpar@774: /// Copy constructor. alpar@774: Edge(const Edge&) { } alpar@774: /// Initialize the iterator to be invalid. alpar@774: Edge(Invalid) { } alpar@732: /// Two iterators are equal if and only if they point to the alpar@732: /// same object or both are invalid. alpar@732: bool operator==(Edge) const { return true; } alpar@732: bool operator!=(Edge) const { return true; } alpar@732: bool operator<(Edge) const { return true; } alpar@732: }; alpar@732: alpar@732: /// This iterator goes trough the outgoing edges of a node. alpar@732: alpar@732: /// This iterator goes trough the \e outgoing edges of a certain node alpar@732: /// of a graph. alpar@732: /// Its usage is quite simple, for example you can count the number alpar@732: /// of outgoing edges of a node \c n alpar@774: /// in graph \c g of type \c Graph as follows. alpar@732: /// \code alpar@774: /// int count=0; alpar@774: /// for (Graph::OutEdgeIt e(g, n); g.valid(e); ++e) ++count; alpar@732: /// \endcode alpar@732: alpar@732: class OutEdgeIt : public Edge { alpar@732: public: alpar@732: /// @warning The default constructor sets the iterator alpar@732: /// to an undefined value. alpar@774: OutEdgeIt() { } alpar@774: /// Copy constructor. alpar@774: OutEdgeIt(const OutEdgeIt&) { } alpar@774: /// Initialize the iterator to be invalid. alpar@774: OutEdgeIt(Invalid) { } alpar@732: /// This constructor sets the iterator to first outgoing edge. alpar@732: alpar@732: /// This constructor set the iterator to the first outgoing edge of alpar@732: /// node alpar@732: ///@param n the node alpar@774: ///@param g the graph alpar@774: OutEdgeIt(const StaticGraphSkeleton& g, const Node& n) { } alpar@774: /// Sets the iterator to the value of the trivial iterator \c e. alpar@774: /// This feature necessitates that each time we alpar@774: /// iterate the edge-set, the iteration order is the same. alpar@774: OutEdgeIt(const StaticGraphSkeleton& g, const Edge& e) { } alpar@774: /// Assign the iterator to the next outedge of the corresponding node. alpar@774: OutEdgeIt& operator++() { return *this; } alpar@732: }; alpar@732: alpar@732: /// This iterator goes trough the incoming edges of a node. alpar@732: alpar@732: /// This iterator goes trough the \e incoming edges of a certain node alpar@732: /// of a graph. alpar@732: /// Its usage is quite simple, for example you can count the number alpar@732: /// of outgoing edges of a node \c n alpar@774: /// in graph \c g of type \c Graph as follows. alpar@732: /// \code alpar@774: /// int count=0; alpar@774: /// for(Graph::InEdgeIt e(g, n); g.valid(e); ++) ++count; alpar@732: /// \endcode alpar@732: alpar@732: class InEdgeIt : public Edge { alpar@732: public: alpar@732: /// @warning The default constructor sets the iterator alpar@732: /// to an undefined value. alpar@774: InEdgeIt() { } alpar@774: /// Copy constructor. alpar@774: InEdgeIt(const InEdgeIt&) { } alpar@774: /// Initialize the iterator to be invalid. alpar@774: InEdgeIt(Invalid) { } alpar@774: /// . alpar@774: InEdgeIt(const StaticGraphSkeleton&, const Node&) { } alpar@774: /// . alpar@774: InEdgeIt(const StaticGraphSkeleton&, const Edge&) { } alpar@774: /// Assign the iterator to the next inedge of the corresponding node. alpar@774: InEdgeIt& operator++() { return *this; } alpar@732: }; alpar@732: // class SymEdgeIt : public Edge {}; alpar@732: alpar@732: /// This iterator goes through each edge. alpar@732: alpar@732: /// This iterator goes through each edge of a graph. alpar@732: /// Its usage is quite simple, for example you can count the number alpar@774: /// of edges in a graph \c g of type \c Graph as follows: alpar@732: /// \code alpar@774: /// int count=0; alpar@774: /// for(Graph::EdgeIt e(g); g.valid(e); ++e) ++count; alpar@732: /// \endcode alpar@732: class EdgeIt : public Edge { alpar@732: public: alpar@732: /// @warning The default constructor sets the iterator alpar@732: /// to an undefined value. alpar@774: EdgeIt() { } alpar@774: /// Copy constructor. alpar@774: EdgeIt(const EdgeIt&) { } alpar@774: /// Initialize the iterator to be invalid. alpar@774: EdgeIt(Invalid) { } alpar@774: /// . alpar@774: EdgeIt(const StaticGraphSkeleton&) { } alpar@774: /// . alpar@774: EdgeIt(const StaticGraphSkeleton&, const Edge&) { } alpar@774: EdgeIt& operator++() { return *this; } alpar@732: }; alpar@732: alpar@732: /// First node of the graph. alpar@732: alpar@732: /// \retval i the first node. alpar@732: /// \return the first node. alpar@732: /// alpar@774: NodeIt& first(NodeIt& i) const { return i; } alpar@732: alpar@732: /// The first incoming edge. alpar@774: InEdgeIt& first(InEdgeIt &i, Node) const { return i; } alpar@732: /// The first outgoing edge. alpar@774: OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; } alpar@774: // SymEdgeIt& first(SymEdgeIt&, Node) const { return i; } alpar@732: /// The first edge of the Graph. alpar@774: EdgeIt& first(EdgeIt& i) const { return i; } alpar@732: alpar@732: // Node getNext(Node) const {} alpar@732: // InEdgeIt getNext(InEdgeIt) const {} alpar@732: // OutEdgeIt getNext(OutEdgeIt) const {} alpar@732: // //SymEdgeIt getNext(SymEdgeIt) const {} alpar@732: // EdgeIt getNext(EdgeIt) const {} alpar@732: alpar@732: /// Go to the next node. alpar@774: NodeIt& next(NodeIt& i) const { return i; } alpar@732: /// Go to the next incoming edge. alpar@774: InEdgeIt& next(InEdgeIt& i) const { return i; } alpar@732: /// Go to the next outgoing edge. alpar@774: OutEdgeIt& next(OutEdgeIt& i) const { return i; } alpar@774: //SymEdgeIt& next(SymEdgeIt&) const { } alpar@732: /// Go to the next edge. alpar@774: EdgeIt& next(EdgeIt& i) const { return i; } alpar@732: alpar@732: ///Gives back the head node of an edge. alpar@732: Node head(Edge) const { return INVALID; } alpar@732: ///Gives back the tail node of an edge. alpar@732: Node tail(Edge) const { return INVALID; } alpar@163: alpar@732: // Node aNode(InEdgeIt) const {} alpar@732: // Node aNode(OutEdgeIt) const {} alpar@732: // Node aNode(SymEdgeIt) const {} alpar@321: alpar@732: // Node bNode(InEdgeIt) const {} alpar@732: // Node bNode(OutEdgeIt) const {} alpar@732: // Node bNode(SymEdgeIt) const {} marci@320: alpar@732: /// Checks if a node iterator is valid alpar@182: alpar@732: ///\todo Maybe, it would be better if iterator converted to alpar@732: ///bool directly, as Jacint prefers. alpar@774: bool valid(const Node&) const { return true; } alpar@732: /// Checks if an edge iterator is valid alpar@182: alpar@732: ///\todo Maybe, it would be better if iterator converted to alpar@732: ///bool directly, as Jacint prefers. alpar@774: bool valid(const Edge&) const { return true; } alpar@182: alpar@732: ///Gives back the \e id of a node. alpar@182: alpar@732: ///\warning Not all graph structures provide this feature. alpar@732: /// alpar@774: int id(const Node&) const { return 0; } alpar@732: ///Gives back the \e id of an edge. alpar@182: alpar@732: ///\warning Not all graph structures provide this feature. alpar@182: /// alpar@774: int id(const Edge&) const { return 0; } alpar@182: alpar@732: /// Resets the graph. alpar@732: alpar@732: /// This function deletes all edges and nodes of the graph. alpar@732: /// It also frees the memory allocated to store them. alpar@774: void clear() { } alpar@732: alpar@774: int nodeNum() const { return 0; } alpar@774: int edgeNum() const { return 0; } alpar@732: alpar@732: alpar@732: ///Reference map of the nodes to type \c T. alpar@732: alpar@732: ///Reference map of the nodes to type \c T. alpar@732: /// \sa ReferenceSkeleton alpar@732: /// \warning Making maps that can handle bool type (NodeMap) alpar@732: /// needs extra attention! alpar@732: alpar@732: template class NodeMap alpar@732: : public ReferenceMap< Node, T > alpar@732: { alpar@732: public: alpar@732: alpar@774: NodeMap(const StaticGraphSkeleton&) { } alpar@774: NodeMap(const StaticGraphSkeleton&, T) { } alpar@732: alpar@732: ///Copy constructor alpar@774: template NodeMap(const NodeMap&) { } alpar@732: ///Assignment operator alpar@774: template NodeMap& operator=(const NodeMap&) alpar@774: { return *this; } alpar@732: }; alpar@732: alpar@732: ///Reference map of the edges to type \c T. alpar@732: alpar@732: ///Reference map of the edges to type \c T. alpar@732: /// \sa ReferenceSkeleton alpar@732: /// \warning Making maps that can handle bool type (EdgeMap) alpar@732: /// needs extra attention! alpar@732: template class EdgeMap alpar@732: : public ReferenceMap alpar@732: { alpar@732: public: alpar@732: typedef T ValueType; alpar@732: typedef Edge KeyType; alpar@732: alpar@774: EdgeMap(const StaticGraphSkeleton&) { } alpar@774: EdgeMap(const StaticGraphSkeleton&, T) { } alpar@147: alpar@732: ///Copy constructor alpar@774: template EdgeMap(const EdgeMap&) { } alpar@732: ///Assignment operator alpar@774: template EdgeMap &operator=(const EdgeMap&) alpar@774: { return *this; } alpar@732: }; alpar@163: }; alpar@163: alpar@186: alpar@732: alpar@732: /// An empty graph class. alpar@186: alpar@732: /// This class provides everything that \c StaticGraphSkeleton alpar@732: /// with additional functionality which enables to build a alpar@732: /// graph from scratch. alpar@732: class GraphSkeleton : public StaticGraphSkeleton alpar@732: { alpar@163: public: alpar@732: /// Defalult constructor. alpar@774: GraphSkeleton() { } alpar@732: ///Copy consructor. alpar@186: alpar@732: ///\todo It is not clear, what we expect from a copy constructor. alpar@732: ///E.g. How to assign the nodes/edges to each other? What about maps? alpar@774: GraphSkeleton(const GraphSkeleton&) { } alpar@186: alpar@732: ///Add a new node to the graph. alpar@732: alpar@732: /// \return the new node. alpar@732: /// alpar@774: Node addNode() { return INVALID; } alpar@732: ///Add a new edge to the graph. alpar@732: alpar@732: ///Add a new edge to the graph with tail node \c tail alpar@732: ///and head node \c head. alpar@732: ///\return the new edge. alpar@774: Edge addEdge(Node, Node) { return INVALID; } alpar@732: alpar@732: /// Resets the graph. alpar@732: alpar@732: /// This function deletes all edges and nodes of the graph. alpar@732: /// It also frees the memory allocated to store them. alpar@732: /// \todo It might belong to \c EraseableGraphSkeleton. alpar@774: void clear() { } alpar@163: }; alpar@163: alpar@732: /// An empty eraseable graph class. alpar@52: alpar@732: /// This class is an extension of \c GraphSkeleton. It also makes it alpar@732: /// possible to erase edges or nodes. alpar@732: class EraseableGraphSkeleton : public GraphSkeleton alpar@163: { alpar@163: public: alpar@732: /// Deletes a node. alpar@774: void erase(Node n) { } alpar@732: /// Deletes an edge. alpar@774: void erase(Edge e) { } alpar@163: alpar@732: /// Defalult constructor. alpar@774: EraseableGraphSkeleton() { } alpar@732: ///Copy consructor. alpar@774: EraseableGraphSkeleton(const GraphSkeleton&) { } alpar@163: }; alpar@163: alpar@732: // @} alpar@732: } //namespace skeleton alpar@242: 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: alpar@503: #endif // HUGO_SKELETON_GRAPH_H