Changes in / [391:c4aa9f097ef1:392:80ec623f529f] in lemon

Files:

• Makefile.am (modified) (1 diff)
• configure.ac (modified) (3 diffs)
• doc/CMakeLists.txt (modified) (1 diff)
• doc/Doxyfile.in (modified) (1 diff)
• doc/Makefile.am (modified) (1 diff)
• doc/groups.dox (modified) (2 diffs)
• doc/images/grid_graph.eps (added)
• doc/migration.dox (modified) (2 diffs)
• lemon/Makefile.am (modified) (3 diffs)
• lemon/bfs.h (modified) (2 diffs)
• lemon/bits/alteration_notifier.h (modified) (3 diffs)
• lemon/bits/array_map.h (modified) (8 diffs)
• lemon/bits/base_extender.h (modified) (1 diff)
• lemon/bits/graph_extender.h (modified) (1 diff)
• lemon/bits/traits.h (modified) (2 diffs)
• lemon/bits/vector_map.h (modified) (7 diffs)
• lemon/full_graph.h (added)
• lemon/grid_graph.h (added)
• lemon/hypercube_graph.h (added)
• lemon/list_graph.h (modified) (1 diff)
• lemon/max_matching.h (added)
• lemon/nauty_reader.h (added)
• lemon/random.h (modified) (8 diffs)
• lemon/smart_graph.h (modified) (5 diffs)
• lemon/suurballe.h (added)
• scripts/chg-len.py (modified) (2 diffs)
• scripts/unify-sources.sh (modified) (3 diffs)
• test/CMakeLists.txt (modified) (1 diff)
• test/Makefile.am (modified) (3 diffs)
• test/digraph_test.cc (modified) (6 diffs)
• test/graph_test.cc (modified) (7 diffs)
• test/graph_test.h (modified) (1 diff)
• test/max_matching_test.cc (added)
• test/min_cost_flow_test.lgf (added)
• test/suurballe_test.cc (added)
• tools/lemon-0.x-to-1.x.sh (modified) (1 diff)

Makefile.am

@@ -1 +1 @@
 ACLOCAL_AMFLAGS = -I m4
+
+AM_CXXFLAGS = $(WARNINGCXXFLAGS)
 
 AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)

configure.ac

@@ -19 +19 @@
 AC_CONFIG_SRCDIR([lemon/list_graph.h])
 AC_CONFIG_HEADERS([config.h lemon/config.h])
-
-lx_cmdline_cxxflags_set=${CXXFLAGS+set}
 
 dnl Do compilation tests using the C++ compiler.
@@ -47 +45 @@
 
 dnl Set custom compiler flags when using g++.
-if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes -a "$ICC" = no; then
-  CXXFLAGS="$CXXFLAGS -Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
+if test "$GXX" = yes -a "$ICC" = no; then
+  WARNINGCXXFLAGS="-Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
 fi
+AC_SUBST([WARNINGCXXFLAGS])
 
 dnl Checks for libraries.
@@ -114 +113 @@
 echo
 echo C++ compiler.................. : $CXX
-echo C++ compiles flags............ : $CXXFLAGS
+echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
 echo
 #echo GLPK support.................. : $lx_glpk_found

doc/CMakeLists.txt

@@ -14 +14 @@
       COMMAND rm -rf gen-images
       COMMAND mkdir gen-images
+      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
       COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
       COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps

doc/Doxyfile.in

@@ -67 +67 @@
 ENABLED_SECTIONS       = 
 MAX_INITIALIZER_LINES  = 5
-SHOW_USED_FILES        = YES
+SHOW_USED_FILES        = NO
 SHOW_DIRECTORIES       = YES
 SHOW_FILES             = YES

doc/Makefile.am

@@ -15 +15 @@
 
 DOC_EPS_IMAGES18 = \
+        grid_graph.eps \
         nodeshape_0.eps \
         nodeshape_1.eps \

doc/groups.dox

@@ -465 +465 @@
 
 /**
-@defgroup lemon_io LEMON Input-Output
+@defgroup lemon_io LEMON Graph Format
 @ingroup io_group
 \brief Reading and writing LEMON Graph Format.
@@ -480 +480 @@
 This group describes general \c EPS drawing methods and special
 graph exporting tools.
+*/
+
+/**
+@defgroup nauty_group NAUTY Format
+@ingroup io_group
+\brief Read \e Nauty format
+Tool to read graphs from \e Nauty format data.
 */
 

doc/migration.dox

@@ -26 +26 @@
 
 Many of these changes adjusted automatically by the
-<tt>script/lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual
+<tt>lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual
 update are typeset <b>boldface</b>.
 
@@ -54 +54 @@
 
 \warning
-<b>The <tt>script/lemon-0.x-to-1.x.sh</tt> tool replaces all instances of
-the words \c graph, \c digraph, \c edge and \c arc, so it replaces them
-in strings, comments etc. as well as in all identifiers.</b>
+<b>The <tt>lemon-0.x-to-1.x.sh</tt> script replaces the words \c graph,
+\c ugraph, \c edge and \c uedge in your own identifiers and in
+strings, comments etc. as well as in all LEMON specific identifiers.
+So use the script carefully and make a backup copy of your source files
+before applying the script to them.</b>
 
 \section migration-lgf LGF tools

lemon/Makefile.am

@@ -13 +13 @@
         lemon/random.cc
 
-#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
+#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) $(AM_CXXFLAGS)
 #lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
 
@@ -29 +29 @@
         lemon/dim2.h \
         lemon/error.h \
+        lemon/full_graph.h \
         lemon/graph_to_eps.h \
+        lemon/grid_graph.h \
+        lemon/hypercube_graph.h \
         lemon/kruskal.h \
         lemon/lgf_reader.h \
@@ -36 +39 @@
         lemon/maps.h \
         lemon/math.h \
+        lemon/max_matching.h \
+        lemon/nauty_reader.h \
         lemon/path.h \
         lemon/random.h \
         lemon/smart_graph.h \
+        lemon/suurballe.h \
         lemon/time_measure.h \
         lemon/tolerance.h \

lemon/bfs.h

@@ -52 +52 @@
     ///Instantiates a PredMap.
 
-    ///This function instantiates a PredMap.
+    ///This function instantiates a PredMap.  
     ///\param g is the digraph, to which we would like to define the
     ///PredMap.
@@ -81 +81 @@
     ///The type of the map that indicates which nodes are reached.
 
-    ///The type of the map that indicates which nodes are reached.
-    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+    ///The type of the map that indicates which nodes are reached.///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     typedef typename Digraph::template NodeMap<bool> ReachedMap;
     ///Instantiates a ReachedMap.

lemon/bits/alteration_notifier.h

@@ -36 +36 @@
   // a container.
   //
-  // The simple graph's can be refered as two containers, one node container
-  // and one edge container. But they are not standard containers they
-  // does not store values directly they are just key continars for more
-  // value containers which are the node and edge maps.
-  //
-  // The graph's node and edge sets can be changed as we add or erase
+  // The simple graphs can be refered as two containers: a node container
+  // and an edge container. But they do not store values directly, they
+  // are just key continars for more value containers, which are the
+  // node and edge maps.
+  //
+  // The node and edge sets of the graphs can be changed as we add or erase
   // nodes and edges in the graph. LEMON would like to handle easily
   // that the node and edge maps should contain values for all nodes or
   // edges. If we want to check on every indicing if the map contains
   // the current indicing key that cause a drawback in the performance
-  // in the library. We use another solution we notify all maps about
+  // in the library. We use another solution: we notify all maps about
   // an alteration in the graph, which cause only drawback on the
   // alteration of the graph.
   //
-  // This class provides an interface to the container. The \e first() and \e
-  // next() member functions make possible to iterate on the keys of the
-  // container. The \e id() function returns an integer id for each key.
-  // The \e maxId() function gives back an upper bound of the ids.
+  // This class provides an interface to a node or edge container.
+  // The first() and next() member functions make possible
+  // to iterate on the keys of the container.
+  // The id() function returns an integer id for each key.
+  // The maxId() function gives back an upper bound of the ids.
   //
   // For the proper functonality of this class, we should notify it
-  // about each alteration in the container. The alterations have four type
-  // as \e add(), \e erase(), \e build() and \e clear(). The \e add() and
-  // \e erase() signals that only one or few items added or erased to or
-  // from the graph. If all items are erased from the graph or from an empty
-  // graph a new graph is builded then it can be signaled with the
+  // about each alteration in the container. The alterations have four type:
+  // add(), erase(), build() and clear(). The add() and
+  // erase() signal that only one or few items added or erased to or
+  // from the graph. If all items are erased from the graph or if a new graph
+  // is built from an empty graph, then it can be signaled with the
   // clear() and build() members. Important rule that if we erase items
-  // from graph we should first signal the alteration and after that erase
+  // from graphs we should first signal the alteration and after that erase
   // them from the container, on the other way on item addition we should
   // first extend the container and just after that signal the alteration.
   //
   // The alteration can be observed with a class inherited from the
-  // \e ObserverBase nested class. The signals can be handled with
+  // ObserverBase nested class. The signals can be handled with
   // overriding the virtual functions defined in the base class.  The
   // observer base can be attached to the notifier with the
-  // \e attach() member and can be detached with detach() function. The
+  // attach() member and can be detached with detach() function. The
   // alteration handlers should not call any function which signals
   // an other alteration in the same notifier and should not
   // detach any observer from the notifier.
   //
-  // Alteration observers try to be exception safe. If an \e add() or
-  // a \e clear() function throws an exception then the remaining
+  // Alteration observers try to be exception safe. If an add() or
+  // a clear() function throws an exception then the remaining
   // observeres will not be notified and the fulfilled additions will
-  // be rolled back by calling the \e erase() or \e clear()
-  // functions. Thence the \e erase() and \e clear() should not throw
-  // exception. Actullay, it can be throw only \ref ImmediateDetach
-  // exception which detach the observer from the notifier.
-  //
-  // There are some place when the alteration observing is not completly
+  // be rolled back by calling the erase() or clear() functions.
+  // Hence erase() and clear() should not throw exception.
+  // Actullay, they can throw only \ref ImmediateDetach exception,
+  // which detach the observer from the notifier.
+  //
+  // There are some cases, when the alteration observing is not completly
   // reliable. If we want to carry out the node degree in the graph
-  // as in the \ref InDegMap and we use the reverseEdge that cause
+  // as in the \ref InDegMap and we use the reverseArc(), then it cause
   // unreliable functionality. Because the alteration observing signals
