COIN-OR::LEMON - Graph Library

Ignore:
Files:
16 added
28 edited

Legend:

Unmodified
Added
Removed
  • .hgignore

    r298 r400  
    3737^objs.*/.*
    3838^test/[a-z_]*$
     39^tools/[a-z-_]*$
    3940^demo/.*_demo$
    4041^build/.*
  • Makefile.am

    r321 r375  
    11ACLOCAL_AMFLAGS = -I m4
     2
     3AM_CXXFLAGS = $(WARNINGCXXFLAGS)
    24
    35AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)
  • configure.ac

    r310 r375  
    1919AC_CONFIG_SRCDIR([lemon/list_graph.h])
    2020AC_CONFIG_HEADERS([config.h lemon/config.h])
    21 
    22 lx_cmdline_cxxflags_set=${CXXFLAGS+set}
    2321
    2422dnl Do compilation tests using the C++ compiler.
     
    4745
    4846dnl Set custom compiler flags when using g++.
    49 if 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"
     47if 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"
    5149fi
     50AC_SUBST([WARNINGCXXFLAGS])
    5251
    5352dnl Checks for libraries.
     
    114113echo
    115114echo C++ compiler.................. : $CXX
    116 echo C++ compiles flags............ : $CXXFLAGS
     115echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS
    117116echo
    118117#echo GLPK support.................. : $lx_glpk_found
  • doc/CMakeLists.txt

    r225 r347  
    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
    1617      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
    1718      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

    r316 r379  
    6767ENABLED_SECTIONS       =
    6868MAX_INITIALIZER_LINES  = 5
    69 SHOW_USED_FILES        = YES
     69SHOW_USED_FILES        = NO
    7070SHOW_DIRECTORIES       = YES
    7171SHOW_FILES             = YES
  • doc/Makefile.am

    r317 r349  
    1515
    1616DOC_EPS_IMAGES18 = \
     17        grid_graph.eps \
    1718        nodeshape_0.eps \
    1819        nodeshape_1.eps \
  • doc/groups.dox

    r318 r403  
    465465
    466466/**
    467 @defgroup lemon_io LEMON Input-Output
     467@defgroup lemon_io LEMON Graph Format
    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
     489Tools 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
     497Tool to read graphs from \e Nauty format data.
    482498*/
    483499
  • doc/migration.dox

    r314 r355  
    2626
    2727Many of these changes adjusted automatically by the
    28 <tt>script/lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual
     28<tt>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>script/lemon-0.x-to-1.x.sh</tt> tool replaces all instances of
    57 the words \c graph, \c digraph, \c edge and \c arc, so it replaces them
    58 in strings, comments etc. as well as in all identifiers.</b>
     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
     58strings, comments etc. as well as in all LEMON specific identifiers.
     59So use the script carefully and make a backup copy of your source files
     60before applying the script to them.</b>
    5961
    6062\section migration-lgf LGF tools
  • lemon/Makefile.am

    r259 r410  
    1313        lemon/random.cc
    1414
    15 #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
     15#lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) $(AM_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 \
    3032        lemon/error.h \
     33        lemon/full_graph.h \
    3134        lemon/graph_to_eps.h \
     35        lemon/grid_graph.h \
     36        lemon/hypercube_graph.h \
    3237        lemon/kruskal.h \
    3338        lemon/lgf_reader.h \
     
    3641        lemon/maps.h \
    3742        lemon/math.h \
     43        lemon/max_matching.h \
     44        lemon/nauty_reader.h \
    3845        lemon/path.h \
     46        lemon/preflow.h \
    3947        lemon/random.h \
    4048        lemon/smart_graph.h \
     49        lemon/suurballe.h \
    4150        lemon/time_measure.h \
    4251        lemon/tolerance.h \
  • lemon/bfs.h

    r301 r341  
    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.
    84     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     83    ///The type of the map that indicates which nodes are reached.///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8584    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8685    ///Instantiates a ReachedMap.
  • lemon/bits/alteration_notifier.h

    r314 r373  
    3636  // a container.
    3737  //
    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
     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
    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 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.
     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.
    5657  //
    5758  // For the proper functonality of this class, we should notify it
    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
     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
    6364  // clear() and build() members. Important rule that if we erase items
    64   // from graph we should first signal the alteration and after that erase
     65  // from graphs we should first signal the alteration and after that erase
    6566  // them from the container, on the other way on item addition we should
    6667  // first extend the container and just after that signal the alteration.
    6768  //
    6869  // The alteration can be observed with a class inherited from the
    69   // \e ObserverBase nested class. The signals can be handled with
     70  // ObserverBase nested class. The signals can be handled with
    7071  // overriding the virtual functions defined in the base class.  The
    7172  // observer base can be attached to the notifier with the
    72   // \e attach() member and can be detached with detach() function. The
     73  // attach() member and can be detached with detach() function. The
    7374  // alteration handlers should not call any function which signals
    7475  // an other alteration in the same notifier and should not
    7576  // detach any observer from the notifier.
    7677  //
    77   // Alteration observers try to be exception safe. If an \e add() or
    78   // a \e clear() function throws an exception then the remaining
     78  // Alteration observers try to be exception safe. If an add() or
     79  // a clear() function throws an exception then the remaining
    7980  // observeres will not be notified and the fulfilled additions will
    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
     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
    8687  // reliable. If we want to carry out the node degree in the graph
    87   // as in the \ref InDegMap and we use the reverseEdge that cause
     88  // as in the \ref InDegMap and we use the reverseArc(), then it cause
    8889  // unreliable functionality. Because the alteration observing signals
    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.
     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.
    9394  //
    9495  // \param _Container The container which is observed.
     
    104105    typedef _Item Item;
    105106
    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
     107    // \brief Exception which can be called from clear() and
     108    // erase().
     109    //
     110    // From the clear() and erase() function only this
    110111    // exception is allowed to throw. The exception immediatly
    111112    // detaches the current observer from the notifier. Because the
    112     // \e clear() and \e erase() should not throw other exceptions
     113    // clear() and erase() should not throw other exceptions
    113114    // it can be used to invalidate the observer.
    114115    struct ImmediateDetach {};
     
    122123    // The observer interface contains some pure virtual functions
    123124    // to override. The add() and erase() functions are
    124     // to notify the oberver when one item is added or
    125     // erased.
     125    // to notify the oberver when one item is added or erased.
    126126    //
    127127    // The build() and clear() members are to notify the observer
  • lemon/bits/array_map.h

    r314 r373  
    3737  // \brief Graph map based on the array storage.
    3838  //
    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.
     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.
    4342  //
    44   // The template parameters are the Graph the current Item type and
     43  // The template parameters are the Graph, the current Item type and
    4544  // the Value type of the map.
    4645  template <typename _Graph, typename _Item, typename _Value>
     
    4847    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
    4948  public:
    50     // The graph type of the maps.
     49    // The graph type.
    5150    typedef _Graph Graph;
    52     // The item type of the map.
     51    // The item type.
    5352    typedef _Item Item;
    5453    // The reference map tag.
    5554    typedef True ReferenceMapTag;
    5655
    57     // The key type of the maps.
     56    // The key type of the map.
    5857    typedef _Item Key;
    5958    // The value type of the map.
     
    201200    // \brief Adds a new key to the map.
    202201    //
    203     // It adds a new key to the map. It called by the observer notifier
     202    // It adds a new key to the map. It is called by the observer notifier
    204203    // and it overrides the add() member function of the observer base.
    205204    virtual void add(const Key& key) {
     
    229228    // \brief Adds more new keys to the map.
    230229    //
    231     // It adds more new keys to the map. It called by the observer notifier
     230    // It adds more new keys to the map. It is called by the observer notifier
    232231    // and it overrides the add() member function of the observer base.
    233232    virtual void add(const std::vector<Key>& keys) {
     
    273272    // \brief Erase a key from the map.
    274273    //
    275     // Erase a key from the map. It called by the observer notifier
     274    // Erase a key from the map. It is called by the observer notifier
    276275    // and it overrides the erase() member function of the observer base.
    277276    virtual void erase(const Key& key) {
     
    282281    // \brief Erase more keys from the map.
    283282    //
    284     // Erase more keys from the map. It called by the observer notifier
     283    // Erase more keys from the map. It is called by the observer notifier
    285284    // and it overrides the erase() member function of the observer base.
    286285    virtual void erase(const std::vector<Key>& keys) {
     
    291290    }
    292291
    293     // \brief Buildes the map.
    294     //
    295     // It buildes the map. It called by the observer notifier
     292    // \brief Builds the map.
     293    //
     294    // It builds the map. It is called by the observer notifier
    296295    // and it overrides the build() member function of the observer base.
    297296    virtual void build() {
     
    307306    // \brief Clear the map.
    308307    //
    309     // It erase all items from the map. It called by the observer notifier
     308    // It erase all items from the map. It is called by the observer notifier
    310309    // and it overrides the clear() member function of the observer base.
    311310    virtual void clear() {
  • lemon/bits/base_extender.h

    r314 r373  
    3131//\ingroup digraphbits
    3232//\file
    33 //\brief Extenders for the digraph types
     33//\brief Extenders for the graph types
    3434namespace lemon {
    3535
  • lemon/bits/graph_extender.h

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

    r314 r372  
    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>
    221234  struct EdgeNumTagIndicator {
    222235    static const bool value = false;
     
    232245
    233246  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>
    234260  struct FindEdgeTagIndicator {
    235261    static const bool value = false;
  • lemon/bits/vector_map.h

    r314 r373  
    3939  // \brief Graph map based on the std::vector storage.
    4040  //
    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.
     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.
    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 called by the observer notifier
     172    // It adds a new key to the map. It is 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 called by the observer notifier
     183    // It adds more new keys to the map. It is 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 called by the observer notifier
     198    // Erase a key from the map. It is 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     // Erase more keys from the map. It called by the observer notifier
     206    // It erases more keys from the map. It is 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 Buildes the map.
    215     //
    216     // It buildes the map. It called by the observer notifier
     214    // \brief Build the map.
     215    //
     216    // It builds the map. It is 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 erase all items from the map. It called by the observer notifier
     226    // It erases all items from the map. It is 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

    r313 r341  
    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

    r391 r392  
    541541    /// @{
    542542
    543     ///\name Initialization
    544     ///
    545     /// @{
    546 
    547543    /// \brief Default constructor
    548544    ///
     
    693689    }
    694690
    695     /// @}
    696 
    697     ///\name Uniform distributions
    698     ///
    699     /// @{
    700 
    701691    /// \brief Returns a random real number from the range [0, 1)
    702692    ///
     
    753743      return _random_bits::IntConversion<Number, Word>::convert(core);
    754744    }
    755 
    756     /// @}
    757745
    758746    unsigned int uinteger() {
     
    789777    ///\name Non-uniform distributions
    790778    ///
    791 
    792779    ///@{
    793780
    794     /// \brief Returns a random bool
     781    /// \brief Returns a random bool with given probability of true result.
    795782    ///
    796783    /// It returns a random bool with given probability of true result.
     
    799786    }
    800787
    801     /// Standard Gauss distribution
    802 
    803     /// Standard Gauss distribution.
     788    /// Standard normal (Gauss) distribution
     789
     790    /// Standard normal (Gauss) distribution.
    804791    /// \note The Cartesian form of the Box-Muller
    805792    /// transformation is used to generate a random normal distribution.
     
    814801      return std::sqrt(-2*std::log(S)/S)*V1;
    815802    }
    816     /// Gauss distribution with given mean and standard deviation
    817 
    818     /// Gauss distribution with given mean and standard deviation.
     803    /// Normal (Gauss) distribution with given mean and standard deviation
     804
     805    /// Normal (Gauss) distribution with given mean and standard deviation.
    819806    /// \sa gauss()
    820807    double gauss(double mean,double std_dev)
    821808    {
    822809      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));
    823850    }
    824851
     
    926953    ///\name Two dimensional distributions
    927954    ///
    928 
    929955    ///@{
    930956
     
    943969      return dim2::Point<double>(V1,V2);
    944970    }
    945     /// A kind of two dimensional Gauss distribution
     971    /// A kind of two dimensional normal (Gauss) distribution
    946972
    947973    /// This function provides a turning symmetric two-dimensional distribution.
  • lemon/smart_graph.h

    r313 r388  
    6868
    6969    typedef True NodeNumTag;
    70     typedef True EdgeNumTag;
     70    typedef True ArcNumTag;
    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].source=b._id;
     308      for(int i=nodes[b._id].first_out; i!=-1; i=arcs[i].next_out) {
     309        arcs[i].source=b._id;
     310      }
    309311      if(connect) addArc(n,b);
    310312      return b;
     
    465467
    466468    public:
    467       operator Edge() const { 
    468         return _id != -1 ? edgeFromId(_id / 2) : INVALID; 
     469      operator Edge() const {
     470        return _id != -1 ? edgeFromId(_id / 2) : INVALID;
    469471      }
    470472
     
    481483      : nodes(), arcs() {}
    482484
     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(); }
    483492
    484493    int maxNodeId() const { return nodes.size()-1; }
     
    729738        dir.push_back(arcFromId(n-1));
    730739        Parent::notifier(Arc()).erase(dir);
    731         nodes[arcs[n].target].first_out=arcs[n].next_out;
    732         nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
     740        nodes[arcs[n-1].target].first_out=arcs[n].next_out;
     741        nodes[arcs[n].target].first_out=arcs[n-1].next_out;
    733742        arcs.pop_back();
    734743        arcs.pop_back();
  • scripts/chg-len.py

    r284 r390  
    22
    33import sys
    4 import os
     4
     5from mercurial import ui, hg
    56
    67if len(sys.argv)>1 and sys.argv[1] in ["-h","--help"]:
     
    1011"""
    1112    exit(0)
    12 plist = os.popen("HGRCPATH='' hg parents --template='{rev}\n'").readlines()
    13 if len(plist)>1:
    14     print "You are in the process of merging"
    15     exit(1)
    16 PAR = int(plist[0])
    1713
    18 f = os.popen("HGRCPATH='' hg log -r 0:tip --template='{rev} {parents}\n'").\
    19     readlines()
    20 REV = -1
    21 lengths=[]
    22 for 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])
     14u = ui.ui()
     15r = hg.repository(u, ".")
     16N = r.changectx(".").rev()
     17lengths=[0]*(N+1)
     18for i in range(N+1):
     19    p=r.changectx(i).parents()
     20    if p[0]:
     21        p0=lengths[p[0].rev()]
    3322    else:
    34         par1 = int(s[1].split(":")[0])
    35         par2 = int(s[2].split(":")[0])
    36     if rev == 0:
    37         lengths.append(0)
     23        p0=-1
     24    if len(p)>1 and p[1]:
     25        p1=lengths[p[1].rev()]
    3826    else:
    39         lengths.append(max(lengths[par1],lengths[par2])+1)
    40 print lengths[PAR]
     27        p1=-1
     28    lengths[i]=max(p0,p1)+1
     29print lengths[N]
  • scripts/unify-sources.sh

    r208 r411  
    44HGROOT=`hg root`
    55
    6 function update_header() {
     6# file enumaration modes
     7
     8function 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
     14function 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
     20function 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
     35function given_files() {
     36    for file in $GIVEN_FILES
     37    do
     38        echo $file
     39    done
     40}
     41
     42# actions
     43
     44function 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
     54function update_warning() {
     55    echo -n " [$2 warning]"
     56    WARNED=YES
     57}
     58
     59function update_init() {
     60    echo Update source files...
     61    TOTAL_FILES=0
     62    CHANGED_FILES=0
     63    WARNED_FILES=0
     64}
     65
     66function 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
     71function update_begin() {
     72    ((TOTAL_FILES++))
     73    CHANGED=NO
     74    WARNED=NO
     75}
     76
     77function 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
     88function 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
     112function 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
     122function check_init() {
     123    echo Check source files...
     124    FAILED_FILES=0
     125    WARNED_FILES=0
     126    TOTAL_FILES=0
     127}
     128
     129function 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
     156function check_begin() {
     157    ((TOTAL_FILES++))
     158    FAILED=NO
     159    WARNED=NO
     160}
     161
     162function 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
     177function header_check() {
     178    if echo $1 | grep -q -E 'Makefile\.am$'
     179    then
     180        return
     181    fi
     182
    7183    TMP_FILE=`mktemp`
    8     FILE_NAME=$1
    9184
    10185    (echo "/* -*- mode: C++; indent-tabs-mode: nil; -*-
     
    26201 */
    27202"
    28         awk 'BEGIN { pm=0; }
     203    awk 'BEGIN { pm=0; }
    29204     pm==3 { print }
    30205     /\/\* / && pm==0 { pm=1;}
     
    32207     /\*\// && pm==1 { pm=2;}
    33208    ' $1
    34         ) >$TMP_FILE
    35 
    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
    40 }
    41 
    42 function update_tabs() {
     209    ) >$TMP_FILE
     210
     211    "$ACTION"_action "$TMP_FILE" "$1" header
     212}
     213
     214function 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
    43223    TMP_FILE=`mktemp`
    44     FILE_NAME=$1
    45 
    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
    53 }
    54 
    55 function remove_trailing_space() {
     224    cat $1 | sed -e "s/$OLD_PATTERN/$NEW_PATTERN/g" >$TMP_FILE
     225
     226    "$ACTION"_action "$TMP_FILE" "$1" 'tabs'
     227}
     228
     229function spaces_check() {
    56230    TMP_FILE=`mktemp`
    57     FILE_NAME=$1
    58 
    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
    66 }
    67 
    68 function long_line_test() {
    69     cat $1 |grep -q -E '.{81,}'
    70 }
    71 
    72 function 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 ]];
    81     then
    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++))
    104     fi
    105 }
    106 
    107 CHANGED_FILES=0
    108 TOTAL_FILES=0
    109 LONG_LINE_FILES=0
    110 if [ $# == 0 ]; then
    111     echo Update all source files...
    112     for i in `hg manifest|grep -E  '\.(cc|h|dox)$'`
     231    cat $1 | sed -e 's/ \+$//g' >$TMP_FILE
     232
     233    "$ACTION"_action "$TMP_FILE" "$1" 'trailing spaces'
     234}
     235
     236function long_lines_check() {
     237    if cat $1 | grep -q -E '.{81,}'
     238    then
     239        "$ACTION"_warning $1 'long lines'
     240    fi
     241}
     242
     243# process the file
     244
     245function 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
    113257    do
    114         update_file $HGROOT/$i
    115         ((TOTAL_FILES++))
     258        "$check"_check $1
    116259    done
    117     echo '  done.'
    118 else
    119     for i in $*
     260    "$ACTION"_end $1
     261    if [ "$ACTION" == 'update' ]
     262    then
     263        echo
     264    fi
     265}
     266
     267function process_all {
     268    "$ACTION"_init
     269    while read file
    120270    do
    121         update_file $i
    122         ((TOTAL_FILES++))
    123     done
     271        process_file $file
     272    done < <($FILES)
     273    "$ACTION"_done
     274}
     275
     276while [ $# -gt 0 ]
     277do
     278   
     279    if [ "$1" == '--help' ] || [ "$1" == '-h' ]
     280    then
     281        echo -n \
     282"Usage:
     283  $0 [OPTIONS] [files]
     284Options:
     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
     350done
     351
     352if [ -z $FILES ]
     353then
     354    FILES=modified_files
    124355fi
    125 echo $CHANGED_FILES out of $TOTAL_FILES files has been changed.
    126 if [[ $LONG_LINE_FILES -gt 1 ]]; then
    127     echo
    128     echo WARNING: $LONG_LINE_FILES files contains long lines!   
    129     echo
    130 elif [[ $LONG_LINE_FILES -gt 0 ]]; then
    131     echo
    132     echo WARNING: a file contains long lines!
    133     echo
     356
     357if [ -z $ACTION ]
     358then
     359    ACTION=update
    134360fi
     361
     362process_all
  • test/CMakeLists.txt

    r225 r339  
    1717  kruskal_test
    1818  maps_test
     19  max_matching_test
    1920  random_test
    2021  path_test
  • test/Makefile.am

    r228 r404  
    11EXTRA_DIST += \
    2         test/CMakeLists.txt
     2        test/CMakeLists.txt \
     3        test/min_cost_flow_test.lgf \
     4        test/preflow_graph.lgf
    35
    46noinst_HEADERS += \
     
    2022        test/kruskal_test \
    2123        test/maps_test \
     24        test/max_matching_test \
    2225        test/random_test \
    2326        test/path_test \
     27        test/preflow_test \
     28        test/suurballe_test \
    2429        test/test_tools_fail \
    2530        test/test_tools_pass \
     
    4348test_kruskal_test_SOURCES = test/kruskal_test.cc
    4449test_maps_test_SOURCES = test/maps_test.cc
     50test_max_matching_test_SOURCES = test/max_matching_test.cc
    4551test_path_test_SOURCES = test/path_test.cc
     52test_preflow_test_SOURCES = test/preflow_test.cc
     53test_suurballe_test_SOURCES = test/suurballe_test.cc
    4654test_random_test_SOURCES = test/random_test.cc
    4755test_test_tools_fail_SOURCES = test/test_tools_fail.cc
  • test/digraph_test.cc

    r228 r388  
    2020#include <lemon/list_graph.h>
    2121#include <lemon/smart_graph.h>
    22 //#include <lemon/full_graph.h>
    23 //#include <lemon/hypercube_graph.h>
     22#include <lemon/full_graph.h>
    2423
    2524#include "test_tools.h"
     
    3029
    3130template <class Digraph>
    32 void checkDigraph() {
     31void checkDigraphBuild() {
    3332  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    3433  Digraph G;
     
    5958  checkGraphConArcList(G, 1);
    6059
    61   Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
     60  Arc a2 = G.addArc(n2, n1),
     61      a3 = G.addArc(n2, n3),
     62      a4 = G.addArc(n2, n3);
     63
    6264  checkGraphNodeList(G, 3);
    6365  checkGraphArcList(G, 4);
     
    7779  checkGraphNodeMap(G);
    7880  checkGraphArcMap(G);
    79 
    80 }
    81 
     81}
     82
     83template <class Digraph>
     84void 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
     114template <class Digraph>
     115void 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
     193template <class Digraph>
     194void 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
     242template <class Digraph>
     243void 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
     262  checkGraphNodeList(G, 3);
     263  checkGraphArcList(G, 4);
     264
     265  checkGraphOutArcList(G, n1, 1);
     266  checkGraphOutArcList(G, n2, 3);
     267  checkGraphOutArcList(G, n3, 0);
     268
     269  checkGraphInArcList(G, n1, 1);
     270  checkGraphInArcList(G, n2, 1);
     271  checkGraphInArcList(G, n3, 2);
     272
     273  checkGraphConArcList(G, 4);
     274
     275  checkNodeIds(G);
     276  checkArcIds(G);
     277  checkGraphNodeMap(G);
     278  checkGraphArcMap(G);
     279
     280  G.addNode();
     281  snapshot.save(G);
     282
     283  G.addArc(G.addNode(), G.addNode());
     284
     285  snapshot.restore();
     286
     287  checkGraphNodeList(G, 4);
     288  checkGraphArcList(G, 4);
     289}
    82290
    83291void checkConcepts() {
     
    110318    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
    111319  }
    112 //  { // Checking FullDigraph
    113 //    checkConcept<Digraph, FullDigraph>();
    114 //  }
    115 //  { // Checking HyperCubeDigraph
    116 //    checkConcept<Digraph, HyperCubeDigraph>();
    117 //  }
     320  { // Checking FullDigraph
     321    checkConcept<Digraph, FullDigraph>();
     322  }
    118323}
    119324
     
    168373}
    169374
     375void 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
    170407void checkDigraphs() {
    171408  { // Checking ListDigraph
    172     checkDigraph<ListDigraph>();
     409    checkDigraphBuild<ListDigraph>();
     410    checkDigraphSplit<ListDigraph>();
     411    checkDigraphAlter<ListDigraph>();
     412    checkDigraphErase<ListDigraph>();
     413    checkDigraphSnapshot<ListDigraph>();
    173414    checkDigraphValidityErase<ListDigraph>();
    174415  }
    175416  { // Checking SmartDigraph
    176     checkDigraph<SmartDigraph>();
     417    checkDigraphBuild<SmartDigraph>();
     418    checkDigraphSplit<SmartDigraph>();
     419    checkDigraphSnapshot<SmartDigraph>();
    177420    checkDigraphValidity<SmartDigraph>();
     421  }
     422  { // Checking FullDigraph
     423    checkFullDigraph(8);
    178424  }
    179425}
  • test/graph_test.cc

    r228 r388  
    2020#include <lemon/list_graph.h>
    2121#include <lemon/smart_graph.h>
    22 // #include <lemon/full_graph.h>
    23 // #include <lemon/grid_graph.h>
     22#include <lemon/full_graph.h>
     23#include <lemon/grid_graph.h>
     24#include <lemon/hypercube_graph.h>
    2425
    2526#include "test_tools.h"
     
    3031
    3132template <class Graph>
    32 void checkGraph() {
     33void checkGraphBuild() {
    3334  TEMPLATE_GRAPH_TYPEDEFS(Graph);
    3435
     
    3637  checkGraphNodeList(G, 0);
    3738  checkGraphEdgeList(G, 0);
     39  checkGraphArcList(G, 0);
    3840
    3941  Node
     
    4345  checkGraphNodeList(G, 3);
    4446  checkGraphEdgeList(G, 0);
     47  checkGraphArcList(G, 0);
    4548
    4649  Edge e1 = G.addEdge(n1, n2);
    4750  check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
    4851        "Wrong edge");
    49   checkGraphNodeList(G, 3);
     52
     53  checkGraphNodeList(G, 3);
     54  checkGraphEdgeList(G, 1);
    5055  checkGraphArcList(G, 2);
    51   checkGraphEdgeList(G, 1);
    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 
     56
     57  checkGraphIncEdgeArcLists(G, n1, 1);
     58  checkGraphIncEdgeArcLists(G, n2, 1);
     59  checkGraphIncEdgeArcLists(G, n3, 0);
     60
     61  checkGraphConEdgeList(G, 1);
    6562  checkGraphConArcList(G, 2);
    66   checkGraphConEdgeList(G, 1);
    67 
    68   Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
    69   checkGraphNodeList(G, 3);
     63
     64  Edge e2 = G.addEdge(n2, n1),
     65       e3 = G.addEdge(n2, n3);
     66
     67  checkGraphNodeList(G, 3);
     68  checkGraphEdgeList(G, 3);
    7069  checkGraphArcList(G, 6);
    71   checkGraphEdgeList(G, 3);
    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 
     70
     71  checkGraphIncEdgeArcLists(G, n1, 2);
     72  checkGraphIncEdgeArcLists(G, n2, 3);
     73  checkGraphIncEdgeArcLists(G, n3, 1);
     74
     75  checkGraphConEdgeList(G, 3);
    8576  checkGraphConArcList(G, 6);
    86   checkGraphConEdgeList(G, 3);
    8777
    8878  checkArcDirections(G);
     
    9686}
    9787
     88template <class Graph>
     89void 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
     167template <class Graph>
     168void 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
     209template <class Graph>
     210void 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
     265void 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
    98312void checkConcepts() {
    99313  { // Checking graph components
     
    125339    checkConcept<ClearableGraphComponent<>, SmartGraph>();
    126340  }
    127 //  { // Checking FullGraph
    128 //    checkConcept<Graph, FullGraph>();
    129 //    checkGraphIterators<FullGraph>();
    130 //  }
    131 //  { // Checking GridGraph
    132 //    checkConcept<Graph, GridGraph>();
    133 //    checkGraphIterators<GridGraph>();
    134 //  }
     341  { // Checking FullGraph
     342    checkConcept<Graph, FullGraph>();
     343  }
     344  { // Checking GridGraph
     345    checkConcept<Graph, GridGraph>();
     346  }
     347  { // Checking HypercubeGraph
     348    checkConcept<Graph, HypercubeGraph>();
     349  }
    135350}
    136351
     
    189404}
    190405
    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 // }
     406void 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
     485void 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}
    234532
    235533void checkGraphs() {
    236534  { // Checking ListGraph
    237     checkGraph<ListGraph>();
     535    checkGraphBuild<ListGraph>();
     536    checkGraphAlter<ListGraph>();
     537    checkGraphErase<ListGraph>();
     538    checkGraphSnapshot<ListGraph>();
    238539    checkGraphValidityErase<ListGraph>();
    239540  }
    240541  { // Checking SmartGraph
    241     checkGraph<SmartGraph>();
     542    checkGraphBuild<SmartGraph>();
     543    checkGraphSnapshot<SmartGraph>();
    242544    checkGraphValidity<SmartGraph>();
    243545  }
    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 //   }
     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  }
    255563}
    256564
  • test/graph_test.h

    r263 r387  
    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);
    117126  }
    118127
  • tools/Makefile.am

    r310 r400  
    11if WANT_TOOLS
    22
    3 bin_PROGRAMS +=
     3bin_PROGRAMS += \
     4        tools/dimacs-to-lgf
     5
    46dist_bin_SCRIPTS += tools/lemon-0.x-to-1.x.sh
    57
    68endif WANT_TOOLS
     9
     10tools_dimacs_to_lgf_SOURCES = tools/dimacs-to-lgf.cc
  • tools/lemon-0.x-to-1.x.sh

    r310 r378  
    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"
    8         exit
     6    echo "Usage:"
     7    echo "  $0 source-file(s)"
     8    exit
    99fi
    1010
    11 TMP=`mktemp`
    12 
    13 sed     -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 
    127 mv $TMP $1
     11for i in $@
     12do
     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
     97done
Note: See TracChangeset for help on using the changeset viewer.