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

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

     2 #ifndef HUGO_SKELETON_GRAPH_H

     3 #define HUGO_SKELETON_GRAPH_H

     5 ///\file

     6 ///\brief Declaration of GraphSkeleton.

     8 #include <hugo/invalid.h>

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

    11 /// The namespace of HugoLib

    12 namespace hugo {

    13   namespace skeleton {

    15     // @defgroup empty_graph The GraphSkeleton class

    16     // @{

    18     /// An empty static graph class.

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

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

    22     /// behind the interface.

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

    24     /// run properly, of course.

    25     ///

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

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

    28     ///

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

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

    31     /// like @ref ListGraph or

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

    33     class StaticGraphSkeleton

    34     {

    35     public:

    36       /// Defalult constructor.

    37       StaticGraphSkeleton() {}

    38       ///Copy consructor.

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

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

    42       StaticGraphSkeleton(const StaticGraphSkeleton &G) {}

    44       /// The base type of the node iterators.

    46       /// This is the base type of each node iterators,

    47       /// thus each kind of node iterator will convert to this.

    48       class Node {

    49       public:

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

    51 	/// to an undefined value.

    52 	Node() {}   //FIXME

    53 	/// Invalid constructor \& conversion.

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

    56 	/// \sa Invalid for more details.

    58 	Node(Invalid) {}

    59 	//Node(const Node &) {}

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

    62 	/// same object or both are invalid.

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

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

    66 	///

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

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

    70       };

    72       /// This iterator goes through each node.

    74       /// This iterator goes through each node.

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

    76       /// of nodes in graph \c G of type \c Graph like this:

    77       /// \code

    78       ///int count=0;

    79       ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;

    80       /// \endcode

    81       class NodeIt : public Node {

    82       public:

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

    84 	/// to an undefined value.

    85 	NodeIt() {} //FIXME

    86 	/// Invalid constructor \& conversion.

    88 	/// Initialize the iterator to be invalid

    89 	/// \sa Invalid for more details.

    90 	NodeIt(Invalid) {}

    91 	/// Sets the iterator to the first node of \c G.

    92 	NodeIt(const StaticGraphSkeleton &) {}

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

    94 	/// to an undefined value.

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

    96       };

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

   100       class Edge {

   101       public:

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

   103 	/// to an undefined value.

   104 	Edge() {}   //FIXME

   105 	/// Initialize the iterator to be invalid

   106 	Edge(Invalid) {}

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

   108 	/// same object or both are invalid.

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

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

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

   112       };

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

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

   117       /// of a graph.

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

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

   120       /// in graph \c G of type \c Graph as follows.

   121       /// \code

   122       ///int count=0;

   123       ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;

   124       /// \endcode

   126       class OutEdgeIt : public Edge {

   127       public:

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

   129 	/// to an undefined value.

   130 	OutEdgeIt() {}

   131 	/// Initialize the iterator to be invalid

   132 	OutEdgeIt(Invalid) {}

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

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

   136 	/// node

   137 	///@param n the node

   138 	///@param G the graph

   139 	OutEdgeIt(const StaticGraphSkeleton &, Node) {}

   140       };

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

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

   145       /// of a graph.

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

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

   148       /// in graph \c G of type \c Graph as follows.

   149       /// \code

   150       ///int count=0;

   151       ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;

   152       /// \endcode

   154       class InEdgeIt : public Edge {

   155       public:

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

   157 	/// to an undefined value.

   158 	InEdgeIt() {}

   159 	/// Initialize the iterator to be invalid

   160 	InEdgeIt(Invalid) {}

   161 	InEdgeIt(const StaticGraphSkeleton &, Node) {}

   162       };

   163       //  class SymEdgeIt : public Edge {};

   165       /// This iterator goes through each edge.

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

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

   169       /// of edges in a graph \c G of type \c Graph as follows:

   170       /// \code

   171       ///int count=0;

   172       ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;

   173       /// \endcode

   174       class EdgeIt : public Edge {

   175       public:

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

   177 	/// to an undefined value.

   178 	EdgeIt() {}

   179 	/// Initialize the iterator to be invalid

   180 	EdgeIt(Invalid) {}

   181 	EdgeIt(const StaticGraphSkeleton &) {}

   182       };

   184       /// First node of the graph.

   186       /// \retval i the first node.

   187       /// \return the first node.

   188       ///

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

   191       /// The first incoming edge.

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

   193       /// The first outgoing edge.

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

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

   196       /// The first edge of the Graph.

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

   199       //     Node getNext(Node) const {}

   200       //     InEdgeIt getNext(InEdgeIt) const {}

   201       //     OutEdgeIt getNext(OutEdgeIt) const {}

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

   203       //     EdgeIt getNext(EdgeIt) const {}

   205       /// Go to the next node.

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

   207       /// Go to the next incoming edge.

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

   209       /// Go to the next outgoing edge.

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

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

   212       /// Go to the next edge.

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

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

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

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

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

   220       //   Node aNode(InEdgeIt) const {}

   221       //   Node aNode(OutEdgeIt) const {}

   222       //   Node aNode(SymEdgeIt) const {}

   224       //   Node bNode(InEdgeIt) const {}

   225       //   Node bNode(OutEdgeIt) const {}

   226       //   Node bNode(SymEdgeIt) const {}

   228       /// Checks if a node iterator is valid

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

   231       ///bool directly, as Jacint prefers.

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

   233       /// Checks if an edge iterator is valid

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

   236       ///bool directly, as Jacint prefers.

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

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

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

   242       ///

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

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

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

   247       ///

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

   250       /// Resets the graph.

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

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

   254       void clear() {}

   256       int nodeNum() const { return 0;}

   257       int edgeNum() const { return 0;}

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

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

   264       /// \sa ReferenceSkeleton

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

   266       /// needs extra attention!

   268       template<class T> class NodeMap

   269 	: public ReferenceMap< Node, T >

   270       {

   271       public:

   273 	class ReferenceMap<Node,T>;

   275 	NodeMap(const StaticGraphSkeleton &) {}

   276 	NodeMap(const StaticGraphSkeleton &, T) {}

   278 	///Copy constructor

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

   280 	///Assignment operator

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

   282 	{return *this;}

   283       };

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

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

   288       /// \sa ReferenceSkeleton

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

   290       /// needs extra attention!

   291       template<class T> class EdgeMap

   292 	: public ReferenceMap<Edge,T>

   293       {

   294       public:

   295 	typedef T ValueType;

   296 	typedef Edge KeyType;

   298 	EdgeMap(const StaticGraphSkeleton &) {}

   299 	EdgeMap(const StaticGraphSkeleton &, T ) {}

   301 	///Copy constructor

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

   303 	///Assignment operator

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

   305 	{return *this;}

   306       };

   307     };

   311     /// An empty graph class.

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

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

   315     /// graph from scratch.

   316     class GraphSkeleton : public StaticGraphSkeleton

   317     {

   318     public:

   319       /// Defalult constructor.

   320       GraphSkeleton() {}

   321       ///Copy consructor.

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

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

   325       GraphSkeleton(const GraphSkeleton &G) {}

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

   329       /// \return the new node.

   330       ///

   331       Node addNode() { return INVALID;}

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

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

   335       ///and head node \c head.

   336       ///\return the new edge.

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

   339       /// Resets the graph.

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

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

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

   344       void clear() {}

   345     };

   347     /// An empty eraseable graph class.

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

   350     /// possible to erase edges or nodes.

   351     class EraseableGraphSkeleton : public GraphSkeleton

   352     {

   353     public:

   354       /// Deletes a node.

   355       void erase(Node n) {}

   356       /// Deletes an edge.

   357       void erase(Edge e) {}

   359       /// Defalult constructor.

   360       EraseableGraphSkeleton() {}

   361       ///Copy consructor.

   362       EraseableGraphSkeleton(const GraphSkeleton &G) {}

   363     };

   365     // @}

   366   } //namespace skeleton

   368 } //namespace hugo

   372 // class EmptyBipGraph : public Graph Skeleton

   373 // {

   374 //   class ANode {};

   375 //   class BNode {};

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

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

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

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

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

   384 //   NodeClass getClass(Node n) {}

   386 // }

   388 #endif // HUGO_SKELETON_GRAPH_H

author	alpar
	Thu, 22 Jul 2004 19:59:18 +0000
changeset 732	33cbc0635e92
parent 542	69bde1d90c04
child 774	4297098d9677
permissions	-rw-r--r--