deba@909: /* -*- C++ -*- deba@909: * src/hugo/skeletons/graph.h - Part of HUGOlib, a generic C++ optimization library deba@909: * deba@909: * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@909: * (Egervary Combinatorial Optimization Research Group, EGRES). deba@909: * deba@909: * Permission to use, modify and distribute this software is granted deba@909: * provided that this copyright notice appears in all copies. For deba@909: * precise terms see the accompanying LICENSE file. deba@909: * deba@909: * This software is provided "AS IS" with no warranty of any kind, deba@909: * express or implied, and with no claim as to its suitability for any deba@909: * purpose. deba@909: * deba@909: */ deba@909: deba@909: #ifndef HUGO_SKELETON_SYM_GRAPH_H deba@909: #define HUGO_SKELETON_SYM_GRAPH_H deba@909: deba@909: ///\ingroup skeletons deba@909: ///\file deba@909: ///\brief Declaration of SymGraph. deba@909: deba@909: #include deba@909: #include deba@909: #include deba@909: deba@909: namespace hugo { deba@909: namespace skeleton { deba@909: deba@909: /// \addtogroup skeletons deba@909: /// @{ deba@909: deba@909: /// An empty static graph class. deba@909: deba@909: /// This class provides all the common features of a symmetric deba@909: /// graph structure, however completely without implementations and deba@909: /// real data structures behind the interface. deba@909: /// All graph algorithms should compile with this class, but it will not deba@909: /// run properly, of course. deba@909: /// deba@909: /// It can be used for checking the interface compatibility, deba@909: /// or it can serve as a skeleton of a new symmetric graph structure. deba@909: /// deba@909: /// Also, you will find here the full documentation of a certain graph deba@909: /// feature, the documentation of a real symmetric graph imlementation deba@909: /// like @ref SymListGraph or alpar@911: /// @ref hugo::SymSmartGraph will just refer to this structure. deba@909: class StaticSymGraph deba@909: { deba@909: public: deba@909: /// Defalult constructor. deba@909: deba@909: /// Defalult constructor. deba@909: /// deba@909: StaticSymGraph() { } deba@909: ///Copy consructor. deba@909: deba@909: // ///\todo It is not clear, what we expect from a copy constructor. deba@909: // ///E.g. How to assign the nodes/edges to each other? What about maps? deba@909: // StaticGraph(const StaticGraph& g) { } deba@909: deba@909: /// The base type of node iterators, deba@909: /// or in other words, the trivial node iterator. deba@909: deba@909: /// This is the base type of each node iterator, deba@909: /// thus each kind of node iterator converts to this. deba@909: /// More precisely each kind of node iterator should be inherited deba@909: /// from the trivial node iterator. deba@909: class Node { deba@909: public: deba@909: /// Default constructor deba@909: deba@909: /// @warning The default constructor sets the iterator deba@909: /// to an undefined value. deba@909: Node() { } deba@909: /// Copy constructor. deba@909: deba@909: /// Copy constructor. deba@909: /// deba@909: Node(const Node&) { } deba@909: deba@909: /// Invalid constructor \& conversion. deba@909: deba@909: /// This constructor initializes the iterator to be invalid. deba@909: /// \sa Invalid for more details. deba@909: Node(Invalid) { } deba@909: /// Equality operator deba@909: deba@909: /// Two iterators are equal if and only if they point to the deba@909: /// same object or both are invalid. deba@909: bool operator==(Node) const { return true; } deba@909: deba@909: /// Inequality operator deba@909: alpar@911: /// \sa operator==(Node n) deba@909: /// deba@909: bool operator!=(Node) const { return true; } deba@909: deba@909: ///Comparison operator. deba@909: deba@909: ///This is a strict ordering between the nodes. deba@909: /// deba@909: ///This ordering can be different from the order in which NodeIt deba@909: ///goes through the nodes. deba@909: ///\todo Possibly we don't need it. deba@909: bool operator<(Node) const { return true; } deba@909: }; deba@909: deba@909: /// This iterator goes through each node. deba@909: deba@909: /// This iterator goes through each node. deba@909: /// Its usage is quite simple, for example you can count the number deba@909: /// of nodes in graph \c g of type \c Graph like this: deba@909: /// \code deba@909: /// int count=0; deba@909: /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count; deba@909: /// \endcode deba@909: class NodeIt : public Node { deba@909: public: deba@909: /// Default constructor deba@909: deba@909: /// @warning The default constructor sets the iterator deba@909: /// to an undefined value. deba@909: NodeIt() { } deba@909: /// Copy constructor. deba@909: deba@909: /// Copy constructor. deba@909: /// deba@909: NodeIt(const NodeIt&) { } deba@909: /// Invalid constructor \& conversion. deba@909: deba@909: /// Initialize the iterator to be invalid. deba@909: /// \sa Invalid for more details. deba@909: NodeIt(Invalid) { } deba@909: /// Sets the iterator to the first node. deba@909: deba@909: /// Sets the iterator to the first node of \c g. deba@909: /// deba@909: NodeIt(const StaticSymGraph& g) { } deba@909: /// Node -> NodeIt conversion. deba@909: deba@909: /// Sets the iterator to the node of \c g pointed by the trivial deba@909: /// iterator n. deba@909: /// This feature necessitates that each time we deba@909: /// iterate the edge-set, the iteration order is the same. deba@909: NodeIt(const StaticSymGraph& g, const Node& n) { } deba@909: /// Next node. deba@909: deba@909: /// Assign the iterator to the next node. deba@909: /// deba@909: NodeIt& operator++() { return *this; } deba@909: }; deba@909: deba@909: deba@909: /// The base type of the symmetric edge iterators. deba@909: deba@909: /// The base type of the symmetric edge iterators. deba@909: /// deba@909: class SymEdge { deba@909: public: deba@909: /// Default constructor deba@909: deba@909: /// @warning The default constructor sets the iterator deba@909: /// to an undefined value. deba@909: SymEdge() { } deba@909: /// Copy constructor. deba@909: deba@909: /// Copy constructor. deba@909: /// deba@909: SymEdge(const SymEdge&) { } deba@909: /// Initialize the iterator to be invalid. deba@909: deba@909: /// Initialize the iterator to be invalid. deba@909: /// deba@909: SymEdge(Invalid) { } deba@909: /// Equality operator deba@909: deba@909: /// Two iterators are equal if and only if they point to the deba@909: /// same object or both are invalid. deba@909: bool operator==(SymEdge) const { return true; } deba@909: /// Inequality operator deba@909: alpar@911: /// \sa operator==(Node n) deba@909: /// deba@909: bool operator!=(SymEdge) const { return true; } deba@909: ///Comparison operator. deba@909: deba@909: ///This is a strict ordering between the nodes. deba@909: /// deba@909: ///This ordering can be different from the order in which NodeIt deba@909: ///goes through the nodes. deba@909: ///\todo Possibly we don't need it. deba@909: bool operator<(SymEdge) const { return true; } deba@909: }; deba@909: deba@909: deba@909: /// The base type of the edge iterators. deba@909: deba@909: /// The base type of the edge iterators. deba@909: /// deba@909: class Edge : public SymEdge { deba@909: public: deba@909: /// Default constructor deba@909: deba@909: /// @warning The default constructor sets the iterator deba@909: /// to an undefined value. deba@909: Edge() { } deba@909: /// Copy constructor. deba@909: deba@909: /// Copy constructor. deba@909: /// deba@909: Edge(const Edge&) { } deba@909: /// Initialize the iterator to be invalid. deba@909: deba@909: /// Initialize the iterator to be invalid. deba@909: /// deba@909: Edge(Invalid) { } deba@909: /// Equality operator deba@909: deba@909: /// Two iterators are equal if and only if they point to the deba@909: /// same object or both are invalid. deba@909: bool operator==(Edge) const { return true; } deba@909: /// Inequality operator deba@909: alpar@911: /// \sa operator==(Node n) deba@909: /// deba@909: bool operator!=(Edge) const { return true; } deba@909: ///Comparison operator. deba@909: deba@909: ///This is a strict ordering between the nodes. deba@909: /// deba@909: ///This ordering can be different from the order in which NodeIt deba@909: ///goes through the nodes. deba@909: ///\todo Possibly we don't need it. deba@909: bool operator<(Edge) const { return true; } deba@909: }; deba@909: deba@909: /// This iterator goes trough the outgoing edges of a node. deba@909: deba@909: /// This iterator goes trough the \e outgoing edges of a certain node deba@909: /// of a graph. deba@909: /// Its usage is quite simple, for example you can count the number deba@909: /// of outgoing edges of a node \c n deba@909: /// in graph \c g of type \c Graph as follows. deba@909: /// \code deba@909: /// int count=0; deba@909: /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count; deba@909: /// \endcode deba@909: deba@909: class OutEdgeIt : public Edge { deba@909: public: deba@909: /// Default constructor deba@909: deba@909: /// @warning The default constructor sets the iterator deba@909: /// to an undefined value. deba@909: OutEdgeIt() { } deba@909: /// Copy constructor. deba@909: deba@909: /// Copy constructor. deba@909: /// deba@909: OutEdgeIt(const OutEdgeIt&) { } deba@909: /// Initialize the iterator to be invalid. deba@909: deba@909: /// Initialize the iterator to be invalid. deba@909: /// deba@909: OutEdgeIt(Invalid) { } deba@909: /// This constructor sets the iterator to first outgoing edge. deba@909: deba@909: /// This constructor set the iterator to the first outgoing edge of deba@909: /// node deba@909: ///@param n the node deba@909: ///@param g the graph deba@909: OutEdgeIt(const StaticSymGraph& g, const Node& n) { } deba@909: /// Edge -> OutEdgeIt conversion deba@909: deba@909: /// Sets the iterator to the value of the trivial iterator \c e. deba@909: /// This feature necessitates that each time we deba@909: /// iterate the edge-set, the iteration order is the same. deba@909: OutEdgeIt(const StaticSymGraph& g, const Edge& e) { } deba@909: ///Next outgoing edge deba@909: deba@909: /// Assign the iterator to the next deba@909: /// outgoing edge of the corresponding node. deba@909: OutEdgeIt& operator++() { return *this; } deba@909: }; deba@909: deba@909: /// This iterator goes trough the incoming edges of a node. deba@909: deba@909: /// This iterator goes trough the \e incoming edges of a certain node deba@909: /// of a graph. deba@909: /// Its usage is quite simple, for example you can count the number deba@909: /// of outgoing edges of a node \c n deba@909: /// in graph \c g of type \c Graph as follows. deba@909: /// \code deba@909: /// int count=0; deba@909: /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count; deba@909: /// \endcode deba@909: deba@909: class InEdgeIt : public Edge { deba@909: public: deba@909: /// Default constructor deba@909: deba@909: /// @warning The default constructor sets the iterator deba@909: /// to an undefined value. deba@909: InEdgeIt() { } deba@909: /// Copy constructor. deba@909: deba@909: /// Copy constructor. deba@909: /// deba@909: InEdgeIt(const InEdgeIt&) { } deba@909: /// Initialize the iterator to be invalid. deba@909: deba@909: /// Initialize the iterator to be invalid. deba@909: /// deba@909: InEdgeIt(Invalid) { } deba@909: /// This constructor sets the iterator to first incoming edge. deba@909: deba@909: /// This constructor set the iterator to the first incoming edge of deba@909: /// node deba@909: ///@param n the node deba@909: ///@param g the graph deba@909: InEdgeIt(const StaticSymGraph& g, const Node& n) { } deba@909: /// Edge -> InEdgeIt conversion deba@909: deba@909: /// Sets the iterator to the value of the trivial iterator \c e. deba@909: /// This feature necessitates that each time we deba@909: /// iterate the edge-set, the iteration order is the same. deba@909: InEdgeIt(const StaticSymGraph& g, const Edge& n) { } deba@909: /// Next incoming edge deba@909: deba@909: /// Assign the iterator to the next inedge of the corresponding node. deba@909: /// deba@909: InEdgeIt& operator++() { return *this; } deba@909: }; deba@909: /// This iterator goes through each symmetric edge. deba@909: deba@909: /// This iterator goes through each symmetric edge of a graph. deba@909: /// Its usage is quite simple, for example you can count the number deba@909: /// of symmetric edges in a graph \c g of type \c Graph as follows: deba@909: /// \code deba@909: /// int count=0; deba@909: /// for(Graph::SymEdgeIt e(g); e!=INVALID; ++e) ++count; deba@909: /// \endcode deba@909: class SymEdgeIt : public SymEdge { deba@909: public: deba@909: /// Default constructor deba@909: deba@909: /// @warning The default constructor sets the iterator deba@909: /// to an undefined value. deba@909: SymEdgeIt() { } deba@909: /// Copy constructor. deba@909: deba@909: /// Copy constructor. deba@909: /// deba@909: SymEdgeIt(const SymEdgeIt&) { } deba@909: /// Initialize the iterator to be invalid. deba@909: deba@909: /// Initialize the iterator to be invalid. deba@909: /// deba@909: SymEdgeIt(Invalid) { } deba@909: /// This constructor sets the iterator to first edge. deba@909: deba@909: /// This constructor set the iterator to the first edge of deba@909: /// node deba@909: ///@param g the graph deba@909: SymEdgeIt(const StaticSymGraph& g) { } deba@909: /// Edge -> EdgeIt conversion deba@909: deba@909: /// Sets the iterator to the value of the trivial iterator \c e. deba@909: /// This feature necessitates that each time we deba@909: /// iterate the edge-set, the iteration order is the same. deba@909: SymEdgeIt(const StaticSymGraph&, const SymEdge&) { } deba@909: ///Next edge deba@909: deba@909: /// Assign the iterator to the next deba@909: /// edge of the corresponding node. deba@909: SymEdgeIt& operator++() { return *this; } deba@909: }; deba@909: /// This iterator goes through each edge. deba@909: deba@909: /// This iterator goes through each edge of a graph. deba@909: /// Its usage is quite simple, for example you can count the number deba@909: /// of edges in a graph \c g of type \c Graph as follows: deba@909: /// \code deba@909: /// int count=0; deba@909: /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; deba@909: /// \endcode deba@909: class EdgeIt : public Edge { deba@909: public: deba@909: /// Default constructor deba@909: deba@909: /// @warning The default constructor sets the iterator deba@909: /// to an undefined value. deba@909: EdgeIt() { } deba@909: /// Copy constructor. deba@909: deba@909: /// Copy constructor. deba@909: /// deba@909: EdgeIt(const EdgeIt&) { } deba@909: /// Initialize the iterator to be invalid. deba@909: deba@909: /// Initialize the iterator to be invalid. deba@909: /// deba@909: EdgeIt(Invalid) { } deba@909: /// This constructor sets the iterator to first edge. deba@909: deba@909: /// This constructor set the iterator to the first edge of deba@909: /// node deba@909: ///@param g the graph deba@909: EdgeIt(const StaticSymGraph& g) { } deba@909: /// Edge -> EdgeIt conversion deba@909: deba@909: /// Sets the iterator to the value of the trivial iterator \c e. deba@909: /// This feature necessitates that each time we deba@909: /// iterate the edge-set, the iteration order is the same. deba@909: EdgeIt(const StaticSymGraph&, const Edge&) { } deba@909: ///Next edge deba@909: deba@909: /// Assign the iterator to the next deba@909: /// edge of the corresponding node. deba@909: EdgeIt& operator++() { return *this; } deba@909: }; deba@909: deba@909: /// First node of the graph. deba@909: deba@909: /// \retval i the first node. deba@909: /// \return the first node. deba@909: /// deba@909: NodeIt& first(NodeIt& i) const { return i; } deba@909: deba@909: /// The first incoming edge. deba@909: deba@909: /// The first incoming edge. deba@909: /// deba@909: InEdgeIt& first(InEdgeIt &i, Node) const { return i; } deba@909: /// The first outgoing edge. deba@909: deba@909: /// The first outgoing edge. deba@909: /// deba@909: OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; } deba@909: /// The first edge of the Graph. deba@909: deba@909: /// The first edge of the Graph. deba@909: /// deba@909: EdgeIt& first(EdgeIt& i) const { return i; } deba@909: /// The first symmetric edge of the Graph. deba@909: deba@909: /// The first symmetric edge of the Graph. deba@909: /// deba@909: SymEdgeIt& first(SymEdgeIt& i) const { return i; } deba@909: deba@909: ///Gives back the head node of an edge. deba@909: deba@909: ///Gives back the head node of an edge. deba@909: /// deba@909: Node head(Edge) const { return INVALID; } deba@909: ///Gives back the tail node of an edge. deba@909: deba@909: ///Gives back the tail node of an edge. deba@909: /// deba@909: Node tail(Edge) const { return INVALID; } deba@909: deba@909: ///Gives back the first node of an symmetric edge. deba@909: deba@909: ///Gives back the first node of an symmetric edge. deba@909: /// deba@909: Node head(SymEdge) const { return INVALID; } deba@909: ///Gives back the second node of an symmetric edge. deba@909: deba@909: ///Gives back the second node of an symmetric edge. deba@909: /// deba@909: Node tail(SymEdge) const { return INVALID; } deba@909: ///Gives back the \e id of a node. deba@909: deba@909: ///\warning Not all graph structures provide this feature. deba@909: /// deba@909: ///\todo Should each graph provide \c id? deba@909: int id(const Node&) const { return 0; } deba@909: ///Gives back the \e id of an edge. deba@909: deba@909: ///\warning Not all graph structures provide this feature. deba@909: /// deba@909: ///\todo Should each graph provide \c id? deba@909: int id(const Edge&) const { return 0; } deba@909: deba@909: ///\warning Not all graph structures provide this feature. deba@909: /// deba@909: ///\todo Should each graph provide \c id? deba@909: int id(const SymEdge&) const { return 0; } deba@909: alpar@911: ///\e deba@909: deba@909: ///\todo Should it be in the concept? deba@909: /// deba@909: int nodeNum() const { return 0; } alpar@911: ///\e deba@909: deba@909: ///\todo Should it be in the concept? deba@909: /// deba@909: int edgeNum() const { return 0; } deba@909: deba@909: ///\todo Should it be in the concept? deba@909: /// deba@909: int symEdgeNum() const { return 0; } deba@909: deba@909: deba@909: /// Gives back the forward directed edge of the symmetric edge. deba@909: Edge forward(SymEdge) const {return INVALID;} deba@909: deba@909: /// Gives back the backward directed edge of the symmetric edge. deba@909: Edge backward(SymEdge) const {return INVALID;}; deba@909: deba@909: /// Gives back the opposite of the edge. deba@909: Edge opposite(Edge) const {return INVALID;} deba@909: deba@909: ///Reference map of the nodes to type \c T. deba@909: /// \ingroup skeletons deba@909: ///Reference map of the nodes to type \c T. deba@909: /// \sa Reference deba@909: /// \warning Making maps that can handle bool type (NodeMap) deba@909: /// needs some extra attention! deba@909: template class NodeMap : public ReferenceMap< Node, T > deba@909: { deba@909: public: deba@909: alpar@911: ///\e deba@909: NodeMap(const StaticSymGraph&) { } alpar@911: ///\e deba@909: NodeMap(const StaticSymGraph&, T) { } deba@909: deba@909: ///Copy constructor deba@909: template NodeMap(const NodeMap&) { } deba@909: ///Assignment operator deba@909: template NodeMap& operator=(const NodeMap&) deba@909: { return *this; } deba@909: }; deba@909: deba@909: ///Reference map of the edges to type \c T. deba@909: deba@909: /// \ingroup skeletons deba@909: ///Reference map of the edges to type \c T. deba@909: /// \sa Reference deba@909: /// \warning Making maps that can handle bool type (EdgeMap) deba@909: /// needs some extra attention! deba@909: template class EdgeMap deba@909: : public ReferenceMap deba@909: { deba@909: public: deba@909: alpar@911: ///\e deba@909: EdgeMap(const StaticSymGraph&) { } alpar@911: ///\e deba@909: EdgeMap(const StaticSymGraph&, T) { } deba@909: deba@909: ///Copy constructor deba@909: template EdgeMap(const EdgeMap&) { } deba@909: ///Assignment operator deba@909: template EdgeMap &operator=(const EdgeMap&) deba@909: { return *this; } deba@909: }; deba@909: deba@909: ///Reference map of the edges to type \c T. deba@909: deba@909: /// \ingroup skeletons deba@909: ///Reference map of the symmetric edges to type \c T. deba@909: /// \sa Reference deba@909: /// \warning Making maps that can handle bool type (EdgeMap) deba@909: /// needs some extra attention! deba@909: template class SymEdgeMap deba@909: : public ReferenceMap deba@909: { deba@909: public: deba@909: alpar@911: ///\e deba@909: SymEdgeMap(const StaticSymGraph&) { } alpar@911: ///\e deba@909: SymEdgeMap(const StaticSymGraph&, T) { } deba@909: deba@909: ///Copy constructor deba@909: template SymEdgeMap(const SymEdgeMap&) { } deba@909: ///Assignment operator deba@909: template SymEdgeMap &operator=(const SymEdgeMap&) deba@909: { return *this; } deba@909: }; deba@909: }; deba@909: deba@909: deba@909: deba@909: /// An empty non-static graph class. deba@909: deba@909: /// This class provides everything that \ref StaticGraph deba@909: /// with additional functionality which enables to build a deba@909: /// graph from scratch. deba@909: class ExtendableSymGraph : public StaticSymGraph deba@909: { deba@909: public: deba@909: /// Defalult constructor. deba@909: deba@909: /// Defalult constructor. deba@909: /// deba@909: ExtendableSymGraph() { } deba@909: ///Add a new node to the graph. deba@909: deba@909: /// \return the new node. deba@909: /// deba@909: Node addNode() { return INVALID; } deba@909: ///Add a new edge to the graph. deba@909: deba@909: ///Add a new symmetric edge to the graph with tail node \c t deba@909: ///and head node \c h. deba@909: ///\return the new edge. deba@909: SymEdge addEdge(Node h, Node t) { return INVALID; } deba@909: deba@909: /// Resets the graph. deba@909: deba@909: /// This function deletes all edges and nodes of the graph. deba@909: /// It also frees the memory allocated to store them. deba@909: /// \todo It might belong to \ref ErasableGraph. deba@909: void clear() { } deba@909: }; deba@909: deba@909: /// An empty erasable graph class. deba@909: deba@909: /// This class is an extension of \ref ExtendableGraph. It also makes it deba@909: /// possible to erase edges or nodes. deba@909: class ErasableSymGraph : public ExtendableSymGraph deba@909: { deba@909: public: deba@909: /// Defalult constructor. deba@909: deba@909: /// Defalult constructor. deba@909: /// deba@909: ErasableSymGraph() { } deba@909: /// Deletes a node. deba@909: deba@909: /// Deletes node \c n node. deba@909: /// deba@909: void erase(Node n) { } deba@909: /// Deletes an edge. deba@909: deba@909: /// Deletes edge \c e edge. deba@909: /// deba@909: void erase(SymEdge e) { } deba@909: }; deba@909: deba@909: // @} deba@909: } //namespace skeleton deba@909: } //namespace hugo deba@909: deba@909: deba@909: deba@909: #endif // HUGO_SKELETON_GRAPH_H