lemon-0.x: lemon/concept/undir_graph.h@0d9f1a71be27

     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/utility.h>

    31 namespace lemon {

    32   namespace concept {

    34     /// \addtogroup graph_concepts

    35     /// @{

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

    39     /// UndirGraph "undirected graph".

    40     template <typename UndirGraph>

    41     class UndirGraphEdge : public UndirGraph::UndirEdge {

    42       typedef typename UndirGraph::UndirEdge UndirEdge;

    43       typedef typename UndirGraph::Node Node;

    44     public:

    46       /// \e

    47       UndirGraphEdge() {}

    49       /// \e

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

    52       /// \e

    53       UndirGraphEdge(Invalid) {}

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

    56       ///

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

    58       ///

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

    60       UndirGraphEdge(const UndirGraph &g,

    61 		     UndirEdge undir_edge, Node n) {

    62 	ignore_unused_variable_warning(undir_edge);

    63 	ignore_unused_variable_warning(g);

    64 	ignore_unused_variable_warning(n);

    65       }

    67       /// \e

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

    70       /// \e

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

    72       /// \e

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

    75       /// \e

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

    78       template <typename Edge>

    79       struct Constraints {

    80 	void constraints() {

    81 	  const_constraints();

    82 	}

    83 	void const_constraints() const {

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

    85 	  UndirEdge ue = e;

    86 	  ue = e;

    88 	  Edge e_with_source(graph,ue,n);

    89 	  ignore_unused_variable_warning(e_with_source);

    90 	}

    91 	Edge e;

    92 	UndirEdge ue;

    93 	UndirGraph graph;

    94 	Node n;

    95       };

    96     };

    99     struct BaseIterableUndirGraphConcept {

   101       template <typename Graph>

   102       struct Constraints {

   104 	typedef typename Graph::UndirEdge UndirEdge;

   105 	typedef typename Graph::Edge Edge;

   106 	typedef typename Graph::Node Node;

   108 	void constraints() {

   109 	  checkConcept<BaseIterableGraphComponent, Graph>();

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

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

   113 	  graph.first(ue);

   114 	  graph.next(ue);

   116 	  const_constraints();

   117 	}

   118 	void const_constraints() {

   119 	  Node n;

   120 	  n = graph.target(ue);

   121 	  n = graph.source(ue);

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

   124 	  bool b;

   125 	  b = graph.forward(e);

   126 	  ignore_unused_variable_warning(b);

   127 	}

   129 	Graph graph;

   130 	Edge e;

   131 	Node n0;

   132 	UndirEdge ue;

   133       };

   135     };

   138     struct IterableUndirGraphConcept {

   140       template <typename Graph>

   141       struct Constraints {

   142 	void constraints() {

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

   144 	  /// Don't we really???

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

   147 	  checkConcept<IterableGraphComponent, Graph> ();

   149 	  typedef typename Graph::UndirEdge UndirEdge;

   150 	  typedef typename Graph::UndirEdgeIt UndirEdgeIt;

   151 	  typedef typename Graph::IncEdgeIt IncEdgeIt;

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

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

   155 	}

   156       };

   158     };

   160     struct MappableUndirGraphConcept {

   162       template <typename Graph>

   163       struct Constraints {

   165 	struct Dummy {

   166 	  int value;

   167 	  Dummy() : value(0) {}

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

   169 	};

   171 	void constraints() {

   172 	  checkConcept<MappableGraphComponent, Graph>();

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

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

   176 	    IntMap >();

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

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

   180 	    BoolMap >();

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

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

   184 	    DummyMap >();

   185 	}

   186       };

   188     };

   190     struct ExtendableUndirGraphConcept {

   192       template <typename Graph>

   193       struct Constraints {

   194 	void constraints() {

   195 	  node_a = graph.addNode();

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

   197 	}

   198 	typename Graph::Node node_a, node_b;

   199 	typename Graph::UndirEdge uedge;

   200 	Graph graph;

   201       };

   203     };

   205     struct ErasableUndirGraphConcept {

   207       template <typename Graph>

   208       struct Constraints {

   209 	void constraints() {

   210 	  graph.erase(n);

   211 	  graph.erase(e);

   212 	}

   213 	Graph graph;

   214 	typename Graph::Node n;

   215 	typename Graph::UndirEdge e;

   216       };

   218     };

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

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

   223     /// Graphs.

   224     ///

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

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

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

   228     /// run properly, of couse.

   229     ///

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

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

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

   233     /// a tutorial about undirected graphs.

   235     class UndirGraph {

   236     public:

   237       ///\e

   239       ///\todo undocumented

   240       ///

   241       typedef True UndirTag;

   243       /// Type describing a node in the graph

   244       typedef GraphNode Node;

   246       /// Type describing an undirected edge

   247       typedef GraphItem<'u'> UndirEdge;

   249       /// Type describing an UndirEdge with direction

   250 #ifndef DOXYGEN

   251       typedef UndirGraphEdge<UndirGraph> Edge;

   252 #else

   253       typedef UndirGraphEdge Edge;

   254 #endif

   256       /// Iterator type which iterates over all nodes

   257 #ifndef DOXYGEN

   258       typedef GraphIterator<UndirGraph, Node> NodeIt;

   259 #else

   260       typedef GraphIterator NodeIt;

   261 #endif

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

   264 #ifndef DOXYGEN

   265       typedef GraphIterator<UndirGraph, UndirEdge> UndirEdgeIt;

   266 #else

   267       typedef GraphIterator UndirEdgeIt;

   268 #endif

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

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

   273       /// edge occurs twice with both directions.

   274 #ifndef DOXYGEN

   275       typedef GraphIterator<UndirGraph, Edge> EdgeIt;

   276 #else

   277       typedef GraphIterator EdgeIt;

   278 #endif

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

   282 #ifndef DOXYGEN

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

   284 #else

   285       typedef GraphIncIterator IncEdgeIt;

   286 #endif

   288       /// Iterator of edges incoming to a node

   289 #ifndef DOXYGEN

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

   291 #else

   292       typedef GraphIncIterator InEdgeIt;

   293 #endif

   295       /// Iterator of edges outgoing from a node

   296 #ifndef DOXYGEN

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

   298 #else

   299       typedef GraphIncIterator OutEdgeIt;

   300 #endif

   302       /// NodeMap template

   303 #ifdef DOXYGEN

   304       typedef GraphMap NodeMap<T>;

   305 #endif

   307       /// UndirEdgeMap template

   308 #ifdef DOXYGEN

   309       typedef GraphMap UndirEdgeMap<T>;

   310 #endif

   312       /// EdgeMap template

   313 #ifdef DOXYGEN

   314       typedef GraphMap EdgeMap<T>;

   315 #endif

   317       template <typename T>

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

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

   320       public:

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

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

   324       };

   326       template <typename T>

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

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

   329       public:

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

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

   333       };

   335       template <typename T>

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

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

   338       public:

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

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

   342       };

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

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

   347       /// the corresponding undirected edge.

   348       ///

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

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

   352       /// Opposite node on an edge

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

   355       ///

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

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

   359       /// First node of the undirected edge.

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

   362       ///

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

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

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

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

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

   368       /// of the directed versions of the edges.

   369       /// \sa forward

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

   372       /// Second node of the undirected edge.

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

   375       /// Source node of the directed edge.

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

   378       /// Target node of the directed edge.

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

   381       /// First 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 first(Node&) const {}

   387       /// Next node of the graph

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

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

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

   392       void next(Node&) const {}

   394       /// First 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 first(UndirEdge&) const {}

   400       /// Next undirected edge of the graph

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

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

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

   405       void next(UndirEdge&) const {}

   407       /// First 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 first(Edge&) const {}

   413       /// Next directed edge of the graph

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

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

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

   418       void next(Edge&) const {}

   420       /// First outgoing edge from a given 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 firstOut(Edge&, Node) const {}

   426       /// Next outgoing edge to a node

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

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

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

   431       void nextOut(Edge&) const {}

   433       /// First incoming edge to a given 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 firstIn(Edge&, Node) const {}

   439       /// Next incoming edge to a node

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

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

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

   444       void nextIn(Edge&) const {}

   447       /// Base node of the iterator

   448       ///

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

   450       Node baseNode(OutEdgeIt e) const {

   451 	return source(e);

   452       }

   453       /// Running node of the iterator

   454       ///

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

   456       /// iterator

   457       Node runningNode(OutEdgeIt e) const {

   458 	return target(e);

   459       }

   461       /// Base node of the iterator

   462       ///

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

   464       Node baseNode(InEdgeIt e) const {

   465 	return target(e);

   466       }

   467       /// Running node of the iterator

   468       ///

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

   470       /// iterator

   471       Node runningNode(InEdgeIt e) const {

   472 	return source(e);

   473       }

   475       /// Base node of the iterator

   476       ///

   477       /// Returns the base node of the iterator

   478       Node baseNode(IncEdgeIt) const {

   479 	return INVALID;

   480       }

   481       /// Running node of the iterator

   482       ///

   483       /// Returns the running node of the iterator

   484       Node runningNode(IncEdgeIt) const {

   485 	return INVALID;

   486       }

   489       template <typename Graph>

   490       struct Constraints {

   491 	void constraints() {

   492 	  checkConcept<BaseIterableUndirGraphConcept, Graph>();

   493 	  checkConcept<IterableUndirGraphConcept, Graph>();

   494 	  checkConcept<MappableUndirGraphConcept, Graph>();

   495 	}

   496       };

   498     };

   500     class ExtendableUndirGraph : public UndirGraph {

   501     public:

   503       template <typename Graph>

   504       struct Constraints {

   505 	void constraints() {

   506 	  checkConcept<BaseIterableUndirGraphConcept, Graph>();

   507 	  checkConcept<IterableUndirGraphConcept, Graph>();

   508 	  checkConcept<MappableUndirGraphConcept, Graph>();

   510 	  checkConcept<UndirGraph, Graph>();

   511 	  checkConcept<ExtendableUndirGraphConcept, Graph>();

   512 	  checkConcept<ClearableGraphComponent, Graph>();

   513 	}

   514       };

   516     };

   518     class ErasableUndirGraph : public ExtendableUndirGraph {

   519     public:

   521       template <typename Graph>

   522       struct Constraints {

   523 	void constraints() {

   524 	  checkConcept<ExtendableUndirGraph, Graph>();

   525 	  checkConcept<ErasableUndirGraphConcept, Graph>();

   526 	}

   527       };

   529     };

   531     /// @}

   533   }

   535 }

   537 #endif

author	alpar
	Mon, 04 Jul 2005 17:16:05 +0000
changeset 1537	0d9f1a71be27
parent 1435	8e85e6bbefdf
child 1620	09feafe81053
permissions	-rw-r--r--