COIN-OR::LEMON - Graph Library

Changeset 738:456fa5bc3256 in lemon-1.2 for lemon


Ignore:
Timestamp:
08/23/09 11:13:21 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Much better implementation for node splitting (#311)
in ListDigraph?. This solution is the same as the one that
is used in SmartDigraph?. It is much faster and does not
invalidate any iterator like the former implementation.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/list_graph.h

    r736 r738  
    3333namespace lemon {
    3434
     35  class ListDigraph;
     36
    3537  class ListDigraphBase {
    3638
     
    6365    class Node {
    6466      friend class ListDigraphBase;
     67      friend class ListDigraph;
    6568    protected:
    6669
     
    7881    class Arc {
    7982      friend class ListDigraphBase;
     83      friend class ListDigraph;
    8084    protected:
    8185
     
    468472    ///\return The newly created node.
    469473    ///
    470     ///\note \c ArcIt and \c OutArcIt iterators referencing the outgoing
    471     ///arcs of node \c n are invalidated. Other iterators remain valid.
     474    ///\note All iterators remain valid.
    472475    ///
    473476    ///\warning This functionality cannot be used together with the
     
    475478    Node split(Node n, bool connect = true) {
    476479      Node b = addNode();
    477       for(OutArcIt e(*this,n);e!=INVALID;) {
    478         OutArcIt f=e;
    479         ++f;
    480         changeSource(e,b);
    481         e=f;
     480      nodes[b.id].first_out=nodes[n.id].first_out;
     481      nodes[n.id].first_out=-1;
     482      for(int i=nodes[b.id].first_out; i!=-1; i=arcs[i].next_out) {
     483        arcs[i].source=b.id;
    482484      }
    483485      if (connect) addArc(n,b);
Note: See TracChangeset for help on using the changeset viewer.