Changes in / [70:e2c2763b7aec:75:6265aa2f9d7e] in lemon-1.2

Location:

lemon

Files:

• concepts/maps.h (modified) (3 diffs)
• list_graph.h (modified) (31 diffs)

lemon/concepts/maps.h

@@ -56 +56 @@
       template<typename _ReadMap>
       struct Constraints {
-
         void constraints() {
           Value val = m[key];
@@ -176 +175 @@
 
       template<typename _ReferenceMap>
-      struct ReferenceMapConcept {
-
-        void constraints() {
-          checkConcept<ReadWriteMap, _ReferenceMap >();
+      struct Constraints {
+        void constraints() {
+          checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
           m[key] = val;
           val  = m[key];
@@ -192 +190 @@
         typename _ReferenceMap::Key& own_key;
         typename _ReferenceMap::Value& own_val;
-        typename _ReferenceMap::Reference& own_ref;
+        typename _ReferenceMap::Reference own_ref;
         Key& key;
         Value& val;
-        Reference& ref;
+        Reference ref;
         _ReferenceMap& m;
       };

lemon/list_graph.h

@@ -112 +112 @@
 
 
-    void first(Arc& e) const { 
+    void first(Arc& arc) const { 
       int n;
       for(n = first_node; 
           n!=-1 && nodes[n].first_in == -1; 
           n = nodes[n].next);
-      e.id = (n == -1) ? -1 : nodes[n].first_in;
+      arc.id = (n == -1) ? -1 : nodes[n].first_in;
     }
 
@@ -294 +294 @@
   typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
 
-  /// \addtogroup digraphs
+  /// \addtogroup graphs
   /// @{
 
-  ///A list digraph class.
-
-  ///This is a simple and fast digraph implementation.
+  ///A general directed graph structure. 
+
+  ///\ref ListDigraph is a simple and fast <em>directed graph</em> 
+  ///implementation based on static linked lists that are stored in 
+  ///\c std::vector structures.   
   ///
   ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
-  ///also provides several additional useful extra functionalities.
-  ///The most of the member functions and nested classes are
-  ///documented only in the concept class.
+  ///also provides several useful additional functionalities.
+  ///Most of the member functions and nested classes are documented
+  ///only in the concept class.
   ///
   ///An important extra feature of this digraph implementation is that
   ///its maps are real \ref concepts::ReferenceMap "reference map"s.
   ///
-  ///\sa concepts::Digraph.
+  ///\sa concepts::Digraph
 
   class ListDigraph : public ExtendedListDigraphBase {
   private:
-    ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.
-    
-    ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.
+    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
+    
+    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
     ///
     ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
     ///\brief Assignment of ListDigraph to another one is \e not allowed.
-    ///Use DigraphCopy() instead.
+    ///Use copyDigraph() instead.
 
     ///Assignment of ListDigraph to another one is \e not allowed.
-    ///Use DigraphCopy() instead.
+    ///Use copyDigraph() instead.
     void operator=(const ListDigraph &) {}
   public:
@@ -336 +338 @@
     ///Add a new node to the digraph.
     
-    /// \return the new node.
-    ///
+    ///Add a new node to the digraph.
+    ///\return the new node.
     Node addNode() { return Parent::addNode(); }
 
@@ -349 +351 @@
     }
 
-    /// Changes the target of \c e to \c n
-
-    /// Changes the target of \c e to \c n
+    /// Change the target of \c e to \c n
+
+    /// Change the target of \c e to \c n
     ///
     ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
     ///the changed arc remain valid. However <tt>InArcIt</tt>s are
     ///invalidated.
+    ///
     ///\warning This functionality cannot be used together with the Snapshot
     ///feature.
@@ -361 +364 @@
       Parent::changeTarget(e,n); 
     }
-    /// Changes the source of \c e to \c n
-
-    /// Changes the source of \c e to \c n
+    /// Change the source of \c e to \c n
+
+    /// Change the source of \c e to \c n
     ///
     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing
     ///the changed arc remain valid. However <tt>OutArcIt</tt>s are
     ///invalidated.
+    ///
     ///\warning This functionality cannot be used together with the Snapshot
     ///feature.
@@ -379 +383 @@
     ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
     ///invalidated.
+    ///
     ///\warning This functionality cannot be used together with the Snapshot
     ///feature.
@@ -387 +392 @@
     }
 
-    /// Using this it is possible to avoid the superfluous memory
+    /// Reserve memory for nodes.
+
+    /// Using this function it is possible to avoid the superfluous memory
     /// allocation: if you know that the digraph you want to build will
     /// be very large (e.g. it will contain millions of nodes and/or arcs)
@@ -395 +402 @@
     void reserveNode(int n) { nodes.reserve(n); };
 
-    /// \brief Using this it is possible to avoid the superfluous memory
-    /// allocation.
-
-    /// Using this it is possible to avoid the superfluous memory
+    /// Reserve memory for arcs.
+
+    /// Using this function it is possible to avoid the superfluous memory
     /// allocation: if you know that the digraph you want to build will
     /// be very large (e.g. it will contain millions of nodes and/or arcs)
@@ -409 +415 @@
 
     ///This function contracts two nodes.
-    ///
     ///Node \p b will be removed but instead of deleting
     ///incident arcs, they will be joined to \p a.
@@ -415 +420 @@
     ///means that loops will be removed.
     ///
-    ///\note The <tt>ArcIt</tt>s
-    ///referencing a moved arc remain
+    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
     ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
     ///may be invalidated.
+    ///
     ///\warning This functionality cannot be used together with the Snapshot
     ///feature.
@@ -453 +458 @@
     ///
     ///\warning This functionality cannot be used together with the
-    ///Snapshot feature.  \todo It could be implemented in a bit
-    ///faster way.
+    ///Snapshot feature.
+    ///
+    ///\todo It could be implemented in a bit faster way.
     Node split(Node n, bool connect = true) {
       Node b = addNode();
@@ -472 +478 @@
     ///the digraph, then the original arc is re-targeted to \c
     ///b. Finally an arc from \c b to the original target is added.
-    ///\return The newly created node.  
-    ///\warning This functionality
-    ///cannot be used together with the Snapshot feature.
+    ///
+    ///\return The newly created node.
+    ///
+    ///\warning This functionality cannot be used together with the
+    ///Snapshot feature.
     Node split(Arc e) {
       Node b = addNode();
@@ -483 +491 @@
       
     /// \brief Class to make a snapshot of the digraph and restore
-    /// to it later.
-    ///
-    /// Class to make a snapshot of the digraph and to restore it
-    /// later.
+    /// it later.
+    ///
+    /// Class to make a snapshot of the digraph and restore it later.
     ///
     /// The newly added nodes and arcs can be removed using the
     /// restore() function.
     ///
-    /// \warning Arc and node deletions cannot be restored. This
-    /// events invalidate the snapshot. 
+    /// \warning Arc and node deletions and other modifications (e.g.
+    /// contracting, splitting, reversing arcs or nodes) cannot be 
+    /// restored. These events invalidate the snapshot. 
     class Snapshot {
     protected:
@@ -777 +785 @@
       Edge() {}
       Edge (Invalid) { id = -1; }
-      bool operator==(const Edge& arc) const {return id == arc.id;}
-      bool operator!=(const Edge& arc) const {return id != arc.id;}
-      bool operator<(const Edge& arc) const {return id < arc.id;}
+      bool operator==(const Edge& edge) const {return id == edge.id;}
+      bool operator!=(const Edge& edge) const {return id != edge.id;}
+      bool operator<(const Edge& edge) const {return id < edge.id;}
     };
 
@@ -910 +918 @@
 
     void firstInc(Edge &e, bool& d, const Node& v) const {
-      int de = nodes[v.id].first_out;
-      if (de != -1 ) {
-        e.id = de / 2;
-        d = ((de & 1) == 1);
+      int a = nodes[v.id].first_out;
+      if (a != -1 ) {
+        e.id = a / 2;
+        d = ((a & 1) == 1);
       } else {
         e.id = -1;
@@ -920 +928 @@
     }
     void nextInc(Edge &e, bool& d) const {
-      int de = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
-      if (de != -1 ) {
-        e.id = de / 2;
-        d = ((de & 1) == 1);
+      int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
+      if (a != -1 ) {
+        e.id = a / 2;
+        d = ((a & 1) == 1);
       } else {
         e.id = -1;
@@ -1009 +1017 @@
     }
     
-    void erase(const Edge& arc) {
-      int n = arc.id * 2;
+    void erase(const Edge& edge) {
+      int n = edge.id * 2;
       
       if (arcs[n].next_out != -1) {
@@ -1090 +1098 @@
   };
 
-//   typedef GraphExtender<UndirDigraphExtender<ListDigraphBase> > 
-//   ExtendedListGraphBase;
-
   typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
 
 
-
-  /// \addtogroup digraphs
+  /// \addtogroup graphs
   /// @{
 
-  ///An undirected list digraph class.
-
-  ///This is a simple and fast undirected digraph implementation.
+  ///A general undirected graph structure.
+
+  ///\ref ListGraph is a simple and fast <em>undirected graph</em> 
+  ///implementation based on static linked lists that are stored in 
+  ///\c std::vector structures. 
   ///
-  ///An important extra feature of this digraph implementation is that
+  ///It conforms to the \ref concepts::Graph "Graph concept" and it
+  ///also provides several useful additional functionalities.
+  ///Most of the member functions and nested classes are documented
+  ///only in the concept class.
+  ///
+  ///An important extra feature of this graph implementation is that
   ///its maps are real \ref concepts::ReferenceMap "reference map"s.
   ///
-  ///It conforms to the
-  ///\ref concepts::Graph "Graph concept".
-  ///
-  ///\sa concepts::Graph.
-  ///
+  ///\sa concepts::Graph
+
   class ListGraph : public ExtendedListGraphBase {
   private:
-    ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
-
-    ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
+    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
+
+    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
     ///
     ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
     ///\brief Assignment of ListGraph to another one is \e not allowed.
-    ///Use GraphCopy() instead.
+    ///Use copyGraph() instead.
 
     ///Assignment of ListGraph to another one is \e not allowed.
-    ///Use GraphCopy() instead.
+    ///Use copyGraph() instead.
     void operator=(const ListGraph &) {}
   public:
@@ -1134 +1142 @@
     typedef ExtendedListGraphBase Parent;
 
-    typedef Parent::OutArcIt IncArcIt;
-
-    /// \brief Add a new node to the digraph.
-    ///
+    typedef Parent::OutArcIt IncEdgeIt;
+
+    /// \brief Add a new node to the graph.
+    ///
+    /// Add a new node to the graph.
     /// \return the new node.
-    ///
     Node addNode() { return Parent::addNode(); }
 
-    /// \brief Add a new edge to the digraph.
-    ///
-    /// Add a new arc to the digraph with source node \c s
+    /// \brief Add a new edge to the graph.
+    ///
+    /// Add a new edge to the graph with source node \c s
     /// and target node \c t.
     /// \return the new edge.
@@ -1150 +1158 @@
       return Parent::addEdge(s, t); 
     }
-    /// \brief Changes the source of \c e to \c n
-    ///
-    /// Changes the source of \c e to \c n
+    /// \brief Change the source of \c e to \c n
+    ///
+    /// This function changes the source of \c e to \c n.
     ///
     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
     ///referencing the changed arc remain
     ///valid. However <tt>OutArcIt</tt>s are invalidated.
+    ///
+    ///\warning This functionality cannot be used together with the
+    ///Snapshot feature.
     void changeSource(Edge e, Node n) { 
       Parent::changeSource(e,n); 
     }    
-    /// \brief Changes the target of \c e to \c n
-    ///
-    /// Changes the target of \c e to \c n
+    /// \brief Change the target of \c e to \c n
+    ///
+    /// This function changes the target of \c e to \c n.
     ///
     /// \note The <tt>ArcIt</tt>s referencing the changed arc remain
     /// valid. However the other iterators may be invalidated.
+    ///
+    ///\warning This functionality cannot be used together with the
+    ///Snapshot feature.
     void changeTarget(Edge e, Node n) { 
       Parent::changeTarget(e,n); 
     }
-    /// \brief Changes the source of \c e to \c n
-    ///
-    /// Changes the source of \c e to \c n. It changes the proper
-    /// node of the represented edge.
+    /// \brief Change the source of \c e to \c n
+    ///
+    /// This function changes the source of \c e to \c n. 
+    /// It also changes the proper node of the represented edge.
     ///
     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
     ///referencing the changed arc remain
     ///valid. However <tt>OutArcIt</tt>s are invalidated.
+    ///
+    ///\warning This functionality cannot be used together with the
+    ///Snapshot feature.
     void changeSource(Arc e, Node n) { 
       if (Parent::direction(e)) {
@@ -1184 +1201 @@
       } 
     }
-    /// \brief Changes the target of \c e to \c n
-    ///
-    /// Changes the target of \c e to \c n. It changes the proper
-    /// node of the represented edge.
+    /// \brief Change the target of \c e to \c n
+    ///
+    /// This function changes the target of \c e to \c n. 
+    /// It also changes the proper node of the represented edge.
     ///
     ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s
     ///referencing the changed arc remain
     ///valid. However <tt>InArcIt</tt>s are invalidated.
+    ///
+    ///\warning This functionality cannot be used together with the
+    ///Snapshot feature.
     void changeTarget(Arc e, Node n) { 
       if (Parent::direction(e)) {
@@ -1202 +1222 @@
     ///
     /// This function contracts two nodes.
-    ///
     /// Node \p b will be removed but instead of deleting
     /// its neighboring arcs, they will be joined to \p a.
@@ -1210 +1229 @@
     /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
     /// valid.
+    ///
+    ///\warning This functionality cannot be used together with the
+    ///Snapshot feature.
     void contract(Node a, Node b, bool r = true) {
-      for(IncArcIt e(*this, b); e!=INVALID;) {
-        IncArcIt f = e; ++f;
+      for(IncEdgeIt e(*this, b); e!=INVALID;) {
+        IncEdgeIt f = e; ++f;
         if (r && runningNode(e) == a) {
           erase(e);
@@ -1226 +1248 @@
 
 
-    /// \brief Class to make a snapshot of the digraph and restore
-    /// to it later.
-    ///
-    /// Class to make a snapshot of the digraph and to restore it
-    /// later.
+    /// \brief Class to make a snapshot of the graph and restore
+    /// it later.
+    ///
+    /// Class to make a snapshot of the graph and restore it later.
     ///
     /// The newly added nodes and edges can be removed
     /// using the restore() function.
     ///
-    /// \warning Arc and node deletions cannot be restored. This
-    /// events invalidate the snapshot. 
+    /// \warning Edge and node deletions and other modifications
+    /// (e.g. changing nodes of edges, contracting nodes) cannot be 
+    /// restored. These events invalidate the snapshot.
     class Snapshot {
     protected:
@@ -1304 +1326 @@
       protected:
 
-        virtual void add(const Edge& arc) {
-          snapshot.addEdge(arc);
-        }
-        virtual void add(const std::vector<Edge>& arcs) {
-          for (int i = arcs.size() - 1; i >= 0; ++i) {
-            snapshot.addEdge(arcs[i]);
-          }
-        }
-        virtual void erase(const Edge& arc) {
-          snapshot.eraseEdge(arc);
-        }
-        virtual void erase(const std::vector<Edge>& arcs) {
-          for (int i = 0; i < int(arcs.size()); ++i) {
-            snapshot.eraseEdge(arcs[i]);
+        virtual void add(const Edge& edge) {
+          snapshot.addEdge(edge);
+        }
+        virtual void add(const std::vector<Edge>& edges) {
+          for (int i = edges.size() - 1; i >= 0; ++i) {
+            snapshot.addEdge(edges[i]);
+          }
+        }
+        virtual void erase(const Edge& edge) {
+          snapshot.eraseEdge(edge);
+        }
+        virtual void erase(const std::vector<Edge>& edges) {
+          for (int i = 0; i < int(edges.size()); ++i) {
+            snapshot.eraseEdge(edges[i]);
           }
         }
         virtual void build() {
-          Edge arc;
-          std::vector<Edge> arcs;
-          for (notifier()->first(arc); arc != INVALID; 
-               notifier()->next(arc)) {
-            arcs.push_back(arc);
-          }
-          for (int i = arcs.size() - 1; i >= 0; --i) {
-            snapshot.addEdge(arcs[i]);
+          Edge edge;
+          std::vector<Edge> edges;
+          for (notifier()->first(edge); edge != INVALID; 
+               notifier()->next(edge)) {
+            edges.push_back(edge);
+          }
+          for (int i = edges.size() - 1; i >= 0; --i) {
+            snapshot.addEdge(edges[i]);
           }
         }
         virtual void clear() {
-          Edge arc;
-          for (notifier()->first(arc); arc != INVALID; 
-               notifier()->next(arc)) {
-            snapshot.eraseEdge(arc);
+          Edge edge;
+          for (notifier()->first(edge); edge != INVALID; 
+               notifier()->next(edge)) {
+            snapshot.eraseEdge(edge);
           }
         }
@@ -1341 +1363 @@
         Snapshot& snapshot;
       };
-      
-      ListGraph *digraph;
+
+      ListGraph *graph;
 
       NodeObserverProxy node_observer_proxy;
-      EdgeObserverProxy arc_observer_proxy;
+      EdgeObserverProxy edge_observer_proxy;
 
       std::list<Node> added_nodes;
-      std::list<Edge> added_arcs;
+      std::list<Edge> added_edges;
 
 
@@ -1359 +1381 @@
         if (it == added_nodes.end()) {
           clear();
-          arc_observer_proxy.detach();
+          edge_observer_proxy.detach();
           throw NodeNotifier::ImmediateDetach();
         } else {
@@ -1366 +1388 @@
       }
 
-      void addEdge(const Edge& arc) {
-        added_arcs.push_front(arc);        
-      }
-      void eraseEdge(const Edge& arc) {
+      void addEdge(const Edge& edge) {
+        added_edges.push_front(edge);        
+      }
+      void eraseEdge(const Edge& edge) {
         std::list<Edge>::iterator it = 
-          std::find(added_arcs.begin(), added_arcs.end(), arc);
-        if (it == added_arcs.end()) {
+          std::find(added_edges.begin(), added_edges.end(), edge);
+        if (it == added_edges.end()) {
           clear();
           node_observer_proxy.detach();
           throw EdgeNotifier::ImmediateDetach();
         } else {
-          added_arcs.erase(it);
-        }        
-      }
-
-      void attach(ListGraph &_digraph) {
-        digraph = &_digraph;
-        node_observer_proxy.attach(digraph->notifier(Node()));
-        arc_observer_proxy.attach(digraph->notifier(Edge()));
+          added_edges.erase(it);
+        }
+      }
+
+      void attach(ListGraph &_graph) {
+        graph = &_graph;
+        node_observer_proxy.attach(graph->notifier(Node()));
+        edge_observer_proxy.attach(graph->notifier(Edge()));
       }
             
       void detach() {
         node_observer_proxy.detach();
-        arc_observer_proxy.detach();
+        edge_observer_proxy.detach();
       }
 
@@ -1398 +1420 @@
       void clear() {
         added_nodes.clear();
-        added_arcs.clear();        
+        added_edges.clear();        
       }
 
@@ -1408 +1430 @@
       /// To actually make a snapshot you must call save().
       Snapshot() 
-        : digraph(0), node_observer_proxy(*this), 
-          arc_observer_proxy(*this) {}
+        : graph(0), node_observer_proxy(*this), 
+          edge_observer_proxy(*this) {}
       
       /// \brief Constructor that immediately makes a snapshot.
       ///      
-      /// This constructor immediately makes a snapshot of the digraph.
-      /// \param _digraph The digraph we make a snapshot of.
-      Snapshot(ListGraph &_digraph) 
+      /// This constructor immediately makes a snapshot of the graph.
+      /// \param _graph The graph we make a snapshot of.
+      Snapshot(ListGraph &_graph) 
         : node_observer_proxy(*this), 
-          arc_observer_proxy(*this) {
-        attach(_digraph);
+          edge_observer_proxy(*this) {
+        attach(_graph);
       }
       
       /// \brief Make a snapshot.
       ///
-      /// Make a snapshot of the digraph.
+      /// Make a snapshot of the graph.
       ///
       /// This function can be called more than once. In case of a repeated
       /// call, the previous snapshot gets lost.
-      /// \param _digraph The digraph we make the snapshot of.
-      void save(ListGraph &_digraph) {
+      /// \param _graph The graph we make the snapshot of.
+      void save(ListGraph &_graph) {
         if (attached()) {
           detach();
           clear();
         }
-        attach(_digraph);
+        attach(_graph);
       }
       
@@ -1441 +1463 @@
       void restore() {
         detach();
-        for(std::list<Edge>::iterator it = added_arcs.begin(); 
-            it != added_arcs.end(); ++it) {
-          digraph->erase(*it);
+        for(std::list<Edge>::iterator it = added_edges.begin(); 
+            it != added_edges.end(); ++it) {
+          graph->erase(*it);
         }
         for(std::list<Node>::iterator it = added_nodes.begin(); 
             it != added_nodes.end(); ++it) {
-          digraph->erase(*it);
+          graph->erase(*it);
         }
         clear();