Changeset 1010:072bddac076e in lemon-0.x for src/lemon

Timestamp:

11/19/04 19:17:25 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

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

Message:

reverseEdge() and contract() member-functions added.

File:

• src/lemon/list_graph.h (modified) (3 diffs)

src/lemon/list_graph.h

@@ -314 +314 @@
   ///This is a simple and fast erasable graph implementation.
   ///
-  ///It conforms to the
-  ///\ref concept::ErasableGraph "ErasableGraph" concept.
+  ///It addition that it conforms to the
+  ///\ref concept::ErasableGraph "ErasableGraph" concept,
+  ///it also provides several additional useful extra functionalities.
   ///\sa concept::ErasableGraph.
 
@@ -325 +326 @@
     /// Moves the target of \c e to \c n
     ///
+    ///\note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
+    ///referencing the moved edge remain
+    ///valid. However <tt>InEdge</tt>'s are invalidated.
     void moveTarget(Edge e, Node n) { _moveTarget(e,n); }
     /// Moves the source of \c e to \c n
@@ -330 +334 @@
     /// Moves the source of \c e to \c n
     ///
+    ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
+    ///referencing the moved edge remain
+    ///valid. However <tt>OutEdge</tt>'s are invalidated.
     void moveSource(Edge e, Node n) { _moveSource(e,n); }
+
+    /// Invert the direction of an edge.
+
+    ///\note The <tt>Edge</tt>'s
+    ///referencing the moved edge remain
+    ///valid. However <tt>OutEdge</tt>'s  and <tt>InEdge</tt>'s are invalidated.
+    void reverseEdge(Edge e) {
+      Node t=target(e);
+      _moveTarget(e,source(e));
+      _moveSource(e,t);
+    }
+
+    ///Using this it possible to avoid the superfluous memory allocation.
 
     ///Using this it possible to avoid the superfluous memory allocation.
     ///\todo more docs...
     void reserveEdge(int n) { edges.reserve(n); };
-    
+
+    ///Contract two nodes.
+
+    ///This function contracts two nodes.
+    ///
+    ///Node \p b will be removed but instead of deleting
+    ///its neighboring edges, they will be joined to \p a.
+    ///The last parameter \p r controls whether to remove loops. \c true
+    ///means that loops will be removed.
+    ///
+    ///\note The <tt>Edge</tt>s
+    ///referencing the moved edge remain
+    ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
+    ///may be invalidated.
+    void contract(Node a,Node b,bool r=true) 
+    {
+      for(OutEdgeIt e(*this,b);e!=INVALID;) {
+        OutEdgeIt f=e;
+        ++f;
+        if(r && target(e)==a) erase(e);
+        else moveSource(e,b);
+        e=f;
+      }
+      for(InEdgeIt e(*this,b);e!=INVALID;) {
+        InEdgeIt f=e;
+        ++f;
+        if(r && source(e)==a) erase(e);
+        else moveTarget(e,b);
+        e=f;
+      }
+      erase(b);
+    }
   };