lemon-0.x: lemon/concept/undir_graph.h@09feafe81053

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

     2  *

     3  * lemon/concept/undir_graph_component.h - Part of LEMON, a generic

     4  * C++ optimization library

     5  *

     6  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi

     7  * Kutatocsoport (Egervary Research Group on Combinatorial Optimization,

     8  * EGRES).

     9  *

    10  * Permission to use, modify and distribute this software is granted

    11  * provided that this copyright notice appears in all copies. For

    12  * precise terms see the accompanying LICENSE file.

    13  *

    14  * This software is provided "AS IS" with no warranty of any kind,

    15  * express or implied, and with no claim as to its suitability for any

    16  * purpose.

    17  *

    18  */

    20 ///\ingroup graph_concepts

    21 ///\file

    22 ///\brief Undirected graphs and components of.

    25 #ifndef LEMON_CONCEPT_UNDIR_GRAPH_H

    26 #define LEMON_CONCEPT_UNDIR_GRAPH_H

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

    29 #include <lemon/concept/graph.h>

    30 #include <lemon/utility.h>

    32 namespace lemon {

    33   namespace concept {

    35     /// Skeleton class which describes an edge with direction in \ref

    36     /// UndirGraph "undirected graph".

    37     template <typename UndirGraph>

    38     class UndirGraphEdge : public UndirGraph::UndirEdge {

    39       typedef typename UndirGraph::UndirEdge UndirEdge;

    40       typedef typename UndirGraph::Node Node;

    41     public:

    43       /// \e

    44       UndirGraphEdge() {}

    46       /// \e

    47       UndirGraphEdge(const UndirGraphEdge& e) : UndirGraph::UndirEdge(e) {}

    49       /// \e

    50       UndirGraphEdge(Invalid) {}

    52       /// \brief Directed edge from undirected edge and a source node.

    53       ///

    54       /// Constructs a directed edge from undirected edge and a source node.

    55       ///

    56       /// \note You have to specify the graph for this constructor.

    57       UndirGraphEdge(const UndirGraph &g,

    58 		     UndirEdge undir_edge, Node n) {

    59 	ignore_unused_variable_warning(undir_edge);

    60 	ignore_unused_variable_warning(g);

    61 	ignore_unused_variable_warning(n);

    62       }

    64       /// \e

    65       UndirGraphEdge& operator=(UndirGraphEdge) { return *this; }

    67       /// \e

    68       bool operator==(UndirGraphEdge) const { return true; }

    69       /// \e

    70       bool operator!=(UndirGraphEdge) const { return false; }

    72       /// \e

    73       bool operator<(UndirGraphEdge) const { return false; }

    75       template <typename Edge>

    76       struct Constraints {

    77 	void constraints() {

    78 	  const_constraints();

    79 	}

    80 	void const_constraints() const {

    81 	  /// \bug This should be is_base_and_derived ...

    82 	  UndirEdge ue = e;

    83 	  ue = e;

    85 	  Edge e_with_source(graph,ue,n);

    86 	  ignore_unused_variable_warning(e_with_source);

    87 	}

    88 	Edge e;

    89 	UndirEdge ue;

    90 	UndirGraph graph;

    91 	Node n;

    92       };

    93     };

    96     struct BaseIterableUndirGraphConcept {

    98       template <typename Graph>

    99       struct Constraints {

   101 	typedef typename Graph::UndirEdge UndirEdge;

   102 	typedef typename Graph::Edge Edge;

   103 	typedef typename Graph::Node Node;

   105 	void constraints() {

   106 	  checkConcept<BaseIterableGraphComponent, Graph>();

   107 	  checkConcept<GraphItem<>, UndirEdge>();

   108 	  //checkConcept<UndirGraphEdge<Graph>, Edge>();

   110 	  graph.first(ue);

   111 	  graph.next(ue);

   113 	  const_constraints();

   114 	}

   115 	void const_constraints() {

   116 	  Node n;

   117 	  n = graph.target(ue);

   118 	  n = graph.source(ue);

   119 	  n = graph.oppositeNode(n0, ue);

   121 	  bool b;

   122 	  b = graph.forward(e);

   123 	  ignore_unused_variable_warning(b);

   124 	}

   126 	Graph graph;

   127 	Edge e;

   128 	Node n0;

   129 	UndirEdge ue;

   130       };

   132     };

   135     struct IterableUndirGraphConcept {

   137       template <typename Graph>

   138       struct Constraints {

   139 	void constraints() {

   140 	  /// \todo we don't need the iterable component to be base iterable

   141 	  /// Don't we really???

   142 	  //checkConcept< BaseIterableUndirGraphConcept, Graph > ();

   144 	  checkConcept<IterableGraphComponent, Graph> ();

   146 	  typedef typename Graph::UndirEdge UndirEdge;

   147 	  typedef typename Graph::UndirEdgeIt UndirEdgeIt;

   148 	  typedef typename Graph::IncEdgeIt IncEdgeIt;

   150 	  checkConcept<GraphIterator<Graph, UndirEdge>, UndirEdgeIt>();

   151 	  checkConcept<GraphIncIterator<Graph, UndirEdge>, IncEdgeIt>();

   152 	}

   153       };

   155     };

   157     struct MappableUndirGraphConcept {

   159       template <typename Graph>

   160       struct Constraints {

   162 	struct Dummy {

   163 	  int value;

   164 	  Dummy() : value(0) {}

   165 	  Dummy(int _v) : value(_v) {}

   166 	};

   168 	void constraints() {

   169 	  checkConcept<MappableGraphComponent, Graph>();

   171 	  typedef typename Graph::template UndirEdgeMap<int> IntMap;

   172 	  checkConcept<GraphMap<Graph, typename Graph::UndirEdge, int>,

   173 	    IntMap >();

   175 	  typedef typename Graph::template UndirEdgeMap<bool> BoolMap;

   176 	  checkConcept<GraphMap<Graph, typename Graph::UndirEdge, bool>,

   177 	    BoolMap >();

   179 	  typedef typename Graph::template UndirEdgeMap<Dummy> DummyMap;

   180 	  checkConcept<GraphMap<Graph, typename Graph::UndirEdge, Dummy>,

   181 	    DummyMap >();

   182 	}

   183       };

   185     };

   187     struct ExtendableUndirGraphConcept {

   189       template <typename Graph>

   190       struct Constraints {

   191 	void constraints() {

   192 	  node_a = graph.addNode();

   193 	  uedge = graph.addEdge(node_a, node_b);

   194 	}

   195 	typename Graph::Node node_a, node_b;

   196 	typename Graph::UndirEdge uedge;

   197 	Graph graph;

   198       };

   200     };

   202     struct ErasableUndirGraphConcept {

   204       template <typename Graph>

   205       struct Constraints {

   206 	void constraints() {

   207 	  graph.erase(n);

   208 	  graph.erase(e);

   209 	}

   210 	Graph graph;

   211 	typename Graph::Node n;

   212 	typename Graph::UndirEdge e;

   213       };

   215     };

   217     /// \addtogroup graph_concepts

   218     /// @{

   221     /// Class describing the concept of Undirected Graphs.

   223     /// This class describes the common interface of all Undirected

   224     /// Graphs.

   225     ///

   226     /// As all concept describing classes it provides only interface

   227     /// without any sensible implementation. So any algorithm for

   228     /// undirected graph should compile with this class, but it will not

   229     /// run properly, of couse.

   230     ///

   231     /// In LEMON undirected graphs also fulfill the concept of directed

   232     /// graphs (\ref lemon::concept::Graph "Graph Concept"). For

   233     /// explanation of this and more see also the page \ref undir_graphs,

   234     /// a tutorial about undirected graphs.

   236     class UndirGraph : public StaticGraph {

   237     public:

   238       ///\e

   240       ///\todo undocumented

   241       ///

   242       typedef True UndirTag;

   244       /// The base type of the undirected edge iterators.

   246       /// The base type of the undirected edge iterators.

   247       ///

   248       class UndirEdge {

   249       public:

   250         /// Default constructor

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

   253         /// to an undefined value.

   254         UndirEdge() { }

   255         /// Copy constructor.

   257         /// Copy constructor.

   258         ///

   259         UndirEdge(const UndirEdge&) { }

   260         /// Edge -> UndirEdge conversion

   262         /// Edge -> UndirEdge conversion

   263         ///

   264         UndirEdge(const Edge&) { }

   265         /// Initialize the iterator to be invalid.

   267         /// Initialize the iterator to be invalid.

   268         ///

   269         UndirEdge(Invalid) { }

   270         /// Equality operator

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

   273         /// same object or both are invalid.

   274         bool operator==(UndirEdge) const { return true; }

   275         /// Inequality operator

   277         /// \sa operator==(UndirEdge n)

   278         ///

   279         bool operator!=(UndirEdge) const { return true; }

   281 	///\e

   283 	///\todo Do we need this?

   284 	///

   285 	bool operator<(const UndirEdge &that) const { return true; }

   286       };

   288       /// This iterator goes through each undirected edge.

   290       /// This iterator goes through each undirected edge of a graph.

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

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

   293       /// \code

   294       /// int count=0;

   295       /// for(Graph::UndirEdgeIt e(g); e!=INVALID; ++e) ++count;

   296       /// \endcode

   297       class UndirEdgeIt : public UndirEdge {

   298       public:

   299         /// Default constructor

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

   302         /// to an undefined value.

   303         UndirEdgeIt() { }

   304         /// Copy constructor.

   306         /// Copy constructor.

   307         ///

   308         UndirEdgeIt(const UndirEdgeIt& e) : UndirEdge(e) { }

   309         /// Initialize the iterator to be invalid.

   311         /// Initialize the iterator to be invalid.

   312         ///

   313         UndirEdgeIt(Invalid) { }

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

   316         /// This constructor sets the iterator to the first edge of \c g.

   317         ///@param g the graph

   318         UndirEdgeIt(const UndirGraph&) { }

   319         /// UndirEdge -> UndirEdgeIt conversion

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

   322         /// This feature necessitates that each time we

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

   324         UndirEdgeIt(const UndirGraph&, const UndirEdge&) { }

   325         ///Next edge

   327         /// Assign the iterator to the next edge.

   328         UndirEdgeIt& operator++() { return *this; }

   329       };

   331       /// This iterator goes trough the incident undirected edges of a node.

   333       /// This iterator goes trough the incident undirected edges

   334       /// of a certain node

   335       /// of a graph.

   336       /// Its usage is quite simple, for example you can compute the

   337       /// degree (i.e. count the number

   338       /// of incident edges of a node \c n

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

   340       /// \code

   341       /// int count=0;

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

   343       /// \endcode

   344       class IncEdgeIt : public UndirEdge {

   345       public:

   346         /// Default constructor

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

   349         /// to an undefined value.

   350         IncEdgeIt() { }

   351         /// Copy constructor.

   353         /// Copy constructor.

   354         ///

   355         IncEdgeIt(const IncEdgeIt& e) : UndirEdge(e) { }

   356         /// Initialize the iterator to be invalid.

   358         /// Initialize the iterator to be invalid.

   359         ///

   360         IncEdgeIt(Invalid) { }

   361         /// This constructor sets the iterator to first incident edge.

   363         /// This constructor set the iterator to the first incident edge of

   364         /// the node.

   365         ///@param n the node

   366         ///@param g the graph

   367         IncEdgeIt(const UndirGraph&, const Node&) { }

   368         /// UndirEdge -> IncEdgeIt conversion

   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         IncEdgeIt(const UndirGraph&, const UndirEdge&) { }

   374         /// Next incident edge

   376         /// Assign the iterator to the next incident edge

   377 	/// of the corresponding node.

   378         IncEdgeIt& operator++() { return *this; }

   379       };

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

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

   384       /// \sa Reference

   385       /// \warning Making maps that can handle bool type (UndirEdgeMap<bool>)

   386       /// needs some extra attention!

   387       template<class T>

   388       class UndirEdgeMap : public ReadWriteMap<UndirEdge,T>

   389       {

   390       public:

   392         ///\e

   393         UndirEdgeMap(const UndirGraph&) { }

   394         ///\e

   395         UndirEdgeMap(const UndirGraph&, T) { }

   396         ///Copy constructor

   397         UndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap<UndirEdge,T>(em) { }

   398         ///Assignment operator

   399         UndirEdgeMap &operator=(const UndirEdgeMap&) { return *this; }

   400         // \todo fix this concept

   401       };

   403       /// Is the Edge oriented "forward"?

   405       /// Returns whether the given directed edge is same orientation as

   406       /// the corresponding undirected edge.

   407       ///

   408       /// \todo "What does the direction of an undirected edge mean?"

   409       bool forward(Edge) const { return true; }

   411       /// Opposite node on an edge

   413       /// \return the opposite of the given Node on the given Edge

   414       ///

   415       /// \todo What should we do if given Node and Edge are not incident?

   416       Node oppositeNode(Node, UndirEdge) const { return INVALID; }

   418       /// First node of the undirected edge.

   420       /// \return the first node of the given UndirEdge.

   421       ///

   422       /// Naturally undirectected edges don't have direction and thus

   423       /// don't have source and target node. But we use these two methods

   424       /// to query the two endnodes of the edge. The direction of the edge

   425       /// which arises this way is called the inherent direction of the

   426       /// undirected edge, and is used to define the "forward" direction

   427       /// of the directed versions of the edges.

   428       /// \sa forward

   429       Node source(UndirEdge) const { return INVALID; }

   431       /// Second node of the undirected edge.

   432       Node target(UndirEdge) const { return INVALID; }

   434       /// Source node of the directed edge.

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

   437       /// Target node of the directed edge.

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

   440       /// First node of the graph

   442       /// \note This method is part of so called \ref

   443       /// developpers_interface "Developpers' interface", so it shouldn't

   444       /// be used in an end-user program.

   445       void first(Node&) const {}

   446       /// Next node of the graph

   448       /// \note This method is part of so called \ref

   449       /// developpers_interface "Developpers' interface", so it shouldn't

   450       /// be used in an end-user program.

   451       void next(Node&) const {}

   453       /// First undirected edge of the graph

   455       /// \note This method is part of so called \ref

   456       /// developpers_interface "Developpers' interface", so it shouldn't

   457       /// be used in an end-user program.

   458       void first(UndirEdge&) const {}

   459       /// Next undirected edge of the graph

   461       /// \note This method is part of so called \ref

   462       /// developpers_interface "Developpers' interface", so it shouldn't

   463       /// be used in an end-user program.

   464       void next(UndirEdge&) const {}

   466       /// First directed edge of the graph

   468       /// \note This method is part of so called \ref

   469       /// developpers_interface "Developpers' interface", so it shouldn't

   470       /// be used in an end-user program.

   471       void first(Edge&) const {}

   472       /// Next directed edge of the graph

   474       /// \note This method is part of so called \ref

   475       /// developpers_interface "Developpers' interface", so it shouldn't

   476       /// be used in an end-user program.

   477       void next(Edge&) const {}

   479       /// First outgoing edge from a given node

   481       /// \note This method is part of so called \ref

   482       /// developpers_interface "Developpers' interface", so it shouldn't

   483       /// be used in an end-user program.

   484       void firstOut(Edge&, Node) const {}

   485       /// Next outgoing edge to a node

   487       /// \note This method is part of so called \ref

   488       /// developpers_interface "Developpers' interface", so it shouldn't

   489       /// be used in an end-user program.

   490       void nextOut(Edge&) const {}

   492       /// First incoming edge to a given node

   494       /// \note This method is part of so called \ref

   495       /// developpers_interface "Developpers' interface", so it shouldn't

   496       /// be used in an end-user program.

   497       void firstIn(Edge&, Node) const {}

   498       /// Next incoming edge to a node

   500       /// \note This method is part of so called \ref

   501       /// developpers_interface "Developpers' interface", so it shouldn't

   502       /// be used in an end-user program.

   503       void nextIn(Edge&) const {}

   506       /// Base node of the iterator

   507       ///

   508       /// Returns the base node (the source in this case) of the iterator

   509       Node baseNode(OutEdgeIt e) const {

   510 	return source(e);

   511       }

   512       /// Running node of the iterator

   513       ///

   514       /// Returns the running node (the target in this case) of the

   515       /// iterator

   516       Node runningNode(OutEdgeIt e) const {

   517 	return target(e);

   518       }

   520       /// Base node of the iterator

   521       ///

   522       /// Returns the base node (the target in this case) of the iterator

   523       Node baseNode(InEdgeIt e) const {

   524 	return target(e);

   525       }

   526       /// Running node of the iterator

   527       ///

   528       /// Returns the running node (the source in this case) of the

   529       /// iterator

   530       Node runningNode(InEdgeIt e) const {

   531 	return source(e);

   532       }

   534       /// Base node of the iterator

   535       ///

   536       /// Returns the base node of the iterator

   537       Node baseNode(IncEdgeIt) const {

   538 	return INVALID;

   539       }

   540       /// Running node of the iterator

   541       ///

   542       /// Returns the running node of the iterator

   543       Node runningNode(IncEdgeIt) const {

   544 	return INVALID;

   545       }

   548       template <typename Graph>

   549       struct Constraints {

   550 	void constraints() {

   551 	  checkConcept<BaseIterableUndirGraphConcept, Graph>();

   552 	  checkConcept<IterableUndirGraphConcept, Graph>();

   553 	  checkConcept<MappableUndirGraphConcept, Graph>();

   554 	}

   555       };

   557     };

   559     class ExtendableUndirGraph : public UndirGraph {

   560     public:

   562       template <typename Graph>

   563       struct Constraints {

   564 	void constraints() {

   565 	  checkConcept<BaseIterableUndirGraphConcept, Graph>();

   566 	  checkConcept<IterableUndirGraphConcept, Graph>();

   567 	  checkConcept<MappableUndirGraphConcept, Graph>();

   569 	  checkConcept<UndirGraph, Graph>();

   570 	  checkConcept<ExtendableUndirGraphConcept, Graph>();

   571 	  checkConcept<ClearableGraphComponent, Graph>();

   572 	}

   573       };

   575     };

   577     class ErasableUndirGraph : public ExtendableUndirGraph {

   578     public:

   580       template <typename Graph>

   581       struct Constraints {

   582 	void constraints() {

   583 	  checkConcept<ExtendableUndirGraph, Graph>();

   584 	  checkConcept<ErasableUndirGraphConcept, Graph>();

   585 	}

   586       };

   588     };

   590     /// @}

   592   }

   594 }

   596 #endif

author	alpar
	Thu, 11 Aug 2005 13:07:54 +0000
changeset 1620	09feafe81053
parent 1448	0274acee0e35
child 1624	61cc647dac99
permissions	-rw-r--r--