1.1 --- a/doc/Doxyfile	Fri Dec 03 12:19:26 2004 +0000
     1.2 +++ b/doc/Doxyfile	Mon Dec 06 00:30:44 2004 +0000
     1.3 @@ -425,12 +425,14 @@
     1.4  
     1.5  INPUT                  = mainpage.dox \
     1.6                           graphs.dox \
     1.7 +                         undir_graphs.dox \ 
     1.8                           named-param.dox \
     1.9                           maps.dox \
    1.10                           coding_style.dox \
    1.11                           groups.dox \
    1.12                           namespaces.dox \
    1.13  			 license.dox \
    1.14 +                         developpers_interface.dox \
    1.15                           ../src/lemon \
    1.16                           ../src/lemon/concept \
    1.17                           ../src/test/test_tools.h

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/doc/developpers_interface.dox	Mon Dec 06 00:30:44 2004 +0000
     2.3 @@ -0,0 +1,7 @@
     2.4 +/*!
     2.5 +
     2.6 +\page developpers_interface Developpers' interface to graph structures
     2.7 +
     2.8 +Under construction
     2.9 +
    2.10 +*/

     3.1 --- a/doc/groups.dox	Fri Dec 03 12:19:26 2004 +0000
     3.2 +++ b/doc/groups.dox	Mon Dec 06 00:30:44 2004 +0000
     3.3 @@ -80,15 +80,27 @@
     3.4  */
     3.5  
     3.6  /**
     3.7 -@defgroup concept Concept
     3.8 +@defgroup concept Concepts
     3.9  \brief Skeleton classes and concept checking classes
    3.10  
    3.11  This group describes the data/algorithm skeletons and concept checking
    3.12 -classes implemented in LEMON. These classes exist in order to make it
    3.13 -easier to check if a certain template class or template function is
    3.14 -correctly implemented.
    3.15 +classes implemented in LEMON.
    3.16 +
    3.17 +One aim of these classes is to make it easier to check if a certain
    3.18 +class or template function is correctly implemented.
    3.19 +
    3.20 +The other (sometimes even more important) aim is to document the concepts.
    3.21 +
    3.22  */
    3.23  
    3.24 +/**
    3.25 +@defgroup graph_concepts Graph Structure Concepts
    3.26 +@ingroup concept
    3.27 +\brief Skeleton and concept checking classes for graph structures
    3.28 +
    3.29 +This group contains the skeletons and concept checking classes of LEMON's
    3.30 +graph structures and helper classes used to implement these.
    3.31 +*/
    3.32  
    3.33  /**
    3.34  @defgroup experimental Experimental Structures and Algorithms

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/doc/undir_graphs.dox	Mon Dec 06 00:30:44 2004 +0000
     4.3 @@ -0,0 +1,9 @@
     4.4 +/*!
     4.5 +
     4.6 +\page undir_graphs Undirected graph structures
     4.7 +
     4.8 +The primary data structures of LEMON are the graph classes.
     4.9 +
    4.10 +Under construction.
    4.11 +
    4.12 +*/

     5.1 --- a/src/lemon/concept/graph.h	Fri Dec 03 12:19:26 2004 +0000
     5.2 +++ b/src/lemon/concept/graph.h	Mon Dec 06 00:30:44 2004 +0000
     5.3 @@ -17,7 +17,7 @@
     5.4  #ifndef LEMON_CONCEPT_GRAPH_H
     5.5  #define LEMON_CONCEPT_GRAPH_H
     5.6  
     5.7 -///\ingroup concept
     5.8 +///\ingroup graph_concepts
     5.9  ///\file
    5.10  ///\brief Declaration of Graph.
    5.11  
    5.12 @@ -29,7 +29,7 @@
    5.13  namespace lemon {
    5.14    namespace concept {
    5.15      
    5.16 -    /// \addtogroup concept
    5.17 +    /// \addtogroup graph_concepts
    5.18      /// @{
    5.19  
    5.20  //     /// An empty static graph class.

     6.1 --- a/src/lemon/concept/graph_component.h	Fri Dec 03 12:19:26 2004 +0000
     6.2 +++ b/src/lemon/concept/graph_component.h	Mon Dec 06 00:30:44 2004 +0000
     6.3 @@ -14,7 +14,7 @@
     6.4   *
     6.5   */
     6.6  
     6.7 -///\ingroup concept
     6.8 +///\ingroup graph_concepts
     6.9  ///\file
    6.10  ///\brief The graph components.
    6.11  
    6.12 @@ -28,22 +28,32 @@
    6.13  namespace lemon {
    6.14    namespace concept {
    6.15  
    6.16 +    /// \addtogroup graph_concepts
    6.17 +    /// @{
    6.18  
    6.19      /****************   Graph iterator concepts   ****************/
    6.20  
    6.21 -    /// Skeleton class for graph Node and Edge
    6.22 +    /// Skeleton class for graph Node and Edge types
    6.23  
    6.24 -    /// \note Because Node and Edge are forbidden to inherit from the same
    6.25 -    /// base class, this is a template. For Node you should instantiate it
    6.26 -    /// with character 'n' and for Edge with 'e'.
    6.27 +    /// This class describes the interface of Node and Edge (and UndirEdge
    6.28 +    /// in undirected graphs) subtypes of graph types.
    6.29 +    ///
    6.30 +    /// \note This class is a template class so that we can use it to
    6.31 +    /// create graph skeleton classes. The reason for this is than Node
    6.32 +    /// and Edge types should \em not derive from the same base class.
    6.33 +    /// For Node you should instantiate it with character 'n' and for Edge
    6.34 +    /// with 'e'.
    6.35  
    6.36 -    template<char _selector>
    6.37 +#ifndef DOXYGEN
    6.38 +    template <char _selector = '0'>
    6.39 +#endif
    6.40      class GraphItem {
    6.41      public:
    6.42        /// Default constructor.
    6.43        
    6.44 -      /// @warning The default constructor sets the item
    6.45 -      /// to an undefined value.
    6.46 +      /// \warning The default constructor is not required to set
    6.47 +      /// the item to some well-defined value. So you should consider it
    6.48 +      /// as uninitialized.
    6.49        GraphItem() {}
    6.50        /// Copy constructor.
    6.51        
    6.52 @@ -71,9 +81,17 @@
    6.53        ///
    6.54        bool operator!=(GraphItem) const { return false; }
    6.55  
    6.56 -      // Technical requirement. Do we really need this?
    6.57 -      //      bool operator<(GraphItem) const { return false; }
    6.58 +      /// Artificial ordering operator.
    6.59  
    6.60 +      /// To allow the use of graph descriptors as key type in std::map or
    6.61 +      /// similar associative container we require this.
    6.62 +      ///
    6.63 +      /// \note This operator only have to define some strict ordering of
    6.64 +      /// the items; this order has nothing to do with the iteration
    6.65 +      /// ordering of the items.
    6.66 +      ///
    6.67 +      /// \bug This is a technical requirement. Do we really need this?
    6.68 +      bool operator<(GraphItem) const { return false; }
    6.69  
    6.70        template<typename _GraphItem>
    6.71        struct Constraints {
    6.72 @@ -88,6 +106,7 @@
    6.73  	  //	  b = (ia == ib) && (ia != ib) && (ia < ib);
    6.74  	  b = (ia == ib) && (ia != ib);
    6.75  	  b = (ia == INVALID) && (ib != INVALID);
    6.76 +	  b = (ia < ib);
    6.77  	}
    6.78  
    6.79  	const _GraphItem &ia;
    6.80 @@ -95,6 +114,21 @@
    6.81        };
    6.82      };
    6.83  
    6.84 +    /// A type describing the concept of graph node
    6.85 +
    6.86 +    /// This is an instantiation of \ref GraphItem which can be used as a
    6.87 +    /// Node subtype in graph skeleton definitions
    6.88 +    typedef GraphItem<'n'> GraphNode;
    6.89 +
    6.90 +    /// A type describing the concept of graph edge
    6.91 +
    6.92 +    /// This is an instantiation of \ref GraphItem which can be used as a
    6.93 +    /// Edge subtype in graph skeleton definitions
    6.94 +    typedef GraphItem<'e'> GraphEdge;
    6.95 +
    6.96 +
    6.97 +    /**************** Basic features of graphs ****************/
    6.98 +
    6.99      /// An empty base graph class.
   6.100    
   6.101      /// This class provides the minimal set of features needed for a graph
   6.102 @@ -629,6 +663,11 @@
   6.103      };
   6.104  
   6.105  
   6.106 +    /// Class describing the concept of graph maps
   6.107 +
   6.108 +    /// This class describes the common interface of the graph maps
   6.109 +    /// (NodeMap, EdgeMap), that is \ref maps "maps" which can be used to
   6.110 +    /// associate data to graph descriptors (nodes or edges).
   6.111      template <typename Graph, typename Item, typename _Value>
   6.112      class GraphMap : public ReadWriteMap<Item, _Value> {
   6.113      protected:      
   6.114 @@ -804,6 +843,8 @@
   6.115        };
   6.116      };
   6.117  
   6.118 +    /// @}
   6.119 +
   6.120    }
   6.121  
   6.122  }

     7.1 --- a/src/lemon/concept/undir_graph.h	Fri Dec 03 12:19:26 2004 +0000
     7.2 +++ b/src/lemon/concept/undir_graph.h	Mon Dec 06 00:30:44 2004 +0000
     7.3 @@ -17,7 +17,7 @@
     7.4   *
     7.5   */
     7.6  
     7.7 -///\ingroup concept
     7.8 +///\ingroup graph_concepts
     7.9  ///\file
    7.10  ///\brief Undirected graphs and components of.
    7.11  
    7.12 @@ -30,7 +30,62 @@
    7.13  namespace lemon {
    7.14    namespace concept {
    7.15  
    7.16 -    /// \todo to be done
    7.17 +    /// \addtogroup graph_concepts
    7.18 +    /// @{
    7.19 +
    7.20 +
    7.21 +    /// Skeleton class which describes an edge with direction in \ref
    7.22 +    /// UndirGraph "undirected graph".
    7.23 +    template <typename UndirEdge>
    7.24 +    class UndirGraphEdge : public UndirEdge {
    7.25 +    public:
    7.26 +
    7.27 +      /// \e
    7.28 +      UndirGraphEdge() {}
    7.29 +
    7.30 +      /// \e
    7.31 +      UndirGraphEdge(const UndirGraphEdge&) {}
    7.32 +
    7.33 +      /// \e
    7.34 +      UndirGraphEdge(Invalid) {}
    7.35 +
    7.36 +      /// \brief Constructs a directed version of an undirected edge
    7.37 +      ///
    7.38 +      /// \param forward If \c true the direction of the contructed edge
    7.39 +      /// is the same as the inherent direction of the \c undir_edge; if
    7.40 +      /// \c false --- the opposite.
    7.41 +      UndirGraphEdge(UndirEdge undir_edge, bool forward) {
    7.42 +	ignore_unused_variable_warning(undir_edge);
    7.43 +	ignore_unused_variable_warning(forward);
    7.44 +      }
    7.45 +
    7.46 +      /// \e
    7.47 +      UndirGraphEdge& operator=(UndirGraphEdge) { return *this; }
    7.48 +
    7.49 +      /// \e
    7.50 +      bool operator==(UndirGraphEdge) const { return true; }
    7.51 +      /// \e
    7.52 +      bool operator!=(UndirGraphEdge) const { return false; }
    7.53 +
    7.54 +      /// \e
    7.55 +      bool operator<(UndirGraphEdge) const { return false; }
    7.56 +
    7.57 +      template <typename Edge>
    7.58 +      struct Constraints {
    7.59 +	void constraints() {
    7.60 +	  /// \bug This should be is_base_and_derived ...
    7.61 +	  UndirEdge ue = e;
    7.62 +	  ue = e;
    7.63 +	  Edge forward(ue, true);
    7.64 +	  Edge backward(ue, false);
    7.65 +
    7.66 +	  ignore_unused_variable_warning(forward);
    7.67 +	  ignore_unused_variable_warning(backward);
    7.68 +	}
    7.69 +	Edge e;
    7.70 +      };
    7.71 +    };
    7.72 +    
    7.73  
    7.74      struct BaseIterableUndirGraphConcept {
    7.75  
    7.76 @@ -43,21 +98,29 @@
    7.77  
    7.78  	void constraints() {
    7.79  	  checkConcept<BaseIterableGraphComponent, Graph>();
    7.80 -	  checkConcept<GraphItem<'u'>, UndirEdge >();
    7.81 +	  checkConcept<GraphItem<>, UndirEdge>();
    7.82 +	  checkConcept<UndirGraphEdge<UndirEdge>, Edge>();
    7.83  
    7.84 -	  /// \bug this should be base_and_derived:
    7.85 -	  UndirEdge ue = e;
    7.86 -	  ue = e;
    7.87 +	  graph.first(ue);
    7.88 +	  graph.next(ue);
    7.89  
    7.90 +	  const_constraints();
    7.91 +	}
    7.92 +	void const_constraints() {
    7.93  	  Node n;
    7.94  	  n = graph.target(ue);
    7.95  	  n = graph.source(ue);
    7.96 +	  n = graph.oppositeNode(n0, ue);
    7.97  
    7.98 -	  graph.first(ue);
    7.99 -	  graph.next(ue);
   7.100 +	  bool b;
   7.101 +	  b = graph.forward(e);
   7.102 +	  ignore_unused_variable_warning(b);
   7.103  	}
   7.104 -	const Graph &graph;
   7.105 +
   7.106 +	Graph graph;
   7.107  	Edge e;
   7.108 +	Node n0;
   7.109 +	UndirEdge ue;
   7.110        };
   7.111  
   7.112      };
   7.113 @@ -76,10 +139,10 @@
   7.114  
   7.115  	  typedef typename Graph::UndirEdge UndirEdge;
   7.116  	  typedef typename Graph::UndirEdgeIt UndirEdgeIt;
   7.117 -	  typedef typename Graph::UndirIncEdgeIt UndirIncEdgeIt;
   7.118 +	  typedef typename Graph::IncEdgeIt IncEdgeIt;
   7.119  
   7.120  	  checkConcept<GraphIterator<Graph, UndirEdge>, UndirEdgeIt>();
   7.121 -	  checkConcept<GraphIncIterator<Graph, UndirEdge>, UndirIncEdgeIt>();
   7.122 +	  checkConcept<GraphIncIterator<Graph, UndirEdge>, IncEdgeIt>();
   7.123  	}
   7.124        };
   7.125  
   7.126 @@ -145,9 +208,228 @@
   7.127  
   7.128      };
   7.129  
   7.130 +    /// Class describing the concept of Undirected Graphs.
   7.131 +
   7.132 +    /// This class describes the common interface of all Undirected
   7.133 +    /// Graphs.
   7.134 +    ///
   7.135 +    /// As all concept describing classes it provides only interface
   7.136 +    /// without any sensible implementation. So any algorithm for
   7.137 +    /// undirected graph should compile with this class, but it will not
   7.138 +    /// run properly, of couse.
   7.139 +    ///
   7.140 +    /// In LEMON undirected graphs also fulfill the concept of directed
   7.141 +    /// graphs (\ref lemon::concept::Graph "Graph Concept"). For
   7.142 +    /// explanation of this and more see also the page \ref undir_graphs,
   7.143 +    /// a tutorial about undirected graphs.
   7.144 +
   7.145      class UndirGraph {
   7.146      public:
   7.147  
   7.148 +      /// Type describing a node in the graph
   7.149 +      typedef GraphNode Node;
   7.150 +
   7.151 +      /// Type describing an undirected edge
   7.152 +      typedef GraphItem<'u'> UndirEdge;
   7.153 +
   7.154 +      /// Type describing an UndirEdge with direction
   7.155 +#ifndef DOXYGEN
   7.156 +      typedef UndirGraphEdge<UndirEdge> Edge;
   7.157 +#else
   7.158 +      typedef UndirGraphEdge Edge;
   7.159 +#endif
   7.160 +
   7.161 +      /// Iterator type which iterates over all nodes
   7.162 +#ifndef DOXYGEN
   7.163 +      typedef GraphIterator<UndirGraph, Node> NodeIt;
   7.164 +#else
   7.165 +      typedef GraphIterator NodeIt;
   7.166 +#endif
   7.167 +
   7.168 +      /// Iterator type which iterates over all undirected edges
   7.169 +#ifndef DOXYGEN
   7.170 +      typedef GraphIterator<UndirGraph, UndirEdge> UndirEdgeIt;
   7.171 +#else
   7.172 +      typedef GraphIterator UndirEdgeIt;
   7.173 +#endif
   7.174 +
   7.175 +      /// Iterator type which iterates over all directed edges.
   7.176 +
   7.177 +      /// Iterator type which iterates over all edges (each undirected
   7.178 +      /// edge occurs twice with both directions.
   7.179 +#ifndef DOXYGEN
   7.180 +      typedef GraphIterator<UndirGraph, Edge> EdgeIt;
   7.181 +#else
   7.182 +      typedef GraphIterator EdgeIt;
   7.183 +#endif
   7.184 +
   7.185 +
   7.186 +      /// Iterator of undirected edges incident to a node
   7.187 +#ifndef DOXYGEN
   7.188 +      typedef GraphIncIterator<UndirGraph, UndirEdge, 'u'> IncEdgeIt;
   7.189 +#else
   7.190 +      typedef GraphIncIterator IncEdgeIt;
   7.191 +#endif
   7.192 +
   7.193 +      /// Iterator of edges incoming to a node
   7.194 +#ifndef DOXYGEN
   7.195 +      typedef GraphIncIterator<UndirGraph, Edge, 'i'> InEdgeIt;
   7.196 +#else
   7.197 +      typedef GraphIncIterator InEdgeIt;
   7.198 +#endif
   7.199 +
   7.200 +      /// Iterator of edges outgoing from a node
   7.201 +#ifndef DOXYGEN
   7.202 +      typedef GraphIncIterator<UndirGraph, Edge, 'o'> OutEdgeIt;
   7.203 +#else
   7.204 +      typedef GraphIncIterator OutEdgeIt;
   7.205 +#endif
   7.206 +
   7.207 +      /// NodeMap template
   7.208 +#ifdef DOXYGEN
   7.209 +      typedef GraphMap NodeMap<T>;
   7.210 +#endif
   7.211 +
   7.212 +      /// UndirEdgeMap template
   7.213 +#ifdef DOXYGEN
   7.214 +      typedef GraphMap UndirEdgeMap<T>;
   7.215 +#endif
   7.216 +
   7.217 +      /// EdgeMap template
   7.218 +#ifdef DOXYGEN
   7.219 +      typedef GraphMap EdgeMap<T>;
   7.220 +#endif
   7.221 +
   7.222 +      template <typename T>
   7.223 +      class NodeMap : public GraphMap<UndirGraph, Node, T> {
   7.224 +	typedef GraphMap<UndirGraph, Node, T> Parent;
   7.225 +      public:
   7.226 +
   7.227 +	explicit NodeMap(const UndirGraph &g) : Parent(g) {}
   7.228 +	NodeMap(const UndirGraph &g, T t) : Parent(g, t) {}
   7.229 +      };
   7.230 +
   7.231 +      template <typename T>
   7.232 +      class UndirEdgeMap : public GraphMap<UndirGraph, UndirEdge, T> {
   7.233 +	typedef GraphMap<UndirGraph, UndirEdge, T> Parent;
   7.234 +      public:
   7.235 +
   7.236 +	explicit UndirEdgeMap(const UndirGraph &g) : Parent(g) {}
   7.237 +	UndirEdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
   7.238 +      };
   7.239 +
   7.240 +      template <typename T>
   7.241 +      class EdgeMap : public GraphMap<UndirGraph, Edge, T> {
   7.242 +	typedef GraphMap<UndirGraph, Edge, T> Parent;
   7.243 +      public:
   7.244 +
   7.245 +	explicit EdgeMap(const UndirGraph &g) : Parent(g) {}
   7.246 +	EdgeMap(const UndirGraph &g, T t) : Parent(g, t) {}
   7.247 +      };
   7.248 +
   7.249 +      /// Is the Edge oriented "forward"?
   7.250 +
   7.251 +      /// Returns whether the given directed edge is same orientation as
   7.252 +      /// the corresponding undirected edge.
   7.253 +      ///
   7.254 +      /// \todo "What does the direction of an undirected edge mean?"
   7.255 +      bool forward(Edge) const { return true; }
   7.256 +
   7.257 +      /// Opposite node on an edge
   7.258 +
   7.259 +      /// \return the opposite of the given Node on the given Edge
   7.260 +      ///
   7.261 +      /// \todo What should we do if given Node and Edge are not incident?
   7.262 +      Node oppositeNode(Node, UndirEdge) const { return INVALID; }
   7.263 +
   7.264 +      /// First node of the undirected edge.
   7.265 +
   7.266 +      /// \return the first node of the given UndirEdge.
   7.267 +      ///
   7.268 +      /// Naturally undirectected edges don't have direction and thus
   7.269 +      /// don't have source and target node. But we use these two methods
   7.270 +      /// to query the two endnodes of the edge. The direction of the edge
   7.271 +      /// which arises this way is called the inherent direction of the
   7.272 +      /// undirected edge, and is used to define the "forward" direction
   7.273 +      /// of the directed versions of the edges.
   7.274 +      /// \sa forward
   7.275 +      Node source(UndirEdge) const { return INVALID; }
   7.276 +
   7.277 +      /// Second node of the undirected edge.
   7.278 +      Node target(UndirEdge) const { return INVALID; }
   7.279 +
   7.280 +      /// Source node of the directed edge.
   7.281 +      Node source(Edge) const { return INVALID; }
   7.282 +
   7.283 +      /// Target node of the directed edge.
   7.284 +      Node target(Edge) const { return INVALID; }
   7.285 +
   7.286 +      /// First node of the graph
   7.287 +
   7.288 +      /// \note This method is part of so called \ref
   7.289 +      /// developpers_interface "Developpers' interface", so it shouldn't
   7.290 +      /// be used in an end-user program.
   7.291 +      void first(Node&) const {}
   7.292 +      /// Next node of the graph
   7.293 +
   7.294 +      /// \note This method is part of so called \ref
   7.295 +      /// developpers_interface "Developpers' interface", so it shouldn't
   7.296 +      /// be used in an end-user program.
   7.297 +      void next(Node&) const {}
   7.298 +
   7.299 +      /// First undirected edge of the graph
   7.300 +
   7.301 +      /// \note This method is part of so called \ref
   7.302 +      /// developpers_interface "Developpers' interface", so it shouldn't
   7.303 +      /// be used in an end-user program.
   7.304 +      void first(UndirEdge&) const {}
   7.305 +      /// Next undirected edge of the graph
   7.306 +
   7.307 +      /// \note This method is part of so called \ref
   7.308 +      /// developpers_interface "Developpers' interface", so it shouldn't
   7.309 +      /// be used in an end-user program.
   7.310 +      void next(UndirEdge&) const {}
   7.311 +
   7.312 +      /// First directed edge of the graph
   7.313 +
   7.314 +      /// \note This method is part of so called \ref
   7.315 +      /// developpers_interface "Developpers' interface", so it shouldn't
   7.316 +      /// be used in an end-user program.
   7.317 +      void first(Edge&) const {}
   7.318 +      /// Next directed edge of the graph
   7.319 +
   7.320 +      /// \note This method is part of so called \ref
   7.321 +      /// developpers_interface "Developpers' interface", so it shouldn't
   7.322 +      /// be used in an end-user program.
   7.323 +      void next(Edge&) const {}
   7.324 +
   7.325 +      /// First outgoing edge from a given node
   7.326 +
   7.327 +      /// \note This method is part of so called \ref
   7.328 +      /// developpers_interface "Developpers' interface", so it shouldn't
   7.329 +      /// be used in an end-user program.
   7.330 +      void firstOut(Edge&, Node) const {}
   7.331 +      /// Next outgoing edge to a node
   7.332 +
   7.333 +      /// \note This method is part of so called \ref
   7.334 +      /// developpers_interface "Developpers' interface", so it shouldn't
   7.335 +      /// be used in an end-user program.
   7.336 +      void nextOut(Edge&) const {}
   7.337 +
   7.338 +      /// First incoming edge to a given node
   7.339 +
   7.340 +      /// \note This method is part of so called \ref
   7.341 +      /// developpers_interface "Developpers' interface", so it shouldn't
   7.342 +      /// be used in an end-user program.
   7.343 +      void firstIn(Edge&, Node) const {}
   7.344 +      /// Next incoming edge to a node
   7.345 +
   7.346 +      /// \note This method is part of so called \ref
   7.347 +      /// developpers_interface "Developpers' interface", so it shouldn't
   7.348 +      /// be used in an end-user program.
   7.349 +      void nextIn(Edge&) const {}
   7.350 +
   7.351 +
   7.352        template <typename Graph>
   7.353        struct Constraints {
   7.354  	void constraints() {
   7.355 @@ -190,6 +472,8 @@
   7.356  
   7.357      };
   7.358  
   7.359 +    /// @}
   7.360 +
   7.361    }
   7.362  
   7.363  }

     8.1 --- a/src/lemon/iterable_graph_extender.h	Fri Dec 03 12:19:26 2004 +0000
     8.2 +++ b/src/lemon/iterable_graph_extender.h	Mon Dec 06 00:30:44 2004 +0000
     8.3 @@ -157,7 +157,7 @@
     8.4  
     8.5      };
     8.6  
     8.7 -    class UndirIncEdgeIt : public UndirEdge { 
     8.8 +    class IncEdgeIt : public UndirEdge { 
     8.9        const Graph* graph;
    8.10        bool forward;
    8.11        friend class IterableUndirGraphExtender;
    8.12 @@ -165,30 +165,30 @@
    8.13        friend class UndirGraphExtender;
    8.14      public:
    8.15  
    8.16 -      UndirIncEdgeIt() { }
    8.17 +      IncEdgeIt() { }
    8.18  
    8.19 -      UndirIncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { }
    8.20 +      IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { }
    8.21  
    8.22 -      explicit UndirIncEdgeIt(const Graph& _graph, const Node &n)
    8.23 +      explicit IncEdgeIt(const Graph& _graph, const Node &n)
    8.24  	: graph(&_graph)
    8.25        {
    8.26  	_graph._dirFirstOut(*this, n);
    8.27        }
    8.28  
    8.29        // FIXME: Do we need this type of constructor here?
    8.30 -      // UndirIncEdgeIt(const Graph& _graph, const Edge& e) : 
    8.31 +      // IncEdgeIt(const Graph& _graph, const Edge& e) : 
    8.32        //   UndirEdge(e), graph(&_graph), forward(_graph.forward(e)) { }
    8.33        // or
    8.34 -      // UndirIncEdgeIt(const Graph& _graph, const Node& n,
    8.35 +      // IncEdgeIt(const Graph& _graph, const Node& n,
    8.36        //    Const UndirEdge &e) ... ?
    8.37  
    8.38 -      UndirIncEdgeIt& operator++() {
    8.39 +      IncEdgeIt& operator++() {
    8.40  	graph->_dirNextOut(*this);
    8.41  	return *this; 
    8.42        }
    8.43      };
    8.44  
    8.45 -    Node source(const UndirIncEdgeIt &e) const {
    8.46 +    Node source(const IncEdgeIt &e) const {
    8.47        return _dirSource(e);
    8.48      }
    8.49  
    8.50 @@ -197,7 +197,7 @@
    8.51      using Parent::source;
    8.52  
    8.53      /// Target of the given Edge.
    8.54 -    Node target(const UndirIncEdgeIt &e) const {
    8.55 +    Node target(const IncEdgeIt &e) const {
    8.56        return _dirTarget(e);
    8.57      }
    8.58  

     9.1 --- a/src/lemon/undir_graph_extender.h	Fri Dec 03 12:19:26 2004 +0000
     9.2 +++ b/src/lemon/undir_graph_extender.h	Mon Dec 06 00:30:44 2004 +0000
     9.3 @@ -108,7 +108,7 @@
     9.4      /// concept. "What does the direction of an undirected edge mean?"
     9.5      bool forward(const Edge &e) const { return e.forward; }
     9.6  
     9.7 -    Node oppsiteNode(const Node &n, const Edge &e) const {
     9.8 +    Node oppositeNode(const Node &n, const UndirEdge &e) const {
     9.9        if( n == Parent::source(e))
    9.10  	return Parent::target(e);
    9.11        else if( n == Parent::target(e))

    10.1 --- a/src/test/undir_graph_test.cc	Fri Dec 03 12:19:26 2004 +0000
    10.2 +++ b/src/test/undir_graph_test.cc	Mon Dec 06 00:30:44 2004 +0000
    10.3 @@ -33,5 +33,7 @@
    10.4    checkConcept<UndirGraph, Graph>();
    10.5    checkConcept<ErasableUndirGraph, Graph>();
    10.6  
    10.7 +  checkConcept<UndirGraph, UndirGraph>();
    10.8 +
    10.9    return 0;
   10.10  }