Changes in / [374:49d9a36b3b84:375:2d87dbd7f8c8] in lemon-main
- 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
r373 r375 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
r374 r375 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" … … 319 318 checkConcept<ClearableDigraphComponent<>, SmartDigraph>(); 320 319 } 321 // { // Checking FullDigraph 322 // checkConcept<Digraph, FullDigraph>(); 323 // } 324 // { // Checking HyperCubeDigraph 325 // checkConcept<Digraph, HyperCubeDigraph>(); 326 // } 320 { // Checking FullDigraph 321 checkConcept<Digraph, FullDigraph>(); 322 } 327 323 } 328 324 … … 375 371 check(!g.valid(g.nodeFromId(-1)), "Wrong validity check"); 376 372 check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); 373 } 374 375 void checkFullDigraph(int num) { 376 typedef FullDigraph Digraph; 377 DIGRAPH_TYPEDEFS(Digraph); 378 Digraph G(num); 379 380 checkGraphNodeList(G, num); 381 checkGraphArcList(G, num * num); 382 383 for (NodeIt n(G); n != INVALID; ++n) { 384 checkGraphOutArcList(G, n, num); 385 checkGraphInArcList(G, n, num); 386 } 387 388 checkGraphConArcList(G, num * num); 389 390 checkNodeIds(G); 391 checkArcIds(G); 392 checkGraphNodeMap(G); 393 checkGraphArcMap(G); 394 395 for (int i = 0; i < G.nodeNum(); ++i) { 396 check(G.index(G(i)) == i, "Wrong index"); 397 } 398 399 for (NodeIt s(G); s != INVALID; ++s) { 400 for (NodeIt t(G); t != INVALID; ++t) { 401 Arc a = G.arc(s, t); 402 check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup"); 403 } 404 } 377 405 } 378 406 … … 392 420 checkDigraphValidity<SmartDigraph>(); 393 421 } 422 { // Checking FullDigraph 423 checkFullDigraph(8); 424 } 394 425 } 395 426 -
test/graph_test.cc
r374 r375 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" … … 262 263 } 263 264 265 void checkFullGraph(int num) { 266 typedef FullGraph Graph; 267 GRAPH_TYPEDEFS(Graph); 268 269 Graph G(num); 270 checkGraphNodeList(G, num); 271 checkGraphEdgeList(G, num * (num - 1) / 2); 272 273 for (NodeIt n(G); n != INVALID; ++n) { 274 checkGraphOutArcList(G, n, num - 1); 275 checkGraphInArcList(G, n, num - 1); 276 checkGraphIncEdgeList(G, n, num - 1); 277 } 278 279 checkGraphConArcList(G, num * (num - 1)); 280 checkGraphConEdgeList(G, num * (num - 1) / 2); 281 282 checkArcDirections(G); 283 284 checkNodeIds(G); 285 checkArcIds(G); 286 checkEdgeIds(G); 287 checkGraphNodeMap(G); 288 checkGraphArcMap(G); 289 checkGraphEdgeMap(G); 290 291 292 for (int i = 0; i < G.nodeNum(); ++i) { 293 check(G.index(G(i)) == i, "Wrong index"); 294 } 295 296 for (NodeIt u(G); u != INVALID; ++u) { 297 for (NodeIt v(G); v != INVALID; ++v) { 298 Edge e = G.edge(u, v); 299 Arc a = G.arc(u, v); 300 if (u == v) { 301 check(e == INVALID, "Wrong edge lookup"); 302 check(a == INVALID, "Wrong arc lookup"); 303 } else { 304 check((G.u(e) == u && G.v(e) == v) || 305 (G.u(e) == v && G.v(e) == u), "Wrong edge lookup"); 306 check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup"); 307 } 308 } 309 } 310 } 311 264 312 void checkConcepts() { 265 313 { // Checking graph components … … 291 339 checkConcept<ClearableGraphComponent<>, SmartGraph>(); 292 340 } 293 // { // Checking FullGraph 294 // checkConcept<Graph, FullGraph>(); 295 // checkGraphIterators<FullGraph>(); 296 // } 297 // { // Checking GridGraph 298 // checkConcept<Graph, GridGraph>(); 299 // checkGraphIterators<GridGraph>(); 300 // } 341 { // Checking FullGraph 342 checkConcept<Graph, FullGraph>(); 343 } 344 { // Checking GridGraph 345 checkConcept<Graph, GridGraph>(); 346 } 347 { // Checking HypercubeGraph 348 checkConcept<Graph, HypercubeGraph>(); 349 } 301 350 } 302 351 … … 355 404 } 356 405 357 // void checkGridGraph(const GridGraph& g, int w, int h) { 358 // check(g.width() == w, "Wrong width"); 359 // check(g.height() == h, "Wrong height"); 360 361 // for (int i = 0; i < w; ++i) { 362 // for (int j = 0; j < h; ++j) { 363 // check(g.col(g(i, j)) == i, "Wrong col"); 364 // check(g.row(g(i, j)) == j, "Wrong row"); 365 // } 366 // } 367 368 // for (int i = 0; i < w; ++i) { 369 // for (int j = 0; j < h - 1; ++j) { 370 // check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down"); 371 // check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down"); 372 // } 373 // check(g.down(g(i, h - 1)) == INVALID, "Wrong down"); 374 // } 375 376 // for (int i = 0; i < w; ++i) { 377 // for (int j = 1; j < h; ++j) { 378 // check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up"); 379 // check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up"); 380 // } 381 // check(g.up(g(i, 0)) == INVALID, "Wrong up"); 382 // } 383 384 // for (int j = 0; j < h; ++j) { 385 // for (int i = 0; i < w - 1; ++i) { 386 // check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right"); 387 // check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right"); 388 // } 389 // check(g.right(g(w - 1, j)) == INVALID, "Wrong right"); 390 // } 391 392 // for (int j = 0; j < h; ++j) { 393 // for (int i = 1; i < w; ++i) { 394 // check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left"); 395 // check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left"); 396 // } 397 // check(g.left(g(0, j)) == INVALID, "Wrong left"); 398 // } 399 // } 406 void checkGridGraph(int width, int height) { 407 typedef GridGraph Graph; 408 GRAPH_TYPEDEFS(Graph); 409 Graph G(width, height); 410 411 check(G.width() == width, "Wrong column number"); 412 check(G.height() == height, "Wrong row number"); 413 414 for (int i = 0; i < width; ++i) { 415 for (int j = 0; j < height; ++j) { 416 check(G.col(G(i, j)) == i, "Wrong column"); 417 check(G.row(G(i, j)) == j, "Wrong row"); 418 check(G.pos(G(i, j)).x == i, "Wrong column"); 419 check(G.pos(G(i, j)).y == j, "Wrong row"); 420 } 421 } 422 423 for (int j = 0; j < height; ++j) { 424 for (int i = 0; i < width - 1; ++i) { 425 check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right"); 426 check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right"); 427 } 428 check(G.right(G(width - 1, j)) == INVALID, "Wrong right"); 429 } 430 431 for (int j = 0; j < height; ++j) { 432 for (int i = 1; i < width; ++i) { 433 check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left"); 434 check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left"); 435 } 436 check(G.left(G(0, j)) == INVALID, "Wrong left"); 437 } 438 439 for (int i = 0; i < width; ++i) { 440 for (int j = 0; j < height - 1; ++j) { 441 check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up"); 442 check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up"); 443 } 444 check(G.up(G(i, height - 1)) == INVALID, "Wrong up"); 445 } 446 447 for (int i = 0; i < width; ++i) { 448 for (int j = 1; j < height; ++j) { 449 check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down"); 450 check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down"); 451 } 452 check(G.down(G(i, 0)) == INVALID, "Wrong down"); 453 } 454 455 checkGraphNodeList(G, width * height); 456 checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height); 457 checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height)); 458 459 for (NodeIt n(G); n != INVALID; ++n) { 460 int nb = 4; 461 if (G.col(n) == 0) --nb; 462 if (G.col(n) == width - 1) --nb; 463 if (G.row(n) == 0) --nb; 464 if (G.row(n) == height - 1) --nb; 465 466 checkGraphOutArcList(G, n, nb); 467 checkGraphInArcList(G, n, nb); 468 checkGraphIncEdgeList(G, n, nb); 469 } 470 471 checkArcDirections(G); 472 473 checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height)); 474 checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height); 475 476 checkNodeIds(G); 477 checkArcIds(G); 478 checkEdgeIds(G); 479 checkGraphNodeMap(G); 480 checkGraphArcMap(G); 481 checkGraphEdgeMap(G); 482 483 } 484 485 void checkHypercubeGraph(int dim) { 486 GRAPH_TYPEDEFS(HypercubeGraph); 487 488 HypercubeGraph G(dim); 489 checkGraphNodeList(G, 1 << dim); 490 checkGraphEdgeList(G, dim * (1 << (dim-1))); 491 checkGraphArcList(G, dim * (1 << dim)); 492 493 Node n = G.nodeFromId(dim); 494 495 for (NodeIt n(G); n != INVALID; ++n) { 496 checkGraphIncEdgeList(G, n, dim); 497 for (IncEdgeIt e(G, n); e != INVALID; ++e) { 498 check( (G.u(e) == n && 499 G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) || 500 (G.v(e) == n && 501 G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))), 502 "Wrong edge or wrong dimension"); 503 } 504 505 checkGraphOutArcList(G, n, dim); 506 for (OutArcIt a(G, n); a != INVALID; ++a) { 507 check(G.source(a) == n && 508 G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))), 509 "Wrong arc or wrong dimension"); 510 } 511 512 checkGraphInArcList(G, n, dim); 513 for (InArcIt a(G, n); a != INVALID; ++a) { 514 check(G.target(a) == n && 515 G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))), 516 "Wrong arc or wrong dimension"); 517 } 518 } 519 520 checkGraphConArcList(G, (1 << dim) * dim); 521 checkGraphConEdgeList(G, dim * (1 << (dim-1))); 522 523 checkArcDirections(G); 524 525 checkNodeIds(G); 526 checkArcIds(G); 527 checkEdgeIds(G); 528 checkGraphNodeMap(G); 529 checkGraphArcMap(G); 530 checkGraphEdgeMap(G); 531 } 400 532 401 533 void checkGraphs() { … … 412 544 checkGraphValidity<SmartGraph>(); 413 545 } 414 // { // Checking FullGraph 415 // FullGraph g(5); 416 // checkGraphNodeList(g, 5); 417 // checkGraphEdgeList(g, 10); 418 // } 419 // { // Checking GridGraph 420 // GridGraph g(5, 6); 421 // checkGraphNodeList(g, 30); 422 // checkGraphEdgeList(g, 49); 423 // checkGridGraph(g, 5, 6); 424 // } 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 } 425 563 } 426 564 -
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.
