lemon-0.x: src/hugo/skeletons/graph.h@d9ec436d11fe

     1 // -*- c++ -*-

     2 #ifndef HUGO_SKELETON_GRAPH_H

     3 #define HUGO_SKELETON_GRAPH_H

     5 ///\ingroup skeletons

     6 ///\file

     7 ///\brief Declaration of GraphSkeleton.

     9 #include <hugo/invalid.h>

    10 #include <hugo/skeletons/maps.h>

    12 /// The namespace of HugoLib

    13 namespace hugo {

    14   namespace skeleton {

    16     /// \addtogroup skeletons

    17     /// @{

    19     /// An empty static graph class.

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

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

    23     /// behind the interface.

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

    25     /// run properly, of course.

    26     ///

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

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

    29     ///

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

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

    32     /// like @ref ListGraph or

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

    34     class StaticGraphSkeleton

    35     {

    36     public:

    37       /// Defalult constructor.

    38       StaticGraphSkeleton() { }

    39       ///Copy consructor.

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

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

    43       StaticGraphSkeleton(const StaticGraphSkeleton& g) { }

    45       /// The base type of node iterators,

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

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

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

    50       /// More precisely each kind of node iterator have to be inherited

    51       /// from the trivial node iterator.

    52       class Node {

    53       public:

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

    55 	/// to an undefined value.

    56 	Node() { }

    57 	/// Copy constructor.

    58 	Node(const Node&) { }

    59 	/// Invalid constructor \& conversion.

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

    62 	/// \sa Invalid for more details.

    63 	Node(Invalid) { }

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

    65 	/// same object or both are invalid.

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

    68 	/// \sa \ref operator==(Node n)

    69 	///

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

    72 	bool operator<(Node) const { return true; }

    73       };

    75       /// This iterator goes through each node.

    77       /// This iterator goes through each node.

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

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

    80       /// \code

    81       /// int count=0;

    82       /// for (Graph::NodeIt n(g); g.valid(n); ++n) ++count;

    83       /// \endcode

    84       class NodeIt : public Node {

    85       public:

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

    87 	/// to an undefined value.

    88 	NodeIt() { }

    89 	/// Copy constructor.

    90 	NodeIt(const NodeIt&) { }

    91 	/// Invalid constructor \& conversion.

    93 	/// Initialize the iterator to be invalid.

    94 	/// \sa Invalid for more details.

    95 	NodeIt(Invalid) { }

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

    97 	NodeIt(const StaticGraphSkeleton& g) { }

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

    99 	/// iterator n. This feature necessitates that each time we

   100 	/// iterate the node-set, the iteration order is the same.

   101 	NodeIt(const StaticGraphSkeleton& g, const Node& n) { }

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

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

   104       };

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

   108       class Edge {

   109       public:

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

   111 	/// to an undefined value.

   112 	Edge() { }

   113 	/// Copy constructor.

   114 	Edge(const Edge&) { }

   115 	/// Initialize the iterator to be invalid.

   116 	Edge(Invalid) { }

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

   118 	/// same object or both are invalid.

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

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

   121 	bool operator<(Edge) const { return true; }

   122       };

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

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

   127       /// of a graph.

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

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

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

   131       /// \code

   132       /// int count=0;

   133       /// for (Graph::OutEdgeIt e(g, n); g.valid(e); ++e) ++count;

   134       /// \endcode

   136       class OutEdgeIt : public Edge {

   137       public:

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

   139 	/// to an undefined value.

   140 	OutEdgeIt() { }

   141 	/// Copy constructor.

   142 	OutEdgeIt(const OutEdgeIt&) { }

   143 	/// Initialize the iterator to be invalid.

   144 	OutEdgeIt(Invalid) { }

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

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

   148 	/// node

   149 	///@param n the node

   150 	///@param g the graph

   151 	OutEdgeIt(const StaticGraphSkeleton& g, const Node& n) { }

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

   153 	/// This feature necessitates that each time we

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

   155 	OutEdgeIt(const StaticGraphSkeleton& g, const Edge& e) { }

   156 	/// Assign the iterator to the next outedge of the corresponding node.

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

   158       };

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

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

   163       /// of a graph.

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

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

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

   167       /// \code

   168       /// int count=0;

   169       /// for(Graph::InEdgeIt e(g, n); g.valid(e); ++) ++count;

   170       /// \endcode

   172       class InEdgeIt : public Edge {

   173       public:

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

   175 	/// to an undefined value.

   176 	InEdgeIt() { }

   177 	/// Copy constructor.

   178 	InEdgeIt(const InEdgeIt&) { }

   179 	/// Initialize the iterator to be invalid.

   180 	InEdgeIt(Invalid) { }

   181 	/// .

   182 	InEdgeIt(const StaticGraphSkeleton&, const Node&) { }

   183 	/// .

   184 	InEdgeIt(const StaticGraphSkeleton&, const Edge&) { }

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

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

   187       };

   188       //  class SymEdgeIt : public Edge {};

   190       /// This iterator goes through each edge.

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

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

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

   195       /// \code

   196       /// int count=0;

   197       /// for(Graph::EdgeIt e(g); g.valid(e); ++e) ++count;

   198       /// \endcode

   199       class EdgeIt : public Edge {

   200       public:

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

   202 	/// to an undefined value.

   203 	EdgeIt() { }

   204 	/// Copy constructor.

   205 	EdgeIt(const EdgeIt&) { }

   206 	/// Initialize the iterator to be invalid.

   207 	EdgeIt(Invalid) { }

   208 	/// .

   209 	EdgeIt(const StaticGraphSkeleton&) { }

   210 	/// .

   211 	EdgeIt(const StaticGraphSkeleton&, const Edge&) { }

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

   213       };

   215       /// First node of the graph.

   217       /// \retval i the first node.

   218       /// \return the first node.

   219       ///

   220       NodeIt& first(NodeIt& i) const { return i; }

   222       /// The first incoming edge.

   223       InEdgeIt& first(InEdgeIt &i, Node) const { return i; }

   224       /// The first outgoing edge.

   225       OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }

   226       //  SymEdgeIt& first(SymEdgeIt&, Node) const { return i; }

   227       /// The first edge of the Graph.

   228       EdgeIt& first(EdgeIt& i) const { return i; }

   230       //     Node getNext(Node) const {}

   231       //     InEdgeIt getNext(InEdgeIt) const {}

   232       //     OutEdgeIt getNext(OutEdgeIt) const {}

   233       //     //SymEdgeIt getNext(SymEdgeIt) const {}

   234       //     EdgeIt getNext(EdgeIt) const {}

   236       /// Go to the next node.

   237       NodeIt& next(NodeIt& i) const { return i; }

   238       /// Go to the next incoming edge.

   239       InEdgeIt& next(InEdgeIt& i) const { return i; }

   240       /// Go to the next outgoing edge.

   241       OutEdgeIt& next(OutEdgeIt& i) const { return i; }

   242       //SymEdgeIt& next(SymEdgeIt&) const { }

   243       /// Go to the next edge.

   244       EdgeIt& next(EdgeIt& i) const { return i; }

   246       ///Gives back the head node of an edge.

   247       Node head(Edge) const { return INVALID; }

   248       ///Gives back the tail node of an edge.

   249       Node tail(Edge) const { return INVALID; }

   251       //   Node aNode(InEdgeIt) const {}

   252       //   Node aNode(OutEdgeIt) const {}

   253       //   Node aNode(SymEdgeIt) const {}

   255       //   Node bNode(InEdgeIt) const {}

   256       //   Node bNode(OutEdgeIt) const {}

   257       //   Node bNode(SymEdgeIt) const {}

   259       /// Checks if a node iterator is valid

   261       ///\todo Maybe, it would be better if iterator converted to

   262       ///bool directly, as Jacint prefers.

   263       bool valid(const Node&) const { return true; }

   264       /// Checks if an edge iterator is valid

   266       ///\todo Maybe, it would be better if iterator converted to

   267       ///bool directly, as Jacint prefers.

   268       bool valid(const Edge&) const { return true; }

   270       ///Gives back the \e id of a node.

   272       ///\warning Not all graph structures provide this feature.

   273       ///

   274       int id(const Node&) const { return 0; }

   275       ///Gives back the \e id of an edge.

   277       ///\warning Not all graph structures provide this feature.

   278       ///

   279       int id(const Edge&) const { return 0; }

   281       /// Resets the graph.

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

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

   285       void clear() { }

   287       int nodeNum() const { return 0; }

   288       int edgeNum() const { return 0; }

   291       ///Reference map of the nodes to type \c T.

   293       ///Reference map of the nodes to type \c T.

   294       /// \sa ReferenceSkeleton

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

   296       /// needs extra attention!

   298       template<class T> class NodeMap

   299 	: public ReferenceMap< Node, T >

   300       {

   301       public:

   303 	NodeMap(const StaticGraphSkeleton&) { }

   304 	NodeMap(const StaticGraphSkeleton&, T) { }

   306 	///Copy constructor

   307 	template<typename TT> NodeMap(const NodeMap<TT>&) { }

   308 	///Assignment operator

   309 	template<typename TT> NodeMap& operator=(const NodeMap<TT>&)

   310 	{ return *this; }

   311       };

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

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

   316       /// \sa ReferenceSkeleton

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

   318       /// needs extra attention!

   319       template<class T> class EdgeMap

   320 	: public ReferenceMap<Edge,T>

   321       {

   322       public:

   323 	typedef T ValueType;

   324 	typedef Edge KeyType;

   326 	EdgeMap(const StaticGraphSkeleton&) { }

   327 	EdgeMap(const StaticGraphSkeleton&, T) { }

   329 	///Copy constructor

   330 	template<typename TT> EdgeMap(const EdgeMap<TT>&) { }

   331 	///Assignment operator

   332 	template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)

   333 	{ return *this; }

   334       };

   335     };

   339     /// An empty graph class.

   341     /// This class provides everything that \c StaticGraphSkeleton

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

   343     /// graph from scratch.

   344     class GraphSkeleton : public StaticGraphSkeleton

   345     {

   346     public:

   347       /// Defalult constructor.

   348       GraphSkeleton() { }

   349       ///Copy consructor.

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

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

   353       GraphSkeleton(const GraphSkeleton&) { }

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

   357       /// \return the new node.

   358       ///

   359       Node addNode() { return INVALID; }

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

   362       ///Add a new edge to the graph with tail node \c tail

   363       ///and head node \c head.

   364       ///\return the new edge.

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

   367       /// Resets the graph.

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

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

   371       /// \todo It might belong to \c EraseableGraphSkeleton.

   372       void clear() { }

   373     };

   375     /// An empty eraseable graph class.

   377     /// This class is an extension of \c GraphSkeleton. It also makes it

   378     /// possible to erase edges or nodes.

   379     class EraseableGraphSkeleton : public GraphSkeleton

   380     {

   381     public:

   382       /// Deletes a node.

   383       void erase(Node n) { }

   384       /// Deletes an edge.

   385       void erase(Edge e) { }

   387       /// Defalult constructor.

   388       EraseableGraphSkeleton() { }

   389       ///Copy consructor.

   390       EraseableGraphSkeleton(const GraphSkeleton&) { }

   391     };

   393     // @}

   394   } //namespace skeleton

   396 } //namespace hugo

   400 // class EmptyBipGraph : public Graph Skeleton

   401 // {

   402 //   class ANode {};

   403 //   class BNode {};

   405 //   ANode &next(ANode &) {}

   406 //   BNode &next(BNode &) {}

   408 //   ANode &getFirst(ANode &) const {}

   409 //   BNode &getFirst(BNode &) const {}

   411 //   enum NodeClass { A = 0, B = 1 };

   412 //   NodeClass getClass(Node n) {}

   414 // }

   416 #endif // HUGO_SKELETON_GRAPH_H

author	alpar
	Fri, 03 Sep 2004 10:28:21 +0000
changeset 794	d9ec436d11fe
parent 774	4297098d9677
child 801	48638058e188
permissions	-rw-r--r--