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) 2005 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 UndirGraph>

    40     class UndirGraphEdge : public UndirGraph::UndirEdge {

    41       typedef typename UndirGraph::UndirEdge UndirEdge;

    42       typedef typename UndirGraph::Node Node;

    43     public:

    45       /// \e

    46       UndirGraphEdge() {}

    48       /// \e

    49       UndirGraphEdge(const UndirGraphEdge&) {}

    51       /// \e

    52       UndirGraphEdge(Invalid) {}

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

    55       ///

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

    57       ///

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

    59       UndirGraphEdge(const UndirGraph &g,

    60 		     UndirEdge undir_edge, Node n) {

    61 	ignore_unused_variable_warning(undir_edge);

    62 	ignore_unused_variable_warning(g);

    63 	ignore_unused_variable_warning(n);

    64       }

    66       /// \e

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

    69       /// \e

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

    71       /// \e

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

    74       /// \e

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

    77       template <typename Edge>

    78       struct Constraints {

    79 	void constraints() {

    80 	  const_constraints();

    81 	}

    82 	void const_constraints() const {

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

    84 	  UndirEdge ue = e;

    85 	  ue = e;

    87 	  Edge e_with_source(graph,ue,n);

    88 	  ignore_unused_variable_warning(e_with_source);

    89 	}

    90 	Edge e;

    91 	UndirEdge ue;

    92 	UndirGraph graph;

    93 	Node n;

    94       };

    95     };

    98     struct BaseIterableUndirGraphConcept {

   100       template <typename Graph>

   101       struct Constraints {

   103 	typedef typename Graph::UndirEdge UndirEdge;

   104 	typedef typename Graph::Edge Edge;

   105 	typedef typename Graph::Node Node;

   107 	void constraints() {

   108 	  checkConcept<BaseIterableGraphComponent, Graph>();

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

   110 	  checkConcept<UndirGraphEdge<Graph>, Edge>();

   112 	  graph.first(ue);

   113 	  graph.next(ue);

   115 	  const_constraints();

   116 	}

   117 	void const_constraints() {

   118 	  Node n;

   119 	  n = graph.target(ue);

   120 	  n = graph.source(ue);

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

   123 	  bool b;

   124 	  b = graph.forward(e);

   125 	  ignore_unused_variable_warning(b);

   126 	}

   128 	Graph graph;

   129 	Edge e;

   130 	Node n0;

   131 	UndirEdge ue;

   132       };

   134     };

   137     struct IterableUndirGraphConcept {

   139       template <typename Graph>

   140       struct Constraints {

   141 	void constraints() {

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

   143 	  /// Don't we really???

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

   146 	  checkConcept<IterableGraphComponent, Graph> ();

   148 	  typedef typename Graph::UndirEdge UndirEdge;

   149 	  typedef typename Graph::UndirEdgeIt UndirEdgeIt;

   150 	  typedef typename Graph::IncEdgeIt IncEdgeIt;

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

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

   154 	}

   155       };

   157     };

   159     struct MappableUndirGraphConcept {

   161       template <typename Graph>

   162       struct Constraints {

   164 	struct Dummy {

   165 	  int value;

   166 	  Dummy() : value(0) {}

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

   168 	};

   170 	void constraints() {

   171 	  checkConcept<MappableGraphComponent, Graph>();

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

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

   175 	    IntMap >();

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

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

   179 	    BoolMap >();

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

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

   183 	    DummyMap >();

   184 	}

   185       };

   187     };

   189     struct ExtendableUndirGraphConcept {

   191       template <typename Graph>

   192       struct Constraints {

   193 	void constraints() {

   194 	  node_a = graph.addNode();

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

   196 	}

   197 	typename Graph::Node node_a, node_b;

   198 	typename Graph::UndirEdge uedge;

   199 	Graph graph;

   200       };

   202     };

   204     struct ErasableUndirGraphConcept {

   206       template <typename Graph>

   207       struct Constraints {

   208 	void constraints() {

   209 	  graph.erase(n);

   210 	  graph.erase(e);

   211 	}

   212 	Graph graph;

   213 	typename Graph::Node n;

   214 	typename Graph::UndirEdge e;

   215       };

   217     };

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

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

   222     /// Graphs.

   223     ///

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

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

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

   227     /// run properly, of couse.

   228     ///

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

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

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

   232     /// a tutorial about undirected graphs.

   234     class UndirGraph {

   235     public:

   237       /// Type describing a node in the graph

   238       typedef GraphNode Node;

   240       /// Type describing an undirected edge

   241       typedef GraphItem<'u'> UndirEdge;

   243       /// Type describing an UndirEdge with direction

   244 #ifndef DOXYGEN

   245       typedef UndirGraphEdge<UndirGraph> Edge;

   246 #else

   247       typedef UndirGraphEdge Edge;

   248 #endif

   250       /// Iterator type which iterates over all nodes

   251 #ifndef DOXYGEN

   252       typedef GraphIterator<UndirGraph, Node> NodeIt;

   253 #else

   254       typedef GraphIterator NodeIt;

   255 #endif

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

   258 #ifndef DOXYGEN

   259       typedef GraphIterator<UndirGraph, UndirEdge> UndirEdgeIt;

   260 #else

   261       typedef GraphIterator UndirEdgeIt;

   262 #endif

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

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

   267       /// edge occurs twice with both directions.

   268 #ifndef DOXYGEN

   269       typedef GraphIterator<UndirGraph, Edge> EdgeIt;

   270 #else

   271       typedef GraphIterator EdgeIt;

   272 #endif

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

   276 #ifndef DOXYGEN

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

   278 #else

   279       typedef GraphIncIterator IncEdgeIt;

   280 #endif

   282       /// Iterator of edges incoming to a node

   283 #ifndef DOXYGEN

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

   285 #else

   286       typedef GraphIncIterator InEdgeIt;

   287 #endif

   289       /// Iterator of edges outgoing from a node

   290 #ifndef DOXYGEN

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

   292 #else

   293       typedef GraphIncIterator OutEdgeIt;

   294 #endif

   296       /// NodeMap template

   297 #ifdef DOXYGEN

   298       typedef GraphMap NodeMap<T>;

   299 #endif

   301       /// UndirEdgeMap template

   302 #ifdef DOXYGEN

   303       typedef GraphMap UndirEdgeMap<T>;

   304 #endif

   306       /// EdgeMap template

   307 #ifdef DOXYGEN

   308       typedef GraphMap EdgeMap<T>;

   309 #endif

   311       template <typename T>

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

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

   314       public:

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

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

   318       };

   320       template <typename T>

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

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

   323       public:

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

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

   327       };

   329       template <typename T>

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

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

   332       public:

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

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

   336       };

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

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

   341       /// the corresponding undirected edge.

   342       ///

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

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

   346       /// Opposite node on an edge

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

   349       ///

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

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

   353       /// First node of the undirected edge.

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

   356       ///

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

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

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

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

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

   362       /// of the directed versions of the edges.

   363       /// \sa forward

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

   366       /// Second node of the undirected edge.

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

   369       /// Source node of the directed edge.

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

   372       /// Target node of the directed edge.

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

   375       /// First node of the graph

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

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

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

   380       void first(Node&) const {}

   381       /// Next node of the graph

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

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

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

   386       void next(Node&) const {}

   388       /// First undirected edge of the graph

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

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

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

   393       void first(UndirEdge&) const {}

   394       /// Next undirected edge of the graph

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

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

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

   399       void next(UndirEdge&) const {}

   401       /// First directed edge of the graph

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

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

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

   406       void first(Edge&) const {}

   407       /// Next directed edge of the graph

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

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

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

   412       void next(Edge&) const {}

   414       /// First outgoing edge from a given node

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

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

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

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

   420       /// Next outgoing edge to a node

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

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

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

   425       void nextOut(Edge&) const {}

   427       /// First incoming edge to a given node

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

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

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

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

   433       /// Next incoming edge to a node

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

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

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

   438       void nextIn(Edge&) const {}

   441       /// Base node of the iterator

   442       ///

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

   444       Node baseNode(OutEdgeIt e) const {

   445 	return source(e);

   446       }

   447       /// Running node of the iterator

   448       ///

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

   450       /// iterator

   451       Node runningNode(OutEdgeIt e) const {

   452 	return target(e);

   453       }

   455       /// Base node of the iterator

   456       ///

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

   458       Node baseNode(InEdgeIt e) const {

   459 	return target(e);

   460       }

   461       /// Running node of the iterator

   462       ///

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

   464       /// iterator

   465       Node runningNode(InEdgeIt e) const {

   466 	return source(e);

   467       }

   469       /// Base node of the iterator

   470       ///

   471       /// Returns the base node of the iterator

   472       Node baseNode(IncEdgeIt e) const {

   473 	return INVALID;

   474       }

   475       /// Running node of the iterator

   476       ///

   477       /// Returns the running node of the iterator

   478       Node runningNode(IncEdgeIt e) const {

   479 	return INVALID;

   480       }

   483       template <typename Graph>

   484       struct Constraints {

   485 	void constraints() {

   486 	  checkConcept<BaseIterableUndirGraphConcept, Graph>();

   487 	  checkConcept<IterableUndirGraphConcept, Graph>();

   488 	  checkConcept<MappableUndirGraphConcept, Graph>();

   489 	}

   490       };

   492     };

   494     class ExtendableUndirGraph : public UndirGraph {

   495     public:

   497       template <typename Graph>

   498       struct Constraints {

   499 	void constraints() {

   500 	  checkConcept<BaseIterableUndirGraphConcept, Graph>();

   501 	  checkConcept<IterableUndirGraphConcept, Graph>();

   502 	  checkConcept<MappableUndirGraphConcept, Graph>();

   504 	  checkConcept<UndirGraph, Graph>();

   505 	  checkConcept<ExtendableUndirGraphConcept, Graph>();

   506 	  checkConcept<ClearableGraphComponent, Graph>();

   507 	}

   508       };

   510     };

   512     class ErasableUndirGraph : public ExtendableUndirGraph {

   513     public:

   515       template <typename Graph>

   516       struct Constraints {

   517 	void constraints() {

   518 	  checkConcept<ExtendableUndirGraph, Graph>();

   519 	  checkConcept<ErasableUndirGraphConcept, Graph>();

   520 	}

   521       };

   523     };

   525     /// @}

   527   }

   529 }

   531 #endif

author	athos
	Tue, 22 Mar 2005 11:45:47 +0000
changeset 1240	88a2ab6bfc4a
parent 1158	29961fa390a3
child 1359	1581f961cfaa
permissions	-rw-r--r--