Changeset 1704:467d7927a901 in lemon-0.x for lemon/graph_utils.h

Timestamp:

10/05/05 15:17:42 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

findUndirEdge, ConUndirEdgeIt?
some modification in the undir graph extenders

File:

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

lemon/graph_utils.h

@@ -161 +161 @@
   }
 
-  /// \brief Function to count the number of the in-edges to node \c n.
-  ///
-  /// This function counts 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 inc-edges to node \c n
   /// in the graph.  
   template <typename Graph>
@@ -215 +215 @@
   // /// \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,
@@ -265 +264 @@
     ConEdgeIt& operator++() {
       Parent::operator=(findEdge(graph, graph.source(*this), 
+                                 graph.target(*this), *this));
+      return *this;
+    }
+  private:
+    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;
@@ -553 +656 @@
     typedef _Item Key;
 
-    typedef True NeedCopy;
-
     /// \brief Constructor.
     ///
@@ -577 +678 @@
     class InverseMap {
     public:
-
-      typedef True NeedCopy;
 
       /// \brief Constructor.
@@ -907 +1006 @@
   public:
 
-    typedef True NeedCopy;
-
     typedef typename Graph::Node Value;
     typedef typename Graph::Edge Key;
@@ -948 +1045 @@
   public:
 
-    typedef True NeedCopy;
-
     typedef typename Graph::Node Value;
     typedef typename Graph::Edge Key;
@@ -989 +1084 @@
   public:
 
-    typedef True NeedCopy;
-
     typedef typename Graph::Edge Value;
     typedef typename Graph::UndirEdge Key;
@@ -1029 +1122 @@
   class BackwardMap {
   public:
-    typedef True NeedCopy;
 
     typedef typename Graph::Edge Value;
@@ -1297 +1389 @@
 
     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;
       }
     }