Changes in / [370:00c8843d491d:371:164fe3abc024] in lemon-1.2
- Files:
-
- 10 added
- 24 edited
-
Makefile.am (modified) (1 diff)
-
configure.ac (modified) (3 diffs)
-
doc/CMakeLists.txt (modified) (1 diff)
-
doc/Doxyfile.in (modified) (1 diff)
-
doc/Makefile.am (modified) (1 diff)
-
doc/groups.dox (modified) (2 diffs)
-
doc/images/grid_graph.eps (added)
-
doc/migration.dox (modified) (2 diffs)
-
lemon/Makefile.am (modified) (3 diffs)
-
lemon/bfs.h (modified) (2 diffs)
-
lemon/bits/alteration_notifier.h (modified) (3 diffs)
-
lemon/bits/array_map.h (modified) (8 diffs)
-
lemon/bits/base_extender.h (modified) (1 diff)
-
lemon/bits/graph_extender.h (modified) (1 diff)
-
lemon/bits/traits.h (modified) (2 diffs)
-
lemon/bits/vector_map.h (modified) (7 diffs)
-
lemon/full_graph.h (added)
-
lemon/grid_graph.h (added)
-
lemon/hypercube_graph.h (added)
-
lemon/list_graph.h (modified) (1 diff)
-
lemon/max_matching.h (added)
-
lemon/nauty_reader.h (added)
-
lemon/random.h (modified) (8 diffs)
-
lemon/smart_graph.h (modified) (3 diffs)
-
lemon/suurballe.h (added)
-
scripts/unify-sources.sh (modified) (3 diffs)
-
test/CMakeLists.txt (modified) (1 diff)
-
test/Makefile.am (modified) (3 diffs)
-
test/digraph_test.cc (modified) (4 diffs)
-
test/graph_test.cc (modified) (5 diffs)
-
test/max_matching_test.cc (added)
-
test/min_cost_flow_test.lgf (added)
-
test/suurballe_test.cc (added)
-
tools/lemon-0.x-to-1.x.sh (modified) (1 diff)
Legend:
- Unmodified
- Added
- Removed
-
Makefile.am
r321 r363 1 1 ACLOCAL_AMFLAGS = -I m4 2 3 AM_CXXFLAGS = $(WARNINGCXXFLAGS) 2 4 3 5 AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir) -
configure.ac
r310 r363 19 19 AC_CONFIG_SRCDIR([lemon/list_graph.h]) 20 20 AC_CONFIG_HEADERS([config.h lemon/config.h]) 21 22 lx_cmdline_cxxflags_set=${CXXFLAGS+set}23 21 24 22 dnl Do compilation tests using the C++ compiler. … … 47 45 48 46 dnl Set custom compiler flags when using g++. 49 if test x"$lx_cmdline_cxxflags_set" != x"set" -a"$GXX" = yes -a "$ICC" = no; then50 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"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" 51 49 fi 50 AC_SUBST([WARNINGCXXFLAGS]) 52 51 53 52 dnl Checks for libraries. … … 114 113 echo 115 114 echo C++ compiler.................. : $CXX 116 echo C++ compiles flags............ : $ CXXFLAGS115 echo C++ compiles flags............ : $WARNINGCXXFLAGS $CXXFLAGS 117 116 echo 118 117 #echo GLPK support.................. : $lx_glpk_found -
doc/CMakeLists.txt
r225 r335 14 14 COMMAND rm -rf gen-images 15 15 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 16 17 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 17 18 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 r367 67 67 ENABLED_SECTIONS = 68 68 MAX_INITIALIZER_LINES = 5 69 SHOW_USED_FILES = YES69 SHOW_USED_FILES = NO 70 70 SHOW_DIRECTORIES = YES 71 71 SHOW_FILES = YES -
doc/Makefile.am
r317 r337 15 15 16 16 DOC_EPS_IMAGES18 = \ 17 grid_graph.eps \ 17 18 nodeshape_0.eps \ 18 19 nodeshape_1.eps \ -
doc/groups.dox
r318 r351 465 465 466 466 /** 467 @defgroup lemon_io LEMON Input-Output467 @defgroup lemon_io LEMON Graph Format 468 468 @ingroup io_group 469 469 \brief Reading and writing LEMON Graph Format. … … 480 480 This group describes general \c EPS drawing methods and special 481 481 graph exporting tools. 482 */ 483 484 /** 485 @defgroup nauty_group NAUTY Format 486 @ingroup io_group 487 \brief Read \e Nauty format 488 Tool to read graphs from \e Nauty format data. 482 489 */ 483 490 -
doc/migration.dox
r314 r343 26 26 27 27 Many of these changes adjusted automatically by the 28 <tt> script/lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual28 <tt>lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual 29 29 update are typeset <b>boldface</b>. 30 30 … … 54 54 55 55 \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 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> 59 61 60 62 \section migration-lgf LGF tools -
lemon/Makefile.am
r259 r366 13 13 lemon/random.cc 14 14 15 #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) 15 #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) $(AM_CXXFLAGS) 16 16 #lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS) 17 17 … … 29 29 lemon/dim2.h \ 30 30 lemon/error.h \ 31 lemon/full_graph.h \ 31 32 lemon/graph_to_eps.h \ 33 lemon/grid_graph.h \ 34 lemon/hypercube_graph.h \ 32 35 lemon/kruskal.h \ 33 36 lemon/lgf_reader.h \ … … 36 39 lemon/maps.h \ 37 40 lemon/math.h \ 41 lemon/max_matching.h \ 42 lemon/nauty_reader.h \ 38 43 lemon/path.h \ 39 44 lemon/random.h \ 40 45 lemon/smart_graph.h \ 46 lemon/suurballe.h \ 41 47 lemon/time_measure.h \ 42 48 lemon/tolerance.h \ -
lemon/bfs.h
r301 r329 52 52 ///Instantiates a PredMap. 53 53 54 ///This function instantiates a PredMap. 54 ///This function instantiates a PredMap. 55 55 ///\param g is the digraph, to which we would like to define the 56 56 ///PredMap. … … 81 81 ///The type of the map that indicates which nodes are reached. 82 82 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. 85 84 typedef typename Digraph::template NodeMap<bool> ReachedMap; 86 85 ///Instantiates a ReachedMap. -
lemon/bits/alteration_notifier.h
r314 r361 36 36 // a container. 37 37 // 38 // The simple graph 's can be refered as two containers, onenode container39 // and one edge container. But they are not standard containersthey40 // does not store values directly they are just key continars for more41 // value containers which are thenode and edge maps.42 // 43 // The graph's node and edge sets can be changed as we add or erase38 // 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 44 44 // nodes and edges in the graph. LEMON would like to handle easily 45 45 // that the node and edge maps should contain values for all nodes or 46 46 // edges. If we want to check on every indicing if the map contains 47 47 // the current indicing key that cause a drawback in the performance 48 // in the library. We use another solution we notify all maps about48 // in the library. We use another solution: we notify all maps about 49 49 // an alteration in the graph, which cause only drawback on the 50 50 // alteration of the graph. 51 51 // 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. 56 57 // 57 58 // For the proper functonality of this class, we should notify it 58 // about each alteration in the container. The alterations have four type 59 // a s \e add(), \e erase(), \e build() and \e clear(). The \e add() and60 // \e erase() signalsthat only one or few items added or erased to or61 // from the graph. If all items are erased from the graph or from an empty62 // graph a new graph is buildedthen it can be signaled with the59 // 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 63 64 // clear() and build() members. Important rule that if we erase items 64 // from graph we should first signal the alteration and after that erase65 // from graphs we should first signal the alteration and after that erase 65 66 // them from the container, on the other way on item addition we should 66 67 // first extend the container and just after that signal the alteration. 67 68 // 68 69 // The alteration can be observed with a class inherited from the 69 // \eObserverBase nested class. The signals can be handled with70 // ObserverBase nested class. The signals can be handled with 70 71 // overriding the virtual functions defined in the base class. The 71 72 // observer base can be attached to the notifier with the 72 // \eattach() member and can be detached with detach() function. The73 // attach() member and can be detached with detach() function. The 73 74 // alteration handlers should not call any function which signals 74 75 // an other alteration in the same notifier and should not 75 76 // detach any observer from the notifier. 76 77 // 77 // Alteration observers try to be exception safe. If an \eadd() or78 // a \eclear() function throws an exception then the remaining78 // Alteration observers try to be exception safe. If an add() or 79 // a clear() function throws an exception then the remaining 79 80 // 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 throw82 // exception. Actullay, it can be throw only \ref ImmediateDetach83 // exceptionwhich detach the observer from the notifier.84 // 85 // There are some placewhen the alteration observing is not completly81 // 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 86 87 // reliable. If we want to carry out the node degree in the graph 87 // as in the \ref InDegMap and we use the reverse Edge that cause88 // as in the \ref InDegMap and we use the reverseArc(), then it cause 88 89 // unreliable functionality. Because the alteration observing signals 89 // only erasing and adding but not the reversing it will stores bad90 // degrees. The sub graph adaptors cannot signal the alterations because91 // just a setting in the filter map can modify the graph and this cannot92 // 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. 93 94 // 94 95 // \param _Container The container which is observed. … … 104 105 typedef _Item Item; 105 106 106 // \brief Exception which can be called from \eclear() and107 // \eerase().108 // 109 // From the \e clear() and \eerase() function only this107 // \brief Exception which can be called from clear() and 108 // erase(). 109 // 110 // From the clear() and erase() function only this 110 111 // exception is allowed to throw. The exception immediatly 111 112 // detaches the current observer from the notifier. Because the 112 // \e clear() and \eerase() should not throw other exceptions113 // clear() and erase() should not throw other exceptions 113 114 // it can be used to invalidate the observer. 114 115 struct ImmediateDetach {}; … … 122 123 // The observer interface contains some pure virtual functions 123 124 // 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. 126 126 // 127 127 // The build() and clear() members are to notify the observer -
lemon/bits/array_map.h
r314 r361 37 37 // \brief Graph map based on the array storage. 38 38 // 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. 43 42 // 44 // The template parameters are the Graph the current Item type and43 // The template parameters are the Graph, the current Item type and 45 44 // the Value type of the map. 46 45 template <typename _Graph, typename _Item, typename _Value> … … 48 47 : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase { 49 48 public: 50 // The graph type of the maps.49 // The graph type. 51 50 typedef _Graph Graph; 52 // The item type of the map.51 // The item type. 53 52 typedef _Item Item; 54 53 // The reference map tag. 55 54 typedef True ReferenceMapTag; 56 55 57 // The key type of the map s.56 // The key type of the map. 58 57 typedef _Item Key; 59 58 // The value type of the map. … … 201 200 // \brief Adds a new key to the map. 202 201 // 203 // It adds a new key to the map. It called by the observer notifier202 // It adds a new key to the map. It is called by the observer notifier 204 203 // and it overrides the add() member function of the observer base. 205 204 virtual void add(const Key& key) { … … 229 228 // \brief Adds more new keys to the map. 230 229 // 231 // It adds more new keys to the map. It called by the observer notifier230 // It adds more new keys to the map. It is called by the observer notifier 232 231 // and it overrides the add() member function of the observer base. 233 232 virtual void add(const std::vector<Key>& keys) { … … 273 272 // \brief Erase a key from the map. 274 273 // 275 // Erase a key from the map. It called by the observer notifier274 // Erase a key from the map. It is called by the observer notifier 276 275 // and it overrides the erase() member function of the observer base. 277 276 virtual void erase(const Key& key) { … … 282 281 // \brief Erase more keys from the map. 283 282 // 284 // Erase more keys from the map. It called by the observer notifier283 // Erase more keys from the map. It is called by the observer notifier 285 284 // and it overrides the erase() member function of the observer base. 286 285 virtual void erase(const std::vector<Key>& keys) { … … 291 290 } 292 291 293 // \brief Build es the map.294 // 295 // It build es the map. Itcalled by the observer notifier292 // \brief Builds the map. 293 // 294 // It builds the map. It is called by the observer notifier 296 295 // and it overrides the build() member function of the observer base. 297 296 virtual void build() { … … 307 306 // \brief Clear the map. 308 307 // 309 // It erase all items from the map. It called by the observer notifier308 // It erase all items from the map. It is called by the observer notifier 310 309 // and it overrides the clear() member function of the observer base. 311 310 virtual void clear() { -
lemon/bits/base_extender.h
r314 r361 31 31 //\ingroup digraphbits 32 32 //\file 33 //\brief Extenders for the digraph types33 //\brief Extenders for the graph types 34 34 namespace lemon { 35 35 -
lemon/bits/graph_extender.h
r314 r361 30 30 //\ingroup graphbits 31 31 //\file 32 //\brief Extenders for the digraph types32 //\brief Extenders for the graph types 33 33 namespace lemon { 34 34 35 35 // \ingroup graphbits 36 36 // 37 // \brief Extender for the Digraphs37 // \brief Extender for the digraph implementations 38 38 template <typename Base> 39 39 class DigraphExtender : public Base { -
lemon/bits/traits.h
r314 r360 219 219 220 220 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> 221 234 struct EdgeNumTagIndicator { 222 235 static const bool value = false; … … 232 245 233 246 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> 234 260 struct FindEdgeTagIndicator { 235 261 static const bool value = false; -
lemon/bits/vector_map.h
r314 r361 39 39 // \brief Graph map based on the std::vector storage. 40 40 // 41 // The VectorMap template class is graph map structure what42 // automatically updates the map when a key is added to or erased from43 // the map. This map type uses thestd::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. 44 44 // 45 45 // \tparam _Graph The graph this map is attached to. … … 170 170 // \brief Adds a new key to the map. 171 171 // 172 // It adds a new key to the map. It called by the observer notifier172 // It adds a new key to the map. It is called by the observer notifier 173 173 // and it overrides the add() member function of the observer base. 174 174 virtual void add(const Key& key) { … … 181 181 // \brief Adds more new keys to the map. 182 182 // 183 // It adds more new keys to the map. It called by the observer notifier183 // It adds more new keys to the map. It is called by the observer notifier 184 184 // and it overrides the add() member function of the observer base. 185 185 virtual void add(const std::vector<Key>& keys) { … … 196 196 // \brief Erase a key from the map. 197 197 // 198 // Erase a key from the map. It called by the observer notifier198 // Erase a key from the map. It is called by the observer notifier 199 199 // and it overrides the erase() member function of the observer base. 200 200 virtual void erase(const Key& key) { … … 204 204 // \brief Erase more keys from the map. 205 205 // 206 // Erase more keys from the map. Itcalled by the observer notifier206 // It erases more keys from the map. It is called by the observer notifier 207 207 // and it overrides the erase() member function of the observer base. 208 208 virtual void erase(const std::vector<Key>& keys) { … … 212 212 } 213 213 214 // \brief Build esthe map.215 // 216 // It build es the map. Itcalled by the observer notifier214 // \brief Build the map. 215 // 216 // It builds the map. It is called by the observer notifier 217 217 // and it overrides the build() member function of the observer base. 218 218 virtual void build() { … … 224 224 // \brief Clear the map. 225 225 // 226 // It erase all items from the map. Itcalled by the observer notifier226 // It erases all items from the map. It is called by the observer notifier 227 227 // and it overrides the clear() member function of the observer base. 228 228 virtual void clear() { -
lemon/list_graph.h
r313 r329 841 841 842 842 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; 845 845 } 846 846 -
lemon/random.h
r280 r340 541 541 /// @{ 542 542 543 ///\name Initialization544 ///545 /// @{546 547 543 /// \brief Default constructor 548 544 /// … … 709 705 } 710 706 711 /// @}712 713 ///\name Uniform distributions714 ///715 /// @{716 717 707 /// \brief Returns a random real number from the range [0, 1) 718 708 /// … … 771 761 return _random_bits::IntConversion<Number, Word>::convert(core); 772 762 } 773 774 /// @}775 763 776 764 unsigned int uinteger() { … … 807 795 ///\name Non-uniform distributions 808 796 /// 809 810 797 ///@{ 811 798 812 /// \brief Returns a random bool 799 /// \brief Returns a random bool with given probability of true result. 813 800 /// 814 801 /// It returns a random bool with given probability of true result. … … 817 804 } 818 805 819 /// Standard Gaussdistribution820 821 /// Standard Gaussdistribution.806 /// Standard normal (Gauss) distribution 807 808 /// Standard normal (Gauss) distribution. 822 809 /// \note The Cartesian form of the Box-Muller 823 810 /// transformation is used to generate a random normal distribution. … … 832 819 return std::sqrt(-2*std::log(S)/S)*V1; 833 820 } 834 /// Gaussdistribution with given mean and standard deviation835 836 /// Gaussdistribution with given mean and standard deviation.821 /// Normal (Gauss) distribution with given mean and standard deviation 822 823 /// Normal (Gauss) distribution with given mean and standard deviation. 837 824 /// \sa gauss() 838 825 double gauss(double mean,double std_dev) 839 826 { 840 827 return gauss()*std_dev+mean; 828 } 829 830 /// Lognormal distribution 831 832 /// Lognormal distribution. The parameters are the mean and the standard 833 /// deviation of <tt>exp(X)</tt>. 834 /// 835 double lognormal(double n_mean,double n_std_dev) 836 { 837 return std::exp(gauss(n_mean,n_std_dev)); 838 } 839 /// Lognormal distribution 840 841 /// Lognormal distribution. The parameter is an <tt>std::pair</tt> of 842 /// the mean and the standard deviation of <tt>exp(X)</tt>. 843 /// 844 double lognormal(const std::pair<double,double> ¶ms) 845 { 846 return std::exp(gauss(params.first,params.second)); 847 } 848 /// Compute the lognormal parameters from mean and standard deviation 849 850 /// This function computes the lognormal parameters from mean and 851 /// standard deviation. The return value can direcly be passed to 852 /// lognormal(). 853 std::pair<double,double> lognormalParamsFromMD(double mean, 854 double std_dev) 855 { 856 double fr=std_dev/mean; 857 fr*=fr; 858 double lg=std::log(1+fr); 859 return std::pair<double,double>(std::log(mean)-lg/2.0,std::sqrt(lg)); 860 } 861 /// Lognormal distribution with given mean and standard deviation 862 863 /// Lognormal distribution with given mean and standard deviation. 864 /// 865 double lognormalMD(double mean,double std_dev) 866 { 867 return lognormal(lognormalParamsFromMD(mean,std_dev)); 841 868 } 842 869 … … 944 971 ///\name Two dimensional distributions 945 972 /// 946 947 973 ///@{ 948 974 … … 961 987 return dim2::Point<double>(V1,V2); 962 988 } 963 /// A kind of two dimensional Gaussdistribution989 /// A kind of two dimensional normal (Gauss) distribution 964 990 965 991 /// This function provides a turning symmetric two-dimensional distribution. -
lemon/smart_graph.h
r370 r371 68 68 69 69 typedef True NodeNumTag; 70 typedef True EdgeNumTag;70 typedef True ArcNumTag; 71 71 72 72 int nodeNum() const { return nodes.size(); } … … 467 467 468 468 public: 469 operator Edge() const { 470 return _id != -1 ? edgeFromId(_id / 2) : INVALID; 469 operator Edge() const { 470 return _id != -1 ? edgeFromId(_id / 2) : INVALID; 471 471 } 472 472 … … 483 483 : nodes(), arcs() {} 484 484 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(); } 485 492 486 493 int maxNodeId() const { return nodes.size()-1; } -
scripts/unify-sources.sh
r208 r341 4 4 HGROOT=`hg root` 5 5 6 function update_header() { 6 # file enumaration modes 7 8 function all_files() { 9 hg status -a -m -c | 10 cut -d ' ' -f 2 | grep -E '(\.(cc|h|dox)$|Makefile\.am$)' | 11 while read file; do echo $HGROOT/$file; done 12 } 13 14 function modified_files() { 15 hg status -a -m | 16 cut -d ' ' -f 2 | grep -E '(\.(cc|h|dox)$|Makefile\.am$)' | 17 while read file; do echo $HGROOT/$file; done 18 } 19 20 function changed_files() { 21 { 22 if [ -n "$HG_PARENT1" ] 23 then 24 hg status --rev $HG_PARENT1:$HG_NODE -a -m 25 fi 26 if [ -n "$HG_PARENT2" ] 27 then 28 hg status --rev $HG_PARENT2:$HG_NODE -a -m 29 fi 30 } | cut -d ' ' -f 2 | grep -E '(\.(cc|h|dox)$|Makefile\.am$)' | 31 sort | uniq | 32 while read file; do echo $HGROOT/$file; done 33 } 34 35 function given_files() { 36 for file in $GIVEN_FILES 37 do 38 echo $file 39 done 40 } 41 42 # actions 43 44 function update_action() { 45 if ! diff -q $1 $2 >/dev/null 46 then 47 echo -n " [$3 updated]" 48 rm $2 49 mv $1 $2 50 CHANGED=YES 51 fi 52 } 53 54 function update_warning() { 55 echo -n " [$2 warning]" 56 WARNED=YES 57 } 58 59 function update_init() { 60 echo Update source files... 61 TOTAL_FILES=0 62 CHANGED_FILES=0 63 WARNED_FILES=0 64 } 65 66 function update_done() { 67 echo $CHANGED_FILES out of $TOTAL_FILES files has been changed. 68 echo $WARNED_FILES out of $TOTAL_FILES files triggered warnings. 69 } 70 71 function update_begin() { 72 ((TOTAL_FILES++)) 73 CHANGED=NO 74 WARNED=NO 75 } 76 77 function update_end() { 78 if [ $CHANGED == YES ] 79 then 80 ((++CHANGED_FILES)) 81 fi 82 if [ $WARNED == YES ] 83 then 84 ((++WARNED_FILES)) 85 fi 86 } 87 88 function check_action() { 89 if [ "$3" == 'tabs' ] 90 then 91 PATTERN=$(echo -e '\t') 92 elif [ "$3" == 'trailing spaces' ] 93 then 94 PATTERN='\ +$' 95 else 96 PATTERN='*' 97 fi 98 99 if ! diff -q $1 $2 >/dev/null 100 then 101 if [ "$PATTERN" == '*' ] 102 then 103 diff $1 $2 | grep '^[0-9]' | sed "s|^\(.*\)c.*$|$2:\1: check failed: $3|g" | 104 sed "s/:\([0-9]*\),\([0-9]*\):\(.*\)$/:\1:\3 (until line \2)/g" 105 else 106 grep -n -E "$PATTERN" $2 | sed "s|^\([0-9]*\):.*$|$2:\1: check failed: $3|g" 107 fi 108 FAILED=YES 109 fi 110 } 111 112 function check_warning() { 113 if [ "$2" == 'long lines' ] 114 then 115 grep -n -E '.{81,}' $1 | sed "s|^\([0-9]*\):.*$|$1:\1: warning: $2|g" 116 else 117 echo "$1: warning: $2" 118 fi 119 WARNED=YES 120 } 121 122 function check_init() { 123 echo Check source files... 124 FAILED_FILES=0 125 WARNED_FILES=0 126 TOTAL_FILES=0 127 } 128 129 function check_done() { 130 echo $FAILED_FILES out of $TOTAL_FILES files has been failed. 131 echo $WARNED_FILES out of $TOTAL_FILES files triggered warnings. 132 133 if [ $FAILED_FILES -gt 0 ] 134 then 135 return 1 136 elif [ $WARNED_FILES -gt 0 ] 137 then 138 if [ "$WARNING" == 'INTERACTIVE' ] 139 then 140 echo -n "Are the files with warnings acceptable? (yes/no) " 141 while read answer 142 do 143 if [ "$answer" == 'yes' ] 144 then 145 return 0 146 elif [ "$answer" == 'no' ] 147 then 148 return 1 149 fi 150 echo -n "Are the files with warnings acceptable? (yes/no) " 151 done 152 elif [ "$WARNING" == 'WERROR' ] 153 then 154 return 1 155 fi 156 fi 157 } 158 159 function check_begin() { 160 ((TOTAL_FILES++)) 161 FAILED=NO 162 WARNED=NO 163 } 164 165 function check_end() { 166 if [ $FAILED == YES ] 167 then 168 ((++FAILED_FILES)) 169 fi 170 if [ $WARNED == YES ] 171 then 172 ((++WARNED_FILES)) 173 fi 174 } 175 176 177 178 # checks 179 180 function header_check() { 181 if echo $1 | grep -q -E 'Makefile\.am$' 182 then 183 return 184 fi 185 7 186 TMP_FILE=`mktemp` 8 FILE_NAME=$19 187 10 188 (echo "/* -*- mode: C++; indent-tabs-mode: nil; -*- … … 26 204 */ 27 205 " 28 206 awk 'BEGIN { pm=0; } 29 207 pm==3 { print } 30 208 /\/\* / && pm==0 { pm=1;} … … 32 210 /\*\// && pm==1 { pm=2;} 33 211 ' $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() { 212 ) >$TMP_FILE 213 214 "$ACTION"_action "$TMP_FILE" "$1" header 215 } 216 217 function tabs_check() { 218 if echo $1 | grep -q -v -E 'Makefile\.am$' 219 then 220 OLD_PATTERN=$(echo -e '\t') 221 NEW_PATTERN=' ' 222 else 223 OLD_PATTERN=' ' 224 NEW_PATTERN=$(echo -e '\t') 225 fi 43 226 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() { 227 cat $1 | sed -e "s/$OLD_PATTERN/$NEW_PATTERN/g" >$TMP_FILE 228 229 "$ACTION"_action "$TMP_FILE" "$1" 'tabs' 230 } 231 232 function spaces_check() { 56 233 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)$'` 234 cat $1 | sed -e 's/ \+$//g' >$TMP_FILE 235 236 "$ACTION"_action "$TMP_FILE" "$1" 'trailing spaces' 237 } 238 239 function long_lines_check() { 240 if cat $1 | grep -q -E '.{81,}' 241 then 242 "$ACTION"_warning $1 'long lines' 243 fi 244 } 245 246 # process the file 247 248 function process_file() { 249 if [ "$ACTION" == 'update' ] 250 then 251 echo -n " $ACTION $1..." 252 else 253 echo " $ACTION $1..." 254 fi 255 256 CHECKING="header tabs spaces long_lines" 257 258 "$ACTION"_begin $1 259 for check in $CHECKING 113 260 do 114 update_file $HGROOT/$i 115 ((TOTAL_FILES++)) 261 "$check"_check $1 116 262 done 117 echo ' done.' 118 else 119 for i in $* 263 "$ACTION"_end $1 264 if [ "$ACTION" == 'update' ] 265 then 266 echo 267 fi 268 } 269 270 function process_all { 271 "$ACTION"_init 272 while read file 120 273 do 121 update_file $i 122 ((TOTAL_FILES++)) 123 done 274 process_file $file 275 done < <($FILES) 276 "$ACTION"_done 277 } 278 279 while [ $# -gt 0 ] 280 do 281 282 if [ "$1" == '--help' ] || [ "$1" == '-h' ] 283 then 284 echo -n \ 285 "Usage: 286 $0 [OPTIONS] [files] 287 Options: 288 --dry-run|-n 289 Check the files, but do not modify them. 290 --interactive|-i 291 If --dry-run is specified and the checker emits warnings, 292 then the user is asked if the warnings should be considered 293 errors. 294 --werror|-w 295 Make all warnings into errors. 296 --all|-a 297 Check all source files in the repository. 298 --modified|-m 299 Check only the modified (and new) source files. This option is 300 useful to check the modification before making a commit. 301 --changed|-c 302 Check only the changed source files compared to the parent(s) of 303 the current hg node. This option is useful as hg hook script. 304 To automatically check all your changes before making a commit, 305 add the following section to the appropriate .hg/hgrc file. 306 307 [hooks] 308 pretxncommit.checksources = scripts/unify-sources.sh -c -n -i 309 310 --help|-h 311 Print this help message. 312 files 313 The files to check/unify. If no file names are given, the modified 314 source files will be checked/unified (just like using the 315 --modified|-m option). 316 " 317 exit 0 318 elif [ "$1" == '--dry-run' ] || [ "$1" == '-n' ] 319 then 320 [ -n "$ACTION" ] && echo "Conflicting action options" >&2 && exit 1 321 ACTION=check 322 elif [ "$1" == "--all" ] || [ "$1" == '-a' ] 323 then 324 [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1 325 FILES=all_files 326 elif [ "$1" == "--changed" ] || [ "$1" == '-c' ] 327 then 328 [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1 329 FILES=changed_files 330 elif [ "$1" == "--modified" ] || [ "$1" == '-m' ] 331 then 332 [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1 333 FILES=modified_files 334 elif [ "$1" == "--interactive" ] || [ "$1" == "-i" ] 335 then 336 [ -n "$WARNING" ] && echo "Conflicting warning options" >&2 && exit 1 337 WARNING='INTERACTIVE' 338 elif [ "$1" == "--werror" ] || [ "$1" == "-w" ] 339 then 340 [ -n "$WARNING" ] && echo "Conflicting warning options" >&2 && exit 1 341 WARNING='WERROR' 342 elif [ $(echo x$1 | cut -c 2) == '-' ] 343 then 344 echo "Invalid option $1" >&2 && exit 1 345 else 346 [ -n "$FILES" ] && echo "Invalid option $1" >&2 && exit 1 347 GIVEN_FILES=$@ 348 FILES=given_files 349 break 350 fi 351 352 shift 353 done 354 355 if [ -z $FILES ] 356 then 357 FILES=modified_files 124 358 fi 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 359 360 if [ -z $ACTION ] 361 then 362 ACTION=update 134 363 fi 364 365 process_all -
test/CMakeLists.txt
r225 r327 17 17 kruskal_test 18 18 maps_test 19 max_matching_test 19 20 random_test 20 21 path_test -
test/Makefile.am
r228 r345 1 1 EXTRA_DIST += \ 2 test/CMakeLists.txt 2 test/CMakeLists.txt \ 3 test/min_cost_flow_test.lgf 3 4 4 5 noinst_HEADERS += \ … … 20 21 test/kruskal_test \ 21 22 test/maps_test \ 23 test/max_matching_test \ 22 24 test/random_test \ 23 25 test/path_test \ 26 test/suurballe_test \ 24 27 test/test_tools_fail \ 25 28 test/test_tools_pass \ … … 43 46 test_kruskal_test_SOURCES = test/kruskal_test.cc 44 47 test_maps_test_SOURCES = test/maps_test.cc 48 test_max_matching_test_SOURCES = test/max_matching_test.cc 45 49 test_path_test_SOURCES = test/path_test.cc 50 test_suurballe_test_SOURCES = test/suurballe_test.cc 46 51 test_random_test_SOURCES = test/random_test.cc 47 52 test_test_tools_fail_SOURCES = test/test_tools_fail.cc -
test/digraph_test.cc
r228 r365 20 20 #include <lemon/list_graph.h> 21 21 #include <lemon/smart_graph.h> 22 //#include <lemon/full_graph.h> 23 //#include <lemon/hypercube_graph.h> 22 #include <lemon/full_graph.h> 24 23 25 24 #include "test_tools.h" … … 80 79 } 81 80 81 void checkFullDigraph(int num) { 82 typedef FullDigraph Digraph; 83 DIGRAPH_TYPEDEFS(Digraph); 84 Digraph G(num); 85 86 checkGraphNodeList(G, num); 87 checkGraphArcList(G, num * num); 88 89 for (NodeIt n(G); n != INVALID; ++n) { 90 checkGraphOutArcList(G, n, num); 91 checkGraphInArcList(G, n, num); 92 } 93 94 checkGraphConArcList(G, num * num); 95 96 checkNodeIds(G); 97 checkArcIds(G); 98 checkGraphNodeMap(G); 99 checkGraphArcMap(G); 100 101 for (int i = 0; i < G.nodeNum(); ++i) { 102 check(G.index(G(i)) == i, "Wrong index"); 103 } 104 105 for (NodeIt s(G); s != INVALID; ++s) { 106 for (NodeIt t(G); t != INVALID; ++t) { 107 Arc a = G.arc(s, t); 108 check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup"); 109 } 110 } 111 112 } 82 113 83 114 void checkConcepts() { … … 110 141 checkConcept<ClearableDigraphComponent<>, SmartDigraph>(); 111 142 } 112 // { // Checking FullDigraph 113 // checkConcept<Digraph, FullDigraph>(); 114 // } 115 // { // Checking HyperCubeDigraph 116 // checkConcept<Digraph, HyperCubeDigraph>(); 117 // } 143 { // Checking FullDigraph 144 checkConcept<Digraph, FullDigraph>(); 145 } 118 146 } 119 147 … … 177 205 checkDigraphValidity<SmartDigraph>(); 178 206 } 207 { // Checking FullDigraph 208 checkFullDigraph(8); 209 } 179 210 } 180 211 -
test/graph_test.cc
r228 r365 20 20 #include <lemon/list_graph.h> 21 21 #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> 24 25 25 26 #include "test_tools.h" … … 96 97 } 97 98 99 void checkFullGraph(int num) { 100 typedef FullGraph Graph; 101 GRAPH_TYPEDEFS(Graph); 102 103 Graph G(num); 104 checkGraphNodeList(G, num); 105 checkGraphEdgeList(G, num * (num - 1) / 2); 106 107 for (NodeIt n(G); n != INVALID; ++n) { 108 checkGraphOutArcList(G, n, num - 1); 109 checkGraphInArcList(G, n, num - 1); 110 checkGraphIncEdgeList(G, n, num - 1); 111 } 112 113 checkGraphConArcList(G, num * (num - 1)); 114 checkGraphConEdgeList(G, num * (num - 1) / 2); 115 116 checkArcDirections(G); 117 118 checkNodeIds(G); 119 checkArcIds(G); 120 checkEdgeIds(G); 121 checkGraphNodeMap(G); 122 checkGraphArcMap(G); 123 checkGraphEdgeMap(G); 124 125 126 for (int i = 0; i < G.nodeNum(); ++i) { 127 check(G.index(G(i)) == i, "Wrong index"); 128 } 129 130 for (NodeIt u(G); u != INVALID; ++u) { 131 for (NodeIt v(G); v != INVALID; ++v) { 132 Edge e = G.edge(u, v); 133 Arc a = G.arc(u, v); 134 if (u == v) { 135 check(e == INVALID, "Wrong edge lookup"); 136 check(a == INVALID, "Wrong arc lookup"); 137 } else { 138 check((G.u(e) == u && G.v(e) == v) || 139 (G.u(e) == v && G.v(e) == u), "Wrong edge lookup"); 140 check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup"); 141 } 142 } 143 } 144 } 145 98 146 void checkConcepts() { 99 147 { // Checking graph components … … 125 173 checkConcept<ClearableGraphComponent<>, SmartGraph>(); 126 174 } 127 // { // Checking FullGraph 128 // checkConcept<Graph, FullGraph>(); 129 // checkGraphIterators<FullGraph>(); 130 // } 131 // { // Checking GridGraph 132 // checkConcept<Graph, GridGraph>(); 133 // checkGraphIterators<GridGraph>(); 134 // } 175 { // Checking FullGraph 176 checkConcept<Graph, FullGraph>(); 177 } 178 { // Checking GridGraph 179 checkConcept<Graph, GridGraph>(); 180 } 181 { // Checking HypercubeGraph 182 checkConcept<Graph, HypercubeGraph>(); 183 } 135 184 } 136 185 … … 189 238 } 190 239 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 // } 240 void checkGridGraph(int width, int height) { 241 typedef GridGraph Graph; 242 GRAPH_TYPEDEFS(Graph); 243 Graph G(width, height); 244 245 check(G.width() == width, "Wrong column number"); 246 check(G.height() == height, "Wrong row number"); 247 248 for (int i = 0; i < width; ++i) { 249 for (int j = 0; j < height; ++j) { 250 check(G.col(G(i, j)) == i, "Wrong column"); 251 check(G.row(G(i, j)) == j, "Wrong row"); 252 check(G.pos(G(i, j)).x == i, "Wrong column"); 253 check(G.pos(G(i, j)).y == j, "Wrong row"); 254 } 255 } 256 257 for (int j = 0; j < height; ++j) { 258 for (int i = 0; i < width - 1; ++i) { 259 check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right"); 260 check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right"); 261 } 262 check(G.right(G(width - 1, j)) == INVALID, "Wrong right"); 263 } 264 265 for (int j = 0; j < height; ++j) { 266 for (int i = 1; i < width; ++i) { 267 check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left"); 268 check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left"); 269 } 270 check(G.left(G(0, j)) == INVALID, "Wrong left"); 271 } 272 273 for (int i = 0; i < width; ++i) { 274 for (int j = 0; j < height - 1; ++j) { 275 check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up"); 276 check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up"); 277 } 278 check(G.up(G(i, height - 1)) == INVALID, "Wrong up"); 279 } 280 281 for (int i = 0; i < width; ++i) { 282 for (int j = 1; j < height; ++j) { 283 check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down"); 284 check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down"); 285 } 286 check(G.down(G(i, 0)) == INVALID, "Wrong down"); 287 } 288 289 checkGraphNodeList(G, width * height); 290 checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height); 291 checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height)); 292 293 for (NodeIt n(G); n != INVALID; ++n) { 294 int nb = 4; 295 if (G.col(n) == 0) --nb; 296 if (G.col(n) == width - 1) --nb; 297 if (G.row(n) == 0) --nb; 298 if (G.row(n) == height - 1) --nb; 299 300 checkGraphOutArcList(G, n, nb); 301 checkGraphInArcList(G, n, nb); 302 checkGraphIncEdgeList(G, n, nb); 303 } 304 305 checkArcDirections(G); 306 307 checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height)); 308 checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height); 309 310 checkNodeIds(G); 311 checkArcIds(G); 312 checkEdgeIds(G); 313 checkGraphNodeMap(G); 314 checkGraphArcMap(G); 315 checkGraphEdgeMap(G); 316 317 } 318 319 void checkHypercubeGraph(int dim) { 320 GRAPH_TYPEDEFS(HypercubeGraph); 321 322 HypercubeGraph G(dim); 323 checkGraphNodeList(G, 1 << dim); 324 checkGraphEdgeList(G, dim * (1 << dim-1)); 325 checkGraphArcList(G, dim * (1 << dim)); 326 327 Node n = G.nodeFromId(dim); 328 329 for (NodeIt n(G); n != INVALID; ++n) { 330 checkGraphIncEdgeList(G, n, dim); 331 for (IncEdgeIt e(G, n); e != INVALID; ++e) { 332 check( (G.u(e) == n && 333 G.id(G.v(e)) == G.id(n) ^ (1 << G.dimension(e))) || 334 (G.v(e) == n && 335 G.id(G.u(e)) == G.id(n) ^ (1 << G.dimension(e))), 336 "Wrong edge or wrong dimension"); 337 } 338 339 checkGraphOutArcList(G, n, dim); 340 for (OutArcIt a(G, n); a != INVALID; ++a) { 341 check(G.source(a) == n && 342 G.id(G.target(a)) == G.id(n) ^ (1 << G.dimension(a)), 343 "Wrong arc or wrong dimension"); 344 } 345 346 checkGraphInArcList(G, n, dim); 347 for (InArcIt a(G, n); a != INVALID; ++a) { 348 check(G.target(a) == n && 349 G.id(G.source(a)) == G.id(n) ^ (1 << G.dimension(a)), 350 "Wrong arc or wrong dimension"); 351 } 352 } 353 354 checkGraphConArcList(G, (1 << dim) * dim); 355 checkGraphConEdgeList(G, dim * (1 << dim-1)); 356 357 checkArcDirections(G); 358 359 checkNodeIds(G); 360 checkArcIds(G); 361 checkEdgeIds(G); 362 checkGraphNodeMap(G); 363 checkGraphArcMap(G); 364 checkGraphEdgeMap(G); 365 } 234 366 235 367 void checkGraphs() { … … 242 374 checkGraphValidity<SmartGraph>(); 243 375 } 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 // } 376 { // Checking FullGraph 377 checkFullGraph(7); 378 checkFullGraph(8); 379 } 380 { // Checking GridGraph 381 checkGridGraph(5, 8); 382 checkGridGraph(8, 5); 383 checkGridGraph(5, 5); 384 checkGridGraph(0, 0); 385 checkGridGraph(1, 1); 386 } 387 { // Checking HypercubeGraph 388 checkHypercubeGraph(1); 389 checkHypercubeGraph(2); 390 checkHypercubeGraph(3); 391 checkHypercubeGraph(4); 392 } 255 393 } 256 394 -
tools/lemon-0.x-to-1.x.sh
r310 r366 4 4 5 5 if [ $# -eq 0 -o x$1 = "x-h" -o x$1 = "x-help" -o x$1 = "x--help" ]; then 6 7 echo " $0 source-file"8 6 echo "Usage:" 7 echo " $0 source-file(s)" 8 exit 9 9 fi 10 10 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 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
Note: See TracChangeset
for help on using the changeset viewer.
