COIN-OR::LEMON - Graph Library

Changeset 788:10c9c3a35b83 in lemon


Ignore:
Timestamp:
09/30/09 08:36:43 (15 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
787:819ca5b50de0 (diff), 786:32baeb8e5c8f (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/list_graph.h

    r786 r788  
    2222///\ingroup graphs
    2323///\file
    24 ///\brief ListDigraph, ListGraph classes.
     24///\brief ListDigraph and ListGraph classes.
    2525
    2626#include <lemon/core.h>
     
    3232
    3333namespace lemon {
     34
     35  class ListDigraph;
    3436
    3537  class ListDigraphBase {
     
    6365    class Node {
    6466      friend class ListDigraphBase;
     67      friend class ListDigraph;
    6568    protected:
    6669
     
    7881    class Arc {
    7982      friend class ListDigraphBase;
     83      friend class ListDigraph;
    8084    protected:
    8185
     
    312316  ///A general directed graph structure.
    313317
    314   ///\ref ListDigraph is a simple and fast <em>directed graph</em>
    315   ///implementation based on static linked lists that are stored in
     318  ///\ref ListDigraph is a versatile and fast directed graph
     319  ///implementation based on linked lists that are stored in
    316320  ///\c std::vector structures.
    317321  ///
    318   ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
    319   ///also provides several useful additional functionalities.
    320   ///Most of the member functions and nested classes are documented
     322  ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"
     323  ///and it also provides several useful additional functionalities.
     324  ///Most of its member functions and nested classes are documented
    321325  ///only in the concept class.
    322326  ///
    323327  ///\sa concepts::Digraph
    324 
     328  ///\sa ListGraph
    325329  class ListDigraph : public ExtendedListDigraphBase {
    326330    typedef ExtendedListDigraphBase Parent;
    327331
    328332  private:
    329     ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
    330 
    331     ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
    332     ///
     333    /// Digraphs are \e not copy constructible. Use DigraphCopy instead.
    333334    ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
    334     ///\brief Assignment of ListDigraph to another one is \e not allowed.
    335     ///Use copyDigraph() instead.
    336 
    337     ///Assignment of ListDigraph to another one is \e not allowed.
    338     ///Use copyDigraph() instead.
     335    /// \brief Assignment of a digraph to another one is \e not allowed.
     336    /// Use DigraphCopy instead.
    339337    void operator=(const ListDigraph &) {}
    340338  public:
     
    348346    ///Add a new node to the digraph.
    349347
    350     ///Add a new node to the digraph.
     348    ///This function adds a new node to the digraph.
    351349    ///\return The new node.
    352350    Node addNode() { return Parent::addNode(); }
     
    354352    ///Add a new arc to the digraph.
    355353
    356     ///Add a new arc to the digraph with source node \c s
     354    ///This function adds a new arc to the digraph with source node \c s
    357355    ///and target node \c t.
    358356    ///\return The new arc.
    359     Arc addArc(const Node& s, const Node& t) {
     357    Arc addArc(Node s, Node t) {
    360358      return Parent::addArc(s, t);
    361359    }
     
    363361    ///\brief Erase a node from the digraph.
    364362    ///
    365     ///Erase a node from the digraph.
    366     ///
    367     void erase(const Node& n) { Parent::erase(n); }
     363    ///This function erases the given node from the digraph.
     364    void erase(Node n) { Parent::erase(n); }
    368365
    369366    ///\brief Erase an arc from the digraph.
    370367    ///
    371     ///Erase an arc from the digraph.
    372     ///
    373     void erase(const Arc& a) { Parent::erase(a); }
     368    ///This function erases the given arc from the digraph.
     369    void erase(Arc a) { Parent::erase(a); }
    374370
    375371    /// Node validity check
    376372
    377     /// This function gives back true if the given node is valid,
    378     /// ie. it is a real node of the graph.
    379     ///
    380     /// \warning A Node pointing to a removed item
    381     /// could become valid again later if new nodes are
    382     /// added to the graph.
     373    /// This function gives back \c true if the given node is valid,
     374    /// i.e. it is a real node of the digraph.
     375    ///
     376    /// \warning A removed node could become valid again if new nodes are
     377    /// added to the digraph.
    383378    bool valid(Node n) const { return Parent::valid(n); }
    384379
    385380    /// Arc validity check
    386381
    387     /// This function gives back true if the given arc is valid,
    388     /// ie. it is a real arc of the graph.
    389     ///
    390     /// \warning An Arc pointing to a removed item
    391     /// could become valid again later if new nodes are
    392     /// added to the graph.
     382    /// This function gives back \c true if the given arc is valid,
     383    /// i.e. it is a real arc of the digraph.
     384    ///
     385    /// \warning A removed arc could become valid again if new arcs are
     386    /// added to the digraph.
    393387    bool valid(Arc a) const { return Parent::valid(a); }
    394388
    395     /// Change the target of \c a to \c n
    396 
    397     /// Change the target of \c a to \c n
    398     ///
    399     ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
    400     ///the changed arc remain valid. However <tt>InArcIt</tt>s are
    401     ///invalidated.
     389    /// Change the target node of an arc
     390
     391    /// This function changes the target node of the given arc \c a to \c n.
     392    ///
     393    ///\note \c ArcIt and \c OutArcIt iterators referencing the changed
     394    ///arc remain valid, however \c InArcIt iterators are invalidated.
    402395    ///
    403396    ///\warning This functionality cannot be used together with the Snapshot
     
    406399      Parent::changeTarget(a,n);
    407400    }
    408     /// Change the source of \c a to \c n
    409 
    410     /// Change the source of \c a to \c n
    411     ///
    412     ///\note The <tt>InArcIt</tt>s referencing the changed arc remain
    413     ///valid. However the <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s are
    414     ///invalidated.
     401    /// Change the source node of an arc
     402
     403    /// This function changes the source node of the given arc \c a to \c n.
     404    ///
     405    ///\note \c InArcIt iterators referencing the changed arc remain
     406    ///valid, however \c ArcIt and \c OutArcIt iterators are invalidated.
    415407    ///
    416408    ///\warning This functionality cannot be used together with the Snapshot
     
    420412    }
    421413
    422     /// Invert the direction of an arc.
    423 
    424     ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
    425     ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
    426     ///invalidated.
     414    /// Reverse the direction of an arc.
     415
     416    /// This function reverses the direction of the given arc.
     417    ///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing
     418    ///the changed arc are invalidated.
    427419    ///
    428420    ///\warning This functionality cannot be used together with the Snapshot
    429421    ///feature.
    430     void reverseArc(Arc e) {
    431       Node t=target(e);
    432       changeTarget(e,source(e));
    433       changeSource(e,t);
    434     }
    435 
    436     /// Reserve memory for nodes.
    437 
    438     /// Using this function it is possible to avoid the superfluous memory
    439     /// allocation: if you know that the digraph you want to build will
    440     /// be very large (e.g. it will contain millions of nodes and/or arcs)
    441     /// then it is worth reserving space for this amount before starting
    442     /// to build the digraph.
    443     /// \sa reserveArc
    444     void reserveNode(int n) { nodes.reserve(n); };
    445 
    446     /// Reserve memory for arcs.
    447 
    448     /// Using this function it is possible to avoid the superfluous memory
    449     /// allocation: if you know that the digraph you want to build will
    450     /// be very large (e.g. it will contain millions of nodes and/or arcs)
    451     /// then it is worth reserving space for this amount before starting
    452     /// to build the digraph.
    453     /// \sa reserveNode
    454     void reserveArc(int m) { arcs.reserve(m); };
     422    void reverseArc(Arc a) {
     423      Node t=target(a);
     424      changeTarget(a,source(a));
     425      changeSource(a,t);
     426    }
    455427
    456428    ///Contract two nodes.
    457429
    458     ///This function contracts two nodes.
    459     ///Node \p b will be removed but instead of deleting
    460     ///incident arcs, they will be joined to \p a.
    461     ///The last parameter \p r controls whether to remove loops. \c true
    462     ///means that loops will be removed.
    463     ///
    464     ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
    465     ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
    466     ///may be invalidated.
     430    ///This function contracts the given two nodes.
     431    ///Node \c v is removed, but instead of deleting its
     432    ///incident arcs, they are joined to node \c u.
     433    ///If the last parameter \c r is \c true (this is the default value),
     434    ///then the newly created loops are removed.
     435    ///
     436    ///\note The moved arcs are joined to node \c u using changeSource()
     437    ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are
     438    ///invalidated for the outgoing arcs of node \c v and \c InArcIt
     439    ///iterators are invalidated for the incomming arcs of \c v.
     440    ///Moreover all iterators referencing node \c v or the removed
     441    ///loops are also invalidated. Other iterators remain valid.
    467442    ///
    468443    ///\warning This functionality cannot be used together with the Snapshot
    469444    ///feature.
    470     void contract(Node a, Node b, bool r = true)
     445    void contract(Node u, Node v, bool r = true)
    471446    {
    472       for(OutArcIt e(*this,b);e!=INVALID;) {
     447      for(OutArcIt e(*this,v);e!=INVALID;) {
    473448        OutArcIt f=e;
    474449        ++f;
    475         if(r && target(e)==a) erase(e);
    476         else changeSource(e,a);
     450        if(r && target(e)==u) erase(e);
     451        else changeSource(e,u);
    477452        e=f;
    478453      }
    479       for(InArcIt e(*this,b);e!=INVALID;) {
     454      for(InArcIt e(*this,v);e!=INVALID;) {
    480455        InArcIt f=e;
    481456        ++f;
    482         if(r && source(e)==a) erase(e);
    483         else changeTarget(e,a);
     457        if(r && source(e)==u) erase(e);
     458        else changeTarget(e,u);
    484459        e=f;
    485460      }
    486       erase(b);
     461      erase(v);
    487462    }
    488463
    489464    ///Split a node.
    490465
    491     ///This function splits a node. First a new node is added to the digraph,
    492     ///then the source of each outgoing arc of \c n is moved to this new node.
    493     ///If \c connect is \c true (this is the default value), then a new arc
    494     ///from \c n to the newly created node is also added.
     466    ///This function splits the given node. First, a new node is added
     467    ///to the digraph, then the source of each outgoing arc of node \c n
     468    ///is moved to this new node.
     469    ///If the second parameter \c connect is \c true (this is the default
     470    ///value), then a new arc from node \c n to the newly created node
     471    ///is also added.
    495472    ///\return The newly created node.
    496473    ///
    497     ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
    498     ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
    499     ///be invalidated.
    500     ///
    501     ///\warning This functionality cannot be used in conjunction with the
     474    ///\note All iterators remain valid.
     475    ///
     476    ///\warning This functionality cannot be used together with the
    502477    ///Snapshot feature.
    503478    Node split(Node n, bool connect = true) {
    504479      Node b = addNode();
    505       for(OutArcIt e(*this,n);e!=INVALID;) {
    506         OutArcIt f=e;
    507         ++f;
    508         changeSource(e,b);
    509         e=f;
     480      nodes[b.id].first_out=nodes[n.id].first_out;
     481      nodes[n.id].first_out=-1;
     482      for(int i=nodes[b.id].first_out; i!=-1; i=arcs[i].next_out) {
     483        arcs[i].source=b.id;
    510484      }
    511485      if (connect) addArc(n,b);
     
    515489    ///Split an arc.
    516490
    517     ///This function splits an arc. First a new node \c b is added to
    518     ///the digraph, then the original arc is re-targeted to \c
    519     ///b. Finally an arc from \c b to the original target is added.
    520     ///
     491    ///This function splits the given arc. First, a new node \c v is
     492    ///added to the digraph, then the target node of the original arc
     493    ///is set to \c v. Finally, an arc from \c v to the original target
     494    ///is added.
    521495    ///\return The newly created node.
     496    ///
     497    ///\note \c InArcIt iterators referencing the original arc are
     498    ///invalidated. Other iterators remain valid.
    522499    ///
    523500    ///\warning This functionality cannot be used together with the
    524501    ///Snapshot feature.
    525     Node split(Arc e) {
    526       Node b = addNode();
    527       addArc(b,target(e));
    528       changeTarget(e,b);
    529       return b;
    530     }
     502    Node split(Arc a) {
     503      Node v = addNode();
     504      addArc(v,target(a));
     505      changeTarget(a,v);
     506      return v;
     507    }
     508
     509    ///Clear the digraph.
     510
     511    ///This function erases all nodes and arcs from the digraph.
     512    ///
     513    void clear() {
     514      Parent::clear();
     515    }
     516
     517    /// Reserve memory for nodes.
     518
     519    /// Using this function, it is possible to avoid superfluous memory
     520    /// allocation: if you know that the digraph you want to build will
     521    /// be large (e.g. it will contain millions of nodes and/or arcs),
     522    /// then it is worth reserving space for this amount before starting
     523    /// to build the digraph.
     524    /// \sa reserveArc()
     525    void reserveNode(int n) { nodes.reserve(n); };
     526
     527    /// Reserve memory for arcs.
     528
     529    /// Using this function, it is possible to avoid superfluous memory
     530    /// allocation: if you know that the digraph you want to build will
     531    /// be large (e.g. it will contain millions of nodes and/or arcs),
     532    /// then it is worth reserving space for this amount before starting
     533    /// to build the digraph.
     534    /// \sa reserveNode()
     535    void reserveArc(int m) { arcs.reserve(m); };
    531536
    532537    /// \brief Class to make a snapshot of the digraph and restore
     
    538543    /// restore() function.
    539544    ///
    540     /// \warning Arc and node deletions and other modifications (e.g.
    541     /// contracting, splitting, reversing arcs or nodes) cannot be
     545    /// \note After a state is restored, you cannot restore a later state,
     546    /// i.e. you cannot add the removed nodes and arcs again using
     547    /// another Snapshot instance.
     548    ///
     549    /// \warning Node and arc deletions and other modifications (e.g.
     550    /// reversing, contracting, splitting arcs or nodes) cannot be
    542551    /// restored. These events invalidate the snapshot.
     552    /// However the arcs and nodes that were added to the digraph after
     553    /// making the current snapshot can be removed without invalidating it.
    543554    class Snapshot {
    544555    protected:
     
    710721      ///
    711722      /// Default constructor.
    712       /// To actually make a snapshot you must call save().
     723      /// You have to call save() to actually make a snapshot.
    713724      Snapshot()
    714725        : digraph(0), node_observer_proxy(*this),
     
    717728      /// \brief Constructor that immediately makes a snapshot.
    718729      ///
    719       /// This constructor immediately makes a snapshot of the digraph.
    720       /// \param _digraph The digraph we make a snapshot of.
    721       Snapshot(ListDigraph &_digraph)
     730      /// This constructor immediately makes a snapshot of the given digraph.
     731      Snapshot(ListDigraph &gr)
    722732        : node_observer_proxy(*this),
    723733          arc_observer_proxy(*this) {
    724         attach(_digraph);
     734        attach(gr);
    725735      }
    726736
    727737      /// \brief Make a snapshot.
    728738      ///
    729       /// Make a snapshot of the digraph.
    730       ///
    731       /// This function can be called more than once. In case of a repeated
     739      /// This function makes a snapshot of the given digraph.
     740      /// It can be called more than once. In case of a repeated
    732741      /// call, the previous snapshot gets lost.
    733       /// \param _digraph The digraph we make the snapshot of.
    734       void save(ListDigraph &_digraph) {
     742      void save(ListDigraph &gr) {
    735743        if (attached()) {
    736744          detach();
    737745          clear();
    738746        }
    739         attach(_digraph);
     747        attach(gr);
    740748      }
    741749
    742750      /// \brief Undo the changes until the last snapshot.
    743       //
    744       /// Undo the changes until the last snapshot created by save().
     751      ///
     752      /// This function undos the changes until the last snapshot
     753      /// created by save() or Snapshot(ListDigraph&).
     754      ///
     755      /// \warning This method invalidates the snapshot, i.e. repeated
     756      /// restoring is not supported unless you call save() again.
    745757      void restore() {
    746758        detach();
     
    756768      }
    757769
    758       /// \brief Gives back true when the snapshot is valid.
     770      /// \brief Returns \c true if the snapshot is valid.
    759771      ///
    760       /// Gives back true when the snapshot is valid.
     772      /// This function returns \c true if the snapshot is valid.
    761773      bool valid() const {
    762774        return attached();
     
    795807
    796808    typedef ListGraphBase Graph;
    797 
    798     class Node;
    799     class Arc;
    800     class Edge;
    801809
    802810    class Node {
     
    848856      bool operator<(const Arc& arc) const {return id < arc.id;}
    849857    };
    850 
    851 
    852858
    853859    ListGraphBase()
     
    11651171  ///A general undirected graph structure.
    11661172
    1167   ///\ref ListGraph is a simple and fast <em>undirected graph</em>
    1168   ///implementation based on static linked lists that are stored in
     1173  ///\ref ListGraph is a versatile and fast undirected graph
     1174  ///implementation based on linked lists that are stored in
    11691175  ///\c std::vector structures.
    11701176  ///
    1171   ///It conforms to the \ref concepts::Graph "Graph concept" and it
    1172   ///also provides several useful additional functionalities.
    1173   ///Most of the member functions and nested classes are documented
     1177  ///This type fully conforms to the \ref concepts::Graph "Graph concept"
     1178  ///and it also provides several useful additional functionalities.
     1179  ///Most of its member functions and nested classes are documented
    11741180  ///only in the concept class.
    11751181  ///
    11761182  ///\sa concepts::Graph
    1177 
     1183  ///\sa ListDigraph
    11781184  class ListGraph : public ExtendedListGraphBase {
    11791185    typedef ExtendedListGraphBase Parent;
    11801186
    11811187  private:
    1182     ///ListGraph is \e not copy constructible. Use copyGraph() instead.
    1183 
    1184     ///ListGraph is \e not copy constructible. Use copyGraph() instead.
    1185     ///
     1188    /// Graphs are \e not copy constructible. Use GraphCopy instead.
    11861189    ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
    1187     ///\brief Assignment of ListGraph to another one is \e not allowed.
    1188     ///Use copyGraph() instead.
    1189 
    1190     ///Assignment of ListGraph to another one is \e not allowed.
    1191     ///Use copyGraph() instead.
     1190    /// \brief Assignment of a graph to another one is \e not allowed.
     1191    /// Use GraphCopy instead.
    11921192    void operator=(const ListGraph &) {}
    11931193  public:
     
    12021202    /// \brief Add a new node to the graph.
    12031203    ///
    1204     /// Add a new node to the graph.
     1204    /// This function adds a new node to the graph.
    12051205    /// \return The new node.
    12061206    Node addNode() { return Parent::addNode(); }
     
    12081208    /// \brief Add a new edge to the graph.
    12091209    ///
    1210     /// Add a new edge to the graph with source node \c s
    1211     /// and target node \c t.
     1210    /// This function adds a new edge to the graph between nodes
     1211    /// \c u and \c v with inherent orientation from node \c u to
     1212    /// node \c v.
    12121213    /// \return The new edge.
    1213     Edge addEdge(const Node& s, const Node& t) {
    1214       return Parent::addEdge(s, t);
    1215     }
    1216 
    1217     /// \brief Erase a node from the graph.
    1218     ///
    1219     /// Erase a node from the graph.
    1220     ///
    1221     void erase(const Node& n) { Parent::erase(n); }
    1222 
    1223     /// \brief Erase an edge from the graph.
    1224     ///
    1225     /// Erase an edge from the graph.
    1226     ///
    1227     void erase(const Edge& e) { Parent::erase(e); }
     1214    Edge addEdge(Node u, Node v) {
     1215      return Parent::addEdge(u, v);
     1216    }
     1217
     1218    ///\brief Erase a node from the graph.
     1219    ///
     1220    /// This function erases the given node from the graph.
     1221    void erase(Node n) { Parent::erase(n); }
     1222
     1223    ///\brief Erase an edge from the graph.
     1224    ///
     1225    /// This function erases the given edge from the graph.
     1226    void erase(Edge e) { Parent::erase(e); }
    12281227    /// Node validity check
    12291228
    1230     /// This function gives back true if the given node is valid,
    1231     /// ie. it is a real node of the graph.
    1232     ///
    1233     /// \warning A Node pointing to a removed item
    1234     /// could become valid again later if new nodes are
     1229    /// This function gives back \c true if the given node is valid,
     1230    /// i.e. it is a real node of the graph.
     1231    ///
     1232    /// \warning A removed node could become valid again if new nodes are
    12351233    /// added to the graph.
    12361234    bool valid(Node n) const { return Parent::valid(n); }
     1235    /// Edge validity check
     1236
     1237    /// This function gives back \c true if the given edge is valid,
     1238    /// i.e. it is a real edge of the graph.
     1239    ///
     1240    /// \warning A removed edge could become valid again if new edges are
     1241    /// added to the graph.
     1242    bool valid(Edge e) const { return Parent::valid(e); }
    12371243    /// Arc validity check
    12381244
    1239     /// This function gives back true if the given arc is valid,
    1240     /// ie. it is a real arc of the graph.
    1241     ///
    1242     /// \warning An Arc pointing to a removed item
    1243     /// could become valid again later if new edges are
     1245    /// This function gives back \c true if the given arc is valid,
     1246    /// i.e. it is a real arc of the graph.
     1247    ///
     1248    /// \warning A removed arc could become valid again if new edges are
    12441249    /// added to the graph.
    12451250    bool valid(Arc a) const { return Parent::valid(a); }
    1246     /// Edge validity check
    1247 
    1248     /// This function gives back true if the given edge is valid,
    1249     /// ie. it is a real arc of the graph.
    1250     ///
    1251     /// \warning A Edge pointing to a removed item
    1252     /// could become valid again later if new edges are
    1253     /// added to the graph.
    1254     bool valid(Edge e) const { return Parent::valid(e); }
    1255     /// \brief Change the end \c u of \c e to \c n
    1256     ///
    1257     /// This function changes the end \c u of \c e to node \c n.
    1258     ///
    1259     ///\note The <tt>EdgeIt</tt>s and <tt>ArcIt</tt>s referencing the
    1260     ///changed edge are invalidated and if the changed node is the
    1261     ///base node of an iterator then this iterator is also
    1262     ///invalidated.
     1251
     1252    /// \brief Change the first node of an edge.
     1253    ///
     1254    /// This function changes the first node of the given edge \c e to \c n.
     1255    ///
     1256    ///\note \c EdgeIt and \c ArcIt iterators referencing the
     1257    ///changed edge are invalidated and all other iterators whose
     1258    ///base node is the changed node are also invalidated.
    12631259    ///
    12641260    ///\warning This functionality cannot be used together with the
     
    12671263      Parent::changeU(e,n);
    12681264    }
    1269     /// \brief Change the end \c v of \c e to \c n
    1270     ///
    1271     /// This function changes the end \c v of \c e to \c n.
    1272     ///
    1273     ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
    1274     ///valid, however <tt>ArcIt</tt>s and if the changed node is the
    1275     ///base node of an iterator then this iterator is invalidated.
     1265    /// \brief Change the second node of an edge.
     1266    ///
     1267    /// This function changes the second node of the given edge \c e to \c n.
     1268    ///
     1269    ///\note \c EdgeIt iterators referencing the changed edge remain
     1270    ///valid, however \c ArcIt iterators referencing the changed edge and
     1271    ///all other iterators whose base node is the changed node are also
     1272    ///invalidated.
    12761273    ///
    12771274    ///\warning This functionality cannot be used together with the
     
    12801277      Parent::changeV(e,n);
    12811278    }
     1279
    12821280    /// \brief Contract two nodes.
    12831281    ///
    1284     /// This function contracts two nodes.
    1285     /// Node \p b will be removed but instead of deleting
    1286     /// its neighboring arcs, they will be joined to \p a.
    1287     /// The last parameter \p r controls whether to remove loops. \c true
    1288     /// means that loops will be removed.
    1289     ///
    1290     /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
    1291     /// valid.
     1282    /// This function contracts the given two nodes.
     1283    /// Node \c b is removed, but instead of deleting
     1284    /// its incident edges, they are joined to node \c a.
     1285    /// If the last parameter \c r is \c true (this is the default value),
     1286    /// then the newly created loops are removed.
     1287    ///
     1288    /// \note The moved edges are joined to node \c a using changeU()
     1289    /// or changeV(), thus all edge and arc iterators whose base node is
     1290    /// \c b are invalidated.
     1291    /// Moreover all iterators referencing node \c b or the removed
     1292    /// loops are also invalidated. Other iterators remain valid.
    12921293    ///
    12931294    ///\warning This functionality cannot be used together with the
     
    13081309    }
    13091310
     1311    ///Clear the graph.
     1312
     1313    ///This function erases all nodes and arcs from the graph.
     1314    ///
     1315    void clear() {
     1316      Parent::clear();
     1317    }
     1318
     1319    /// Reserve memory for nodes.
     1320
     1321    /// Using this function, it is possible to avoid superfluous memory
     1322    /// allocation: if you know that the graph you want to build will
     1323    /// be large (e.g. it will contain millions of nodes and/or edges),
     1324    /// then it is worth reserving space for this amount before starting
     1325    /// to build the graph.
     1326    /// \sa reserveEdge()
     1327    void reserveNode(int n) { nodes.reserve(n); };
     1328
     1329    /// Reserve memory for edges.
     1330
     1331    /// Using this function, it is possible to avoid superfluous memory
     1332    /// allocation: if you know that the graph you want to build will
     1333    /// be large (e.g. it will contain millions of nodes and/or edges),
     1334    /// then it is worth reserving space for this amount before starting
     1335    /// to build the graph.
     1336    /// \sa reserveNode()
     1337    void reserveEdge(int m) { arcs.reserve(2 * m); };
    13101338
    13111339    /// \brief Class to make a snapshot of the graph and restore
     
    13171345    /// using the restore() function.
    13181346    ///
    1319     /// \warning Edge and node deletions and other modifications
    1320     /// (e.g. changing nodes of edges, contracting nodes) cannot be
    1321     /// restored. These events invalidate the snapshot.
     1347    /// \note After a state is restored, you cannot restore a later state,
     1348    /// i.e. you cannot add the removed nodes and edges again using
     1349    /// another Snapshot instance.
     1350    ///
     1351    /// \warning Node and edge deletions and other modifications
     1352    /// (e.g. changing the end-nodes of edges or contracting nodes)
     1353    /// cannot be restored. These events invalidate the snapshot.
     1354    /// However the edges and nodes that were added to the graph after
     1355    /// making the current snapshot can be removed without invalidating it.
    13221356    class Snapshot {
    13231357    protected:
     
    14891523      ///
    14901524      /// Default constructor.
    1491       /// To actually make a snapshot you must call save().
     1525      /// You have to call save() to actually make a snapshot.
    14921526      Snapshot()
    14931527        : graph(0), node_observer_proxy(*this),
     
    14961530      /// \brief Constructor that immediately makes a snapshot.
    14971531      ///
    1498       /// This constructor immediately makes a snapshot of the graph.
    1499       /// \param _graph The graph we make a snapshot of.
    1500       Snapshot(ListGraph &_graph)
     1532      /// This constructor immediately makes a snapshot of the given graph.
     1533      Snapshot(ListGraph &gr)
    15011534        : node_observer_proxy(*this),
    15021535          edge_observer_proxy(*this) {
    1503         attach(_graph);
     1536        attach(gr);
    15041537      }
    15051538
    15061539      /// \brief Make a snapshot.
    15071540      ///
    1508       /// Make a snapshot of the graph.
    1509       ///
    1510       /// This function can be called more than once. In case of a repeated
     1541      /// This function makes a snapshot of the given graph.
     1542      /// It can be called more than once. In case of a repeated
    15111543      /// call, the previous snapshot gets lost.
    1512       /// \param _graph The graph we make the snapshot of.
    1513       void save(ListGraph &_graph) {
     1544      void save(ListGraph &gr) {
    15141545        if (attached()) {
    15151546          detach();
    15161547          clear();
    15171548        }
    1518         attach(_graph);
     1549        attach(gr);
    15191550      }
    15201551
    15211552      /// \brief Undo the changes until the last snapshot.
    1522       //
    1523       /// Undo the changes until the last snapshot created by save().
     1553      ///
     1554      /// This function undos the changes until the last snapshot
     1555      /// created by save() or Snapshot(ListGraph&).
     1556      ///
     1557      /// \warning This method invalidates the snapshot, i.e. repeated
     1558      /// restoring is not supported unless you call save() again.
    15241559      void restore() {
    15251560        detach();
     
    15351570      }
    15361571
    1537       /// \brief Gives back true when the snapshot is valid.
     1572      /// \brief Returns \c true if the snapshot is valid.
    15381573      ///
    1539       /// Gives back true when the snapshot is valid.
     1574      /// This function returns \c true if the snapshot is valid.
    15401575      bool valid() const {
    15411576        return attached();
  • lemon/list_graph.h

    r787 r788  
    121121      int n;
    122122      for(n = first_node;
    123           n!=-1 && nodes[n].first_in == -1;
     123          n != -1 && nodes[n].first_out == -1;
    124124          n = nodes[n].next) {}
    125       arc.id = (n == -1) ? -1 : nodes[n].first_in;
     125      arc.id = (n == -1) ? -1 : nodes[n].first_out;
    126126    }
    127127
    128128    void next(Arc& arc) const {
    129       if (arcs[arc.id].next_in != -1) {
    130         arc.id = arcs[arc.id].next_in;
     129      if (arcs[arc.id].next_out != -1) {
     130        arc.id = arcs[arc.id].next_out;
    131131      } else {
    132132        int n;
    133         for(n = nodes[arcs[arc.id].target].next;
    134             n!=-1 && nodes[n].first_in == -1;
     133        for(n = nodes[arcs[arc.id].source].next;
     134            n != -1 && nodes[n].first_out == -1;
    135135            n = nodes[n].next) {}
    136         arc.id = (n == -1) ? -1 : nodes[n].first_in;
     136        arc.id = (n == -1) ? -1 : nodes[n].first_out;
    137137      }
    138138    }
Note: See TracChangeset for help on using the changeset viewer.