lemon-0.x: lemon/concept/graph.h@f9113440b667

     1 /* -*- C++ -*-

     2  * lemon/concept/graph.h - Part of LEMON, a generic C++ optimization library

     3  *

     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     6  *

     7  * Permission to use, modify and distribute this software is granted

     8  * provided that this copyright notice appears in all copies. For

     9  * precise terms see the accompanying LICENSE file.

    10  *

    11  * This software is provided "AS IS" with no warranty of any kind,

    12  * express or implied, and with no claim as to its suitability for any

    13  * purpose.

    14  *

    15  */

    17 #ifndef LEMON_CONCEPT_GRAPH_H

    18 #define LEMON_CONCEPT_GRAPH_H

    20 ///\ingroup graph_concepts

    21 ///\file

    22 ///\brief Declaration of Graph.

    24 #include <lemon/invalid.h>

    25 #include <lemon/utility.h>

    26 #include <lemon/concept/maps.h>

    27 #include <lemon/concept_check.h>

    28 #include <lemon/concept/graph_component.h>

    30 namespace lemon {

    31   namespace concept {

    34     /// \addtogroup graph_concepts

    35     /// @{

    37     /**************** The full-featured graph concepts ****************/

    40     /// \brief Modular static graph class.

    41     ///

    42     /// It should be the same as the \c StaticGraph class.

    43     class _StaticGraph

    44       :  virtual public BaseGraphComponent,

    45          public IterableGraphComponent, public MappableGraphComponent {

    46     public:

    47       ///\e

    49       ///\todo undocumented

    50       ///

    51       typedef False UndirTag;

    53       typedef BaseGraphComponent::Node Node;

    54       typedef BaseGraphComponent::Edge Edge;

    56       template <typename _Graph>

    57       struct Constraints {

    58         void constraints() {

    59           checkConcept<IterableGraphComponent, _Graph>();

    60           checkConcept<MappableGraphComponent, _Graph>();

    61         }

    62       };

    63     };

    65     /// \brief Modular extendable graph class.

    66     ///

    67     /// It should be the same as the \c ExtendableGraph class.

    68     class _ExtendableGraph

    69       :  virtual public BaseGraphComponent, public _StaticGraph,

    70          public ExtendableGraphComponent, public ClearableGraphComponent {

    71     public:

    72       typedef BaseGraphComponent::Node Node;

    73       typedef BaseGraphComponent::Edge Edge;

    75       template <typename _Graph>

    76       struct Constraints {

    77         void constraints() {

    78           checkConcept<_StaticGraph, _Graph >();

    79           checkConcept<ExtendableGraphComponent, _Graph >();

    80           checkConcept<ClearableGraphComponent, _Graph >();

    81         }

    82       };

    83     };

    85     /// \brief Modular erasable graph class.

    86     ///

    87     /// It should be the same as the \c ErasableGraph class.

    88     class _ErasableGraph

    89       :  virtual public BaseGraphComponent, public _ExtendableGraph,

    90          public ErasableGraphComponent {

    91     public:

    92       typedef BaseGraphComponent::Node Node;

    93       typedef BaseGraphComponent::Edge Edge;

    95       template <typename _Graph>

    96       struct Constraints {

    97         void constraints() {

    98           checkConcept<_ExtendableGraph, _Graph >();

    99           checkConcept<ErasableGraphComponent, _Graph >();

   100         }

   101       };

   102     };

   104     /// An empty static graph class.

   106     /// This class provides all the common features of a graph structure,

   107     /// however completely without implementations and real data structures

   108     /// behind the interface.

   109     /// All graph algorithms should compile with this class, but it will not

   110     /// run properly, of course.

   111     ///

   112     /// It can be used for checking the interface compatibility,

   113     /// or it can serve as a skeleton of a new graph structure.

   114     ///

   115     /// Also, you will find here the full documentation of a certain graph

   116     /// feature, the documentation of a real graph imlementation

   117     /// like @ref ListGraph or

   118     /// @ref SmartGraph will just refer to this structure.

   119     ///

   120     /// \todo A pages describing the concept of concept description would

   121     /// be nice.

   122     class StaticGraph

   123     {

   124     public:

   125       ///\e

   127       ///\todo undocumented

   128       ///

   129       typedef False UndirTag;

   131       /// Defalult constructor.

   133       /// Defalult constructor.

   134       ///

   135       StaticGraph() { }

   136       ///Copy consructor.

   138 //       ///\todo It is not clear, what we expect from a copy constructor.

   139 //       ///E.g. How to assign the nodes/edges to each other? What about maps?

   140 //       StaticGraph(const StaticGraph& g) { }

   142       /// The base type of node iterators,

   143       /// or in other words, the trivial node iterator.

   145       /// This is the base type of each node iterator,

   146       /// thus each kind of node iterator converts to this.

   147       /// More precisely each kind of node iterator should be inherited

   148       /// from the trivial node iterator.

   149       class Node {

   150       public:

   151         /// Default constructor

   153         /// @warning The default constructor sets the iterator

   154         /// to an undefined value.

   155         Node() { }

   156         /// Copy constructor.

   158         /// Copy constructor.

   159         ///

   160         Node(const Node&) { }

   162         /// Invalid constructor \& conversion.

   164         /// This constructor initializes the iterator to be invalid.

   165         /// \sa Invalid for more details.

   166         Node(Invalid) { }

   167         /// Equality operator

   169         /// Two iterators are equal if and only if they point to the

   170         /// same object or both are invalid.

   171         bool operator==(Node) const { return true; }

   173         /// Inequality operator

   175         /// \sa operator==(Node n)

   176         ///

   177         bool operator!=(Node) const { return true; }

   179       };

   181       /// This iterator goes through each node.

   183       /// This iterator goes through each node.

   184       /// Its usage is quite simple, for example you can count the number

   185       /// of nodes in graph \c g of type \c Graph like this:

   186       /// \code

   187       /// int count=0;

   188       /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;

   189       /// \endcode

   190       class NodeIt : public Node {

   191       public:

   192         /// Default constructor

   194         /// @warning The default constructor sets the iterator

   195         /// to an undefined value.

   196         NodeIt() { }

   197         /// Copy constructor.

   199         /// Copy constructor.

   200         ///

   201         NodeIt(const NodeIt& n) : Node(n) { }

   202         /// Invalid constructor \& conversion.

   204         /// Initialize the iterator to be invalid.

   205         /// \sa Invalid for more details.

   206         NodeIt(Invalid) { }

   207         /// Sets the iterator to the first node.

   209         /// Sets the iterator to the first node of \c g.

   210         ///

   211         NodeIt(const StaticGraph&) { }

   212         /// Node -> NodeIt conversion.

   214         /// Sets the iterator to the node of \c the graph pointed by

   215 	/// the trivial iterator.

   216         /// This feature necessitates that each time we

   217         /// iterate the edge-set, the iteration order is the same.

   218         NodeIt(const StaticGraph&, const Node&) { }

   219         /// Next node.

   221         /// Assign the iterator to the next node.

   222         ///

   223         NodeIt& operator++() { return *this; }

   224       };

   227       /// The base type of the edge iterators.

   229       /// The base type of the edge iterators.

   230       ///

   231       class Edge {

   232       public:

   233         /// Default constructor

   235         /// @warning The default constructor sets the iterator

   236         /// to an undefined value.

   237         Edge() { }

   238         /// Copy constructor.

   240         /// Copy constructor.

   241         ///

   242         Edge(const Edge&) { }

   243         /// Initialize the iterator to be invalid.

   245         /// Initialize the iterator to be invalid.

   246         ///

   247         Edge(Invalid) { }

   248         /// Equality operator

   250         /// Two iterators are equal if and only if they point to the

   251         /// same object or both are invalid.

   252         bool operator==(Edge) const { return true; }

   253         /// Inequality operator

   255         /// \sa operator==(Node n)

   256         ///

   257         bool operator!=(Edge) const { return true; }

   258       };

   260       /// This iterator goes trough the outgoing edges of a node.

   262       /// This iterator goes trough the \e outgoing edges of a certain node

   263       /// of a graph.

   264       /// Its usage is quite simple, for example you can count the number

   265       /// of outgoing edges of a node \c n

   266       /// in graph \c g of type \c Graph as follows.

   267       /// \code

   268       /// int count=0;

   269       /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;

   270       /// \endcode

   272       class OutEdgeIt : public Edge {

   273       public:

   274         /// Default constructor

   276         /// @warning The default constructor sets the iterator

   277         /// to an undefined value.

   278         OutEdgeIt() { }

   279         /// Copy constructor.

   281         /// Copy constructor.

   282         ///

   283         OutEdgeIt(const OutEdgeIt& e) : Edge(e) { }

   284         /// Initialize the iterator to be invalid.

   286         /// Initialize the iterator to be invalid.

   287         ///

   288         OutEdgeIt(Invalid) { }

   289         /// This constructor sets the iterator to the first outgoing edge.

   291         /// This constructor sets the iterator to the first outgoing edge of

   292         /// the node.

   293         ///@param n the node

   294         ///@param g the graph

   295         OutEdgeIt(const StaticGraph&, const Node&) { }

   296         /// Edge -> OutEdgeIt conversion

   298         /// Sets the iterator to the value of the trivial iterator.

   299 	/// This feature necessitates that each time we

   300         /// iterate the edge-set, the iteration order is the same.

   301         OutEdgeIt(const StaticGraph&, const Edge&) { }

   302         ///Next outgoing edge

   304         /// Assign the iterator to the next

   305         /// outgoing edge of the corresponding node.

   306         OutEdgeIt& operator++() { return *this; }

   307       };

   309       /// This iterator goes trough the incoming edges of a node.

   311       /// This iterator goes trough the \e incoming edges of a certain node

   312       /// of a graph.

   313       /// Its usage is quite simple, for example you can count the number

   314       /// of outgoing edges of a node \c n

   315       /// in graph \c g of type \c Graph as follows.

   316       /// \code

   317       /// int count=0;

   318       /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;

   319       /// \endcode

   321       class InEdgeIt : public Edge {

   322       public:

   323         /// Default constructor

   325         /// @warning The default constructor sets the iterator

   326         /// to an undefined value.

   327         InEdgeIt() { }

   328         /// Copy constructor.

   330         /// Copy constructor.

   331         ///

   332         InEdgeIt(const InEdgeIt& e) : Edge(e) { }

   333         /// Initialize the iterator to be invalid.

   335         /// Initialize the iterator to be invalid.

   336         ///

   337         InEdgeIt(Invalid) { }

   338         /// This constructor sets the iterator to first incoming edge.

   340         /// This constructor set the iterator to the first incoming edge of

   341         /// the node.

   342         ///@param n the node

   343         ///@param g the graph

   344         InEdgeIt(const StaticGraph&, const Node&) { }

   345         /// Edge -> InEdgeIt conversion

   347         /// Sets the iterator to the value of the trivial iterator \c e.

   348         /// This feature necessitates that each time we

   349         /// iterate the edge-set, the iteration order is the same.

   350         InEdgeIt(const StaticGraph&, const Edge&) { }

   351         /// Next incoming edge

   353         /// Assign the iterator to the next inedge of the corresponding node.

   354         ///

   355         InEdgeIt& operator++() { return *this; }

   356       };

   357       /// This iterator goes through each edge.

   359       /// This iterator goes through each edge of a graph.

   360       /// Its usage is quite simple, for example you can count the number

   361       /// of edges in a graph \c g of type \c Graph as follows:

   362       /// \code

   363       /// int count=0;

   364       /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;

   365       /// \endcode

   366       class EdgeIt : public Edge {

   367       public:

   368         /// Default constructor

   370         /// @warning The default constructor sets the iterator

   371         /// to an undefined value.

   372         EdgeIt() { }

   373         /// Copy constructor.

   375         /// Copy constructor.

   376         ///

   377         EdgeIt(const EdgeIt& e) : Edge(e) { }

   378         /// Initialize the iterator to be invalid.

   380         /// Initialize the iterator to be invalid.

   381         ///

   382         EdgeIt(Invalid) { }

   383         /// This constructor sets the iterator to the first edge.

   385         /// This constructor sets the iterator to the first edge of \c g.

   386         ///@param g the graph

   387         EdgeIt(const StaticGraph&) { }

   388         /// Edge -> EdgeIt conversion

   390         /// Sets the iterator to the value of the trivial iterator \c e.

   391         /// This feature necessitates that each time we

   392         /// iterate the edge-set, the iteration order is the same.

   393         EdgeIt(const StaticGraph&, const Edge&) { }

   394         ///Next edge

   396         /// Assign the iterator to the next edge.

   397         EdgeIt& operator++() { return *this; }

   398       };

   399       ///Gives back the target node of an edge.

   401       ///Gives back the target node of an edge.

   402       ///

   403       Node target(Edge) const { return INVALID; }

   404       ///Gives back the source node of an edge.

   406       ///Gives back the source node of an edge.

   407       ///

   408       Node source(Edge) const { return INVALID; }

   409       /// Read write map of the nodes to type \c T.

   411       /// \ingroup concept

   412       /// ReadWrite map of the nodes to type \c T.

   413       /// \sa Reference

   414       /// \warning Making maps that can handle bool type (NodeMap<bool>)

   415       /// needs some extra attention!

   416       template<class T>

   417       class NodeMap : public ReadWriteMap< Node, T >

   418       {

   419       public:

   421         ///\e

   422         NodeMap(const StaticGraph&) { }

   423         ///\e

   424         NodeMap(const StaticGraph&, T) { }

   426         ///Copy constructor

   427         NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }

   428         ///Assignment operator

   429         NodeMap& operator=(const NodeMap&) { return *this; }

   430         // \todo fix this concept

   431       };

   433       /// Read write map of the edges to type \c T.

   435       /// \ingroup concept

   436       ///Reference map of the edges to type \c T.

   437       /// \sa Reference

   438       /// \warning Making maps that can handle bool type (EdgeMap<bool>)

   439       /// needs some extra attention!

   440       template<class T>

   441       class EdgeMap : public ReadWriteMap<Edge,T>

   442       {

   443       public:

   445         ///\e

   446         EdgeMap(const StaticGraph&) { }

   447         ///\e

   448         EdgeMap(const StaticGraph&, T) { }

   449         ///Copy constructor

   450         EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }

   451         ///Assignment operator

   452         EdgeMap& operator=(const EdgeMap&) { return *this; }

   453         // \todo fix this concept

   454       };

   456       template <typename _Graph>

   457       struct Constraints : public _StaticGraph::Constraints<_Graph> {};

   459     };

   461     /// An empty non-static graph class.

   463     /// This class provides everything that \ref StaticGraph does.

   464     /// Additionally it enables building graphs from scratch.

   465     class ExtendableGraph : public StaticGraph

   466     {

   467     public:

   468       /// Defalult constructor.

   470       /// Defalult constructor.

   471       ///

   472       ExtendableGraph() { }

   473       ///Add a new node to the graph.

   475       /// \return the new node.

   476       ///

   477       Node addNode() { return INVALID; }

   478       ///Add a new edge to the graph.

   480       ///Add a new edge to the graph with source node \c s

   481       ///and target node \c t.

   482       ///\return the new edge.

   483       Edge addEdge(Node, Node) { return INVALID; }

   485       /// Resets the graph.

   487       /// This function deletes all edges and nodes of the graph.

   488       /// It also frees the memory allocated to store them.

   489       /// \todo It might belong to \ref ErasableGraph.

   490       void clear() { }

   492       template <typename _Graph>

   493       struct Constraints : public _ExtendableGraph::Constraints<_Graph> {};

   495     };

   497     /// An empty erasable graph class.

   499     /// This class is an extension of \ref ExtendableGraph. It makes it

   500     /// possible to erase edges or nodes.

   501     class ErasableGraph : public ExtendableGraph

   502     {

   503     public:

   504       /// Defalult constructor.

   506       /// Defalult constructor.

   507       ///

   508       ErasableGraph() { }

   509       /// Deletes a node.

   511       /// Deletes node \c n node.

   512       ///

   513       void erase(Node) { }

   514       /// Deletes an edge.

   516       /// Deletes edge \c e edge.

   517       ///

   518       void erase(Edge) { }

   520       template <typename _Graph>

   521       struct Constraints : public _ErasableGraph::Constraints<_Graph> {};

   523     };

   526     /************* New GraphBase stuff **************/

   529 //     /// A minimal GraphBase concept

   531 //     /// This class describes a minimal concept which can be extended to a

   532 //     /// full-featured graph with \ref GraphFactory.

   533 //     class GraphBase {

   534 //     public:

   536 //       GraphBase() {}

   538 //       /// \bug Should we demand that Node and Edge be subclasses of the

   539 //       /// Graph class???

   541 //       typedef GraphItem<'n'> Node;

   542 //       typedef GraphItem<'e'> Edge;

   544 // //       class Node : public BaseGraphItem<'n'> {};

   545 // //       class Edge : public BaseGraphItem<'e'> {};

   547 //       // Graph operation

   548 //       void firstNode(Node &n) const { }

   549 //       void firstEdge(Edge &e) const { }

   551 //       void firstOutEdge(Edge &e, Node) const { }

   552 //       void firstInEdge(Edge &e, Node) const { }

   554 //       void nextNode(Node &n) const { }

   555 //       void nextEdge(Edge &e) const { }

   558 //       // Question: isn't it reasonable if this methods have a Node

   559 //       // parameter? Like this:

   560 //       // Edge& nextOut(Edge &e, Node) const { return e; }

   561 //       void nextOutEdge(Edge &e) const { }

   562 //       void nextInEdge(Edge &e) const { }

   564 //       Node target(Edge) const { return Node(); }

   565 //       Node source(Edge) const { return Node(); }

   568 //       // Do we need id, nodeNum, edgeNum and co. in this basic graphbase

   569 //       // concept?

   572 //       // Maps.

   573 //       //

   574 //       // We need a special slimer concept which does not provide maps (it

   575 //       // wouldn't be strictly slimer, cause for map-factory id() & friends

   576 //       // a required...)

   578 //       template<typename T>

   579 //       class NodeMap : public GraphMap<GraphBase, Node, T> {};

   581 //       template<typename T>

   582 //       class EdgeMap : public GraphMap<GraphBase, Node, T> {};

   583 //     };

   585     // @}

   586   } //namespace concept

   587 } //namespace lemon

   591 #endif // LEMON_CONCEPT_GRAPH_H

author	hegyi
	Thu, 23 Jun 2005 17:56:24 +0000
changeset 1509	f9113440b667
parent 1448	0274acee0e35
child 1563	0853ed07a677
permissions	-rw-r--r--