COIN-OR::LEMON - Graph Library

Changeset 1010:072bddac076e in lemon-0.x


Ignore:
Timestamp:
11/19/04 19:17:25 (15 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:
1 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/list_graph.h

    r986 r1010  
    314314  ///This is a simple and fast erasable graph implementation.
    315315  ///
    316   ///It conforms to the
    317   ///\ref concept::ErasableGraph "ErasableGraph" concept.
     316  ///It addition that it conforms to the
     317  ///\ref concept::ErasableGraph "ErasableGraph" concept,
     318  ///it also provides several additional useful extra functionalities.
    318319  ///\sa concept::ErasableGraph.
    319320
     
    325326    /// Moves the target of \c e to \c n
    326327    ///
     328    ///\note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
     329    ///referencing the moved edge remain
     330    ///valid. However <tt>InEdge</tt>'s are invalidated.
    327331    void moveTarget(Edge e, Node n) { _moveTarget(e,n); }
    328332    /// Moves the source of \c e to \c n
     
    330334    /// Moves the source of \c e to \c n
    331335    ///
     336    ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
     337    ///referencing the moved edge remain
     338    ///valid. However <tt>OutEdge</tt>'s are invalidated.
    332339    void moveSource(Edge e, Node n) { _moveSource(e,n); }
     340
     341    /// Invert the direction of an edge.
     342
     343    ///\note The <tt>Edge</tt>'s
     344    ///referencing the moved edge remain
     345    ///valid. However <tt>OutEdge</tt>'s  and <tt>InEdge</tt>'s are invalidated.
     346    void reverseEdge(Edge e) {
     347      Node t=target(e);
     348      _moveTarget(e,source(e));
     349      _moveSource(e,t);
     350    }
     351
     352    ///Using this it possible to avoid the superfluous memory allocation.
    333353
    334354    ///Using this it possible to avoid the superfluous memory allocation.
    335355    ///\todo more docs...
    336356    void reserveEdge(int n) { edges.reserve(n); };
    337    
     357
     358    ///Contract two nodes.
     359
     360    ///This function contracts two nodes.
     361    ///
     362    ///Node \p b will be removed but instead of deleting
     363    ///its neighboring edges, they will be joined to \p a.
     364    ///The last parameter \p r controls whether to remove loops. \c true
     365    ///means that loops will be removed.
     366    ///
     367    ///\note The <tt>Edge</tt>s
     368    ///referencing the moved edge remain
     369    ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
     370    ///may be invalidated.
     371    void contract(Node a,Node b,bool r=true)
     372    {
     373      for(OutEdgeIt e(*this,b);e!=INVALID;) {
     374        OutEdgeIt f=e;
     375        ++f;
     376        if(r && target(e)==a) erase(e);
     377        else moveSource(e,b);
     378        e=f;
     379      }
     380      for(InEdgeIt e(*this,b);e!=INVALID;) {
     381        InEdgeIt f=e;
     382        ++f;
     383        if(r && source(e)==a) erase(e);
     384        else moveTarget(e,b);
     385        e=f;
     386      }
     387      erase(b);
     388    }
    338389  };
    339390 
Note: See TracChangeset for help on using the changeset viewer.