lemon-0.x: lemon/concept/undir_graph.h@61cc647dac99

     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         UndirEdgeIt(const UndirGraph&) { }

   318         /// UndirEdge -> UndirEdgeIt conversion

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

   321         /// This feature necessitates that each time we

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

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

   324         ///Next edge

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

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

   328       };

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

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

   333       /// of a certain node

   334       /// of a graph.

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

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

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

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

   339       /// \code

   340       /// int count=0;

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

   342       /// \endcode

   343       class IncEdgeIt : public UndirEdge {

   344       public:

   345         /// Default constructor

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

   348         /// to an undefined value.

   349         IncEdgeIt() { }

   350         /// Copy constructor.

   352         /// Copy constructor.

   353         ///

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

   355         /// Initialize the iterator to be invalid.

   357         /// Initialize the iterator to be invalid.

   358         ///

   359         IncEdgeIt(Invalid) { }

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

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

   363         /// the node.

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

   365         /// UndirEdge -> IncEdgeIt conversion

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

   368         /// This feature necessitates that each time we

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

   370         IncEdgeIt(const UndirGraph&, const UndirEdge&) { }

   371         /// Next incident edge

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

   374 	/// of the corresponding node.

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

   376       };

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

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

   381       /// \sa Reference

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

   383       /// needs some extra attention!

   384       template<class T>

   385       class UndirEdgeMap : public ReadWriteMap<UndirEdge,T>

   386       {

   387       public:

   389         ///\e

   390         UndirEdgeMap(const UndirGraph&) { }

   391         ///\e

   392         UndirEdgeMap(const UndirGraph&, T) { }

   393         ///Copy constructor

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

   395         ///Assignment operator

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

   397         // \todo fix this concept

   398       };

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

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

   403       /// the corresponding undirected edge.

   404       ///

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

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

   408       /// Opposite node on an edge

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

   411       ///

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

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

   415       /// First node of the undirected edge.

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

   418       ///

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

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

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

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

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

   424       /// of the directed versions of the edges.

   425       /// \sa forward

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

   428       /// Second node of the undirected edge.

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

   431       /// Source node of the directed edge.

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

   434       /// Target node of the directed edge.

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

   437       /// First node of the graph

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

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

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

   442       void first(Node&) const {}

   443       /// Next node of the graph

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

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

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

   448       void next(Node&) const {}

   450       /// First undirected edge of the graph

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

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

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

   455       void first(UndirEdge&) const {}

   456       /// Next undirected edge of the graph

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

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

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

   461       void next(UndirEdge&) const {}

   463       /// First directed edge of the graph

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

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

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

   468       void first(Edge&) const {}

   469       /// Next directed edge of the graph

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

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

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

   474       void next(Edge&) const {}

   476       /// First outgoing edge from a given node

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

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

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

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

   482       /// Next outgoing edge to a node

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

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

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

   487       void nextOut(Edge&) const {}

   489       /// First incoming edge to a given node

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

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

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

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

   495       /// Next incoming edge to a node

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

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

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

   500       void nextIn(Edge&) const {}

   503       /// Base node of the iterator

   504       ///

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

   506       Node baseNode(OutEdgeIt e) const {

   507 	return source(e);

   508       }

   509       /// Running node of the iterator

   510       ///

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

   512       /// iterator

   513       Node runningNode(OutEdgeIt e) const {

   514 	return target(e);

   515       }

   517       /// Base node of the iterator

   518       ///

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

   520       Node baseNode(InEdgeIt e) const {

   521 	return target(e);

   522       }

   523       /// Running node of the iterator

   524       ///

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

   526       /// iterator

   527       Node runningNode(InEdgeIt e) const {

   528 	return source(e);

   529       }

   531       /// Base node of the iterator

   532       ///

   533       /// Returns the base node of the iterator

   534       Node baseNode(IncEdgeIt) const {

   535 	return INVALID;

   536       }

   537       /// Running node of the iterator

   538       ///

   539       /// Returns the running node of the iterator

   540       Node runningNode(IncEdgeIt) const {

   541 	return INVALID;

   542       }

   545       template <typename Graph>

   546       struct Constraints {

   547 	void constraints() {

   548 	  checkConcept<BaseIterableUndirGraphConcept, Graph>();

   549 	  checkConcept<IterableUndirGraphConcept, Graph>();

   550 	  checkConcept<MappableUndirGraphConcept, Graph>();

   551 	}

   552       };

   554     };

   556     class ExtendableUndirGraph : public UndirGraph {

   557     public:

   559       template <typename Graph>

   560       struct Constraints {

   561 	void constraints() {

   562 	  checkConcept<BaseIterableUndirGraphConcept, Graph>();

   563 	  checkConcept<IterableUndirGraphConcept, Graph>();

   564 	  checkConcept<MappableUndirGraphConcept, Graph>();

   566 	  checkConcept<UndirGraph, Graph>();

   567 	  checkConcept<ExtendableUndirGraphConcept, Graph>();

   568 	  checkConcept<ClearableGraphComponent, Graph>();

   569 	}

   570       };

   572     };

   574     class ErasableUndirGraph : public ExtendableUndirGraph {

   575     public:

   577       template <typename Graph>

   578       struct Constraints {

   579 	void constraints() {

   580 	  checkConcept<ExtendableUndirGraph, Graph>();

   581 	  checkConcept<ErasableUndirGraphConcept, Graph>();

   582 	}

   583       };

   585     };

   587     /// @}

   589   }

   591 }

   593 #endif

author	alpar
	Thu, 11 Aug 2005 14:31:06 +0000
changeset 1624	61cc647dac99
parent 1620	09feafe81053
child 1627	3fd1ba6e9872
permissions	-rw-r--r--