COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/skeletons/sym_graph.h @ 909:6a22e0dfd453

Last change on this file since 909:6a22e0dfd453 was 909:6a22e0dfd453, checked in by Balazs Dezso, 20 years ago

New symmetric Graph concept.
New symmetric list and smart graph.
Symmetric Graph tests based on the Graph Tests.

File size: 18.2 KB
Line 
1/* -*- C++ -*-
2 * src/hugo/skeletons/graph.h - Part of HUGOlib, 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 */
16
17#ifndef HUGO_SKELETON_SYM_GRAPH_H
18#define HUGO_SKELETON_SYM_GRAPH_H
19
20///\ingroup skeletons
21///\file
22///\brief Declaration of SymGraph.
23
24#include <hugo/invalid.h>
25#include <hugo/skeletons/graph.h>
26#include <hugo/skeletons/maps.h>
27
28namespace hugo {
29  namespace skeleton {
30   
31    /// \addtogroup skeletons
32    /// @{
33
34    /// An empty static graph class.
35 
36    /// This class provides all the common features of a symmetric
37    /// graph structure, however completely without implementations and
38    /// real data structures behind the interface.
39    /// All graph algorithms should compile with this class, but it will not
40    /// run properly, of course.
41    ///
42    /// It can be used for checking the interface compatibility,
43    /// or it can serve as a skeleton of a new symmetric graph structure.
44    ///
45    /// Also, you will find here the full documentation of a certain graph
46    /// feature, the documentation of a real symmetric graph imlementation
47    /// like @ref SymListGraph or
48    /// @ref SymSmartGraph will just refer to this structure.
49    class StaticSymGraph
50    {
51    public:
52      /// Defalult constructor.
53
54      /// Defalult constructor.
55      ///
56      StaticSymGraph() { }
57      ///Copy consructor.
58
59//       ///\todo It is not clear, what we expect from a copy constructor.
60//       ///E.g. How to assign the nodes/edges to each other? What about maps?
61//       StaticGraph(const StaticGraph& g) { }
62
63      /// The base type of node iterators,
64      /// or in other words, the trivial node iterator.
65
66      /// This is the base type of each node iterator,
67      /// thus each kind of node iterator converts to this.
68      /// More precisely each kind of node iterator should be inherited
69      /// from the trivial node iterator.
70      class Node {
71      public:
72        /// Default constructor
73
74        /// @warning The default constructor sets the iterator
75        /// to an undefined value.
76        Node() { }
77        /// Copy constructor.
78
79        /// Copy constructor.
80        ///
81        Node(const Node&) { }
82
83        /// Invalid constructor \& conversion.
84
85        /// This constructor initializes the iterator to be invalid.
86        /// \sa Invalid for more details.
87        Node(Invalid) { }
88        /// Equality operator
89
90        /// Two iterators are equal if and only if they point to the
91        /// same object or both are invalid.
92        bool operator==(Node) const { return true; }
93
94        /// Inequality operator
95       
96        /// \sa \ref operator==(Node n)
97        ///
98        bool operator!=(Node) const { return true; }
99
100        ///Comparison operator.
101
102        ///This is a strict ordering between the nodes.
103        ///
104        ///This ordering can be different from the order in which NodeIt
105        ///goes through the nodes.
106        ///\todo Possibly we don't need it.
107        bool operator<(Node) const { return true; }
108      };
109   
110      /// This iterator goes through each node.
111
112      /// This iterator goes through each node.
113      /// Its usage is quite simple, for example you can count the number
114      /// of nodes in graph \c g of type \c Graph like this:
115      /// \code
116      /// int count=0;
117      /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
118      /// \endcode
119      class NodeIt : public Node {
120      public:
121        /// Default constructor
122
123        /// @warning The default constructor sets the iterator
124        /// to an undefined value.
125        NodeIt() { }
126        /// Copy constructor.
127       
128        /// Copy constructor.
129        ///
130        NodeIt(const NodeIt&) { }
131        /// Invalid constructor \& conversion.
132
133        /// Initialize the iterator to be invalid.
134        /// \sa Invalid for more details.
135        NodeIt(Invalid) { }
136        /// Sets the iterator to the first node.
137
138        /// Sets the iterator to the first node of \c g.
139        ///
140        NodeIt(const StaticSymGraph& g) { }
141        /// Node -> NodeIt conversion.
142
143        /// Sets the iterator to the node of \c g pointed by the trivial
144        /// iterator n.
145        /// This feature necessitates that each time we
146        /// iterate the edge-set, the iteration order is the same.
147        NodeIt(const StaticSymGraph& g, const Node& n) { }
148        /// Next node.
149
150        /// Assign the iterator to the next node.
151        ///
152        NodeIt& operator++() { return *this; }
153      };
154   
155   
156      /// The base type of the symmetric edge iterators.
157
158      /// The base type of the symmetric edge iterators.
159      ///
160      class SymEdge {
161      public:
162        /// Default constructor
163
164        /// @warning The default constructor sets the iterator
165        /// to an undefined value.
166        SymEdge() { }
167        /// Copy constructor.
168
169        /// Copy constructor.
170        ///
171        SymEdge(const SymEdge&) { }
172        /// Initialize the iterator to be invalid.
173
174        /// Initialize the iterator to be invalid.
175        ///
176        SymEdge(Invalid) { }
177        /// Equality operator
178
179        /// Two iterators are equal if and only if they point to the
180        /// same object or both are invalid.
181        bool operator==(SymEdge) const { return true; }
182        /// Inequality operator
183
184        /// \sa \ref operator==(Node n)
185        ///
186        bool operator!=(SymEdge) const { return true; }
187        ///Comparison operator.
188
189        ///This is a strict ordering between the nodes.
190        ///
191        ///This ordering can be different from the order in which NodeIt
192        ///goes through the nodes.
193        ///\todo Possibly we don't need it.
194        bool operator<(SymEdge) const { return true; }
195      };
196
197
198      /// The base type of the edge iterators.
199
200      /// The base type of the edge iterators.
201      ///
202      class Edge : public SymEdge {
203      public:
204        /// Default constructor
205
206        /// @warning The default constructor sets the iterator
207        /// to an undefined value.
208        Edge() { }
209        /// Copy constructor.
210
211        /// Copy constructor.
212        ///
213        Edge(const Edge&) { }
214        /// Initialize the iterator to be invalid.
215
216        /// Initialize the iterator to be invalid.
217        ///
218        Edge(Invalid) { }
219        /// Equality operator
220
221        /// Two iterators are equal if and only if they point to the
222        /// same object or both are invalid.
223        bool operator==(Edge) const { return true; }
224        /// Inequality operator
225
226        /// \sa \ref operator==(Node n)
227        ///
228        bool operator!=(Edge) const { return true; }
229        ///Comparison operator.
230
231        ///This is a strict ordering between the nodes.
232        ///
233        ///This ordering can be different from the order in which NodeIt
234        ///goes through the nodes.
235        ///\todo Possibly we don't need it.
236        bool operator<(Edge) const { return true; }
237      };
238   
239      /// This iterator goes trough the outgoing edges of a node.
240
241      /// This iterator goes trough the \e outgoing edges of a certain node
242      /// of a graph.
243      /// Its usage is quite simple, for example you can count the number
244      /// of outgoing edges of a node \c n
245      /// in graph \c g of type \c Graph as follows.
246      /// \code
247      /// int count=0;
248      /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
249      /// \endcode
250   
251      class OutEdgeIt : public Edge {
252      public:
253        /// Default constructor
254
255        /// @warning The default constructor sets the iterator
256        /// to an undefined value.
257        OutEdgeIt() { }
258        /// Copy constructor.
259
260        /// Copy constructor.
261        ///
262        OutEdgeIt(const OutEdgeIt&) { }
263        /// Initialize the iterator to be invalid.
264
265        /// Initialize the iterator to be invalid.
266        ///
267        OutEdgeIt(Invalid) { }
268        /// This constructor sets the iterator to first outgoing edge.
269   
270        /// This constructor set the iterator to the first outgoing edge of
271        /// node
272        ///@param n the node
273        ///@param g the graph
274        OutEdgeIt(const StaticSymGraph& g, const Node& n) { }
275        /// Edge -> OutEdgeIt conversion
276
277        /// Sets the iterator to the value of the trivial iterator \c e.
278        /// This feature necessitates that each time we
279        /// iterate the edge-set, the iteration order is the same.
280        OutEdgeIt(const StaticSymGraph& g, const Edge& e) { }
281        ///Next outgoing edge
282       
283        /// Assign the iterator to the next
284        /// outgoing edge of the corresponding node.
285        OutEdgeIt& operator++() { return *this; }
286      };
287
288      /// This iterator goes trough the incoming edges of a node.
289
290      /// This iterator goes trough the \e incoming edges of a certain node
291      /// of a graph.
292      /// Its usage is quite simple, for example you can count the number
293      /// of outgoing edges of a node \c n
294      /// in graph \c g of type \c Graph as follows.
295      /// \code
296      /// int count=0;
297      /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
298      /// \endcode
299
300      class InEdgeIt : public Edge {
301      public:
302        /// Default constructor
303
304        /// @warning The default constructor sets the iterator
305        /// to an undefined value.
306        InEdgeIt() { }
307        /// Copy constructor.
308
309        /// Copy constructor.
310        ///
311        InEdgeIt(const InEdgeIt&) { }
312        /// Initialize the iterator to be invalid.
313
314        /// Initialize the iterator to be invalid.
315        ///
316        InEdgeIt(Invalid) { }
317        /// This constructor sets the iterator to first incoming edge.
318   
319        /// This constructor set the iterator to the first incoming edge of
320        /// node
321        ///@param n the node
322        ///@param g the graph
323        InEdgeIt(const StaticSymGraph& g, const Node& n) { }
324        /// Edge -> InEdgeIt conversion
325
326        /// Sets the iterator to the value of the trivial iterator \c e.
327        /// This feature necessitates that each time we
328        /// iterate the edge-set, the iteration order is the same.
329        InEdgeIt(const StaticSymGraph& g, const Edge& n) { }
330        /// Next incoming edge
331
332        /// Assign the iterator to the next inedge of the corresponding node.
333        ///
334        InEdgeIt& operator++() { return *this; }
335      };
336      /// This iterator goes through each symmetric edge.
337
338      /// This iterator goes through each symmetric edge of a graph.
339      /// Its usage is quite simple, for example you can count the number
340      /// of symmetric edges in a graph \c g of type \c Graph as follows:
341      /// \code
342      /// int count=0;
343      /// for(Graph::SymEdgeIt e(g); e!=INVALID; ++e) ++count;
344      /// \endcode
345      class SymEdgeIt : public SymEdge {
346      public:
347        /// Default constructor
348
349        /// @warning The default constructor sets the iterator
350        /// to an undefined value.
351        SymEdgeIt() { }
352        /// Copy constructor.
353
354        /// Copy constructor.
355        ///
356        SymEdgeIt(const SymEdgeIt&) { }
357        /// Initialize the iterator to be invalid.
358
359        /// Initialize the iterator to be invalid.
360        ///
361        SymEdgeIt(Invalid) { }
362        /// This constructor sets the iterator to first edge.
363   
364        /// This constructor set the iterator to the first edge of
365        /// node
366        ///@param g the graph
367        SymEdgeIt(const StaticSymGraph& g) { }
368        /// Edge -> EdgeIt conversion
369
370        /// Sets the iterator to the value of the trivial iterator \c e.
371        /// This feature necessitates that each time we
372        /// iterate the edge-set, the iteration order is the same.
373        SymEdgeIt(const StaticSymGraph&, const SymEdge&) { }
374        ///Next edge
375       
376        /// Assign the iterator to the next
377        /// edge of the corresponding node.
378        SymEdgeIt& operator++() { return *this; }
379      };
380      /// This iterator goes through each edge.
381
382      /// This iterator goes through each edge of a graph.
383      /// Its usage is quite simple, for example you can count the number
384      /// of edges in a graph \c g of type \c Graph as follows:
385      /// \code
386      /// int count=0;
387      /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
388      /// \endcode
389      class EdgeIt : public Edge {
390      public:
391        /// Default constructor
392
393        /// @warning The default constructor sets the iterator
394        /// to an undefined value.
395        EdgeIt() { }
396        /// Copy constructor.
397
398        /// Copy constructor.
399        ///
400        EdgeIt(const EdgeIt&) { }
401        /// Initialize the iterator to be invalid.
402
403        /// Initialize the iterator to be invalid.
404        ///
405        EdgeIt(Invalid) { }
406        /// This constructor sets the iterator to first edge.
407   
408        /// This constructor set the iterator to the first edge of
409        /// node
410        ///@param g the graph
411        EdgeIt(const StaticSymGraph& g) { }
412        /// Edge -> EdgeIt conversion
413
414        /// Sets the iterator to the value of the trivial iterator \c e.
415        /// This feature necessitates that each time we
416        /// iterate the edge-set, the iteration order is the same.
417        EdgeIt(const StaticSymGraph&, const Edge&) { }
418        ///Next edge
419       
420        /// Assign the iterator to the next
421        /// edge of the corresponding node.
422        EdgeIt& operator++() { return *this; }
423      };
424
425      /// First node of the graph.
426
427      /// \retval i the first node.
428      /// \return the first node.
429      ///
430      NodeIt& first(NodeIt& i) const { return i; }
431
432      /// The first incoming edge.
433
434      /// The first incoming edge.
435      ///
436      InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
437      /// The first outgoing edge.
438
439      /// The first outgoing edge.
440      ///
441      OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
442      /// The first edge of the Graph.
443
444      /// The first edge of the Graph.
445      ///
446      EdgeIt& first(EdgeIt& i) const { return i; }
447      /// The first symmetric edge of the Graph.
448
449      /// The first symmetric edge of the Graph.
450      ///
451      SymEdgeIt& first(SymEdgeIt& i) const { return i; }
452
453      ///Gives back the head node of an edge.
454
455      ///Gives back the head node of an edge.
456      ///
457      Node head(Edge) const { return INVALID; }
458      ///Gives back the tail node of an edge.
459
460      ///Gives back the tail node of an edge.
461      ///
462      Node tail(Edge) const { return INVALID; }
463 
464      ///Gives back the first node of an symmetric edge.
465
466      ///Gives back the first node of an symmetric edge.
467      ///
468      Node head(SymEdge) const { return INVALID; }
469      ///Gives back the second node of an symmetric edge.
470
471      ///Gives back the second node of an symmetric edge.
472      ///
473      Node tail(SymEdge) const { return INVALID; }
474      ///Gives back the \e id of a node.
475
476      ///\warning Not all graph structures provide this feature.
477      ///
478      ///\todo Should each graph provide \c id?
479      int id(const Node&) const { return 0; }
480      ///Gives back the \e id of an edge.
481
482      ///\warning Not all graph structures provide this feature.
483      ///
484      ///\todo Should each graph provide \c id?
485      int id(const Edge&) const { return 0; }
486
487      ///\warning Not all graph structures provide this feature.
488      ///
489      ///\todo Should each graph provide \c id?
490      int id(const SymEdge&) const { return 0; }
491
492      /// .
493     
494      ///\todo Should it be in the concept?
495      ///
496      int nodeNum() const { return 0; }
497      /// .
498
499      ///\todo Should it be in the concept?
500      ///
501      int edgeNum() const { return 0; }
502
503      ///\todo Should it be in the concept?
504      ///
505      int symEdgeNum() const { return 0; }
506
507
508      /// Gives back the forward directed edge of the symmetric edge.
509      Edge forward(SymEdge) const {return INVALID;}
510
511      /// Gives back the backward directed edge of the symmetric edge.
512      Edge backward(SymEdge) const {return INVALID;};
513
514      /// Gives back the opposite of the edge.
515      Edge opposite(Edge) const {return INVALID;}
516
517      ///Reference map of the nodes to type \c T.
518      /// \ingroup skeletons
519      ///Reference map of the nodes to type \c T.
520      /// \sa Reference
521      /// \warning Making maps that can handle bool type (NodeMap<bool>)
522      /// needs some extra attention!
523      template<class T> class NodeMap : public ReferenceMap< Node, T >
524      {
525      public:
526
527        /// .
528        NodeMap(const StaticSymGraph&) { }
529        /// .
530        NodeMap(const StaticSymGraph&, T) { }
531
532        ///Copy constructor
533        template<typename TT> NodeMap(const NodeMap<TT>&) { }
534        ///Assignment operator
535        template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
536        { return *this; }
537      };
538
539      ///Reference map of the edges to type \c T.
540
541      /// \ingroup skeletons
542      ///Reference map of the edges to type \c T.
543      /// \sa Reference
544      /// \warning Making maps that can handle bool type (EdgeMap<bool>)
545      /// needs some extra attention!
546      template<class T> class EdgeMap
547        : public ReferenceMap<Edge,T>
548      {
549      public:
550
551        /// .
552        EdgeMap(const StaticSymGraph&) { }
553        /// .
554        EdgeMap(const StaticSymGraph&, T) { }
555   
556        ///Copy constructor
557        template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
558        ///Assignment operator
559        template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
560        { return *this; }
561      };
562
563      ///Reference map of the edges to type \c T.
564
565      /// \ingroup skeletons
566      ///Reference map of the symmetric edges to type \c T.
567      /// \sa Reference
568      /// \warning Making maps that can handle bool type (EdgeMap<bool>)
569      /// needs some extra attention!
570      template<class T> class SymEdgeMap
571        : public ReferenceMap<SymEdge,T>
572      {
573      public:
574
575        /// .
576        SymEdgeMap(const StaticSymGraph&) { }
577        /// .
578        SymEdgeMap(const StaticSymGraph&, T) { }
579   
580        ///Copy constructor
581        template<typename TT> SymEdgeMap(const SymEdgeMap<TT>&) { }
582        ///Assignment operator
583        template<typename TT> SymEdgeMap &operator=(const SymEdgeMap<TT>&)
584        { return *this; }
585      };
586    };
587
588
589 
590    /// An empty non-static graph class.
591
592    /// This class provides everything that \ref StaticGraph
593    /// with additional functionality which enables to build a
594    /// graph from scratch.
595    class ExtendableSymGraph : public StaticSymGraph
596    {
597    public:
598      /// Defalult constructor.
599
600      /// Defalult constructor.
601      ///
602      ExtendableSymGraph() { }
603      ///Add a new node to the graph.
604
605      /// \return the new node.
606      ///
607      Node addNode() { return INVALID; }
608      ///Add a new edge to the graph.
609
610      ///Add a new symmetric edge to the graph with tail node \c t
611      ///and head node \c h.
612      ///\return the new edge.
613      SymEdge addEdge(Node h, Node t) { return INVALID; }
614   
615      /// Resets the graph.
616
617      /// This function deletes all edges and nodes of the graph.
618      /// It also frees the memory allocated to store them.
619      /// \todo It might belong to \ref ErasableGraph.
620      void clear() { }
621    };
622
623    /// An empty erasable graph class.
624 
625    /// This class is an extension of \ref ExtendableGraph. It also makes it
626    /// possible to erase edges or nodes.
627    class ErasableSymGraph : public ExtendableSymGraph
628    {
629    public:
630      /// Defalult constructor.
631
632      /// Defalult constructor.
633      ///
634      ErasableSymGraph() { }
635      /// Deletes a node.
636
637      /// Deletes node \c n node.
638      ///
639      void erase(Node n) { }
640      /// Deletes an edge.
641
642      /// Deletes edge \c e edge.
643      ///
644      void erase(SymEdge e) { }
645    };
646
647    // @}
648  } //namespace skeleton 
649} //namespace hugo
650
651
652
653#endif // HUGO_SKELETON_GRAPH_H
Note: See TracBrowser for help on using the repository browser.