-  // only erasing and adding but not the reversing it will stores bad
-  // degrees. The sub graph adaptors cannot signal the alterations because
-  // just a setting in the filter map can modify the graph and this cannot
-  // be watched in any way.
+  // only erasing and adding but not the reversing, it will stores bad
+  // degrees. Apart form that the subgraph adaptors cannot even signal
+  // the alterations because just a setting in the filter map can modify
+  // the graph and this cannot be watched in any way.
   //
   // \param _Container The container which is observed.
@@ -104 +105 @@
     typedef _Item Item;
 
-    // \brief Exception which can be called from \e clear() and
-    // \e erase().
-    //
-    // From the \e clear() and \e erase() function only this
+    // \brief Exception which can be called from clear() and
+    // erase().
+    //
+    // From the clear() and erase() function only this
     // exception is allowed to throw. The exception immediatly
     // detaches the current observer from the notifier. Because the
-    // \e clear() and \e erase() should not throw other exceptions
+    // clear() and erase() should not throw other exceptions
     // it can be used to invalidate the observer.
     struct ImmediateDetach {};
@@ -122 +123 @@
     // The observer interface contains some pure virtual functions
     // to override. The add() and erase() functions are
-    // to notify the oberver when one item is added or
-    // erased.
+    // to notify the oberver when one item is added or erased.
     //
     // The build() and clear() members are to notify the observer

lemon/bits/array_map.h

@@ -37 +37 @@
   // \brief Graph map based on the array storage.
   //
-  // The ArrayMap template class is graph map structure what
-  // automatically updates the map when a key is added to or erased from
-  // the map. This map uses the allocators to implement
-  // the container functionality.
+  // The ArrayMap template class is graph map structure that automatically
+  // updates the map when a key is added to or erased from the graph.
+  // This map uses the allocators to implement the container functionality.
   //
-  // The template parameters are the Graph the current Item type and
+  // The template parameters are the Graph, the current Item type and
   // the Value type of the map.
   template <typename _Graph, typename _Item, typename _Value>
@@ -48 +47 @@
     : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
   public:
-    // The graph type of the maps.
+    // The graph type.
     typedef _Graph Graph;
-    // The item type of the map.
+    // The item type.
     typedef _Item Item;
     // The reference map tag.
     typedef True ReferenceMapTag;
 
-    // The key type of the maps.
+    // The key type of the map.
     typedef _Item Key;
     // The value type of the map.
@@ -201 +200 @@
     // \brief Adds a new key to the map.
     //
