lemon-0.x: src/lemon/concept/undir

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

     2  *

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

     4  * C++ optimization library

     5  *

     6  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi

     7  * Kutatocsoport (Egervary Combinatorial Optimization Research Group,

     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>

    30 namespace lemon {

    31   namespace concept {

    33     /// \addtogroup graph_concepts

    34     /// @{

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

    38     /// UndirGraph "undirected graph".

    39     template <typename UndirEdge>

    40     class UndirGraphEdge : public UndirEdge {

    41     public:

    43       /// \e

    44       UndirGraphEdge() {}

    46       /// \e

    47       UndirGraphEdge(const UndirGraphEdge&) {}

    49       /// \e

    50       UndirGraphEdge(Invalid) {}

    52       /// \brief Constructs a directed version of an undirected edge

    53       ///

    54       /// \param forward If \c true the direction of the contructed edge

    55       /// is the same as the inherent direction of the \c undir_edge; if

    56       /// \c false --- the opposite.

    57       UndirGraphEdge(UndirEdge undir_edge, bool forward) {

    58 	ignore_unused_variable_warning(undir_edge);

    59 	ignore_unused_variable_warning(forward);

    60       }

    62       /// \e

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

    65       /// \e

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

    67       /// \e

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

    70       /// \e

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

    73       template <typename Edge>

    74       struct Constraints {

    75 	void constraints() {

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

    77 	  UndirEdge ue = e;

    78 	  ue = e;

    79 	  Edge forward(ue, true);

    80 	  Edge backward(ue, false);

    82 	  ignore_unused_variable_warning(forward);

    83 	  ignore_unused_variable_warning(backward);

    84 	}

    85 	Edge e;

    86       };

    87     };

    90     struct BaseIterableUndirGraphConcept {

    92       template <typename Graph>

    93       struct Constraints {

    95 	typedef typename Graph::UndirEdge UndirEdge;

    96 	typedef typename Graph::Edge Edge;

    97 	typedef typename Graph::Node Node;

    99 	void constraints() {

   100 	  checkConcept<BaseIterableGraphComponent, Graph>();

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

   102 	  checkConcept<UndirGraphEdge<UndirEdge>, Edge>();

   104 	  graph.first(ue);

   105 	  graph.next(ue);

   107 	  const_constraints();

   108 	}

   109 	void const_constraints() {

   110 	  Node n;

   111 	  n = graph.target(ue);

   112 	  n = graph.source(ue);

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

   115 	  bool b;

   116 	  b = graph.forward(e);

   117 	  ignore_unused_variable_warning(b);

   118 	}

   120 	Graph graph;

   121 	Edge e;

   122 	Node n0;

   123 	UndirEdge ue;

   124       };

   126     };

   129     struct IterableUndirGraphConcept {

   131       template <typename Graph>

   132       struct Constraints {

   133 	void constraints() {

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

   135 	  /// Don't we really???

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

   138 	  checkConcept<IterableGraphComponent, Graph> ();

   140 	  typedef typename Graph::UndirEdge UndirEdge;

   141 	  typedef typename Graph::UndirEdgeIt UndirEdgeIt;

   142 	  typedef typename Graph::IncEdgeIt IncEdgeIt;

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

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

   146 	}

   147       };

   149     };

   151     struct MappableUndirGraphConcept {

   153       template <typename Graph>

   154       struct Constraints {

   156 	struct Dummy {

   157 	  int value;

   158 	  Dummy() : value(0) {}

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

   160 	};

   162 	void constraints() {

   163 	  checkConcept<MappableGraphComponent, Graph>();

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

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

   167 	    IntMap >();

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

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

   171 	    BoolMap >();

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

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

   175 	    DummyMap >();

   176 	}

   177       };

   179     };

   181     struct ExtendableUndirGraphConcept {

   183       template <typename Graph>

   184       struct Constraints {

   185 	void constraints() {

   186 	  node_a = graph.addNode();

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

   188 	}

   189 	typename Graph::Node node_a, node_b;

   190 	typename Graph::UndirEdge uedge;

   191 	Graph graph;

   192       };

   194     };

   196     struct ErasableUndirGraphConcept {

   198       template <typename Graph>

   199       struct Constraints {

   200 	void constraints() {

   201 	  graph.erase(n);

   202 	  graph.erase(e);

   203 	}

   204 	Graph graph;

   205 	typename Graph::Node n;

   206 	typename Graph::UndirEdge e;

   207       };

   209     };

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

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

   214     /// Graphs.

   215     ///

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

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

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

   219     /// run properly, of couse.

   220     ///

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

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

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

   224     /// a tutorial about undirected graphs.

   226     class UndirGraph {

   227     public:

   229       /// Type describing a node in the graph

   230       typedef GraphNode Node;

   232       /// Type describing an undirected edge

   233       typedef GraphItem<'u'> UndirEdge;

   235       /// Type describing an UndirEdge with direction

   236 #ifndef DOXYGEN

   237       typedef UndirGraphEdge<UndirEdge> Edge;

   238 #else

   239       typedef UndirGraphEdge Edge;

   240 #endif

   242       /// Iterator type which iterates over all nodes

   243 #ifndef DOXYGEN

   244       typedef GraphIterator<UndirGraph, Node> NodeIt;

   245 #else

   246       typedef GraphIterator NodeIt;

   247 #endif

   249       /// Iterator type which iterates over all undirected edges

   250 #ifndef DOXYGEN

   251       typedef GraphIterator<UndirGraph, UndirEdge> UndirEdgeIt;

   252 #else

   253       typedef GraphIterator UndirEdgeIt;

   254 #endif

   256       /// Iterator type which iterates over all directed edges.

   258       /// Iterator type which iterates over all edges (each undirected

   259       /// edge occurs twice with both directions.

   260 #ifndef DOXYGEN

   261       typedef GraphIterator<UndirGraph, Edge> EdgeIt;

   262 #else

   263       typedef GraphIterator EdgeIt;

   264 #endif

   267       /// Iterator of undirected edges incident to a node

   268 #ifndef DOXYGEN

   269       typedef GraphIncIterator<UndirGraph, UndirEdge, 'u'> IncEdgeIt;

   270 #else

   271       typedef GraphIncIterator IncEdgeIt;

   272 #endif

   274       /// Iterator of edges incoming to a node

   275 #ifndef DOXYGEN

   276       typedef GraphIncIterator<UndirGraph, Edge, 'i'> InEdgeIt;

   277 #else

   278       typedef GraphIncIterator InEdgeIt;

   279 #endif

   281       /// Iterator of edges outgoing from a node

   282 #ifndef DOXYGEN

   283       typedef GraphIncIterator<UndirGraph, Edge, 'o'> OutEdgeIt;

   284 #else

   285       typedef GraphIncIterator OutEdgeIt;

   286 #endif

   288       /// NodeMap template

   289 #ifdef DOXYGEN

   290       typedef GraphMap NodeMap<T>;

   291 #endif

   293       /// UndirEdgeMap template

   294 #ifdef DOXYGEN

   295       typedef GraphMap UndirEdgeMap<T>;

   296 #endif

   298       /// EdgeMap template

   299 #ifdef DOXYGEN

   300       typedef GraphMap EdgeMap<T>;

   301 #endif

   303       template <typename T>

   304       class NodeMap : public GraphMap<UndirGraph, Node, T> {

   305 	typedef GraphMap<UndirGraph, Node, T> Parent;

   306       public:

   308 	explicit NodeMap(const UndirGraph &g) : Parent(g) {}

   309 	NodeMap(const UndirGraph &g, T t) : Parent(g, t) {}

   310       };

   312       template <typename T>

   313       class UndirEdgeMap : public GraphMap<UndirGraph, UndirEdge, T> {

   314 	typedef GraphMap<UndirGraph, UndirEdge, T> Parent;

   315       public:

   317 	explicit UndirEdgeMap(const UndirGraph &g) : Parent(g) {}

   318 	UndirEdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}

   319       };

   321       template <typename T>

   322       class EdgeMap : public GraphMap<UndirGraph, Edge, T> {

   323 	typedef GraphMap<UndirGraph, Edge, T> Parent;

   324       public:

   326 	explicit EdgeMap(const UndirGraph &g) : Parent(g) {}

   327 	EdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}

   328       };

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

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

   333       /// the corresponding undirected edge.

   334       ///

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

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

   338       /// Opposite node on an edge

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

   341       ///

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

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

   345       /// First node of the undirected edge.

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

   348       ///

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

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

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

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

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

   354       /// of the directed versions of the edges.

   355       /// \sa forward

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

   358       /// Second node of the undirected edge.

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

   361       /// Source node of the directed edge.

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

   364       /// Target node of the directed edge.

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

   367       /// First node of the graph

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

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

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

   372       void first(Node&) const {}

   373       /// Next node of the graph

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

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

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

   378       void next(Node&) const {}

   380       /// First undirected edge of the graph

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

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

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

   385       void first(UndirEdge&) const {}

   386       /// Next undirected edge of the graph

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

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

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

   391       void next(UndirEdge&) const {}

   393       /// First directed edge of the graph

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

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

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

   398       void first(Edge&) const {}

   399       /// Next directed edge of the graph

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

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

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

   404       void next(Edge&) const {}

   406       /// First outgoing edge from a given node

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

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

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

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

   412       /// Next outgoing edge to a node

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

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

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

   417       void nextOut(Edge&) const {}

   419       /// First incoming edge to a given node

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

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

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

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

   425       /// Next incoming edge to a node

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

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

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

   430       void nextIn(Edge&) const {}

   433       template <typename Graph>

   434       struct Constraints {

   435 	void constraints() {

   436 	  checkConcept<BaseIterableUndirGraphConcept, Graph>();

   437 	  checkConcept<IterableUndirGraphConcept, Graph>();

   438 	  checkConcept<MappableUndirGraphConcept, Graph>();

   439 	}

   440       };

   442     };

   444     class ExtendableUndirGraph : public UndirGraph {

   445     public:

   447       template <typename Graph>

   448       struct Constraints {

   449 	void constraints() {

   450 	  checkConcept<BaseIterableUndirGraphConcept, Graph>();

   451 	  checkConcept<IterableUndirGraphConcept, Graph>();

   452 	  checkConcept<MappableUndirGraphConcept, Graph>();

   454 	  checkConcept<UndirGraph, Graph>();

   455 	  checkConcept<ExtendableUndirGraphConcept, Graph>();

   456 	  checkConcept<ClearableGraphComponent, Graph>();

   457 	}

   458       };

   460     };

   462     class ErasableUndirGraph : public ExtendableUndirGraph {

   463     public:

   465       template <typename Graph>

   466       struct Constraints {

   467 	void constraints() {

   468 	  checkConcept<ExtendableUndirGraph, Graph>();

   469 	  checkConcept<ErasableUndirGraphConcept, Graph>();

   470 	}

   471       };

   473     };

   475     /// @}

   477   }

   479 }

   481 #endif

author	alpar
	Sun, 16 Jan 2005 22:27:34 +0000
changeset 1082	e9eae612f01c
parent 1022	567f392d1d2e
child 1158	29961fa390a3
permissions	-rw-r--r--