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 / [398:532f34ea9cf3:397:62f9787c516c] in lemon-1.2


Ignore:
Files:
16 deleted
28 edited

Legend:

Unmodified
Added
Removed

  • .hgignore

    r385 r298  
    3737^objs.*/.*
    3838^test/[a-z_]*$
    39 ^tools/[a-z-_]*$
    4039^demo/.*_demo$
    4140^build/.*

  • 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

    r388 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 dimacs_group DIMACS format
    486 @ingroup io_group
    487 \brief Read and write files in DIMACS format
    488 
    489 Tools to read a digraph from or write it to a file in DIMACS format data.
    490 */
    491 
    492 /**
    493 @defgroup nauty_group NAUTY Format
    494 @ingroup io_group
    495 \brief Read \e Nauty format
    496 
    497 Tool to read graphs from \e Nauty format data.
    498482*/
    499483

  • 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

    r395 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
    … …  
    2828        lemon/dijkstra.h \
    2929        lemon/dim2.h \
    30         lemon/dimacs.h \
    31         lemon/elevator.h \
    3230        lemon/error.h \
    33         lemon/full_graph.h \
    3431        lemon/graph_to_eps.h \
    35         lemon/grid_graph.h \
    36         lemon/hypercube_graph.h \
    3732        lemon/kruskal.h \
    3833        lemon/lgf_reader.h \
    … …  
    4136        lemon/maps.h \
    4237        lemon/math.h \
    43         lemon/max_matching.h \
    44         lemon/nauty_reader.h \
    4538        lemon/path.h \
    46         lemon/preflow.h \
    4739        lemon/random.h \
    4840        lemon/smart_graph.h \
    49         lemon/suurballe.h \
    5041        lemon/time_measure.h \
    5142        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

    r378 r377  
    541541    /// @{
    542542
     543    ///\name Initialization
     544    ///
     545    /// @{
     546
    543547    /// \brief Default constructor
    544548    ///
    … …  
    689693    }
    690694
     695    /// @}
     696
     697    ///\name Uniform distributions
     698    ///
     699    /// @{
     700
    691701    /// \brief Returns a random real number from the range [0, 1)
    692702    ///
    … …  
    743753      return _random_bits::IntConversion<Number, Word>::convert(core);
    744754    }
     755
     756    /// @}
    745757
    746758    unsigned int uinteger() {
    … …  
    777789    ///\name Non-uniform distributions
    778790    ///
     791
    779792    ///@{
    780793
    781     /// \brief Returns a random bool with given probability of true result.
     794    /// \brief Returns a random bool
    782795    ///
    783796    /// It returns a random bool with given probability of true result.
    … …  
    786799    }
    787800
    788     /// Standard normal (Gauss) distribution
    789 
    790     /// Standard normal (Gauss) distribution.
     801    /// Standard Gauss distribution
     802
     803    /// Standard Gauss distribution.
    791804    /// \note The Cartesian form of the Box-Muller
    792805    /// transformation is used to generate a random normal distribution.
    … …  
    801814      return std::sqrt(-2*std::log(S)/S)*V1;
    802815    }
    803     /// Normal (Gauss) distribution with given mean and standard deviation
    804 
    805     /// Normal (Gauss) distribution with given mean and standard deviation.
     816    /// Gauss distribution with given mean and standard deviation
     817
     818    /// Gauss distribution with given mean and standard deviation.
    806819    /// \sa gauss()
    807820    double gauss(double mean,double std_dev)
    808821    {
    809822      return gauss()*std_dev+mean;
    810     }
    811 
    812     /// Lognormal distribution
    813 
    814     /// Lognormal distribution. The parameters are the mean and the standard
    815     /// deviation of <tt>exp(X)</tt>.
    816     ///
    817     double lognormal(double n_mean,double n_std_dev)
    818     {
    819       return std::exp(gauss(n_mean,n_std_dev));
    820     }
    821     /// Lognormal distribution
    822 
    823     /// Lognormal distribution. The parameter is an <tt>std::pair</tt> of
    824     /// the mean and the standard deviation of <tt>exp(X)</tt>.
    825     ///
    826     double lognormal(const std::pair<double,double> &params)
    827     {
    828       return std::exp(gauss(params.first,params.second));
    829     }
    830     /// Compute the lognormal parameters from mean and standard deviation
    831 
    832     /// This function computes the lognormal parameters from mean and
    833     /// standard deviation. The return value can direcly be passed to
    834     /// lognormal().
    835     std::pair<double,double> lognormalParamsFromMD(double mean,
    836                                                    double std_dev)
    837     {
    838       double fr=std_dev/mean;
    839       fr*=fr;
    840       double lg=std::log(1+fr);
    841       return std::pair<double,double>(std::log(mean)-lg/2.0,std::sqrt(lg));
    842     }
    843     /// Lognormal distribution with given mean and standard deviation
    844 
    845     /// Lognormal distribution with given mean and standard deviation.
    846     ///
    847     double lognormalMD(double mean,double std_dev)
    848     {
    849       return lognormal(lognormalParamsFromMD(mean,std_dev));
    850823    }
    851824
    … …  
    953926    ///\name Two dimensional distributions
    954927    ///
     928
    955929    ///@{
    956930
    … …  
    969943      return dim2::Point<double>(V1,V2);
    970944    }
    971     /// A kind of two dimensional normal (Gauss) distribution
     945    /// A kind of two dimensional Gauss distribution
    972946
    973947    /// This function provides a turning symmetric two-dimensional distribution.

  • lemon/smart_graph.h

    r375 r313  
    6868
    6969    typedef True NodeNumTag;
    70     typedef True ArcNumTag;
     70    typedef True EdgeNumTag;
    7171
    7272    int nodeNum() const { return nodes.size(); }
    … …  
    306306      nodes[b._id].first_out=nodes[n._id].first_out;
    307307      nodes[n._id].first_out=-1;
    308       for(int i=nodes[b._id].first_out; i!=-1; i=arcs[i].next_out) {
    309         arcs[i].source=b._id;
    310       }
     308      for(int i=nodes[b._id].first_out;i!=-1;i++) arcs[i].source=b._id;
    311309      if(connect) addArc(n,b);
    312310      return b;
    … …  
    467465
    468466    public:
    469       operator Edge() const {
    470         return _id != -1 ? edgeFromId(_id / 2) : INVALID;
     467      operator Edge() const { 
     468        return _id != -1 ? edgeFromId(_id / 2) : INVALID; 
    471469      }
    472470
    … …  
    483481      : nodes(), arcs() {}
    484482
    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(); }
    492483
    493484    int maxNodeId() const { return nodes.size()-1; }
    … …  
    738729        dir.push_back(arcFromId(n-1));
    739730        Parent::notifier(Arc()).erase(dir);
    740         nodes[arcs[n-1].target].first_out=arcs[n].next_out;
    741         nodes[arcs[n].target].first_out=arcs[n-1].next_out;
     731        nodes[arcs[n].target].first_out=arcs[n].next_out;
     732        nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
    742733        arcs.pop_back();
    743734        arcs.pop_back();

  • scripts/chg-len.py

    r376 r284  
    22
    33import sys
    4 
    5 from mercurial import ui, hg
     4import os
    65
    76if len(sys.argv)>1 and sys.argv[1] in ["-h","--help"]:
    … …  
    1110"""
    1211    exit(0)
     12plist = os.popen("HGRCPATH='' hg parents --template='{rev}\n'").readlines()
     13if len(plist)>1:
     14    print "You are in the process of merging"
     15    exit(1)
     16PAR = int(plist[0])
    1317
    14 u = ui.ui()
    15 r = hg.repository(u, ".")
    16 N = r.changectx(".").rev()
    17 lengths=[0]*(N+1)
    18 for i in range(N+1):
    19     p=r.changectx(i).parents()
    20     if p[0]:
    21         p0=lengths[p[0].rev()]
     18f = os.popen("HGRCPATH='' hg log -r 0:tip --template='{rev} {parents}\n'").\
     19    readlines()
     20REV = -1
     21lengths=[]
     22for l in f:
     23    REV+=1
     24    s = l.split()
     25    rev = int(s[0])
     26    if REV != rev:
     27        print "Something is seriously wrong"
     28        exit(1)
     29    if len(s) == 1:
     30        par1 = par2 = rev - 1
     31    elif len(s) == 2:
     32        par1 = par2 = int(s[1].split(":")[0])
    2233    else:
    23         p0=-1
    24     if len(p)>1 and p[1]:
    25         p1=lengths[p[1].rev()]
     34        par1 = int(s[1].split(":")[0])
     35        par2 = int(s[2].split(":")[0])
     36    if rev == 0:
     37        lengths.append(0)
    2638    else:
    27         p1=-1
    28     lengths[i]=max(p0,p1)+1
    29 print lengths[N]
     39        lengths.append(max(lengths[par1],lengths[par2])+1)
     40print lengths[PAR]

  • scripts/unify-sources.sh

    r396 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 [ $WARNED_FILES -gt 0 -o $FAILED_FILES -gt 0 ]
    134     then
    135         if [ "$WARNING" == 'INTERACTIVE' ]
    136         then
    137             echo -n "Are the files with errors/warnings acceptable? (yes/no) "
    138             while read answer
    139             do
    140                 if [ "$answer" == 'yes' ]
    141                 then
    142                     return 0
    143                 elif [ "$answer" == 'no' ]
    144                 then
    145                     return 1
    146                 fi
    147                 echo -n "Are the files with errors/warnings acceptable? (yes/no) "
    148             done
    149         elif [ "$WARNING" == 'WERROR' ]
    150         then
    151             return 1
    152         fi
    153     fi
    154 }
    155 
    156 function check_begin() {
    157     ((TOTAL_FILES++))
    158     FAILED=NO
    159     WARNED=NO
    160 }
    161 
    162 function check_end() {
    163     if [ $FAILED == YES ]
    164     then
    165         ((++FAILED_FILES))
    166     fi
    167     if [ $WARNED == YES ]
    168     then
    169         ((++WARNED_FILES))
    170     fi
    171 }
    172 
    173 
    174 
    175 # checks
    176 
    177 function header_check() {
    178     if echo $1 | grep -q -E 'Makefile\.am$'
    179     then
    180         return
    181     fi
    182 
     6function update_header() {
    1837    TMP_FILE=`mktemp`
     8    FILE_NAME=$1
    1849
    18510    (echo "/* -*- mode: C++; indent-tabs-mode: nil; -*-
    … …  
    20126 */
    20227"
    203     awk 'BEGIN { pm=0; }
     28        awk 'BEGIN { pm=0; }
    20429     pm==3 { print }
    20530     /\/\* / && pm==0 { pm=1;}
    … …  
    20732     /\*\// && pm==1 { pm=2;}
    20833    ' $1
    209     ) >$TMP_FILE
     34        ) >$TMP_FILE
    21035
    211     "$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
    21240}
    21341
    214 function tabs_check() {
    215     if echo $1 | grep -q -v -E 'Makefile\.am$'
    216     then
    217         OLD_PATTERN=$(echo -e '\t')
    218         NEW_PATTERN='        '
    219     else
    220         OLD_PATTERN='        '
    221         NEW_PATTERN=$(echo -e '\t')
    222     fi
     42function update_tabs() {
    22343    TMP_FILE=`mktemp`
    224     cat $1 | sed -e "s/$OLD_PATTERN/$NEW_PATTERN/g" >$TMP_FILE
     44    FILE_NAME=$1
    22545
    226     "$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
    22753}
    22854
    229 function spaces_check() {
     55function remove_trailing_space() {
    23056    TMP_FILE=`mktemp`
    231     cat $1 | sed -e 's/ \+$//g' >$TMP_FILE
     57    FILE_NAME=$1
    23258
    233     "$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
    23466}
    23567
    236 function long_lines_check() {
    237     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 ]];
    23881    then
    239         "$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++))
    240104    fi
    241105}
    242106
    243 # process the file
    244 
    245 function process_file() {
    246     if [ "$ACTION" == 'update' ]
    247     then
    248         echo -n "    $ACTION $1..."
    249     else
    250         echo "    $ACTION $1..."
    251     fi
    252 
    253     CHECKING="header tabs spaces long_lines"
    254 
    255     "$ACTION"_begin $1
    256     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)$'`
    257113    do
    258         "$check"_check $1
     114        update_file $HGROOT/$i
     115        ((TOTAL_FILES++))
    259116    done
    260     "$ACTION"_end $1
    261     if [ "$ACTION" == 'update' ]
    262     then
    263         echo
    264     fi
    265 }
    266 
    267 function process_all {
    268     "$ACTION"_init
    269     while read file
     117    echo '  done.'
     118else
     119    for i in $*
    270120    do
    271         process_file $file
    272     done < <($FILES)
    273     "$ACTION"_done
    274 }
    275 
    276 while [ $# -gt 0 ]
    277 do
    278    
    279     if [ "$1" == '--help' ] || [ "$1" == '-h' ]
    280     then
    281         echo -n \
    282 "Usage:
    283   $0 [OPTIONS] [files]
    284 Options:
    285   --dry-run|-n
    286      Check the files, but do not modify them.
    287   --interactive|-i
    288      If --dry-run is specified and the checker emits warnings,
    289      then the user is asked if the warnings should be considered
    290      errors.
    291   --werror|-w
    292      Make all warnings into errors.
    293   --all|-a
    294      Check all source files in the repository.
    295   --modified|-m
    296      Check only the modified (and new) source files. This option is
    297      useful to check the modification before making a commit.
    298   --changed|-c
    299      Check only the changed source files compared to the parent(s) of
    300      the current hg node.  This option is useful as hg hook script.
    301      To automatically check all your changes before making a commit,
    302      add the following section to the appropriate .hg/hgrc file.
    303 
    304        [hooks]
    305        pretxncommit.checksources = scripts/unify-sources.sh -c -n -i
    306 
    307   --help|-h
    308      Print this help message.
    309   files
    310      The files to check/unify. If no file names are given, the modified
    311      source files will be checked/unified (just like using the
    312      --modified|-m option).
    313 "
    314         exit 0
    315     elif [ "$1" == '--dry-run' ] || [ "$1" == '-n' ]
    316     then
    317         [ -n "$ACTION" ] && echo "Conflicting action options" >&2 && exit 1
    318         ACTION=check
    319     elif [ "$1" == "--all" ] || [ "$1" == '-a' ]
    320     then
    321         [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1
    322         FILES=all_files
    323     elif [ "$1" == "--changed" ] || [ "$1" == '-c' ]
    324     then
    325         [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1
    326         FILES=changed_files
    327     elif [ "$1" == "--modified" ] || [ "$1" == '-m' ]
    328     then
    329         [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1
    330         FILES=modified_files
    331     elif [ "$1" == "--interactive" ] || [ "$1" == "-i" ]
    332     then
    333         [ -n "$WARNING" ] && echo "Conflicting warning options" >&2 && exit 1
    334         WARNING='INTERACTIVE'
    335     elif [ "$1" == "--werror" ] || [ "$1" == "-w" ]
    336     then
    337         [ -n "$WARNING" ] && echo "Conflicting warning options" >&2 && exit 1
    338         WARNING='WERROR'
    339     elif [ $(echo x$1 | cut -c 2) == '-' ]
    340     then
    341         echo "Invalid option $1" >&2 && exit 1
    342     else
    343         [ -n "$FILES" ] && echo "Invalid option $1" >&2 && exit 1
    344         GIVEN_FILES=$@
    345         FILES=given_files
    346         break
    347     fi
    348    
    349     shift
    350 done
    351 
    352 if [ -z $FILES ]
    353 then
    354     FILES=modified_files
     121        update_file $i
     122        ((TOTAL_FILES++))
     123    done
    355124fi
    356 
    357 if [ -z $ACTION ]
    358 then
    359     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
    360134fi
    361 
    362 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

    r389 r228  
    11EXTRA_DIST += \
    2         test/CMakeLists.txt \
    3         test/min_cost_flow_test.lgf \
    4         test/preflow_graph.lgf
     2        test/CMakeLists.txt
    53
    64noinst_HEADERS += \
    … …  
    2220        test/kruskal_test \
    2321        test/maps_test \
    24         test/max_matching_test \
    2522        test/random_test \
    2623        test/path_test \
    27         test/preflow_test \
    28         test/suurballe_test \
    2924        test/test_tools_fail \
    3025        test/test_tools_pass \
    … …  
    4843test_kruskal_test_SOURCES = test/kruskal_test.cc
    4944test_maps_test_SOURCES = test/maps_test.cc
    50 test_max_matching_test_SOURCES = test/max_matching_test.cc
    5145test_path_test_SOURCES = test/path_test.cc
    52 test_preflow_test_SOURCES = test/preflow_test.cc
    53 test_suurballe_test_SOURCES = test/suurballe_test.cc
    5446test_random_test_SOURCES = test/random_test.cc
    5547test_test_tools_fail_SOURCES = test/test_tools_fail.cc

  • test/digraph_test.cc

    r375 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"
    … …  
    2930
    3031template <class Digraph>
    31 void checkDigraphBuild() {
     32void checkDigraph() {
    3233  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    3334  Digraph G;
    … …  
    5859  checkGraphConArcList(G, 1);
    5960
    60   Arc a2 = G.addArc(n2, n1),
    61       a3 = G.addArc(n2, n3),
    62       a4 = G.addArc(n2, n3);
    63 
    64   checkGraphNodeList(G, 3);
    65   checkGraphArcList(G, 4);
    66 
    67   checkGraphOutArcList(G, n1, 1);
    68   checkGraphOutArcList(G, n2, 3);
    69   checkGraphOutArcList(G, n3, 0);
    70 
    71   checkGraphInArcList(G, n1, 1);
    72   checkGraphInArcList(G, n2, 1);
    73   checkGraphInArcList(G, n3, 2);
    74 
    75   checkGraphConArcList(G, 4);
    76 
    77   checkNodeIds(G);
    78   checkArcIds(G);
    79   checkGraphNodeMap(G);
    80   checkGraphArcMap(G);
    81 }
    82 
    83 template <class Digraph>
    84 void checkDigraphSplit() {
    85   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    86 
    87   Digraph G;
    88   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
    89   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
    90       a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
    91 
    92   Node n4 = G.split(n2);
    93 
    94   check(G.target(OutArcIt(G, n2)) == n4 &&
    95         G.source(InArcIt(G, n4)) == n2,
    96         "Wrong split.");
    97 
    98   checkGraphNodeList(G, 4);
    99   checkGraphArcList(G, 5);
    100 
    101   checkGraphOutArcList(G, n1, 1);
    102   checkGraphOutArcList(G, n2, 1);
    103   checkGraphOutArcList(G, n3, 0);
    104   checkGraphOutArcList(G, n4, 3);
    105 
    106   checkGraphInArcList(G, n1, 1);
    107   checkGraphInArcList(G, n2, 1);
    108   checkGraphInArcList(G, n3, 2);
    109   checkGraphInArcList(G, n4, 1);
    110 
    111   checkGraphConArcList(G, 5);
    112 }
    113 
    114 template <class Digraph>
    115 void checkDigraphAlter() {
    116   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    117 
    118   Digraph G;
    119   Node n1 = G.addNode(), n2 = G.addNode(),
    120        n3 = G.addNode(), n4 = G.addNode();
    121   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
    122       a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3),
    123       a5 = G.addArc(n2, n4);
    124 
    125   checkGraphNodeList(G, 4);
    126   checkGraphArcList(G, 5);
    127 
    128   // Check changeSource() and changeTarget()
    129   G.changeTarget(a4, n1);
    130 
    131   checkGraphNodeList(G, 4);
    132   checkGraphArcList(G, 5);
    133 
    134   checkGraphOutArcList(G, n1, 1);
    135   checkGraphOutArcList(G, n2, 1);
    136   checkGraphOutArcList(G, n3, 0);
    137   checkGraphOutArcList(G, n4, 3);
    138 
    139   checkGraphInArcList(G, n1, 2);
    140   checkGraphInArcList(G, n2, 1);
    141   checkGraphInArcList(G, n3, 1);
    142   checkGraphInArcList(G, n4, 1);
    143 
    144   checkGraphConArcList(G, 5);
    145 
    146   G.changeSource(a4, n3);
    147 
    148   checkGraphNodeList(G, 4);
    149   checkGraphArcList(G, 5);
    150 
    151   checkGraphOutArcList(G, n1, 1);
    152   checkGraphOutArcList(G, n2, 1);
    153   checkGraphOutArcList(G, n3, 1);
    154   checkGraphOutArcList(G, n4, 2);
    155 
    156   checkGraphInArcList(G, n1, 2);
    157   checkGraphInArcList(G, n2, 1);
    158   checkGraphInArcList(G, n3, 1);
    159   checkGraphInArcList(G, n4, 1);
    160 
    161   checkGraphConArcList(G, 5);
    162 
    163   // Check contract()
    164   G.contract(n2, n4, false);
    165 
    166   checkGraphNodeList(G, 3);
    167   checkGraphArcList(G, 5);
    168 
    169   checkGraphOutArcList(G, n1, 1);
    170   checkGraphOutArcList(G, n2, 3);
    171   checkGraphOutArcList(G, n3, 1);
    172 
    173   checkGraphInArcList(G, n1, 2);
    174   checkGraphInArcList(G, n2, 2);
    175   checkGraphInArcList(G, n3, 1);
    176 
    177   checkGraphConArcList(G, 5);
    178 
    179   G.contract(n2, n1);
    180 
    181   checkGraphNodeList(G, 2);
    182   checkGraphArcList(G, 3);
    183 
    184   checkGraphOutArcList(G, n2, 2);
    185   checkGraphOutArcList(G, n3, 1);
    186 
    187   checkGraphInArcList(G, n2, 2);
    188   checkGraphInArcList(G, n3, 1);
    189 
    190   checkGraphConArcList(G, 3);
    191 }
    192 
    193 template <class Digraph>
    194 void checkDigraphErase() {
    195   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    196 
    197   Digraph G;
    198   Node n1 = G.addNode(), n2 = G.addNode(),
    199        n3 = G.addNode(), n4 = G.addNode();
    200   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
    201       a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1),
    202       a5 = G.addArc(n2, n4);
    203 
    204   // Check arc deletion
    205   G.erase(a1);
    206 
    207   checkGraphNodeList(G, 4);
    208   checkGraphArcList(G, 4);
    209 
    210   checkGraphOutArcList(G, n1, 0);
    211   checkGraphOutArcList(G, n2, 1);
    212   checkGraphOutArcList(G, n3, 1);
    213   checkGraphOutArcList(G, n4, 2);
    214 
    215   checkGraphInArcList(G, n1, 2);
    216   checkGraphInArcList(G, n2, 0);
    217   checkGraphInArcList(G, n3, 1);
    218   checkGraphInArcList(G, n4, 1);
    219 
    220   checkGraphConArcList(G, 4);
    221 
    222   // Check node deletion
    223   G.erase(n4);
    224 
    225   checkGraphNodeList(G, 3);
    226   checkGraphArcList(G, 1);
    227 
    228   checkGraphOutArcList(G, n1, 0);
    229   checkGraphOutArcList(G, n2, 0);
    230   checkGraphOutArcList(G, n3, 1);
    231   checkGraphOutArcList(G, n4, 0);
    232 
    233   checkGraphInArcList(G, n1, 1);
    234   checkGraphInArcList(G, n2, 0);
    235   checkGraphInArcList(G, n3, 0);
    236   checkGraphInArcList(G, n4, 0);
    237 
    238   checkGraphConArcList(G, 1);
    239 }
    240 
    241 
    242 template <class Digraph>
    243 void checkDigraphSnapshot() {
    244   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    245 
    246   Digraph G;
    247   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
    248   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
    249       a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
    250 
    251   typename Digraph::Snapshot snapshot(G);
    252 
    253   Node n = G.addNode();
    254   G.addArc(n3, n);
    255   G.addArc(n, n3);
    256 
    257   checkGraphNodeList(G, 4);
    258   checkGraphArcList(G, 6);
    259 
    260   snapshot.restore();
    261 
     61  Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
    26262  checkGraphNodeList(G, 3);
    26363  checkGraphArcList(G, 4);
    … …  
    27878  checkGraphArcMap(G);
    27979
    280   G.addNode();
    281   snapshot.save(G);
     80}
    28281
    283   G.addArc(G.addNode(), G.addNode());
    284 
    285   snapshot.restore();
    286 
    287   checkGraphNodeList(G, 4);
    288   checkGraphArcList(G, 4);
    289 }
    29082
    29183void checkConcepts() {
    … …  
    318110    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
    319111  }
    320   { // Checking FullDigraph
    321     checkConcept<Digraph, FullDigraph>();
    322   }
     112//  { // Checking FullDigraph
     113//    checkConcept<Digraph, FullDigraph>();
     114//  }
     115//  { // Checking HyperCubeDigraph
     116//    checkConcept<Digraph, HyperCubeDigraph>();
     117//  }
    323118}
    324119
    … …  
    373168}
    374169
    375 void checkFullDigraph(int num) {
    376   typedef FullDigraph Digraph;
    377   DIGRAPH_TYPEDEFS(Digraph);
    378   Digraph G(num);
    379 
    380   checkGraphNodeList(G, num);
    381   checkGraphArcList(G, num * num);
    382 
    383   for (NodeIt n(G); n != INVALID; ++n) {
    384     checkGraphOutArcList(G, n, num);
    385     checkGraphInArcList(G, n, num);
    386   }
    387 
    388   checkGraphConArcList(G, num * num);
    389 
    390   checkNodeIds(G);
    391   checkArcIds(G);
    392   checkGraphNodeMap(G);
    393   checkGraphArcMap(G);
    394 
    395   for (int i = 0; i < G.nodeNum(); ++i) {
    396     check(G.index(G(i)) == i, "Wrong index");
    397   }
    398 
    399   for (NodeIt s(G); s != INVALID; ++s) {
    400     for (NodeIt t(G); t != INVALID; ++t) {
    401       Arc a = G.arc(s, t);
    402       check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
    403     }
    404   }
    405 }
    406 
    407170void checkDigraphs() {
    408171  { // Checking ListDigraph
    409     checkDigraphBuild<ListDigraph>();
    410     checkDigraphSplit<ListDigraph>();
    411     checkDigraphAlter<ListDigraph>();
    412     checkDigraphErase<ListDigraph>();
    413     checkDigraphSnapshot<ListDigraph>();
     172    checkDigraph<ListDigraph>();
    414173    checkDigraphValidityErase<ListDigraph>();
    415174  }
    416175  { // Checking SmartDigraph
    417     checkDigraphBuild<SmartDigraph>();
    418     checkDigraphSplit<SmartDigraph>();
    419     checkDigraphSnapshot<SmartDigraph>();
     176    checkDigraph<SmartDigraph>();
    420177    checkDigraphValidity<SmartDigraph>();
    421   }
    422   { // Checking FullDigraph
    423     checkFullDigraph(8);
    424178  }
    425179}

  • test/graph_test.cc

    r375 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"
    … …  
    3130
    3231template <class Graph>
    33 void checkGraphBuild() {
     32void checkGraph() {
    3433  TEMPLATE_GRAPH_TYPEDEFS(Graph);
    3534
    … …  
    3736  checkGraphNodeList(G, 0);
    3837  checkGraphEdgeList(G, 0);
    39   checkGraphArcList(G, 0);
    4038
    4139  Node
    … …  
    4543  checkGraphNodeList(G, 3);
    4644  checkGraphEdgeList(G, 0);
    47   checkGraphArcList(G, 0);
    4845
    4946  Edge e1 = G.addEdge(n1, n2);
    5047  check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
    5148        "Wrong edge");
    52 
    5349  checkGraphNodeList(G, 3);
     50  checkGraphArcList(G, 2);
    5451  checkGraphEdgeList(G, 1);
    55   checkGraphArcList(G, 2);
    56 
    57   checkGraphIncEdgeArcLists(G, n1, 1);
    58   checkGraphIncEdgeArcLists(G, n2, 1);
    59   checkGraphIncEdgeArcLists(G, n3, 0);
    60 
     52
     53  checkGraphOutArcList(G, n1, 1);
     54  checkGraphOutArcList(G, n2, 1);
     55  checkGraphOutArcList(G, n3, 0);
     56
     57  checkGraphInArcList(G, n1, 1);
     58  checkGraphInArcList(G, n2, 1);
     59  checkGraphInArcList(G, n3, 0);
     60
     61  checkGraphIncEdgeList(G, n1, 1);
     62  checkGraphIncEdgeList(G, n2, 1);
     63  checkGraphIncEdgeList(G, n3, 0);
     64
     65  checkGraphConArcList(G, 2);
    6166  checkGraphConEdgeList(G, 1);
    62   checkGraphConArcList(G, 2);
    63 
    64   Edge e2 = G.addEdge(n2, n1),
    65        e3 = G.addEdge(n2, n3);
    66 
     67
     68  Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
    6769  checkGraphNodeList(G, 3);
     70  checkGraphArcList(G, 6);
    6871  checkGraphEdgeList(G, 3);
    69   checkGraphArcList(G, 6);
    70 
    71   checkGraphIncEdgeArcLists(G, n1, 2);
    72   checkGraphIncEdgeArcLists(G, n2, 3);
    73   checkGraphIncEdgeArcLists(G, n3, 1);
    74 
     72
     73  checkGraphOutArcList(G, n1, 2);
     74  checkGraphOutArcList(G, n2, 3);
     75  checkGraphOutArcList(G, n3, 1);
     76
     77  checkGraphInArcList(G, n1, 2);
     78  checkGraphInArcList(G, n2, 3);
     79  checkGraphInArcList(G, n3, 1);
     80
     81  checkGraphIncEdgeList(G, n1, 2);
     82  checkGraphIncEdgeList(G, n2, 3);
     83  checkGraphIncEdgeList(G, n3, 1);
     84
     85  checkGraphConArcList(G, 6);
    7586  checkGraphConEdgeList(G, 3);
    76   checkGraphConArcList(G, 6);
    7787
    7888  checkArcDirections(G);
    … …  
    8696}
    8797
    88 template <class Graph>
    89 void checkGraphAlter() {
    90   TEMPLATE_GRAPH_TYPEDEFS(Graph);
    91 
    92   Graph G;
    93   Node n1 = G.addNode(), n2 = G.addNode(),
    94        n3 = G.addNode(), n4 = G.addNode();
    95   Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
    96        e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
    97        e5 = G.addEdge(n4, n3);
    98 
    99   checkGraphNodeList(G, 4);
    100   checkGraphEdgeList(G, 5);
    101   checkGraphArcList(G, 10);
    102 
    103   // Check changeU() and changeV()
    104   if (G.u(e2) == n2) {
    105     G.changeU(e2, n3);
    106   } else {
    107     G.changeV(e2, n3);
    108   }
    109 
    110   checkGraphNodeList(G, 4);
    111   checkGraphEdgeList(G, 5);
    112   checkGraphArcList(G, 10);
    113 
    114   checkGraphIncEdgeArcLists(G, n1, 3);
    115   checkGraphIncEdgeArcLists(G, n2, 2);
    116   checkGraphIncEdgeArcLists(G, n3, 3);
    117   checkGraphIncEdgeArcLists(G, n4, 2);
    118 
    119   checkGraphConEdgeList(G, 5);
    120   checkGraphConArcList(G, 10);
    121 
    122   if (G.u(e2) == n1) {
    123     G.changeU(e2, n2);
    124   } else {
    125     G.changeV(e2, n2);
    126   }
    127 
    128   checkGraphNodeList(G, 4);
    129   checkGraphEdgeList(G, 5);
    130   checkGraphArcList(G, 10);
    131 
    132   checkGraphIncEdgeArcLists(G, n1, 2);
    133   checkGraphIncEdgeArcLists(G, n2, 3);
    134   checkGraphIncEdgeArcLists(G, n3, 3);
    135   checkGraphIncEdgeArcLists(G, n4, 2);
    136 
    137   checkGraphConEdgeList(G, 5);
    138   checkGraphConArcList(G, 10);
    139 
    140   // Check contract()
    141   G.contract(n1, n4, false);
    142 
    143   checkGraphNodeList(G, 3);
    144   checkGraphEdgeList(G, 5);
    145   checkGraphArcList(G, 10);
    146 
    147   checkGraphIncEdgeArcLists(G, n1, 4);
    148   checkGraphIncEdgeArcLists(G, n2, 3);
    149   checkGraphIncEdgeArcLists(G, n3, 3);
    150 
    151   checkGraphConEdgeList(G, 5);
    152   checkGraphConArcList(G, 10);
    153 
    154   G.contract(n2, n3);
    155 
    156   checkGraphNodeList(G, 2);
    157   checkGraphEdgeList(G, 3);
    158   checkGraphArcList(G, 6);
    159 
    160   checkGraphIncEdgeArcLists(G, n1, 4);
    161   checkGraphIncEdgeArcLists(G, n2, 2);
    162 
    163   checkGraphConEdgeList(G, 3);
    164   checkGraphConArcList(G, 6);
    165 }
    166 
    167 template <class Graph>
    168 void checkGraphErase() {
    169   TEMPLATE_GRAPH_TYPEDEFS(Graph);
    170 
    171   Graph G;
    172   Node n1 = G.addNode(), n2 = G.addNode(),
    173        n3 = G.addNode(), n4 = G.addNode();
    174   Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
    175        e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
    176        e5 = G.addEdge(n4, n3);
    177 
    178   // Check edge deletion
    179   G.erase(e2);
    180 
    181   checkGraphNodeList(G, 4);
    182   checkGraphEdgeList(G, 4);
    183   checkGraphArcList(G, 8);
    184 
    185   checkGraphIncEdgeArcLists(G, n1, 2);
    186   checkGraphIncEdgeArcLists(G, n2, 2);
    187   checkGraphIncEdgeArcLists(G, n3, 2);
    188   checkGraphIncEdgeArcLists(G, n4, 2);
    189 
    190   checkGraphConEdgeList(G, 4);
    191   checkGraphConArcList(G, 8);
    192 
    193   // Check node deletion
    194   G.erase(n3);
    195 
    196   checkGraphNodeList(G, 3);
    197   checkGraphEdgeList(G, 2);
    198   checkGraphArcList(G, 4);
    199 
    200   checkGraphIncEdgeArcLists(G, n1, 2);
    201   checkGraphIncEdgeArcLists(G, n2, 1);
    202   checkGraphIncEdgeArcLists(G, n4, 1);
    203 
    204   checkGraphConEdgeList(G, 2);
    205   checkGraphConArcList(G, 4);
    206 }
    207 
    208 
    209 template <class Graph>
    210 void checkGraphSnapshot() {
    211   TEMPLATE_GRAPH_TYPEDEFS(Graph);
    212 
    213   Graph G;
    214   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
    215   Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
    216        e3 = G.addEdge(n2, n3);
    217 
    218   checkGraphNodeList(G, 3);
    219   checkGraphEdgeList(G, 3);
    220   checkGraphArcList(G, 6);
    221 
    222   typename Graph::Snapshot snapshot(G);
    223 
    224   Node n = G.addNode();
    225   G.addEdge(n3, n);
    226   G.addEdge(n, n3);
    227   G.addEdge(n3, n2);
    228 
    229   checkGraphNodeList(G, 4);
    230   checkGraphEdgeList(G, 6);
    231   checkGraphArcList(G, 12);
    232 
    233   snapshot.restore();
    234 
    235   checkGraphNodeList(G, 3);
    236   checkGraphEdgeList(G, 3);
    237   checkGraphArcList(G, 6);
    238 
    239   checkGraphIncEdgeArcLists(G, n1, 2);
    240   checkGraphIncEdgeArcLists(G, n2, 3);
    241   checkGraphIncEdgeArcLists(G, n3, 1);
    242 
    243   checkGraphConEdgeList(G, 3);
    244   checkGraphConArcList(G, 6);
    245 
    246   checkNodeIds(G);
    247   checkEdgeIds(G);
    248   checkArcIds(G);
    249   checkGraphNodeMap(G);
    250   checkGraphEdgeMap(G);
    251   checkGraphArcMap(G);
    252 
    253   G.addNode();
    254   snapshot.save(G);
    255 
    256   G.addEdge(G.addNode(), G.addNode());
    257 
    258   snapshot.restore();
    259 
    260   checkGraphNodeList(G, 4);
    261   checkGraphEdgeList(G, 3);
    262   checkGraphArcList(G, 6);
    263 }
    264 
    265 void checkFullGraph(int num) {
    266   typedef FullGraph Graph;
    267   GRAPH_TYPEDEFS(Graph);
    268 
    269   Graph G(num);
    270   checkGraphNodeList(G, num);
    271   checkGraphEdgeList(G, num * (num - 1) / 2);
    272 
    273   for (NodeIt n(G); n != INVALID; ++n) {
    274     checkGraphOutArcList(G, n, num - 1);
    275     checkGraphInArcList(G, n, num - 1);
    276     checkGraphIncEdgeList(G, n, num - 1);
    277   }
    278 
    279   checkGraphConArcList(G, num * (num - 1));
    280   checkGraphConEdgeList(G, num * (num - 1) / 2);
    281 
    282   checkArcDirections(G);
    283 
    284   checkNodeIds(G);
    285   checkArcIds(G);
    286   checkEdgeIds(G);
    287   checkGraphNodeMap(G);
    288   checkGraphArcMap(G);
    289   checkGraphEdgeMap(G);
    290 
    291 
    292   for (int i = 0; i < G.nodeNum(); ++i) {
    293     check(G.index(G(i)) == i, "Wrong index");
    294   }
    295 
    296   for (NodeIt u(G); u != INVALID; ++u) {
    297     for (NodeIt v(G); v != INVALID; ++v) {
    298       Edge e = G.edge(u, v);
    299       Arc a = G.arc(u, v);
    300       if (u == v) {
    301         check(e == INVALID, "Wrong edge lookup");
    302         check(a == INVALID, "Wrong arc lookup");
    303       } else {
    304         check((G.u(e) == u && G.v(e) == v) ||
    305               (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");
    306         check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");
    307       }
    308     }
    309   }
    310 }
    311 
    31298void checkConcepts() {
    31399  { // Checking graph components
    … …  
    339125    checkConcept<ClearableGraphComponent<>, SmartGraph>();
    340126  }
    341   { // Checking FullGraph
    342     checkConcept<Graph, FullGraph>();
    343   }
    344   { // Checking GridGraph
    345     checkConcept<Graph, GridGraph>();
    346   }
    347   { // Checking HypercubeGraph
    348     checkConcept<Graph, HypercubeGraph>();
    349   }
     127//  { // Checking FullGraph
     128//    checkConcept<Graph, FullGraph>();
     129//    checkGraphIterators<FullGraph>();
     130//  }
     131//  { // Checking GridGraph
     132//    checkConcept<Graph, GridGraph>();
     133//    checkGraphIterators<GridGraph>();
     134//  }
    350135}
    351136
    … …  
    404189}
    405190
    406 void checkGridGraph(int width, int height) {
    407   typedef GridGraph Graph;
    408   GRAPH_TYPEDEFS(Graph);
    409   Graph G(width, height);
    410 
    411   check(G.width() == width, "Wrong column number");
    412   check(G.height() == height, "Wrong row number");
    413 
    414   for (int i = 0; i < width; ++i) {
    415     for (int j = 0; j < height; ++j) {
    416       check(G.col(G(i, j)) == i, "Wrong column");
    417       check(G.row(G(i, j)) == j, "Wrong row");
    418       check(G.pos(G(i, j)).x == i, "Wrong column");
    419       check(G.pos(G(i, j)).y == j, "Wrong row");
    420     }
    421   }
    422 
    423   for (int j = 0; j < height; ++j) {
    424     for (int i = 0; i < width - 1; ++i) {
    425       check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");
    426       check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");
    427     }
    428     check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
    429   }
    430 
    431   for (int j = 0; j < height; ++j) {
    432     for (int i = 1; i < width; ++i) {
    433       check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");
    434       check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");
    435     }
    436     check(G.left(G(0, j)) == INVALID, "Wrong left");
    437   }
    438 
    439   for (int i = 0; i < width; ++i) {
    440     for (int j = 0; j < height - 1; ++j) {
    441       check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");
    442       check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");
    443     }
    444     check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
    445   }
    446 
    447   for (int i = 0; i < width; ++i) {
    448     for (int j = 1; j < height; ++j) {
    449       check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");
    450       check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");
    451     }
    452     check(G.down(G(i, 0)) == INVALID, "Wrong down");
    453   }
    454 
    455   checkGraphNodeList(G, width * height);
    456   checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
    457   checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
    458 
    459   for (NodeIt n(G); n != INVALID; ++n) {
    460     int nb = 4;
    461     if (G.col(n) == 0) --nb;
    462     if (G.col(n) == width - 1) --nb;
    463     if (G.row(n) == 0) --nb;
    464     if (G.row(n) == height - 1) --nb;
    465 
    466     checkGraphOutArcList(G, n, nb);
    467     checkGraphInArcList(G, n, nb);
    468     checkGraphIncEdgeList(G, n, nb);
    469   }
    470 
    471   checkArcDirections(G);
    472 
    473   checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
    474   checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
    475 
    476   checkNodeIds(G);
    477   checkArcIds(G);
    478   checkEdgeIds(G);
    479   checkGraphNodeMap(G);
    480   checkGraphArcMap(G);
    481   checkGraphEdgeMap(G);
    482 
    483 }
    484 
    485 void checkHypercubeGraph(int dim) {
    486   GRAPH_TYPEDEFS(HypercubeGraph);
    487 
    488   HypercubeGraph G(dim);
    489   checkGraphNodeList(G, 1 << dim);
    490   checkGraphEdgeList(G, dim * (1 << (dim-1)));
    491   checkGraphArcList(G, dim * (1 << dim));
    492 
    493   Node n = G.nodeFromId(dim);
    494 
    495   for (NodeIt n(G); n != INVALID; ++n) {
    496     checkGraphIncEdgeList(G, n, dim);
    497     for (IncEdgeIt e(G, n); e != INVALID; ++e) {
    498       check( (G.u(e) == n &&
    499               G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) ||
    500              (G.v(e) == n &&
    501               G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))),
    502              "Wrong edge or wrong dimension");
    503     }
    504 
    505     checkGraphOutArcList(G, n, dim);
    506     for (OutArcIt a(G, n); a != INVALID; ++a) {
    507       check(G.source(a) == n &&
    508             G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))),
    509             "Wrong arc or wrong dimension");
    510     }
    511 
    512     checkGraphInArcList(G, n, dim);
    513     for (InArcIt a(G, n); a != INVALID; ++a) {
    514       check(G.target(a) == n &&
    515             G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))),
    516             "Wrong arc or wrong dimension");
    517     }
    518   }
    519 
    520   checkGraphConArcList(G, (1 << dim) * dim);
    521   checkGraphConEdgeList(G, dim * (1 << (dim-1)));
    522 
    523   checkArcDirections(G);
    524 
    525   checkNodeIds(G);
    526   checkArcIds(G);
    527   checkEdgeIds(G);
    528   checkGraphNodeMap(G);
    529   checkGraphArcMap(G);
    530   checkGraphEdgeMap(G);
    531 }
     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// }
    532234
    533235void checkGraphs() {
    534236  { // Checking ListGraph
    535     checkGraphBuild<ListGraph>();
    536     checkGraphAlter<ListGraph>();
    537     checkGraphErase<ListGraph>();
    538     checkGraphSnapshot<ListGraph>();
     237    checkGraph<ListGraph>();
    539238    checkGraphValidityErase<ListGraph>();
    540239  }
    541240  { // Checking SmartGraph
    542     checkGraphBuild<SmartGraph>();
    543     checkGraphSnapshot<SmartGraph>();
     241    checkGraph<SmartGraph>();
    544242    checkGraphValidity<SmartGraph>();
    545243  }
    546   { // Checking FullGraph
    547     checkFullGraph(7);
    548     checkFullGraph(8);
    549   }
    550   { // Checking GridGraph
    551     checkGridGraph(5, 8);
    552     checkGridGraph(8, 5);
    553     checkGridGraph(5, 5);
    554     checkGridGraph(0, 0);
    555     checkGridGraph(1, 1);
    556   }
    557   { // Checking HypercubeGraph
    558     checkHypercubeGraph(1);
    559     checkHypercubeGraph(2);
    560     checkHypercubeGraph(3);
    561     checkHypercubeGraph(4);
    562   }
     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//   }
    563255}
    564256

  • test/graph_test.h

    r374 r263  
    115115    check(e==INVALID,"Wrong IncEdge list linking.");
    116116    check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
    117   }
    118 
    119   template <class Graph>
    120   void checkGraphIncEdgeArcLists(const Graph &G, typename Graph::Node n,
    121                                  int cnt)
    122   {
    123     checkGraphIncEdgeList(G, n, cnt);
    124     checkGraphOutArcList(G, n, cnt);
    125     checkGraphInArcList(G, n, cnt);
    126117  }
    127118

  • tools/Makefile.am

    r385 r310  
    11if WANT_TOOLS
    22
    3 bin_PROGRAMS += \
    4         tools/dimacs-to-lgf
    5 
     3bin_PROGRAMS +=
    64dist_bin_SCRIPTS += tools/lemon-0.x-to-1.x.sh
    75
    86endif WANT_TOOLS
    9 
    10 tools_dimacs_to_lgf_SOURCES = tools/dimacs-to-lgf.cc

  • 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.