lemon-0.x: src/lemon/concept/graph.h@4fb22cfa5759

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

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

     3  *

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

     5  * (Egervary Combinatorial Optimization Research Group, 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/concept/maps.h>

    26 #include <lemon/concept_check.h>

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

    29 namespace lemon {

    30   namespace concept {

    33     /// \addtogroup graph_concepts

    34     /// @{

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

    39     /// \brief Modular builded static graph class.

    40     ///

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

    42     class _StaticGraph

    43       :  virtual public BaseGraphComponent,

    44 	 public IterableGraphComponent, public MappableGraphComponent {

    45     public:

    46       typedef BaseGraphComponent::Node Node;

    47       typedef BaseGraphComponent::Edge Edge;

    49       template <typename _Graph>

    50       struct Constraints {

    51 	void constraints() {

    52 	  checkConcept<IterableGraphComponent, _Graph>();

    53 	  checkConcept<MappableGraphComponent, _Graph>();

    54 	}

    55       };

    56     };

    58     /// \brief Modular builded extendable graph class.

    59     ///

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

    61     class _ExtendableGraph

    62       :  virtual public BaseGraphComponent, public _StaticGraph,

    63 	 public ExtendableGraphComponent, public ClearableGraphComponent {

    64     public:

    65       typedef BaseGraphComponent::Node Node;

    66       typedef BaseGraphComponent::Edge Edge;

    68       template <typename _Graph>

    69       struct Constraints {

    70 	void constraints() {

    71 	  checkConcept<_StaticGraph, _Graph >();

    72 	  checkConcept<ExtendableGraphComponent, _Graph >();

    73 	  checkConcept<ClearableGraphComponent, _Graph >();

    74 	}

    75       };

    76     };

    78     /// \brief Modular builded erasable graph class.

    79     ///

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

    81     class _ErasableGraph

    82       :  virtual public BaseGraphComponent, public _ExtendableGraph,

    83 	 public ErasableGraphComponent {

    84     public:

    85       typedef BaseGraphComponent::Node Node;

    86       typedef BaseGraphComponent::Edge Edge;

    88       template <typename _Graph>

    89       struct Constraints {

    90 	void constraints() {

    91 	  checkConcept<_ExtendableGraph, _Graph >();

    92 	  checkConcept<ErasableGraphComponent, _Graph >();

    93 	}

    94       };

    95     };

    97     /// An empty static graph class.

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

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

   101     /// behind the interface.

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

   103     /// run properly, of course.

   104     ///

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

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

   107     ///

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

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

   110     /// like @ref ListGraph or

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

   112     ///

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

   114     /// be nice.

   115     class StaticGraph

   116     {

   117     public:

   118       /// Defalult constructor.

   120       /// Defalult constructor.

   121       ///

   122       StaticGraph() { }

   123       ///Copy consructor.

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

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

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

   129       /// The base type of node iterators,

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

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

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

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

   135       /// from the trivial node iterator.

   136       class Node {

   137       public:

   138 	/// Default constructor

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

   141 	/// to an undefined value.

   142 	Node() { }

   143 	/// Copy constructor.

   145 	/// Copy constructor.

   146 	///

   147 	Node(const Node&) { }

   149 	/// Invalid constructor \& conversion.

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

   152 	/// \sa Invalid for more details.

   153 	Node(Invalid) { }

   154 	/// Equality operator

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

   157 	/// same object or both are invalid.

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

   160 	/// Inequality operator

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

   163 	///

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

   166       };

   168       /// This iterator goes through each node.

   170       /// This iterator goes through each node.

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

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

   173       /// \code

   174       /// int count=0;

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

   176       /// \endcode

   177       class NodeIt : public Node {

   178       public:

   179 	/// Default constructor

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

   182 	/// to an undefined value.

   183 	NodeIt() { }

   184 	/// Copy constructor.

   186 	/// Copy constructor.

   187 	///

   188 	NodeIt(const NodeIt&) { }

   189 	/// Invalid constructor \& conversion.

   191 	/// Initialize the iterator to be invalid.

   192 	/// \sa Invalid for more details.

   193 	NodeIt(Invalid) { }

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

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

   197 	///

   198 	NodeIt(const StaticGraph& g) { }

   199 	/// Node -> NodeIt conversion.

   201 	/// Sets the iterator to the node of \c g pointed by the trivial

   202 	/// iterator n.

   203 	/// This feature necessitates that each time we

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

   205 	NodeIt(const StaticGraph& g, const Node& n) { }

   206 	/// Next node.

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

   209 	///

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

   211       };

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

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

   217       ///

   218       class Edge {

   219       public:

   220 	/// Default constructor

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

   223 	/// to an undefined value.

   224 	Edge() { }

   225 	/// Copy constructor.

   227 	/// Copy constructor.

   228 	///

   229 	Edge(const Edge&) { }

   230 	/// Initialize the iterator to be invalid.

   232 	/// Initialize the iterator to be invalid.

   233 	///

   234 	Edge(Invalid) { }

   235 	/// Equality operator

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

   238 	/// same object or both are invalid.

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

   240 	/// Inequality operator

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

   243 	///

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

   245       };

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

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

   250       /// of a graph.

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

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

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

   254       /// \code

   255       /// int count=0;

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

   257       /// \endcode

   259       class OutEdgeIt : public Edge {

   260       public:

   261 	/// Default constructor

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

   264 	/// to an undefined value.

   265 	OutEdgeIt() { }

   266 	/// Copy constructor.

   268 	/// Copy constructor.

   269 	///

   270 	OutEdgeIt(const OutEdgeIt&) { }

   271 	/// Initialize the iterator to be invalid.

   273 	/// Initialize the iterator to be invalid.

   274 	///

   275 	OutEdgeIt(Invalid) { }

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

   278 	/// This constructor set the iterator to the first outgoing edge of

   279 	/// node

   280 	///@param n the node

   281 	///@param g the graph

   282 	OutEdgeIt(const StaticGraph& g, const Node& n) { }

   283 	/// Edge -> OutEdgeIt conversion

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

   286 	/// This feature necessitates that each time we

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

   288 	OutEdgeIt(const StaticGraph& g, const Edge& e) { }

   289 	///Next outgoing edge

   291 	/// Assign the iterator to the next

   292 	/// outgoing edge of the corresponding node.

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

   294       };

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

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

   299       /// of a graph.

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

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

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

   303       /// \code

   304       /// int count=0;

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

   306       /// \endcode

   308       class InEdgeIt : public Edge {

   309       public:

   310 	/// Default constructor

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

   313 	/// to an undefined value.

   314 	InEdgeIt() { }

   315 	/// Copy constructor.

   317 	/// Copy constructor.

   318 	///

   319 	InEdgeIt(const InEdgeIt&) { }

   320 	/// Initialize the iterator to be invalid.

   322 	/// Initialize the iterator to be invalid.

   323 	///

   324 	InEdgeIt(Invalid) { }

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

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

   328 	/// node

   329 	///@param n the node

   330 	///@param g the graph

   331 	InEdgeIt(const StaticGraph& g, const Node& n) { }

   332 	/// Edge -> InEdgeIt conversion

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

   335 	/// This feature necessitates that each time we

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

   337 	InEdgeIt(const StaticGraph& g, const Edge& n) { }

   338 	/// Next incoming edge

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

   341 	///

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

   343       };

   344       /// This iterator goes through each edge.

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

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

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

   349       /// \code

   350       /// int count=0;

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

   352       /// \endcode

   353       class EdgeIt : public Edge {

   354       public:

   355 	/// Default constructor

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

   358 	/// to an undefined value.

   359 	EdgeIt() { }

   360 	/// Copy constructor.

   362 	/// Copy constructor.

   363 	///

   364 	EdgeIt(const EdgeIt&) { }

   365 	/// Initialize the iterator to be invalid.

   367 	/// Initialize the iterator to be invalid.

   368 	///

   369 	EdgeIt(Invalid) { }

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

   372 	/// This constructor set the iterator to the first edge of

   373 	/// node

   374 	///@param g the graph

   375 	EdgeIt(const StaticGraph& g) { }

   376 	/// Edge -> EdgeIt conversion

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

   379 	/// This feature necessitates that each time we

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

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

   382     	///Next edge

   384 	/// Assign the iterator to the next

   385 	/// edge of the corresponding node.

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

   387       };

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

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

   391       ///

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

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

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

   396       ///

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

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

   400       /// \ingroup concept

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

   402       /// \sa Reference

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

   404       /// needs some extra attention!

   405       template<class T>

   406       class NodeMap : public ReadWriteMap< Node, T >

   407       {

   408       public:

   410 	///\e

   411 	NodeMap(const StaticGraph&) { }

   412 	///\e

   413 	NodeMap(const StaticGraph&, T) { }

   415 	///Copy constructor

   416 	NodeMap(const NodeMap&) { }

   417 	///Assignment operator

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

   419 	// \todo fix this concept

   420       };

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

   424       /// \ingroup concept

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

   426       /// \sa Reference

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

   428       /// needs some extra attention!

   429       template<class T>

   430       class EdgeMap : public ReadWriteMap<Edge,T>

   431       {

   432       public:

   434 	///\e

   435 	EdgeMap(const StaticGraph&) { }

   436 	///\e

   437 	EdgeMap(const StaticGraph&, T) { }

   438 	///Copy constructor

   439 	EdgeMap(const EdgeMap&) { }

   440 	///Assignment operator

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

   442 	// \todo fix this concept

   443       };

   445       template <typename _Graph>

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

   448     };

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

   452     /// This class provides everything that \ref StaticGraph

   453     /// with additional functionality which enables to build a

   454     /// graph from scratch.

   455     class ExtendableGraph : public StaticGraph

   456     {

   457     public:

   458       /// Defalult constructor.

   460       /// Defalult constructor.

   461       ///

   462       ExtendableGraph() { }

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

   465       /// \return the new node.

   466       ///

   467       Node addNode() { return INVALID; }

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

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

   471       ///and target node \c t.

   472       ///\return the new edge.

   473       Edge addEdge(Node s, Node t) { return INVALID; }

   475       /// Resets the graph.

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

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

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

   480       void clear() { }

   482       template <typename _Graph>

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

   485     };

   487     /// An empty erasable graph class.

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

   490     /// possible to erase edges or nodes.

   491     class ErasableGraph : public ExtendableGraph

   492     {

   493     public:

   494       /// Defalult constructor.

   496       /// Defalult constructor.

   497       ///

   498       ErasableGraph() { }

   499       /// Deletes a node.

   501       /// Deletes node \c n node.

   502       ///

   503       void erase(Node n) { }

   504       /// Deletes an edge.

   506       /// Deletes edge \c e edge.

   507       ///

   508       void erase(Edge e) { }

   510       template <typename _Graph>

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

   513     };

   516     /************* New GraphBase stuff **************/

   519 //     /// A minimal GraphBase concept

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

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

   523 //     class GraphBase {

   524 //     public:

   526 //       GraphBase() {}

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

   529 //       /// Graph class???

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

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

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

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

   537 //       // Graph operation

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

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

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

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

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

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

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

   549 //       // parameter? Like this:

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

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

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

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

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

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

   559 //       // concept?

   562 //       // Maps.

   563 //       //

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

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

   566 //       // a required...)

   568 //       template<typename T>

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

   571 //       template<typename T>

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

   573 //     };

   575     // @}

   576   } //namespace concept

   577 } //namespace lemon

   581 #endif // LEMON_CONCEPT_GRAPH_H

author	marci
	Tue, 08 Feb 2005 17:47:19 +0000
changeset 1143	4fb22cfa5759
parent 1030	c8a41699e613
child 1164	80bb73097736
permissions	-rw-r--r--