-    // It adds a new key to the map. It called by the observer notifier
+    // It adds a new key to the map. It is called by the observer notifier
     // and it overrides the add() member function of the observer base.
     virtual void add(const Key& key) {
@@ -229 +228 @@
     // \brief Adds more new keys to the map.
     //
-    // It adds more new keys to the map. It called by the observer notifier
+    // It adds more new keys to the map. It is called by the observer notifier
     // and it overrides the add() member function of the observer base.
     virtual void add(const std::vector<Key>& keys) {
@@ -273 +272 @@
     // \brief Erase a key from the map.
     //
-    // Erase a key from the map. It called by the observer notifier
+    // Erase a key from the map. It is called by the observer notifier
     // and it overrides the erase() member function of the observer base.
     virtual void erase(const Key& key) {
@@ -282 +281 @@
     // \brief Erase more keys from the map.
     //
-    // Erase more keys from the map. It called by the observer notifier
+    // Erase more keys from the map. It is called by the observer notifier
     // and it overrides the erase() member function of the observer base.
     virtual void erase(const std::vector<Key>& keys) {
@@ -291 +290 @@
     }
 
-    // \brief Buildes the map.
-    //
-    // It buildes the map. It called by the observer notifier
+    // \brief Builds the map.
+    //
+    // It builds the map. It is called by the observer notifier
     // and it overrides the build() member function of the observer base.
     virtual void build() {
@@ -307 +306 @@
     // \brief Clear the map.
     //
-    // It erase all items from the map. It called by the observer notifier
+    // It erase all items from the map. It is called by the observer notifier
     // and it overrides the clear() member function of the observer base.
     virtual void clear() {

lemon/bits/base_extender.h

@@ -31 +31 @@
 //\ingroup digraphbits
 //\file
-//\brief Extenders for the digraph types
+//\brief Extenders for the graph types
 namespace lemon {
 

lemon/bits/graph_extender.h

@@ -30 +30 @@
 //\ingroup graphbits
 //\file
-//\brief Extenders for the digraph types
+//\brief Extenders for the graph types
 namespace lemon {
 
   // \ingroup graphbits
   //
-  // \brief Extender for the Digraphs
+  // \brief Extender for the digraph implementations
   template <typename Base>
   class DigraphExtender : public Base {

lemon/bits/traits.h

@@ -219 +219 @@
 
   template <typename Graph, typename Enable = void>
+  struct ArcNumTagIndicator {
+    static const bool value = false;
+  };
+
+  template <typename Graph>
+  struct ArcNumTagIndicator<
+    Graph,
+    typename enable_if<typename Graph::ArcNumTag, void>::type
+  > {
+    static const bool value = true;
+  };
+
+  template <typename Graph, typename Enable = void>
   struct EdgeNumTagIndicator {
     static const bool value = false;
@@ -232 +245 @@
 
   template <typename Graph, typename Enable = void>
+  struct FindArcTagIndicator {
+    static const bool value = false;
+  };
+
+  template <typename Graph>
+  struct FindArcTagIndicator<
+    Graph,
+    typename enable_if<typename Graph::FindArcTag, void>::type
+  > {
+    static const bool value = true;
+  };
+
+  template <typename Graph, typename Enable = void>
   struct FindEdgeTagIndicator {
     static const bool value = false;

lemon/bits/vector_map.h

@@ -39 +39 @@
   // \brief Graph map based on the std::vector storage.
   //
-  // The VectorMap template class is graph map structure what
-  // automatically updates the map when a key is added to or erased from
-  // the map. This map type uses the std::vector to store the values.
+  // The VectorMap template class is graph map structure that automatically
+  // updates the map when a key is added to or erased from the graph.
+  // This map type uses std::vector to store the values.
   //
   // \tparam _Graph The graph this map is attached to.
@@ -170 +170 @@
     // \brief Adds a new key to the map.
     //
-    // It adds a new key to the map. It called by the observer notifier
+    // It adds a new key to the map. It is called by the observer notifier
     // and it overrides the add() member function of the observer base.
     virtual void add(const Key& key) {
@@ -181 +181 @@
     // \brief Adds more new keys to the map.
     //
-    // It adds more new keys to the map. It called by the observer notifier
+    // It adds more new keys to the map. It is called by the observer notifier
     // and it overrides the add() member function of the observer base.
     virtual void add(const std::vector<Key>& keys) {
@@ -196 +196 @@
     // \brief Erase a key from the map.
     //
-    // Erase a key from the map. It called by the observer notifier
+    // Erase a key from the map. It is called by the observer notifier
     // and it overrides the erase() member function of the observer base.
     virtual void erase(const Key& key) {
@@ -204 +204 @@
     // \brief Erase more keys from the map.
     //
-    // Erase more keys from the map. It called by the observer notifier
+    // It erases more keys from the map. It is called by the observer notifier
     // and it overrides the erase() member function of the observer base.
     virtual void erase(const std::vector<Key>& keys) {
@@ -212 +212 @@
     }
 
-    // \brief Buildes the map.
-    //
-    // It buildes the map. It called by the observer notifier
+    // \brief Build the map.
+    //
+    // It builds the map. It is called by the observer notifier
     // and it overrides the build() member function of the observer base.
     virtual void build() {
@@ -224 +224 @@
     // \brief Clear the map.
     //
-    // It erase all items from the map. It called by the observer notifier
+    // It erases all items from the map. It is called by the observer notifier
     // and it overrides the clear() member function of the observer base.
     virtual void clear() {

lemon/list_graph.h

@@ -841 +841 @@
 
     public:
-      operator Edge() const { 
-        return id != -1 ? edgeFromId(id / 2) : INVALID; 
+      operator Edge() const {
+        return id != -1 ? edgeFromId(id / 2) : INVALID;
       }
 

lemon/random.h

@@ -541 +541 @@
     /// @{
 
-    ///\name Initialization
-    ///
-    /// @{
-
     /// \brief Default constructor
     ///
@@ -693 +689 @@
     }
 
-    /// @}
-
-    ///\name Uniform distributions
-    ///
-    /// @{
-
     /// \brief Returns a random real number from the range [0, 1)
     ///
@@ -753 +743 @@
       return _random_bits::IntConversion<Number, Word>::convert(core);
     }
-
-    /// @}
 
     unsigned int uinteger() {
@@ -789 +777 @@
     ///\name Non-uniform distributions
     ///
-
     ///@{
 
-    /// \brief Returns a random bool
+    /// \brief Returns a random bool with given probability of true result.
     ///
     /// It returns a random bool with given probability of true result.
@@ -799 +786 @@
     }
 
-    /// Standard Gauss distribution
-
-    /// Standard Gauss distribution.
+    /// Standard normal (Gauss) distribution
+
+    /// Standard normal (Gauss) distribution.
     /// \note The Cartesian form of the Box-Muller
     /// transformation is used to generate a random normal distribution.
@@ -814 +801 @@
       return std::sqrt(-2*std::log(S)/S)*V1;
     }
-    /// Gauss distribution with given mean and standard deviation
-
-    /// Gauss distribution with given mean and standard deviation.
+    /// Normal (Gauss) distribution with given mean and standard deviation
+
+    /// Normal (Gauss) distribution with given mean and standard deviation.
     /// \sa gauss()
     double gauss(double mean,double std_dev)
     {
       return gauss()*std_dev+mean;
+    }
+
+    /// Lognormal distribution
+
+    /// Lognormal distribution. The parameters are the mean and the standard
+    /// deviation of <tt>exp(X)</tt>.
+    ///
+    double lognormal(double n_mean,double n_std_dev)
+    {
+      return std::exp(gauss(n_mean,n_std_dev));
+    }
+    /// Lognormal distribution
+
+    /// Lognormal distribution. The parameter is an <tt>std::pair</tt> of
+    /// the mean and the standard deviation of <tt>exp(X)</tt>.
+    ///
+    double lognormal(const std::pair<double,double> &params)
+    {
+      return std::exp(gauss(params.first,params.second));
+    }
+    /// Compute the lognormal parameters from mean and standard deviation
+
+    /// This function computes the lognormal parameters from mean and
+    /// standard deviation. The return value can direcly be passed to
+    /// lognormal().
+    std::pair<double,double> lognormalParamsFromMD(double mean,
+                                                   double std_dev)
+    {
+      double fr=std_dev/mean;
+      fr*=fr;
+      double lg=std::log(1+fr);
+      return std::pair<double,double>(std::log(mean)-lg/2.0,std::sqrt(lg));
+    }
+    /// Lognormal distribution with given mean and standard deviation
+
+    /// Lognormal distribution with given mean and standard deviation.
+    ///
+    double lognormalMD(double mean,double std_dev)
+    {
+      return lognormal(lognormalParamsFromMD(mean,std_dev));
     }
 
@@ -926 +953 @@
     ///\name Two dimensional distributions
     ///
-
     ///@{
 
@@ -943 +969 @@
       return dim2::Point<double>(V1,V2);
     }
-    /// A kind of two dimensional Gauss distribution
+    /// A kind of two dimensional normal (Gauss) distribution
 
     /// This function provides a turning symmetric two-dimensional distribution.

lemon/smart_graph.h

@@ -68 +68 @@
 
     typedef True NodeNumTag;
-    typedef True EdgeNumTag;
+    typedef True ArcNumTag;
 
     int nodeNum() const { return nodes.size(); }
@@ -306 +306 @@
       nodes[b._id].first_out=nodes[n._id].first_out;
       nodes[n._id].first_out=-1;
-      for(int i=nodes[b._id].first_out;i!=-1;i++) arcs[i].source=b._id;
+      for(int i=nodes[b._id].first_out; i!=-1; i=arcs[i].next_out) {
+        arcs[i].source=b._id;
+      }
       if(connect) addArc(n,b);
       return b;
@@ -465 +467 @@
 
     public:
-      operator Edge() const { 
-        return _id != -1 ? edgeFromId(_id / 2) : INVALID; 
+      operator Edge() const {
+        return _id != -1 ? edgeFromId(_id / 2) : INVALID;
       }
 
@@ -481 +483 @@
       : nodes(), arcs() {}
 
+    typedef True NodeNumTag;
+    typedef True EdgeNumTag;
+    typedef True ArcNumTag;
+
+    int nodeNum() const { return nodes.size(); }
+    int edgeNum() const { return arcs.size() / 2; }
+    int arcNum() const { return arcs.size(); }
 
     int maxNodeId() const { return nodes.size()-1; }
@@ -729 +738 @@
         dir.push_back(arcFromId(n-1));
         Parent::notifier(Arc()).erase(dir);
-        nodes[arcs[n].target].first_out=arcs[n].next_out;
-        nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
+        nodes[arcs[n-1].target].first_out=arcs[n].next_out;
+        nodes[arcs[n].target].first_out=arcs[n-1].next_out;
         arcs.pop_back();
         arcs.pop_back();

scripts/chg-len.py

@@ -2 +2 @@
 
 import sys
-import os
+
+from mercurial import ui, hg
 
 if len(sys.argv)>1 and sys.argv[1] in ["-h","--help"]:
@@ -10 +11 @@
 """
     exit(0)
-plist = os.popen("HGRCPATH='' hg parents --template='{rev}\n'").readlines()
-if len(plist)>1:
-    print "You are in the process of merging"
-    exit(1)
-PAR = int(plist[0])
 
-f = os.popen("HGRCPATH='' hg log -r 0:tip --template='{rev} {parents}\n'").\
-    readlines()
-REV = -1
-lengths=[]
-for l in f:
-    REV+=1
-    s = l.split()
-    rev = int(s[0])
-    if REV != rev:
-        print "Something is seriously wrong"
-        exit(1)
-    if len(s) == 1:
-        par1 = par2 = rev - 1
-    elif len(s) == 2:
-        par1 = par2 = int(s[1].split(":")[0])
+u = ui.ui()
+r = hg.repository(u, ".")
+N = r.changectx(".").rev()
+lengths=[0]*(N+1)
+for i in range(N+1):
+    p=r.changectx(i).parents()
+    if p[0]:
+        p0=lengths[p[0].rev()]
     else:
-        par1 = int(s[1].split(":")[0])
-        par2 = int(s[2].split(":")[0])
-    if rev == 0:
-        lengths.append(0)
+        p0=-1
+    if len(p)>1 and p[1]:
+        p1=lengths[p[1].rev()]
     else:
-        lengths.append(max(lengths[par1],lengths[par2])+1)
-print lengths[PAR]
+        p1=-1
+    lengths[i]=max(p0,p1)+1
+print lengths[N]

scripts/unify-sources.sh

@@ -4 +4 @@
 HGROOT=`hg root`
 
-function update_header() {
+# file enumaration modes
+
+function all_files() {
+    hg status -a -m -c |
+    cut -d ' ' -f 2 | grep -E '(\.(cc|h|dox)$|Makefile\.am$)' |
+    while read file; do echo $HGROOT/$file; done
+}
+
+function modified_files() {
+    hg status -a -m |
+    cut -d ' ' -f 2 | grep -E  '(\.(cc|h|dox)$|Makefile\.am$)' |
+    while read file; do echo $HGROOT/$file; done
+}
+
+function changed_files() {
+    {
+        if [ -n "$HG_PARENT1" ]
+        then
+            hg status --rev $HG_PARENT1:$HG_NODE -a -m
+        fi
+        if [ -n "$HG_PARENT2" ]
+        then
+            hg status --rev $HG_PARENT2:$HG_NODE -a -m
+        fi
+    } | cut -d ' ' -f 2 | grep -E '(\.(cc|h|dox)$|Makefile\.am$)' | 
+    sort | uniq |
+    while read file; do echo $HGROOT/$file; done
+}
+
+function given_files() {
+    for file in $GIVEN_FILES
+    do
+        echo $file
+    done
+}
+
+# actions
+
+function update_action() {
+    if ! diff -q $1 $2 >/dev/null
+    then
+        echo -n " [$3 updated]"
+        rm $2
+        mv $1 $2
+        CHANGED=YES
+    fi
+}
+
+function update_warning() {
+    echo -n " [$2 warning]"
+    WARNED=YES
+}
+
+function update_init() {
+    echo Update source files...
+    TOTAL_FILES=0
+    CHANGED_FILES=0
+    WARNED_FILES=0
+}
+
+function update_done() {
+    echo $CHANGED_FILES out of $TOTAL_FILES files has been changed.
+    echo $WARNED_FILES out of $TOTAL_FILES files triggered warnings.
+}
+
+function update_begin() {
+    ((TOTAL_FILES++))
+    CHANGED=NO
+    WARNED=NO
+}
+
+function update_end() {
+    if [ $CHANGED == YES ]
+    then
+        ((++CHANGED_FILES))
+    fi
+    if [ $WARNED == YES ]
+    then
+        ((++WARNED_FILES))
+    fi
+}
+
+function check_action() {
+    if [ "$3" == 'tabs' ]
+    then
+        PATTERN=$(echo -e '\t')
+    elif [ "$3" == 'trailing spaces' ]
+    then
+        PATTERN='\ +$'
+    else
+        PATTERN='*'
+    fi
+
+    if ! diff -q $1 $2 >/dev/null
+    then
+        if [ "$PATTERN" == '*' ]
+        then
+            diff $1 $2 | grep '^[0-9]' | sed "s|^\(.*\)c.*$|$2:\1: check failed: $3|g" |
+              sed "s/:\([0-9]*\),\([0-9]*\):\(.*\)$/:\1:\3 (until line \2)/g"
+        else
+            grep -n -E "$PATTERN" $2 | sed "s|^\([0-9]*\):.*$|$2:\1: check failed: $3|g"
+        fi
+        FAILED=YES
+    fi
+}
+
+function check_warning() {
+    if [ "$2" == 'long lines' ]
+    then
+        grep -n -E '.{81,}' $1 | sed "s|^\([0-9]*\):.*$|$1:\1: warning: $2|g"
+    else
+        echo "$1: warning: $2"
+    fi
+    WARNED=YES
+}
+
+function check_init() {
+    echo Check source files...
+    FAILED_FILES=0
+    WARNED_FILES=0
+    TOTAL_FILES=0
+}
+
+function check_done() {
+    echo $FAILED_FILES out of $TOTAL_FILES files has been failed.
+    echo $WARNED_FILES out of $TOTAL_FILES files triggered warnings.
+
+    if [ $FAILED_FILES -gt 0 ]
+    then
+        return 1
+    elif [ $WARNED_FILES -gt 0 ]
+    then
+        if [ "$WARNING" == 'INTERACTIVE' ]
+        then
+            echo -n "Are the files with warnings acceptable? (yes/no) "
+            while read answer
+            do
+                if [ "$answer" == 'yes' ]
+                then
+                    return 0
+                elif [ "$answer" == 'no' ]
+                then
+                    return 1
+                fi
+                echo -n "Are the files with warnings acceptable? (yes/no) "
+            done
+        elif [ "$WARNING" == 'WERROR' ]
+        then
+            return 1
+        fi
+    fi
+}
+
+function check_begin() {
+    ((TOTAL_FILES++))
+    FAILED=NO
+    WARNED=NO
+}
+
+function check_end() {
+    if [ $FAILED == YES ]
+    then
+        ((++FAILED_FILES))
+    fi
+    if [ $WARNED == YES ]
+    then
+        ((++WARNED_FILES))
+    fi
+}
+
+
+
+# checks
+
+function header_check() {
+    if echo $1 | grep -q -E 'Makefile\.am$'
+    then
+        return
+    fi
+
     TMP_FILE=`mktemp`
-    FILE_NAME=$1
 
     (echo "/* -*- mode: C++; indent-tabs-mode: nil; -*-
@@ -26 +204 @@
  */
 "
-        awk 'BEGIN { pm=0; }
+    awk 'BEGIN { pm=0; }
      pm==3 { print }
      /\/\* / && pm==0 { pm=1;}
@@ -32 +210 @@
      /\*\// && pm==1 { pm=2;}
     ' $1
-        ) >$TMP_FILE
-
-    HEADER_CH=`diff -q $TMP_FILE $FILE_NAME >/dev/null&&echo NO||echo YES`
-
-    rm $FILE_NAME
-    mv $TMP_FILE $FILE_NAME
-}
-
-function update_tabs() {
+    ) >$TMP_FILE
+
+    "$ACTION"_action "$TMP_FILE" "$1" header
+}
+
+function tabs_check() {
+    if echo $1 | grep -q -v -E 'Makefile\.am$'
+    then
+        OLD_PATTERN=$(echo -e '\t')
+        NEW_PATTERN='        '
+    else
+        OLD_PATTERN='        '
+        NEW_PATTERN=$(echo -e '\t')
+    fi
     TMP_FILE=`mktemp`
-    FILE_NAME=$1
-
-    cat $1 |
-    sed -e 's/\t/        /g' >$TMP_FILE
-
-    TABS_CH=`diff -q $TMP_FILE $FILE_NAME >/dev/null&&echo NO||echo YES`
-
-    rm $FILE_NAME
-    mv $TMP_FILE $FILE_NAME
-}
-
-function remove_trailing_space() {
+    cat $1 | sed -e "s/$OLD_PATTERN/$NEW_PATTERN/g" >$TMP_FILE
+
+    "$ACTION"_action "$TMP_FILE" "$1" 'tabs'
+}
+
+function spaces_check() {
     TMP_FILE=`mktemp`
-    FILE_NAME=$1
-
-    cat $1 |
-    sed -e 's/ \+$//g' >$TMP_FILE
-
-    SPACES_CH=`diff -q $TMP_FILE $FILE_NAME >/dev/null&&echo NO||echo YES`
-
-    rm $FILE_NAME
-    mv $TMP_FILE $FILE_NAME
-}
-
-function long_line_test() {
-    cat $1 |grep -q -E '.{81,}'
-}
-
-function update_file() {
-    echo -n '    update' $i ...
-
-    update_header $1
-    update_tabs $1
-    remove_trailing_space $1
-
-    CHANGED=NO;
-    if [[ $HEADER_CH = YES ]];
-    then
-        echo -n '  [header updated]'
-        CHANGED=YES;
-    fi
-    if [[ $TABS_CH = YES ]];
-    then
-        echo -n ' [tabs removed]'
-        CHANGED=YES;
-    fi
-    if [[ $SPACES_CH = YES ]];
-    then
-        echo -n ' [trailing spaces removed]'
-        CHANGED=YES;
-    fi
-    if long_line_test $1 ;
-    then
-        echo -n ' [LONG LINES]'
-        ((LONG_LINE_FILES++))
-    fi
-    echo
-    if [[ $CHANGED = YES ]];
-    then
-        ((CHANGED_FILES++))
-    fi
-}
-
-CHANGED_FILES=0
-TOTAL_FILES=0
-LONG_LINE_FILES=0
-if [ $# == 0 ]; then
-    echo Update all source files...
-    for i in `hg manifest|grep -E  '\.(cc|h|dox)$'`
+    cat $1 | sed -e 's/ \+$//g' >$TMP_FILE
+
+    "$ACTION"_action "$TMP_FILE" "$1" 'trailing spaces'
+}
+
+function long_lines_check() {
+    if cat $1 | grep -q -E '.{81,}'
+    then
+        "$ACTION"_warning $1 'long lines'
+    fi
+}
+
+# process the file
+
+function process_file() {
+    if [ "$ACTION" == 'update' ]
+    then
+        echo -n "    $ACTION $1..."
+    else
+        echo "    $ACTION $1..."
+    fi
+
+    CHECKING="header tabs spaces long_lines"
+
+    "$ACTION"_begin $1
+    for check in $CHECKING
     do
-        update_file $HGROOT/$i
-        ((TOTAL_FILES++))
+        "$check"_check $1
     done
-    echo '  done.'
-else
-    for i in $*
+    "$ACTION"_end $1
+    if [ "$ACTION" == 'update' ]
+    then
+        echo
+    fi
+}
+
+function process_all {
+    "$ACTION"_init
+    while read file
     do
-        update_file $i
-        ((TOTAL_FILES++))
-    done
+        process_file $file
+    done < <($FILES)
+    "$ACTION"_done
+}
+
+while [ $# -gt 0 ]
+do
+    
+    if [ "$1" == '--help' ] || [ "$1" == '-h' ]
+    then
+        echo -n \
+"Usage:
+  $0 [OPTIONS] [files]
+Options:
+  --dry-run|-n
+     Check the files, but do not modify them.
+  --interactive|-i
+     If --dry-run is specified and the checker emits warnings,
+     then the user is asked if the warnings should be considered
+     errors.
+  --werror|-w
+     Make all warnings into errors.
+  --all|-a
+     Check all source files in the repository.
+  --modified|-m
+     Check only the modified (and new) source files. This option is
+     useful to check the modification before making a commit.
+  --changed|-c
+     Check only the changed source files compared to the parent(s) of
+     the current hg node.  This option is useful as hg hook script.
+     To automatically check all your changes before making a commit,
+     add the following section to the appropriate .hg/hgrc file.
+
+       [hooks]
+       pretxncommit.checksources = scripts/unify-sources.sh -c -n -i
+
+  --help|-h
+     Print this help message.
+  files
+     The files to check/unify. If no file names are given, the modified
+     source files will be checked/unified (just like using the
+     --modified|-m option).
+"
+        exit 0
+    elif [ "$1" == '--dry-run' ] || [ "$1" == '-n' ]
+    then
+        [ -n "$ACTION" ] && echo "Conflicting action options" >&2 && exit 1
+        ACTION=check
+    elif [ "$1" == "--all" ] || [ "$1" == '-a' ]
+    then
+        [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1
+        FILES=all_files
+    elif [ "$1" == "--changed" ] || [ "$1" == '-c' ]
+    then
+        [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1
+        FILES=changed_files
+    elif [ "$1" == "--modified" ] || [ "$1" == '-m' ]
+    then
+        [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1
+        FILES=modified_files
+    elif [ "$1" == "--interactive" ] || [ "$1" == "-i" ]
+    then
+        [ -n "$WARNING" ] && echo "Conflicting warning options" >&2 && exit 1
+        WARNING='INTERACTIVE'
+    elif [ "$1" == "--werror" ] || [ "$1" == "-w" ]
+    then
+        [ -n "$WARNING" ] && echo "Conflicting warning options" >&2 && exit 1
+        WARNING='WERROR'
+    elif [ $(echo x$1 | cut -c 2) == '-' ]
+    then
+        echo "Invalid option $1" >&2 && exit 1
+    else
+        [ -n "$FILES" ] && echo "Invalid option $1" >&2 && exit 1
+        GIVEN_FILES=$@
+        FILES=given_files
+        break
+    fi
+    
+    shift
+done
+
+if [ -z $FILES ]
+then
+    FILES=modified_files
 fi
-echo $CHANGED_FILES out of $TOTAL_FILES files has been changed.
-if [[ $LONG_LINE_FILES -gt 1 ]]; then
-    echo
-    echo WARNING: $LONG_LINE_FILES files contains long lines!    
-    echo
-elif [[ $LONG_LINE_FILES -gt 0 ]]; then
-    echo
-    echo WARNING: a file contains long lines!
-    echo
+
+if [ -z $ACTION ]
+then
+    ACTION=update
 fi
+
+process_all

test/CMakeLists.txt

@@ -17 +17 @@
   kruskal_test
   maps_test
+  max_matching_test
   random_test
   path_test

test/Makefile.am

@@ -1 +1 @@
 EXTRA_DIST += \
-        test/CMakeLists.txt
+        test/CMakeLists.txt \
+        test/min_cost_flow_test.lgf
 
 noinst_HEADERS += \
@@ -20 +21 @@
         test/kruskal_test \
         test/maps_test \
+        test/max_matching_test \
         test/random_test \
         test/path_test \
+        test/suurballe_test \
         test/test_tools_fail \
         test/test_tools_pass \
@@ -43 +46 @@
 test_kruskal_test_SOURCES = test/kruskal_test.cc
 test_maps_test_SOURCES = test/maps_test.cc
+test_max_matching_test_SOURCES = test/max_matching_test.cc
 test_path_test_SOURCES = test/path_test.cc
+test_suurballe_test_SOURCES = test/suurballe_test.cc
 test_random_test_SOURCES = test/random_test.cc
 test_test_tools_fail_SOURCES = test/test_tools_fail.cc

test/digraph_test.cc

@@ -20 +20 @@
 #include <lemon/list_graph.h>
 #include <lemon/smart_graph.h>
-//#include <lemon/full_graph.h>
-//#include <lemon/hypercube_graph.h>
+#include <lemon/full_graph.h>
 
 #include "test_tools.h"
@@ -30 +29 @@
 
 template <class Digraph>
-void checkDigraph() {
+void checkDigraphBuild() {
   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   Digraph G;
@@ -59 +58 @@
   checkGraphConArcList(G, 1);
 
-  Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
+  Arc a2 = G.addArc(n2, n1),
+      a3 = G.addArc(n2, n3),
+      a4 = G.addArc(n2, n3);
+
   checkGraphNodeList(G, 3);
   checkGraphArcList(G, 4);
@@ -77 +79 @@
   checkGraphNodeMap(G);
   checkGraphArcMap(G);
-
-}
-
+}
+
+template <class Digraph>
+void checkDigraphSplit() {
+  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+
+  Digraph G;
+  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
+  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
+      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
+
+  Node n4 = G.split(n2);
+
+  check(G.target(OutArcIt(G, n2)) == n4 &&
+        G.source(InArcIt(G, n4)) == n2,
+        "Wrong split.");
+
+  checkGraphNodeList(G, 4);
+  checkGraphArcList(G, 5);
+
+  checkGraphOutArcList(G, n1, 1);
+  checkGraphOutArcList(G, n2, 1);
+  checkGraphOutArcList(G, n3, 0);
+  checkGraphOutArcList(G, n4, 3);
+
+  checkGraphInArcList(G, n1, 1);
+  checkGraphInArcList(G, n2, 1);
+  checkGraphInArcList(G, n3, 2);
+  checkGraphInArcList(G, n4, 1);
+
+  checkGraphConArcList(G, 5);
+}
+
+template <class Digraph>
+void checkDigraphAlter() {
+  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+
+  Digraph G;
+  Node n1 = G.addNode(), n2 = G.addNode(),
+       n3 = G.addNode(), n4 = G.addNode();
+  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
+      a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3),
+      a5 = G.addArc(n2, n4);
+
+  checkGraphNodeList(G, 4);
+  checkGraphArcList(G, 5);
+
+  // Check changeSource() and changeTarget()
+  G.changeTarget(a4, n1);
+
+  checkGraphNodeList(G, 4);
+  checkGraphArcList(G, 5);
+
+  checkGraphOutArcList(G, n1, 1);
+  checkGraphOutArcList(G, n2, 1);
+  checkGraphOutArcList(G, n3, 0);
+  checkGraphOutArcList(G, n4, 3);
+
+  checkGraphInArcList(G, n1, 2);
+  checkGraphInArcList(G, n2, 1);
+  checkGraphInArcList(G, n3, 1);
+  checkGraphInArcList(G, n4, 1);
+
+  checkGraphConArcList(G, 5);
+
+  G.changeSource(a4, n3);
+
+  checkGraphNodeList(G, 4);
+  checkGraphArcList(G, 5);
+
+  checkGraphOutArcList(G, n1, 1);
+  checkGraphOutArcList(G, n2, 1);
+  checkGraphOutArcList(G, n3, 1);
+  checkGraphOutArcList(G, n4, 2);
+
+  checkGraphInArcList(G, n1, 2);
+  checkGraphInArcList(G, n2, 1);
+  checkGraphInArcList(G, n3, 1);
+  checkGraphInArcList(G, n4, 1);
+
+  checkGraphConArcList(G, 5);
+
+  // Check contract()
+  G.contract(n2, n4, false);
+
+  checkGraphNodeList(G, 3);
+  checkGraphArcList(G, 5);
+
+  checkGraphOutArcList(G, n1, 1);
+  checkGraphOutArcList(G, n2, 3);
+  checkGraphOutArcList(G, n3, 1);
+
+  checkGraphInArcList(G, n1, 2);
+  checkGraphInArcList(G, n2, 2);
+  checkGraphInArcList(G, n3, 1);
+
+  checkGraphConArcList(G, 5);
+
+  G.contract(n2, n1);
+
+  checkGraphNodeList(G, 2);
+  checkGraphArcList(G, 3);
+
+  checkGraphOutArcList(G, n2, 2);
+  checkGraphOutArcList(G, n3, 1);
+
+  checkGraphInArcList(G, n2, 2);
+  checkGraphInArcList(G, n3, 1);
+
+  checkGraphConArcList(G, 3);
+}
+
+template <class Digraph>
+void checkDigraphErase() {
+  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+
+  Digraph G;
+  Node n1 = G.addNode(), n2 = G.addNode(),
+       n3 = G.addNode(), n4 = G.addNode();
+  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
+      a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1),
+      a5 = G.addArc(n2, n4);
+
+  // Check arc deletion
+  G.erase(a1);
+
+  checkGraphNodeList(G, 4);
+  checkGraphArcList(G, 4);
+
+  checkGraphOutArcList(G, n1, 0);
+  checkGraphOutArcList(G, n2, 1);
+  checkGraphOutArcList(G, n3, 1);
+  checkGraphOutArcList(G, n4, 2);
+
+  checkGraphInArcList(G, n1, 2);
+  checkGraphInArcList(G, n2, 0);
+  checkGraphInArcList(G, n3, 1);
+  checkGraphInArcList(G, n4, 1);
+
+  checkGraphConArcList(G, 4);
+
+  // Check node deletion
+  G.erase(n4);
+
+  checkGraphNodeList(G, 3);
+  checkGraphArcList(G, 1);
+
+  checkGraphOutArcList(G, n1, 0);
+  checkGraphOutArcList(G, n2, 0);
+  checkGraphOutArcList(G, n3, 1);
+  checkGraphOutArcList(G, n4, 0);
+
+  checkGraphInArcList(G, n1, 1);
+  checkGraphInArcList(G, n2, 0);
+  checkGraphInArcList(G, n3, 0);
+  checkGraphInArcList(G, n4, 0);
+
+  checkGraphConArcList(G, 1);
+}
+
+
+template <class Digraph>
+void checkDigraphSnapshot() {
+  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
+
+  Digraph G;
+  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
+  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
+      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
+
+  typename Digraph::Snapshot snapshot(G);
+
+  Node n = G.addNode();
+  G.addArc(n3, n);
+  G.addArc(n, n3);
+
+  checkGraphNodeList(G, 4);
+  checkGraphArcList(G, 6);
+
+  snapshot.restore();
+
+  checkGraphNodeList(G, 3);
+  checkGraphArcList(G, 4);
+
+  checkGraphOutArcList(G, n1, 1);
+  checkGraphOutArcList(G, n2, 3);
+  checkGraphOutArcList(G, n3, 0);
+
+  checkGraphInArcList(G, n1, 1);
+  checkGraphInArcList(G, n2, 1);
+  checkGraphInArcList(G, n3, 2);
+
+  checkGraphConArcList(G, 4);
+
+  checkNodeIds(G);
+  checkArcIds(G);
+  checkGraphNodeMap(G);
+  checkGraphArcMap(G);
+
+  G.addNode();
+  snapshot.save(G);
+
+  G.addArc(G.addNode(), G.addNode());
+
+  snapshot.restore();
+
+  checkGraphNodeList(G, 4);
+  checkGraphArcList(G, 4);
+}
 
 void checkConcepts() {
@@ -110 +318 @@
     checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
   }
-//  { // Checking FullDigraph
-//    checkConcept<Digraph, FullDigraph>();
-//  }
-//  { // Checking HyperCubeDigraph
-//    checkConcept<Digraph, HyperCubeDigraph>();
-//  }
+  { // Checking FullDigraph
+    checkConcept<Digraph, FullDigraph>();
+  }
 }
 
@@ -168 +373 @@
 }
 
+void checkFullDigraph(int num) {
+  typedef FullDigraph Digraph;
+  DIGRAPH_TYPEDEFS(Digraph);
+  Digraph G(num);
+
+  checkGraphNodeList(G, num);
+  checkGraphArcList(G, num * num);
+
+  for (NodeIt n(G); n != INVALID; ++n) {
+    checkGraphOutArcList(G, n, num);
+    checkGraphInArcList(G, n, num);
+  }
+
+  checkGraphConArcList(G, num * num);
+
+  checkNodeIds(G);
+  checkArcIds(G);
+  checkGraphNodeMap(G);
+  checkGraphArcMap(G);
+
+  for (int i = 0; i < G.nodeNum(); ++i) {
+    check(G.index(G(i)) == i, "Wrong index");
+  }
+
+  for (NodeIt s(G); s != INVALID; ++s) {
+    for (NodeIt t(G); t != INVALID; ++t) {
+      Arc a = G.arc(s, t);
+      check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
+    }
+  }
+}
+
 void checkDigraphs() {
   { // Checking ListDigraph
-    checkDigraph<ListDigraph>();
+    checkDigraphBuild<ListDigraph>();
+    checkDigraphSplit<ListDigraph>();
+    checkDigraphAlter<ListDigraph>();
+    checkDigraphErase<ListDigraph>();
+    checkDigraphSnapshot<ListDigraph>();
     checkDigraphValidityErase<ListDigraph>();
   }
   { // Checking SmartDigraph
-    checkDigraph<SmartDigraph>();
+    checkDigraphBuild<SmartDigraph>();
+    checkDigraphSplit<SmartDigraph>();
+    checkDigraphSnapshot<SmartDigraph>();
     checkDigraphValidity<SmartDigraph>();
+  }
+  { // Checking FullDigraph
+    checkFullDigraph(8);
   }
 }

test/graph_test.cc

@@ -20 +20 @@
 #include <lemon/list_graph.h>
 #include <lemon/smart_graph.h>
-// #include <lemon/full_graph.h>
-// #include <lemon/grid_graph.h>
+#include <lemon/full_graph.h>
+#include <lemon/grid_graph.h>
+#include <lemon/hypercube_graph.h>
 
 #include "test_tools.h"
@@ -30 +31 @@
 
 template <class Graph>
-void checkGraph() {
+void checkGraphBuild() {
   TEMPLATE_GRAPH_TYPEDEFS(Graph);
 
@@ -36 +37 @@
   checkGraphNodeList(G, 0);
   checkGraphEdgeList(G, 0);
+  checkGraphArcList(G, 0);
 
   Node
@@ -43 +45 @@
   checkGraphNodeList(G, 3);
   checkGraphEdgeList(G, 0);
+  checkGraphArcList(G, 0);
 
   Edge e1 = G.addEdge(n1, n2);
   check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
         "Wrong edge");
-  checkGraphNodeList(G, 3);
+
+  checkGraphNodeList(G, 3);
+  checkGraphEdgeList(G, 1);
   checkGraphArcList(G, 2);
-  checkGraphEdgeList(G, 1);
-
-  checkGraphOutArcList(G, n1, 1);
-  checkGraphOutArcList(G, n2, 1);
-  checkGraphOutArcList(G, n3, 0);
-
-  checkGraphInArcList(G, n1, 1);
-  checkGraphInArcList(G, n2, 1);
-  checkGraphInArcList(G, n3, 0);
-
-  checkGraphIncEdgeList(G, n1, 1);
-  checkGraphIncEdgeList(G, n2, 1);
-  checkGraphIncEdgeList(G, n3, 0);
-
+
+  checkGraphIncEdgeArcLists(G, n1, 1);
+  checkGraphIncEdgeArcLists(G, n2, 1);
+  checkGraphIncEdgeArcLists(G, n3, 0);
+
+  checkGraphConEdgeList(G, 1);
   checkGraphConArcList(G, 2);
-  checkGraphConEdgeList(G, 1);
-
-  Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
-  checkGraphNodeList(G, 3);
+
+  Edge e2 = G.addEdge(n2, n1),
+       e3 = G.addEdge(n2, n3);
+
+  checkGraphNodeList(G, 3);
+  checkGraphEdgeList(G, 3);
   checkGraphArcList(G, 6);
-  checkGraphEdgeList(G, 3);
-
-  checkGraphOutArcList(G, n1, 2);
-  checkGraphOutArcList(G, n2, 3);
-  checkGraphOutArcList(G, n3, 1);
-
-  checkGraphInArcList(G, n1, 2);
-  checkGraphInArcList(G, n2, 3);
-  checkGraphInArcList(G, n3, 1);
-
-  checkGraphIncEdgeList(G, n1, 2);
-  checkGraphIncEdgeList(G, n2, 3);
-  checkGraphIncEdgeList(G, n3, 1);
-
+
+  checkGraphIncEdgeArcLists(G, n1, 2);
+  checkGraphIncEdgeArcLists(G, n2, 3);
+  checkGraphIncEdgeArcLists(G, n3, 1);
+
+  checkGraphConEdgeList(G, 3);
   checkGraphConArcList(G, 6);
-  checkGraphConEdgeList(G, 3);
 
   checkArcDirections(G);
@@ -96 +86 @@
 }
 
+template <class Graph>
+void checkGraphAlter() {
+  TEMPLATE_GRAPH_TYPEDEFS(Graph);
+
+  Graph G;
+  Node n1 = G.addNode(), n2 = G.addNode(),
+       n3 = G.addNode(), n4 = G.addNode();
+  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
+       e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
+       e5 = G.addEdge(n4, n3);
+
+  checkGraphNodeList(G, 4);
+  checkGraphEdgeList(G, 5);
+  checkGraphArcList(G, 10);
+
+  // Check changeU() and changeV()
+  if (G.u(e2) == n2) {
+    G.changeU(e2, n3);
+  } else {
+    G.changeV(e2, n3);
+  }
+
+  checkGraphNodeList(G, 4);
+  checkGraphEdgeList(G, 5);
+  checkGraphArcList(G, 10);
+
+  checkGraphIncEdgeArcLists(G, n1, 3);
+  checkGraphIncEdgeArcLists(G, n2, 2);
+  checkGraphIncEdgeArcLists(G, n3, 3);
+  checkGraphIncEdgeArcLists(G, n4, 2);
+
+  checkGraphConEdgeList(G, 5);
+  checkGraphConArcList(G, 10);
+
+  if (G.u(e2) == n1) {
+    G.changeU(e2, n2);
+  } else {
+    G.changeV(e2, n2);
+  }
+
+  checkGraphNodeList(G, 4);
+  checkGraphEdgeList(G, 5);
+  checkGraphArcList(G, 10);
+
+  checkGraphIncEdgeArcLists(G, n1, 2);
+  checkGraphIncEdgeArcLists(G, n2, 3);
+  checkGraphIncEdgeArcLists(G, n3, 3);
+  checkGraphIncEdgeArcLists(G, n4, 2);
+
+  checkGraphConEdgeList(G, 5);
+  checkGraphConArcList(G, 10);
+
+  // Check contract()
+  G.contract(n1, n4, false);
+
+  checkGraphNodeList(G, 3);
+  checkGraphEdgeList(G, 5);
+  checkGraphArcList(G, 10);
+
+  checkGraphIncEdgeArcLists(G, n1, 4);
+  checkGraphIncEdgeArcLists(G, n2, 3);
+  checkGraphIncEdgeArcLists(G, n3, 3);
+
+  checkGraphConEdgeList(G, 5);
+  checkGraphConArcList(G, 10);
+
+  G.contract(n2, n3);
+
+  checkGraphNodeList(G, 2);
+  checkGraphEdgeList(G, 3);
+  checkGraphArcList(G, 6);
+
+  checkGraphIncEdgeArcLists(G, n1, 4);
+  checkGraphIncEdgeArcLists(G, n2, 2);
+
+  checkGraphConEdgeList(G, 3);
+  checkGraphConArcList(G, 6);
+}
+
+template <class Graph>
+void checkGraphErase() {
+  TEMPLATE_GRAPH_TYPEDEFS(Graph);
+
+  Graph G;
+  Node n1 = G.addNode(), n2 = G.addNode(),
+       n3 = G.addNode(), n4 = G.addNode();
+  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
+       e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
+       e5 = G.addEdge(n4, n3);
+
+  // Check edge deletion
+  G.erase(e2);
+
+  checkGraphNodeList(G, 4);
+  checkGraphEdgeList(G, 4);
+  checkGraphArcList(G, 8);
+
+  checkGraphIncEdgeArcLists(G, n1, 2);
+  checkGraphIncEdgeArcLists(G, n2, 2);
+  checkGraphIncEdgeArcLists(G, n3, 2);
+  checkGraphIncEdgeArcLists(G, n4, 2);
+
+  checkGraphConEdgeList(G, 4);
+  checkGraphConArcList(G, 8);
+
+  // Check node deletion
+  G.erase(n3);
+
+  checkGraphNodeList(G, 3);
+  checkGraphEdgeList(G, 2);
+  checkGraphArcList(G, 4);
+
+  checkGraphIncEdgeArcLists(G, n1, 2);
+  checkGraphIncEdgeArcLists(G, n2, 1);
+  checkGraphIncEdgeArcLists(G, n4, 1);
+
+  checkGraphConEdgeList(G, 2);
+  checkGraphConArcList(G, 4);
+}
+
+
+template <class Graph>
+void checkGraphSnapshot() {
+  TEMPLATE_GRAPH_TYPEDEFS(Graph);
+
+  Graph G;
+  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
+  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
+       e3 = G.addEdge(n2, n3);
+
+  checkGraphNodeList(G, 3);
+  checkGraphEdgeList(G, 3);
+  checkGraphArcList(G, 6);
+
+  typename Graph::Snapshot snapshot(G);
+
+  Node n = G.addNode();
+  G.addEdge(n3, n);
+  G.addEdge(n, n3);
+  G.addEdge(n3, n2);
+
+  checkGraphNodeList(G, 4);
+  checkGraphEdgeList(G, 6);
+  checkGraphArcList(G, 12);
+
+  snapshot.restore();
+
+  checkGraphNodeList(G, 3);
+  checkGraphEdgeList(G, 3);
+  checkGraphArcList(G, 6);
+
+  checkGraphIncEdgeArcLists(G, n1, 2);
+  checkGraphIncEdgeArcLists(G, n2, 3);
+  checkGraphIncEdgeArcLists(G, n3, 1);
+
+  checkGraphConEdgeList(G, 3);
+  checkGraphConArcList(G, 6);
+
+  checkNodeIds(G);
+  checkEdgeIds(G);
+  checkArcIds(G);
+  checkGraphNodeMap(G);
+  checkGraphEdgeMap(G);
+  checkGraphArcMap(G);
+
+  G.addNode();
+  snapshot.save(G);
+
+  G.addEdge(G.addNode(), G.addNode());
+
+  snapshot.restore();
+
+  checkGraphNodeList(G, 4);
+  checkGraphEdgeList(G, 3);
+  checkGraphArcList(G, 6);
+}
+
+void checkFullGraph(int num) {
+  typedef FullGraph Graph;
+  GRAPH_TYPEDEFS(Graph);
+
+  Graph G(num);
+  checkGraphNodeList(G, num);
+  checkGraphEdgeList(G, num * (num - 1) / 2);
+
+  for (NodeIt n(G); n != INVALID; ++n) {
+    checkGraphOutArcList(G, n, num - 1);
+    checkGraphInArcList(G, n, num - 1);
+    checkGraphIncEdgeList(G, n, num - 1);
+  }
+
+  checkGraphConArcList(G, num * (num - 1));
+  checkGraphConEdgeList(G, num * (num - 1) / 2);
+
+  checkArcDirections(G);
+
+  checkNodeIds(G);
+  checkArcIds(G);
+  checkEdgeIds(G);
+  checkGraphNodeMap(G);
+  checkGraphArcMap(G);
+  checkGraphEdgeMap(G);
+
+
+  for (int i = 0; i < G.nodeNum(); ++i) {
+    check(G.index(G(i)) == i, "Wrong index");
+  }
+
+  for (NodeIt u(G); u != INVALID; ++u) {
+    for (NodeIt v(G); v != INVALID; ++v) {
+      Edge e = G.edge(u, v);
+      Arc a = G.arc(u, v);
+      if (u == v) {
+        check(e == INVALID, "Wrong edge lookup");
+        check(a == INVALID, "Wrong arc lookup");
+      } else {
+        check((G.u(e) == u && G.v(e) == v) ||
+              (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");
+        check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");
+      }
+    }
+  }
+}
+
 void checkConcepts() {
   { // Checking graph components
@@ -125 +339 @@
     checkConcept<ClearableGraphComponent<>, SmartGraph>();
   }
-//  { // Checking FullGraph
-//    checkConcept<Graph, FullGraph>();
-//    checkGraphIterators<FullGraph>();
-//  }
-//  { // Checking GridGraph
-//    checkConcept<Graph, GridGraph>();
-//    checkGraphIterators<GridGraph>();
-//  }
+  { // Checking FullGraph
+    checkConcept<Graph, FullGraph>();
+  }
+  { // Checking GridGraph
+    checkConcept<Graph, GridGraph>();
+  }
+  { // Checking HypercubeGraph
+    checkConcept<Graph, HypercubeGraph>();
+  }
 }
 
@@ -189 +404 @@
 }
 
-// void checkGridGraph(const GridGraph& g, int w, int h) {
-//   check(g.width() == w, "Wrong width");
-//   check(g.height() == h, "Wrong height");
-
-//   for (int i = 0; i < w; ++i) {
-//     for (int j = 0; j < h; ++j) {
-//       check(g.col(g(i, j)) == i, "Wrong col");
-//       check(g.row(g(i, j)) == j, "Wrong row");
-//     }
-//   }
-
-//   for (int i = 0; i < w; ++i) {
-//     for (int j = 0; j < h - 1; ++j) {
-//       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
-//       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
-//     }
-//     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
-//   }
-
-//   for (int i = 0; i < w; ++i) {
-//     for (int j = 1; j < h; ++j) {
-//       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
-//       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
-//     }
-//     check(g.up(g(i, 0)) == INVALID, "Wrong up");
-//   }
-
-//   for (int j = 0; j < h; ++j) {
-//     for (int i = 0; i < w - 1; ++i) {
-//       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
-//       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");
-//     }
-//     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");
-//   }
-
-//   for (int j = 0; j < h; ++j) {
-//     for (int i = 1; i < w; ++i) {
-//       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
-//       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
-//     }
-//     check(g.left(g(0, j)) == INVALID, "Wrong left");
-//   }
-// }
+void checkGridGraph(int width, int height) {
+  typedef GridGraph Graph;
+  GRAPH_TYPEDEFS(Graph);
+  Graph G(width, height);
+
+  check(G.width() == width, "Wrong column number");
+  check(G.height() == height, "Wrong row number");
+
+  for (int i = 0; i < width; ++i) {
+    for (int j = 0; j < height; ++j) {
+      check(G.col(G(i, j)) == i, "Wrong column");
+      check(G.row(G(i, j)) == j, "Wrong row");
+      check(G.pos(G(i, j)).x == i, "Wrong column");
+      check(G.pos(G(i, j)).y == j, "Wrong row");
+    }
+  }
+
+  for (int j = 0; j < height; ++j) {
+    for (int i = 0; i < width - 1; ++i) {
+      check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");
+      check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");
+    }
+    check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
+  }
+
+  for (int j = 0; j < height; ++j) {
+    for (int i = 1; i < width; ++i) {
+      check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");
+      check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");
+    }
+    check(G.left(G(0, j)) == INVALID, "Wrong left");
+  }
+
+  for (int i = 0; i < width; ++i) {
+    for (int j = 0; j < height - 1; ++j) {
+      check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");
+      check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");
+    }
+    check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
+  }
+
+  for (int i = 0; i < width; ++i) {
+    for (int j = 1; j < height; ++j) {
+      check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");
+      check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");
+    }
+    check(G.down(G(i, 0)) == INVALID, "Wrong down");
+  }
+
+  checkGraphNodeList(G, width * height);
+  checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
+  checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
+
+  for (NodeIt n(G); n != INVALID; ++n) {
+    int nb = 4;
+    if (G.col(n) == 0) --nb;
+    if (G.col(n) == width - 1) --nb;
+    if (G.row(n) == 0) --nb;
+    if (G.row(n) == height - 1) --nb;
+
+    checkGraphOutArcList(G, n, nb);
+    checkGraphInArcList(G, n, nb);
+    checkGraphIncEdgeList(G, n, nb);
+  }
+
+  checkArcDirections(G);
+
+  checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
+  checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
+
+  checkNodeIds(G);
+  checkArcIds(G);
+  checkEdgeIds(G);
+  checkGraphNodeMap(G);
+  checkGraphArcMap(G);
+  checkGraphEdgeMap(G);
+
+}
+
+void checkHypercubeGraph(int dim) {
+  GRAPH_TYPEDEFS(HypercubeGraph);
+
+  HypercubeGraph G(dim);
+  checkGraphNodeList(G, 1 << dim);
+  checkGraphEdgeList(G, dim * (1 << (dim-1)));
+  checkGraphArcList(G, dim * (1 << dim));
+
+  Node n = G.nodeFromId(dim);
+
+  for (NodeIt n(G); n != INVALID; ++n) {
+    checkGraphIncEdgeList(G, n, dim);
+    for (IncEdgeIt e(G, n); e != INVALID; ++e) {
+      check( (G.u(e) == n &&
+              G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) ||
+             (G.v(e) == n &&
+              G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))),
+             "Wrong edge or wrong dimension");
+    }
+
+    checkGraphOutArcList(G, n, dim);
+    for (OutArcIt a(G, n); a != INVALID; ++a) {
+      check(G.source(a) == n &&
+            G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))),
+            "Wrong arc or wrong dimension");
+    }
+
+    checkGraphInArcList(G, n, dim);
+    for (InArcIt a(G, n); a != INVALID; ++a) {
+      check(G.target(a) == n &&
+            G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))),
+            "Wrong arc or wrong dimension");
+    }
+  }
+
+  checkGraphConArcList(G, (1 << dim) * dim);
+  checkGraphConEdgeList(G, dim * (1 << (dim-1)));
+
+  checkArcDirections(G);
+
+  checkNodeIds(G);
+  checkArcIds(G);
+  checkEdgeIds(G);
+  checkGraphNodeMap(G);
+  checkGraphArcMap(G);
+  checkGraphEdgeMap(G);
+}
 
 void checkGraphs() {
   { // Checking ListGraph
-    checkGraph<ListGraph>();
+    checkGraphBuild<ListGraph>();
+    checkGraphAlter<ListGraph>();
+    checkGraphErase<ListGraph>();
+    checkGraphSnapshot<ListGraph>();
     checkGraphValidityErase<ListGraph>();
   }
   { // Checking SmartGraph
-    checkGraph<SmartGraph>();
+    checkGraphBuild<SmartGraph>();
+    checkGraphSnapshot<SmartGraph>();
     checkGraphValidity<SmartGraph>();
   }
-//   { // Checking FullGraph
-//     FullGraph g(5);
-//     checkGraphNodeList(g, 5);
-//     checkGraphEdgeList(g, 10);
-//   }
-//   { // Checking GridGraph
-//     GridGraph g(5, 6);
-//     checkGraphNodeList(g, 30);
-//     checkGraphEdgeList(g, 49);
-//     checkGridGraph(g, 5, 6);
-//   }
+  { // Checking FullGraph
+    checkFullGraph(7);
+    checkFullGraph(8);
+  }
+  { // Checking GridGraph
+    checkGridGraph(5, 8);
+    checkGridGraph(8, 5);
+    checkGridGraph(5, 5);
+    checkGridGraph(0, 0);
+    checkGridGraph(1, 1);
+  }
+  { // Checking HypercubeGraph
+    checkHypercubeGraph(1);
+    checkHypercubeGraph(2);
+    checkHypercubeGraph(3);
+    checkHypercubeGraph(4);
+  }
 }
 

test/graph_test.h

@@ -115 +115 @@
     check(e==INVALID,"Wrong IncEdge list linking.");
     check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
+  }
+
+  template <class Graph>
+  void checkGraphIncEdgeArcLists(const Graph &G, typename Graph::Node n,
+                                 int cnt)
+  {
+    checkGraphIncEdgeList(G, n, cnt);
+    checkGraphOutArcList(G, n, cnt);
+    checkGraphInArcList(G, n, cnt);
   }
 

tools/lemon-0.x-to-1.x.sh

@@ -4 +4 @@
 
 if [ $# -eq 0 -o x$1 = "x-h" -o x$1 = "x-help" -o x$1 = "x--help" ]; then
-        echo "Usage:"
-        echo "  $0 source-file"
-        exit
+    echo "Usage:"
+    echo "  $0 source-file(s)"
+    exit
 fi
 
-TMP=`mktemp`
-
-sed     -e "s/undirected graph/_gr_aph_label_/g"\
-        -e "s/undirected edge/_ed_ge_label_/g"\
-        -e "s/graph_/_gr_aph_label__/g"\
-        -e "s/_graph/__gr_aph_label_/g"\
-        -e "s/UGraph/_Gr_aph_label_/g"\
-        -e "s/uGraph/_gr_aph_label_/g"\
-        -e "s/ugraph/_gr_aph_label_/g"\
-        -e "s/Graph/_Digr_aph_label_/g"\
-        -e "s/graph/_digr_aph_label_/g"\
-        -e "s/UEdge/_Ed_ge_label_/g"\
-        -e "s/uEdge/_ed_ge_label_/g"\
-        -e "s/uedge/_ed_ge_label_/g"\
-        -e "s/IncEdgeIt/_In_cEd_geIt_label_/g"\
-        -e "s/Edge/_Ar_c_label_/g"\
-        -e "s/edge/_ar_c_label_/g"\
-        -e "s/ANode/_Re_d_label_/g"\
-        -e "s/BNode/_Blu_e_label_/g"\
-        -e "s/A-Node/_Re_d_label_/g"\
-        -e "s/B-Node/_Blu_e_label_/g"\
-        -e "s/anode/_re_d_label_/g"\
-        -e "s/bnode/_blu_e_label_/g"\
-        -e "s/aNode/_re_d_label_/g"\
-        -e "s/bNode/_blu_e_label_/g"\
-        -e "s/_Digr_aph_label_/Digraph/g"\
-        -e "s/_digr_aph_label_/digraph/g"\
-        -e "s/_Gr_aph_label_/Graph/g"\
-        -e "s/_gr_aph_label_/graph/g"\
-        -e "s/_Ar_c_label_/Arc/g"\
-        -e "s/_ar_c_label_/arc/g"\
-        -e "s/_Ed_ge_label_/Edge/g"\
-        -e "s/_ed_ge_label_/edge/g"\
-        -e "s/_In_cEd_geIt_label_/IncEdgeIt/g"\
-        -e "s/_Re_d_label_/Red/g"\
-        -e "s/_Blu_e_label_/Blue/g"\
-        -e "s/_re_d_label_/red/g"\
-        -e "s/_blu_e_label_/blue/g"\
-        -e "s/\(\W\)DefPredMap\(\W\)/\1SetPredMap\2/g"\
-        -e "s/\(\W\)DefPredMap$/\1SetPredMap/g"\
-        -e "s/^DefPredMap\(\W\)/SetPredMap\1/g"\
-        -e "s/^DefPredMap$/SetPredMap/g"\
-        -e "s/\(\W\)DefDistMap\(\W\)/\1SetDistMap\2/g"\
-        -e "s/\(\W\)DefDistMap$/\1SetDistMap/g"\
-        -e "s/^DefDistMap\(\W\)/SetDistMap\1/g"\
-        -e "s/^DefDistMap$/SetDistMap/g"\
-        -e "s/\(\W\)DefReachedMap\(\W\)/\1SetReachedMap\2/g"\
-        -e "s/\(\W\)DefReachedMap$/\1SetReachedMap/g"\
-        -e "s/^DefReachedMap\(\W\)/SetReachedMap\1/g"\
-        -e "s/^DefReachedMap$/SetReachedMap/g"\
-        -e "s/\(\W\)DefProcessedMap\(\W\)/\1SetProcessedMap\2/g"\
-        -e "s/\(\W\)DefProcessedMap$/\1SetProcessedMap/g"\
-        -e "s/^DefProcessedMap\(\W\)/SetProcessedMap\1/g"\
-        -e "s/^DefProcessedMap$/SetProcessedMap/g"\
-        -e "s/\(\W\)DefHeap\(\W\)/\1SetHeap\2/g"\
-        -e "s/\(\W\)DefHeap$/\1SetHeap/g"\
-        -e "s/^DefHeap\(\W\)/SetHeap\1/g"\
-        -e "s/^DefHeap$/SetHeap/g"\
-        -e "s/\(\W\)DefStandardHeap\(\W\)/\1SetStandradHeap\2/g"\
-        -e "s/\(\W\)DefStandardHeap$/\1SetStandradHeap/g"\
-        -e "s/^DefStandardHeap\(\W\)/SetStandradHeap\1/g"\
-        -e "s/^DefStandardHeap$/SetStandradHeap/g"\
-        -e "s/\(\W\)DefOperationTraits\(\W\)/\1SetOperationTraits\2/g"\
-        -e "s/\(\W\)DefOperationTraits$/\1SetOperationTraits/g"\
-        -e "s/^DefOperationTraits\(\W\)/SetOperationTraits\1/g"\
-        -e "s/^DefOperationTraits$/SetOperationTraits/g"\
-        -e "s/\(\W\)DefProcessedMapToBeDefaultMap\(\W\)/\1SetStandardProcessedMap\2/g"\
-        -e "s/\(\W\)DefProcessedMapToBeDefaultMap$/\1SetStandardProcessedMap/g"\
-        -e "s/^DefProcessedMapToBeDefaultMap\(\W\)/SetStandardProcessedMap\1/g"\
-        -e "s/^DefProcessedMapToBeDefaultMap$/SetStandardProcessedMap/g"\
-        -e "s/\(\W\)IntegerMap\(\W\)/\1RangeMap\2/g"\
-        -e "s/\(\W\)IntegerMap$/\1RangeMap/g"\
-        -e "s/^IntegerMap\(\W\)/RangeMap\1/g"\
-        -e "s/^IntegerMap$/RangeMap/g"\
-        -e "s/\(\W\)integerMap\(\W\)/\1rangeMap\2/g"\
-        -e "s/\(\W\)integerMap$/\1rangeMap/g"\
-        -e "s/^integerMap\(\W\)/rangeMap\1/g"\
-        -e "s/^integerMap$/rangeMap/g"\
-        -e "s/\(\W\)copyGraph\(\W\)/\1graphCopy\2/g"\
-        -e "s/\(\W\)copyGraph$/\1graphCopy/g"\
-        -e "s/^copyGraph\(\W\)/graphCopy\1/g"\
-        -e "s/^copyGraph$/graphCopy/g"\
-        -e "s/\(\W\)copyDigraph\(\W\)/\1digraphCopy\2/g"\
-        -e "s/\(\W\)copyDigraph$/\1digraphCopy/g"\
-        -e "s/^copyDigraph\(\W\)/digraphCopy\1/g"\
-        -e "s/^copyDigraph$/digraphCopy/g"\
-        -e "s/\(\W\)\([sS]\)tdMap\(\W\)/\1\2parseMap\3/g"\
-        -e "s/\(\W\)\([sS]\)tdMap$/\1\2parseMap/g"\
-        -e "s/^\([sS]\)tdMap\(\W\)/\1parseMap\2/g"\
-        -e "s/^\([sS]\)tdMap$/\1parseMap/g"\
-        -e "s/\(\W\)\([Ff]\)unctorMap\(\W\)/\1\2unctorToMap\3/g"\
-        -e "s/\(\W\)\([Ff]\)unctorMap$/\1\2unctorToMap/g"\
-        -e "s/^\([Ff]\)unctorMap\(\W\)/\1unctorToMap\2/g"\
-        -e "s/^\([Ff]\)unctorMap$/\1unctorToMap/g"\
-        -e "s/\(\W\)\([Mm]\)apFunctor\(\W\)/\1\2apToFunctor\3/g"\
-        -e "s/\(\W\)\([Mm]\)apFunctor$/\1\2apToFunctor/g"\
-        -e "s/^\([Mm]\)apFunctor\(\W\)/\1apToFunctor\2/g"\
-        -e "s/^\([Mm]\)apFunctor$/\1apToFunctor/g"\
-        -e "s/\(\W\)\([Ff]\)orkWriteMap\(\W\)/\1\2orkMap\3/g"\
-        -e "s/\(\W\)\([Ff]\)orkWriteMap$/\1\2orkMap/g"\
-        -e "s/^\([Ff]\)orkWriteMap\(\W\)/\1orkMap\2/g"\
-        -e "s/^\([Ff]\)orkWriteMap$/\1orkMap/g"\
-        -e "s/\(\W\)StoreBoolMap\(\W\)/\1LoggerBoolMap\2/g"\
-        -e "s/\(\W\)StoreBoolMap$/\1LoggerBoolMap/g"\
-        -e "s/^StoreBoolMap\(\W\)/LoggerBoolMap\1/g"\
-        -e "s/^StoreBoolMap$/LoggerBoolMap/g"\
-        -e "s/\(\W\)storeBoolMap\(\W\)/\1loggerBoolMap\2/g"\
-        -e "s/\(\W\)storeBoolMap$/\1loggerBoolMap/g"\
-        -e "s/^storeBoolMap\(\W\)/loggerBoolMap\1/g"\
-        -e "s/^storeBoolMap$/loggerBoolMap/g"\
-        -e "s/\(\W\)BoundingBox\(\W\)/\1Box\2/g"\
-        -e "s/\(\W\)BoundingBox$/\1Box/g"\
-        -e "s/^BoundingBox\(\W\)/Box\1/g"\
-        -e "s/^BoundingBox$/Box/g"\
-<$1 > $TMP
-
-mv $TMP $1
+for i in $@
+do
+    echo Update $i...
+    TMP=`mktemp`
+    sed -e "s/\<undirected graph\>/_gr_aph_label_/g"\
+        -e "s/\<undirected graphs\>/_gr_aph_label_s/g"\
+        -e "s/\<undirected edge\>/_ed_ge_label_/g"\
+        -e "s/\<undirected edges\>/_ed_ge_label_s/g"\
+        -e "s/\<directed graph\>/_digr_aph_label_/g"\
+        -e "s/\<directed graphs\>/_digr_aph_label_s/g"\
+        -e "s/\<directed edge\>/_ar_c_label_/g"\
+        -e "s/\<directed edges\>/_ar_c_label_s/g"\
+        -e "s/UGraph/_Gr_aph_label_/g"\
+        -e "s/u[Gg]raph/_gr_aph_label_/g"\
+        -e "s/\<Graph\>/_Digr_aph_label_/g"\
+        -e "s/\<graph\>/_digr_aph_label_/g"\
+        -e "s/\<Graphs\>/_Digr_aph_label_s/g"\
+        -e "s/\<graphs\>/_digr_aph_label_s/g"\
+        -e "s/_Graph/__Gr_aph_label_/g"\
+        -e "s/\([Gg]\)raph\([a-z_]\)/_\1r_aph_label_\2/g"\
+        -e "s/\([a-z_]\)graph/\1_gr_aph_label_/g"\
+        -e "s/Graph/_Digr_aph_label_/g"\
+        -e "s/graph/_digr_aph_label_/g"\
+        -e "s/UEdge/_Ed_ge_label_/g"\
+        -e "s/u[Ee]dge/_ed_ge_label_/g"\
+        -e "s/IncEdgeIt/_In_cEd_geIt_label_/g"\
+        -e "s/\<Edge\>/_Ar_c_label_/g"\
+        -e "s/\<edge\>/_ar_c_label_/g"\
+        -e "s/\<Edges\>/_Ar_c_label_s/g"\
+        -e "s/\<edges\>/_ar_c_label_s/g"\
+        -e "s/_Edge/__Ed_ge_label_/g"\
+        -e "s/Edge\([a-z_]\)/_Ed_ge_label_\1/g"\
+        -e "s/edge\([a-z_]\)/_ed_ge_label_\1/g"\
+        -e "s/\([a-z_]\)edge/\1_ed_ge_label_/g"\
+        -e "s/Edge/_Ar_c_label_/g"\
+        -e "s/edge/_ar_c_label_/g"\
+        -e "s/A[Nn]ode/_Re_d_label_/g"\
+        -e "s/B[Nn]ode/_Blu_e_label_/g"\
+        -e "s/A-[Nn]ode/_Re_d_label_/g"\
+        -e "s/B-[Nn]ode/_Blu_e_label_/g"\
+        -e "s/a[Nn]ode/_re_d_label_/g"\
+        -e "s/b[Nn]ode/_blu_e_label_/g"\
+        -e "s/\<UGRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__GR_APH_TY_PEDE_FS_label_\1/g"\
+        -e "s/\<GRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__DIGR_APH_TY_PEDE_FS_label_\1/g"\
+        -e "s/\<UGRAPH_TYPEDEFS\>/_GR_APH_TY_PEDE_FS_label_/g"\
+        -e "s/\<GRAPH_TYPEDEFS\>/_DIGR_APH_TY_PEDE_FS_label_/g"\
+        -e "s/_Digr_aph_label_/Digraph/g"\
+        -e "s/_digr_aph_label_/digraph/g"\
+        -e "s/_Gr_aph_label_/Graph/g"\
+        -e "s/_gr_aph_label_/graph/g"\
+        -e "s/_Ar_c_label_/Arc/g"\
+        -e "s/_ar_c_label_/arc/g"\
+        -e "s/_Ed_ge_label_/Edge/g"\
+        -e "s/_ed_ge_label_/edge/g"\
+        -e "s/_In_cEd_geIt_label_/IncEdgeIt/g"\
+        -e "s/_Re_d_label_/Red/g"\
+        -e "s/_Blu_e_label_/Blue/g"\
+        -e "s/_re_d_label_/red/g"\
+        -e "s/_blu_e_label_/blue/g"\
+        -e "s/_GR_APH_TY_PEDE_FS_label_/GRAPH_TYPEDEFS/g"\
+        -e "s/_DIGR_APH_TY_PEDE_FS_label_/DIGRAPH_TYPEDEFS/g"\
+        -e "s/DigraphToEps/GraphToEps/g"\
+        -e "s/digraphToEps/graphToEps/g"\
+        -e "s/\<DefPredMap\>/SetPredMap/g"\
+        -e "s/\<DefDistMap\>/SetDistMap/g"\
+        -e "s/\<DefReachedMap\>/SetReachedMap/g"\
+        -e "s/\<DefProcessedMap\>/SetProcessedMap/g"\
+        -e "s/\<DefHeap\>/SetHeap/g"\
+        -e "s/\<DefStandardHeap\>/SetStandradHeap/g"\
+        -e "s/\<DefOperationTraits\>/SetOperationTraits/g"\
+        -e "s/\<DefProcessedMapToBeDefaultMap\>/SetStandardProcessedMap/g"\
+        -e "s/\<copyGraph\>/graphCopy/g"\
+        -e "s/\<copyDigraph\>/digraphCopy/g"\
+        -e "s/\<HyperCubeDigraph\>/HypercubeGraph/g"\
+        -e "s/\<IntegerMap\>/RangeMap/g"\
+        -e "s/\<integerMap\>/rangeMap/g"\
+        -e "s/\<\([sS]\)tdMap\>/\1parseMap/g"\
+        -e "s/\<\([Ff]\)unctorMap\>/\1unctorToMap/g"\
+        -e "s/\<\([Mm]\)apFunctor\>/\1apToFunctor/g"\
+        -e "s/\<\([Ff]\)orkWriteMap\>/\1orkMap/g"\
+        -e "s/\<StoreBoolMap\>/LoggerBoolMap/g"\
+        -e "s/\<storeBoolMap\>/loggerBoolMap/g"\
+        -e "s/\<BoundingBox\>/Box/g"\
+        -e "s/\<readNauty\>/readNautyGraph/g"\
+    <$i > $TMP
+    mv $TMP $i
+done