1.1 --- a/src/lemon/concept/graph_component.h	Sat Feb 19 21:11:20 2005 +0000
     1.2 +++ b/src/lemon/concept/graph_component.h	Sun Feb 20 01:02:07 2005 +0000
     1.3 @@ -625,11 +625,19 @@
     1.4  	  ++(++it1);
     1.5  	  Edge e = it1;
     1.6  	  e = it2;
     1.7 +
     1.8 +	  const_constraits();
     1.9  	}
    1.10  
    1.11 -	Edge& edge;
    1.12 -	Node& node;
    1.13 -	Graph& graph;
    1.14 +	void const_constraits() {
    1.15 +	  Node n = graph.baseNode(it);
    1.16 +	  n = graph.runningNode(it);
    1.17 +	}
    1.18 +
    1.19 +	Edge edge;
    1.20 +	Node node;
    1.21 +	Graph graph;
    1.22 +	_GraphIncIterator it;
    1.23        };
    1.24      };
    1.25  

     2.1 --- a/src/lemon/concept/undir_graph.h	Sat Feb 19 21:11:20 2005 +0000
     2.2 +++ b/src/lemon/concept/undir_graph.h	Sun Feb 20 01:02:07 2005 +0000
     2.3 @@ -36,8 +36,10 @@
     2.4  
     2.5      /// Skeleton class which describes an edge with direction in \ref
     2.6      /// UndirGraph "undirected graph".
     2.7 -    template <typename UndirEdge>
     2.8 -    class UndirGraphEdge : public UndirEdge {
     2.9 +    template <typename UndirGraph>
    2.10 +    class UndirGraphEdge : public UndirGraph::UndirEdge {
    2.11 +      typedef typename UndirGraph::UndirEdge UndirEdge;
    2.12 +      typedef typename UndirGraph::Node Node;
    2.13      public:
    2.14  
    2.15        /// \e
    2.16 @@ -49,14 +51,16 @@
    2.17        /// \e
    2.18        UndirGraphEdge(Invalid) {}
    2.19  
    2.20 -      /// \brief Constructs a directed version of an undirected edge
    2.21 +      /// \brief Directed edge from undirected edge and a source node.
    2.22        ///
    2.23 -      /// \param forward If \c true the direction of the contructed edge
    2.24 -      /// is the same as the inherent direction of the \c undir_edge; if
    2.25 -      /// \c false --- the opposite.
    2.26 -      UndirGraphEdge(UndirEdge undir_edge, bool forward) {
    2.27 +      /// Constructs a directed edge from undirected edge and a source node.
    2.28 +      ///
    2.29 +      /// \note You have to specify the graph for this constructor.
    2.30 +      UndirGraphEdge(const UndirGraph &g,
    2.31 +		     UndirEdge undir_edge, Node n) {
    2.32  	ignore_unused_variable_warning(undir_edge);
    2.33 -	ignore_unused_variable_warning(forward);
    2.34 +	ignore_unused_variable_warning(g);
    2.35 +	ignore_unused_variable_warning(n);
    2.36        }
    2.37  
    2.38        /// \e
    2.39 @@ -73,16 +77,20 @@
    2.40        template <typename Edge>
    2.41        struct Constraints {
    2.42  	void constraints() {
    2.43 +	  const_constraints();
    2.44 +	}
    2.45 +	void const_constraints() const {
    2.46  	  /// \bug This should be is_base_and_derived ...
    2.47  	  UndirEdge ue = e;
    2.48  	  ue = e;
    2.49 -	  Edge forward(ue, true);
    2.50 -	  Edge backward(ue, false);
    2.51  
    2.52 -	  ignore_unused_variable_warning(forward);
    2.53 -	  ignore_unused_variable_warning(backward);
    2.54 +	  Edge e_with_source(graph,ue,n);
    2.55 +	  ignore_unused_variable_warning(e_with_source);
    2.56  	}
    2.57  	Edge e;
    2.58 +	UndirEdge ue;
    2.59 +	UndirGraph graph;
    2.60 +	Node n;
    2.61        };
    2.62      };
    2.63      
    2.64 @@ -99,7 +107,7 @@
    2.65  	void constraints() {
    2.66  	  checkConcept<BaseIterableGraphComponent, Graph>();
    2.67  	  checkConcept<GraphItem<>, UndirEdge>();
    2.68 -	  checkConcept<UndirGraphEdge<UndirEdge>, Edge>();
    2.69 +	  checkConcept<UndirGraphEdge<Graph>, Edge>();
    2.70  
    2.71  	  graph.first(ue);
    2.72  	  graph.next(ue);
    2.73 @@ -234,7 +242,7 @@
    2.74  
    2.75        /// Type describing an UndirEdge with direction
    2.76  #ifndef DOXYGEN
    2.77 -      typedef UndirGraphEdge<UndirEdge> Edge;
    2.78 +      typedef UndirGraphEdge<UndirGraph> Edge;
    2.79  #else
    2.80        typedef UndirGraphEdge Edge;
    2.81  #endif
    2.82 @@ -430,6 +438,48 @@
    2.83        void nextIn(Edge&) const {}
    2.84  
    2.85  
    2.86 +      /// Base node of the iterator
    2.87 +      ///
    2.88 +      /// Returns the base node (the source in this case) of the iterator
    2.89 +      Node baseNode(OutEdgeIt e) const {
    2.90 +	return source(e);
    2.91 +      }
    2.92 +      /// Running node of the iterator
    2.93 +      ///
    2.94 +      /// Returns the running node (the target in this case) of the
    2.95 +      /// iterator
    2.96 +      Node runningNode(OutEdgeIt e) const {
    2.97 +	return target(e);
    2.98 +      }
    2.99 +
   2.100 +      /// Base node of the iterator
   2.101 +      ///
   2.102 +      /// Returns the base node (the target in this case) of the iterator
   2.103 +      Node baseNode(InEdgeIt e) const {
   2.104 +	return target(e);
   2.105 +      }
   2.106 +      /// Running node of the iterator
   2.107 +      ///
   2.108 +      /// Returns the running node (the source in this case) of the
   2.109 +      /// iterator
   2.110 +      Node runningNode(InEdgeIt e) const {
   2.111 +	return source(e);
   2.112 +      }
   2.113 +
   2.114 +      /// Base node of the iterator
   2.115 +      ///
   2.116 +      /// Returns the base node of the iterator
   2.117 +      Node baseNode(IncEdgeIt e) const {
   2.118 +	return INVALID;
   2.119 +      }
   2.120 +      /// Running node of the iterator
   2.121 +      ///
   2.122 +      /// Returns the running node of the iterator
   2.123 +      Node runningNode(IncEdgeIt e) const {
   2.124 +	return INVALID;
   2.125 +      }
   2.126 +
   2.127 +
   2.128        template <typename Graph>
   2.129        struct Constraints {
   2.130  	void constraints() {

     3.1 --- a/src/lemon/iterable_graph_extender.h	Sat Feb 19 21:11:20 2005 +0000
     3.2 +++ b/src/lemon/iterable_graph_extender.h	Sun Feb 20 01:02:07 2005 +0000
     3.3 @@ -110,6 +110,42 @@
     3.4  
     3.5      };
     3.6  
     3.7 +    /// Base node of the iterator
     3.8 +    ///
     3.9 +    /// Returns the base node (ie. the source in this case) of the iterator
    3.10 +    ///
    3.11 +    /// \todo Document in the concept!
    3.12 +    Node baseNode(const OutEdgeIt &e) const {
    3.13 +      return source(e);
    3.14 +    }
    3.15 +    /// Running node of the iterator
    3.16 +    ///
    3.17 +    /// Returns the running node (ie. the target in this case) of the
    3.18 +    /// iterator
    3.19 +    ///
    3.20 +    /// \todo Document in the concept!
    3.21 +    Node runningNode(const OutEdgeIt &e) const {
    3.22 +      return target(e);
    3.23 +    }
    3.24 +
    3.25 +    /// Base node of the iterator
    3.26 +    ///
    3.27 +    /// Returns the base node (ie. the target in this case) of the iterator
    3.28 +    ///
    3.29 +    /// \todo Document in the concept!
    3.30 +    Node baseNode(const InEdgeIt &e) const {
    3.31 +      return target(e);
    3.32 +    }
    3.33 +    /// Running node of the iterator
    3.34 +    ///
    3.35 +    /// Returns the running node (ie. the source in this case) of the
    3.36 +    /// iterator
    3.37 +    ///
    3.38 +    /// \todo Document in the concept!
    3.39 +    Node runningNode(const InEdgeIt &e) const {
    3.40 +      return source(e);
    3.41 +    }
    3.42 +
    3.43      using Parent::first;
    3.44  
    3.45    private:
    3.46 @@ -124,6 +160,11 @@
    3.47      void first(InEdgeIt &) const;
    3.48  
    3.49    };
    3.50 +
    3.51 +
    3.52 +
    3.53 +
    3.54 +
    3.55    
    3.56    template <typename _Base>
    3.57    class IterableUndirGraphExtender : public IterableGraphExtender<_Base> {
    3.58 @@ -169,18 +210,17 @@
    3.59  
    3.60        IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { }
    3.61  
    3.62 -      explicit IncEdgeIt(const Graph& _graph, const Node &n)
    3.63 +      IncEdgeIt(const Graph& _graph, const Node &n)
    3.64  	: graph(&_graph)
    3.65        {
    3.66  	_graph._dirFirstOut(*this, n);
    3.67        }
    3.68  
    3.69 -      // FIXME: Do we need this type of constructor here?
    3.70 -      // IncEdgeIt(const Graph& _graph, const Edge& e) : 
    3.71 -      //   UndirEdge(e), graph(&_graph), forward(_graph.forward(e)) { }
    3.72 -      // or
    3.73 -      // IncEdgeIt(const Graph& _graph, const Node& n,
    3.74 -      //    Const UndirEdge &e) ... ?
    3.75 +      IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)
    3.76 +	: graph(&_graph), UndirEdge(ue)
    3.77 +      {
    3.78 +	forward = (_graph.source(ue) == n);
    3.79 +      }
    3.80  
    3.81        IncEdgeIt& operator++() {
    3.82  	graph->_dirNextOut(*this);
    3.83 @@ -188,23 +228,22 @@
    3.84        }
    3.85      };
    3.86  
    3.87 -    Node source(const IncEdgeIt &e) const {
    3.88 +    using Parent::baseNode;
    3.89 +    using Parent::runningNode;
    3.90 +
    3.91 +    /// Base node of the iterator
    3.92 +    ///
    3.93 +    /// Returns the base node of the iterator
    3.94 +    Node baseNode(const IncEdgeIt &e) const {
    3.95        return _dirSource(e);
    3.96      }
    3.97 -
    3.98 -    /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
    3.99 -    /// or something???
   3.100 -    using Parent::source;
   3.101 -
   3.102 -    /// Target of the given Edge.
   3.103 -    Node target(const IncEdgeIt &e) const {
   3.104 +    /// Running node of the iterator
   3.105 +    ///
   3.106 +    /// Returns the running node of the iterator
   3.107 +    Node runningNode(const IncEdgeIt &e) const {
   3.108        return _dirTarget(e);
   3.109      }
   3.110  
   3.111 -    /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
   3.112 -    /// or something???
   3.113 -    using Parent::target;
   3.114 -
   3.115    };
   3.116  }
   3.117  

     4.1 --- a/src/lemon/max_matching.h	Sat Feb 19 21:11:20 2005 +0000
     4.2 +++ b/src/lemon/max_matching.h	Sun Feb 20 01:02:07 2005 +0000
     4.3 @@ -180,7 +180,7 @@
     4.4  	if ( todo[v] && _mate[v]!=INVALID ) {
     4.5  	  Node u=_mate[v];
     4.6  	  for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
     4.7 -	    if ( g.target(e) == u ) {
     4.8 +	    if ( g.runningNode(e) == u ) {
     4.9  	      map.set(u,e);
    4.10  	      map.set(v,e);
    4.11  	      todo.set(u,false);
    4.12 @@ -227,7 +227,7 @@
    4.13  	if ( todo[v] && _mate[v]!=INVALID ) {
    4.14  	  Node u=_mate[v];
    4.15  	  for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
    4.16 -	    if ( g.target(e) == u ) {
    4.17 +	    if ( g.runningNode(e) == u ) {
    4.18  	      map.set(e,true);
    4.19  	      todo.set(u,false);
    4.20  	      todo.set(v,false);
    4.21 @@ -332,7 +332,7 @@
    4.22        R.pop();
    4.23  	
    4.24        for( IncEdgeIt e(g,x); e!=INVALID ; ++e ) {
    4.25 -	Node y=g.target(e);
    4.26 +	Node y=g.runningNode(e);
    4.27  
    4.28  	if ( position[y] == D && blossom.find(x) != blossom.find(y) ) { 
    4.29  	  //x and y must be in the same tree
    4.30 @@ -388,7 +388,7 @@
    4.31        Q.pop();
    4.32  	
    4.33        for( IncEdgeIt e(g,x); e!=INVALID; ++e ) {
    4.34 -	Node y=g.target(e);
    4.35 +	Node y=g.runningNode(e);
    4.36  	      
    4.37  	switch ( position[y] ) {
    4.38  	case D:          //x and y must be in the same tree
    4.39 @@ -453,7 +453,7 @@
    4.40      for(NodeIt v(g); v!=INVALID; ++v)
    4.41        if ( _mate[v]==INVALID ) {
    4.42  	for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) {
    4.43 -	  Node y=g.target(e);
    4.44 +	  Node y=g.runningNode(e);
    4.45  	  if ( _mate[y]==INVALID && y!=v ) {
    4.46  	    _mate.set(v,y);
    4.47  	    _mate.set(y,v);
    4.48 @@ -484,7 +484,7 @@
    4.49    bool MaxMatching<Graph>::noShrinkStep(Node x, typename Graph::NodeMap<Node>& ear,  
    4.50  					UFE& blossom, UFE& tree, std::queue<Node>& Q) {
    4.51      for( IncEdgeIt e(g,x); e!= INVALID; ++e ) {
    4.52 -      Node y=g.target(e);
    4.53 +      Node y=g.runningNode(e);
    4.54  	
    4.55        if ( position[y]==C ) {
    4.56  	if ( _mate[y]!=INVALID ) {       //grow

     5.1 --- a/src/lemon/undir_graph_extender.h	Sat Feb 19 21:11:20 2005 +0000
     5.2 +++ b/src/lemon/undir_graph_extender.h	Sun Feb 20 01:02:07 2005 +0000
     5.3 @@ -44,9 +44,22 @@
     5.4  
     5.5      public:
     5.6        Edge() {}
     5.7 -      /// Construct a direct edge from undirect edge and a direction.
     5.8 +
     5.9 +      /// \brief Directed edge from undirected edge and a direction.
    5.10 +      ///
    5.11 +      /// This constructor is not a part of the concept interface of
    5.12 +      /// undirected graph, so please avoid using it if possible!
    5.13        Edge(const UndirEdge &ue, bool _forward) :
    5.14 -	UndirEdge(ue), forward(_forward) {}
    5.15 +        UndirEdge(ue), forward(_forward) {}
    5.16 +
    5.17 +      /// \brief Directed edge from undirected edge and a source node.
    5.18 +      ///
    5.19 +      /// Constructs a directed edge from undirected edge and a source node.
    5.20 +      ///
    5.21 +      /// \note You have to specify the graph for this constructor.
    5.22 +      Edge(const Graph &g, const UndirEdge &ue, const Node &n) :
    5.23 +	UndirEdge(ue) { forward = (g.source(ue) == n); }
    5.24 +
    5.25        /// Invalid edge constructor
    5.26        Edge(Invalid i) : UndirEdge(i), forward(true) {}
    5.27  
    5.28 @@ -63,9 +76,9 @@
    5.29      };
    5.30  
    5.31  
    5.32 -    /// \brief Returns the Edge of opposite direction.
    5.33 +    /// \brief Edge of opposite direction.
    5.34      ///
    5.35 -    /// \bug Is this a good name for this? Or "reverse" is better?
    5.36 +    /// Returns the Edge of opposite direction.
    5.37      Edge opposite(const Edge &e) const {
    5.38        return Edge(e,!e.forward);
    5.39      }
    5.40 @@ -117,6 +130,17 @@
    5.41  	return INVALID;
    5.42      }
    5.43  
    5.44 +    /// Directed edge from an undirected edge and a source node.
    5.45 +    ///
    5.46 +    /// Returns a (directed) Edge corresponding to the specified UndirEdge
    5.47 +    /// and source Node.
    5.48 +    ///
    5.49 +    ///\todo Do we need this?
    5.50 +    ///
    5.51 +    ///\todo Better name...
    5.52 +    Edge edgeWithSource(const UndirEdge &ue, const Node &s) const {
    5.53 +      return Edge(*this, eu, s);
    5.54 +    }
    5.55  
    5.56      using Parent::first;
    5.57      void first(Edge &e) const {

     6.1 --- a/src/test/max_matching_test.cc	Sat Feb 19 21:11:20 2005 +0000
     6.2 +++ b/src/test/max_matching_test.cc	Sun Feb 20 01:02:07 2005 +0000
     6.3 @@ -159,7 +159,7 @@
     6.4  	Node w=Q.front();	
     6.5  	Q.pop();
     6.6  	for(IncEdgeIt e(g,w); e!=INVALID; ++e) {
     6.7 -	  Node u=g.target(e);
     6.8 +	  Node u=g.runningNode(e);
     6.9  	  if ( pos[u]==max_matching.D && todo[u] ) {
    6.10  	    ++comp_size;
    6.11  	    Q.push(u);