COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [371:164fe3abc024:370:00c8843d491d] in lemon-1.1


Ignore:
Files:
10 deleted
24 edited

Legend:

Unmodified
Added
Removed

  • Makefile.am

    r363 r321  
    11ACLOCAL_AMFLAGS = -I m4
    2 
    3 AM_CXXFLAGS = $(WARNINGCXXFLAGS)
    42
    53AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)

  • configure.ac

    r363 r310  
    1919AC_CONFIG_SRCDIR([lemon/list_graph.h])
    2020AC_CONFIG_HEADERS([config.h lemon/config.h])
     21
     22lx_cmdline_cxxflags_set=${CXXFLAGS+set}
    2123
    2224dnl Do compilation tests using the C++ compiler.
    … …  
    4547
    4648dnl Set custom compiler flags when using g++.
    47 if test "$GXX" = yes -a "$ICC" = no; then
    48   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"
     49if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes -a "$ICC" = no; then
     50  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"
    4951fi
    50 AC_SUBST([WARNINGCXXFLAGS])
    5152
    5253dnl Checks for libraries.
    … …  
    113114echo
    114115echo C++ compiler.................. : $CXX
    115 echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
     116echo C++ compiles flags............ : $CXXFLAGS
    116117echo
    117118#echo GLPK support.................. : $lx_glpk_found

  • doc/CMakeLists.txt

    r335 r225  
    1414      COMMAND rm -rf gen-images
    1515      COMMAND mkdir gen-images
    16       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
    1716      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
    1817      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

    r367 r316  
    6767ENABLED_SECTIONS       =
    6868MAX_INITIALIZER_LINES  = 5
    69 SHOW_USED_FILES        = NO
     69SHOW_USED_FILES        = YES
    7070SHOW_DIRECTORIES       = YES
    7171SHOW_FILES             = YES

  • doc/Makefile.am

    r337 r317  
    1515
    1616DOC_EPS_IMAGES18 = \
    17         grid_graph.eps \
    1817        nodeshape_0.eps \
    1918        nodeshape_1.eps \

  • doc/groups.dox

    r351 r318  
    465465
    466466/**
    467 @defgroup lemon_io LEMON Graph Format
     467@defgroup lemon_io LEMON Input-Output
    468468@ingroup io_group
    469469\brief Reading and writing LEMON Graph Format.
    … …  
    480480This group describes general \c EPS drawing methods and special
    481481graph exporting tools.
    482 */
    483 
    484 /**
    485 @defgroup nauty_group NAUTY Format
    486 @ingroup io_group
    487 \brief Read \e Nauty format
    488 Tool to read graphs from \e Nauty format data.
    489482*/
    490483

  • doc/migration.dox

    r343 r314  
    2626
    2727Many of these changes adjusted automatically by the
    28 <tt>lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual
     28<tt>script/lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual
    2929update are typeset <b>boldface</b>.
    3030
    … …  
    5454
    5555\warning
    56 <b>The <tt>lemon-0.x-to-1.x.sh</tt> script replaces the words \c graph,
    57 \c ugraph, \c edge and \c uedge in your own identifiers and in
    58 strings, comments etc. as well as in all LEMON specific identifiers.
    59 So use the script carefully and make a backup copy of your source files
    60 before applying the script to them.</b>
     56<b>The <tt>script/lemon-0.x-to-1.x.sh</tt> tool replaces all instances of
     57the words \c graph, \c digraph, \c edge and \c arc, so it replaces them
     58in strings, comments etc. as well as in all identifiers.</b>
    6159
    6260\section migration-lgf LGF tools

  • lemon/Makefile.am

    r366 r259  
    1313        lemon/random.cc
    1414
    15 #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) $(AM_CXXFLAGS)
     15#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
    1616#lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
    1717
    … …  
    2929        lemon/dim2.h \
    3030        lemon/error.h \
    31         lemon/full_graph.h \
    3231        lemon/graph_to_eps.h \
    33         lemon/grid_graph.h \
    34         lemon/hypercube_graph.h \
    3532        lemon/kruskal.h \
    3633        lemon/lgf_reader.h \
    … …  
    3936        lemon/maps.h \
    4037        lemon/math.h \
    41         lemon/max_matching.h \
    42         lemon/nauty_reader.h \
    4338        lemon/path.h \
    4439        lemon/random.h \
    4540        lemon/smart_graph.h \
    46         lemon/suurballe.h \
    4741        lemon/time_measure.h \
    4842        lemon/tolerance.h \

  • lemon/bfs.h

    r329 r301  
    5252    ///Instantiates a PredMap.
    5353
    54     ///This function instantiates a PredMap. 
     54    ///This function instantiates a PredMap.
    5555    ///\param g is the digraph, to which we would like to define the
    5656    ///PredMap.
    … …  
    8181    ///The type of the map that indicates which nodes are reached.
    8282
    83     ///The type of the map that indicates which nodes are reached.///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     83    ///The type of the map that indicates which nodes are reached.
     84    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8485    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8586    ///Instantiates a ReachedMap.

  • lemon/bits/alteration_notifier.h

    r361 r314  
    3636  // a container.
    3737  //
    38   // The simple graphs can be refered as two containers: a node container
    39   // and an edge container. But they do not store values directly, they
    40   // are just key continars for more value containers, which are the
    41   // node and edge maps.
    42   //
    43   // The node and edge sets of the graphs can be changed as we add or erase
     38  // The simple graph's can be refered as two containers, one node container
     39  // and one edge container. But they are not standard containers they
     40  // does not store values directly they are just key continars for more
     41  // value containers which are the node and edge maps.
     42  //
     43  // The graph's node and edge sets can be changed as we add or erase
    4444  // nodes and edges in the graph. LEMON would like to handle easily
    4545  // that the node and edge maps should contain values for all nodes or
    4646  // edges. If we want to check on every indicing if the map contains
    4747  // the current indicing key that cause a drawback in the performance
    48   // in the library. We use another solution: we notify all maps about
     48  // in the library. We use another solution we notify all maps about
    4949  // an alteration in the graph, which cause only drawback on the
    5050  // alteration of the graph.
    5151  //
    52   // This class provides an interface to a node or edge container.
    53   // The first() and next() member functions make possible
    54   // to iterate on the keys of the container.
    55   // The id() function returns an integer id for each key.
    56   // The maxId() function gives back an upper bound of the ids.
     52  // This class provides an interface to the container. The \e first() and \e
     53  // next() member functions make possible to iterate on the keys of the
     54  // container. The \e id() function returns an integer id for each key.
     55  // The \e maxId() function gives back an upper bound of the ids.
    5756  //
    5857  // For the proper functonality of this class, we should notify it
    59   // about each alteration in the container. The alterations have four type:
    60   // add(), erase(), build() and clear(). The add() and
    61   // erase() signal that only one or few items added or erased to or
    62   // from the graph. If all items are erased from the graph or if a new graph
    63   // is built from an empty graph, then it can be signaled with the
     58  // about each alteration in the container. The alterations have four type
     59  // as \e add(), \e erase(), \e build() and \e clear(). The \e add() and
     60  // \e erase() signals that only one or few items added or erased to or
     61  // from the graph. If all items are erased from the graph or from an empty
     62  // graph a new graph is builded then it can be signaled with the
    6463  // clear() and build() members. Important rule that if we erase items
    65   // from graphs we should first signal the alteration and after that erase
     64  // from graph we should first signal the alteration and after that erase
    6665  // them from the container, on the other way on item addition we should
    6766  // first extend the container and just after that signal the alteration.
    6867  //
    6968  // The alteration can be observed with a class inherited from the
    70   // ObserverBase nested class. The signals can be handled with
     69  // \e ObserverBase nested class. The signals can be handled with
    7170  // overriding the virtual functions defined in the base class.  The
    7271  // observer base can be attached to the notifier with the
    73   // attach() member and can be detached with detach() function. The
     72  // \e attach() member and can be detached with detach() function. The
    7473  // alteration handlers should not call any function which signals
    7574  // an other alteration in the same notifier and should not
    7675  // detach any observer from the notifier.
    7776  //
    78   // Alteration observers try to be exception safe. If an add() or
    79   // a clear() function throws an exception then the remaining
     77  // Alteration observers try to be exception safe. If an \e add() or
     78  // a \e clear() function throws an exception then the remaining
    8079  // observeres will not be notified and the fulfilled additions will
    81   // be rolled back by calling the erase() or clear() functions.
    82   // Hence erase() and clear() should not throw exception.
    83   // Actullay, they can throw only \ref ImmediateDetach exception,
    84   // which detach the observer from the notifier.
    85   //
    86   // There are some cases, when the alteration observing is not completly
     80  // be rolled back by calling the \e erase() or \e clear()
     81  // functions. Thence the \e erase() and \e clear() should not throw
     82  // exception. Actullay, it can be throw only \ref ImmediateDetach
     83  // exception which detach the observer from the notifier.
     84  //
     85  // There are some place when the alteration observing is not completly
    8786  // reliable. If we want to carry out the node degree in the graph
    88   // as in the \ref InDegMap and we use the reverseArc(), then it cause
     87  // as in the \ref InDegMap and we use the reverseEdge that cause
    8988  // unreliable functionality. Because the alteration observing signals
    90   // only erasing and adding but not the reversing, it will stores bad
    91   // degrees. Apart form that the subgraph adaptors cannot even signal
    92   // the alterations because just a setting in the filter map can modify
    93   // the graph and this cannot be watched in any way.
     89  // only erasing and adding but not the reversing it will stores bad
     90  // degrees. The sub graph adaptors cannot signal the alterations because
     91  // just a setting in the filter map can modify the graph and this cannot
     92  // be watched in any way.
    9493  //
    9594  // \param _Container The container which is observed.
    … …  
    105104    typedef _Item Item;
    106105
    107     // \brief Exception which can be called from clear() and
    108     // erase().
    109     //
    110     // From the clear() and erase() function only this
     106    // \brief Exception which can be called from \e clear() and
     107    // \e erase().
     108    //
     109    // From the \e clear() and \e erase() function only this
    111110    // exception is allowed to throw. The exception immediatly
    112111    // detaches the current observer from the notifier. Because the
    113     // clear() and erase() should not throw other exceptions
     112    // \e clear() and \e erase() should not throw other exceptions
    114113    // it can be used to invalidate the observer.
    115114    struct ImmediateDetach {};
    … …  
    123122    // The observer interface contains some pure virtual functions
    124123    // to override. The add() and erase() functions are
    125     // to notify the oberver when one item is added or erased.
     124    // to notify the oberver when one item is added or
     125    // erased.
    126126    //
    127127    // The build() and clear() members are to notify the observer

  • lemon/bits/array_map.h

    r361 r314  
    3737  // \brief Graph map based on the array storage.
    3838  //
    39   // The ArrayMap template class is graph map structure that automatically
    40   // updates the map when a key is added to or erased from the graph.
    41   // This map uses the allocators to implement the container functionality.
     39  // The ArrayMap template class is graph map structure what
     40  // automatically updates the map when a key is added to or erased from
     41  // the map. This map uses the allocators to implement
     42  // the container functionality.
    4243  //
    43   // The template parameters are the Graph, the current Item type and
     44  // The template parameters are the Graph the current Item type and
    4445  // the Value type of the map.
    4546  template <typename _Graph, typename _Item, typename _Value>
    … …  
    4748    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
    4849  public:
    49     // The graph type.
     50    // The graph type of the maps.
    5051    typedef _Graph Graph;
    51     // The item type.
     52    // The item type of the map.
    5253    typedef _Item Item;
    5354    // The reference map tag.
    5455    typedef True ReferenceMapTag;
    5556
    56     // The key type of the map.
     57    // The key type of the maps.
    5758    typedef _Item Key;
    5859    // The value type of the map.
    … …  
    200201    // \brief Adds a new key to the map.
    201202    //
    202     // It adds a new key to the map. It is called by the observer notifier
     203    // It adds a new key to the map. It called by the observer notifier
    203204    // and it overrides the add() member function of the observer base.
    204205    virtual void add(const Key& key) {
    … …  
    228229    // \brief Adds more new keys to the map.
    229230    //
    230     // It adds more new keys to the map. It is called by the observer notifier
     231    // It adds more new keys to the map. It called by the observer notifier
    231232    // and it overrides the add() member function of the observer base.
    232233    virtual void add(const std::vector<Key>& keys) {
    … …  
    272273    // \brief Erase a key from the map.
    273274    //
    274     // Erase a key from the map. It is called by the observer notifier
     275    // Erase a key from the map. It called by the observer notifier
    275276    // and it overrides the erase() member function of the observer base.
    276277    virtual void erase(const Key& key) {
    … …  
    281282    // \brief Erase more keys from the map.
    282283    //
    283     // Erase more keys from the map. It is called by the observer notifier
     284    // Erase more keys from the map. It called by the observer notifier
    284285    // and it overrides the erase() member function of the observer base.
    285286    virtual void erase(const std::vector<Key>& keys) {
    … …  
    290291    }
    291292
    292     // \brief Builds the map.
    293     //
    294     // It builds the map. It is called by the observer notifier
     293    // \brief Buildes the map.
     294    //
     295    // It buildes the map. It called by the observer notifier
    295296    // and it overrides the build() member function of the observer base.
    296297    virtual void build() {
    … …  
    306307    // \brief Clear the map.
    307308    //
    308     // It erase all items from the map. It is called by the observer notifier
     309    // It erase all items from the map. It called by the observer notifier
    309310    // and it overrides the clear() member function of the observer base.
    310311    virtual void clear() {

  • lemon/bits/base_extender.h

    r361 r314  
    3131//\ingroup digraphbits
    3232//\file
    33 //\brief Extenders for the graph types
     33//\brief Extenders for the digraph types
    3434namespace lemon {
    3535

  • lemon/bits/graph_extender.h

    r361 r314  
    3030//\ingroup graphbits
    3131//\file
    32 //\brief Extenders for the graph types
     32//\brief Extenders for the digraph types
    3333namespace lemon {
    3434
    3535  // \ingroup graphbits
    3636  //
    37   // \brief Extender for the digraph implementations
     37  // \brief Extender for the Digraphs
    3838  template <typename Base>
    3939  class DigraphExtender : public Base {

  • lemon/bits/traits.h

    r360 r314  
    219219
    220220  template <typename Graph, typename Enable = void>
    221   struct ArcNumTagIndicator {
    222     static const bool value = false;
    223   };
    224 
    225   template <typename Graph>
    226   struct ArcNumTagIndicator<
    227     Graph,
    228     typename enable_if<typename Graph::ArcNumTag, void>::type
    229   > {
    230     static const bool value = true;
    231   };
    232 
    233   template <typename Graph, typename Enable = void>
    234221  struct EdgeNumTagIndicator {
    235222    static const bool value = false;
    … …  
    245232
    246233  template <typename Graph, typename Enable = void>
    247   struct FindArcTagIndicator {
    248     static const bool value = false;
    249   };
    250 
    251   template <typename Graph>
    252   struct FindArcTagIndicator<
    253     Graph,
    254     typename enable_if<typename Graph::FindArcTag, void>::type
    255   > {
    256     static const bool value = true;
    257   };
    258 
    259   template <typename Graph, typename Enable = void>
    260234  struct FindEdgeTagIndicator {
    261235    static const bool value = false;

  • lemon/bits/vector_map.h

    r361 r314  
    3939  // \brief Graph map based on the std::vector storage.
    4040  //
    41   // The VectorMap template class is graph map structure that automatically
    42   // updates the map when a key is added to or erased from the graph.
    43   // This map type uses std::vector to store the values.
     41  // The VectorMap template class is graph map structure what
     42  // automatically updates the map when a key is added to or erased from
     43  // the map. This map type uses the std::vector to store the values.
    4444  //
    4545  // \tparam _Graph The graph this map is attached to.
    … …  
    170170    // \brief Adds a new key to the map.
    171171    //
    172     // It adds a new key to the map. It is called by the observer notifier
     172    // It adds a new key to the map. It called by the observer notifier
    173173    // and it overrides the add() member function of the observer base.
    174174    virtual void add(const Key& key) {
    … …  
    181181    // \brief Adds more new keys to the map.
    182182    //
    183     // It adds more new keys to the map. It is called by the observer notifier
     183    // It adds more new keys to the map. It called by the observer notifier
    184184    // and it overrides the add() member function of the observer base.
    185185    virtual void add(const std::vector<Key>& keys) {
    … …  
    196196    // \brief Erase a key from the map.
    197197    //
    198     // Erase a key from the map. It is called by the observer notifier
     198    // Erase a key from the map. It called by the observer notifier
    199199    // and it overrides the erase() member function of the observer base.
    200200    virtual void erase(const Key& key) {
    … …  
    204204    // \brief Erase more keys from the map.
    205205    //
    206     // It erases more keys from the map. It is called by the observer notifier
     206    // Erase more keys from the map. It called by the observer notifier
    207207    // and it overrides the erase() member function of the observer base.
    208208    virtual void erase(const std::vector<Key>& keys) {
    … …  
    212212    }
    213213
    214     // \brief Build the map.
    215     //
    216     // It builds the map. It is called by the observer notifier
     214    // \brief Buildes the map.
     215    //
     216    // It buildes the map. It called by the observer notifier
    217217    // and it overrides the build() member function of the observer base.
    218218    virtual void build() {
    … …  
    224224    // \brief Clear the map.
    225225    //
    226     // It erases all items from the map. It is called by the observer notifier
     226    // It erase all items from the map. It called by the observer notifier
    227227    // and it overrides the clear() member function of the observer base.
    228228    virtual void clear() {

  • lemon/list_graph.h

    r329 r313  
    841841
    842842    public:
    843       operator Edge() const {
    844         return id != -1 ? edgeFromId(id / 2) : INVALID;
     843      operator Edge() const { 
     844        return id != -1 ? edgeFromId(id / 2) : INVALID; 
    845845      }
    846846

  • lemon/random.h

    r340 r280  
    541541    /// @{
    542542
     543    ///\name Initialization
     544    ///
     545    /// @{
     546
    543547    /// \brief Default constructor
    544548    ///
    … …  
    705709    }
    706710
     711    /// @}
     712
     713    ///\name Uniform distributions
     714    ///
     715    /// @{
     716
    707717    /// \brief Returns a random real number from the range [0, 1)
    708718    ///
    … …  
    761771      return _random_bits::IntConversion<Number, Word>::convert(core);
    762772    }
     773
     774    /// @}
    763775
    764776    unsigned int uinteger() {
    … …  
    795807    ///\name Non-uniform distributions
    796808    ///
     809
    797810    ///@{
    798811
    799     /// \brief Returns a random bool with given probability of true result.
     812    /// \brief Returns a random bool
    800813    ///
    801814    /// It returns a random bool with given probability of true result.
    … …  
    804817    }
    805818
    806     /// Standard normal (Gauss) distribution
    807 
    808     /// Standard normal (Gauss) distribution.
     819    /// Standard Gauss distribution
     820
     821    /// Standard Gauss distribution.
    809822    /// \note The Cartesian form of the Box-Muller
    810823    /// transformation is used to generate a random normal distribution.
    … …  
    819832      return std::sqrt(-2*std::log(S)/S)*V1;
    820833    }
    821     /// Normal (Gauss) distribution with given mean and standard deviation
    822 
    823     /// Normal (Gauss) distribution with given mean and standard deviation.
     834    /// Gauss distribution with given mean and standard deviation
     835
     836    /// Gauss distribution with given mean and standard deviation.
    824837    /// \sa gauss()
    825838    double gauss(double mean,double std_dev)
    826839    {
    827840      return gauss()*std_dev+mean;
    828     }
    829 
    830     /// Lognormal distribution
    831 
    832     /// Lognormal distribution. The parameters are the mean and the standard
    833     /// deviation of <tt>exp(X)</tt>.
    834     ///
    835     double lognormal(double n_mean,double n_std_dev)
    836     {
    837       return std::exp(gauss(n_mean,n_std_dev));
    838     }
    839     /// Lognormal distribution
    840 
    841     /// Lognormal distribution. The parameter is an <tt>std::pair</tt> of
    842     /// the mean and the standard deviation of <tt>exp(X)</tt>.
    843     ///
    844     double lognormal(const std::pair<double,double> &params)
    845     {
    846       return std::exp(gauss(params.first,params.second));
    847     }
    848     /// Compute the lognormal parameters from mean and standard deviation
    849 
    850     /// This function computes the lognormal parameters from mean and
    851     /// standard deviation. The return value can direcly be passed to
    852     /// lognormal().
    853     std::pair<double,double> lognormalParamsFromMD(double mean,
    854                                                    double std_dev)
    855     {
    856       double fr=std_dev/mean;
    857       fr*=fr;
    858       double lg=std::log(1+fr);
    859       return std::pair<double,double>(std::log(mean)-lg/2.0,std::sqrt(lg));
    860     }
    861     /// Lognormal distribution with given mean and standard deviation
    862 
    863     /// Lognormal distribution with given mean and standard deviation.
    864     ///
    865     double lognormalMD(double mean,double std_dev)
    866     {
    867       return lognormal(lognormalParamsFromMD(mean,std_dev));
    868841    }
    869842
    … …  
    971944    ///\name Two dimensional distributions
    972945    ///
     946
    973947    ///@{
    974948
    … …  
    987961      return dim2::Point<double>(V1,V2);
    988962    }
    989     /// A kind of two dimensional normal (Gauss) distribution
     963    /// A kind of two dimensional Gauss distribution
    990964
    991965    /// This function provides a turning symmetric two-dimensional distribution.

  • lemon/smart_graph.h

    r371 r370  
    6868
    6969    typedef True NodeNumTag;
    70     typedef True ArcNumTag;
     70    typedef True EdgeNumTag;
    7171
    7272    int nodeNum() const { return nodes.size(); }
    … …  
    467467
    468468    public:
    469       operator Edge() const {
    470         return _id != -1 ? edgeFromId(_id / 2) : INVALID;
     469      operator Edge() const { 
     470        return _id != -1 ? edgeFromId(_id / 2) : INVALID; 
    471471      }
    472472
    … …  
    483483      : nodes(), arcs() {}
    484484
    485     typedef True NodeNumTag;
    486     typedef True EdgeNumTag;
    487     typedef True ArcNumTag;
    488 
    489     int nodeNum() const { return nodes.size(); }
    490     int edgeNum() const { return arcs.size() / 2; }
    491     int arcNum() const { return arcs.size(); }
    492485
    493486    int maxNodeId() const { return nodes.size()-1; }

  • scripts/unify-sources.sh

    r341 r208  
    44HGROOT=`hg root`
    55
    6 # file enumaration modes
    7 
    8 function all_files() {
    9     hg status -a -m -c |
    10     cut -d ' ' -f 2 | grep -E '(\.(cc|h|dox)$|Makefile\.am$)' |
    11     while read file; do echo $HGROOT/$file; done
    12 }
    13 
    14 function modified_files() {
    15     hg status -a -m |
    16     cut -d ' ' -f 2 | grep -E  '(\.(cc|h|dox)$|Makefile\.am$)' |
    17     while read file; do echo $HGROOT/$file; done
    18 }
    19 
    20 function changed_files() {
    21     {
    22         if [ -n "$HG_PARENT1" ]
    23         then
    24             hg status --rev $HG_PARENT1:$HG_NODE -a -m
    25         fi
    26         if [ -n "$HG_PARENT2" ]
    27         then
    28             hg status --rev $HG_PARENT2:$HG_NODE -a -m
    29         fi
    30     } | cut -d ' ' -f 2 | grep -E '(\.(cc|h|dox)$|Makefile\.am$)' |
    31     sort | uniq |
    32     while read file; do echo $HGROOT/$file; done
    33 }
    34 
    35 function given_files() {
    36     for file in $GIVEN_FILES
    37     do
    38         echo $file
    39     done
    40 }
    41 
    42 # actions
    43 
    44 function update_action() {
    45     if ! diff -q $1 $2 >/dev/null
    46     then
    47         echo -n " [$3 updated]"
    48         rm $2
    49         mv $1 $2
    50         CHANGED=YES
    51     fi
    52 }
    53 
    54 function update_warning() {
    55     echo -n " [$2 warning]"
    56     WARNED=YES
    57 }
    58 
    59 function update_init() {
    60     echo Update source files...
    61     TOTAL_FILES=0
    62     CHANGED_FILES=0
    63     WARNED_FILES=0
    64 }
    65 
    66 function update_done() {
    67     echo $CHANGED_FILES out of $TOTAL_FILES files has been changed.
    68     echo $WARNED_FILES out of $TOTAL_FILES files triggered warnings.
    69 }
    70 
    71 function update_begin() {
    72     ((TOTAL_FILES++))
    73     CHANGED=NO
    74     WARNED=NO
    75 }
    76 
    77 function update_end() {
    78     if [ $CHANGED == YES ]
    79     then
    80         ((++CHANGED_FILES))
    81     fi
    82     if [ $WARNED == YES ]
    83     then
    84         ((++WARNED_FILES))
    85     fi
    86 }
    87 
    88 function check_action() {
    89     if [ "$3" == 'tabs' ]
    90     then
    91         PATTERN=$(echo -e '\t')
    92     elif [ "$3" == 'trailing spaces' ]
    93     then
    94         PATTERN='\ +$'
    95     else
    96         PATTERN='*'
    97     fi
    98 
    99     if ! diff -q $1 $2 >/dev/null
    100     then
    101         if [ "$PATTERN" == '*' ]
    102         then
    103             diff $1 $2 | grep '^[0-9]' | sed "s|^\(.*\)c.*$|$2:\1: check failed: $3|g" |
    104               sed "s/:\([0-9]*\),\([0-9]*\):\(.*\)$/:\1:\3 (until line \2)/g"
    105         else
    106             grep -n -E "$PATTERN" $2 | sed "s|^\([0-9]*\):.*$|$2:\1: check failed: $3|g"
    107         fi
    108         FAILED=YES
    109     fi
    110 }
    111 
    112 function check_warning() {
    113     if [ "$2" == 'long lines' ]
    114     then
    115         grep -n -E '.{81,}' $1 | sed "s|^\([0-9]*\):.*$|$1:\1: warning: $2|g"
    116     else
    117         echo "$1: warning: $2"
    118     fi
    119     WARNED=YES
    120 }
    121 
    122 function check_init() {
    123     echo Check source files...
    124     FAILED_FILES=0
    125     WARNED_FILES=0
    126     TOTAL_FILES=0
    127 }
    128 
    129 function check_done() {
    130     echo $FAILED_FILES out of $TOTAL_FILES files has been failed.
    131     echo $WARNED_FILES out of $TOTAL_FILES files triggered warnings.
    132 
    133     if [ $FAILED_FILES -gt 0 ]
    134     then
    135         return 1
    136     elif [ $WARNED_FILES -gt 0 ]
    137     then
    138         if [ "$WARNING" == 'INTERACTIVE' ]
    139         then
    140             echo -n "Are the files with warnings acceptable? (yes/no) "
    141             while read answer
    142             do
    143                 if [ "$answer" == 'yes' ]
    144                 then
    145                     return 0
    146                 elif [ "$answer" == 'no' ]
    147                 then
    148                     return 1
    149                 fi
    150                 echo -n "Are the files with warnings acceptable? (yes/no) "
    151             done
    152         elif [ "$WARNING" == 'WERROR' ]
    153         then
    154             return 1
    155         fi
    156     fi
    157 }
    158 
    159 function check_begin() {
    160     ((TOTAL_FILES++))
    161     FAILED=NO
    162     WARNED=NO
    163 }
    164 
    165 function check_end() {
    166     if [ $FAILED == YES ]
    167     then
    168         ((++FAILED_FILES))
    169     fi
    170     if [ $WARNED == YES ]
    171     then
    172         ((++WARNED_FILES))
    173     fi
    174 }
    175 
    176 
    177 
    178 # checks
    179 
    180 function header_check() {
    181     if echo $1 | grep -q -E 'Makefile\.am$'
    182     then
    183         return
    184     fi
    185 
     6function update_header() {
    1867    TMP_FILE=`mktemp`
     8    FILE_NAME=$1
    1879
    18810    (echo "/* -*- mode: C++; indent-tabs-mode: nil; -*-
    … …  
    20426 */
    20527"
    206     awk 'BEGIN { pm=0; }
     28        awk 'BEGIN { pm=0; }
    20729     pm==3 { print }
    20830     /\/\* / && pm==0 { pm=1;}
    … …  
    21032     /\*\// && pm==1 { pm=2;}
    21133    ' $1
    212     ) >$TMP_FILE
     34        ) >$TMP_FILE
    21335
    214     "$ACTION"_action "$TMP_FILE" "$1" header
     36    HEADER_CH=`diff -q $TMP_FILE $FILE_NAME >/dev/null&&echo NO||echo YES`
     37
     38    rm $FILE_NAME
     39    mv $TMP_FILE $FILE_NAME
    21540}
    21641
    217 function tabs_check() {
    218     if echo $1 | grep -q -v -E 'Makefile\.am$'
    219     then
    220         OLD_PATTERN=$(echo -e '\t')
    221         NEW_PATTERN='        '
    222     else
    223         OLD_PATTERN='        '
    224         NEW_PATTERN=$(echo -e '\t')
    225     fi
     42function update_tabs() {
    22643    TMP_FILE=`mktemp`
    227     cat $1 | sed -e "s/$OLD_PATTERN/$NEW_PATTERN/g" >$TMP_FILE
     44    FILE_NAME=$1
    22845
    229     "$ACTION"_action "$TMP_FILE" "$1" 'tabs'
     46    cat $1 |
     47    sed -e 's/\t/        /g' >$TMP_FILE
     48
     49    TABS_CH=`diff -q $TMP_FILE $FILE_NAME >/dev/null&&echo NO||echo YES`
     50
     51    rm $FILE_NAME
     52    mv $TMP_FILE $FILE_NAME
    23053}
    23154
    232 function spaces_check() {
     55function remove_trailing_space() {
    23356    TMP_FILE=`mktemp`
    234     cat $1 | sed -e 's/ \+$//g' >$TMP_FILE
     57    FILE_NAME=$1
    23558
    236     "$ACTION"_action "$TMP_FILE" "$1" 'trailing spaces'
     59    cat $1 |
     60    sed -e 's/ \+$//g' >$TMP_FILE
     61
     62    SPACES_CH=`diff -q $TMP_FILE $FILE_NAME >/dev/null&&echo NO||echo YES`
     63
     64    rm $FILE_NAME
     65    mv $TMP_FILE $FILE_NAME
    23766}
    23867
    239 function long_lines_check() {
    240     if cat $1 | grep -q -E '.{81,}'
     68function long_line_test() {
     69    cat $1 |grep -q -E '.{81,}'
     70}
     71
     72function update_file() {
     73    echo -n '    update' $i ...
     74
     75    update_header $1
     76    update_tabs $1
     77    remove_trailing_space $1
     78
     79    CHANGED=NO;
     80    if [[ $HEADER_CH = YES ]];
    24181    then
    242         "$ACTION"_warning $1 'long lines'
     82        echo -n '  [header updated]'
     83        CHANGED=YES;
     84    fi
     85    if [[ $TABS_CH = YES ]];
     86    then
     87        echo -n ' [tabs removed]'
     88        CHANGED=YES;
     89    fi
     90    if [[ $SPACES_CH = YES ]];
     91    then
     92        echo -n ' [trailing spaces removed]'
     93        CHANGED=YES;
     94    fi
     95    if long_line_test $1 ;
     96    then
     97        echo -n ' [LONG LINES]'
     98        ((LONG_LINE_FILES++))
     99    fi
     100    echo
     101    if [[ $CHANGED = YES ]];
     102    then
     103        ((CHANGED_FILES++))
    243104    fi
    244105}
    245106
    246 # process the file
    247 
    248 function process_file() {
    249     if [ "$ACTION" == 'update' ]
    250     then
    251         echo -n "    $ACTION $1..."
    252     else
    253         echo "    $ACTION $1..."
    254     fi
    255 
    256     CHECKING="header tabs spaces long_lines"
    257 
    258     "$ACTION"_begin $1
    259     for check in $CHECKING
     107CHANGED_FILES=0
     108TOTAL_FILES=0
     109LONG_LINE_FILES=0
     110if [ $# == 0 ]; then
     111    echo Update all source files...
     112    for i in `hg manifest|grep -E  '\.(cc|h|dox)$'`
    260113    do
    261         "$check"_check $1
     114        update_file $HGROOT/$i
     115        ((TOTAL_FILES++))
    262116    done
    263     "$ACTION"_end $1
    264     if [ "$ACTION" == 'update' ]
    265     then
    266         echo
    267     fi
    268 }
    269 
    270 function process_all {
    271     "$ACTION"_init
    272     while read file
     117    echo '  done.'
     118else
     119    for i in $*
    273120    do
    274         process_file $file
    275     done < <($FILES)
    276     "$ACTION"_done
    277 }
    278 
    279 while [ $# -gt 0 ]
    280 do
    281    
    282     if [ "$1" == '--help' ] || [ "$1" == '-h' ]
    283     then
    284         echo -n \
    285 "Usage:
    286   $0 [OPTIONS] [files]
    287 Options:
    288   --dry-run|-n
    289      Check the files, but do not modify them.
    290   --interactive|-i
    291      If --dry-run is specified and the checker emits warnings,
    292      then the user is asked if the warnings should be considered
    293      errors.
    294   --werror|-w
    295      Make all warnings into errors.
    296   --all|-a
    297      Check all source files in the repository.
    298   --modified|-m
    299      Check only the modified (and new) source files. This option is
    300      useful to check the modification before making a commit.
    301   --changed|-c
    302      Check only the changed source files compared to the parent(s) of
    303      the current hg node.  This option is useful as hg hook script.
    304      To automatically check all your changes before making a commit,
    305      add the following section to the appropriate .hg/hgrc file.
    306 
    307        [hooks]
    308        pretxncommit.checksources = scripts/unify-sources.sh -c -n -i
    309 
    310   --help|-h
    311      Print this help message.
    312   files
    313      The files to check/unify. If no file names are given, the modified
    314      source files will be checked/unified (just like using the
    315      --modified|-m option).
    316 "
    317         exit 0
    318     elif [ "$1" == '--dry-run' ] || [ "$1" == '-n' ]
    319     then
    320         [ -n "$ACTION" ] && echo "Conflicting action options" >&2 && exit 1
    321         ACTION=check
    322     elif [ "$1" == "--all" ] || [ "$1" == '-a' ]
    323     then
    324         [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1
    325         FILES=all_files
    326     elif [ "$1" == "--changed" ] || [ "$1" == '-c' ]
    327     then
    328         [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1
    329         FILES=changed_files
    330     elif [ "$1" == "--modified" ] || [ "$1" == '-m' ]
    331     then
    332         [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1
    333         FILES=modified_files
    334     elif [ "$1" == "--interactive" ] || [ "$1" == "-i" ]
    335     then
    336         [ -n "$WARNING" ] && echo "Conflicting warning options" >&2 && exit 1
    337         WARNING='INTERACTIVE'
    338     elif [ "$1" == "--werror" ] || [ "$1" == "-w" ]
    339     then
    340         [ -n "$WARNING" ] && echo "Conflicting warning options" >&2 && exit 1
    341         WARNING='WERROR'
    342     elif [ $(echo x$1 | cut -c 2) == '-' ]
    343     then
    344         echo "Invalid option $1" >&2 && exit 1
    345     else
    346         [ -n "$FILES" ] && echo "Invalid option $1" >&2 && exit 1
    347         GIVEN_FILES=$@
    348         FILES=given_files
    349         break
    350     fi
    351    
    352     shift
    353 done
    354 
    355 if [ -z $FILES ]
    356 then
    357     FILES=modified_files
     121        update_file $i
     122        ((TOTAL_FILES++))
     123    done
    358124fi
    359 
    360 if [ -z $ACTION ]
    361 then
    362     ACTION=update
     125echo $CHANGED_FILES out of $TOTAL_FILES files has been changed.
     126if [[ $LONG_LINE_FILES -gt 1 ]]; then
     127    echo
     128    echo WARNING: $LONG_LINE_FILES files contains long lines!   
     129    echo
     130elif [[ $LONG_LINE_FILES -gt 0 ]]; then
     131    echo
     132    echo WARNING: a file contains long lines!
     133    echo
    363134fi
    364 
    365 process_all

  • test/CMakeLists.txt

    r327 r225  
    1717  kruskal_test
    1818  maps_test
    19   max_matching_test
    2019  random_test
    2120  path_test

  • test/Makefile.am

    r345 r228  
    11EXTRA_DIST += \
    2         test/CMakeLists.txt \
    3         test/min_cost_flow_test.lgf
     2        test/CMakeLists.txt
    43
    54noinst_HEADERS += \
    … …  
    2120        test/kruskal_test \
    2221        test/maps_test \
    23         test/max_matching_test \
    2422        test/random_test \
    2523        test/path_test \
    26         test/suurballe_test \
    2724        test/test_tools_fail \
    2825        test/test_tools_pass \
    … …  
    4643test_kruskal_test_SOURCES = test/kruskal_test.cc
    4744test_maps_test_SOURCES = test/maps_test.cc
    48 test_max_matching_test_SOURCES = test/max_matching_test.cc
    4945test_path_test_SOURCES = test/path_test.cc
    50 test_suurballe_test_SOURCES = test/suurballe_test.cc
    5146test_random_test_SOURCES = test/random_test.cc
    5247test_test_tools_fail_SOURCES = test/test_tools_fail.cc

  • test/digraph_test.cc

    r365 r228  
    2020#include <lemon/list_graph.h>
    2121#include <lemon/smart_graph.h>
    22 #include <lemon/full_graph.h>
     22//#include <lemon/full_graph.h>
     23//#include <lemon/hypercube_graph.h>
    2324
    2425#include "test_tools.h"
    … …  
    7980}
    8081
    81 void checkFullDigraph(int num) {
    82   typedef FullDigraph Digraph;
    83   DIGRAPH_TYPEDEFS(Digraph);
    84   Digraph G(num);
    85 
    86   checkGraphNodeList(G, num);
    87   checkGraphArcList(G, num * num);
    88 
    89   for (NodeIt n(G); n != INVALID; ++n) {
    90     checkGraphOutArcList(G, n, num);
    91     checkGraphInArcList(G, n, num);
    92   }
    93 
    94   checkGraphConArcList(G, num * num);
    95 
    96   checkNodeIds(G);
    97   checkArcIds(G);
    98   checkGraphNodeMap(G);
    99   checkGraphArcMap(G);
    100 
    101   for (int i = 0; i < G.nodeNum(); ++i) {
    102     check(G.index(G(i)) == i, "Wrong index");
    103   }
    104 
    105   for (NodeIt s(G); s != INVALID; ++s) {
    106     for (NodeIt t(G); t != INVALID; ++t) {
    107       Arc a = G.arc(s, t);
    108       check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
    109     }
    110   }
    111 
    112 }
    11382
    11483void checkConcepts() {
    … …  
    141110    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
    142111  }
    143   { // Checking FullDigraph
    144     checkConcept<Digraph, FullDigraph>();
    145   }
     112//  { // Checking FullDigraph
     113//    checkConcept<Digraph, FullDigraph>();
     114//  }
     115//  { // Checking HyperCubeDigraph
     116//    checkConcept<Digraph, HyperCubeDigraph>();
     117//  }
    146118}
    147119
    … …  
    205177    checkDigraphValidity<SmartDigraph>();
    206178  }
    207   { // Checking FullDigraph
    208     checkFullDigraph(8);
    209   }
    210179}
    211180

  • test/graph_test.cc

    r365 r228  
    2020#include <lemon/list_graph.h>
    2121#include <lemon/smart_graph.h>
    22 #include <lemon/full_graph.h>
    23 #include <lemon/grid_graph.h>
    24 #include <lemon/hypercube_graph.h>
     22// #include <lemon/full_graph.h>
     23// #include <lemon/grid_graph.h>
    2524
    2625#include "test_tools.h"
    … …  
    9796}
    9897
    99 void checkFullGraph(int num) {
    100   typedef FullGraph Graph;
    101   GRAPH_TYPEDEFS(Graph);
    102 
    103   Graph G(num);
    104   checkGraphNodeList(G, num);
    105   checkGraphEdgeList(G, num * (num - 1) / 2);
    106 
    107   for (NodeIt n(G); n != INVALID; ++n) {
    108     checkGraphOutArcList(G, n, num - 1);
    109     checkGraphInArcList(G, n, num - 1);
    110     checkGraphIncEdgeList(G, n, num - 1);
    111   }
    112 
    113   checkGraphConArcList(G, num * (num - 1));
    114   checkGraphConEdgeList(G, num * (num - 1) / 2);
    115 
    116   checkArcDirections(G);
    117 
    118   checkNodeIds(G);
    119   checkArcIds(G);
    120   checkEdgeIds(G);
    121   checkGraphNodeMap(G);
    122   checkGraphArcMap(G);
    123   checkGraphEdgeMap(G);
    124 
    125 
    126   for (int i = 0; i < G.nodeNum(); ++i) {
    127     check(G.index(G(i)) == i, "Wrong index");
    128   }
    129 
    130   for (NodeIt u(G); u != INVALID; ++u) {
    131     for (NodeIt v(G); v != INVALID; ++v) {
    132       Edge e = G.edge(u, v);
    133       Arc a = G.arc(u, v);
    134       if (u == v) {
    135         check(e == INVALID, "Wrong edge lookup");
    136         check(a == INVALID, "Wrong arc lookup");
    137       } else {
    138         check((G.u(e) == u && G.v(e) == v) ||
    139               (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");
    140         check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");
    141       }
    142     }
    143   }
    144 }
    145 
    14698void checkConcepts() {
    14799  { // Checking graph components
    … …  
    173125    checkConcept<ClearableGraphComponent<>, SmartGraph>();
    174126  }
    175   { // Checking FullGraph
    176     checkConcept<Graph, FullGraph>();
    177   }
    178   { // Checking GridGraph
    179     checkConcept<Graph, GridGraph>();
    180   }
    181   { // Checking HypercubeGraph
    182     checkConcept<Graph, HypercubeGraph>();
    183   }
     127//  { // Checking FullGraph
     128//    checkConcept<Graph, FullGraph>();
     129//    checkGraphIterators<FullGraph>();
     130//  }
     131//  { // Checking GridGraph
     132//    checkConcept<Graph, GridGraph>();
     133//    checkGraphIterators<GridGraph>();
     134//  }
    184135}
    185136
    … …  
    238189}
    239190
    240 void checkGridGraph(int width, int height) {
    241   typedef GridGraph Graph;
    242   GRAPH_TYPEDEFS(Graph);
    243   Graph G(width, height);
    244 
    245   check(G.width() == width, "Wrong column number");
    246   check(G.height() == height, "Wrong row number");
    247 
    248   for (int i = 0; i < width; ++i) {
    249     for (int j = 0; j < height; ++j) {
    250       check(G.col(G(i, j)) == i, "Wrong column");
    251       check(G.row(G(i, j)) == j, "Wrong row");
    252       check(G.pos(G(i, j)).x == i, "Wrong column");
    253       check(G.pos(G(i, j)).y == j, "Wrong row");
    254     }
    255   }
    256 
    257   for (int j = 0; j < height; ++j) {
    258     for (int i = 0; i < width - 1; ++i) {
    259       check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");
    260       check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");
    261     }
    262     check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
    263   }
    264 
    265   for (int j = 0; j < height; ++j) {
    266     for (int i = 1; i < width; ++i) {
    267       check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");
    268       check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");
    269     }
    270     check(G.left(G(0, j)) == INVALID, "Wrong left");
    271   }
    272 
    273   for (int i = 0; i < width; ++i) {
    274     for (int j = 0; j < height - 1; ++j) {
    275       check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");
    276       check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");
    277     }
    278     check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
    279   }
    280 
    281   for (int i = 0; i < width; ++i) {
    282     for (int j = 1; j < height; ++j) {
    283       check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");
    284       check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");
    285     }
    286     check(G.down(G(i, 0)) == INVALID, "Wrong down");
    287   }
    288 
    289   checkGraphNodeList(G, width * height);
    290   checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
    291   checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
    292 
    293   for (NodeIt n(G); n != INVALID; ++n) {
    294     int nb = 4;
    295     if (G.col(n) == 0) --nb;
    296     if (G.col(n) == width - 1) --nb;
    297     if (G.row(n) == 0) --nb;
    298     if (G.row(n) == height - 1) --nb;
    299 
    300     checkGraphOutArcList(G, n, nb);
    301     checkGraphInArcList(G, n, nb);
    302     checkGraphIncEdgeList(G, n, nb);
    303   }
    304 
    305   checkArcDirections(G);
    306 
    307   checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
    308   checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
    309 
    310   checkNodeIds(G);
    311   checkArcIds(G);
    312   checkEdgeIds(G);
    313   checkGraphNodeMap(G);
    314   checkGraphArcMap(G);
    315   checkGraphEdgeMap(G);
    316 
    317 }
    318 
    319 void checkHypercubeGraph(int dim) {
    320   GRAPH_TYPEDEFS(HypercubeGraph);
    321 
    322   HypercubeGraph G(dim);
    323   checkGraphNodeList(G, 1 << dim);
    324   checkGraphEdgeList(G, dim * (1 << dim-1));
    325   checkGraphArcList(G, dim * (1 << dim));
    326 
    327   Node n = G.nodeFromId(dim);
    328 
    329   for (NodeIt n(G); n != INVALID; ++n) {
    330     checkGraphIncEdgeList(G, n, dim);
    331     for (IncEdgeIt e(G, n); e != INVALID; ++e) {
    332       check( (G.u(e) == n &&
    333               G.id(G.v(e)) == G.id(n) ^ (1 << G.dimension(e))) ||
    334              (G.v(e) == n &&
    335               G.id(G.u(e)) == G.id(n) ^ (1 << G.dimension(e))),
    336              "Wrong edge or wrong dimension");
    337     }
    338 
    339     checkGraphOutArcList(G, n, dim);
    340     for (OutArcIt a(G, n); a != INVALID; ++a) {
    341       check(G.source(a) == n &&
    342             G.id(G.target(a)) == G.id(n) ^ (1 << G.dimension(a)),
    343             "Wrong arc or wrong dimension");
    344     }
    345 
    346     checkGraphInArcList(G, n, dim);
    347     for (InArcIt a(G, n); a != INVALID; ++a) {
    348       check(G.target(a) == n &&
    349             G.id(G.source(a)) == G.id(n) ^ (1 << G.dimension(a)),
    350             "Wrong arc or wrong dimension");
    351     }
    352   }
    353 
    354   checkGraphConArcList(G, (1 << dim) * dim);
    355   checkGraphConEdgeList(G, dim * (1 << dim-1));
    356 
    357   checkArcDirections(G);
    358 
    359   checkNodeIds(G);
    360   checkArcIds(G);
    361   checkEdgeIds(G);
    362   checkGraphNodeMap(G);
    363   checkGraphArcMap(G);
    364   checkGraphEdgeMap(G);
    365 }
     191// void checkGridGraph(const GridGraph& g, int w, int h) {
     192//   check(g.width() == w, "Wrong width");
     193//   check(g.height() == h, "Wrong height");
     194
     195//   for (int i = 0; i < w; ++i) {
     196//     for (int j = 0; j < h; ++j) {
     197//       check(g.col(g(i, j)) == i, "Wrong col");
     198//       check(g.row(g(i, j)) == j, "Wrong row");
     199//     }
     200//   }
     201
     202//   for (int i = 0; i < w; ++i) {
     203//     for (int j = 0; j < h - 1; ++j) {
     204//       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
     205//       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
     206//     }
     207//     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
     208//   }
     209
     210//   for (int i = 0; i < w; ++i) {
     211//     for (int j = 1; j < h; ++j) {
     212//       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
     213//       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
     214//     }
     215//     check(g.up(g(i, 0)) == INVALID, "Wrong up");
     216//   }
     217
     218//   for (int j = 0; j < h; ++j) {
     219//     for (int i = 0; i < w - 1; ++i) {
     220//       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
     221//       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");
     222//     }
     223//     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");
     224//   }
     225
     226//   for (int j = 0; j < h; ++j) {
     227//     for (int i = 1; i < w; ++i) {
     228//       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
     229//       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
     230//     }
     231//     check(g.left(g(0, j)) == INVALID, "Wrong left");
     232//   }
     233// }
    366234
    367235void checkGraphs() {
    … …  
    374242    checkGraphValidity<SmartGraph>();
    375243  }
    376   { // Checking FullGraph
    377     checkFullGraph(7);
    378     checkFullGraph(8);
    379   }
    380   { // Checking GridGraph
    381     checkGridGraph(5, 8);
    382     checkGridGraph(8, 5);
    383     checkGridGraph(5, 5);
    384     checkGridGraph(0, 0);
    385     checkGridGraph(1, 1);
    386   }
    387   { // Checking HypercubeGraph
    388     checkHypercubeGraph(1);
    389     checkHypercubeGraph(2);
    390     checkHypercubeGraph(3);
    391     checkHypercubeGraph(4);
    392   }
     244//   { // Checking FullGraph
     245//     FullGraph g(5);
     246//     checkGraphNodeList(g, 5);
     247//     checkGraphEdgeList(g, 10);
     248//   }
     249//   { // Checking GridGraph
     250//     GridGraph g(5, 6);
     251//     checkGraphNodeList(g, 30);
     252//     checkGraphEdgeList(g, 49);
     253//     checkGridGraph(g, 5, 6);
     254//   }
    393255}
    394256

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

    r366 r310  
    44
    55if [ $# -eq 0 -o x$1 = "x-h" -o x$1 = "x-help" -o x$1 = "x--help" ]; then
    6     echo "Usage:"
    7     echo "  $0 source-file(s)"
    8     exit
     6        echo "Usage:"
     7        echo "  $0 source-file"
     8        exit
    99fi
    1010
    11 for i in $@
    12 do
    13     echo Update $i...
    14     TMP=`mktemp`
    15     sed -e "s/\<undirected graph\>/_gr_aph_label_/g"\
    16         -e "s/\<undirected graphs\>/_gr_aph_label_s/g"\
    17         -e "s/\<undirected edge\>/_ed_ge_label_/g"\
    18         -e "s/\<undirected edges\>/_ed_ge_label_s/g"\
    19         -e "s/\<directed graph\>/_digr_aph_label_/g"\
    20         -e "s/\<directed graphs\>/_digr_aph_label_s/g"\
    21         -e "s/\<directed edge\>/_ar_c_label_/g"\
    22         -e "s/\<directed edges\>/_ar_c_label_s/g"\
    23         -e "s/UGraph/_Gr_aph_label_/g"\
    24         -e "s/u[Gg]raph/_gr_aph_label_/g"\
    25         -e "s/\<Graph\>/_Digr_aph_label_/g"\
    26         -e "s/\<graph\>/_digr_aph_label_/g"\
    27         -e "s/\<Graphs\>/_Digr_aph_label_s/g"\
    28         -e "s/\<graphs\>/_digr_aph_label_s/g"\
    29         -e "s/_Graph/__Gr_aph_label_/g"\
    30         -e "s/\([Gg]\)raph\([a-z_]\)/_\1r_aph_label_\2/g"\
    31         -e "s/\([a-z_]\)graph/\1_gr_aph_label_/g"\
    32         -e "s/Graph/_Digr_aph_label_/g"\
    33         -e "s/graph/_digr_aph_label_/g"\
    34         -e "s/UEdge/_Ed_ge_label_/g"\
    35         -e "s/u[Ee]dge/_ed_ge_label_/g"\
    36         -e "s/IncEdgeIt/_In_cEd_geIt_label_/g"\
    37         -e "s/\<Edge\>/_Ar_c_label_/g"\
    38         -e "s/\<edge\>/_ar_c_label_/g"\
    39         -e "s/\<Edges\>/_Ar_c_label_s/g"\
    40         -e "s/\<edges\>/_ar_c_label_s/g"\
    41         -e "s/_Edge/__Ed_ge_label_/g"\
    42         -e "s/Edge\([a-z_]\)/_Ed_ge_label_\1/g"\
    43         -e "s/edge\([a-z_]\)/_ed_ge_label_\1/g"\
    44         -e "s/\([a-z_]\)edge/\1_ed_ge_label_/g"\
    45         -e "s/Edge/_Ar_c_label_/g"\
    46         -e "s/edge/_ar_c_label_/g"\
    47         -e "s/A[Nn]ode/_Re_d_label_/g"\
    48         -e "s/B[Nn]ode/_Blu_e_label_/g"\
    49         -e "s/A-[Nn]ode/_Re_d_label_/g"\
    50         -e "s/B-[Nn]ode/_Blu_e_label_/g"\
    51         -e "s/a[Nn]ode/_re_d_label_/g"\
    52         -e "s/b[Nn]ode/_blu_e_label_/g"\
    53         -e "s/\<UGRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__GR_APH_TY_PEDE_FS_label_\1/g"\
    54         -e "s/\<GRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__DIGR_APH_TY_PEDE_FS_label_\1/g"\
    55         -e "s/\<UGRAPH_TYPEDEFS\>/_GR_APH_TY_PEDE_FS_label_/g"\
    56         -e "s/\<GRAPH_TYPEDEFS\>/_DIGR_APH_TY_PEDE_FS_label_/g"\
    57         -e "s/_Digr_aph_label_/Digraph/g"\
    58         -e "s/_digr_aph_label_/digraph/g"\
    59         -e "s/_Gr_aph_label_/Graph/g"\
    60         -e "s/_gr_aph_label_/graph/g"\
    61         -e "s/_Ar_c_label_/Arc/g"\
    62         -e "s/_ar_c_label_/arc/g"\
    63         -e "s/_Ed_ge_label_/Edge/g"\
    64         -e "s/_ed_ge_label_/edge/g"\
    65         -e "s/_In_cEd_geIt_label_/IncEdgeIt/g"\
    66         -e "s/_Re_d_label_/Red/g"\
    67         -e "s/_Blu_e_label_/Blue/g"\
    68         -e "s/_re_d_label_/red/g"\
    69         -e "s/_blu_e_label_/blue/g"\
    70         -e "s/_GR_APH_TY_PEDE_FS_label_/GRAPH_TYPEDEFS/g"\
    71         -e "s/_DIGR_APH_TY_PEDE_FS_label_/DIGRAPH_TYPEDEFS/g"\
    72         -e "s/DigraphToEps/GraphToEps/g"\
    73         -e "s/digraphToEps/graphToEps/g"\
    74         -e "s/\<DefPredMap\>/SetPredMap/g"\
    75         -e "s/\<DefDistMap\>/SetDistMap/g"\
    76         -e "s/\<DefReachedMap\>/SetReachedMap/g"\
    77         -e "s/\<DefProcessedMap\>/SetProcessedMap/g"\
    78         -e "s/\<DefHeap\>/SetHeap/g"\
    79         -e "s/\<DefStandardHeap\>/SetStandradHeap/g"\
    80         -e "s/\<DefOperationTraits\>/SetOperationTraits/g"\
    81         -e "s/\<DefProcessedMapToBeDefaultMap\>/SetStandardProcessedMap/g"\
    82         -e "s/\<copyGraph\>/graphCopy/g"\
    83         -e "s/\<copyDigraph\>/digraphCopy/g"\
    84         -e "s/\<HyperCubeDigraph\>/HypercubeGraph/g"\
    85         -e "s/\<IntegerMap\>/RangeMap/g"\
    86         -e "s/\<integerMap\>/rangeMap/g"\
    87         -e "s/\<\([sS]\)tdMap\>/\1parseMap/g"\
    88         -e "s/\<\([Ff]\)unctorMap\>/\1unctorToMap/g"\
    89         -e "s/\<\([Mm]\)apFunctor\>/\1apToFunctor/g"\
    90         -e "s/\<\([Ff]\)orkWriteMap\>/\1orkMap/g"\
    91         -e "s/\<StoreBoolMap\>/LoggerBoolMap/g"\
    92         -e "s/\<storeBoolMap\>/loggerBoolMap/g"\
    93         -e "s/\<BoundingBox\>/Box/g"\
    94         -e "s/\<readNauty\>/readNautyGraph/g"\
    95     <$i > $TMP
    96     mv $TMP $i
    97 done
     11TMP=`mktemp`
     12
     13sed     -e "s/undirected graph/_gr_aph_label_/g"\
     14        -e "s/undirected edge/_ed_ge_label_/g"\
     15        -e "s/graph_/_gr_aph_label__/g"\
     16        -e "s/_graph/__gr_aph_label_/g"\
     17        -e "s/UGraph/_Gr_aph_label_/g"\
     18        -e "s/uGraph/_gr_aph_label_/g"\
     19        -e "s/ugraph/_gr_aph_label_/g"\
     20        -e "s/Graph/_Digr_aph_label_/g"\
     21        -e "s/graph/_digr_aph_label_/g"\
     22        -e "s/UEdge/_Ed_ge_label_/g"\
     23        -e "s/uEdge/_ed_ge_label_/g"\
     24        -e "s/uedge/_ed_ge_label_/g"\
     25        -e "s/IncEdgeIt/_In_cEd_geIt_label_/g"\
     26        -e "s/Edge/_Ar_c_label_/g"\
     27        -e "s/edge/_ar_c_label_/g"\
     28        -e "s/ANode/_Re_d_label_/g"\
     29        -e "s/BNode/_Blu_e_label_/g"\
     30        -e "s/A-Node/_Re_d_label_/g"\
     31        -e "s/B-Node/_Blu_e_label_/g"\
     32        -e "s/anode/_re_d_label_/g"\
     33        -e "s/bnode/_blu_e_label_/g"\
     34        -e "s/aNode/_re_d_label_/g"\
     35        -e "s/bNode/_blu_e_label_/g"\
     36        -e "s/_Digr_aph_label_/Digraph/g"\
     37        -e "s/_digr_aph_label_/digraph/g"\
     38        -e "s/_Gr_aph_label_/Graph/g"\
     39        -e "s/_gr_aph_label_/graph/g"\
     40        -e "s/_Ar_c_label_/Arc/g"\
     41        -e "s/_ar_c_label_/arc/g"\
     42        -e "s/_Ed_ge_label_/Edge/g"\
     43        -e "s/_ed_ge_label_/edge/g"\
     44        -e "s/_In_cEd_geIt_label_/IncEdgeIt/g"\
     45        -e "s/_Re_d_label_/Red/g"\
     46        -e "s/_Blu_e_label_/Blue/g"\
     47        -e "s/_re_d_label_/red/g"\
     48        -e "s/_blu_e_label_/blue/g"\
     49        -e "s/\(\W\)DefPredMap\(\W\)/\1SetPredMap\2/g"\
     50        -e "s/\(\W\)DefPredMap$/\1SetPredMap/g"\
     51        -e "s/^DefPredMap\(\W\)/SetPredMap\1/g"\
     52        -e "s/^DefPredMap$/SetPredMap/g"\
     53        -e "s/\(\W\)DefDistMap\(\W\)/\1SetDistMap\2/g"\
     54        -e "s/\(\W\)DefDistMap$/\1SetDistMap/g"\
     55        -e "s/^DefDistMap\(\W\)/SetDistMap\1/g"\
     56        -e "s/^DefDistMap$/SetDistMap/g"\
     57        -e "s/\(\W\)DefReachedMap\(\W\)/\1SetReachedMap\2/g"\
     58        -e "s/\(\W\)DefReachedMap$/\1SetReachedMap/g"\
     59        -e "s/^DefReachedMap\(\W\)/SetReachedMap\1/g"\
     60        -e "s/^DefReachedMap$/SetReachedMap/g"\
     61        -e "s/\(\W\)DefProcessedMap\(\W\)/\1SetProcessedMap\2/g"\
     62        -e "s/\(\W\)DefProcessedMap$/\1SetProcessedMap/g"\
     63        -e "s/^DefProcessedMap\(\W\)/SetProcessedMap\1/g"\
     64        -e "s/^DefProcessedMap$/SetProcessedMap/g"\
     65        -e "s/\(\W\)DefHeap\(\W\)/\1SetHeap\2/g"\
     66        -e "s/\(\W\)DefHeap$/\1SetHeap/g"\
     67        -e "s/^DefHeap\(\W\)/SetHeap\1/g"\
     68        -e "s/^DefHeap$/SetHeap/g"\
     69        -e "s/\(\W\)DefStandardHeap\(\W\)/\1SetStandradHeap\2/g"\
     70        -e "s/\(\W\)DefStandardHeap$/\1SetStandradHeap/g"\
     71        -e "s/^DefStandardHeap\(\W\)/SetStandradHeap\1/g"\
     72        -e "s/^DefStandardHeap$/SetStandradHeap/g"\
     73        -e "s/\(\W\)DefOperationTraits\(\W\)/\1SetOperationTraits\2/g"\
     74        -e "s/\(\W\)DefOperationTraits$/\1SetOperationTraits/g"\
     75        -e "s/^DefOperationTraits\(\W\)/SetOperationTraits\1/g"\
     76        -e "s/^DefOperationTraits$/SetOperationTraits/g"\
     77        -e "s/\(\W\)DefProcessedMapToBeDefaultMap\(\W\)/\1SetStandardProcessedMap\2/g"\
     78        -e "s/\(\W\)DefProcessedMapToBeDefaultMap$/\1SetStandardProcessedMap/g"\
     79        -e "s/^DefProcessedMapToBeDefaultMap\(\W\)/SetStandardProcessedMap\1/g"\
     80        -e "s/^DefProcessedMapToBeDefaultMap$/SetStandardProcessedMap/g"\
     81        -e "s/\(\W\)IntegerMap\(\W\)/\1RangeMap\2/g"\
     82        -e "s/\(\W\)IntegerMap$/\1RangeMap/g"\
     83        -e "s/^IntegerMap\(\W\)/RangeMap\1/g"\
     84        -e "s/^IntegerMap$/RangeMap/g"\
     85        -e "s/\(\W\)integerMap\(\W\)/\1rangeMap\2/g"\
     86        -e "s/\(\W\)integerMap$/\1rangeMap/g"\
     87        -e "s/^integerMap\(\W\)/rangeMap\1/g"\
     88        -e "s/^integerMap$/rangeMap/g"\
     89        -e "s/\(\W\)copyGraph\(\W\)/\1graphCopy\2/g"\
     90        -e "s/\(\W\)copyGraph$/\1graphCopy/g"\
     91        -e "s/^copyGraph\(\W\)/graphCopy\1/g"\
     92        -e "s/^copyGraph$/graphCopy/g"\
     93        -e "s/\(\W\)copyDigraph\(\W\)/\1digraphCopy\2/g"\
     94        -e "s/\(\W\)copyDigraph$/\1digraphCopy/g"\
     95        -e "s/^copyDigraph\(\W\)/digraphCopy\1/g"\
     96        -e "s/^copyDigraph$/digraphCopy/g"\
     97        -e "s/\(\W\)\([sS]\)tdMap\(\W\)/\1\2parseMap\3/g"\
     98        -e "s/\(\W\)\([sS]\)tdMap$/\1\2parseMap/g"\
     99        -e "s/^\([sS]\)tdMap\(\W\)/\1parseMap\2/g"\
     100        -e "s/^\([sS]\)tdMap$/\1parseMap/g"\
     101        -e "s/\(\W\)\([Ff]\)unctorMap\(\W\)/\1\2unctorToMap\3/g"\
     102        -e "s/\(\W\)\([Ff]\)unctorMap$/\1\2unctorToMap/g"\
     103        -e "s/^\([Ff]\)unctorMap\(\W\)/\1unctorToMap\2/g"\
     104        -e "s/^\([Ff]\)unctorMap$/\1unctorToMap/g"\
     105        -e "s/\(\W\)\([Mm]\)apFunctor\(\W\)/\1\2apToFunctor\3/g"\
     106        -e "s/\(\W\)\([Mm]\)apFunctor$/\1\2apToFunctor/g"\
     107        -e "s/^\([Mm]\)apFunctor\(\W\)/\1apToFunctor\2/g"\
     108        -e "s/^\([Mm]\)apFunctor$/\1apToFunctor/g"\
     109        -e "s/\(\W\)\([Ff]\)orkWriteMap\(\W\)/\1\2orkMap\3/g"\
     110        -e "s/\(\W\)\([Ff]\)orkWriteMap$/\1\2orkMap/g"\
     111        -e "s/^\([Ff]\)orkWriteMap\(\W\)/\1orkMap\2/g"\
     112        -e "s/^\([Ff]\)orkWriteMap$/\1orkMap/g"\
     113        -e "s/\(\W\)StoreBoolMap\(\W\)/\1LoggerBoolMap\2/g"\
     114        -e "s/\(\W\)StoreBoolMap$/\1LoggerBoolMap/g"\
     115        -e "s/^StoreBoolMap\(\W\)/LoggerBoolMap\1/g"\
     116        -e "s/^StoreBoolMap$/LoggerBoolMap/g"\
     117        -e "s/\(\W\)storeBoolMap\(\W\)/\1loggerBoolMap\2/g"\
     118        -e "s/\(\W\)storeBoolMap$/\1loggerBoolMap/g"\
     119        -e "s/^storeBoolMap\(\W\)/loggerBoolMap\1/g"\
     120        -e "s/^storeBoolMap$/loggerBoolMap/g"\
     121        -e "s/\(\W\)BoundingBox\(\W\)/\1Box\2/g"\
     122        -e "s/\(\W\)BoundingBox$/\1Box/g"\
     123        -e "s/^BoundingBox\(\W\)/Box\1/g"\
     124        -e "s/^BoundingBox$/Box/g"\
     125<$1 > $TMP
     126
     127mv $TMP $1
Note: See TracChangeset for help on using the changeset viewer.