COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/list_graph.h

    r73 r39  
    1717 */
    1818
    19 #ifndef LEMON_LIST_GRAPH_H
    20 #define LEMON_LIST_GRAPH_H
    21 
    22 ///\ingroup graphs
    23 ///\file
    24 ///\brief ListDigraph, ListGraph classes.
    25 
    26 #include <lemon/bits/graph_extender.h>
    27 
    28 #include <vector>
    29 #include <list>
    30 
    31 namespace lemon {
    32 
    33   class ListDigraphBase {
    34 
    35   protected:
    36     struct NodeT {
    37       int first_in, first_out;
    38       int prev, next;
    39     };
    40  
    41     struct ArcT {
    42       int target, source;
    43       int prev_in, prev_out;
    44       int next_in, next_out;
    45     };
    46 
    47     std::vector<NodeT> nodes;
    48 
    49     int first_node;
    50 
    51     int first_free_node;
    52 
    53     std::vector<ArcT> arcs;
    54 
    55     int first_free_arc;
    56    
    57   public:
    58    
    59     typedef ListDigraphBase Digraph;
    60    
    61     class Node {
    62       friend class ListDigraphBase;
    63     protected:
    64 
    65       int id;
    66       explicit Node(int pid) { id = pid;}
    67 
    68     public:
    69       Node() {}
    70       Node (Invalid) { id = -1; }
    71       bool operator==(const Node& node) const {return id == node.id;}
    72       bool operator!=(const Node& node) const {return id != node.id;}
    73       bool operator<(const Node& node) const {return id < node.id;}
    74     };
    75 
    76     class Arc {
    77       friend class ListDigraphBase;
    78     protected:
    79 
    80       int id;
    81       explicit Arc(int pid) { id = pid;}
    82 
    83     public:
    84       Arc() {}
    85       Arc (Invalid) { id = -1; }
    86       bool operator==(const Arc& arc) const {return id == arc.id;}
    87       bool operator!=(const Arc& arc) const {return id != arc.id;}
    88       bool operator<(const Arc& arc) const {return id < arc.id;}
    89     };
    90 
    91 
    92 
    93     ListDigraphBase()
    94       : nodes(), first_node(-1),
    95         first_free_node(-1), arcs(), first_free_arc(-1) {}
    96 
    97    
    98     int maxNodeId() const { return nodes.size()-1; }
    99     int maxArcId() const { return arcs.size()-1; }
    100 
    101     Node source(Arc e) const { return Node(arcs[e.id].source); }
    102     Node target(Arc e) const { return Node(arcs[e.id].target); }
    103 
    104 
    105     void first(Node& node) const {
    106       node.id = first_node;
    107     }
    108 
    109     void next(Node& node) const {
    110       node.id = nodes[node.id].next;
    111     }
    112 
    113 
    114     void first(Arc& arc) const {
    115       int n;
    116       for(n = first_node;
    117           n!=-1 && nodes[n].first_in == -1;
    118           n = nodes[n].next);
    119       arc.id = (n == -1) ? -1 : nodes[n].first_in;
    120     }
    121 
    122     void next(Arc& arc) const {
    123       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       }     
    132     }
    133 
    134     void firstOut(Arc &e, const Node& v) const {
    135       e.id = nodes[v.id].first_out;
    136     }
    137     void nextOut(Arc &e) const {
    138       e.id=arcs[e.id].next_out;
    139     }
    140 
    141     void firstIn(Arc &e, const Node& v) const {
    142       e.id = nodes[v.id].first_in;
    143     }
    144     void nextIn(Arc &e) const {
    145       e.id=arcs[e.id].next_in;
    146     }
    147 
    148    
    149     static int id(Node v) { return v.id; }
    150     static int id(Arc e) { return e.id; }
    151 
    152     static Node nodeFromId(int id) { return Node(id);}
    153     static Arc arcFromId(int id) { return Arc(id);}
    154 
    155     Node addNode() {     
    156       int n;
    157      
    158       if(first_free_node==-1) {
    159         n = nodes.size();
    160         nodes.push_back(NodeT());
    161       } else {
    162         n = first_free_node;
    163         first_free_node = nodes[n].next;
    164       }
    165      
    166       nodes[n].next = first_node;
    167       if(first_node != -1) nodes[first_node].prev = n;
    168       first_node = n;
    169       nodes[n].prev = -1;
    170      
    171       nodes[n].first_in = nodes[n].first_out = -1;
    172      
    173       return Node(n);
    174     }
    175    
    176     Arc addArc(Node u, Node v) {
    177       int n;     
    178 
    179       if (first_free_arc == -1) {
    180         n = arcs.size();
    181         arcs.push_back(ArcT());
    182       } else {
    183         n = first_free_arc;
    184         first_free_arc = arcs[n].next_in;
    185       }
    186      
    187       arcs[n].source = u.id;
    188       arcs[n].target = v.id;
    189 
    190       arcs[n].next_out = nodes[u.id].first_out;
    191       if(nodes[u.id].first_out != -1) {
    192         arcs[nodes[u.id].first_out].prev_out = n;
    193       }
    194      
    195       arcs[n].next_in = nodes[v.id].first_in;
    196       if(nodes[v.id].first_in != -1) {
    197         arcs[nodes[v.id].first_in].prev_in = n;
    198       }
    199      
    200       arcs[n].prev_in = arcs[n].prev_out = -1;
    201        
    202       nodes[u.id].first_out = nodes[v.id].first_in = n;
    203 
    204       return Arc(n);
    205     }
    206    
    207     void erase(const Node& node) {
    208       int n = node.id;
    209      
    210       if(nodes[n].next != -1) {
    211         nodes[nodes[n].next].prev = nodes[n].prev;
    212       }
    213      
    214       if(nodes[n].prev != -1) {
    215         nodes[nodes[n].prev].next = nodes[n].next;
    216       } else {
    217         first_node = nodes[n].next;
    218       }
    219      
    220       nodes[n].next = first_free_node;
    221       first_free_node = n;
    222 
    223     }
    224    
    225     void erase(const Arc& arc) {
    226       int n = arc.id;
    227      
    228       if(arcs[n].next_in!=-1) {
    229         arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
    230       }
    231 
    232       if(arcs[n].prev_in!=-1) {
    233         arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
    234       } else {
    235         nodes[arcs[n].target].first_in = arcs[n].next_in;
    236       }
    237 
    238      
    239       if(arcs[n].next_out!=-1) {
    240         arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
    241       }
    242 
    243       if(arcs[n].prev_out!=-1) {
    244         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
    245       } else {
    246         nodes[arcs[n].source].first_out = arcs[n].next_out;
    247       }
    248      
    249       arcs[n].next_in = first_free_arc;
    250       first_free_arc = n;     
    251 
    252     }
    253 
    254     void clear() {
    255       arcs.clear();
    256       nodes.clear();
    257       first_node = first_free_node = first_free_arc = -1;
    258     }
    259 
    260   protected:
    261     void changeTarget(Arc e, Node n)
    262     {
    263       if(arcs[e.id].next_in != -1)
    264         arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;
    265       if(arcs[e.id].prev_in != -1)
    266         arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;
    267       else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in;
    268       if (nodes[n.id].first_in != -1) {
    269         arcs[nodes[n.id].first_in].prev_in = e.id;
    270       }
    271       arcs[e.id].target = n.id;
    272       arcs[e.id].prev_in = -1;
    273       arcs[e.id].next_in = nodes[n.id].first_in;
    274       nodes[n.id].first_in = e.id;
    275     }
    276     void changeSource(Arc e, Node n)
    277     {
    278       if(arcs[e.id].next_out != -1)
    279         arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;
    280       if(arcs[e.id].prev_out != -1)
    281         arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;
    282       else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out;
    283       if (nodes[n.id].first_out != -1) {
    284         arcs[nodes[n.id].first_out].prev_out = e.id;
    285       }
    286       arcs[e.id].source = n.id;
    287       arcs[e.id].prev_out = -1;
    288       arcs[e.id].next_out = nodes[n.id].first_out;
    289       nodes[n.id].first_out = e.id;
    290     }
    291 
    292   };
    293 
    294   typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
    295 
    296   /// \addtogroup graphs
    297   /// @{
    298 
    299   ///A general directed graph structure.
    300 
    301   ///\ref ListDigraph is a simple and fast <em>directed graph</em>
    302   ///implementation based on static linked lists that are stored in
    303   ///\c std::vector structures.   
    304   ///
    305   ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
    306   ///also provides several useful additional functionalities.
    307   ///Most of the member functions and nested classes are documented
    308   ///only in the concept class.
    309   ///
    310   ///An important extra feature of this digraph implementation is that
    311   ///its maps are real \ref concepts::ReferenceMap "reference map"s.
    312   ///
    313   ///\sa concepts::Digraph
    314 
    315   class ListDigraph : public ExtendedListDigraphBase {
    316   private:
    317     ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
    318    
    319     ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
    320     ///
    321     ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
    322     ///\brief Assignment of ListDigraph to another one is \e not allowed.
    323     ///Use copyDigraph() instead.
    324 
    325     ///Assignment of ListDigraph to another one is \e not allowed.
    326     ///Use copyDigraph() instead.
    327     void operator=(const ListDigraph &) {}
    328   public:
    329 
    330     typedef ExtendedListDigraphBase Parent;
    331 
    332     /// Constructor
    333    
    334     /// Constructor.
    335     ///
    336     ListDigraph() {}
    337 
    338     ///Add a new node to the digraph.
    339    
    340     ///Add a new node to the digraph.
    341     ///\return the new node.
    342     Node addNode() { return Parent::addNode(); }
    343 
    344     ///Add a new arc to the digraph.
    345    
    346     ///Add a new arc to the digraph with source node \c s
    347     ///and target node \c t.
    348     ///\return the new arc.
    349     Arc addArc(const Node& s, const Node& t) {
    350       return Parent::addArc(s, t);
    351     }
    352 
    353     /// Change the target of \c e to \c n
    354 
    355     /// Change the target of \c e to \c n
    356     ///
    357     ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
    358     ///the changed arc remain valid. However <tt>InArcIt</tt>s are
    359     ///invalidated.
    360     ///
    361     ///\warning This functionality cannot be used together with the Snapshot
    362     ///feature.
    363     void changeTarget(Arc e, Node n) {
    364       Parent::changeTarget(e,n);
    365     }
    366     /// Change the source of \c e to \c n
    367 
    368     /// Change the source of \c e to \c n
    369     ///
    370     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing
    371     ///the changed arc remain valid. However <tt>OutArcIt</tt>s are
    372     ///invalidated.
    373     ///
    374     ///\warning This functionality cannot be used together with the Snapshot
    375     ///feature.
    376     void changeSource(Arc e, Node n) {
    377       Parent::changeSource(e,n);
    378     }
    379 
    380     /// Invert the direction of an arc.
    381 
    382     ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
    383     ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
    384     ///invalidated.
    385     ///
    386     ///\warning This functionality cannot be used together with the Snapshot
    387     ///feature.
    388     void reverseArc(Arc e) {
    389       Node t=target(e);
    390       changeTarget(e,source(e));
    391       changeSource(e,t);
    392     }
    393 
    394     /// Reserve memory for nodes.
    395 
    396     /// Using this function it is possible to avoid the superfluous memory
    397     /// allocation: if you know that the digraph you want to build will
    398     /// be very large (e.g. it will contain millions of nodes and/or arcs)
    399     /// then it is worth reserving space for this amount before starting
    400     /// to build the digraph.
    401     /// \sa reserveArc
    402     void reserveNode(int n) { nodes.reserve(n); };
    403 
    404     /// Reserve memory for arcs.
    405 
    406     /// Using this function it is possible to avoid the superfluous memory
    407     /// allocation: if you know that the digraph you want to build will
    408     /// be very large (e.g. it will contain millions of nodes and/or arcs)
    409     /// then it is worth reserving space for this amount before starting
    410     /// to build the digraph.
    411     /// \sa reserveNode
    412     void reserveArc(int m) { arcs.reserve(m); };
    413 
    414     ///Contract two nodes.
    415 
    416     ///This function contracts two nodes.
    417     ///Node \p b will be removed but instead of deleting
    418     ///incident arcs, they will be joined to \p a.
    419     ///The last parameter \p r controls whether to remove loops. \c true
    420     ///means that loops will be removed.
    421     ///
    422     ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
    423     ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
    424     ///may be invalidated.
    425     ///
    426     ///\warning This functionality cannot be used together with the Snapshot
    427     ///feature.
    428     void contract(Node a, Node b, bool r = true)
    429     {
    430       for(OutArcIt e(*this,b);e!=INVALID;) {
    431         OutArcIt f=e;
    432         ++f;
    433         if(r && target(e)==a) erase(e);
    434         else changeSource(e,a);
    435         e=f;
    436       }
    437       for(InArcIt e(*this,b);e!=INVALID;) {
    438         InArcIt f=e;
    439         ++f;
    440         if(r && source(e)==a) erase(e);
    441         else changeTarget(e,a);
    442         e=f;
    443       }
    444       erase(b);
    445     }
    446 
    447     ///Split a node.
    448 
    449     ///This function splits a node. First a new node is added to the digraph,
    450     ///then the source of each outgoing arc of \c n is moved to this new node.
    451     ///If \c connect is \c true (this is the default value), then a new arc
    452     ///from \c n to the newly created node is also added.
    453     ///\return The newly created node.
    454     ///
    455     ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
    456     ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
    457     ///be invalidated. 
    458     ///
    459     ///\warning This functionality cannot be used together with the
    460     ///Snapshot feature.
    461     ///
    462     ///\todo It could be implemented in a bit faster way.
    463     Node split(Node n, bool connect = true) {
    464       Node b = addNode();
    465       for(OutArcIt e(*this,n);e!=INVALID;) {
    466         OutArcIt f=e;
    467         ++f;
    468         changeSource(e,b);
    469         e=f;
    470       }
    471       if (connect) addArc(n,b);
    472       return b;
    473     }
    474      
    475     ///Split an arc.
    476 
    477     ///This function splits an arc. First a new node \c b is added to
    478     ///the digraph, then the original arc is re-targeted to \c
    479     ///b. Finally an arc from \c b to the original target is added.
    480     ///
    481     ///\return The newly created node.
    482     ///
    483     ///\warning This functionality cannot be used together with the
    484     ///Snapshot feature.
    485     Node split(Arc e) {
    486       Node b = addNode();
    487       addArc(b,target(e));
    488       changeTarget(e,b);
    489       return b;
    490     }
    491      
    492     /// \brief Class to make a snapshot of the digraph and restore
    493     /// it later.
    494     ///
    495     /// Class to make a snapshot of the digraph and restore it later.
    496     ///
    497     /// The newly added nodes and arcs can be removed using the
    498     /// restore() function.
    499     ///
    500     /// \warning Arc and node deletions and other modifications (e.g.
    501     /// contracting, splitting, reversing arcs or nodes) cannot be
    502     /// restored. These events invalidate the snapshot.
    503     class Snapshot {
    504     protected:
    505 
    506       typedef Parent::NodeNotifier NodeNotifier;
    507 
    508       class NodeObserverProxy : public NodeNotifier::ObserverBase {
    509       public:
    510 
    511         NodeObserverProxy(Snapshot& _snapshot)
    512           : snapshot(_snapshot) {}
    513 
    514         using NodeNotifier::ObserverBase::attach;
    515         using NodeNotifier::ObserverBase::detach;
    516         using NodeNotifier::ObserverBase::attached;
    517        
    518       protected:
    519        
    520         virtual void add(const Node& node) {
    521           snapshot.addNode(node);
    522         }
    523         virtual void add(const std::vector<Node>& nodes) {
    524           for (int i = nodes.size() - 1; i >= 0; ++i) {
    525             snapshot.addNode(nodes[i]);
    526           }
    527         }
    528         virtual void erase(const Node& node) {
    529           snapshot.eraseNode(node);
    530         }
    531         virtual void erase(const std::vector<Node>& nodes) {
    532           for (int i = 0; i < int(nodes.size()); ++i) {
    533             snapshot.eraseNode(nodes[i]);
    534           }
    535         }
    536         virtual void build() {
    537           Node node;
    538           std::vector<Node> nodes;
    539           for (notifier()->first(node); node != INVALID;
    540                notifier()->next(node)) {
    541             nodes.push_back(node);
    542           }
    543           for (int i = nodes.size() - 1; i >= 0; --i) {
    544             snapshot.addNode(nodes[i]);
    545           }
    546         }
    547         virtual void clear() {
    548           Node node;
    549           for (notifier()->first(node); node != INVALID;
    550                notifier()->next(node)) {
    551             snapshot.eraseNode(node);
    552           }
    553         }
    554 
    555         Snapshot& snapshot;
    556       };
    557 
    558       class ArcObserverProxy : public ArcNotifier::ObserverBase {
    559       public:
    560 
    561         ArcObserverProxy(Snapshot& _snapshot)
    562           : snapshot(_snapshot) {}
    563 
    564         using ArcNotifier::ObserverBase::attach;
    565         using ArcNotifier::ObserverBase::detach;
    566         using ArcNotifier::ObserverBase::attached;
    567        
    568       protected:
    569 
    570         virtual void add(const Arc& arc) {
    571           snapshot.addArc(arc);
    572         }
    573         virtual void add(const std::vector<Arc>& arcs) {
    574           for (int i = arcs.size() - 1; i >= 0; ++i) {
    575             snapshot.addArc(arcs[i]);
    576           }
    577         }
    578         virtual void erase(const Arc& arc) {
    579           snapshot.eraseArc(arc);
    580         }
    581         virtual void erase(const std::vector<Arc>& arcs) {
    582           for (int i = 0; i < int(arcs.size()); ++i) {
    583             snapshot.eraseArc(arcs[i]);
    584           }
    585         }
    586         virtual void build() {
    587           Arc arc;
    588           std::vector<Arc> arcs;
    589           for (notifier()->first(arc); arc != INVALID;
    590                notifier()->next(arc)) {
    591             arcs.push_back(arc);
    592           }
    593           for (int i = arcs.size() - 1; i >= 0; --i) {
    594             snapshot.addArc(arcs[i]);
    595           }
    596         }
    597         virtual void clear() {
    598           Arc arc;
    599           for (notifier()->first(arc); arc != INVALID;
    600                notifier()->next(arc)) {
    601             snapshot.eraseArc(arc);
    602           }
    603         }
    604 
    605         Snapshot& snapshot;
    606       };
    607      
    608       ListDigraph *digraph;
    609 
    610       NodeObserverProxy node_observer_proxy;
    611       ArcObserverProxy arc_observer_proxy;
    612 
    613       std::list<Node> added_nodes;
    614       std::list<Arc> added_arcs;
    615 
    616 
    617       void addNode(const Node& node) {
    618         added_nodes.push_front(node);       
    619       }
    620       void eraseNode(const Node& node) {
    621         std::list<Node>::iterator it =
    622           std::find(added_nodes.begin(), added_nodes.end(), node);
    623         if (it == added_nodes.end()) {
    624           clear();
    625           arc_observer_proxy.detach();
    626           throw NodeNotifier::ImmediateDetach();
    627         } else {
    628           added_nodes.erase(it);
    629         }
    630       }
    631 
    632       void addArc(const Arc& arc) {
    633         added_arcs.push_front(arc);       
    634       }
    635       void eraseArc(const Arc& arc) {
    636         std::list<Arc>::iterator it =
    637           std::find(added_arcs.begin(), added_arcs.end(), arc);
    638         if (it == added_arcs.end()) {
    639           clear();
    640           node_observer_proxy.detach();
    641           throw ArcNotifier::ImmediateDetach();
    642         } else {
    643           added_arcs.erase(it);
    644         }       
    645       }
    646 
    647       void attach(ListDigraph &_digraph) {
    648         digraph = &_digraph;
    649         node_observer_proxy.attach(digraph->notifier(Node()));
    650         arc_observer_proxy.attach(digraph->notifier(Arc()));
    651       }
    652            
    653       void detach() {
    654         node_observer_proxy.detach();
    655         arc_observer_proxy.detach();
    656       }
    657 
    658       bool attached() const {
    659         return node_observer_proxy.attached();
    660       }
    661 
    662       void clear() {
    663         added_nodes.clear();
    664         added_arcs.clear();       
    665       }
    666 
    667     public:
    668 
    669       /// \brief Default constructor.
    670       ///
    671       /// Default constructor.
    672       /// To actually make a snapshot you must call save().
    673       Snapshot()
    674         : digraph(0), node_observer_proxy(*this),
    675           arc_observer_proxy(*this) {}
    676      
    677       /// \brief Constructor that immediately makes a snapshot.
    678       ///     
    679       /// This constructor immediately makes a snapshot of the digraph.
    680       /// \param _digraph The digraph we make a snapshot of.
    681       Snapshot(ListDigraph &_digraph)
    682         : node_observer_proxy(*this),
    683           arc_observer_proxy(*this) {
    684         attach(_digraph);
    685       }
    686      
    687       /// \brief Make a snapshot.
    688       ///
    689       /// Make a snapshot of the digraph.
    690       ///
    691       /// This function can be called more than once. In case of a repeated
    692       /// call, the previous snapshot gets lost.
    693       /// \param _digraph The digraph we make the snapshot of.
    694       void save(ListDigraph &_digraph) {
    695         if (attached()) {
    696           detach();
    697           clear();
    698         }
    699         attach(_digraph);
    700       }
    701      
    702       /// \brief Undo the changes until the last snapshot.
    703       //
    704       /// Undo the changes until the last snapshot created by save().
    705       void restore() {
    706         detach();
    707         for(std::list<Arc>::iterator it = added_arcs.begin();
    708             it != added_arcs.end(); ++it) {
    709           digraph->erase(*it);
    710         }
    711         for(std::list<Node>::iterator it = added_nodes.begin();
    712             it != added_nodes.end(); ++it) {
    713           digraph->erase(*it);
    714         }
    715         clear();
    716       }
    717 
    718       /// \brief Gives back true when the snapshot is valid.
    719       ///
    720       /// Gives back true when the snapshot is valid.
    721       bool valid() const {
    722         return attached();
    723       }
    724     };
    725    
    726   };
    727 
    728   ///@}
    729 
    730   class ListGraphBase {
    731 
    732   protected:
    733 
    734     struct NodeT {
    735       int first_out;
    736       int prev, next;
    737     };
    738  
    739     struct ArcT {
    740       int target;
    741       int prev_out, next_out;
    742     };
    743 
    744     std::vector<NodeT> nodes;
    745 
    746     int first_node;
    747 
    748     int first_free_node;
    749 
    750     std::vector<ArcT> arcs;
    751 
    752     int first_free_arc;
    753    
    754   public:
    755    
    756     typedef ListGraphBase Digraph;
    757 
    758     class Node;
    759     class Arc;
    760     class Edge;
    761    
    762     class Node {
    763       friend class ListGraphBase;
    764     protected:
    765 
    766       int id;
    767       explicit Node(int pid) { id = pid;}
    768 
    769     public:
    770       Node() {}
    771       Node (Invalid) { id = -1; }
    772       bool operator==(const Node& node) const {return id == node.id;}
    773       bool operator!=(const Node& node) const {return id != node.id;}
    774       bool operator<(const Node& node) const {return id < node.id;}
    775     };
    776 
    777     class Edge {
    778       friend class ListGraphBase;
    779     protected:
    780 
    781       int id;
    782       explicit Edge(int pid) { id = pid;}
    783 
    784     public:
    785       Edge() {}
    786       Edge (Invalid) { id = -1; }
    787       bool operator==(const Edge& edge) const {return id == edge.id;}
    788       bool operator!=(const Edge& edge) const {return id != edge.id;}
    789       bool operator<(const Edge& edge) const {return id < edge.id;}
    790     };
    791 
    792     class Arc {
    793       friend class ListGraphBase;
    794     protected:
    795 
    796       int id;
    797       explicit Arc(int pid) { id = pid;}
    798 
    799     public:
    800       operator Edge() const { return edgeFromId(id / 2); }
    801 
    802       Arc() {}
    803       Arc (Invalid) { id = -1; }
    804       bool operator==(const Arc& arc) const {return id == arc.id;}
    805       bool operator!=(const Arc& arc) const {return id != arc.id;}
    806       bool operator<(const Arc& arc) const {return id < arc.id;}
    807     };
    808 
    809 
    810 
    811     ListGraphBase()
    812       : nodes(), first_node(-1),
    813         first_free_node(-1), arcs(), first_free_arc(-1) {}
    814 
    815    
    816     int maxNodeId() const { return nodes.size()-1; }
    817     int maxEdgeId() const { return arcs.size() / 2 - 1; }
    818     int maxArcId() const { return arcs.size()-1; }
    819 
    820     Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
    821     Node target(Arc e) const { return Node(arcs[e.id].target); }
    822 
    823     Node u(Edge e) const { return Node(arcs[2 * e.id].target); }
    824     Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
    825 
    826     static bool direction(Arc e) {
    827       return (e.id & 1) == 1;
    828     }
    829 
    830     static Arc direct(Edge e, bool d) {
    831       return Arc(e.id * 2 + (d ? 1 : 0));
    832     }
    833 
    834     void first(Node& node) const {
    835       node.id = first_node;
    836     }
    837 
    838     void next(Node& node) const {
    839       node.id = nodes[node.id].next;
    840     }
    841 
    842     void first(Arc& e) const {
    843       int n = first_node;
    844       while (n != -1 && nodes[n].first_out == -1) {
    845         n = nodes[n].next;
    846       }
    847       e.id = (n == -1) ? -1 : nodes[n].first_out;
    848     }
    849 
    850     void next(Arc& e) const {
    851       if (arcs[e.id].next_out != -1) {
    852         e.id = arcs[e.id].next_out;
    853       } else {
    854         int n = nodes[arcs[e.id ^ 1].target].next;
    855         while(n != -1 && nodes[n].first_out == -1) {
    856           n = nodes[n].next;
    857         }
    858         e.id = (n == -1) ? -1 : nodes[n].first_out;
    859       }     
    860     }
    861 
    862     void first(Edge& e) const {
    863       int n = first_node;
    864       while (n != -1) {
    865         e.id = nodes[n].first_out;
    866         while ((e.id & 1) != 1) {
    867           e.id = arcs[e.id].next_out;
    868         }
    869         if (e.id != -1) {
    870           e.id /= 2;
    871           return;
    872         }
    873         n = nodes[n].next;
    874       }
    875       e.id = -1;
    876     }
    877 
    878     void next(Edge& e) const {
    879       int n = arcs[e.id * 2].target;
    880       e.id = arcs[(e.id * 2) | 1].next_out;
    881       while ((e.id & 1) != 1) {
    882         e.id = arcs[e.id].next_out;
    883       }
    884       if (e.id != -1) {
    885         e.id /= 2;
    886         return;
    887       }
    888       n = nodes[n].next;
    889       while (n != -1) {
    890         e.id = nodes[n].first_out;
    891         while ((e.id & 1) != 1) {
    892           e.id = arcs[e.id].next_out;
    893         }
    894         if (e.id != -1) {
    895           e.id /= 2;
    896           return;
    897         }
    898         n = nodes[n].next;
    899       }
    900       e.id = -1;
    901     }
    902 
    903     void firstOut(Arc &e, const Node& v) const {
    904       e.id = nodes[v.id].first_out;
    905     }
    906     void nextOut(Arc &e) const {
    907       e.id = arcs[e.id].next_out;
    908     }
    909 
    910     void firstIn(Arc &e, const Node& v) const {
    911       e.id = ((nodes[v.id].first_out) ^ 1);
    912       if (e.id == -2) e.id = -1;
    913     }
    914     void nextIn(Arc &e) const {
    915       e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
    916       if (e.id == -2) e.id = -1;
    917     }
    918 
    919     void firstInc(Edge &e, bool& d, const Node& v) const {
    920       int a = nodes[v.id].first_out;
    921       if (a != -1 ) {
    922         e.id = a / 2;
    923         d = ((a & 1) == 1);
    924       } else {
    925         e.id = -1;
    926         d = true;
    927       }
    928     }
    929     void nextInc(Edge &e, bool& d) const {
    930       int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
    931       if (a != -1 ) {
    932         e.id = a / 2;
    933         d = ((a & 1) == 1);
    934       } else {
    935         e.id = -1;
    936         d = true;
    937       }
    938     }
    939    
    940     static int id(Node v) { return v.id; }
    941     static int id(Arc e) { return e.id; }
    942     static int id(Edge e) { return e.id; }
    943 
    944     static Node nodeFromId(int id) { return Node(id);}
    945     static Arc arcFromId(int id) { return Arc(id);}
    946     static Edge edgeFromId(int id) { return Edge(id);}
    947 
    948     Node addNode() {     
    949       int n;
    950      
    951       if(first_free_node==-1) {
    952         n = nodes.size();
    953         nodes.push_back(NodeT());
    954       } else {
    955         n = first_free_node;
    956         first_free_node = nodes[n].next;
    957       }
    958      
    959       nodes[n].next = first_node;
    960       if (first_node != -1) nodes[first_node].prev = n;
    961       first_node = n;
    962       nodes[n].prev = -1;
    963      
    964       nodes[n].first_out = -1;
    965      
    966       return Node(n);
    967     }
    968    
    969     Edge addEdge(Node u, Node v) {
    970       int n;     
    971 
    972       if (first_free_arc == -1) {
    973         n = arcs.size();
    974         arcs.push_back(ArcT());
    975         arcs.push_back(ArcT());
    976       } else {
    977         n = first_free_arc;
    978         first_free_arc = arcs[n].next_out;
    979       }
    980      
    981       arcs[n].target = u.id;
    982       arcs[n | 1].target = v.id;
    983 
    984       arcs[n].next_out = nodes[v.id].first_out;
    985       if (nodes[v.id].first_out != -1) {
    986         arcs[nodes[v.id].first_out].prev_out = n;
    987       }     
    988       arcs[n].prev_out = -1;
    989       nodes[v.id].first_out = n;
    990      
    991       arcs[n | 1].next_out = nodes[u.id].first_out;
    992       if (nodes[u.id].first_out != -1) {
    993         arcs[nodes[u.id].first_out].prev_out = (n | 1);
    994       }
    995       arcs[n | 1].prev_out = -1;     
    996       nodes[u.id].first_out = (n | 1);
    997 
    998       return Edge(n / 2);
    999     }
    1000    
    1001     void erase(const Node& node) {
    1002       int n = node.id;
    1003      
    1004       if(nodes[n].next != -1) {
    1005         nodes[nodes[n].next].prev = nodes[n].prev;
    1006       }
    1007      
    1008       if(nodes[n].prev != -1) {
    1009         nodes[nodes[n].prev].next = nodes[n].next;
    1010       } else {
    1011         first_node = nodes[n].next;
    1012       }
    1013      
    1014       nodes[n].next = first_free_node;
    1015       first_free_node = n;
    1016 
    1017     }
    1018    
    1019     void erase(const Edge& edge) {
    1020       int n = edge.id * 2;
    1021      
    1022       if (arcs[n].next_out != -1) {
    1023         arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
    1024       }
    1025 
    1026       if (arcs[n].prev_out != -1) {
    1027         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
    1028       } else {
    1029         nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
    1030       }
    1031 
    1032       if (arcs[n | 1].next_out != -1) {
    1033         arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
    1034       }
    1035 
    1036       if (arcs[n | 1].prev_out != -1) {
    1037         arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
    1038       } else {
    1039         nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
    1040       }
    1041      
    1042       arcs[n].next_out = first_free_arc;
    1043       first_free_arc = n;     
    1044 
    1045     }
    1046 
    1047     void clear() {
    1048       arcs.clear();
    1049       nodes.clear();
    1050       first_node = first_free_node = first_free_arc = -1;
    1051     }
    1052 
    1053   protected:
    1054 
    1055     void changeTarget(Edge e, Node n) {
    1056       if(arcs[2 * e.id].next_out != -1) {
    1057         arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
    1058       }
    1059       if(arcs[2 * e.id].prev_out != -1) {
    1060         arcs[arcs[2 * e.id].prev_out].next_out =
    1061           arcs[2 * e.id].next_out;
    1062       } else {
    1063         nodes[arcs[(2 * e.id) | 1].target].first_out =
    1064           arcs[2 * e.id].next_out;
    1065       }
    1066 
    1067       if (nodes[n.id].first_out != -1) {
    1068         arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
    1069       }
    1070       arcs[(2 * e.id) | 1].target = n.id;
    1071       arcs[2 * e.id].prev_out = -1;
    1072       arcs[2 * e.id].next_out = nodes[n.id].first_out;
    1073       nodes[n.id].first_out = 2 * e.id;
    1074     }
    1075 
    1076     void changeSource(Edge e, Node n) {
    1077       if(arcs[(2 * e.id) | 1].next_out != -1) {
    1078         arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
    1079           arcs[(2 * e.id) | 1].prev_out;
    1080       }
    1081       if(arcs[(2 * e.id) | 1].prev_out != -1) {
    1082         arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
    1083           arcs[(2 * e.id) | 1].next_out;
    1084       } else {
    1085         nodes[arcs[2 * e.id].target].first_out =
    1086           arcs[(2 * e.id) | 1].next_out;
    1087       }
    1088 
    1089       if (nodes[n.id].first_out != -1) {
    1090         arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
    1091       }
    1092       arcs[2 * e.id].target = n.id;
    1093       arcs[(2 * e.id) | 1].prev_out = -1;
    1094       arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
    1095       nodes[n.id].first_out = ((2 * e.id) | 1);
    1096     }
    1097 
    1098   };
    1099 
    1100   typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
    1101 
    1102 
    1103   /// \addtogroup graphs
    1104   /// @{
    1105 
    1106   ///A general undirected graph structure.
    1107 
    1108   ///\ref ListGraph is a simple and fast <em>undirected graph</em>
    1109   ///implementation based on static linked lists that are stored in
    1110   ///\c std::vector structures.
    1111   ///
    1112   ///It conforms to the \ref concepts::Graph "Graph concept" and it
    1113   ///also provides several useful additional functionalities.
    1114   ///Most of the member functions and nested classes are documented
    1115   ///only in the concept class.
    1116   ///
    1117   ///An important extra feature of this graph implementation is that
    1118   ///its maps are real \ref concepts::ReferenceMap "reference map"s.
    1119   ///
    1120   ///\sa concepts::Graph
    1121 
    1122   class ListGraph : public ExtendedListGraphBase {
    1123   private:
    1124     ///ListGraph is \e not copy constructible. Use copyGraph() instead.
    1125 
    1126     ///ListGraph is \e not copy constructible. Use copyGraph() instead.
    1127     ///
    1128     ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
    1129     ///\brief Assignment of ListGraph to another one is \e not allowed.
    1130     ///Use copyGraph() instead.
    1131 
    1132     ///Assignment of ListGraph to another one is \e not allowed.
    1133     ///Use copyGraph() instead.
    1134     void operator=(const ListGraph &) {}
    1135   public:
    1136     /// Constructor
    1137    
    1138     /// Constructor.
    1139     ///
    1140     ListGraph() {}
    1141 
    1142     typedef ExtendedListGraphBase Parent;
    1143 
    1144     typedef Parent::OutArcIt IncEdgeIt;
    1145 
    1146     /// \brief Add a new node to the graph.
    1147     ///
    1148     /// Add a new node to the graph.
    1149     /// \return the new node.
    1150     Node addNode() { return Parent::addNode(); }
    1151 
    1152     /// \brief Add a new edge to the graph.
    1153     ///
    1154     /// Add a new edge to the graph with source node \c s
    1155     /// and target node \c t.
    1156     /// \return the new edge.
    1157     Edge addEdge(const Node& s, const Node& t) {
    1158       return Parent::addEdge(s, t);
    1159     }
    1160     /// \brief Change the source of \c e to \c n
    1161     ///
    1162     /// This function changes the source of \c e to \c n.
    1163     ///
    1164     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
    1165     ///referencing the changed arc remain
    1166     ///valid. However <tt>OutArcIt</tt>s are invalidated.
    1167     ///
    1168     ///\warning This functionality cannot be used together with the
    1169     ///Snapshot feature.
    1170     void changeSource(Edge e, Node n) {
    1171       Parent::changeSource(e,n);
    1172     }   
    1173     /// \brief Change the target of \c e to \c n
    1174     ///
    1175     /// This function changes the target of \c e to \c n.
    1176     ///
    1177     /// \note The <tt>ArcIt</tt>s referencing the changed arc remain
    1178     /// valid. However the other iterators may be invalidated.
    1179     ///
    1180     ///\warning This functionality cannot be used together with the
    1181     ///Snapshot feature.
    1182     void changeTarget(Edge e, Node n) {
    1183       Parent::changeTarget(e,n);
    1184     }
    1185     /// \brief Change the source of \c e to \c n
    1186     ///
    1187     /// This function changes the source of \c e to \c n.
    1188     /// It also changes the proper node of the represented edge.
    1189     ///
    1190     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
    1191     ///referencing the changed arc remain
    1192     ///valid. However <tt>OutArcIt</tt>s are invalidated.
    1193     ///
    1194     ///\warning This functionality cannot be used together with the
    1195     ///Snapshot feature.
    1196     void changeSource(Arc e, Node n) {
    1197       if (Parent::direction(e)) {
    1198         Parent::changeSource(e,n);
    1199       } else {
    1200         Parent::changeTarget(e,n);
    1201       }
    1202     }
    1203     /// \brief Change the target of \c e to \c n
    1204     ///
    1205     /// This function changes the target of \c e to \c n.
    1206     /// It also changes the proper node of the represented edge.
    1207     ///
    1208     ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s
    1209     ///referencing the changed arc remain
    1210     ///valid. However <tt>InArcIt</tt>s are invalidated.
    1211     ///
    1212     ///\warning This functionality cannot be used together with the
    1213     ///Snapshot feature.
    1214     void changeTarget(Arc e, Node n) {
    1215       if (Parent::direction(e)) {
    1216         Parent::changeTarget(e,n);
    1217       } else {
    1218         Parent::changeSource(e,n);
    1219       }
    1220     }
    1221     /// \brief Contract two nodes.
    1222     ///
    1223     /// This function contracts two nodes.
    1224     /// Node \p b will be removed but instead of deleting
    1225     /// its neighboring arcs, they will be joined to \p a.
    1226     /// The last parameter \p r controls whether to remove loops. \c true
    1227     /// means that loops will be removed.
    1228     ///
    1229     /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
    1230     /// valid.
    1231     ///
    1232     ///\warning This functionality cannot be used together with the
    1233     ///Snapshot feature.
    1234     void contract(Node a, Node b, bool r = true) {
    1235       for(IncEdgeIt e(*this, b); e!=INVALID;) {
    1236         IncEdgeIt f = e; ++f;
    1237         if (r && runningNode(e) == a) {
    1238           erase(e);
    1239         } else if (source(e) == b) {
    1240           changeSource(e, a);
    1241         } else {
    1242           changeTarget(e, a);
    1243         }
    1244         e = f;
    1245       }
    1246       erase(b);
    1247     }
    1248 
    1249 
    1250     /// \brief Class to make a snapshot of the graph and restore
    1251     /// it later.
    1252     ///
    1253     /// Class to make a snapshot of the graph and restore it later.
    1254     ///
    1255     /// The newly added nodes and edges can be removed
    1256     /// using the restore() function.
    1257     ///
    1258     /// \warning Edge and node deletions and other modifications
    1259     /// (e.g. changing nodes of edges, contracting nodes) cannot be
    1260     /// restored. These events invalidate the snapshot.
    1261     class Snapshot {
    1262     protected:
    1263 
    1264       typedef Parent::NodeNotifier NodeNotifier;
    1265 
    1266       class NodeObserverProxy : public NodeNotifier::ObserverBase {
    1267       public:
    1268 
    1269         NodeObserverProxy(Snapshot& _snapshot)
    1270           : snapshot(_snapshot) {}
    1271 
    1272         using NodeNotifier::ObserverBase::attach;
    1273         using NodeNotifier::ObserverBase::detach;
    1274         using NodeNotifier::ObserverBase::attached;
    1275        
    1276       protected:
    1277        
    1278         virtual void add(const Node& node) {
    1279           snapshot.addNode(node);
    1280         }
    1281         virtual void add(const std::vector<Node>& nodes) {
    1282           for (int i = nodes.size() - 1; i >= 0; ++i) {
    1283             snapshot.addNode(nodes[i]);
    1284           }
    1285         }
    1286         virtual void erase(const Node& node) {
    1287           snapshot.eraseNode(node);
    1288         }
    1289         virtual void erase(const std::vector<Node>& nodes) {
    1290           for (int i = 0; i < int(nodes.size()); ++i) {
    1291             snapshot.eraseNode(nodes[i]);
    1292           }
    1293         }
    1294         virtual void build() {
    1295           Node node;
    1296           std::vector<Node> nodes;
    1297           for (notifier()->first(node); node != INVALID;
    1298                notifier()->next(node)) {
    1299             nodes.push_back(node);
    1300           }
    1301           for (int i = nodes.size() - 1; i >= 0; --i) {
    1302             snapshot.addNode(nodes[i]);
    1303           }
    1304         }
    1305         virtual void clear() {
    1306           Node node;
    1307           for (notifier()->first(node); node != INVALID;
    1308                notifier()->next(node)) {
    1309             snapshot.eraseNode(node);
    1310           }
    1311         }
    1312 
    1313         Snapshot& snapshot;
    1314       };
    1315 
    1316       class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
    1317       public:
    1318 
    1319         EdgeObserverProxy(Snapshot& _snapshot)
    1320           : snapshot(_snapshot) {}
    1321 
    1322         using EdgeNotifier::ObserverBase::attach;
    1323         using EdgeNotifier::ObserverBase::detach;
    1324         using EdgeNotifier::ObserverBase::attached;
    1325        
    1326       protected:
    1327 
    1328         virtual void add(const Edge& edge) {
    1329           snapshot.addEdge(edge);
    1330         }
    1331         virtual void add(const std::vector<Edge>& edges) {
    1332           for (int i = edges.size() - 1; i >= 0; ++i) {
    1333             snapshot.addEdge(edges[i]);
    1334           }
    1335         }
    1336         virtual void erase(const Edge& edge) {
    1337           snapshot.eraseEdge(edge);
    1338         }
    1339         virtual void erase(const std::vector<Edge>& edges) {
    1340           for (int i = 0; i < int(edges.size()); ++i) {
    1341             snapshot.eraseEdge(edges[i]);
    1342           }
    1343         }
    1344         virtual void build() {
    1345           Edge edge;
    1346           std::vector<Edge> edges;
    1347           for (notifier()->first(edge); edge != INVALID;
    1348                notifier()->next(edge)) {
    1349             edges.push_back(edge);
    1350           }
    1351           for (int i = edges.size() - 1; i >= 0; --i) {
    1352             snapshot.addEdge(edges[i]);
    1353           }
    1354         }
    1355         virtual void clear() {
    1356           Edge edge;
    1357           for (notifier()->first(edge); edge != INVALID;
    1358                notifier()->next(edge)) {
    1359             snapshot.eraseEdge(edge);
    1360           }
    1361         }
    1362 
    1363         Snapshot& snapshot;
    1364       };
    1365 
    1366       ListGraph *graph;
    1367 
    1368       NodeObserverProxy node_observer_proxy;
    1369       EdgeObserverProxy edge_observer_proxy;
    1370 
    1371       std::list<Node> added_nodes;
    1372       std::list<Edge> added_edges;
    1373 
    1374 
    1375       void addNode(const Node& node) {
    1376         added_nodes.push_front(node);       
    1377       }
    1378       void eraseNode(const Node& node) {
    1379         std::list<Node>::iterator it =
    1380           std::find(added_nodes.begin(), added_nodes.end(), node);
    1381         if (it == added_nodes.end()) {
    1382           clear();
    1383           edge_observer_proxy.detach();
    1384           throw NodeNotifier::ImmediateDetach();
    1385         } else {
    1386           added_nodes.erase(it);
    1387         }
    1388       }
    1389 
    1390       void addEdge(const Edge& edge) {
    1391         added_edges.push_front(edge);       
    1392       }
    1393       void eraseEdge(const Edge& edge) {
    1394         std::list<Edge>::iterator it =
    1395           std::find(added_edges.begin(), added_edges.end(), edge);
    1396         if (it == added_edges.end()) {
    1397           clear();
    1398           node_observer_proxy.detach();
    1399           throw EdgeNotifier::ImmediateDetach();
    1400         } else {
    1401           added_edges.erase(it);
    1402         }
    1403       }
    1404 
    1405       void attach(ListGraph &_graph) {
    1406         graph = &_graph;
    1407         node_observer_proxy.attach(graph->notifier(Node()));
    1408         edge_observer_proxy.attach(graph->notifier(Edge()));
    1409       }
    1410            
    1411       void detach() {
    1412         node_observer_proxy.detach();
    1413         edge_observer_proxy.detach();
    1414       }
    1415 
    1416       bool attached() const {
    1417         return node_observer_proxy.attached();
    1418       }
    1419 
    1420       void clear() {
    1421         added_nodes.clear();
    1422         added_edges.clear();       
    1423       }
    1424 
    1425     public:
    1426 
    1427       /// \brief Default constructor.
    1428       ///
    1429       /// Default constructor.
    1430       /// To actually make a snapshot you must call save().
    1431       Snapshot()
    1432         : graph(0), node_observer_proxy(*this),
    1433           edge_observer_proxy(*this) {}
    1434      
    1435       /// \brief Constructor that immediately makes a snapshot.
    1436       ///     
    1437       /// This constructor immediately makes a snapshot of the graph.
    1438       /// \param _graph The graph we make a snapshot of.
    1439       Snapshot(ListGraph &_graph)
    1440         : node_observer_proxy(*this),
    1441           edge_observer_proxy(*this) {
    1442         attach(_graph);
    1443       }
    1444      
    1445       /// \brief Make a snapshot.
    1446       ///
    1447       /// Make a snapshot of the graph.
    1448       ///
    1449       /// This function can be called more than once. In case of a repeated
    1450       /// call, the previous snapshot gets lost.
    1451       /// \param _graph The graph we make the snapshot of.
    1452       void save(ListGraph &_graph) {
    1453         if (attached()) {
    1454           detach();
    1455           clear();
    1456         }
    1457         attach(_graph);
    1458       }
    1459      
    1460       /// \brief Undo the changes until the last snapshot.
    1461       //
    1462       /// Undo the changes until the last snapshot created by save().
    1463       void restore() {
    1464         detach();
    1465         for(std::list<Edge>::iterator it = added_edges.begin();
    1466             it != added_edges.end(); ++it) {
    1467           graph->erase(*it);
    1468         }
    1469         for(std::list<Node>::iterator it = added_nodes.begin();
    1470             it != added_nodes.end(); ++it) {
    1471           graph->erase(*it);
    1472         }
    1473         clear();
    1474       }
    1475 
    1476       /// \brief Gives back true when the snapshot is valid.
    1477       ///
    1478       /// Gives back true when the snapshot is valid.
    1479       bool valid() const {
    1480         return attached();
    1481       }
    1482     };
    1483   };
    1484  
    1485   /// @} 
    1486 } //namespace lemon
    1487  
    1488 
    1489 #endif
Note: See TracChangeset for help on using the changeset viewer.