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