lemon-0.x: lemon/concept/undir_graph.h@8b225c2935e7

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

     2  *

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

     4  * C++ optimization library

     5  *

     6  * Copyright (C) 2006 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.direction(e);

   123 	  Edge e = graph.direct(UndirEdge(), true);

   124 	  e = graph.direct(UndirEdge(), n);

   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     /// \addtogroup graph_concepts

   221     /// @{

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

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

   227     /// Graphs.

   228     ///

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

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

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

   232     /// run properly, of couse.

   233     ///

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

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

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

   237     /// a tutorial about undirected graphs.

   238     ///

   239     /// You can assume that all undirected graph can be handled

   240     /// as a static directed graph. This way it is fully conform

   241     /// to the StaticGraph concept.

   243     class UndirGraph {

   244     public:

   245       ///\e

   247       ///\todo undocumented

   248       ///

   249       typedef True UndirTag;

   251       /// \brief The base type of node iterators,

   252       /// or in other words, the trivial node iterator.

   253       ///

   254       /// This is the base type of each node iterator,

   255       /// thus each kind of node iterator converts to this.

   256       /// More precisely each kind of node iterator should be inherited

   257       /// from the trivial node iterator.

   258       class Node {

   259       public:

   260         /// Default constructor

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

   263         /// to an undefined value.

   264         Node() { }

   265         /// Copy constructor.

   267         /// Copy constructor.

   268         ///

   269         Node(const Node&) { }

   271         /// Invalid constructor \& conversion.

   273         /// This constructor initializes the iterator to be invalid.

   274         /// \sa Invalid for more details.

   275         Node(Invalid) { }

   276         /// Equality operator

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

   279         /// same object or both are invalid.

   280         bool operator==(Node) const { return true; }

   282         /// Inequality operator

   284         /// \sa operator==(Node n)

   285         ///

   286         bool operator!=(Node) const { return true; }

   288 	/// Artificial ordering operator.

   290 	/// To allow the use of graph descriptors as key type in std::map or

   291 	/// similar associative container we require this.

   292 	///

   293 	/// \note This operator only have to define some strict ordering of

   294 	/// the items; this order has nothing to do with the iteration

   295 	/// ordering of the items.

   296 	///

   297 	/// \bug This is a technical requirement. Do we really need this?

   298 	bool operator<(Node) const { return false; }

   300       };

   302       /// This iterator goes through each node.

   304       /// This iterator goes through each node.

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

   306       /// of nodes in graph \c g of type \c Graph like this:

   307       /// \code

   308       /// int count=0;

   309       /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;

   310       /// \endcode

   311       class NodeIt : public Node {

   312       public:

   313         /// Default constructor

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

   316         /// to an undefined value.

   317         NodeIt() { }

   318         /// Copy constructor.

   320         /// Copy constructor.

   321         ///

   322         NodeIt(const NodeIt& n) : Node(n) { }

   323         /// Invalid constructor \& conversion.

   325         /// Initialize the iterator to be invalid.

   326         /// \sa Invalid for more details.

   327         NodeIt(Invalid) { }

   328         /// Sets the iterator to the first node.

   330         /// Sets the iterator to the first node of \c g.

   331         ///

   332         NodeIt(const UndirGraph&) { }

   333         /// Node -> NodeIt conversion.

   335         /// Sets the iterator to the node of \c the graph pointed by

   336 	/// the trivial iterator.

   337         /// This feature necessitates that each time we

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

   339         NodeIt(const UndirGraph&, const Node&) { }

   340         /// Next node.

   342         /// Assign the iterator to the next node.

   343         ///

   344         NodeIt& operator++() { return *this; }

   345       };

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

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

   351       ///

   352       class UndirEdge {

   353       public:

   354         /// Default constructor

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

   357         /// to an undefined value.

   358         UndirEdge() { }

   359         /// Copy constructor.

   361         /// Copy constructor.

   362         ///

   363         UndirEdge(const UndirEdge&) { }

   364         /// Initialize the iterator to be invalid.

   366         /// Initialize the iterator to be invalid.

   367         ///

   368         UndirEdge(Invalid) { }

   369         /// Equality operator

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

   372         /// same object or both are invalid.

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

   374         /// Inequality operator

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

   377         ///

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

   380 	/// Artificial ordering operator.

   382 	/// To allow the use of graph descriptors as key type in std::map or

   383 	/// similar associative container we require this.

   384 	///

   385 	/// \note This operator only have to define some strict ordering of

   386 	/// the items; this order has nothing to do with the iteration

   387 	/// ordering of the items.

   388 	///

   389 	/// \bug This is a technical requirement. Do we really need this?

   390 	bool operator<(UndirEdge) const { return false; }

   391       };

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

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

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

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

   398       /// \code

   399       /// int count=0;

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

   401       /// \endcode

   402       class UndirEdgeIt : public UndirEdge {

   403       public:

   404         /// Default constructor

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

   407         /// to an undefined value.

   408         UndirEdgeIt() { }

   409         /// Copy constructor.

   411         /// Copy constructor.

   412         ///

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

   414         /// Initialize the iterator to be invalid.

   416         /// Initialize the iterator to be invalid.

   417         ///

   418         UndirEdgeIt(Invalid) { }

   419         /// This constructor sets the iterator to the first undirected edge.

   421         /// This constructor sets the iterator to the first undirected edge.

   422         UndirEdgeIt(const UndirGraph&) { }

   423         /// UndirEdge -> UndirEdgeIt conversion

   425         /// Sets the iterator to the value of the trivial iterator.

   426         /// This feature necessitates that each time we

   427         /// iterate the undirected edge-set, the iteration order is the

   428 	/// same.

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

   430         /// Next undirected edge

   432         /// Assign the iterator to the next undirected edge.

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

   434       };

   436       /// \brief This iterator goes trough the incident undirected

   437       /// edges of a node.

   438       ///

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

   440       /// of a certain node

   441       /// of a graph.

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

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

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

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

   446       /// \code

   447       /// int count=0;

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

   449       /// \endcode

   450       class IncEdgeIt : public UndirEdge {

   451       public:

   452         /// Default constructor

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

   455         /// to an undefined value.

   456         IncEdgeIt() { }

   457         /// Copy constructor.

   459         /// Copy constructor.

   460         ///

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

   462         /// Initialize the iterator to be invalid.

   464         /// Initialize the iterator to be invalid.

   465         ///

   466         IncEdgeIt(Invalid) { }

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

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

   470         /// the node.

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

   472         /// UndirEdge -> IncEdgeIt conversion

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

   475         /// This feature necessitates that each time we

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

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

   478         /// Next incident edge

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

   481 	/// of the corresponding node.

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

   483       };

   485       /// The directed edge type.

   487       /// The directed edge type. It can be converted to the

   488       /// undirected edge.

   489       class Edge : public UndirEdge {

   490       public:

   491         /// Default constructor

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

   494         /// to an undefined value.

   495         Edge() { }

   496         /// Copy constructor.

   498         /// Copy constructor.

   499         ///

   500         Edge(const Edge& e) : UndirEdge(e) { }

   501         /// Initialize the iterator to be invalid.

   503         /// Initialize the iterator to be invalid.

   504         ///

   505         Edge(Invalid) { }

   506         /// Equality operator

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

   509         /// same object or both are invalid.

   510         bool operator==(Edge) const { return true; }

   511         /// Inequality operator

   513         /// \sa operator==(Edge n)

   514         ///

   515         bool operator!=(Edge) const { return true; }

   517 	/// Artificial ordering operator.

   519 	/// To allow the use of graph descriptors as key type in std::map or

   520 	/// similar associative container we require this.

   521 	///

   522 	/// \note This operator only have to define some strict ordering of

   523 	/// the items; this order has nothing to do with the iteration

   524 	/// ordering of the items.

   525 	///

   526 	/// \bug This is a technical requirement. Do we really need this?

   527 	bool operator<(Edge) const { return false; }

   529       };

   530       /// This iterator goes through each directed edge.

   532       /// This iterator goes through each edge of a graph.

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

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

   535       /// \code

   536       /// int count=0;

   537       /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;

   538       /// \endcode

   539       class EdgeIt : public Edge {

   540       public:

   541         /// Default constructor

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

   544         /// to an undefined value.

   545         EdgeIt() { }

   546         /// Copy constructor.

   548         /// Copy constructor.

   549         ///

   550         EdgeIt(const EdgeIt& e) : Edge(e) { }

   551         /// Initialize the iterator to be invalid.

   553         /// Initialize the iterator to be invalid.

   554         ///

   555         EdgeIt(Invalid) { }

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

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

   559         ///@param g the graph

   560         EdgeIt(const UndirGraph &g) { ignore_unused_variable_warning(g); }

   561         /// Edge -> EdgeIt conversion

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

   564         /// This feature necessitates that each time we

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

   566         EdgeIt(const UndirGraph&, const Edge&) { }

   567         ///Next edge

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

   570         EdgeIt& operator++() { return *this; }

   571       };

   573       /// This iterator goes trough the outgoing directed edges of a node.

   575       /// This iterator goes trough the \e outgoing edges of a certain node

   576       /// of a graph.

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

   578       /// of outgoing edges of a node \c n

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

   580       /// \code

   581       /// int count=0;

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

   583       /// \endcode

   585       class OutEdgeIt : public Edge {

   586       public:

   587         /// Default constructor

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

   590         /// to an undefined value.

   591         OutEdgeIt() { }

   592         /// Copy constructor.

   594         /// Copy constructor.

   595         ///

   596         OutEdgeIt(const OutEdgeIt& e) : Edge(e) { }

   597         /// Initialize the iterator to be invalid.

   599         /// Initialize the iterator to be invalid.

   600         ///

   601         OutEdgeIt(Invalid) { }

   602         /// This constructor sets the iterator to the first outgoing edge.

   604         /// This constructor sets the iterator to the first outgoing edge of

   605         /// the node.

   606         ///@param n the node

   607         ///@param g the graph

   608         OutEdgeIt(const UndirGraph& n, const Node& g) {

   609 	  ignore_unused_variable_warning(n);

   610 	  ignore_unused_variable_warning(g);

   611 	}

   612         /// Edge -> OutEdgeIt conversion

   614         /// Sets the iterator to the value of the trivial iterator.

   615 	/// This feature necessitates that each time we

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

   617         OutEdgeIt(const UndirGraph&, const Edge&) { }

   618         ///Next outgoing edge

   620         /// Assign the iterator to the next

   621         /// outgoing edge of the corresponding node.

   622         OutEdgeIt& operator++() { return *this; }

   623       };

   625       /// This iterator goes trough the incoming directed edges of a node.

   627       /// This iterator goes trough the \e incoming edges of a certain node

   628       /// of a graph.

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

   630       /// of outgoing edges of a node \c n

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

   632       /// \code

   633       /// int count=0;

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

   635       /// \endcode

   637       class InEdgeIt : public Edge {

   638       public:

   639         /// Default constructor

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

   642         /// to an undefined value.

   643         InEdgeIt() { }

   644         /// Copy constructor.

   646         /// Copy constructor.

   647         ///

   648         InEdgeIt(const InEdgeIt& e) : Edge(e) { }

   649         /// Initialize the iterator to be invalid.

   651         /// Initialize the iterator to be invalid.

   652         ///

   653         InEdgeIt(Invalid) { }

   654         /// This constructor sets the iterator to first incoming edge.

   656         /// This constructor set the iterator to the first incoming edge of

   657         /// the node.

   658         ///@param n the node

   659         ///@param g the graph

   660         InEdgeIt(const UndirGraph& g, const Node& n) {

   661 	  ignore_unused_variable_warning(n);

   662 	  ignore_unused_variable_warning(g);

   663 	}

   664         /// Edge -> InEdgeIt conversion

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

   667         /// This feature necessitates that each time we

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

   669         InEdgeIt(const UndirGraph&, const Edge&) { }

   670         /// Next incoming edge

   672         /// Assign the iterator to the next inedge of the corresponding node.

   673         ///

   674         InEdgeIt& operator++() { return *this; }

   675       };

   677       /// \brief Read write map of the nodes to type \c T.

   678       ///

   679       /// ReadWrite map of the nodes to type \c T.

   680       /// \sa Reference

   681       /// \warning Making maps that can handle bool type (NodeMap<bool>)

   682       /// needs some extra attention!

   683       /// \todo Wrong documentation

   684       template<class T>

   685       class NodeMap : public ReadWriteMap< Node, T >

   686       {

   687       public:

   689         ///\e

   690         NodeMap(const UndirGraph&) { }

   691         ///\e

   692         NodeMap(const UndirGraph&, T) { }

   694         ///Copy constructor

   695         NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }

   696         ///Assignment operator

   697         NodeMap& operator=(const NodeMap&) { return *this; }

   698         // \todo fix this concept

   699       };

   701       /// \brief Read write map of the directed edges to type \c T.

   702       ///

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

   704       /// \sa Reference

   705       /// \warning Making maps that can handle bool type (EdgeMap<bool>)

   706       /// needs some extra attention!

   707       /// \todo Wrong documentation

   708       template<class T>

   709       class EdgeMap : public ReadWriteMap<Edge,T>

   710       {

   711       public:

   713         ///\e

   714         EdgeMap(const UndirGraph&) { }

   715         ///\e

   716         EdgeMap(const UndirGraph&, T) { }

   717         ///Copy constructor

   718         EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }

   719         ///Assignment operator

   720         EdgeMap& operator=(const EdgeMap&) { return *this; }

   721         // \todo fix this concept

   722       };

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

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

   727       /// \sa Reference

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

   729       /// needs some extra attention!

   730       /// \todo Wrong documentation

   731       template<class T>

   732       class UndirEdgeMap : public ReadWriteMap<UndirEdge,T>

   733       {

   734       public:

   736         ///\e

   737         UndirEdgeMap(const UndirGraph&) { }

   738         ///\e

   739         UndirEdgeMap(const UndirGraph&, T) { }

   740         ///Copy constructor

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

   742         ///Assignment operator

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

   744         // \todo fix this concept

   745       };

   747       /// \brief Direct the given undirected edge.

   748       ///

   749       /// Direct the given undirected edge. The returned edge source

   750       /// will be the given edge.

   751       Edge direct(const UndirEdge&, const Node&) const {

   752 	return INVALID;

   753       }

   755       /// \brief Direct the given undirected edge.

   756       ///

   757       /// Direct the given undirected edge. The returned edge source

   758       /// will be the source of the undirected edge if the given bool

   759       /// is true.

   760       Edge direct(const UndirEdge&, bool) const {

   761 	return INVALID;

   762       }

   764       /// \brief Returns true if the edge has default orientation.

   765       ///

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

   767       /// the corresponding undirected edge.

   768       bool direction(Edge) const { return true; }

   770       /// \brief Returns the opposite directed edge.

   771       ///

   772       /// Returns the opposite directed edge.

   773       Edge oppositeEdge(Edge) const { return INVALID; }

   775       /// \brief Opposite node on an edge

   776       ///

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

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

   780       /// \brief First node of the undirected edge.

   781       ///

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

   783       ///

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

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

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

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

   788       /// undirected edge, and is used to define the "default" direction

   789       /// of the directed versions of the edges.

   790       /// \sa direction

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

   793       /// \brief Second node of the undirected edge.

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

   796       /// \brief Source node of the directed edge.

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

   799       /// \brief Target node of the directed edge.

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

   802 //       /// \brief First node of the graph

   803 //       ///

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

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

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

   807       void first(Node&) const {}

   808 //       /// \brief Next node of the graph

   809 //       ///

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

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

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

   813       void next(Node&) const {}

   815 //       /// \brief First undirected edge of the graph

   816 //       ///

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

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

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

   820       void first(UndirEdge&) const {}

   821 //       /// \brief Next undirected edge of the graph

   822 //       ///

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

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

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

   826       void next(UndirEdge&) const {}

   828 //       /// \brief First directed edge of the graph

   829 //       ///

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

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

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

   833       void first(Edge&) const {}

   834 //       /// \brief Next directed edge of the graph

   835 //       ///

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

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

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

   839       void next(Edge&) const {}

   841 //       /// \brief First outgoing edge from a given node

   842 //       ///

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

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

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

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

   847 //       /// \brief Next outgoing edge to a node

   848 //       ///

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

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

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

   852       void nextOut(Edge&) const {}

   854 //       /// \brief First incoming edge to a given node

   855 //       ///

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

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

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

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

   860 //       /// \brief Next incoming edge to a node

   861 //       ///

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

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

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

   865       void nextIn(Edge&) const {}

   868       /// \brief Base node of the iterator

   869       ///

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

   871       Node baseNode(OutEdgeIt e) const {

   872 	return source(e);

   873       }

   874       /// \brief Running node of the iterator

   875       ///

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

   877       /// iterator

   878       Node runningNode(OutEdgeIt e) const {

   879 	return target(e);

   880       }

   882       /// \brief Base node of the iterator

   883       ///

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

   885       Node baseNode(InEdgeIt e) const {

   886 	return target(e);

   887       }

   888       /// \brief Running node of the iterator

   889       ///

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

   891       /// iterator

   892       Node runningNode(InEdgeIt e) const {

   893 	return source(e);

   894       }

   896       /// \brief Base node of the iterator

   897       ///

   898       /// Returns the base node of the iterator

   899       Node baseNode(IncEdgeIt) const {

   900 	return INVALID;

   901       }

   903       /// \brief Running node of the iterator

   904       ///

   905       /// Returns the running node of the iterator

   906       Node runningNode(IncEdgeIt) const {

   907 	return INVALID;

   908       }

   910       template <typename Graph>

   911       struct Constraints {

   912 	void constraints() {

   913 	  checkConcept<BaseIterableUndirGraphConcept, Graph>();

   914 	  checkConcept<IterableUndirGraphConcept, Graph>();

   915 	  checkConcept<MappableUndirGraphConcept, Graph>();

   916 	}

   917       };

   919     };

   921     /// \brief An empty non-static undirected graph class.

   922     ///

   923     /// This class provides everything that \ref UndirGraph does.

   924     /// Additionally it enables building graphs from scratch.

   925     class ExtendableUndirGraph : public UndirGraph {

   926     public:

   928       /// \brief Add a new node to the graph.

   929       ///

   930       /// Add a new node to the graph.

   931       /// \return the new node.

   932       Node addNode();

   934       /// \brief Add a new undirected edge to the graph.

   935       ///

   936       /// Add a new undirected edge to the graph.

   937       /// \return the new edge.

   938       UndirEdge addEdge(const Node& from, const Node& to);

   940       /// \brief Resets the graph.

   941       ///

   942       /// This function deletes all undirected edges and nodes of the graph.

   943       /// It also frees the memory allocated to store them.

   944       void clear() { }

   946       template <typename Graph>

   947       struct Constraints {

   948 	void constraints() {

   949 	  checkConcept<BaseIterableUndirGraphConcept, Graph>();

   950 	  checkConcept<IterableUndirGraphConcept, Graph>();

   951 	  checkConcept<MappableUndirGraphConcept, Graph>();

   953 	  checkConcept<UndirGraph, Graph>();

   954 	  checkConcept<ExtendableUndirGraphConcept, Graph>();

   955 	  checkConcept<ClearableGraphComponent, Graph>();

   956 	}

   957       };

   959     };

   961     /// \brief An empty erasable undirected graph class.

   962     ///

   963     /// This class is an extension of \ref ExtendableUndirGraph. It makes it

   964     /// possible to erase undirected edges or nodes.

   965     class ErasableUndirGraph : public ExtendableUndirGraph {

   966     public:

   968       /// \brief Deletes a node.

   969       ///

   970       /// Deletes a node.

   971       ///

   972       void erase(Node) { }

   973       /// \brief Deletes an undirected edge.

   974       ///

   975       /// Deletes an undirected edge.

   976       ///

   977       void erase(UndirEdge) { }

   979       template <typename Graph>

   980       struct Constraints {

   981 	void constraints() {

   982 	  checkConcept<ExtendableUndirGraph, Graph>();

   983 	  checkConcept<ErasableUndirGraphConcept, Graph>();

   984 	}

   985       };

   987     };

   989     /// @}

   991   }

   993 }

   995 #endif

author	hegyi
	Mon, 09 Jan 2006 11:55:47 +0000
changeset 1886	8b225c2935e7
parent 1669	66ae78d29f1e
permissions	-rw-r--r--