# HG changeset patch # User alpar # Date 1123765674 0 # Node ID 09feafe81053777d8befe970d6ecc5e2c83f9869 # Parent f0700b9e6418329ef0f704dd56db4789e930c0c1 Start working on UndirGraph concept clarification and its harmonization with the directed graph concept. Not yet done!!! diff -r f0700b9e6418 -r 09feafe81053 lemon/concept/graph.h --- a/lemon/concept/graph.h Wed Aug 10 19:23:51 2005 +0000 +++ b/lemon/concept/graph.h Thu Aug 11 13:07:54 2005 +0000 @@ -31,9 +31,6 @@ namespace concept { - /// \addtogroup graph_concepts - /// @{ - /**************** The full-featured graph concepts ****************/ @@ -101,6 +98,9 @@ }; }; + /// \addtogroup graph_concepts + /// @{ + /// An empty static graph class. /// This class provides all the common features of a graph structure, @@ -252,7 +252,7 @@ bool operator==(Edge) const { return true; } /// Inequality operator - /// \sa operator==(Node n) + /// \sa operator==(Edge n) /// bool operator!=(Edge) const { return true; } }; diff -r f0700b9e6418 -r 09feafe81053 lemon/concept/graph_component.h --- a/lemon/concept/graph_component.h Wed Aug 10 19:23:51 2005 +0000 +++ b/lemon/concept/graph_component.h Thu Aug 11 13:07:54 2005 +0000 @@ -30,9 +30,6 @@ namespace lemon { namespace concept { - /// \addtogroup graph_concepts - /// @{ - /**************** Graph iterator concepts ****************/ /// Skeleton class for graph Node and Edge types @@ -996,8 +993,6 @@ }; }; - /// @} - } } diff -r f0700b9e6418 -r 09feafe81053 lemon/concept/undir_graph.h --- a/lemon/concept/undir_graph.h Wed Aug 10 19:23:51 2005 +0000 +++ b/lemon/concept/undir_graph.h Thu Aug 11 13:07:54 2005 +0000 @@ -26,15 +26,12 @@ #define LEMON_CONCEPT_UNDIR_GRAPH_H #include +#include #include namespace lemon { namespace concept { - /// \addtogroup graph_concepts - /// @{ - - /// Skeleton class which describes an edge with direction in \ref /// UndirGraph "undirected graph". template @@ -108,7 +105,7 @@ void constraints() { checkConcept(); checkConcept, UndirEdge>(); - checkConcept, Edge>(); + //checkConcept, Edge>(); graph.first(ue); graph.next(ue); @@ -217,6 +214,10 @@ }; + /// \addtogroup graph_concepts + /// @{ + + /// Class describing the concept of Undirected Graphs. /// This class describes the common interface of all Undirected @@ -232,7 +233,7 @@ /// explanation of this and more see also the page \ref undir_graphs, /// a tutorial about undirected graphs. - class UndirGraph { + class UndirGraph : public StaticGraph { public: ///\e @@ -240,105 +241,163 @@ /// typedef True UndirTag; - /// Type describing a node in the graph - typedef GraphNode Node; + /// The base type of the undirected edge iterators. + + /// The base type of the undirected edge iterators. + /// + class UndirEdge { + public: + /// Default constructor - /// Type describing an undirected edge - typedef GraphItem<'u'> UndirEdge; + /// @warning The default constructor sets the iterator + /// to an undefined value. + UndirEdge() { } + /// Copy constructor. - /// Type describing an UndirEdge with direction -#ifndef DOXYGEN - typedef UndirGraphEdge Edge; -#else - typedef UndirGraphEdge Edge; -#endif + /// Copy constructor. + /// + UndirEdge(const UndirEdge&) { } + /// Edge -> UndirEdge conversion - /// Iterator type which iterates over all nodes -#ifndef DOXYGEN - typedef GraphIterator NodeIt; -#else - typedef GraphIterator NodeIt; -#endif + /// Edge -> UndirEdge conversion + /// + UndirEdge(const Edge&) { } + /// Initialize the iterator to be invalid. - /// Iterator type which iterates over all undirected edges -#ifndef DOXYGEN - typedef GraphIterator UndirEdgeIt; -#else - typedef GraphIterator UndirEdgeIt; -#endif + /// Initialize the iterator to be invalid. + /// + UndirEdge(Invalid) { } + /// Equality operator - /// Iterator type which iterates over all directed edges. + /// Two iterators are equal if and only if they point to the + /// same object or both are invalid. + bool operator==(UndirEdge) const { return true; } + /// Inequality operator - /// Iterator type which iterates over all edges (each undirected - /// edge occurs twice with both directions. -#ifndef DOXYGEN - typedef GraphIterator EdgeIt; -#else - typedef GraphIterator EdgeIt; -#endif + /// \sa operator==(UndirEdge n) + /// + bool operator!=(UndirEdge) const { return true; } + ///\e - /// Iterator of undirected edges incident to a node -#ifndef DOXYGEN - typedef GraphIncIterator IncEdgeIt; -#else - typedef GraphIncIterator IncEdgeIt; -#endif + ///\todo Do we need this? + /// + bool operator<(const UndirEdge &that) const { return true; } + }; + + /// This iterator goes through each undirected edge. - /// Iterator of edges incoming to a node -#ifndef DOXYGEN - typedef GraphIncIterator InEdgeIt; -#else - typedef GraphIncIterator InEdgeIt; -#endif + /// This iterator goes through each undirected edge of a graph. + /// Its usage is quite simple, for example you can count the number + /// of edges in a graph \c g of type \c Graph as follows: + /// \code + /// int count=0; + /// for(Graph::UndirEdgeIt e(g); e!=INVALID; ++e) ++count; + /// \endcode + class UndirEdgeIt : public UndirEdge { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + UndirEdgeIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + UndirEdgeIt(const UndirEdgeIt& e) : UndirEdge(e) { } + /// Initialize the iterator to be invalid. - /// Iterator of edges outgoing from a node -#ifndef DOXYGEN - typedef GraphIncIterator OutEdgeIt; -#else - typedef GraphIncIterator OutEdgeIt; -#endif + /// Initialize the iterator to be invalid. + /// + UndirEdgeIt(Invalid) { } + /// This constructor sets the iterator to the first edge. + + /// This constructor sets the iterator to the first edge of \c g. + ///@param g the graph + UndirEdgeIt(const UndirGraph&) { } + /// UndirEdge -> UndirEdgeIt conversion - /// NodeMap template -#ifdef DOXYGEN - typedef GraphMap NodeMap; -#endif + /// Sets the iterator to the value of the trivial iterator \c e. + /// This feature necessitates that each time we + /// iterate the edge-set, the iteration order is the same. + UndirEdgeIt(const UndirGraph&, const UndirEdge&) { } + ///Next edge + + /// Assign the iterator to the next edge. + UndirEdgeIt& operator++() { return *this; } + }; - /// UndirEdgeMap template -#ifdef DOXYGEN - typedef GraphMap UndirEdgeMap; -#endif + /// This iterator goes trough the incident undirected edges of a node. - /// EdgeMap template -#ifdef DOXYGEN - typedef GraphMap EdgeMap; -#endif + /// This iterator goes trough the incident undirected edges + /// of a certain node + /// of a graph. + /// Its usage is quite simple, for example you can compute the + /// degree (i.e. count the number + /// of incident edges of a node \c n + /// in graph \c g of type \c Graph as follows. + /// \code + /// int count=0; + /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count; + /// \endcode + class IncEdgeIt : public UndirEdge { + public: + /// Default constructor - template - class NodeMap : public GraphMap { - typedef GraphMap Parent; + /// @warning The default constructor sets the iterator + /// to an undefined value. + IncEdgeIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + IncEdgeIt(const IncEdgeIt& e) : UndirEdge(e) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + IncEdgeIt(Invalid) { } + /// This constructor sets the iterator to first incident edge. + + /// This constructor set the iterator to the first incident edge of + /// the node. + ///@param n the node + ///@param g the graph + IncEdgeIt(const UndirGraph&, const Node&) { } + /// UndirEdge -> IncEdgeIt conversion + + /// Sets the iterator to the value of the trivial iterator \c e. + /// This feature necessitates that each time we + /// iterate the edge-set, the iteration order is the same. + IncEdgeIt(const UndirGraph&, const UndirEdge&) { } + /// Next incident edge + + /// Assign the iterator to the next incident edge + /// of the corresponding node. + IncEdgeIt& operator++() { return *this; } + }; + + /// Read write map of the undirected edges to type \c T. + + /// Reference map of the edges to type \c T. + /// \sa Reference + /// \warning Making maps that can handle bool type (UndirEdgeMap) + /// needs some extra attention! + template + class UndirEdgeMap : public ReadWriteMap + { public: - explicit NodeMap(const UndirGraph &g) : Parent(g) {} - NodeMap(const UndirGraph &g, T t) : Parent(g, t) {} - }; - - template - class UndirEdgeMap : public GraphMap { - typedef GraphMap Parent; - public: - - explicit UndirEdgeMap(const UndirGraph &g) : Parent(g) {} - UndirEdgeMap(const UndirGraph &g, T t) : Parent(g, t) {} - }; - - template - class EdgeMap : public GraphMap { - typedef GraphMap Parent; - public: - - explicit EdgeMap(const UndirGraph &g) : Parent(g) {} - EdgeMap(const UndirGraph &g, T t) : Parent(g, t) {} + ///\e + UndirEdgeMap(const UndirGraph&) { } + ///\e + UndirEdgeMap(const UndirGraph&, T) { } + ///Copy constructor + UndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap(em) { } + ///Assignment operator + UndirEdgeMap &operator=(const UndirEdgeMap&) { return *this; } + // \todo fix this concept }; /// Is the Edge oriented "forward"?