COIN-OR::LEMON - Graph Library

Changeset 209:765619b7cbb2 in lemon-1.0 for lemon/list_graph.h


Ignore:
Timestamp:
07/13/08 20:51:02 (11 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Phase:
public
Message:

Apply unify-sources.sh to the source tree

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/list_graph.h

    r184 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
     
    3838      int prev, next;
    3939    };
    40  
     40
    4141    struct ArcT {
    4242      int target, source;
     
    5454
    5555    int first_free_arc;
    56    
     56
    5757  public:
    58    
     58
    5959    typedef ListDigraphBase Digraph;
    60    
     60
    6161    class Node {
    6262      friend class ListDigraphBase;
     
    9393    ListDigraphBase()
    9494      : nodes(), first_node(-1),
    95         first_free_node(-1), arcs(), first_free_arc(-1) {}
    96 
    97    
    98     int maxNodeId() const { return nodes.size()-1; } 
     95        first_free_node(-1), arcs(), first_free_arc(-1) {}
     96
     97
     98    int maxNodeId() const { return nodes.size()-1; }
    9999    int maxArcId() const { return arcs.size()-1; }
    100100
     
    103103
    104104
    105     void first(Node& node) const { 
     105    void first(Node& node) const {
    106106      node.id = first_node;
    107107    }
     
    112112
    113113
    114     void first(Arc& arc) const { 
     114    void first(Arc& arc) const {
    115115      int n;
    116       for(n = first_node; 
    117           n!=-1 && nodes[n].first_in == -1;
    118           n = nodes[n].next) {}
     116      for(n = first_node;
     117          n!=-1 && nodes[n].first_in == -1;
     118          n = nodes[n].next) {}
    119119      arc.id = (n == -1) ? -1 : nodes[n].first_in;
    120120    }
     
    122122    void next(Arc& arc) const {
    123123      if (arcs[arc.id].next_in != -1) {
    124         arc.id = arcs[arc.id].next_in;
    125       } else {
    126         int n;
    127         for(n = nodes[arcs[arc.id].target].next;
    128             n!=-1 && nodes[n].first_in == -1;
    129             n = nodes[n].next) {}
    130         arc.id = (n == -1) ? -1 : nodes[n].first_in;
    131       }     
     124        arc.id = arcs[arc.id].next_in;
     125      } else {
     126        int n;
     127        for(n = nodes[arcs[arc.id].target].next;
     128            n!=-1 && nodes[n].first_in == -1;
     129            n = nodes[n].next) {}
     130        arc.id = (n == -1) ? -1 : nodes[n].first_in;
     131      }
    132132    }
    133133
     
    146146    }
    147147
    148    
     148
    149149    static int id(Node v) { return v.id; }
    150150    static int id(Arc e) { return e.id; }
     
    153153    static Arc arcFromId(int id) { return Arc(id);}
    154154
    155     bool valid(Node n) const { 
    156       return n.id >= 0 && n.id < static_cast<int>(nodes.size()) && 
    157         nodes[n.id].prev != -2;
    158     }
    159 
    160     bool valid(Arc a) const { 
    161       return a.id >= 0 && a.id < static_cast<int>(arcs.size()) && 
    162         arcs[a.id].prev_in != -2;
    163     }
    164 
    165     Node addNode() {     
     155    bool valid(Node n) const {
     156      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
     157        nodes[n.id].prev != -2;
     158    }
     159
     160    bool valid(Arc a) const {
     161      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
     162        arcs[a.id].prev_in != -2;
     163    }
     164
     165    Node addNode() {
    166166      int n;
    167      
     167
    168168      if(first_free_node==-1) {
    169         n = nodes.size();
    170         nodes.push_back(NodeT());
    171       } else {
    172         n = first_free_node;
    173         first_free_node = nodes[n].next;
    174       }
    175      
     169        n = nodes.size();
     170        nodes.push_back(NodeT());
     171      } else {
     172        n = first_free_node;
     173        first_free_node = nodes[n].next;
     174      }
     175
    176176      nodes[n].next = first_node;
    177177      if(first_node != -1) nodes[first_node].prev = n;
    178178      first_node = n;
    179179      nodes[n].prev = -1;
    180      
     180
    181181      nodes[n].first_in = nodes[n].first_out = -1;
    182      
     182
    183183      return Node(n);
    184184    }
    185    
     185
    186186    Arc addArc(Node u, Node v) {
    187       int n;     
     187      int n;
    188188
    189189      if (first_free_arc == -1) {
    190         n = arcs.size();
    191         arcs.push_back(ArcT());
    192       } else {
    193         n = first_free_arc;
    194         first_free_arc = arcs[n].next_in;
    195       }
    196      
    197       arcs[n].source = u.id; 
     190        n = arcs.size();
     191        arcs.push_back(ArcT());
     192      } else {
     193        n = first_free_arc;
     194        first_free_arc = arcs[n].next_in;
     195      }
     196
     197      arcs[n].source = u.id;
    198198      arcs[n].target = v.id;
    199199
    200200      arcs[n].next_out = nodes[u.id].first_out;
    201201      if(nodes[u.id].first_out != -1) {
    202         arcs[nodes[u.id].first_out].prev_out = n;
    203       }
    204      
     202        arcs[nodes[u.id].first_out].prev_out = n;
     203      }
     204
    205205      arcs[n].next_in = nodes[v.id].first_in;
    206206      if(nodes[v.id].first_in != -1) {
    207         arcs[nodes[v.id].first_in].prev_in = n;
    208       }
    209      
     207        arcs[nodes[v.id].first_in].prev_in = n;
     208      }
     209
    210210      arcs[n].prev_in = arcs[n].prev_out = -1;
    211        
     211
    212212      nodes[u.id].first_out = nodes[v.id].first_in = n;
    213213
    214214      return Arc(n);
    215215    }
    216    
     216
    217217    void erase(const Node& node) {
    218218      int n = node.id;
    219      
     219
    220220      if(nodes[n].next != -1) {
    221         nodes[nodes[n].next].prev = nodes[n].prev;
    222       }
    223      
     221        nodes[nodes[n].next].prev = nodes[n].prev;
     222      }
     223
    224224      if(nodes[n].prev != -1) {
    225         nodes[nodes[n].prev].next = nodes[n].next;
    226       } else {
    227         first_node = nodes[n].next;
    228       }
    229      
     225        nodes[nodes[n].prev].next = nodes[n].next;
     226      } else {
     227        first_node = nodes[n].next;
     228      }
     229
    230230      nodes[n].next = first_free_node;
    231231      first_free_node = n;
     
    233233
    234234    }
    235    
     235
    236236    void erase(const Arc& arc) {
    237237      int n = arc.id;
    238      
     238
    239239      if(arcs[n].next_in!=-1) {
    240         arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
     240        arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
    241241      }
    242242
    243243      if(arcs[n].prev_in!=-1) {
    244         arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
    245       } else {
    246         nodes[arcs[n].target].first_in = arcs[n].next_in;
    247       }
    248 
    249      
     244        arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
     245      } else {
     246        nodes[arcs[n].target].first_in = arcs[n].next_in;
     247      }
     248
     249
    250250      if(arcs[n].next_out!=-1) {
    251         arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
    252       } 
     251        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
     252      }
    253253
    254254      if(arcs[n].prev_out!=-1) {
    255         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
    256       } else {
    257         nodes[arcs[n].source].first_out = arcs[n].next_out;
    258       }
    259      
     255        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
     256      } else {
     257        nodes[arcs[n].source].first_out = arcs[n].next_out;
     258      }
     259
    260260      arcs[n].next_in = first_free_arc;
    261261      first_free_arc = n;
     
    270270
    271271  protected:
    272     void changeTarget(Arc e, Node n) 
     272    void changeTarget(Arc e, Node n)
    273273    {
    274274      if(arcs[e.id].next_in != -1)
    275         arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;
     275        arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;
    276276      if(arcs[e.id].prev_in != -1)
    277         arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;
     277        arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;
    278278      else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in;
    279279      if (nodes[n.id].first_in != -1) {
    280         arcs[nodes[n.id].first_in].prev_in = e.id;
     280        arcs[nodes[n.id].first_in].prev_in = e.id;
    281281      }
    282282      arcs[e.id].target = n.id;
     
    285285      nodes[n.id].first_in = e.id;
    286286    }
    287     void changeSource(Arc e, Node n) 
     287    void changeSource(Arc e, Node n)
    288288    {
    289289      if(arcs[e.id].next_out != -1)
    290         arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;
     290        arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;
    291291      if(arcs[e.id].prev_out != -1)
    292         arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;
     292        arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;
    293293      else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out;
    294294      if (nodes[n.id].first_out != -1) {
    295         arcs[nodes[n.id].first_out].prev_out = e.id;
     295        arcs[nodes[n.id].first_out].prev_out = e.id;
    296296      }
    297297      arcs[e.id].source = n.id;
     
    308308  /// @{
    309309
    310   ///A general directed graph structure. 
    311 
    312   ///\ref ListDigraph is a simple and fast <em>directed graph</em> 
    313   ///implementation based on static linked lists that are stored in 
    314   ///\c std::vector structures.   
     310  ///A general directed graph structure.
     311
     312  ///\ref ListDigraph is a simple and fast <em>directed graph</em>
     313  ///implementation based on static linked lists that are stored in
     314  ///\c std::vector structures.
    315315  ///
    316316  ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
     
    327327  private:
    328328    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
    329    
     329
    330330    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
    331331    ///
     
    342342
    343343    /// Constructor
    344    
     344
    345345    /// Constructor.
    346346    ///
     
    348348
    349349    ///Add a new node to the digraph.
    350    
     350
    351351    ///Add a new node to the digraph.
    352352    ///\return the new node.
     
    354354
    355355    ///Add a new arc to the digraph.
    356    
     356
    357357    ///Add a new arc to the digraph with source node \c s
    358358    ///and target node \c t.
    359359    ///\return the new arc.
    360     Arc addArc(const Node& s, const Node& t) { 
    361       return Parent::addArc(s, t); 
     360    Arc addArc(const Node& s, const Node& t) {
     361      return Parent::addArc(s, t);
    362362    }
    363363
     
    365365
    366366    /// This function gives back true if the given node is valid,
    367     /// ie. it is a real node of the graph. 
     367    /// ie. it is a real node of the graph.
    368368    ///
    369369    /// \warning A Node pointing to a removed item
     
    375375
    376376    /// This function gives back true if the given arc is valid,
    377     /// ie. it is a real arc of the graph. 
     377    /// ie. it is a real arc of the graph.
    378378    ///
    379379    /// \warning An Arc pointing to a removed item
     
    392392    ///\warning This functionality cannot be used together with the Snapshot
    393393    ///feature.
    394     void changeTarget(Arc e, Node n) { 
    395       Parent::changeTarget(e,n); 
     394    void changeTarget(Arc e, Node n) {
     395      Parent::changeTarget(e,n);
    396396    }
    397397    /// Change the source of \c e to \c n
     
    405405    ///\warning This functionality cannot be used together with the Snapshot
    406406    ///feature.
    407     void changeSource(Arc e, Node n) { 
     407    void changeSource(Arc e, Node n) {
    408408      Parent::changeSource(e,n);
    409409    }
     
    457457    ///\warning This functionality cannot be used together with the Snapshot
    458458    ///feature.
    459     void contract(Node a, Node b, bool r = true) 
     459    void contract(Node a, Node b, bool r = true)
    460460    {
    461461      for(OutArcIt e(*this,b);e!=INVALID;) {
    462         OutArcIt f=e;
    463         ++f;
    464         if(r && target(e)==a) erase(e);
    465         else changeSource(e,a);
    466         e=f;
     462        OutArcIt f=e;
     463        ++f;
     464        if(r && target(e)==a) erase(e);
     465        else changeSource(e,a);
     466        e=f;
    467467      }
    468468      for(InArcIt e(*this,b);e!=INVALID;) {
    469         InArcIt f=e;
    470         ++f;
    471         if(r && source(e)==a) erase(e);
    472         else changeTarget(e,a);
    473         e=f;
     469        InArcIt f=e;
     470        ++f;
     471        if(r && source(e)==a) erase(e);
     472        else changeTarget(e,a);
     473        e=f;
    474474      }
    475475      erase(b);
     
    486486    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
    487487    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
    488     ///be invalidated. 
     488    ///be invalidated.
    489489    ///
    490490    ///\warning This functionality cannot be used together with the
     
    495495      Node b = addNode();
    496496      for(OutArcIt e(*this,n);e!=INVALID;) {
    497         OutArcIt f=e;
    498         ++f;
    499         changeSource(e,b);
    500         e=f;
     497         OutArcIt f=e;
     498        ++f;
     499        changeSource(e,b);
     500        e=f;
    501501      }
    502502      if (connect) addArc(n,b);
    503503      return b;
    504504    }
    505      
     505
    506506    ///Split an arc.
    507507
     
    520520      return b;
    521521    }
    522      
     522
    523523    /// \brief Class to make a snapshot of the digraph and restore
    524524    /// it later.
     
    530530    ///
    531531    /// \warning Arc and node deletions and other modifications (e.g.
    532     /// contracting, splitting, reversing arcs or nodes) cannot be 
    533     /// restored. These events invalidate the snapshot. 
     532    /// contracting, splitting, reversing arcs or nodes) cannot be
     533    /// restored. These events invalidate the snapshot.
    534534    class Snapshot {
    535535    protected:
     
    546546        using NodeNotifier::ObserverBase::detach;
    547547        using NodeNotifier::ObserverBase::attached;
    548        
     548
    549549      protected:
    550        
     550
    551551        virtual void add(const Node& node) {
    552552          snapshot.addNode(node);
     
    568568          Node node;
    569569          std::vector<Node> nodes;
    570           for (notifier()->first(node); node != INVALID; 
     570          for (notifier()->first(node); node != INVALID;
    571571               notifier()->next(node)) {
    572572            nodes.push_back(node);
     
    578578        virtual void clear() {
    579579          Node node;
    580           for (notifier()->first(node); node != INVALID; 
     580          for (notifier()->first(node); node != INVALID;
    581581               notifier()->next(node)) {
    582582            snapshot.eraseNode(node);
     
    596596        using ArcNotifier::ObserverBase::detach;
    597597        using ArcNotifier::ObserverBase::attached;
    598        
     598
    599599      protected:
    600600
     
    618618          Arc arc;
    619619          std::vector<Arc> arcs;
    620           for (notifier()->first(arc); arc != INVALID; 
     620          for (notifier()->first(arc); arc != INVALID;
    621621               notifier()->next(arc)) {
    622622            arcs.push_back(arc);
     
    628628        virtual void clear() {
    629629          Arc arc;
    630           for (notifier()->first(arc); arc != INVALID; 
     630          for (notifier()->first(arc); arc != INVALID;
    631631               notifier()->next(arc)) {
    632632            snapshot.eraseArc(arc);
     
    636636        Snapshot& snapshot;
    637637      };
    638      
     638
    639639      ListDigraph *digraph;
    640640
     
    647647
    648648      void addNode(const Node& node) {
    649         added_nodes.push_front(node);       
     649        added_nodes.push_front(node);
    650650      }
    651651      void eraseNode(const Node& node) {
    652         std::list<Node>::iterator it = 
     652        std::list<Node>::iterator it =
    653653          std::find(added_nodes.begin(), added_nodes.end(), node);
    654654        if (it == added_nodes.end()) {
     
    662662
    663663      void addArc(const Arc& arc) {
    664         added_arcs.push_front(arc);       
     664        added_arcs.push_front(arc);
    665665      }
    666666      void eraseArc(const Arc& arc) {
    667         std::list<Arc>::iterator it = 
     667        std::list<Arc>::iterator it =
    668668          std::find(added_arcs.begin(), added_arcs.end(), arc);
    669669        if (it == added_arcs.end()) {
    670670          clear();
    671           node_observer_proxy.detach(); 
     671          node_observer_proxy.detach();
    672672          throw ArcNotifier::ImmediateDetach();
    673673        } else {
    674674          added_arcs.erase(it);
    675         }       
     675        }
    676676      }
    677677
    678678      void attach(ListDigraph &_digraph) {
    679         digraph = &_digraph;
    680         node_observer_proxy.attach(digraph->notifier(Node()));
     679        digraph = &_digraph;
     680        node_observer_proxy.attach(digraph->notifier(Node()));
    681681        arc_observer_proxy.attach(digraph->notifier(Arc()));
    682682      }
    683            
     683
    684684      void detach() {
    685         node_observer_proxy.detach();
    686         arc_observer_proxy.detach();
     685        node_observer_proxy.detach();
     686        arc_observer_proxy.detach();
    687687      }
    688688
     
    693693      void clear() {
    694694        added_nodes.clear();
    695         added_arcs.clear();       
     695        added_arcs.clear();
    696696      }
    697697
     
    702702      /// Default constructor.
    703703      /// To actually make a snapshot you must call save().
    704       Snapshot() 
    705         : digraph(0), node_observer_proxy(*this), 
     704      Snapshot()
     705        : digraph(0), node_observer_proxy(*this),
    706706          arc_observer_proxy(*this) {}
    707      
     707
    708708      /// \brief Constructor that immediately makes a snapshot.
    709       ///     
     709      ///
    710710      /// This constructor immediately makes a snapshot of the digraph.
    711711      /// \param _digraph The digraph we make a snapshot of.
    712       Snapshot(ListDigraph &_digraph) 
    713         : node_observer_proxy(*this), 
     712      Snapshot(ListDigraph &_digraph)
     713        : node_observer_proxy(*this),
    714714          arc_observer_proxy(*this) {
    715         attach(_digraph);
    716       }
    717      
     715        attach(_digraph);
     716      }
     717
    718718      /// \brief Make a snapshot.
    719719      ///
     
    730730        attach(_digraph);
    731731      }
    732      
     732
    733733      /// \brief Undo the changes until the last snapshot.
    734       // 
     734      //
    735735      /// Undo the changes until the last snapshot created by save().
    736736      void restore() {
    737         detach();
    738         for(std::list<Arc>::iterator it = added_arcs.begin();
     737        detach();
     738        for(std::list<Arc>::iterator it = added_arcs.begin();
    739739            it != added_arcs.end(); ++it) {
    740           digraph->erase(*it);
    741         }
    742         for(std::list<Node>::iterator it = added_nodes.begin();
     740          digraph->erase(*it);
     741        }
     742        for(std::list<Node>::iterator it = added_nodes.begin();
    743743            it != added_nodes.end(); ++it) {
    744           digraph->erase(*it);
    745         }
     744          digraph->erase(*it);
     745        }
    746746        clear();
    747747      }
     
    754754      }
    755755    };
    756    
     756
    757757  };
    758758
     
    767767      int prev, next;
    768768    };
    769  
     769
    770770    struct ArcT {
    771771      int target;
     
    782782
    783783    int first_free_arc;
    784    
     784
    785785  public:
    786    
     786
    787787    typedef ListGraphBase Digraph;
    788788
     
    790790    class Arc;
    791791    class Edge;
    792    
     792
    793793    class Node {
    794794      friend class ListGraphBase;
     
    842842    ListGraphBase()
    843843      : nodes(), first_node(-1),
    844         first_free_node(-1), arcs(), first_free_arc(-1) {}
    845 
    846    
    847     int maxNodeId() const { return nodes.size()-1; } 
     844        first_free_node(-1), arcs(), first_free_arc(-1) {}
     845
     846
     847    int maxNodeId() const { return nodes.size()-1; }
    848848    int maxEdgeId() const { return arcs.size() / 2 - 1; }
    849849    int maxArcId() const { return arcs.size()-1; }
     
    863863    }
    864864
    865     void first(Node& node) const { 
     865    void first(Node& node) const {
    866866      node.id = first_node;
    867867    }
     
    871871    }
    872872
    873     void first(Arc& e) const { 
     873    void first(Arc& e) const {
    874874      int n = first_node;
    875875      while (n != -1 && nodes[n].first_out == -1) {
     
    881881    void next(Arc& e) const {
    882882      if (arcs[e.id].next_out != -1) {
    883         e.id = arcs[e.id].next_out;
    884       } else {
    885         int n = nodes[arcs[e.id ^ 1].target].next;
     883        e.id = arcs[e.id].next_out;
     884      } else {
     885        int n = nodes[arcs[e.id ^ 1].target].next;
    886886        while(n != -1 && nodes[n].first_out == -1) {
    887887          n = nodes[n].next;
    888888        }
    889         e.id = (n == -1) ? -1 : nodes[n].first_out;
    890       }     
    891     }
    892 
    893     void first(Edge& e) const { 
     889        e.id = (n == -1) ? -1 : nodes[n].first_out;
     890      }
     891    }
     892
     893    void first(Edge& e) const {
    894894      int n = first_node;
    895895      while (n != -1) {
     
    901901          e.id /= 2;
    902902          return;
    903         } 
     903        }
    904904        n = nodes[n].next;
    905905      }
     
    916916        e.id /= 2;
    917917        return;
    918       } 
     918      }
    919919      n = nodes[n].next;
    920920      while (n != -1) {
     
    926926          e.id /= 2;
    927927          return;
    928         } 
     928        }
    929929        n = nodes[n].next;
    930930      }
     
    968968      }
    969969    }
    970    
     970
    971971    static int id(Node v) { return v.id; }
    972972    static int id(Arc e) { return e.id; }
     
    977977    static Edge edgeFromId(int id) { return Edge(id);}
    978978
    979     bool valid(Node n) const { 
    980       return n.id >= 0 && n.id < static_cast<int>(nodes.size()) && 
    981         nodes[n.id].prev != -2;
    982     }
    983 
    984     bool valid(Arc a) const { 
    985       return a.id >= 0 && a.id < static_cast<int>(arcs.size()) && 
    986         arcs[a.id].prev_out != -2;
    987     }
    988 
    989     bool valid(Edge e) const { 
    990       return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) && 
    991         arcs[2 * e.id].prev_out != -2;
    992     }
    993 
    994     Node addNode() {     
     979    bool valid(Node n) const {
     980      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
     981        nodes[n.id].prev != -2;
     982    }
     983
     984    bool valid(Arc a) const {
     985      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
     986        arcs[a.id].prev_out != -2;
     987    }
     988
     989    bool valid(Edge e) const {
     990      return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
     991        arcs[2 * e.id].prev_out != -2;
     992    }
     993
     994    Node addNode() {
    995995      int n;
    996      
     996
    997997      if(first_free_node==-1) {
    998         n = nodes.size();
    999         nodes.push_back(NodeT());
    1000       } else {
    1001         n = first_free_node;
    1002         first_free_node = nodes[n].next;
    1003       }
    1004      
     998        n = nodes.size();
     999        nodes.push_back(NodeT());
     1000      } else {
     1001        n = first_free_node;
     1002        first_free_node = nodes[n].next;
     1003      }
     1004
    10051005      nodes[n].next = first_node;
    10061006      if (first_node != -1) nodes[first_node].prev = n;
    10071007      first_node = n;
    10081008      nodes[n].prev = -1;
    1009      
     1009
    10101010      nodes[n].first_out = -1;
    1011      
     1011
    10121012      return Node(n);
    10131013    }
    1014    
     1014
    10151015    Edge addEdge(Node u, Node v) {
    1016       int n;     
     1016      int n;
    10171017
    10181018      if (first_free_arc == -1) {
    1019         n = arcs.size();
    1020         arcs.push_back(ArcT());
    1021         arcs.push_back(ArcT());
    1022       } else {
    1023         n = first_free_arc;
    1024         first_free_arc = arcs[n].next_out;
    1025       }
    1026      
     1019        n = arcs.size();
     1020        arcs.push_back(ArcT());
     1021        arcs.push_back(ArcT());
     1022      } else {
     1023        n = first_free_arc;
     1024        first_free_arc = arcs[n].next_out;
     1025      }
     1026
    10271027      arcs[n].target = u.id;
    10281028      arcs[n | 1].target = v.id;
     
    10301030      arcs[n].next_out = nodes[v.id].first_out;
    10311031      if (nodes[v.id].first_out != -1) {
    1032         arcs[nodes[v.id].first_out].prev_out = n;
    1033       }     
     1032        arcs[nodes[v.id].first_out].prev_out = n;
     1033      }
    10341034      arcs[n].prev_out = -1;
    10351035      nodes[v.id].first_out = n;
    1036      
     1036
    10371037      arcs[n | 1].next_out = nodes[u.id].first_out;
    10381038      if (nodes[u.id].first_out != -1) {
    1039         arcs[nodes[u.id].first_out].prev_out = (n | 1);
    1040       }
    1041       arcs[n | 1].prev_out = -1;     
     1039        arcs[nodes[u.id].first_out].prev_out = (n | 1);
     1040      }
     1041      arcs[n | 1].prev_out = -1;
    10421042      nodes[u.id].first_out = (n | 1);
    10431043
    10441044      return Edge(n / 2);
    10451045    }
    1046    
     1046
    10471047    void erase(const Node& node) {
    10481048      int n = node.id;
    1049      
     1049
    10501050      if(nodes[n].next != -1) {
    1051         nodes[nodes[n].next].prev = nodes[n].prev;
    1052       }
    1053      
     1051        nodes[nodes[n].next].prev = nodes[n].prev;
     1052      }
     1053
    10541054      if(nodes[n].prev != -1) {
    1055         nodes[nodes[n].prev].next = nodes[n].next;
    1056       } else {
    1057         first_node = nodes[n].next;
    1058       }
    1059      
     1055        nodes[nodes[n].prev].next = nodes[n].next;
     1056      } else {
     1057        first_node = nodes[n].next;
     1058      }
     1059
    10601060      nodes[n].next = first_free_node;
    10611061      first_free_node = n;
    10621062      nodes[n].prev = -2;
    10631063    }
    1064    
     1064
    10651065    void erase(const Edge& edge) {
    10661066      int n = edge.id * 2;
    1067      
     1067
    10681068      if (arcs[n].next_out != -1) {
    1069         arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
    1070       } 
     1069        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
     1070      }
    10711071
    10721072      if (arcs[n].prev_out != -1) {
    1073         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
    1074       } else {
    1075         nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
     1073        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
     1074      } else {
     1075        nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
    10761076      }
    10771077
    10781078      if (arcs[n | 1].next_out != -1) {
    1079         arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
    1080       } 
     1079        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
     1080      }
    10811081
    10821082      if (arcs[n | 1].prev_out != -1) {
    1083         arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
    1084       } else {
    1085         nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
    1086       }
    1087      
     1083        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
     1084      } else {
     1085        nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
     1086      }
     1087
    10881088      arcs[n].next_out = first_free_arc;
    1089       first_free_arc = n;     
     1089      first_free_arc = n;
    10901090      arcs[n].prev_out = -2;
    10911091      arcs[n | 1].prev_out = -2;
     
    11031103    void changeTarget(Edge e, Node n) {
    11041104      if(arcs[2 * e.id].next_out != -1) {
    1105         arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
     1105        arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
    11061106      }
    11071107      if(arcs[2 * e.id].prev_out != -1) {
    1108         arcs[arcs[2 * e.id].prev_out].next_out =
     1108        arcs[arcs[2 * e.id].prev_out].next_out =
    11091109          arcs[2 * e.id].next_out;
    11101110      } else {
    1111         nodes[arcs[(2 * e.id) | 1].target].first_out = 
     1111        nodes[arcs[(2 * e.id) | 1].target].first_out =
    11121112          arcs[2 * e.id].next_out;
    11131113      }
    11141114
    11151115      if (nodes[n.id].first_out != -1) {
    1116         arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
     1116        arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
    11171117      }
    11181118      arcs[(2 * e.id) | 1].target = n.id;
     
    11241124    void changeSource(Edge e, Node n) {
    11251125      if(arcs[(2 * e.id) | 1].next_out != -1) {
    1126         arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
     1126        arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
    11271127          arcs[(2 * e.id) | 1].prev_out;
    11281128      }
    11291129      if(arcs[(2 * e.id) | 1].prev_out != -1) {
    1130         arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
     1130        arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
    11311131          arcs[(2 * e.id) | 1].next_out;
    11321132      } else {
    1133         nodes[arcs[2 * e.id].target].first_out = 
     1133        nodes[arcs[2 * e.id].target].first_out =
    11341134          arcs[(2 * e.id) | 1].next_out;
    11351135      }
    11361136
    11371137      if (nodes[n.id].first_out != -1) {
    1138         arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
     1138        arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
    11391139      }
    11401140      arcs[2 * e.id].target = n.id;
     
    11541154  ///A general undirected graph structure.
    11551155
    1156   ///\ref ListGraph is a simple and fast <em>undirected graph</em> 
    1157   ///implementation based on static linked lists that are stored in 
    1158   ///\c std::vector structures. 
     1156  ///\ref ListGraph is a simple and fast <em>undirected graph</em>
     1157  ///implementation based on static linked lists that are stored in
     1158  ///\c std::vector structures.
    11591159  ///
    11601160  ///It conforms to the \ref concepts::Graph "Graph concept" and it
     
    11831183  public:
    11841184    /// Constructor
    1185    
     1185
    11861186    /// Constructor.
    11871187    ///
     
    12031203    /// and target node \c t.
    12041204    /// \return the new edge.
    1205     Edge addEdge(const Node& s, const Node& t) { 
    1206       return Parent::addEdge(s, t); 
     1205    Edge addEdge(const Node& s, const Node& t) {
     1206      return Parent::addEdge(s, t);
    12071207    }
    12081208    /// Node validity check
    12091209
    12101210    /// This function gives back true if the given node is valid,
    1211     /// ie. it is a real node of the graph. 
     1211    /// ie. it is a real node of the graph.
    12121212    ///
    12131213    /// \warning A Node pointing to a removed item
     
    12181218
    12191219    /// This function gives back true if the given arc is valid,
    1220     /// ie. it is a real arc of the graph. 
     1220    /// ie. it is a real arc of the graph.
    12211221    ///
    12221222    /// \warning An Arc pointing to a removed item
     
    12271227
    12281228    /// This function gives back true if the given edge is valid,
    1229     /// ie. it is a real arc of the graph. 
     1229    /// ie. it is a real arc of the graph.
    12301230    ///
    12311231    /// \warning A Edge pointing to a removed item
     
    12431243    ///\warning This functionality cannot be used together with the
    12441244    ///Snapshot feature.
    1245     void changeSource(Edge e, Node n) { 
    1246       Parent::changeSource(e,n); 
    1247     }   
     1245    void changeSource(Edge e, Node n) {
     1246      Parent::changeSource(e,n);
     1247    }
    12481248    /// \brief Change the target of \c e to \c n
    12491249    ///
     
    12551255    ///\warning This functionality cannot be used together with the
    12561256    ///Snapshot feature.
    1257     void changeTarget(Edge e, Node n) { 
    1258       Parent::changeTarget(e,n); 
     1257    void changeTarget(Edge e, Node n) {
     1258      Parent::changeTarget(e,n);
    12591259    }
    12601260    /// \brief Change the source of \c e to \c n
    12611261    ///
    1262     /// This function changes the source of \c e to \c n. 
     1262    /// This function changes the source of \c e to \c n.
    12631263    /// It also changes the proper node of the represented edge.
    12641264    ///
     
    12691269    ///\warning This functionality cannot be used together with the
    12701270    ///Snapshot feature.
    1271     void changeSource(Arc e, Node n) { 
     1271    void changeSource(Arc e, Node n) {
    12721272      if (Parent::direction(e)) {
    12731273        Parent::changeSource(e,n);
    12741274      } else {
    12751275        Parent::changeTarget(e,n);
    1276       } 
     1276      }
    12771277    }
    12781278    /// \brief Change the target of \c e to \c n
    12791279    ///
    1280     /// This function changes the target of \c e to \c n. 
     1280    /// This function changes the target of \c e to \c n.
    12811281    /// It also changes the proper node of the represented edge.
    12821282    ///
     
    12871287    ///\warning This functionality cannot be used together with the
    12881288    ///Snapshot feature.
    1289     void changeTarget(Arc e, Node n) { 
     1289    void changeTarget(Arc e, Node n) {
    12901290      if (Parent::direction(e)) {
    12911291        Parent::changeTarget(e,n);
    12921292      } else {
    12931293        Parent::changeSource(e,n);
    1294       } 
     1294      }
    12951295    }
    12961296    /// \brief Contract two nodes.
     
    13091309    void contract(Node a, Node b, bool r = true) {
    13101310      for(IncEdgeIt e(*this, b); e!=INVALID;) {
    1311         IncEdgeIt f = e; ++f;
    1312         if (r && runningNode(e) == a) {
    1313           erase(e);
    1314         } else if (source(e) == b) {
    1315           changeSource(e, a);
    1316         } else {
    1317           changeTarget(e, a);
    1318         }
    1319         e = f;
     1311        IncEdgeIt f = e; ++f;
     1312        if (r && runningNode(e) == a) {
     1313          erase(e);
     1314        } else if (source(e) == b) {
     1315          changeSource(e, a);
     1316        } else {
     1317          changeTarget(e, a);
     1318        }
     1319        e = f;
    13201320      }
    13211321      erase(b);
     
    13321332    ///
    13331333    /// \warning Edge and node deletions and other modifications
    1334     /// (e.g. changing nodes of edges, contracting nodes) cannot be 
     1334    /// (e.g. changing nodes of edges, contracting nodes) cannot be
    13351335    /// restored. These events invalidate the snapshot.
    13361336    class Snapshot {
     
    13481348        using NodeNotifier::ObserverBase::detach;
    13491349        using NodeNotifier::ObserverBase::attached;
    1350        
     1350
    13511351      protected:
    1352        
     1352
    13531353        virtual void add(const Node& node) {
    13541354          snapshot.addNode(node);
     
    13701370          Node node;
    13711371          std::vector<Node> nodes;
    1372           for (notifier()->first(node); node != INVALID; 
     1372          for (notifier()->first(node); node != INVALID;
    13731373               notifier()->next(node)) {
    13741374            nodes.push_back(node);
     
    13801380        virtual void clear() {
    13811381          Node node;
    1382           for (notifier()->first(node); node != INVALID; 
     1382          for (notifier()->first(node); node != INVALID;
    13831383               notifier()->next(node)) {
    13841384            snapshot.eraseNode(node);
     
    13981398        using EdgeNotifier::ObserverBase::detach;
    13991399        using EdgeNotifier::ObserverBase::attached;
    1400        
     1400
    14011401      protected:
    14021402
     
    14201420          Edge edge;
    14211421          std::vector<Edge> edges;
    1422           for (notifier()->first(edge); edge != INVALID; 
     1422          for (notifier()->first(edge); edge != INVALID;
    14231423               notifier()->next(edge)) {
    14241424            edges.push_back(edge);
     
    14301430        virtual void clear() {
    14311431          Edge edge;
    1432           for (notifier()->first(edge); edge != INVALID; 
     1432          for (notifier()->first(edge); edge != INVALID;
    14331433               notifier()->next(edge)) {
    14341434            snapshot.eraseEdge(edge);
     
    14491449
    14501450      void addNode(const Node& node) {
    1451         added_nodes.push_front(node);       
     1451        added_nodes.push_front(node);
    14521452      }
    14531453      void eraseNode(const Node& node) {
    1454         std::list<Node>::iterator it = 
     1454        std::list<Node>::iterator it =
    14551455          std::find(added_nodes.begin(), added_nodes.end(), node);
    14561456        if (it == added_nodes.end()) {
     
    14641464
    14651465      void addEdge(const Edge& edge) {
    1466         added_edges.push_front(edge);       
     1466        added_edges.push_front(edge);
    14671467      }
    14681468      void eraseEdge(const Edge& edge) {
    1469         std::list<Edge>::iterator it = 
     1469        std::list<Edge>::iterator it =
    14701470          std::find(added_edges.begin(), added_edges.end(), edge);
    14711471        if (it == added_edges.end()) {
     
    14791479
    14801480      void attach(ListGraph &_graph) {
    1481         graph = &_graph;
    1482         node_observer_proxy.attach(graph->notifier(Node()));
     1481        graph = &_graph;
     1482        node_observer_proxy.attach(graph->notifier(Node()));
    14831483        edge_observer_proxy.attach(graph->notifier(Edge()));
    14841484      }
    1485            
     1485
    14861486      void detach() {
    1487         node_observer_proxy.detach();
    1488         edge_observer_proxy.detach();
     1487        node_observer_proxy.detach();
     1488        edge_observer_proxy.detach();
    14891489      }
    14901490
     
    14951495      void clear() {
    14961496        added_nodes.clear();
    1497         added_edges.clear();       
     1497        added_edges.clear();
    14981498      }
    14991499
     
    15041504      /// Default constructor.
    15051505      /// To actually make a snapshot you must call save().
    1506       Snapshot() 
    1507         : graph(0), node_observer_proxy(*this), 
     1506      Snapshot()
     1507        : graph(0), node_observer_proxy(*this),
    15081508          edge_observer_proxy(*this) {}
    1509      
     1509
    15101510      /// \brief Constructor that immediately makes a snapshot.
    1511       ///     
     1511      ///
    15121512      /// This constructor immediately makes a snapshot of the graph.
    15131513      /// \param _graph The graph we make a snapshot of.
    1514       Snapshot(ListGraph &_graph) 
    1515         : node_observer_proxy(*this), 
     1514      Snapshot(ListGraph &_graph)
     1515        : node_observer_proxy(*this),
    15161516          edge_observer_proxy(*this) {
    1517         attach(_graph);
    1518       }
    1519      
     1517        attach(_graph);
     1518      }
     1519
    15201520      /// \brief Make a snapshot.
    15211521      ///
     
    15321532        attach(_graph);
    15331533      }
    1534      
     1534
    15351535      /// \brief Undo the changes until the last snapshot.
    1536       // 
     1536      //
    15371537      /// Undo the changes until the last snapshot created by save().
    15381538      void restore() {
    1539         detach();
    1540         for(std::list<Edge>::iterator it = added_edges.begin();
     1539        detach();
     1540        for(std::list<Edge>::iterator it = added_edges.begin();
    15411541            it != added_edges.end(); ++it) {
    1542           graph->erase(*it);
    1543         }
    1544         for(std::list<Node>::iterator it = added_nodes.begin();
     1542          graph->erase(*it);
     1543        }
     1544        for(std::list<Node>::iterator it = added_nodes.begin();
    15451545            it != added_nodes.end(); ++it) {
    1546           graph->erase(*it);
    1547         }
     1546          graph->erase(*it);
     1547        }
    15481548        clear();
    15491549      }
     
    15571557    };
    15581558  };
    1559  
    1560   /// @} 
     1559
     1560  /// @}
    15611561} //namespace lemon
    1562  
     1562
    15631563
    15641564#endif
Note: See TracChangeset for help on using the changeset viewer.