Changes in / [383:a8a22a96d495:384:fc6954b4fce4] in lemon-main
- Files:
-
- 1 added
- 20 edited
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/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 -
lemon/Makefile.am
r379 r384 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 … … 33 33 lemon/graph_to_eps.h \ 34 34 lemon/grid_graph.h \ 35 lemon/hypercube_graph.h \ 35 36 lemon/kruskal.h \ 36 37 lemon/lgf_reader.h \ -
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/full_graph.h
r355 r360 307 307 308 308 typedef True NodeNumTag; 309 typedef True ArcNumTag; 309 310 typedef True EdgeNumTag; 310 311 … … 344 345 345 346 typedef True FindEdgeTag; 347 typedef True FindArcTag; 346 348 347 349 Edge findEdge(Node u, Node v, Edge prev = INVALID) const { -
lemon/grid_graph.h
r338 r360 83 83 84 84 typedef True NodeNumTag; 85 typedef True EdgeNumTag; 85 86 typedef True ArcNumTag; 86 87 … … 128 129 129 130 typedef True FindEdgeTag; 131 typedef True FindArcTag; 130 132 131 133 Edge findEdge(Node u, Node v, Edge prev = INVALID) const { -
lemon/nauty_reader.h
r352 r359 39 39 /// general, connected, biconnected, triangle-free, 4-cycle-free, 40 40 /// bipartite and graphs with given edge number and degree 41 /// constraints). This function reads a \e nauty \e graph \e format41 /// constraints). This function reads a \e nauty \e graph6 \e format 42 42 /// line from the given stream and builds it in the given graph. 43 43 /// … … 49 49 /// int num = 0; 50 50 /// SmartGraph graph; 51 /// while (readNauty (graph, std::cin)) {51 /// while (readNautyGraph(graph, std::cin)) { 52 52 /// PlanarityChecking<SmartGraph> pc(graph); 53 53 /// if (pc.run()) ++num; … … 62 62 ///\endcode 63 63 template <typename Graph> 64 std::istream& readNauty (Graph& graph, std::istream& is = std::cin) {64 std::istream& readNautyGraph(Graph& graph, std::istream& is = std::cin) { 65 65 graph.clear(); 66 66 -
lemon/random.h
r340 r378 689 689 } 690 690 691 /// \brief Returns a random real number the range [0, b)692 ///693 /// It returns a random real number from the range [0, b).694 template <typename Number>695 Number real(Number b) {696 return real<Number>() * b;697 }698 699 /// \brief Returns a random real number from the range [a, b)700 ///701 /// It returns a random real number from the range [a, b).702 template <typename Number>703 Number real(Number a, Number b) {704 return real<Number>() * (b - a) + a;705 }706 707 691 /// \brief Returns a random real number from the range [0, 1) 708 692 /// … … 715 699 /// 716 700 /// It returns a random real number from the range [0, b). 717 template <typename Number> 718 Number operator()(Number b) { 719 return real<Number>() * b; 701 double operator()(double b) { 702 return real<double>() * b; 720 703 } 721 704 … … 723 706 /// 724 707 /// It returns a random real number from the range [a, b). 725 template <typename Number> 726 Number operator()(Number a, Number b) { 727 return real<Number>() * (b - a) + a; 708 double operator()(double a, double b) { 709 return real<double>() * (b - a) + a; 728 710 } 729 711 -
lemon/smart_graph.h
r329 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(); } … … 306 306 nodes[b._id].first_out=nodes[n._id].first_out; 307 307 nodes[n._id].first_out=-1; 308 for(int i=nodes[b._id].first_out;i!=-1;i++) arcs[i].source=b._id; 308 for(int i=nodes[b._id].first_out; i!=-1; i=arcs[i].next_out) { 309 arcs[i].source=b._id; 310 } 309 311 if(connect) addArc(n,b); 310 312 return b; … … 481 483 : nodes(), arcs() {} 482 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(); } 483 492 484 493 int maxNodeId() const { return nodes.size()-1; } … … 729 738 dir.push_back(arcFromId(n-1)); 730 739 Parent::notifier(Arc()).erase(dir); 731 nodes[arcs[n ].target].first_out=arcs[n].next_out;732 nodes[arcs[n -1].target].first_out=arcs[n-1].next_out;740 nodes[arcs[n-1].target].first_out=arcs[n].next_out; 741 nodes[arcs[n].target].first_out=arcs[n-1].next_out; 733 742 arcs.pop_back(); 734 743 arcs.pop_back(); -
scripts/chg-len.py
r284 r376 2 2 3 3 import sys 4 import os 4 5 from mercurial import ui, hg 5 6 6 7 if len(sys.argv)>1 and sys.argv[1] in ["-h","--help"]: … … 10 11 """ 11 12 exit(0) 12 plist = os.popen("HGRCPATH='' hg parents --template='{rev}\n'").readlines()13 if len(plist)>1:14 print "You are in the process of merging"15 exit(1)16 PAR = int(plist[0])17 13 18 f = os.popen("HGRCPATH='' hg log -r 0:tip --template='{rev} {parents}\n'").\ 19 readlines() 20 REV = -1 21 lengths=[] 22 for l in f: 23 REV+=1 24 s = l.split() 25 rev = int(s[0]) 26 if REV != rev: 27 print "Something is seriously wrong" 28 exit(1) 29 if len(s) == 1: 30 par1 = par2 = rev - 1 31 elif len(s) == 2: 32 par1 = par2 = int(s[1].split(":")[0]) 14 u = ui.ui() 15 r = hg.repository(u, ".") 16 N = r.changectx(".").rev() 17 lengths=[0]*(N+1) 18 for i in range(N+1): 19 p=r.changectx(i).parents() 20 if p[0]: 21 p0=lengths[p[0].rev()] 33 22 else: 34 par1 = int(s[1].split(":")[0]) 35 par2 = int(s[2].split(":")[0]) 36 if rev == 0: 37 lengths.append(0) 23 p0=-1 24 if len(p)>1 and p[1]: 25 p1=lengths[p[1].rev()] 38 26 else: 39 lengths.append(max(lengths[par1],lengths[par2])+1) 40 print lengths[PAR] 27 p1=-1 28 lengths[i]=max(p0,p1)+1 29 print lengths[N] -
test/digraph_test.cc
r354 r375 21 21 #include <lemon/smart_graph.h> 22 22 #include <lemon/full_graph.h> 23 //#include <lemon/hypercube_graph.h>24 23 25 24 #include "test_tools.h" … … 30 29 31 30 template <class Digraph> 32 void checkDigraph () {31 void checkDigraphBuild() { 33 32 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 34 33 Digraph G; … … 59 58 checkGraphConArcList(G, 1); 60 59 61 Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); 60 Arc a2 = G.addArc(n2, n1), 61 a3 = G.addArc(n2, n3), 62 a4 = G.addArc(n2, n3); 63 62 64 checkGraphNodeList(G, 3); 63 65 checkGraphArcList(G, 4); … … 77 79 checkGraphNodeMap(G); 78 80 checkGraphArcMap(G); 79 80 } 81 82 void checkFullDigraph(int num) { 83 typedef FullDigraph Digraph; 84 DIGRAPH_TYPEDEFS(Digraph); 85 Digraph G(num); 86 87 checkGraphNodeList(G, num); 88 checkGraphArcList(G, num * num); 89 90 for (NodeIt n(G); n != INVALID; ++n) { 91 checkGraphOutArcList(G, n, num); 92 checkGraphInArcList(G, n, num); 93 } 94 95 checkGraphConArcList(G, num * num); 81 } 82 83 template <class Digraph> 84 void checkDigraphSplit() { 85 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 86 87 Digraph G; 88 Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(); 89 Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1), 90 a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); 91 92 Node n4 = G.split(n2); 93 94 check(G.target(OutArcIt(G, n2)) == n4 && 95 G.source(InArcIt(G, n4)) == n2, 96 "Wrong split."); 97 98 checkGraphNodeList(G, 4); 99 checkGraphArcList(G, 5); 100 101 checkGraphOutArcList(G, n1, 1); 102 checkGraphOutArcList(G, n2, 1); 103 checkGraphOutArcList(G, n3, 0); 104 checkGraphOutArcList(G, n4, 3); 105 106 checkGraphInArcList(G, n1, 1); 107 checkGraphInArcList(G, n2, 1); 108 checkGraphInArcList(G, n3, 2); 109 checkGraphInArcList(G, n4, 1); 110 111 checkGraphConArcList(G, 5); 112 } 113 114 template <class Digraph> 115 void checkDigraphAlter() { 116 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 117 118 Digraph G; 119 Node n1 = G.addNode(), n2 = G.addNode(), 120 n3 = G.addNode(), n4 = G.addNode(); 121 Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1), 122 a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3), 123 a5 = G.addArc(n2, n4); 124 125 checkGraphNodeList(G, 4); 126 checkGraphArcList(G, 5); 127 128 // Check changeSource() and changeTarget() 129 G.changeTarget(a4, n1); 130 131 checkGraphNodeList(G, 4); 132 checkGraphArcList(G, 5); 133 134 checkGraphOutArcList(G, n1, 1); 135 checkGraphOutArcList(G, n2, 1); 136 checkGraphOutArcList(G, n3, 0); 137 checkGraphOutArcList(G, n4, 3); 138 139 checkGraphInArcList(G, n1, 2); 140 checkGraphInArcList(G, n2, 1); 141 checkGraphInArcList(G, n3, 1); 142 checkGraphInArcList(G, n4, 1); 143 144 checkGraphConArcList(G, 5); 145 146 G.changeSource(a4, n3); 147 148 checkGraphNodeList(G, 4); 149 checkGraphArcList(G, 5); 150 151 checkGraphOutArcList(G, n1, 1); 152 checkGraphOutArcList(G, n2, 1); 153 checkGraphOutArcList(G, n3, 1); 154 checkGraphOutArcList(G, n4, 2); 155 156 checkGraphInArcList(G, n1, 2); 157 checkGraphInArcList(G, n2, 1); 158 checkGraphInArcList(G, n3, 1); 159 checkGraphInArcList(G, n4, 1); 160 161 checkGraphConArcList(G, 5); 162 163 // Check contract() 164 G.contract(n2, n4, false); 165 166 checkGraphNodeList(G, 3); 167 checkGraphArcList(G, 5); 168 169 checkGraphOutArcList(G, n1, 1); 170 checkGraphOutArcList(G, n2, 3); 171 checkGraphOutArcList(G, n3, 1); 172 173 checkGraphInArcList(G, n1, 2); 174 checkGraphInArcList(G, n2, 2); 175 checkGraphInArcList(G, n3, 1); 176 177 checkGraphConArcList(G, 5); 178 179 G.contract(n2, n1); 180 181 checkGraphNodeList(G, 2); 182 checkGraphArcList(G, 3); 183 184 checkGraphOutArcList(G, n2, 2); 185 checkGraphOutArcList(G, n3, 1); 186 187 checkGraphInArcList(G, n2, 2); 188 checkGraphInArcList(G, n3, 1); 189 190 checkGraphConArcList(G, 3); 191 } 192 193 template <class Digraph> 194 void checkDigraphErase() { 195 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 196 197 Digraph G; 198 Node n1 = G.addNode(), n2 = G.addNode(), 199 n3 = G.addNode(), n4 = G.addNode(); 200 Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1), 201 a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1), 202 a5 = G.addArc(n2, n4); 203 204 // Check arc deletion 205 G.erase(a1); 206 207 checkGraphNodeList(G, 4); 208 checkGraphArcList(G, 4); 209 210 checkGraphOutArcList(G, n1, 0); 211 checkGraphOutArcList(G, n2, 1); 212 checkGraphOutArcList(G, n3, 1); 213 checkGraphOutArcList(G, n4, 2); 214 215 checkGraphInArcList(G, n1, 2); 216 checkGraphInArcList(G, n2, 0); 217 checkGraphInArcList(G, n3, 1); 218 checkGraphInArcList(G, n4, 1); 219 220 checkGraphConArcList(G, 4); 221 222 // Check node deletion 223 G.erase(n4); 224 225 checkGraphNodeList(G, 3); 226 checkGraphArcList(G, 1); 227 228 checkGraphOutArcList(G, n1, 0); 229 checkGraphOutArcList(G, n2, 0); 230 checkGraphOutArcList(G, n3, 1); 231 checkGraphOutArcList(G, n4, 0); 232 233 checkGraphInArcList(G, n1, 1); 234 checkGraphInArcList(G, n2, 0); 235 checkGraphInArcList(G, n3, 0); 236 checkGraphInArcList(G, n4, 0); 237 238 checkGraphConArcList(G, 1); 239 } 240 241 242 template <class Digraph> 243 void checkDigraphSnapshot() { 244 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 245 246 Digraph G; 247 Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(); 248 Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1), 249 a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); 250 251 typename Digraph::Snapshot snapshot(G); 252 253 Node n = G.addNode(); 254 G.addArc(n3, n); 255 G.addArc(n, n3); 256 257 checkGraphNodeList(G, 4); 258 checkGraphArcList(G, 6); 259 260 snapshot.restore(); 261 262 checkGraphNodeList(G, 3); 263 checkGraphArcList(G, 4); 264 265 checkGraphOutArcList(G, n1, 1); 266 checkGraphOutArcList(G, n2, 3); 267 checkGraphOutArcList(G, n3, 0); 268 269 checkGraphInArcList(G, n1, 1); 270 checkGraphInArcList(G, n2, 1); 271 checkGraphInArcList(G, n3, 2); 272 273 checkGraphConArcList(G, 4); 96 274 97 275 checkNodeIds(G); … … 100 278 checkGraphArcMap(G); 101 279 102 for (int i = 0; i < G.nodeNum(); ++i) { 103 check(G.index(G(i)) == i, "Wrong index"); 104 } 105 106 for (NodeIt s(G); s != INVALID; ++s) { 107 for (NodeIt t(G); t != INVALID; ++t) { 108 Arc a = G.arc(s, t); 109 check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup"); 110 } 111 } 112 113 } 114 280 G.addNode(); 281 snapshot.save(G); 282 283 G.addArc(G.addNode(), G.addNode()); 284 285 snapshot.restore(); 286 287 checkGraphNodeList(G, 4); 288 checkGraphArcList(G, 4); 289 } 115 290 116 291 void checkConcepts() { … … 146 321 checkConcept<Digraph, FullDigraph>(); 147 322 } 148 // { // Checking HyperCubeDigraph149 // checkConcept<Digraph, HyperCubeDigraph>();150 // }151 323 } 152 324 … … 201 373 } 202 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 } 405 } 406 203 407 void checkDigraphs() { 204 408 { // Checking ListDigraph 205 checkDigraph<ListDigraph>(); 409 checkDigraphBuild<ListDigraph>(); 410 checkDigraphSplit<ListDigraph>(); 411 checkDigraphAlter<ListDigraph>(); 412 checkDigraphErase<ListDigraph>(); 413 checkDigraphSnapshot<ListDigraph>(); 206 414 checkDigraphValidityErase<ListDigraph>(); 207 415 } 208 416 { // Checking SmartDigraph 209 checkDigraph<SmartDigraph>(); 417 checkDigraphBuild<SmartDigraph>(); 418 checkDigraphSplit<SmartDigraph>(); 419 checkDigraphSnapshot<SmartDigraph>(); 210 420 checkDigraphValidity<SmartDigraph>(); 211 421 } -
test/graph_test.cc
r356 r375 22 22 #include <lemon/full_graph.h> 23 23 #include <lemon/grid_graph.h> 24 #include <lemon/hypercube_graph.h> 24 25 25 26 #include "test_tools.h" … … 30 31 31 32 template <class Graph> 32 void checkGraph () {33 void checkGraphBuild() { 33 34 TEMPLATE_GRAPH_TYPEDEFS(Graph); 34 35 … … 36 37 checkGraphNodeList(G, 0); 37 38 checkGraphEdgeList(G, 0); 39 checkGraphArcList(G, 0); 38 40 39 41 Node … … 43 45 checkGraphNodeList(G, 3); 44 46 checkGraphEdgeList(G, 0); 47 checkGraphArcList(G, 0); 45 48 46 49 Edge e1 = G.addEdge(n1, n2); 47 50 check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1), 48 51 "Wrong edge"); 49 checkGraphNodeList(G, 3); 52 53 checkGraphNodeList(G, 3); 54 checkGraphEdgeList(G, 1); 50 55 checkGraphArcList(G, 2); 51 checkGraphEdgeList(G, 1); 52 53 checkGraphOutArcList(G, n1, 1); 54 checkGraphOutArcList(G, n2, 1); 55 checkGraphOutArcList(G, n3, 0); 56 57 checkGraphInArcList(G, n1, 1); 58 checkGraphInArcList(G, n2, 1); 59 checkGraphInArcList(G, n3, 0); 60 61 checkGraphIncEdgeList(G, n1, 1); 62 checkGraphIncEdgeList(G, n2, 1); 63 checkGraphIncEdgeList(G, n3, 0); 64 56 57 checkGraphIncEdgeArcLists(G, n1, 1); 58 checkGraphIncEdgeArcLists(G, n2, 1); 59 checkGraphIncEdgeArcLists(G, n3, 0); 60 61 checkGraphConEdgeList(G, 1); 65 62 checkGraphConArcList(G, 2); 66 checkGraphConEdgeList(G, 1); 67 68 Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3); 69 checkGraphNodeList(G, 3); 63 64 Edge e2 = G.addEdge(n2, n1), 65 e3 = G.addEdge(n2, n3); 66 67 checkGraphNodeList(G, 3); 68 checkGraphEdgeList(G, 3); 70 69 checkGraphArcList(G, 6); 71 checkGraphEdgeList(G, 3); 72 73 checkGraphOutArcList(G, n1, 2); 74 checkGraphOutArcList(G, n2, 3); 75 checkGraphOutArcList(G, n3, 1); 76 77 checkGraphInArcList(G, n1, 2); 78 checkGraphInArcList(G, n2, 3); 79 checkGraphInArcList(G, n3, 1); 80 81 checkGraphIncEdgeList(G, n1, 2); 82 checkGraphIncEdgeList(G, n2, 3); 83 checkGraphIncEdgeList(G, n3, 1); 84 70 71 checkGraphIncEdgeArcLists(G, n1, 2); 72 checkGraphIncEdgeArcLists(G, n2, 3); 73 checkGraphIncEdgeArcLists(G, n3, 1); 74 75 checkGraphConEdgeList(G, 3); 85 76 checkGraphConArcList(G, 6); 86 checkGraphConEdgeList(G, 3);87 77 88 78 checkArcDirections(G); … … 96 86 } 97 87 88 template <class Graph> 89 void checkGraphAlter() { 90 TEMPLATE_GRAPH_TYPEDEFS(Graph); 91 92 Graph G; 93 Node n1 = G.addNode(), n2 = G.addNode(), 94 n3 = G.addNode(), n4 = G.addNode(); 95 Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1), 96 e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4), 97 e5 = G.addEdge(n4, n3); 98 99 checkGraphNodeList(G, 4); 100 checkGraphEdgeList(G, 5); 101 checkGraphArcList(G, 10); 102 103 // Check changeU() and changeV() 104 if (G.u(e2) == n2) { 105 G.changeU(e2, n3); 106 } else { 107 G.changeV(e2, n3); 108 } 109 110 checkGraphNodeList(G, 4); 111 checkGraphEdgeList(G, 5); 112 checkGraphArcList(G, 10); 113 114 checkGraphIncEdgeArcLists(G, n1, 3); 115 checkGraphIncEdgeArcLists(G, n2, 2); 116 checkGraphIncEdgeArcLists(G, n3, 3); 117 checkGraphIncEdgeArcLists(G, n4, 2); 118 119 checkGraphConEdgeList(G, 5); 120 checkGraphConArcList(G, 10); 121 122 if (G.u(e2) == n1) { 123 G.changeU(e2, n2); 124 } else { 125 G.changeV(e2, n2); 126 } 127 128 checkGraphNodeList(G, 4); 129 checkGraphEdgeList(G, 5); 130 checkGraphArcList(G, 10); 131 132 checkGraphIncEdgeArcLists(G, n1, 2); 133 checkGraphIncEdgeArcLists(G, n2, 3); 134 checkGraphIncEdgeArcLists(G, n3, 3); 135 checkGraphIncEdgeArcLists(G, n4, 2); 136 137 checkGraphConEdgeList(G, 5); 138 checkGraphConArcList(G, 10); 139 140 // Check contract() 141 G.contract(n1, n4, false); 142 143 checkGraphNodeList(G, 3); 144 checkGraphEdgeList(G, 5); 145 checkGraphArcList(G, 10); 146 147 checkGraphIncEdgeArcLists(G, n1, 4); 148 checkGraphIncEdgeArcLists(G, n2, 3); 149 checkGraphIncEdgeArcLists(G, n3, 3); 150 151 checkGraphConEdgeList(G, 5); 152 checkGraphConArcList(G, 10); 153 154 G.contract(n2, n3); 155 156 checkGraphNodeList(G, 2); 157 checkGraphEdgeList(G, 3); 158 checkGraphArcList(G, 6); 159 160 checkGraphIncEdgeArcLists(G, n1, 4); 161 checkGraphIncEdgeArcLists(G, n2, 2); 162 163 checkGraphConEdgeList(G, 3); 164 checkGraphConArcList(G, 6); 165 } 166 167 template <class Graph> 168 void checkGraphErase() { 169 TEMPLATE_GRAPH_TYPEDEFS(Graph); 170 171 Graph G; 172 Node n1 = G.addNode(), n2 = G.addNode(), 173 n3 = G.addNode(), n4 = G.addNode(); 174 Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1), 175 e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4), 176 e5 = G.addEdge(n4, n3); 177 178 // Check edge deletion 179 G.erase(e2); 180 181 checkGraphNodeList(G, 4); 182 checkGraphEdgeList(G, 4); 183 checkGraphArcList(G, 8); 184 185 checkGraphIncEdgeArcLists(G, n1, 2); 186 checkGraphIncEdgeArcLists(G, n2, 2); 187 checkGraphIncEdgeArcLists(G, n3, 2); 188 checkGraphIncEdgeArcLists(G, n4, 2); 189 190 checkGraphConEdgeList(G, 4); 191 checkGraphConArcList(G, 8); 192 193 // Check node deletion 194 G.erase(n3); 195 196 checkGraphNodeList(G, 3); 197 checkGraphEdgeList(G, 2); 198 checkGraphArcList(G, 4); 199 200 checkGraphIncEdgeArcLists(G, n1, 2); 201 checkGraphIncEdgeArcLists(G, n2, 1); 202 checkGraphIncEdgeArcLists(G, n4, 1); 203 204 checkGraphConEdgeList(G, 2); 205 checkGraphConArcList(G, 4); 206 } 207 208 209 template <class Graph> 210 void checkGraphSnapshot() { 211 TEMPLATE_GRAPH_TYPEDEFS(Graph); 212 213 Graph G; 214 Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(); 215 Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1), 216 e3 = G.addEdge(n2, n3); 217 218 checkGraphNodeList(G, 3); 219 checkGraphEdgeList(G, 3); 220 checkGraphArcList(G, 6); 221 222 typename Graph::Snapshot snapshot(G); 223 224 Node n = G.addNode(); 225 G.addEdge(n3, n); 226 G.addEdge(n, n3); 227 G.addEdge(n3, n2); 228 229 checkGraphNodeList(G, 4); 230 checkGraphEdgeList(G, 6); 231 checkGraphArcList(G, 12); 232 233 snapshot.restore(); 234 235 checkGraphNodeList(G, 3); 236 checkGraphEdgeList(G, 3); 237 checkGraphArcList(G, 6); 238 239 checkGraphIncEdgeArcLists(G, n1, 2); 240 checkGraphIncEdgeArcLists(G, n2, 3); 241 checkGraphIncEdgeArcLists(G, n3, 1); 242 243 checkGraphConEdgeList(G, 3); 244 checkGraphConArcList(G, 6); 245 246 checkNodeIds(G); 247 checkEdgeIds(G); 248 checkArcIds(G); 249 checkGraphNodeMap(G); 250 checkGraphEdgeMap(G); 251 checkGraphArcMap(G); 252 253 G.addNode(); 254 snapshot.save(G); 255 256 G.addEdge(G.addNode(), G.addNode()); 257 258 snapshot.restore(); 259 260 checkGraphNodeList(G, 4); 261 checkGraphEdgeList(G, 3); 262 checkGraphArcList(G, 6); 263 } 264 98 265 void checkFullGraph(int num) { 99 266 typedef FullGraph Graph; … … 105 272 106 273 for (NodeIt n(G); n != INVALID; ++n) { 107 checkGraphOutArcList(G, n, num - 1); 108 checkGraphInArcList(G, n, num - 1); 109 checkGraphIncEdgeList(G, n, num - 1); 274 checkGraphOutArcList(G, n, num - 1); 275 checkGraphInArcList(G, n, num - 1); 276 checkGraphIncEdgeList(G, n, num - 1); 110 277 } 111 278 … … 122 289 checkGraphEdgeMap(G); 123 290 124 291 125 292 for (int i = 0; i < G.nodeNum(); ++i) { 126 293 check(G.index(G(i)) == i, "Wrong index"); … … 178 345 checkConcept<Graph, GridGraph>(); 179 346 } 347 { // Checking HypercubeGraph 348 checkConcept<Graph, HypercubeGraph>(); 349 } 180 350 } 181 351 … … 313 483 } 314 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 } 532 315 533 void checkGraphs() { 316 534 { // Checking ListGraph 317 checkGraph<ListGraph>(); 535 checkGraphBuild<ListGraph>(); 536 checkGraphAlter<ListGraph>(); 537 checkGraphErase<ListGraph>(); 538 checkGraphSnapshot<ListGraph>(); 318 539 checkGraphValidityErase<ListGraph>(); 319 540 } 320 541 { // Checking SmartGraph 321 checkGraph<SmartGraph>(); 542 checkGraphBuild<SmartGraph>(); 543 checkGraphSnapshot<SmartGraph>(); 322 544 checkGraphValidity<SmartGraph>(); 323 545 } 324 { // Checking FullGraph 546 { // Checking FullGraph 325 547 checkFullGraph(7); 326 548 checkFullGraph(8); … … 333 555 checkGridGraph(1, 1); 334 556 } 557 { // Checking HypercubeGraph 558 checkHypercubeGraph(1); 559 checkHypercubeGraph(2); 560 checkHypercubeGraph(3); 561 checkHypercubeGraph(4); 562 } 335 563 } 336 564 -
test/graph_test.h
r263 r374 115 115 check(e==INVALID,"Wrong IncEdge list linking."); 116 116 check(countIncEdges(G,n)==cnt,"Wrong IncEdge number."); 117 } 118 119 template <class Graph> 120 void checkGraphIncEdgeArcLists(const Graph &G, typename Graph::Node n, 121 int cnt) 122 { 123 checkGraphIncEdgeList(G, n, cnt); 124 checkGraphOutArcList(G, n, cnt); 125 checkGraphInArcList(G, n, cnt); 117 126 } 118 127 -
tools/lemon-0.x-to-1.x.sh
r344 r366 82 82 -e "s/\<copyGraph\>/graphCopy/g"\ 83 83 -e "s/\<copyDigraph\>/digraphCopy/g"\ 84 -e "s/\<HyperCubeDigraph\>/HypercubeGraph/g"\ 84 85 -e "s/\<IntegerMap\>/RangeMap/g"\ 85 86 -e "s/\<integerMap\>/rangeMap/g"\ … … 91 92 -e "s/\<storeBoolMap\>/loggerBoolMap/g"\ 92 93 -e "s/\<BoundingBox\>/Box/g"\ 94 -e "s/\<readNauty\>/readNautyGraph/g"\ 93 95 <$i > $TMP 94 96 mv $TMP $i
Note: See TracChangeset
for help on using the changeset viewer.