# HG changeset patch
# User deba
# Date 1128518262 0
# Node ID 467d7927a901586de48fa9d1f11e81d390d9b193
# Parent  eb90e3d6bddc0299d3f171d7b79b5b952e37b512
findUndirEdge, ConUndirEdgeIt
some modification in the undir graph extenders

diff -r eb90e3d6bddc -r 467d7927a901 lemon/bits/iterable_graph_extender.h
--- a/lemon/bits/iterable_graph_extender.h	Wed Oct 05 13:15:47 2005 +0000
+++ b/lemon/bits/iterable_graph_extender.h	Wed Oct 05 13:17:42 2005 +0000
@@ -216,30 +216,25 @@
 
     class IncEdgeIt : public Parent::UndirEdge { 
       const Graph* graph;
-      bool forward;
+      bool direction;
       friend class IterableUndirGraphExtender;
-      template <typename G>
-      friend class UndirGraphExtender;
     public:
 
       IncEdgeIt() { }
 
-      IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { }
+      IncEdgeIt(Invalid i) : UndirEdge(i), direction(false) { }
 
-      IncEdgeIt(const Graph& _graph, const Node &n)
-	: graph(&_graph)
-      {
-	_graph._dirFirstOut(*this, n);
+      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
+	_graph.firstInc(*this, direction, n);
       }
 
       IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)
-	: graph(&_graph), UndirEdge(ue)
-      {
-	forward = (_graph.source(ue) == n);
+	: graph(&_graph), UndirEdge(ue) {
+	direction = (_graph.source(ue) == n);
       }
 
       IncEdgeIt& operator++() {
-	graph->_dirNextOut(*this);
+	graph->nextInc(*this, direction);
 	return *this; 
       }
     };
@@ -251,13 +246,13 @@
     ///
     /// Returns the base node of the iterator
     Node baseNode(const IncEdgeIt &e) const {
-      return _dirSource(e);
+      return e.direction ? source(e) : target(e);
     }
     /// Running node of the iterator
     ///
     /// Returns the running node of the iterator
     Node runningNode(const IncEdgeIt &e) const {
-      return _dirTarget(e);
+      return e.direction ? target(e) : source(e);
     }
 
     /// \brief The opposite node on the given undirected edge.
diff -r eb90e3d6bddc -r 467d7927a901 lemon/bits/undir_graph_extender.h
--- a/lemon/bits/undir_graph_extender.h	Wed Oct 05 13:15:47 2005 +0000
+++ b/lemon/bits/undir_graph_extender.h	Wed Oct 05 13:17:42 2005 +0000
@@ -71,18 +71,6 @@
       return Edge(e,!e.forward);
     }
 
-  protected:
-
-    template <typename E>
-    Node _dirSource(const E &e) const {
-      return e.forward ? Parent::source(e) : Parent::target(e);
-    }
-
-    template <typename E>
-    Node _dirTarget(const E &e) const {
-      return e.forward ? Parent::target(e) : Parent::source(e);
-    }
-
   public:
     /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
     /// or something???
@@ -90,7 +78,7 @@
 
     /// Source of the given Edge.
     Node source(const Edge &e) const {
-      return _dirSource(e);
+      return e.forward ? Parent::source(e) : Parent::target(e);
     }
 
     /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
@@ -99,7 +87,7 @@
 
     /// Target of the given Edge.
     Node target(const Edge &e) const {
-      return _dirTarget(e);
+      return e.forward ? Parent::target(e) : Parent::source(e);
     }
 
     Node oppositeNode(const Node &n, const UndirEdge &e) const {
@@ -154,11 +142,9 @@
       }
     }
 
-    
-  protected:
+  public:
 
