Changeset 2020:332245399dc6 in lemon-0.x

Timestamp:

03/30/06 10:38:41 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2658

Message:

Rewritten countItems and findEdges

File:

• lemon/graph_utils.h (modified) (11 diffs)

lemon/graph_utils.h

@@ -103 +103 @@
   /// 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) {
@@ -114 +115 @@
   // Node counting:
 
-  template <typename Graph>
-  inline typename enable_if<typename Graph::NodeNumTag, int>::type
-  _countNodes(const Graph &g) {
-    return g.nodeNum();
-  }
-
-  template <typename Graph>
-  inline int _countNodes(Wrap<Graph> w) {
-    return countItems<Graph, typename Graph::NodeIt>(w.value);
+  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>
+    struct CountNodesSelector<
+      Graph, typename 
+      enable_if<typename Graph::NodeNumTag, void>::type> 
+    {
+      static int count(const Graph &g) {
+        return g.nodeNum();
+      }
+    };    
   }
 
@@ -135 +145 @@
   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();
-  }
-
-  template <typename Graph>
-  inline int _countEdges(Wrap<Graph> w) {
-    return countItems<Graph, typename Graph::EdgeIt>(w.value);
+  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>
+    struct CountEdgesSelector<
+      Graph, 
+      typename enable_if<typename Graph::EdgeNumTag, void>::type> 
+    {
+      static int count(const Graph &g) {
+        return g.edgeNum();
+      }
+    };    
   }
 
@@ -159 +179 @@
   template <typename Graph>
   inline int countEdges(const Graph& g) {
-    return _countEdges<Graph>(g);
+    return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
   }
 
   // Undirected edge counting:
-
-  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);
+  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>
+    struct CountUEdgesSelector<
+      Graph, 
+      typename enable_if<typename Graph::EdgeNumTag, void>::type> 
+    {
+      static int count(const Graph &g) {
+        return g.uEdgeNum();
+      }
+    };    
   }
 
@@ -184 +211 @@
   template <typename Graph>
   inline int countUEdges(const Graph& g) {
-    return _countUEdges<Graph>(g);
-  }
-
+    return _graph_utils_bits::CountUEdgesSelector<Graph>::count(g);
+
+  }
 
 
@@ -225 +252 @@
   }
 
-
-  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;
-    }
+  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>
+    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);
+      }
+    };    
   }
 
@@ -268 +299 @@
   /// }
   ///\endcode
-  // /// \todo We may want to use the "GraphBase" 
-  // /// interface here...
   template <typename Graph>
   inline typename Graph::Edge findEdge(const Graph &g,
@@ -275 +304 @@
                                        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);
   }
 
@@ -326 +355 @@
   };
 
-  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);
-  }
-
-  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;
-    }
+  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>
+    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);
+      }
+    };    
   }
 
@@ -358 +404 @@
   ///
   /// 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
@@ -371 +419 @@
   /// }
   ///\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);
   }