1.1 --- a/src/lemon/concept/graph_component.h	Mon Nov 22 17:50:26 2004 +0000
     1.2 +++ b/src/lemon/concept/graph_component.h	Thu Nov 25 14:48:24 2004 +0000
     1.3 @@ -505,62 +505,66 @@
     1.4      /// base class, the _selector is a additional template parameter. For 
     1.5      /// InEdgeIt you should instantiate it with character 'i' and for 
     1.6      /// OutEdgeIt with 'o'.
     1.7 -    /// \todo check the name of the concept GraphIncEdgeIterator
     1.8 -    template <typename _Graph, char _selector>
     1.9 -    class GraphIncEdgeIterator : public _Graph::Edge {
    1.10 +    /// \todo Is this a good name for this concept?
    1.11 +    template <typename Graph,
    1.12 +	      typename Edge = typename Graph::Edge,
    1.13 +	      char _selector = '0'>
    1.14 +    class GraphIncIterator : public Edge {
    1.15      public:
    1.16        /// Default constructor.
    1.17        
    1.18        /// @warning The default constructor sets the iterator
    1.19        /// to an undefined value.
    1.20 -      GraphIncEdgeIterator() {}
    1.21 +      GraphIncIterator() {}
    1.22        /// Copy constructor.
    1.23        
    1.24        /// Copy constructor.
    1.25        ///
    1.26 -      GraphIncEdgeIterator(GraphIncEdgeIterator const&) {}
    1.27 +      GraphIncIterator(GraphIncIterator const&) {}
    1.28        /// Sets the iterator to the first edge incoming into or outgoing from the node.
    1.29        
    1.30        /// Sets the iterator to the first edge incoming into or outgoing from the node.
    1.31        ///
    1.32 -      explicit GraphIncEdgeIterator(const _Graph&, const typename _Graph::Node&) {}
    1.33 +      explicit GraphIncIterator(const Graph&, const typename Graph::Node&) {}
    1.34        /// Invalid constructor \& conversion.
    1.35  
    1.36        /// This constructor initializes the item to be invalid.
    1.37        /// \sa Invalid for more details.
    1.38 -      GraphIncEdgeIterator(Invalid) {}
    1.39 +      GraphIncIterator(Invalid) {}
    1.40        /// Assign operator for nodes.
    1.41  
    1.42        /// The nodes are assignable. 
    1.43        ///
    1.44 -      GraphIncEdgeIterator& operator=(GraphIncEdgeIterator const&) { return *this; }      
    1.45 +      GraphIncIterator& operator=(GraphIncIterator const&) { return *this; }      
    1.46        /// Next edge.
    1.47  
    1.48        /// Assign the iterator to the next node.
    1.49        ///
    1.50 -      GraphIncEdgeIterator& operator++() { return *this; }
    1.51 +      GraphIncIterator& operator++() { return *this; }
    1.52 +
    1.53        //	Node operator*() const { return INVALID; }
    1.54 +
    1.55        /// Equality operator
    1.56  
    1.57        /// Two iterators are equal if and only if they point to the
    1.58        /// same object or both are invalid.
    1.59 -      bool operator==(const GraphIncEdgeIterator&) const { return true;}
    1.60 +      bool operator==(const GraphIncIterator&) const { return true;}
    1.61 +
    1.62        /// Inequality operator
    1.63  	
    1.64        /// \sa operator==(Node n)
    1.65        ///
    1.66 -      bool operator!=(const GraphIncEdgeIterator&) const { return true;}
    1.67 +      bool operator!=(const GraphIncIterator&) const { return true;}
    1.68  
    1.69 -      template <typename _GraphIncEdgeIterator>
    1.70 +      template <typename _GraphIncIterator>
    1.71        struct Constraints {
    1.72 -	typedef typename _Graph::Node Node;
    1.73 -	typedef typename _Graph::Edge Edge;
    1.74 +	typedef typename Graph::Node Node;
    1.75  	void constraints() {
    1.76 -	  checkConcept<GraphItem<'e'>, _GraphIncEdgeIterator>();
    1.77 -	  _GraphIncEdgeIterator it1(graph, node);
    1.78 +	  checkConcept<GraphItem<'e'>, _GraphIncIterator>();
    1.79 +	  _GraphIncIterator it1(graph, node);
    1.80  	  /// \todo Do we need OutEdgeIt(Edge) kind of constructor?
    1.81 -	  //	_GraphIncEdgeIterator it2(edge);
    1.82 -	  _GraphIncEdgeIterator it2;
    1.83 +	  //	_GraphIncIterator it2(edge);
    1.84 +	  _GraphIncIterator it2;
    1.85  
    1.86  	  it2 = ++it1;
    1.87  	  ++it2 = it1;
    1.88 @@ -571,9 +575,11 @@
    1.89  
    1.90  	Edge& edge;
    1.91  	Node& node;
    1.92 -	_Graph& graph;
    1.93 +	Graph& graph;
    1.94        };
    1.95      };
    1.96 +
    1.97 +
    1.98      /// An empty iterable base graph class.
    1.99    
   1.100      /// This class provides beside the core graph features
   1.101 @@ -602,12 +608,12 @@
   1.102  
   1.103        /// This iterator goes trough the \e inccoming edges of a certain node
   1.104        /// of a graph.
   1.105 -      typedef GraphIncEdgeIterator<Graph, 'i'> InEdgeIt;
   1.106 +      typedef GraphIncIterator<Graph, Edge, 'i'> InEdgeIt;
   1.107        /// This iterator goes trough the outgoing edges of a node.
   1.108  
   1.109        /// This iterator goes trough the \e outgoing edges of a certain node
   1.110        /// of a graph.
   1.111 -      typedef GraphIncEdgeIterator<Graph, 'o'> OutEdgeIt;
   1.112 +      typedef GraphIncIterator<Graph, Edge, 'o'> OutEdgeIt;
   1.113      };
   1.114      
   1.115      template <typename _Graph> 
   1.116 @@ -617,8 +623,8 @@
   1.117  
   1.118  	checkConcept<GraphIterator<_Graph, typename _Graph::Edge>, typename _Graph::EdgeIt >();
   1.119  	checkConcept<GraphIterator<_Graph, typename _Graph::Node>, typename _Graph::NodeIt >();
   1.120 -	checkConcept<GraphIncEdgeIterator<_Graph, 'i'>, typename _Graph::InEdgeIt >();
   1.121 -	checkConcept<GraphIncEdgeIterator<_Graph, 'o'>, typename _Graph::OutEdgeIt >();
   1.122 +	checkConcept<GraphIncIterator<_Graph>, typename _Graph::InEdgeIt >();
   1.123 +	checkConcept<GraphIncIterator<_Graph>, typename _Graph::OutEdgeIt >();
   1.124        }
   1.125      };
   1.126  

     2.1 --- a/src/lemon/concept/undir_graph.h	Mon Nov 22 17:50:26 2004 +0000
     2.2 +++ b/src/lemon/concept/undir_graph.h	Thu Nov 25 14:48:24 2004 +0000
     2.3 @@ -67,8 +67,13 @@
     2.4  
     2.5  	typedef typename Graph::UndirEdge UndirEdge;
     2.6  	typedef typename Graph::UndirEdgeIt UndirEdgeIt;
     2.7 +	typedef typename Graph::UndirIncEdgeIt UndirIncEdgeIt;
     2.8  
     2.9  	checkConcept< GraphIterator<Graph, UndirEdge>, UndirEdgeIt >();
    2.10 +
    2.11 +	checkConcept<
    2.12 +	  GraphIncIterator<Graph, UndirEdge>,
    2.13 +	  UndirIncEdgeIt >();
    2.14        }
    2.15      };
    2.16  

     3.1 --- a/src/lemon/iterable_graph_extender.h	Mon Nov 22 17:50:26 2004 +0000
     3.2 +++ b/src/lemon/iterable_graph_extender.h	Thu Nov 25 14:48:24 2004 +0000
     3.3 @@ -131,6 +131,7 @@
     3.4  
     3.5      typedef IterableGraphExtender<_Base> Parent;
     3.6      typedef IterableUndirGraphExtender<_Base> Graph;
     3.7 +    typedef typename Parent::Node Node;
     3.8  
     3.9      typedef typename Parent::UndirEdge UndirEdge;
    3.10  
    3.11 @@ -156,6 +157,50 @@
    3.12  
    3.13      };
    3.14  
    3.15 +    class UndirIncEdgeIt : public UndirEdge { 
    3.16 +      const Graph* graph;
    3.17 +      bool forward;
    3.18 +      friend class IterableUndirGraphExtender;
    3.19 +      template <typename G>
    3.20 +      friend class UndirGraphExtender;
    3.21 +    public:
    3.22 +
    3.23 +      UndirIncEdgeIt() { }
    3.24 +
    3.25 +      UndirIncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { }
    3.26 +
    3.27 +      explicit UndirIncEdgeIt(const Graph& _graph, const Node &n)
    3.28 +	: graph(&_graph)
    3.29 +      {
    3.30 +	_graph._dirFirstOut(*this, n);
    3.31 +      }
    3.32 +
    3.33 +      // FIXME: Do we need this type of constructor here?
    3.34 +      // UndirIncEdgeIt(const Graph& _graph, const UndirEdge& e) : 
    3.35 +      //   UndirEdge(e), graph(&_graph) { }
    3.36 +
    3.37 +      UndirIncEdgeIt& operator++() {
    3.38 +	graph->_dirNextOut(*this);
    3.39 +	return *this; 
    3.40 +      }
    3.41 +    };
    3.42 +
    3.43 +    Node source(const UndirIncEdgeIt &e) const {
    3.44 +      return _dirSource(e);
    3.45 +    }
    3.46 +
    3.47 +    /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
    3.48 +    /// or something???
    3.49 +    using Parent::source;
    3.50 +
    3.51 +    /// Target of the given Edge.
    3.52 +    Node target(const UndirIncEdgeIt &e) const {
    3.53 +      return _dirTarget(e);
    3.54 +    }
    3.55 +
    3.56 +    /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
    3.57 +    /// or something???
    3.58 +    using Parent::target;
    3.59  
    3.60    };
    3.61  }

     4.1 --- a/src/lemon/undir_graph_extender.h	Mon Nov 22 17:50:26 2004 +0000
     4.2 +++ b/src/lemon/undir_graph_extender.h	Thu Nov 25 14:48:24 2004 +0000
     4.3 @@ -70,24 +70,37 @@
     4.4        return Edge(e,!e.forward);
     4.5      }
     4.6  
     4.7 -    /// Source of the given Edge.
     4.8 -    Node source(const Edge &e) const {
     4.9 +  protected:
    4.10 +
    4.11 +    template <typename E>
    4.12 +    Node _dirSource(const E &e) const {
    4.13        return e.forward ? Parent::source(e) : Parent::target(e);
    4.14      }
    4.15  
    4.16 +    template <typename E>
    4.17 +    Node _dirTarget(const E &e) const {
    4.18 +      return e.forward ? Parent::target(e) : Parent::source(e);
    4.19 +    }
    4.20 +
    4.21 +  public:
    4.22      /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
    4.23      /// or something???
    4.24      using Parent::source;
    4.25  
    4.26 -    /// Target of the given Edge.
    4.27 -    Node target(const Edge &e) const {
    4.28 -      return e.forward ? Parent::target(e) : Parent::source(e);
    4.29 +    /// Source of the given Edge.
    4.30 +    Node source(const Edge &e) const {
    4.31 +      return _dirSource(e);
    4.32      }
    4.33  
    4.34      /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
    4.35      /// or something???
    4.36      using Parent::target;
    4.37  
    4.38 +    /// Target of the given Edge.
    4.39 +    Node target(const Edge &e) const {
    4.40 +      return _dirTarget(e);
    4.41 +    }
    4.42 +
    4.43      /// Returns whether the given directed edge is same orientation as the
    4.44      /// corresponding undirected edge.
    4.45      ///
    4.46 @@ -122,7 +135,11 @@
    4.47        }
    4.48      }
    4.49  
    4.50 -    void firstOut(Edge &e, const Node &n) const {
    4.51 +    
    4.52 +  protected:
    4.53 +
    4.54 +    template <typename E>
    4.55 +    void _dirFirstOut(E &e, const Node &n) const {
    4.56        Parent::firstOut(e,n);
    4.57        if( UndirEdge(e) != INVALID ) {
    4.58  	e.forward = true;
    4.59 @@ -132,7 +149,8 @@
    4.60  	e.forward = false;
    4.61        }
    4.62      }
    4.63 -    void firstIn(Edge &e, const Node &n) const {
    4.64 +    template <typename E>
    4.65 +    void _dirFirstIn(E &e, const Node &n) const {
    4.66        Parent::firstIn(e,n);
    4.67        if( UndirEdge(e) != INVALID ) {
    4.68  	e.forward = true;
    4.69 @@ -143,7 +161,8 @@
    4.70        }
    4.71      }
    4.72  
    4.73 -    void nextOut(Edge &e) const {
    4.74 +    template <typename E>
    4.75 +    void _dirNextOut(E &e) const {
    4.76        if( e.forward ) {
    4.77  	Parent::nextOut(e);
    4.78  	if( UndirEdge(e) == INVALID ) {
    4.79 @@ -155,7 +174,8 @@
    4.80  	Parent::nextIn(e);
    4.81        }
    4.82      }
    4.83 -    void nextIn(Edge &e) const {
    4.84 +    template <typename E>
    4.85 +    void _dirNextIn(E &e) const {
    4.86        if( e.forward ) {
    4.87  	Parent::nextIn(e);
    4.88  	if( UndirEdge(e) == INVALID ) {
    4.89 @@ -168,21 +188,52 @@
    4.90        }
    4.91      }
    4.92  
    4.93 +  public:
    4.94 +
    4.95 +    void firstOut(Edge &e, const Node &n) const {
    4.96 +      _dirFirstOut(e, n);
    4.97 +    }
    4.98 +    void firstIn(Edge &e, const Node &n) const {
    4.99 +      _dirFirstIn(e, n);
   4.100 +    }
   4.101 +
   4.102 +    void nextOut(Edge &e) const {
   4.103 +      _dirNextOut(e);
   4.104 +    }
   4.105 +    void nextIn(Edge &e) const {
   4.106 +      _dirNextIn(e);
   4.107 +    }
   4.108 +
   4.109      // Miscellaneous stuff:
   4.110  
   4.111      /// \todo these methods (id, maxEdgeId) should be moved into separate
   4.112      /// Extender
   4.113  
   4.114 -    using Parent::id;
   4.115 +    // using Parent::id;
   4.116 +    // Using "using" is not a good idea, cause it could be that there is
   4.117 +    // no "id" in Parent...
   4.118 +
   4.119 +    int id(const Node &n) const {
   4.120 +      return Parent::id(n);
   4.121 +    }
   4.122 +
   4.123 +    int id(const UndirEdge &e) const {
   4.124 +      return Parent::id(e);
   4.125 +    }
   4.126  
   4.127      int id(const Edge &e) const {
   4.128        return 2 * Parent::id(e) + int(e.forward);
   4.129      }
   4.130  
   4.131 -    int maxId(Edge = INVALID) const {
   4.132 +
   4.133 +    int maxId(Node n) const {
   4.134 +      return Parent::maxId(Node());
   4.135 +    }
   4.136 +
   4.137 +    int maxId(Edge) const {
   4.138        return 2 * Parent::maxId(typename Parent::Edge()) + 1;
   4.139      }
   4.140 -    int maxId(UndirEdge = INVALID) const {
   4.141 +    int maxId(UndirEdge) const {
   4.142        return Parent::maxId(typename Parent::Edge());
   4.143      }
   4.144