lemon/concepts/graph.h
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 22 Jan 2008 10:59:14 +0000
changeset 59 4ab73d92f0fb
child 61 d718974f1290
permissions -rw-r--r--
Merge
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2007
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 ///\ingroup graph_concepts
    20 ///\file
    21 ///\brief The concept of Undirected Graphs.
    22 
    23 #ifndef LEMON_CONCEPT_GRAPH_H
    24 #define LEMON_CONCEPT_GRAPH_H
    25 
    26 #include <lemon/concepts/graph_components.h>
    27 #include <lemon/concepts/graph.h>
    28 #include <lemon/bits/utility.h>
    29 
    30 namespace lemon {
    31   namespace concepts {
    32 
    33     /// \ingroup graph_concepts
    34     ///
    35     /// \brief Class describing the concept of Undirected Graphs.
    36     ///
    37     /// This class describes the common interface of all Undirected
    38     /// Graphs.
    39     ///
    40     /// As all concept describing classes it provides only interface
    41     /// without any sensible implementation. So any algorithm for
    42     /// undirected graph should compile with this class, but it will not
    43     /// run properly, of course.
    44     ///
    45     /// The LEMON undirected graphs also fulfill the concept of
    46     /// directed graphs (\ref lemon::concepts::Digraph "Digraph
    47     /// Concept"). Each edges can be seen as two opposite
    48     /// directed arc and consequently the undirected graph can be
    49     /// seen as the direceted graph of these directed arcs. The
    50     /// Graph has the Edge inner class for the edges and
    51     /// the Arc type for the directed arcs. The Arc type is
    52     /// convertible to Edge or inherited from it so from a directed
    53     /// arc we can get the represented edge.
    54     ///
    55     /// In the sense of the LEMON each edge has a default
    56     /// direction (it should be in every computer implementation,
    57     /// because the order of edge's nodes defines an
    58     /// orientation). With the default orientation we can define that
    59     /// the directed arc is forward or backward directed. With the \c
    60     /// direction() and \c direct() function we can get the direction
    61     /// of the directed arc and we can direct an edge.
    62     ///
    63     /// The EdgeIt is an iterator for the edges. We can use
    64     /// the EdgeMap to map values for the edges. The InArcIt and
    65     /// OutArcIt iterates on the same edges but with opposite
    66     /// direction. The IncArcIt iterates also on the same edges
    67     /// as the OutArcIt and InArcIt but it is not convertible to Arc just
    68     /// to Edge.  
    69     class Graph {
    70     public:
    71       /// \brief The undirected graph should be tagged by the
    72       /// UndirectedTag.
    73       ///
    74       /// The undirected graph should be tagged by the UndirectedTag. This
    75       /// tag helps the enable_if technics to make compile time 
    76       /// specializations for undirected graphs.  
    77       typedef True UndirectedTag;
    78 
    79       /// \brief The base type of node iterators, 
    80       /// or in other words, the trivial node iterator.
    81       ///
    82       /// This is the base type of each node iterator,
    83       /// thus each kind of node iterator converts to this.
    84       /// More precisely each kind of node iterator should be inherited 
    85       /// from the trivial node iterator.
    86       class Node {
    87       public:
    88         /// Default constructor
    89 
    90         /// @warning The default constructor sets the iterator
    91         /// to an undefined value.
    92         Node() { }
    93         /// Copy constructor.
    94 
    95         /// Copy constructor.
    96         ///
    97         Node(const Node&) { }
    98 
    99         /// Invalid constructor \& conversion.
   100 
   101         /// This constructor initializes the iterator to be invalid.
   102         /// \sa Invalid for more details.
   103         Node(Invalid) { }
   104         /// Equality operator
   105 
   106         /// Two iterators are equal if and only if they point to the
   107         /// same object or both are invalid.
   108         bool operator==(Node) const { return true; }
   109 
   110         /// Inequality operator
   111         
   112         /// \sa operator==(Node n)
   113         ///
   114         bool operator!=(Node) const { return true; }
   115 
   116 	/// Artificial ordering operator.
   117 	
   118 	/// To allow the use of graph descriptors as key type in std::map or
   119 	/// similar associative container we require this.
   120 	///
   121 	/// \note This operator only have to define some strict ordering of
   122 	/// the items; this order has nothing to do with the iteration
   123 	/// ordering of the items.
   124 	bool operator<(Node) const { return false; }
   125 
   126       };
   127     
   128       /// This iterator goes through each node.
   129 
   130       /// This iterator goes through each node.
   131       /// Its usage is quite simple, for example you can count the number
   132       /// of nodes in graph \c g of type \c Graph like this:
   133       ///\code
   134       /// int count=0;
   135       /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
   136       ///\endcode
   137       class NodeIt : public Node {
   138       public:
   139         /// Default constructor
   140 
   141         /// @warning The default constructor sets the iterator
   142         /// to an undefined value.
   143         NodeIt() { }
   144         /// Copy constructor.
   145         
   146         /// Copy constructor.
   147         ///
   148         NodeIt(const NodeIt& n) : Node(n) { }
   149         /// Invalid constructor \& conversion.
   150 
   151         /// Initialize the iterator to be invalid.
   152         /// \sa Invalid for more details.
   153         NodeIt(Invalid) { }
   154         /// Sets the iterator to the first node.
   155 
   156         /// Sets the iterator to the first node of \c g.
   157         ///
   158         NodeIt(const Graph&) { }
   159         /// Node -> NodeIt conversion.
   160 
   161         /// Sets the iterator to the node of \c the graph pointed by 
   162 	/// the trivial iterator.
   163         /// This feature necessitates that each time we 
   164         /// iterate the arc-set, the iteration order is the same.
   165         NodeIt(const Graph&, const Node&) { }
   166         /// Next node.
   167 
   168         /// Assign the iterator to the next node.
   169         ///
   170         NodeIt& operator++() { return *this; }
   171       };
   172     
   173     
   174       /// The base type of the edge iterators.
   175 
   176       /// The base type of the edge iterators.
   177       ///
   178       class Edge {
   179       public:
   180         /// Default constructor
   181 
   182         /// @warning The default constructor sets the iterator
   183         /// to an undefined value.
   184         Edge() { }
   185         /// Copy constructor.
   186 
   187         /// Copy constructor.
   188         ///
   189         Edge(const Edge&) { }
   190         /// Initialize the iterator to be invalid.
   191 
   192         /// Initialize the iterator to be invalid.
   193         ///
   194         Edge(Invalid) { }
   195         /// Equality operator
   196 
   197         /// Two iterators are equal if and only if they point to the
   198         /// same object or both are invalid.
   199         bool operator==(Edge) const { return true; }
   200         /// Inequality operator
   201 
   202         /// \sa operator==(Edge n)
   203         ///
   204         bool operator!=(Edge) const { return true; }
   205 
   206 	/// Artificial ordering operator.
   207 	
   208 	/// To allow the use of graph descriptors as key type in std::map or
   209 	/// similar associative container we require this.
   210 	///
   211 	/// \note This operator only have to define some strict ordering of
   212 	/// the items; this order has nothing to do with the iteration
   213 	/// ordering of the items.
   214 	bool operator<(Edge) const { return false; }
   215       };
   216 
   217       /// This iterator goes through each edge.
   218 
   219       /// This iterator goes through each edge of a graph.
   220       /// Its usage is quite simple, for example you can count the number
   221       /// of edges in a graph \c g of type \c Graph as follows:
   222       ///\code
   223       /// int count=0;
   224       /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
   225       ///\endcode
   226       class EdgeIt : public Edge {
   227       public:
   228         /// Default constructor
   229 
   230         /// @warning The default constructor sets the iterator
   231         /// to an undefined value.
   232         EdgeIt() { }
   233         /// Copy constructor.
   234 
   235         /// Copy constructor.
   236         ///
   237         EdgeIt(const EdgeIt& e) : Edge(e) { }
   238         /// Initialize the iterator to be invalid.
   239 
   240         /// Initialize the iterator to be invalid.
   241         ///
   242         EdgeIt(Invalid) { }
   243         /// This constructor sets the iterator to the first edge.
   244     
   245         /// This constructor sets the iterator to the first edge.
   246         EdgeIt(const Graph&) { }
   247         /// Edge -> EdgeIt conversion
   248 
   249         /// Sets the iterator to the value of the trivial iterator.
   250         /// This feature necessitates that each time we
   251         /// iterate the edge-set, the iteration order is the 
   252 	/// same.
   253         EdgeIt(const Graph&, const Edge&) { } 
   254         /// Next edge
   255         
   256         /// Assign the iterator to the next edge.
   257         EdgeIt& operator++() { return *this; }
   258       };
   259 
   260       /// \brief This iterator goes trough the incident undirected 
   261       /// arcs of a node.
   262       ///
   263       /// This iterator goes trough the incident edges
   264       /// of a certain node of a graph. You should assume that the 
   265       /// loop arcs will be iterated twice.
   266       /// 
   267       /// Its usage is quite simple, for example you can compute the
   268       /// degree (i.e. count the number of incident arcs of a node \c n
   269       /// in graph \c g of type \c Graph as follows. 
   270       ///
   271       ///\code
   272       /// int count=0;
   273       /// for(Graph::IncArcIt e(g, n); e!=INVALID; ++e) ++count;
   274       ///\endcode
   275       class IncArcIt : public Edge {
   276       public:
   277         /// Default constructor
   278 
   279         /// @warning The default constructor sets the iterator
   280         /// to an undefined value.
   281         IncArcIt() { }
   282         /// Copy constructor.
   283 
   284         /// Copy constructor.
   285         ///
   286         IncArcIt(const IncArcIt& e) : Edge(e) { }
   287         /// Initialize the iterator to be invalid.
   288 
   289         /// Initialize the iterator to be invalid.
   290         ///
   291         IncArcIt(Invalid) { }
   292         /// This constructor sets the iterator to first incident arc.
   293     
   294         /// This constructor set the iterator to the first incident arc of
   295         /// the node.
   296         IncArcIt(const Graph&, const Node&) { }
   297         /// Edge -> IncArcIt conversion
   298 
   299         /// Sets the iterator to the value of the trivial iterator \c e.
   300         /// This feature necessitates that each time we 
   301         /// iterate the arc-set, the iteration order is the same.
   302         IncArcIt(const Graph&, const Edge&) { }
   303         /// Next incident arc
   304 
   305         /// Assign the iterator to the next incident arc
   306 	/// of the corresponding node.
   307         IncArcIt& operator++() { return *this; }
   308       };
   309 
   310       /// The directed arc type.
   311 
   312       /// The directed arc type. It can be converted to the
   313       /// edge or it should be inherited from the undirected
   314       /// arc.
   315       class Arc : public Edge {
   316       public:
   317         /// Default constructor
   318 
   319         /// @warning The default constructor sets the iterator
   320         /// to an undefined value.
   321         Arc() { }
   322         /// Copy constructor.
   323 
   324         /// Copy constructor.
   325         ///
   326         Arc(const Arc& e) : Edge(e) { }
   327         /// Initialize the iterator to be invalid.
   328 
   329         /// Initialize the iterator to be invalid.
   330         ///
   331         Arc(Invalid) { }
   332         /// Equality operator
   333 
   334         /// Two iterators are equal if and only if they point to the
   335         /// same object or both are invalid.
   336         bool operator==(Arc) const { return true; }
   337         /// Inequality operator
   338 
   339         /// \sa operator==(Arc n)
   340         ///
   341         bool operator!=(Arc) const { return true; }
   342 
   343 	/// Artificial ordering operator.
   344 	
   345 	/// To allow the use of graph descriptors as key type in std::map or
   346 	/// similar associative container we require this.
   347 	///
   348 	/// \note This operator only have to define some strict ordering of
   349 	/// the items; this order has nothing to do with the iteration
   350 	/// ordering of the items.
   351 	bool operator<(Arc) const { return false; }
   352 	
   353       }; 
   354       /// This iterator goes through each directed arc.
   355 
   356       /// This iterator goes through each arc of a graph.
   357       /// Its usage is quite simple, for example you can count the number
   358       /// of arcs in a graph \c g of type \c Graph as follows:
   359       ///\code
   360       /// int count=0;
   361       /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
   362       ///\endcode
   363       class ArcIt : public Arc {
   364       public:
   365         /// Default constructor
   366 
   367         /// @warning The default constructor sets the iterator
   368         /// to an undefined value.
   369         ArcIt() { }
   370         /// Copy constructor.
   371 
   372         /// Copy constructor.
   373         ///
   374         ArcIt(const ArcIt& e) : Arc(e) { }
   375         /// Initialize the iterator to be invalid.
   376 
   377         /// Initialize the iterator to be invalid.
   378         ///
   379         ArcIt(Invalid) { }
   380         /// This constructor sets the iterator to the first arc.
   381     
   382         /// This constructor sets the iterator to the first arc of \c g.
   383         ///@param g the graph
   384         ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
   385         /// Arc -> ArcIt conversion
   386 
   387         /// Sets the iterator to the value of the trivial iterator \c e.
   388         /// This feature necessitates that each time we 
   389         /// iterate the arc-set, the iteration order is the same.
   390         ArcIt(const Graph&, const Arc&) { } 
   391         ///Next arc
   392         
   393         /// Assign the iterator to the next arc.
   394         ArcIt& operator++() { return *this; }
   395       };
   396    
   397       /// This iterator goes trough the outgoing directed arcs of a node.
   398 
   399       /// This iterator goes trough the \e outgoing arcs of a certain node
   400       /// of a graph.
   401       /// Its usage is quite simple, for example you can count the number
   402       /// of outgoing arcs of a node \c n
   403       /// in graph \c g of type \c Graph as follows.
   404       ///\code
   405       /// int count=0;
   406       /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
   407       ///\endcode
   408     
   409       class OutArcIt : public Arc {
   410       public:
   411         /// Default constructor
   412 
   413         /// @warning The default constructor sets the iterator
   414         /// to an undefined value.
   415         OutArcIt() { }
   416         /// Copy constructor.
   417 
   418         /// Copy constructor.
   419         ///
   420         OutArcIt(const OutArcIt& e) : Arc(e) { }
   421         /// Initialize the iterator to be invalid.
   422 
   423         /// Initialize the iterator to be invalid.
   424         ///
   425         OutArcIt(Invalid) { }
   426         /// This constructor sets the iterator to the first outgoing arc.
   427     
   428         /// This constructor sets the iterator to the first outgoing arc of
   429         /// the node.
   430         ///@param n the node
   431         ///@param g the graph
   432         OutArcIt(const Graph& n, const Node& g) {
   433 	  ignore_unused_variable_warning(n);
   434 	  ignore_unused_variable_warning(g);
   435 	}
   436         /// Arc -> OutArcIt conversion
   437 
   438         /// Sets the iterator to the value of the trivial iterator.
   439 	/// This feature necessitates that each time we 
   440         /// iterate the arc-set, the iteration order is the same.
   441         OutArcIt(const Graph&, const Arc&) { }
   442         ///Next outgoing arc
   443         
   444         /// Assign the iterator to the next 
   445         /// outgoing arc of the corresponding node.
   446         OutArcIt& operator++() { return *this; }
   447       };
   448 
   449       /// This iterator goes trough the incoming directed arcs of a node.
   450 
   451       /// This iterator goes trough the \e incoming arcs of a certain node
   452       /// of a graph.
   453       /// Its usage is quite simple, for example you can count the number
   454       /// of outgoing arcs of a node \c n
   455       /// in graph \c g of type \c Graph as follows.
   456       ///\code
   457       /// int count=0;
   458       /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
   459       ///\endcode
   460 
   461       class InArcIt : public Arc {
   462       public:
   463         /// Default constructor
   464 
   465         /// @warning The default constructor sets the iterator
   466         /// to an undefined value.
   467         InArcIt() { }
   468         /// Copy constructor.
   469 
   470         /// Copy constructor.
   471         ///
   472         InArcIt(const InArcIt& e) : Arc(e) { }
   473         /// Initialize the iterator to be invalid.
   474 
   475         /// Initialize the iterator to be invalid.
   476         ///
   477         InArcIt(Invalid) { }
   478         /// This constructor sets the iterator to first incoming arc.
   479     
   480         /// This constructor set the iterator to the first incoming arc of
   481         /// the node.
   482         ///@param n the node
   483         ///@param g the graph
   484         InArcIt(const Graph& g, const Node& n) { 
   485 	  ignore_unused_variable_warning(n);
   486 	  ignore_unused_variable_warning(g);
   487 	}
   488         /// Arc -> InArcIt conversion
   489 
   490         /// Sets the iterator to the value of the trivial iterator \c e.
   491         /// This feature necessitates that each time we 
   492         /// iterate the arc-set, the iteration order is the same.
   493         InArcIt(const Graph&, const Arc&) { }
   494         /// Next incoming arc
   495 
   496         /// Assign the iterator to the next inarc of the corresponding node.
   497         ///
   498         InArcIt& operator++() { return *this; }
   499       };
   500 
   501       /// \brief Read write map of the nodes to type \c T.
   502       /// 
   503       /// ReadWrite map of the nodes to type \c T.
   504       /// \sa Reference
   505       template<class T> 
   506       class NodeMap : public ReadWriteMap< Node, T >
   507       {
   508       public:
   509 
   510         ///\e
   511         NodeMap(const Graph&) { }
   512         ///\e
   513         NodeMap(const Graph&, T) { }
   514 
   515         ///Copy constructor
   516         NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
   517         ///Assignment operator
   518         template <typename CMap>
   519         NodeMap& operator=(const CMap&) { 
   520           checkConcept<ReadMap<Node, T>, CMap>();
   521           return *this; 
   522         }
   523       };
   524 
   525       /// \brief Read write map of the directed arcs to type \c T.
   526       ///
   527       /// Reference map of the directed arcs to type \c T.
   528       /// \sa Reference
   529       template<class T> 
   530       class ArcMap : public ReadWriteMap<Arc,T>
   531       {
   532       public:
   533 
   534         ///\e
   535         ArcMap(const Graph&) { }
   536         ///\e
   537         ArcMap(const Graph&, T) { }
   538         ///Copy constructor
   539         ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
   540         ///Assignment operator
   541         template <typename CMap>
   542         ArcMap& operator=(const CMap&) { 
   543           checkConcept<ReadMap<Arc, T>, CMap>();
   544           return *this; 
   545         }
   546       };
   547 
   548       /// Read write map of the edges to type \c T.
   549 
   550       /// Reference map of the arcs to type \c T.
   551       /// \sa Reference
   552       template<class T> 
   553       class EdgeMap : public ReadWriteMap<Edge,T>
   554       {
   555       public:
   556 
   557         ///\e
   558         EdgeMap(const Graph&) { }
   559         ///\e
   560         EdgeMap(const Graph&, T) { }
   561         ///Copy constructor
   562         EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {}
   563         ///Assignment operator
   564         template <typename CMap>
   565         EdgeMap& operator=(const CMap&) { 
   566           checkConcept<ReadMap<Edge, T>, CMap>();
   567           return *this; 
   568         }
   569       };
   570 
   571       /// \brief Direct the given edge.
   572       ///
   573       /// Direct the given edge. The returned arc source
   574       /// will be the given node.
   575       Arc direct(const Edge&, const Node&) const {
   576 	return INVALID;
   577       }
   578 
   579       /// \brief Direct the given edge.
   580       ///
   581       /// Direct the given edge. The returned arc
   582       /// represents the given edge and the direction comes
   583       /// from the bool parameter. The source of the edge and
   584       /// the directed arc is the same when the given bool is true.
   585       Arc direct(const Edge&, bool) const {
   586 	return INVALID;
   587       }
   588 
   589       /// \brief Returns true if the arc has default orientation.
   590       ///
   591       /// Returns whether the given directed arc is same orientation as
   592       /// the corresponding edge's default orientation.
   593       bool direction(Arc) const { return true; }
   594 
   595       /// \brief Returns the opposite directed arc.
   596       ///
   597       /// Returns the opposite directed arc.
   598       Arc oppositeArc(Arc) const { return INVALID; }
   599 
   600       /// \brief Opposite node on an arc
   601       ///
   602       /// \return the opposite of the given Node on the given Edge
   603       Node oppositeNode(Node, Edge) const { return INVALID; }
   604 
   605       /// \brief First node of the edge.
   606       ///
   607       /// \return the first node of the given Edge.
   608       ///
   609       /// Naturally edges don't have direction and thus
   610       /// don't have source and target node. But we use these two methods
   611       /// to query the two nodes of the arc. The direction of the arc
   612       /// which arises this way is called the inherent direction of the
   613       /// edge, and is used to define the "default" direction
   614       /// of the directed versions of the arcs.
   615       /// \sa direction
   616       Node u(Edge) const { return INVALID; }
   617 
   618       /// \brief Second node of the edge.
   619       Node v(Edge) const { return INVALID; }
   620 
   621       /// \brief Source node of the directed arc.
   622       Node source(Arc) const { return INVALID; }
   623 
   624       /// \brief Target node of the directed arc.
   625       Node target(Arc) const { return INVALID; }
   626 
   627       void first(Node&) const {}
   628       void next(Node&) const {}
   629 
   630       void first(Edge&) const {}
   631       void next(Edge&) const {}
   632 
   633       void first(Arc&) const {}
   634       void next(Arc&) const {}
   635 
   636       void firstOut(Arc&, Node) const {}
   637       void nextOut(Arc&) const {}
   638 
   639       void firstIn(Arc&, Node) const {}
   640       void nextIn(Arc&) const {}
   641 
   642 
   643       void firstInc(Edge &, bool &, const Node &) const {}
   644       void nextInc(Edge &, bool &) const {}
   645 
   646       /// \brief Base node of the iterator
   647       ///
   648       /// Returns the base node (the source in this case) of the iterator
   649       Node baseNode(OutArcIt e) const {
   650 	return source(e);
   651       }
   652       /// \brief Running node of the iterator
   653       ///
   654       /// Returns the running node (the target in this case) of the
   655       /// iterator
   656       Node runningNode(OutArcIt e) const {
   657 	return target(e);
   658       }
   659 
   660       /// \brief Base node of the iterator
   661       ///
   662       /// Returns the base node (the target in this case) of the iterator
   663       Node baseNode(InArcIt e) const {
   664 	return target(e);
   665       }
   666       /// \brief Running node of the iterator
   667       ///
   668       /// Returns the running node (the source in this case) of the
   669       /// iterator
   670       Node runningNode(InArcIt e) const {
   671 	return source(e);
   672       }
   673 
   674       /// \brief Base node of the iterator
   675       ///
   676       /// Returns the base node of the iterator
   677       Node baseNode(IncArcIt) const {
   678 	return INVALID;
   679       }
   680       
   681       /// \brief Running node of the iterator
   682       ///
   683       /// Returns the running node of the iterator
   684       Node runningNode(IncArcIt) const {
   685 	return INVALID;
   686       }
   687 
   688       template <typename Graph>
   689       struct Constraints {
   690 	void constraints() {
   691 	  checkConcept<IterableGraphComponent<>, Graph>();
   692 	  checkConcept<MappableGraphComponent<>, Graph>();
   693 	}
   694       };
   695 
   696     };
   697 
   698   }
   699 
   700 }
   701 
   702 #endif