lemon/list_graph.h
changeset 75 6265aa2f9d7e
parent 57 c1acf0018c0a
child 149 2f7ae34e1333
     1.1 --- a/lemon/list_graph.h	Fri Feb 08 13:42:11 2008 +0100
     1.2 +++ b/lemon/list_graph.h	Tue Feb 12 21:03:19 2008 +0000
     1.3 @@ -111,12 +111,12 @@
     1.4      }
     1.5  
     1.6  
     1.7 -    void first(Arc& e) const { 
     1.8 +    void first(Arc& arc) const { 
     1.9        int n;
    1.10        for(n = first_node; 
    1.11  	  n!=-1 && nodes[n].first_in == -1; 
    1.12  	  n = nodes[n].next);
    1.13 -      e.id = (n == -1) ? -1 : nodes[n].first_in;
    1.14 +      arc.id = (n == -1) ? -1 : nodes[n].first_in;
    1.15      }
    1.16  
    1.17      void next(Arc& arc) const {
    1.18 @@ -293,35 +293,37 @@
    1.19  
    1.20    typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
    1.21  
    1.22 -  /// \addtogroup digraphs
    1.23 +  /// \addtogroup graphs
    1.24    /// @{
    1.25  
    1.26 -  ///A list digraph class.
    1.27 +  ///A general directed graph structure. 
    1.28  
    1.29 -  ///This is a simple and fast digraph implementation.
    1.30 +  ///\ref ListDigraph is a simple and fast <em>directed graph</em> 
    1.31 +  ///implementation based on static linked lists that are stored in 
    1.32 +  ///\c std::vector structures.   
    1.33    ///
    1.34    ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
    1.35 -  ///also provides several additional useful extra functionalities.
    1.36 -  ///The most of the member functions and nested classes are
    1.37 -  ///documented only in the concept class.
    1.38 +  ///also provides several useful additional functionalities.
    1.39 +  ///Most of the member functions and nested classes are documented
    1.40 +  ///only in the concept class.
    1.41    ///
    1.42    ///An important extra feature of this digraph implementation is that
    1.43    ///its maps are real \ref concepts::ReferenceMap "reference map"s.
    1.44    ///
    1.45 -  ///\sa concepts::Digraph.
    1.46 +  ///\sa concepts::Digraph
    1.47  
    1.48    class ListDigraph : public ExtendedListDigraphBase {
    1.49    private:
    1.50 -    ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.
    1.51 +    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
    1.52      
    1.53 -    ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.
    1.54 +    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
    1.55      ///
    1.56      ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
    1.57      ///\brief Assignment of ListDigraph to another one is \e not allowed.
    1.58 -    ///Use DigraphCopy() instead.
    1.59 +    ///Use copyDigraph() instead.
    1.60  
    1.61      ///Assignment of ListDigraph to another one is \e not allowed.
    1.62 -    ///Use DigraphCopy() instead.
    1.63 +    ///Use copyDigraph() instead.
    1.64      void operator=(const ListDigraph &) {}
    1.65    public:
    1.66  
    1.67 @@ -335,8 +337,8 @@
    1.68  
    1.69      ///Add a new node to the digraph.
    1.70      
    1.71 -    /// \return the new node.
    1.72 -    ///
    1.73 +    ///Add a new node to the digraph.
    1.74 +    ///\return the new node.
    1.75      Node addNode() { return Parent::addNode(); }
    1.76  
    1.77      ///Add a new arc to the digraph.
    1.78 @@ -348,25 +350,27 @@
    1.79        return Parent::addArc(s, t); 
    1.80      }
    1.81  
    1.82 -    /// Changes the target of \c e to \c n
    1.83 +    /// Change the target of \c e to \c n
    1.84  
    1.85 -    /// Changes the target of \c e to \c n
    1.86 +    /// Change the target of \c e to \c n
    1.87      ///
    1.88      ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
    1.89      ///the changed arc remain valid. However <tt>InArcIt</tt>s are
    1.90      ///invalidated.
    1.91 +    ///
    1.92      ///\warning This functionality cannot be used together with the Snapshot
    1.93      ///feature.
    1.94      void changeTarget(Arc e, Node n) { 
    1.95        Parent::changeTarget(e,n); 
    1.96      }
    1.97 -    /// Changes the source of \c e to \c n
    1.98 +    /// Change the source of \c e to \c n
    1.99  
   1.100 -    /// Changes the source of \c e to \c n
   1.101 +    /// Change the source of \c e to \c n
   1.102      ///
   1.103      ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing
   1.104      ///the changed arc remain valid. However <tt>OutArcIt</tt>s are
   1.105      ///invalidated.
   1.106 +    ///
   1.107      ///\warning This functionality cannot be used together with the Snapshot
   1.108      ///feature.
   1.109      void changeSource(Arc e, Node n) { 
   1.110 @@ -378,6 +382,7 @@
   1.111      ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
   1.112      ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
   1.113      ///invalidated.
   1.114 +    ///
   1.115      ///\warning This functionality cannot be used together with the Snapshot
   1.116      ///feature.
   1.117      void reverseArc(Arc e) {
   1.118 @@ -386,7 +391,9 @@
   1.119        changeSource(e,t);
   1.120      }
   1.121  
   1.122 -    /// Using this it is possible to avoid the superfluous memory
   1.123 +    /// Reserve memory for nodes.
   1.124 +
   1.125 +    /// Using this function it is possible to avoid the superfluous memory
   1.126      /// allocation: if you know that the digraph you want to build will
   1.127      /// be very large (e.g. it will contain millions of nodes and/or arcs)
   1.128      /// then it is worth reserving space for this amount before starting
   1.129 @@ -394,10 +401,9 @@
   1.130      /// \sa reserveArc
   1.131      void reserveNode(int n) { nodes.reserve(n); };
   1.132  
   1.133 -    /// \brief Using this it is possible to avoid the superfluous memory
   1.134 -    /// allocation.
   1.135 +    /// Reserve memory for arcs.
   1.136  
   1.137 -    /// Using this it is possible to avoid the superfluous memory
   1.138 +    /// Using this function it is possible to avoid the superfluous memory
   1.139      /// allocation: if you know that the digraph you want to build will
   1.140      /// be very large (e.g. it will contain millions of nodes and/or arcs)
   1.141      /// then it is worth reserving space for this amount before starting
   1.142 @@ -408,16 +414,15 @@
   1.143      ///Contract two nodes.
   1.144  
   1.145      ///This function contracts two nodes.
   1.146 -    ///
   1.147      ///Node \p b will be removed but instead of deleting
   1.148      ///incident arcs, they will be joined to \p a.
   1.149      ///The last parameter \p r controls whether to remove loops. \c true
   1.150      ///means that loops will be removed.
   1.151      ///
   1.152 -    ///\note The <tt>ArcIt</tt>s
   1.153 -    ///referencing a moved arc remain
   1.154 +    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
   1.155      ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
   1.156      ///may be invalidated.
   1.157 +    ///
   1.158      ///\warning This functionality cannot be used together with the Snapshot
   1.159      ///feature.
   1.160      void contract(Node a, Node b, bool r = true) 
   1.161 @@ -452,8 +457,9 @@
   1.162      ///be invalidated.  
   1.163      ///
   1.164      ///\warning This functionality cannot be used together with the
   1.165 -    ///Snapshot feature.  \todo It could be implemented in a bit
   1.166 -    ///faster way.
   1.167 +    ///Snapshot feature.
   1.168 +    ///
   1.169 +    ///\todo It could be implemented in a bit faster way.
   1.170      Node split(Node n, bool connect = true) {
   1.171        Node b = addNode();
   1.172        for(OutArcIt e(*this,n);e!=INVALID;) {
   1.173 @@ -471,9 +477,11 @@
   1.174      ///This function splits an arc. First a new node \c b is added to
   1.175      ///the digraph, then the original arc is re-targeted to \c
   1.176      ///b. Finally an arc from \c b to the original target is added.
   1.177 -    ///\return The newly created node.  
   1.178 -    ///\warning This functionality
   1.179 -    ///cannot be used together with the Snapshot feature.
   1.180 +    ///
   1.181 +    ///\return The newly created node.
   1.182 +    ///
   1.183 +    ///\warning This functionality cannot be used together with the
   1.184 +    ///Snapshot feature.
   1.185      Node split(Arc e) {
   1.186        Node b = addNode();
   1.187        addArc(b,target(e));
   1.188 @@ -482,16 +490,16 @@
   1.189      }
   1.190        
   1.191      /// \brief Class to make a snapshot of the digraph and restore
   1.192 -    /// to it later.
   1.193 +    /// it later.
   1.194      ///
   1.195 -    /// Class to make a snapshot of the digraph and to restore it
   1.196 -    /// later.
   1.197 +    /// Class to make a snapshot of the digraph and restore it later.
   1.198      ///
   1.199      /// The newly added nodes and arcs can be removed using the
   1.200      /// restore() function.
   1.201      ///
   1.202 -    /// \warning Arc and node deletions cannot be restored. This
   1.203 -    /// events invalidate the snapshot. 
   1.204 +    /// \warning Arc and node deletions and other modifications (e.g.
   1.205 +    /// contracting, splitting, reversing arcs or nodes) cannot be 
   1.206 +    /// restored. These events invalidate the snapshot. 
   1.207      class Snapshot {
   1.208      protected:
   1.209  
   1.210 @@ -776,9 +784,9 @@
   1.211      public:
   1.212        Edge() {}
   1.213        Edge (Invalid) { id = -1; }
   1.214 -      bool operator==(const Edge& arc) const {return id == arc.id;}
   1.215 -      bool operator!=(const Edge& arc) const {return id != arc.id;}
   1.216 -      bool operator<(const Edge& arc) const {return id < arc.id;}
   1.217 +      bool operator==(const Edge& edge) const {return id == edge.id;}
   1.218 +      bool operator!=(const Edge& edge) const {return id != edge.id;}
   1.219 +      bool operator<(const Edge& edge) const {return id < edge.id;}
   1.220      };
   1.221  
   1.222      class Arc {
   1.223 @@ -909,20 +917,20 @@
   1.224      }
   1.225  
   1.226      void firstInc(Edge &e, bool& d, const Node& v) const {
   1.227 -      int de = nodes[v.id].first_out;
   1.228 -      if (de != -1 ) {
   1.229 -        e.id = de / 2;
   1.230 -        d = ((de & 1) == 1);
   1.231 +      int a = nodes[v.id].first_out;
   1.232 +      if (a != -1 ) {
   1.233 +        e.id = a / 2;
   1.234 +        d = ((a & 1) == 1);
   1.235        } else {
   1.236          e.id = -1;
   1.237          d = true;
   1.238        }
   1.239      }
   1.240      void nextInc(Edge &e, bool& d) const {
   1.241 -      int de = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
   1.242 -      if (de != -1 ) {
   1.243 -        e.id = de / 2;
   1.244 -        d = ((de & 1) == 1);
   1.245 +      int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
   1.246 +      if (a != -1 ) {
   1.247 +        e.id = a / 2;
   1.248 +        d = ((a & 1) == 1);
   1.249        } else {
   1.250          e.id = -1;
   1.251          d = true;
   1.252 @@ -1008,8 +1016,8 @@
   1.253  
   1.254      }
   1.255      
   1.256 -    void erase(const Edge& arc) {
   1.257 -      int n = arc.id * 2;
   1.258 +    void erase(const Edge& edge) {
   1.259 +      int n = edge.id * 2;
   1.260        
   1.261        if (arcs[n].next_out != -1) {
   1.262  	arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
   1.263 @@ -1089,40 +1097,40 @@
   1.264  
   1.265    };
   1.266  
   1.267 -//   typedef GraphExtender<UndirDigraphExtender<ListDigraphBase> > 
   1.268 -//   ExtendedListGraphBase;
   1.269 -
   1.270    typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
   1.271  
   1.272  
   1.273 -
   1.274 -  /// \addtogroup digraphs
   1.275 +  /// \addtogroup graphs
   1.276    /// @{
   1.277  
   1.278 -  ///An undirected list digraph class.
   1.279 +  ///A general undirected graph structure.
   1.280  
   1.281 -  ///This is a simple and fast undirected digraph implementation.
   1.282 +  ///\ref ListGraph is a simple and fast <em>undirected graph</em> 
   1.283 +  ///implementation based on static linked lists that are stored in 
   1.284 +  ///\c std::vector structures. 
   1.285    ///
   1.286 -  ///An important extra feature of this digraph implementation is that
   1.287 +  ///It conforms to the \ref concepts::Graph "Graph concept" and it
   1.288 +  ///also provides several useful additional functionalities.
   1.289 +  ///Most of the member functions and nested classes are documented
   1.290 +  ///only in the concept class.
   1.291 +  ///
   1.292 +  ///An important extra feature of this graph implementation is that
   1.293    ///its maps are real \ref concepts::ReferenceMap "reference map"s.
   1.294    ///
   1.295 -  ///It conforms to the
   1.296 -  ///\ref concepts::Graph "Graph concept".
   1.297 -  ///
   1.298 -  ///\sa concepts::Graph.
   1.299 -  ///
   1.300 +  ///\sa concepts::Graph
   1.301 +
   1.302    class ListGraph : public ExtendedListGraphBase {
   1.303    private:
   1.304 -    ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
   1.305 +    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
   1.306  
   1.307 -    ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
   1.308 +    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
   1.309      ///
   1.310      ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
   1.311      ///\brief Assignment of ListGraph to another one is \e not allowed.
   1.312 -    ///Use GraphCopy() instead.
   1.313 +    ///Use copyGraph() instead.
   1.314  
   1.315      ///Assignment of ListGraph to another one is \e not allowed.
   1.316 -    ///Use GraphCopy() instead.
   1.317 +    ///Use copyGraph() instead.
   1.318      void operator=(const ListGraph &) {}
   1.319    public:
   1.320      /// Constructor
   1.321 @@ -1133,49 +1141,58 @@
   1.322  
   1.323      typedef ExtendedListGraphBase Parent;
   1.324  
   1.325 -    typedef Parent::OutArcIt IncArcIt;
   1.326 +    typedef Parent::OutArcIt IncEdgeIt;
   1.327  
   1.328 -    /// \brief Add a new node to the digraph.
   1.329 +    /// \brief Add a new node to the graph.
   1.330      ///
   1.331 +    /// Add a new node to the graph.
   1.332      /// \return the new node.
   1.333 -    ///
   1.334      Node addNode() { return Parent::addNode(); }
   1.335  
   1.336 -    /// \brief Add a new edge to the digraph.
   1.337 +    /// \brief Add a new edge to the graph.
   1.338      ///
   1.339 -    /// Add a new arc to the digraph with source node \c s
   1.340 +    /// Add a new edge to the graph with source node \c s
   1.341      /// and target node \c t.
   1.342      /// \return the new edge.
   1.343      Edge addEdge(const Node& s, const Node& t) { 
   1.344        return Parent::addEdge(s, t); 
   1.345      }
   1.346 -    /// \brief Changes the source of \c e to \c n
   1.347 +    /// \brief Change the source of \c e to \c n
   1.348      ///
   1.349 -    /// Changes the source of \c e to \c n
   1.350 +    /// This function changes the source of \c e to \c n.
   1.351      ///
   1.352      ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
   1.353      ///referencing the changed arc remain
   1.354      ///valid. However <tt>OutArcIt</tt>s are invalidated.
   1.355 +    ///
   1.356 +    ///\warning This functionality cannot be used together with the
   1.357 +    ///Snapshot feature.
   1.358      void changeSource(Edge e, Node n) { 
   1.359        Parent::changeSource(e,n); 
   1.360      }    
   1.361 -    /// \brief Changes the target of \c e to \c n
   1.362 +    /// \brief Change the target of \c e to \c n
   1.363      ///
   1.364 -    /// Changes the target of \c e to \c n
   1.365 +    /// This function changes the target of \c e to \c n.
   1.366      ///
   1.367      /// \note The <tt>ArcIt</tt>s referencing the changed arc remain
   1.368      /// valid. However the other iterators may be invalidated.
   1.369 +    ///
   1.370 +    ///\warning This functionality cannot be used together with the
   1.371 +    ///Snapshot feature.
   1.372      void changeTarget(Edge e, Node n) { 
   1.373        Parent::changeTarget(e,n); 
   1.374      }
   1.375 -    /// \brief Changes the source of \c e to \c n
   1.376 +    /// \brief Change the source of \c e to \c n
   1.377      ///
   1.378 -    /// Changes the source of \c e to \c n. It changes the proper
   1.379 -    /// node of the represented edge.
   1.380 +    /// This function changes the source of \c e to \c n. 
   1.381 +    /// It also changes the proper node of the represented edge.
   1.382      ///
   1.383      ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
   1.384      ///referencing the changed arc remain
   1.385      ///valid. However <tt>OutArcIt</tt>s are invalidated.
   1.386 +    ///
   1.387 +    ///\warning This functionality cannot be used together with the
   1.388 +    ///Snapshot feature.
   1.389      void changeSource(Arc e, Node n) { 
   1.390        if (Parent::direction(e)) {
   1.391          Parent::changeSource(e,n);
   1.392 @@ -1183,14 +1200,17 @@
   1.393          Parent::changeTarget(e,n);
   1.394        } 
   1.395      }
   1.396 -    /// \brief Changes the target of \c e to \c n
   1.397 +    /// \brief Change the target of \c e to \c n
   1.398      ///
   1.399 -    /// Changes the target of \c e to \c n. It changes the proper
   1.400 -    /// node of the represented edge.
   1.401 +    /// This function changes the target of \c e to \c n. 
   1.402 +    /// It also changes the proper node of the represented edge.
   1.403      ///
   1.404      ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s
   1.405      ///referencing the changed arc remain
   1.406      ///valid. However <tt>InArcIt</tt>s are invalidated.
   1.407 +    ///
   1.408 +    ///\warning This functionality cannot be used together with the
   1.409 +    ///Snapshot feature.
   1.410      void changeTarget(Arc e, Node n) { 
   1.411        if (Parent::direction(e)) {
   1.412          Parent::changeTarget(e,n);
   1.413 @@ -1201,7 +1221,6 @@
   1.414      /// \brief Contract two nodes.
   1.415      ///
   1.416      /// This function contracts two nodes.
   1.417 -    ///
   1.418      /// Node \p b will be removed but instead of deleting
   1.419      /// its neighboring arcs, they will be joined to \p a.
   1.420      /// The last parameter \p r controls whether to remove loops. \c true
   1.421 @@ -1209,9 +1228,12 @@
   1.422      ///
   1.423      /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
   1.424      /// valid.
   1.425 +    ///
   1.426 +    ///\warning This functionality cannot be used together with the
   1.427 +    ///Snapshot feature.
   1.428      void contract(Node a, Node b, bool r = true) {
   1.429 -      for(IncArcIt e(*this, b); e!=INVALID;) {
   1.430 -	IncArcIt f = e; ++f;
   1.431 +      for(IncEdgeIt e(*this, b); e!=INVALID;) {
   1.432 +	IncEdgeIt f = e; ++f;
   1.433  	if (r && runningNode(e) == a) {
   1.434  	  erase(e);
   1.435  	} else if (source(e) == b) {
   1.436 @@ -1225,17 +1247,17 @@
   1.437      }
   1.438  
   1.439  
   1.440 -    /// \brief Class to make a snapshot of the digraph and restore
   1.441 -    /// to it later.
   1.442 +    /// \brief Class to make a snapshot of the graph and restore
   1.443 +    /// it later.
   1.444      ///
   1.445 -    /// Class to make a snapshot of the digraph and to restore it
   1.446 -    /// later.
   1.447 +    /// Class to make a snapshot of the graph and restore it later.
   1.448      ///
   1.449      /// The newly added nodes and edges can be removed
   1.450      /// using the restore() function.
   1.451      ///
   1.452 -    /// \warning Arc and node deletions cannot be restored. This
   1.453 -    /// events invalidate the snapshot. 
   1.454 +    /// \warning Edge and node deletions and other modifications
   1.455 +    /// (e.g. changing nodes of edges, contracting nodes) cannot be 
   1.456 +    /// restored. These events invalidate the snapshot.
   1.457      class Snapshot {
   1.458      protected:
   1.459  
   1.460 @@ -1303,51 +1325,51 @@
   1.461          
   1.462        protected:
   1.463  
   1.464 -        virtual void add(const Edge& arc) {
   1.465 -          snapshot.addEdge(arc);
   1.466 +        virtual void add(const Edge& edge) {
   1.467 +          snapshot.addEdge(edge);
   1.468          }
   1.469 -        virtual void add(const std::vector<Edge>& arcs) {
   1.470 -          for (int i = arcs.size() - 1; i >= 0; ++i) {
   1.471 -            snapshot.addEdge(arcs[i]);
   1.472 +        virtual void add(const std::vector<Edge>& edges) {
   1.473 +          for (int i = edges.size() - 1; i >= 0; ++i) {
   1.474 +            snapshot.addEdge(edges[i]);
   1.475            }
   1.476          }
   1.477 -        virtual void erase(const Edge& arc) {
   1.478 -          snapshot.eraseEdge(arc);
   1.479 +        virtual void erase(const Edge& edge) {
   1.480 +          snapshot.eraseEdge(edge);
   1.481          }
   1.482 -        virtual void erase(const std::vector<Edge>& arcs) {
   1.483 -          for (int i = 0; i < int(arcs.size()); ++i) {
   1.484 -            snapshot.eraseEdge(arcs[i]);
   1.485 +        virtual void erase(const std::vector<Edge>& edges) {
   1.486 +          for (int i = 0; i < int(edges.size()); ++i) {
   1.487 +            snapshot.eraseEdge(edges[i]);
   1.488            }
   1.489          }
   1.490          virtual void build() {
   1.491 -          Edge arc;
   1.492 -          std::vector<Edge> arcs;
   1.493 -          for (notifier()->first(arc); arc != INVALID; 
   1.494 -               notifier()->next(arc)) {
   1.495 -            arcs.push_back(arc);
   1.496 +          Edge edge;
   1.497 +          std::vector<Edge> edges;
   1.498 +          for (notifier()->first(edge); edge != INVALID; 
   1.499 +               notifier()->next(edge)) {
   1.500 +            edges.push_back(edge);
   1.501            }
   1.502 -          for (int i = arcs.size() - 1; i >= 0; --i) {
   1.503 -            snapshot.addEdge(arcs[i]);
   1.504 +          for (int i = edges.size() - 1; i >= 0; --i) {
   1.505 +            snapshot.addEdge(edges[i]);
   1.506            }
   1.507          }
   1.508          virtual void clear() {
   1.509 -          Edge arc;
   1.510 -          for (notifier()->first(arc); arc != INVALID; 
   1.511 -               notifier()->next(arc)) {
   1.512 -            snapshot.eraseEdge(arc);
   1.513 +          Edge edge;
   1.514 +          for (notifier()->first(edge); edge != INVALID; 
   1.515 +               notifier()->next(edge)) {
   1.516 +            snapshot.eraseEdge(edge);
   1.517            }
   1.518          }
   1.519  
   1.520          Snapshot& snapshot;
   1.521        };
   1.522 -      
   1.523 -      ListGraph *digraph;
   1.524 +
   1.525 +      ListGraph *graph;
   1.526  
   1.527        NodeObserverProxy node_observer_proxy;
   1.528 -      EdgeObserverProxy arc_observer_proxy;
   1.529 +      EdgeObserverProxy edge_observer_proxy;
   1.530  
   1.531        std::list<Node> added_nodes;
   1.532 -      std::list<Edge> added_arcs;
   1.533 +      std::list<Edge> added_edges;
   1.534  
   1.535  
   1.536        void addNode(const Node& node) {
   1.537 @@ -1358,37 +1380,37 @@
   1.538            std::find(added_nodes.begin(), added_nodes.end(), node);
   1.539          if (it == added_nodes.end()) {
   1.540            clear();
   1.541 -          arc_observer_proxy.detach();
   1.542 +          edge_observer_proxy.detach();
   1.543            throw NodeNotifier::ImmediateDetach();
   1.544          } else {
   1.545            added_nodes.erase(it);
   1.546          }
   1.547        }
   1.548  
   1.549 -      void addEdge(const Edge& arc) {
   1.550 -        added_arcs.push_front(arc);        
   1.551 +      void addEdge(const Edge& edge) {
   1.552 +        added_edges.push_front(edge);        
   1.553        }
   1.554 -      void eraseEdge(const Edge& arc) {
   1.555 +      void eraseEdge(const Edge& edge) {
   1.556          std::list<Edge>::iterator it = 
   1.557 -          std::find(added_arcs.begin(), added_arcs.end(), arc);
   1.558 -        if (it == added_arcs.end()) {
   1.559 +          std::find(added_edges.begin(), added_edges.end(), edge);
   1.560 +        if (it == added_edges.end()) {
   1.561            clear();
   1.562            node_observer_proxy.detach();
   1.563            throw EdgeNotifier::ImmediateDetach();
   1.564          } else {
   1.565 -          added_arcs.erase(it);
   1.566 -        }        
   1.567 +          added_edges.erase(it);
   1.568 +        }
   1.569        }
   1.570  
   1.571 -      void attach(ListGraph &_digraph) {
   1.572 -	digraph = &_digraph;
   1.573 -	node_observer_proxy.attach(digraph->notifier(Node()));
   1.574 -        arc_observer_proxy.attach(digraph->notifier(Edge()));
   1.575 +      void attach(ListGraph &_graph) {
   1.576 +	graph = &_graph;
   1.577 +	node_observer_proxy.attach(graph->notifier(Node()));
   1.578 +        edge_observer_proxy.attach(graph->notifier(Edge()));
   1.579        }
   1.580              
   1.581        void detach() {
   1.582  	node_observer_proxy.detach();
   1.583 -	arc_observer_proxy.detach();
   1.584 +	edge_observer_proxy.detach();
   1.585        }
   1.586  
   1.587        bool attached() const {
   1.588 @@ -1397,7 +1419,7 @@
   1.589  
   1.590        void clear() {
   1.591          added_nodes.clear();
   1.592 -        added_arcs.clear();        
   1.593 +        added_edges.clear();        
   1.594        }
   1.595  
   1.596      public:
   1.597 @@ -1407,32 +1429,32 @@
   1.598        /// Default constructor.
   1.599        /// To actually make a snapshot you must call save().
   1.600        Snapshot() 
   1.601 -        : digraph(0), node_observer_proxy(*this), 
   1.602 -          arc_observer_proxy(*this) {}
   1.603 +        : graph(0), node_observer_proxy(*this), 
   1.604 +          edge_observer_proxy(*this) {}
   1.605        
   1.606        /// \brief Constructor that immediately makes a snapshot.
   1.607        ///      
   1.608 -      /// This constructor immediately makes a snapshot of the digraph.
   1.609 -      /// \param _digraph The digraph we make a snapshot of.
   1.610 -      Snapshot(ListGraph &_digraph) 
   1.611 +      /// This constructor immediately makes a snapshot of the graph.
   1.612 +      /// \param _graph The graph we make a snapshot of.
   1.613 +      Snapshot(ListGraph &_graph) 
   1.614          : node_observer_proxy(*this), 
   1.615 -          arc_observer_proxy(*this) {
   1.616 -	attach(_digraph);
   1.617 +          edge_observer_proxy(*this) {
   1.618 +	attach(_graph);
   1.619        }
   1.620        
   1.621        /// \brief Make a snapshot.
   1.622        ///
   1.623 -      /// Make a snapshot of the digraph.
   1.624 +      /// Make a snapshot of the graph.
   1.625        ///
   1.626        /// This function can be called more than once. In case of a repeated
   1.627        /// call, the previous snapshot gets lost.
   1.628 -      /// \param _digraph The digraph we make the snapshot of.
   1.629 -      void save(ListGraph &_digraph) {
   1.630 +      /// \param _graph The graph we make the snapshot of.
   1.631 +      void save(ListGraph &_graph) {
   1.632          if (attached()) {
   1.633            detach();
   1.634            clear();
   1.635          }
   1.636 -        attach(_digraph);
   1.637 +        attach(_graph);
   1.638        }
   1.639        
   1.640        /// \brief Undo the changes until the last snapshot.
   1.641 @@ -1440,13 +1462,13 @@
   1.642        /// Undo the changes until the last snapshot created by save().
   1.643        void restore() {
   1.644  	detach();
   1.645 -	for(std::list<Edge>::iterator it = added_arcs.begin(); 
   1.646 -            it != added_arcs.end(); ++it) {
   1.647 -	  digraph->erase(*it);
   1.648 +	for(std::list<Edge>::iterator it = added_edges.begin(); 
   1.649 +            it != added_edges.end(); ++it) {
   1.650 +	  graph->erase(*it);
   1.651  	}
   1.652  	for(std::list<Node>::iterator it = added_nodes.begin(); 
   1.653              it != added_nodes.end(); ++it) {
   1.654 -	  digraph->erase(*it);
   1.655 +	  graph->erase(*it);
   1.656  	}
   1.657          clear();
   1.658        }