1.1 --- a/src/lemon/list_graph.h	Fri Nov 19 17:22:29 2004 +0000
     1.2 +++ b/src/lemon/list_graph.h	Fri Nov 19 18:17:25 2004 +0000
     1.3 @@ -313,8 +313,9 @@
     1.4  
     1.5    ///This is a simple and fast erasable graph implementation.
     1.6    ///
     1.7 -  ///It conforms to the
     1.8 -  ///\ref concept::ErasableGraph "ErasableGraph" concept.
     1.9 +  ///It addition that it conforms to the
    1.10 +  ///\ref concept::ErasableGraph "ErasableGraph" concept,
    1.11 +  ///it also provides several additional useful extra functionalities.
    1.12    ///\sa concept::ErasableGraph.
    1.13  
    1.14    class ListGraph : public ErasableListGraphBase 
    1.15 @@ -324,17 +325,67 @@
    1.16  
    1.17      /// Moves the target of \c e to \c n
    1.18      ///
    1.19 +    ///\note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
    1.20 +    ///referencing the moved edge remain
    1.21 +    ///valid. However <tt>InEdge</tt>'s are invalidated.
    1.22      void moveTarget(Edge e, Node n) { _moveTarget(e,n); }
    1.23      /// Moves the source of \c e to \c n
    1.24  
    1.25      /// Moves the source of \c e to \c n
    1.26      ///
    1.27 +    ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
    1.28 +    ///referencing the moved edge remain
    1.29 +    ///valid. However <tt>OutEdge</tt>'s are invalidated.
    1.30      void moveSource(Edge e, Node n) { _moveSource(e,n); }
    1.31  
    1.32 +    /// Invert the direction of an edge.
    1.33 +
    1.34 +    ///\note The <tt>Edge</tt>'s
    1.35 +    ///referencing the moved edge remain
    1.36 +    ///valid. However <tt>OutEdge</tt>'s  and <tt>InEdge</tt>'s are invalidated.
    1.37 +    void reverseEdge(Edge e) {
    1.38 +      Node t=target(e);
    1.39 +      _moveTarget(e,source(e));
    1.40 +      _moveSource(e,t);
    1.41 +    }
    1.42 +
    1.43 +    ///Using this it possible to avoid the superfluous memory allocation.
    1.44 +
    1.45      ///Using this it possible to avoid the superfluous memory allocation.
    1.46      ///\todo more docs...
    1.47      void reserveEdge(int n) { edges.reserve(n); };
    1.48 -    
    1.49 +
    1.50 +    ///Contract two nodes.
    1.51 +
    1.52 +    ///This function contracts two nodes.
    1.53 +    ///
    1.54 +    ///Node \p b will be removed but instead of deleting
    1.55 +    ///its neighboring edges, they will be joined to \p a.
    1.56 +    ///The last parameter \p r controls whether to remove loops. \c true
    1.57 +    ///means that loops will be removed.
    1.58 +    ///
    1.59 +    ///\note The <tt>Edge</tt>s
    1.60 +    ///referencing the moved edge remain
    1.61 +    ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
    1.62 +    ///may be invalidated.
    1.63 +    void contract(Node a,Node b,bool r=true) 
    1.64 +    {
    1.65 +      for(OutEdgeIt e(*this,b);e!=INVALID;) {
    1.66 +	OutEdgeIt f=e;
    1.67 +	++f;
    1.68 +	if(r && target(e)==a) erase(e);
    1.69 +	else moveSource(e,b);
    1.70 +	e=f;
    1.71 +      }
    1.72 +      for(InEdgeIt e(*this,b);e!=INVALID;) {
    1.73 +	InEdgeIt f=e;
    1.74 +	++f;
    1.75 +	if(r && source(e)==a) erase(e);
    1.76 +	else moveTarget(e,b);
    1.77 +	e=f;
    1.78 +      }
    1.79 +      erase(b);
    1.80 +    }
    1.81    };
    1.82    
    1.83    /// @}