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