author Peter Kovacs Tue, 05 Feb 2008 11:24:57 +0100 changeset 73 c56b7389dc78 parent 63 1113f6d12c0c child 74 9394072da54f
Several fixes and improvements in list_graph.h.

- Fix incorrect or misleading renamings in the code and in the documentation.
- Improve the documentation.
 lemon/list_graph.h file | annotate | diff | comparison | revisions
     1.1 --- a/lemon/list_graph.h	Fri Jan 25 14:52:50 2008 +0000
1.2 +++ b/lemon/list_graph.h	Tue Feb 05 11:24:57 2008 +0100
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.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.60
1.61      ///Assignment of ListDigraph to another one is \e not allowed.
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.76
1.77      ///Add a new arc to the digraph.
1.78 @@ -348,25 +350,27 @@
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.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.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.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.314
1.315      ///Assignment of ListGraph to another one is \e not allowed.
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.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.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.466 +        virtual void add(const Edge& 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.472 +        virtual void add(const std::vector<Edge>& edges) {
1.473 +          for (int i = edges.size() - 1; i >= 0; ++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.504 +          for (int i = edges.size() - 1; i >= 0; --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.534
1.535
1.536        void addNode(const Node& node) {
1.537 @@ -1358,37 +1380,37 @@
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.546          }
1.547        }
1.548
1.549 -      void addEdge(const Edge& arc) {
1.551 +      void addEdge(const Edge& 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.558 -        if (it == added_arcs.end()) {
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.566 -        }
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.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  	}