# HG changeset patch
# User deba
# Date 1143707921 0
# Node ID 332245399dc65dd4c46d4c5b37c578e93764e074
# Parent  e70c1f6849bcbb693f2d63fa2e3ddafc44f002c9
Rewritten countItems and findEdges

diff -r e70c1f6849bc -r 332245399dc6 lemon/graph_utils.h
--- a/lemon/graph_utils.h	Mon Mar 27 16:25:14 2006 +0000
+++ b/lemon/graph_utils.h	Thu Mar 30 08:38:41 2006 +0000
@@ -102,8 +102,9 @@
   /// The complexity of the function is O(n) because
   /// it iterates on all of the items.
 
-  template <typename Graph, typename ItemIt>
+  template <typename Graph, typename Item>
   inline int countItems(const Graph& g) {
+    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
     int num = 0;
     for (ItemIt it(g); it != INVALID; ++it) {
       ++num;
@@ -113,15 +114,24 @@
 
   // Node counting:
 
-  template <typename Graph>
-  inline typename enable_if<typename Graph::NodeNumTag, int>::type
-  _countNodes(const Graph &g) {
-    return g.nodeNum();
-  }
+  namespace _graph_utils_bits {
+    
+    template <typename Graph, typename Enable = void>
+    struct CountNodesSelector {
+      static int count(const Graph &g) {
+        return countItems<Graph, typename Graph::Node>(g);
+      }
+    };
 
-  template <typename Graph>
-  inline int _countNodes(Wrap<Graph> w) {
-    return countItems<Graph, typename Graph::NodeIt>(w.value);
+    template <typename Graph>
+    struct CountNodesSelector<
+      Graph, typename 
+      enable_if<typename Graph::NodeNumTag, void>::type> 
+    {
+      static int count(const Graph &g) {
+        return g.nodeNum();
+      }
+    };    
   }
 
   /// \brief Function to count the nodes in the graph.
@@ -134,20 +144,30 @@
 
   template <typename Graph>
   inline int countNodes(const Graph& g) {
-    return _countNodes<Graph>(g);
+    return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
   }
 
+
   // Edge counting:
 
-  template <typename Graph>
-  inline typename enable_if<typename Graph::EdgeNumTag, int>::type
-  _countEdges(const Graph &g) {
-    return g.edgeNum();
-  }
+  namespace _graph_utils_bits {
+    
+    template <typename Graph, typename Enable = void>
+    struct CountEdgesSelector {
+      static int count(const Graph &g) {
+        return countItems<Graph, typename Graph::Edge>(g);
+      }
+    };
 
-  template <typename Graph>
-  inline int _countEdges(Wrap<Graph> w) {
-    return countItems<Graph, typename Graph::EdgeIt>(w.value);
+    template <typename Graph>
+    struct CountEdgesSelector<
+      Graph, 
+      typename enable_if<typename Graph::EdgeNumTag, void>::type> 
+    {
+      static int count(const Graph &g) {
+        return g.edgeNum();
+      }
+    };    
   }
 
   /// \brief Function to count the edges in the graph.
@@ -158,21 +178,28 @@
 
   template <typename Graph>
   inline int countEdges(const Graph& g) {
-    return _countEdges<Graph>(g);
+    return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
   }
 
   // Undirected edge counting:
+  namespace _graph_utils_bits {
+    
+    template <typename Graph, typename Enable = void>
+    struct CountUEdgesSelector {
+      static int count(const Graph &g) {
+        return countItems<Graph, typename Graph::UEdge>(g);
+      }
+    };
 
-  template <typename Graph>
-  inline
-  typename enable_if<typename Graph::EdgeNumTag, int>::type
-  _countUEdges(const Graph &g) {
-    return g.uEdgeNum();
-  }
-
-  template <typename Graph>
-  inline int _countUEdges(Wrap<Graph> w) {
-    return countItems<Graph, typename Graph::UEdgeIt>(w.value);
+    template <typename Graph>
+    struct CountUEdgesSelector<
+      Graph, 
+      typename enable_if<typename Graph::EdgeNumTag, void>::type> 
+    {
+      static int count(const Graph &g) {
+        return g.uEdgeNum();
+      }
+    };    
   }
 
   /// \brief Function to count the undirected edges in the graph.
@@ -183,11 +210,11 @@
 
   template <typename Graph>
   inline int countUEdges(const Graph& g) {
-    return _countUEdges<Graph>(g);
+    return _graph_utils_bits::CountUEdgesSelector<Graph>::count(g);
+
   }
 
 
-
   template <typename Graph, typename DegIt>
   inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
     int num = 0;
@@ -224,32 +251,36 @@
     return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
   }
 
+  namespace _graph_utils_bits {
+    
+    template <typename Graph, typename Enable = void>
+    struct FindEdgeSelector {
+      typedef typename Graph::Node Node;
+      typedef typename Graph::Edge Edge;
+      static Edge find(const Graph &g, Node u, Node v, Edge e) {
+        if (e == INVALID) {
+          g.firstOut(e, u);
+        } else {
+          g.nextOut(e);
+        }
+        while (e != INVALID && g.target(e) != v) {
+          g.nextOut(e);
+        }
+        return e;
+      }
+    };
 
-  template <typename Graph>
-  inline
-  typename enable_if<typename Graph::FindEdgeTag, typename Graph::Edge>::type 
-  _findEdge(const Graph &g,
-	    typename Graph::Node u, typename Graph::Node v,
-	    typename Graph::Edge prev = INVALID) {
-    return g.findEdge(u, v, prev);
-  }
-
-  template <typename Graph>
-  inline typename Graph::Edge 
-  _findEdge(Wrap<Graph> w,
-	    typename Graph::Node u, 
-	    typename Graph::Node v,
-	    typename Graph::Edge 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, prev); ++e;
-      while (e != INVALID && g.target(e) != v) ++e;
-      return e;
-    }
+    template <typename Graph>
+    struct FindEdgeSelector<
+      Graph, 
+      typename enable_if<typename Graph::FindEdgeTag, void>::type> 
+    {
+      typedef typename Graph::Node Node;
+      typedef typename Graph::Edge Edge;
+      static Edge find(const Graph &g, Node u, Node v, Edge prev) {
+        return g.findEdge(u, v, prev);
+      }
+    };    
   }
 
   /// \brief Finds an edge between two nodes of a graph.
@@ -267,14 +298,12 @@
   ///   ...
   /// }
   ///\endcode
-  // /// \todo We may want to use the "GraphBase" 
-  // /// interface here...
   template <typename Graph>
   inline typename Graph::Edge findEdge(const Graph &g,
 				       typename Graph::Node u, 
 				       typename Graph::Node v,
 				       typename Graph::Edge prev = INVALID) {
-    return _findEdge<Graph>(g, u, v, prev);
+    return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, prev);
   }
 
   /// \brief Iterator for iterating on edges connected the same nodes.
@@ -325,38 +354,57 @@
     const Graph& graph;
   };
 
-  template <typename Graph>
-  inline
-  typename enable_if<
-    typename Graph::FindEdgeTag, 
-    typename Graph::UEdge>::type 
-  _findUEdge(const Graph &g,
-	    typename Graph::Node u, typename Graph::Node v,
-	    typename Graph::UEdge prev = INVALID) {
-    return g.findUEdge(u, v, prev);
-  }
+  namespace _graph_utils_bits {
+    
+    template <typename Graph, typename Enable = void>
+    struct FindUEdgeSelector {
+      typedef typename Graph::Node Node;
+      typedef typename Graph::UEdge UEdge;
+      static UEdge find(const Graph &g, Node u, Node v, UEdge e) {
+        bool b;
+        if (u != v) {
+          if (e == INVALID) {
+            g.firstInc(e, u, b);
+          } else {
+            b = g.source(e) == u;
+            g.nextInc(e, b);
+          }
+          while (e != INVALID && g.target(e) != v) {
+            g.nextInc(e, b);
+          }
+        } else {
+          if (e == INVALID) {
+            g.firstInc(e, u, b);
+          } else {
+            b = true;
+            g.nextInc(e, b);
+          }
+          while (e != INVALID && (!b || g.target(e) != v)) {
+            g.nextInc(e, b);
+          }
+        }
+        return e;
+      }
+    };
 
-  template <typename Graph>
-  inline typename Graph::UEdge 
-  _findUEdge(Wrap<Graph> w,
-	    typename Graph::Node u, 
-	    typename Graph::Node v,
-	    typename Graph::UEdge 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;
-    }
+    template <typename Graph>
+    struct FindUEdgeSelector<
+      Graph, 
+      typename enable_if<typename Graph::FindEdgeTag, void>::type> 
+    {
+      typedef typename Graph::Node Node;
+      typedef typename Graph::UEdge UEdge;
+      static UEdge find(const Graph &g, Node u, Node v, UEdge prev) {
+        return g.findUEdge(u, v, prev);
+      }
+    };    
   }
 
   /// \brief Finds an uedge between two nodes of a graph.
   ///
   /// Finds an uedge from node \c u to node \c v in graph \c g.
+  /// If the node \c u and node \c v is equal then each loop edge
+  /// will be enumerated.
   ///
   /// 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
@@ -370,15 +418,12 @@
   ///   ...
   /// }
   ///\endcode
-  // /// \todo We may want to use the "GraphBase" 
-  // /// interface here...
   template <typename Graph>
-  inline typename Graph::UEdge 
-  findUEdge(const Graph &g,
-		typename Graph::Node u, 
-		typename Graph::Node v,
-		typename Graph::UEdge prev = INVALID) {
-    return _findUEdge<Graph>(g, u, v, prev);
+  inline typename Graph::UEdge findEdge(const Graph &g,
+                                        typename Graph::Node u, 
+                                        typename Graph::Node v,
+                                        typename Graph::UEdge prev = INVALID) {
+    return _graph_utils_bits::FindUEdgeSelector<Graph>::find(g, u, v, prev);
   }
 
   /// \brief Iterator for iterating on uedges connected the same nodes.