-    template <typename E>
-    void _dirFirstOut(E &e, const Node &n) const {
+    void firstOut(Edge &e, const Node &n) const {
       Parent::firstIn(e,n);
       if( UndirEdge(e) != INVALID ) {
 	e.forward = false;
@@ -168,20 +154,7 @@
 	e.forward = true;
       }
     }
-    template <typename E>
-    void _dirFirstIn(E &e, const Node &n) const {
-      Parent::firstOut(e,n);
-      if( UndirEdge(e) != INVALID ) {
-	e.forward = false;
-      }
-      else {
-	Parent::firstIn(e,n);
-	e.forward = true;
-      }
-    }
-
-    template <typename E>
-    void _dirNextOut(E &e) const {
+    void nextOut(Edge &e) const {
       if( ! e.forward ) {
 	Node n = Parent::target(e);
 	Parent::nextIn(e);
@@ -194,8 +167,18 @@
 	Parent::nextOut(e);
       }
     }
-    template <typename E>
-    void _dirNextIn(E &e) const {
+
+    void firstIn(Edge &e, const Node &n) const {
+      Parent::firstOut(e,n);
+      if( UndirEdge(e) != INVALID ) {
+	e.forward = false;
+      }
+      else {
+	Parent::firstIn(e,n);
+	e.forward = true;
+      }
+    }
+    void nextIn(Edge &e) const {
       if( ! e.forward ) {
 	Node n = Parent::source(e);
 	Parent::nextOut(e);
@@ -209,20 +192,38 @@
       }
     }
 
-  public:
-
-    void firstOut(Edge &e, const Node &n) const {
-      _dirFirstOut(e, n);
+    void firstInc(UndirEdge &e, const Node &n) const {
+      Parent::firstOut(e, n);
+      if (e != INVALID) return;
+      Parent::firstIn(e, n);
     }
-    void firstIn(Edge &e, const Node &n) const {
-      _dirFirstIn(e, n);
+    void nextInc(UndirEdge &e, const Node &n) const {
+      if (Parent::source(e) == n) {
+	Parent::nextOut(e);
+	if (e != INVALID) return;
+	Parent::firstIn(e, n);
+      } else {
+	Parent::nextIn(e);
+      }
     }
 
-    void nextOut(Edge &e) const {
-      _dirNextOut(e);
+    void firstInc(UndirEdge &e, bool &d, const Node &n) const {
+      d = true;
+      Parent::firstOut(e, n);
+      if (e != INVALID) return;
+      d = false;
+      Parent::firstIn(e, n);
     }
-    void nextIn(Edge &e) const {
-      _dirNextIn(e);
+    void nextInc(UndirEdge &e, bool &d) const {
+      if (d) {
+	Node s = Parent::source(e);
+	Parent::nextOut(e);
+	if (e != INVALID) return;
+	d = false;
+	Parent::firstIn(e, s);
+      } else {
+	Parent::nextIn(e);
+      }
     }
 
     // Miscellaneous stuff:
@@ -262,10 +263,47 @@
     int edgeNum() const {
       return 2 * Parent::edgeNum();
     }
+
     int undirEdgeNum() const {
       return Parent::edgeNum();
     }
 
+    Edge findEdge(Node source, Node target, Edge prev) const {
+      if (prev == INVALID) {
+	UndirEdge edge = Parent::findEdge(source, target);
+	if (edge != INVALID) return direct(edge, true);
+	edge = Parent::findEdge(target, source);
+	if (edge != INVALID) return direct(edge, false);
+      } else if (direction(prev)) {
+	UndirEdge edge = Parent::findEdge(source, target, prev);
+	if (edge != INVALID) return direct(edge, true);
+	edge = Parent::findEdge(target, source);
+	if (edge != INVALID) return direct(edge, false);	
+      } else {
+	UndirEdge edge = Parent::findEdge(target, source, prev);
+	if (edge != INVALID) return direct(edge, false);	      
+      }
+      return INVALID;
+    }
+
+    UndirEdge findUndirEdge(Node source, Node target, UndirEdge prev) const {
+      if (prev == INVALID) {
+	UndirEdge edge = Parent::findEdge(source, target);
+	if (edge != INVALID) return edge;
+	edge = Parent::findEdge(target, source);
+	if (edge != INVALID) return edge;
+      } else if (Parent::source(prev) == source) {
+	UndirEdge edge = Parent::findEdge(source, target, prev);
+	if (edge != INVALID) return edge;
+	edge = Parent::findEdge(target, source);
+	if (edge != INVALID) return edge;	
+      } else {
+	UndirEdge edge = Parent::findEdge(target, source, prev);
+	if (edge != INVALID) return edge;	      
+      }
+      return INVALID;
+    }
+
   };
 
 }
diff -r eb90e3d6bddc -r 467d7927a901 lemon/graph_utils.h
--- a/lemon/graph_utils.h	Wed Oct 05 13:15:47 2005 +0000
+++ b/lemon/graph_utils.h	Wed Oct 05 13:17:42 2005 +0000
@@ -160,9 +160,9 @@
     return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
   }
 
-  /// \brief Function to count the number of the in-edges to node \c n.
+  /// \brief Function to count the number of the inc-edges to node \c n.
   ///
-  /// This function counts the number of the in-edges to node \c n
+  /// This function counts the number of the inc-edges to node \c n
   /// in the graph.  
   template <typename Graph>
   inline int countIncEdges(const Graph& _g,  const typename Graph::Node& _n) {
@@ -214,7 +214,6 @@
   /// \endcode
   // /// \todo We may want to use the "GraphBase" 
   // /// interface here...
-  // /// It would not work with the undirected graphs.
   template <typename Graph>
   inline typename Graph::Edge findEdge(const Graph &g,
 				       typename Graph::Node u, 
@@ -271,6 +270,110 @@
     const Graph& graph;
   };
 
+  template <typename Graph>
+  inline
+  typename enable_if<
+    typename Graph::FindEdgeTag, 
+    typename Graph::UndirEdge>::type 
+  _findUndirEdge(const Graph &g,
+	    typename Graph::Node u, typename Graph::Node v,
+	    typename Graph::UndirEdge prev = INVALID) {
+    return g.findUndirEdge(u, v, prev);
+  }
+
+  template <typename Graph>
+  inline typename Graph::UndirEdge 
+  _findUndirEdge(Wrap<Graph> w,
+	    typename Graph::Node u, 
+	    typename Graph::Node v,
+	    typename Graph::UndirEdge prev = INVALID) {
+    const Graph& g = w.value;
+    if (prev == INVALID) {
+      typename Graph::OutEdgeIt e(g, u);
+      while (e != INVALID && g.target(e) != v) ++e;
+      return e;
+    } else {
+      typename Graph::OutEdgeIt e(g, g.direct(prev, u)); ++e;
+      while (e != INVALID && g.target(e) != v) ++e;
+      return e;
+    }
+  }
+
+  /// \brief Finds an undir edge between two nodes of a graph.
+  ///
+  /// Finds an undir edge from node \c u to node \c v in graph \c g.
+  ///
+  /// If \c prev is \ref INVALID (this is the default value), then
+  /// it finds the first edge from \c u to \c v. Otherwise it looks for
+  /// the next edge from \c u to \c v after \c prev.
+  /// \return The found edge or \ref INVALID if there is no such an edge.
+  ///
+  /// Thus you can iterate through each edge from \c u to \c v as it follows.
+  /// \code
+  /// for(UndirEdge e = findUndirEdge(g,u,v); e != INVALID; 
+  ///     e = findUndirEdge(g,u,v,e)) {
+  ///   ...
+  /// }
+  /// \endcode
+  // /// \todo We may want to use the "GraphBase" 
+  // /// interface here...
+  template <typename Graph>
+  inline typename Graph::UndirEdge 
+  findUndirEdge(const Graph &g,
+		typename Graph::Node u, 
+		typename Graph::Node v,
+		typename Graph::UndirEdge prev = INVALID) {
+    return _findUndirEdge<Graph>(g, u, v, prev);
+  }
+
+  /// \brief Iterator for iterating on undir edges connected the same nodes.
+  ///
+  /// Iterator for iterating on undir edges connected the same nodes. It is 
+  /// higher level interface for the findUndirEdge() function. You can
+  /// use it the following way:
+  /// \code
+  /// for (ConUndirEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
+  ///   ...
+  /// }
+  /// \endcode
+  ///
+  /// \author Balazs Dezso 
+  template <typename _Graph>
+  class ConUndirEdgeIt : public _Graph::UndirEdge {
+  public:
+
+    typedef _Graph Graph;
+    typedef typename Graph::UndirEdge Parent;
+
+    typedef typename Graph::UndirEdge UndirEdge;
+    typedef typename Graph::Node Node;
+
+    /// \brief Constructor.
+    ///
+    /// Construct a new ConUndirEdgeIt iterating on the edges which
+    /// connects the \c u and \c v node.
+    ConUndirEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
+      Parent::operator=(findUndirEdge(graph, u, v));
+    }
+
+    /// \brief Constructor.
+    ///
+    /// Construct a new ConUndirEdgeIt which continues the iterating from 
+    /// the \c e edge.
+    ConUndirEdgeIt(const Graph& g, UndirEdge e) : Parent(e), graph(g) {}
+    
+    /// \brief Increment operator.
+    ///
+    /// It increments the iterator and gives back the next edge.
+    ConUndirEdgeIt& operator++() {
+      Parent::operator=(findUndirEdge(graph, graph.source(*this), 
+				 graph.target(*this), *this));
+      return *this;
+    }
+  private:
+    const Graph& graph;
+  };
+
   /// \brief Copy a map.
   ///
   /// This function copies the \c source map to the \c target map. It uses the
@@ -552,8 +655,6 @@
     typedef _Item Item;
     typedef _Item Key;
 
-    typedef True NeedCopy;
-
     /// \brief Constructor.
     ///
     /// Constructor for creating id map.
@@ -577,8 +678,6 @@
     class InverseMap {
     public:
 
-      typedef True NeedCopy;
-
       /// \brief Constructor.
       ///
       /// Constructor for creating an id-to-item map.
@@ -906,8 +1005,6 @@
   class SourceMap {
   public:
 
-    typedef True NeedCopy;
-
     typedef typename Graph::Node Value;
     typedef typename Graph::Edge Key;
 
@@ -947,8 +1044,6 @@
   class TargetMap {
   public:
 
-    typedef True NeedCopy;
-
     typedef typename Graph::Node Value;
     typedef typename Graph::Edge Key;
 
@@ -988,8 +1083,6 @@
   class ForwardMap {
   public:
 
-    typedef True NeedCopy;
-
     typedef typename Graph::Edge Value;
     typedef typename Graph::UndirEdge Key;
 
@@ -1028,7 +1121,6 @@
   template <typename Graph>
   class BackwardMap {
   public:
-    typedef True NeedCopy;
 
     typedef typename Graph::Edge Value;
     typedef typename Graph::UndirEdge Key;
@@ -1296,11 +1388,10 @@
   protected:
 
     static int index(int i, int j) {
-      int m = i > j ? i : j;
       if (i < j) {
-	return m * m + i;
+	return j * j + i;
       } else {
-	return m * m + m + j;
+	return i * i + i + j;
       }
     }