Changes in / [67:9de02aa380de:65:bfbc57a51fbb] in lemon
- Files:
-
- 25 deleted
- 21 edited
Legend:
- Unmodified
- Added
- Removed
-
configure.ac
r64 r21 3 3 dnl Version information. 4 4 m4_define([lemon_version_major], [0]) 5 m4_define([lemon_version_minor], [ 99])6 m4_define([lemon_version_micro], [ ])5 m4_define([lemon_version_minor], [6]) 6 m4_define([lemon_version_micro], [90]) 7 7 m4_define([lemon_version_nano], []) 8 8 m4_define([lemon_version_tag], [hg]) … … 14 14 AC_CONFIG_AUX_DIR([build-aux]) 15 15 AC_CONFIG_MACRO_DIR([m4]) 16 AM_INIT_AUTOMAKE([-Wall -Werror foreign subdir-objects nostdinc])16 AM_INIT_AUTOMAKE([-Wall -Werror foreign subdir-objects]) 17 17 AC_CONFIG_SRCDIR([lemon/list_graph.h]) 18 18 AC_CONFIG_HEADERS([config.h lemon/config.h]) … … 27 27 AC_PROG_LIBTOOL 28 28 29 AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])30 31 29 if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes; then 32 30 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" 33 31 fi 32 33 AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no]) 34 34 35 35 dnl Checks for libraries. … … 37 37 LX_CHECK_CPLEX 38 38 LX_CHECK_SOPLEX 39 40 dnl Enable/disable installing the documentation 41 AC_ARG_ENABLE([doc], 42 AS_HELP_STRING([--enable-doc@<:@=yes|no|full@:>@], [build the documentation (full enables internal documentation too) @<:@default=yes@:>@]) 43 AS_HELP_STRING([--disable-doc], [do not build the documentation]), 44 [], [enable_doc=yes]) 45 46 AC_MSG_CHECKING([whether to build the documention]) 47 case "$enable_doc" in 48 yes) 49 DOXYGEN_INTERNAL_DOCS=NO 50 AC_MSG_RESULT([yes]) 51 ;; 52 full) 53 DOXYGEN_INTERNAL_DOCS=YES 54 AC_MSG_RESULT([full]) 55 ;; 56 no) 57 DOXYGEN_INTERNAL_DOCS=NO 58 AC_MSG_RESULT([no]) 59 ;; 60 *) 61 AC_MSG_ERROR([bad value $enable_doc for option --enable-doc]) 62 ;; 63 esac 64 AC_SUBST(DOXYGEN_INTERNAL_DOCS) 65 AM_CONDITIONAL([WANT_DOC], [test x"$enable_doc" != x"no"]) 39 66 40 67 dnl Disable/enable building the demo programs … … 111 138 echo SOPLEX support................ : $lx_soplex_found 112 139 echo 113 echo Build benchmarks.............. : $enable_benchmark114 echo Build demo programs........... : $enable_demo115 echo Build additional tools........ : $enable_tools140 echo build benchmarks.............. : $enable_benchmark 141 echo build demo programs........... : $enable_demo 142 echo build additional tools........ : $enable_tools 116 143 echo 117 144 echo The packace will be installed in … … 119 146 echo $prefix. 120 147 echo 148 echo The documentation will be installed in 149 echo -n ' ' 150 eval echo ${datadir}/doc/$PACKAGE. 151 echo 121 152 echo '*********************************************************************' 122 153 123 154 echo 124 echo Configure complete, now type \'make\' and then \'make install\'.155 echo configure complete, now type \'make\' and then \'make install\'. 125 156 echo -
doc/Makefile.am
r60 r2 1 htmldir = $(datadir)/doc/$(PACKAGE)/html 2 1 3 EXTRA_DIST += \ 2 4 doc/Makefile \ 3 doc/Doxyfile.in \ 4 doc/coding_style.dox \ 5 doc/dirs.dox \ 6 doc/groups.dox \ 7 doc/license.dox \ 8 doc/mainpage.dox \ 9 doc/namespaces.dox \ 10 doc/html 5 doc/Doxyfile.in 11 6 12 doc/html: 13 $(MAKE) $(AM_MAKEFLAGS) html 14 15 html-local: 7 doc: 16 8 if test ${doxygen_found} = yes; then \ 17 9 cd doc; \ 18 10 doxygen Doxyfile; \ 19 11 cd ..; \ 20 else \ 21 echo; \ 22 echo "Doxygen not found."; \ 23 echo; \ 24 exit 1; \ 12 fi 13 14 doc-clean: 15 if test ${doxygen_found} = yes; then \ 16 rm -rf doc/html; \ 17 rm -f doc/doxygen.log; \ 18 cd doc; \ 19 doxygen Doxyfile; \ 20 cd ..; \ 25 21 fi 26 22 … … 29 25 -rm -f doc/doxygen.log 30 26 31 update-external-tags: 32 wget -O doc/libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag && \ 33 mv doc/libstdc++.tag.tmp doc/libstdc++.tag || \ 34 rm doc/libstdc++.tag.tmp 27 doc/html: 28 $(MAKE) $(AM_MAKEFLAGS) doc-clean 35 29 36 install-html-local: doc/html 30 if WANT_DOC 31 32 install-data-local: doc/html 37 33 @$(NORMAL_INSTALL) 38 $(mkinstalldirs) $(DESTDIR)$(htmldir) /docs39 for p in doc/html/*.{html,css,png,map,gif,tag}; do \34 $(mkinstalldirs) $(DESTDIR)$(htmldir) 35 @dir='doc/html'; shopt -s nullglob; for p in $$dir/*.html $$dir/*.css $$dir/*.png $$dir/*.gif $$dir/*.dot $$dir/*.php $$dir/*.idx $$dir/*.tag ; do \ 40 36 f="`echo $$p | sed -e 's|^.*/||'`"; \ 41 echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/ docs/$$f"; \42 $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/ docs/$$f; \37 echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/$$f"; \ 38 $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/$$f; \ 43 39 done 44 40 45 uninstall-local: 41 uninstall-local: doc/html 46 42 @$(NORMAL_UNINSTALL) 47 for p in doc/html/*.{html,css,png,map,gif,tag}; do \43 @dir='doc/html'; shopt -s nullglob; for p in $$dir/*.html $$dir/*.css $$dir/*.png $$dir/*.gif $$dir/*.dot $$dir/*.php $$dir/*.idx $$dir/*.tag ; do \ 48 44 f="`echo $$p | sed -e 's|^.*/||'`"; \ 49 echo " rm -f $(DESTDIR)$(htmldir)/ docs/$$f"; \50 rm -f $(DESTDIR)$(htmldir)/ docs/$$f; \45 echo " rm -f $(DESTDIR)$(htmldir)/$$f"; \ 46 rm -f $(DESTDIR)$(htmldir)/$$f; \ 51 47 done 52 48 53 .PHONY: update-external-tags 49 endif WANT_DOC 50 51 .PHONY: doc doc-clean -
lemon/Makefile.am
r67 r65 18 18 lemon/concept_check.h \ 19 19 lemon/dim2.h \ 20 lemon/error.h \20 lemon/random.h \ 21 21 lemon/list_graph.h \ 22 lemon/maps.h \ 23 lemon/random.h \ 22 lemon/maps.h \ 24 23 lemon/tolerance.h 25 24 26 25 bits_HEADERS += \ 27 lemon/bits/alteration_notifier.h \28 lemon/bits/array_map.h \29 lemon/bits/base_extender.h \30 lemon/bits/default_map.h \31 lemon/bits/graph_extender.h \32 26 lemon/bits/invalid.h \ 33 lemon/bits/map_extender.h \ 34 lemon/bits/traits.h \ 35 lemon/bits/utility.h \ 36 lemon/bits/vector_map.h 27 lemon/bits/utility.h 37 28 38 29 concept_HEADERS += \ 39 lemon/concept_check.h \ 40 lemon/concepts/digraph.h \ 41 lemon/concepts/graph.h \ 42 lemon/concepts/maps.h \ 43 lemon/concepts/graph_components.h 30 lemon/concepts/maps.h -
lemon/base.cc
r49 r7 3 3 * This file is a part of LEMON, a generic C++ optimization library 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2007 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 18 18 19 19 ///\file 20 ///\brief Some basic non -inline functionsand static global data.20 ///\brief Some basic non inline function and static global data. 21 21 22 22 #include<lemon/tolerance.h> -
lemon/bits/invalid.h
r49 r13 3 3 * This file is a part of LEMON, a generic C++ optimization library 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2007 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 27 27 /// \brief Dummy type to make it easier to create invalid iterators. 28 28 /// 29 /// Dummy type to make it easier to create invalid iterators.30 29 /// See \ref INVALID for the usage. 31 30 struct Invalid { -
lemon/bits/utility.h
r39 r7 3 3 * This file is a part of LEMON, a generic C++ optimization library 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2007 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/concept_check.h
r53 r27 3 3 * This file is a part of LEMON, a generic C++ optimization library 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2007 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 34 34 // See http://www.boost.org/libs/concept_check for documentation. 35 35 36 ///\file 37 ///\brief Basic utilities for concept checking. 38 /// 39 ///\todo Are we still using BOOST concept checking utility? 40 ///Is the BOOST copyright notice necessary? 41 42 #ifndef LEMON_CONCEPT_CHECK_H 43 #define LEMON_CONCEPT_CHECK_H 36 #ifndef LEMON_CONCEPT_CHECKS_H 37 #define LEMON_CONCEPT_CHECKS_H 44 38 45 39 namespace lemon { … … 53 47 template <class T> inline void ignore_unused_variable_warning(const T&) { } 54 48 55 ///\e56 49 template <class Concept> 57 50 inline void function_requires() … … 63 56 } 64 57 65 ///\e66 58 template <typename Concept, typename Type> 67 59 inline void checkConcept() { … … 73 65 } 74 66 67 #define BOOST_CLASS_REQUIRE(type_var, ns, concept) \ 68 typedef void (ns::concept <type_var>::* func##type_var##concept)(); \ 69 template <func##type_var##concept Tp1_> \ 70 struct concept_checking_##type_var##concept { }; \ 71 typedef concept_checking_##type_var##concept< \ 72 BOOST_FPTR ns::concept<type_var>::constraints> \ 73 concept_checking_typedef_##type_var##concept 74 75 #define BOOST_CLASS_REQUIRE2(type_var1, type_var2, ns, concept) \ 76 typedef void (ns::concept <type_var1,type_var2>::* \ 77 func##type_var1##type_var2##concept)(); \ 78 template <func##type_var1##type_var2##concept Tp1_> \ 79 struct concept_checking_##type_var1##type_var2##concept { }; \ 80 typedef concept_checking_##type_var1##type_var2##concept< \ 81 BOOST_FPTR ns::concept<type_var1,type_var2>::constraints> \ 82 concept_checking_typedef_##type_var1##type_var2##concept 83 84 #define BOOST_CLASS_REQUIRE3(tv1, tv2, tv3, ns, concept) \ 85 typedef void (ns::concept <tv1,tv2,tv3>::* \ 86 func##tv1##tv2##tv3##concept)(); \ 87 template <func##tv1##tv2##tv3##concept Tp1_> \ 88 struct concept_checking_##tv1##tv2##tv3##concept { }; \ 89 typedef concept_checking_##tv1##tv2##tv3##concept< \ 90 BOOST_FPTR ns::concept<tv1,tv2,tv3>::constraints> \ 91 concept_checking_typedef_##tv1##tv2##tv3##concept 92 93 #define BOOST_CLASS_REQUIRE4(tv1, tv2, tv3, tv4, ns, concept) \ 94 typedef void (ns::concept <tv1,tv2,tv3,tv4>::* \ 95 func##tv1##tv2##tv3##tv4##concept)(); \ 96 template <func##tv1##tv2##tv3##tv4##concept Tp1_> \ 97 struct concept_checking_##tv1##tv2##tv3##tv4##concept { }; \ 98 typedef concept_checking_##tv1##tv2##tv3##tv4##concept< \ 99 BOOST_FPTR ns::concept<tv1,tv2,tv3,tv4>::constraints> \ 100 concept_checking_typedef_##tv1##tv2##tv3##tv4##concept 101 102 75 103 } // namespace lemon 76 104 77 #endif // LEMON_CONCEPT_CHECK _H105 #endif // LEMON_CONCEPT_CHECKS_H -
lemon/concepts/maps.h
r51 r28 3 3 * This file is a part of LEMON, a generic C++ optimization library 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2007 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 42 42 { 43 43 public: 44 /// The key type of the map.45 typedef K Key; 46 /// The value type of the map. (The type of objects associated with the keys).44 /// Map's key type. 45 typedef K Key; 46 /// Map's value type. (The type of objects associated with the keys). 47 47 typedef T Value; 48 48 49 49 /// Returns the value associated with a key. 50 50 51 /// Returns the value associated with a key.52 51 /// \bug Value shouldn't need to be default constructible. 53 52 /// … … 83 82 { 84 83 public: 85 /// The key type of the map.86 typedef K Key; 87 /// The value type of the map. (The type of objects associated with the keys).84 /// Map's key type. 85 typedef K Key; 86 /// Map's value type. (The type of objects associated with the keys). 88 87 typedef T Value; 89 88 … … 115 114 }; 116 115 117 /// Read/ writable map concept116 /// Read/Writable map concept 118 117 119 118 /// Read/writable map concept. … … 121 120 template<typename K, typename T> 122 121 class ReadWriteMap : public ReadMap<K,T>, 123 public WriteMap<K,T>124 { 125 public: 126 /// The key type of the map.127 typedef K Key; 128 /// The value type of the map. (The type of objects associated with the keys).122 public WriteMap<K,T> 123 { 124 public: 125 /// Map's key type. 126 typedef K Key; 127 /// Map's value type. (The type of objects associated with the keys). 129 128 typedef T Value; 130 129 … … 148 147 /// Dereferable map concept. 149 148 /// 150 /// \todo Rethink this concept.151 149 template<typename K, typename T, typename R, typename CR> 152 150 class ReferenceMap : public ReadWriteMap<K,T> … … 155 153 /// Tag for reference maps. 156 154 typedef True ReferenceMapTag; 157 /// The key type of the map.158 typedef K Key; 159 /// The value type of the map. (The type of objects associated with the keys).160 typedef T Value; 161 /// The reference type of the map.155 /// Map's key type. 156 typedef K Key; 157 /// Map's value type. (The type of objects associated with the keys). 158 typedef T Value; 159 /// Map's reference type. 162 160 typedef R Reference; 163 /// The const reference type of the map.161 /// Map's const reference type. 164 162 typedef CR ConstReference; 165 163 … … 168 166 public: 169 167 170 ///Returns a reference to the value associated witha key.168 ///Returns a reference to the value associated to a key. 171 169 Reference operator[](const Key &) { return tmp; } 172 ///Returns a const reference to the value associated witha key.170 ///Returns a const reference to the value associated to a key. 173 171 ConstReference operator[](const Key &) const { return tmp; } 174 172 /// Sets the value associated with a key. 175 173 void set(const Key &k,const Value &t) { operator[](k)=t; } 176 174 175 /// \todo Rethink this concept. 177 176 template<typename _ReferenceMap> 178 177 struct ReferenceMapConcept { -
lemon/dim2.h
r49 r15 3 3 * This file is a part of LEMON, a generic C++ optimization library 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2007 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 28 28 /// 29 29 /// The class \ref lemon::dim2::Point "dim2::Point" implements 30 /// a two dimensional vector with the usual operations. 30 ///a two dimensional vector with the usual 31 /// operations. 31 32 /// 32 33 /// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox" … … 49 50 50 51 /// A simple two dimensional vector (plainvector) implementation 51 /// with the usual vector operations. 52 ///with the usual vector 53 /// operators. 54 /// 52 55 template<typename T> 53 56 class Point { … … 68 71 Point(T a, T b) : x(a), y(b) { } 69 72 70 /// Returns the dimension of the vector (i.e. returns 2).73 ///The dimension of the vector. 71 74 72 75 ///The dimension of the vector. … … 94 97 } 95 98 96 ///Increment the left hand side by \cu99 ///Increment the left hand side by u 97 100 Point<T>& operator +=(const Point<T>& u) { 98 101 x += u.x; … … 101 104 } 102 105 103 ///Decrement the left hand side by \cu106 ///Decrement the left hand side by u 104 107 Point<T>& operator -=(const Point<T>& u) { 105 108 x -= u.x; … … 313 316 ///if at least one point was added to the box or the coordinates of 314 317 ///the box were set). 315 ///316 318 ///The coordinates of an empty bounding box are not defined. 317 319 bool empty() const { … … 324 326 } 325 327 326 ///Give back the bottom left corner of the box327 328 ///Give back the bottom left corner of the box.328 ///Give back the bottom left corner 329 330 ///Give back the bottom left corner. 329 331 ///If the bounding box is empty, then the return value is not defined. 330 332 Point<T> bottomLeft() const { … … 332 334 } 333 335 334 ///Set the bottom left corner of the box335 336 ///Set the bottom left corner of the box.336 ///Set the bottom left corner 337 338 ///Set the bottom left corner. 337 339 ///It should only be used for non-empty box. 338 340 void bottomLeft(Point<T> p) { … … 340 342 } 341 343 342 ///Give back the top right corner of the box343 344 ///Give back the top right corner of the box.344 ///Give back the top right corner 345 346 ///Give back the top right corner. 345 347 ///If the bounding box is empty, then the return value is not defined. 346 348 Point<T> topRight() const { … … 348 350 } 349 351 350 ///Set the top right corner of the box351 352 ///Set the top right corner of the box.352 ///Set the top right corner 353 354 ///Set the top right corner. 353 355 ///It should only be used for non-empty box. 354 356 void topRight(Point<T> p) { … … 356 358 } 357 359 358 ///Give back the bottom right corner of the box359 360 ///Give back the bottom right corner of the box.360 ///Give back the bottom right corner 361 362 ///Give back the bottom right corner. 361 363 ///If the bounding box is empty, then the return value is not defined. 362 364 Point<T> bottomRight() const { … … 364 366 } 365 367 366 ///Set the bottom right corner of the box367 368 ///Set the bottom right corner of the box.368 ///Set the bottom right corner 369 370 ///Set the bottom right corner. 369 371 ///It should only be used for non-empty box. 370 372 void bottomRight(Point<T> p) { … … 373 375 } 374 376 375 ///Give back the top left corner of the box376 377 ///Give back the top left corner of the box.377 ///Give back the top left corner 378 379 ///Give back the top left corner. 378 380 ///If the bounding box is empty, then the return value is not defined. 379 381 Point<T> topLeft() const { … … 381 383 } 382 384 383 ///Set the top left corner of the box384 385 ///Set the top left corner of the box.385 ///Set the top left corner 386 387 ///Set the top left corner. 386 388 ///It should only be used for non-empty box. 387 389 void topLeft(Point<T> p) { … … 667 669 668 670 669 ///\brief Map of the \ref Point::normSquare() "normSquare()" 670 ///of a \ref Point "Point"-map 671 /// 672 ///Map of the \ref Point::normSquare() "normSquare()" 673 ///of a \ref Point "Point"-map. 674 ///\ingroup maps 671 ///\brief Map of the \ref Point::normSquare() "normSquare()" 672 ///of a \ref Point "Point"-map 673 /// 674 ///Map of the \ref Point::normSquare() "normSquare()" 675 ///of a \ref Point "Point"-map. 676 ///\ingroup maps 677 /// 675 678 template<class M> 676 679 class NormSquareMap -
lemon/list_graph.h
r57 r2 1 /* -*- C++ -*-2 *3 * This file is a part of LEMON, a generic C++ optimization library4 *5 * Copyright (C) 2003-20086 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport7 * (Egervary Research Group on Combinatorial Optimization, EGRES).8 *9 * Permission to use, modify and distribute this software is granted10 * provided that this copyright notice appears in all copies. For11 * precise terms see the accompanying LICENSE file.12 *13 * This software is provided "AS IS" with no warranty of any kind,14 * express or implied, and with no claim as to its suitability for any15 * purpose.16 *17 */18 19 #ifndef LEMON_LIST_GRAPH_H20 #define LEMON_LIST_GRAPH_H21 22 ///\ingroup graphs23 ///\file24 ///\brief ListDigraph, ListGraph classes.25 26 #include <lemon/bits/graph_extender.h>27 28 #include <vector>29 #include <list>30 31 namespace lemon {32 33 class ListDigraphBase {34 35 protected:36 struct NodeT {37 int first_in, first_out;38 int prev, next;39 };40 41 struct ArcT {42 int target, source;43 int prev_in, prev_out;44 int next_in, next_out;45 };46 47 std::vector<NodeT> nodes;48 49 int first_node;50 51 int first_free_node;52 53 std::vector<ArcT> arcs;54 55 int first_free_arc;56 57 public:58 59 typedef ListDigraphBase Digraph;60 61 class Node {62 friend class ListDigraphBase;63 protected:64 65 int id;66 explicit Node(int pid) { id = pid;}67 68 public:69 Node() {}70 Node (Invalid) { id = -1; }71 bool operator==(const Node& node) const {return id == node.id;}72 bool operator!=(const Node& node) const {return id != node.id;}73 bool operator<(const Node& node) const {return id < node.id;}74 };75 76 class Arc {77 friend class ListDigraphBase;78 protected:79 80 int id;81 explicit Arc(int pid) { id = pid;}82 83 public:84 Arc() {}85 Arc (Invalid) { id = -1; }86 bool operator==(const Arc& arc) const {return id == arc.id;}87 bool operator!=(const Arc& arc) const {return id != arc.id;}88 bool operator<(const Arc& arc) const {return id < arc.id;}89 };90 91 92 93 ListDigraphBase()94 : nodes(), first_node(-1),95 first_free_node(-1), arcs(), first_free_arc(-1) {}96 97 98 int maxNodeId() const { return nodes.size()-1; }99 int maxArcId() const { return arcs.size()-1; }100 101 Node source(Arc e) const { return Node(arcs[e.id].source); }102 Node target(Arc e) const { return Node(arcs[e.id].target); }103 104 105 void first(Node& node) const {106 node.id = first_node;107 }108 109 void next(Node& node) const {110 node.id = nodes[node.id].next;111 }112 113 114 void first(Arc& e) const {115 int n;116 for(n = first_node;117 n!=-1 && nodes[n].first_in == -1;118 n = nodes[n].next);119 e.id = (n == -1) ? -1 : nodes[n].first_in;120 }121 122 void next(Arc& arc) const {123 if (arcs[arc.id].next_in != -1) {124 arc.id = arcs[arc.id].next_in;125 } else {126 int n;127 for(n = nodes[arcs[arc.id].target].next;128 n!=-1 && nodes[n].first_in == -1;129 n = nodes[n].next);130 arc.id = (n == -1) ? -1 : nodes[n].first_in;131 }132 }133 134 void firstOut(Arc &e, const Node& v) const {135 e.id = nodes[v.id].first_out;136 }137 void nextOut(Arc &e) const {138 e.id=arcs[e.id].next_out;139 }140 141 void firstIn(Arc &e, const Node& v) const {142 e.id = nodes[v.id].first_in;143 }144 void nextIn(Arc &e) const {145 e.id=arcs[e.id].next_in;146 }147 148 149 static int id(Node v) { return v.id; }150 static int id(Arc e) { return e.id; }151 152 static Node nodeFromId(int id) { return Node(id);}153 static Arc arcFromId(int id) { return Arc(id);}154 155 Node addNode() {156 int n;157 158 if(first_free_node==-1) {159 n = nodes.size();160 nodes.push_back(NodeT());161 } else {162 n = first_free_node;163 first_free_node = nodes[n].next;164 }165 166 nodes[n].next = first_node;167 if(first_node != -1) nodes[first_node].prev = n;168 first_node = n;169 nodes[n].prev = -1;170 171 nodes[n].first_in = nodes[n].first_out = -1;172 173 return Node(n);174 }175 176 Arc addArc(Node u, Node v) {177 int n;178 179 if (first_free_arc == -1) {180 n = arcs.size();181 arcs.push_back(ArcT());182 } else {183 n = first_free_arc;184 first_free_arc = arcs[n].next_in;185 }186 187 arcs[n].source = u.id;188 arcs[n].target = v.id;189 190 arcs[n].next_out = nodes[u.id].first_out;191 if(nodes[u.id].first_out != -1) {192 arcs[nodes[u.id].first_out].prev_out = n;193 }194 195 arcs[n].next_in = nodes[v.id].first_in;196 if(nodes[v.id].first_in != -1) {197 arcs[nodes[v.id].first_in].prev_in = n;198 }199 200 arcs[n].prev_in = arcs[n].prev_out = -1;201 202 nodes[u.id].first_out = nodes[v.id].first_in = n;203 204 return Arc(n);205 }206 207 void erase(const Node& node) {208 int n = node.id;209 210 if(nodes[n].next != -1) {211 nodes[nodes[n].next].prev = nodes[n].prev;212 }213 214 if(nodes[n].prev != -1) {215 nodes[nodes[n].prev].next = nodes[n].next;216 } else {217 first_node = nodes[n].next;218 }219 220 nodes[n].next = first_free_node;221 first_free_node = n;222 223 }224 225 void erase(const Arc& arc) {226 int n = arc.id;227 228 if(arcs[n].next_in!=-1) {229 arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;230 }231 232 if(arcs[n].prev_in!=-1) {233 arcs[arcs[n].prev_in].next_in = arcs[n].next_in;234 } else {235 nodes[arcs[n].target].first_in = arcs[n].next_in;236 }237 238 239 if(arcs[n].next_out!=-1) {240 arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;241 }242 243 if(arcs[n].prev_out!=-1) {244 arcs[arcs[n].prev_out].next_out = arcs[n].next_out;245 } else {246 nodes[arcs[n].source].first_out = arcs[n].next_out;247 }248 249 arcs[n].next_in = first_free_arc;250 first_free_arc = n;251 252 }253 254 void clear() {255 arcs.clear();256 nodes.clear();257 first_node = first_free_node = first_free_arc = -1;258 }259 260 protected:261 void changeTarget(Arc e, Node n)262 {263 if(arcs[e.id].next_in != -1)264 arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;265 if(arcs[e.id].prev_in != -1)266 arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;267 else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in;268 if (nodes[n.id].first_in != -1) {269 arcs[nodes[n.id].first_in].prev_in = e.id;270 }271 arcs[e.id].target = n.id;272 arcs[e.id].prev_in = -1;273 arcs[e.id].next_in = nodes[n.id].first_in;274 nodes[n.id].first_in = e.id;275 }276 void changeSource(Arc e, Node n)277 {278 if(arcs[e.id].next_out != -1)279 arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;280 if(arcs[e.id].prev_out != -1)281 arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;282 else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out;283 if (nodes[n.id].first_out != -1) {284 arcs[nodes[n.id].first_out].prev_out = e.id;285 }286 arcs[e.id].source = n.id;287 arcs[e.id].prev_out = -1;288 arcs[e.id].next_out = nodes[n.id].first_out;289 nodes[n.id].first_out = e.id;290 }291 292 };293 294 typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;295 296 /// \addtogroup digraphs297 /// @{298 299 ///A list digraph class.300 301 ///This is a simple and fast digraph implementation.302 ///303 ///It conforms to the \ref concepts::Digraph "Digraph concept" and it304 ///also provides several additional useful extra functionalities.305 ///The most of the member functions and nested classes are306 ///documented only in the concept class.307 ///308 ///An important extra feature of this digraph implementation is that309 ///its maps are real \ref concepts::ReferenceMap "reference map"s.310 ///311 ///\sa concepts::Digraph.312 313 class ListDigraph : public ExtendedListDigraphBase {314 private:315 ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.316 317 ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.318 ///319 ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};320 ///\brief Assignment of ListDigraph to another one is \e not allowed.321 ///Use DigraphCopy() instead.322 323 ///Assignment of ListDigraph to another one is \e not allowed.324 ///Use DigraphCopy() instead.325 void operator=(const ListDigraph &) {}326 public:327 328 typedef ExtendedListDigraphBase Parent;329 330 /// Constructor331 332 /// Constructor.333 ///334 ListDigraph() {}335 336 ///Add a new node to the digraph.337 338 /// \return the new node.339 ///340 Node addNode() { return Parent::addNode(); }341 342 ///Add a new arc to the digraph.343 344 ///Add a new arc to the digraph with source node \c s345 ///and target node \c t.346 ///\return the new arc.347 Arc addArc(const Node& s, const Node& t) {348 return Parent::addArc(s, t);349 }350 351 /// Changes the target of \c e to \c n352 353 /// Changes the target of \c e to \c n354 ///355 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing356 ///the changed arc remain valid. However <tt>InArcIt</tt>s are357 ///invalidated.358 ///\warning This functionality cannot be used together with the Snapshot359 ///feature.360 void changeTarget(Arc e, Node n) {361 Parent::changeTarget(e,n);362 }363 /// Changes the source of \c e to \c n364 365 /// Changes the source of \c e to \c n366 ///367 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing368 ///the changed arc remain valid. However <tt>OutArcIt</tt>s are369 ///invalidated.370 ///\warning This functionality cannot be used together with the Snapshot371 ///feature.372 void changeSource(Arc e, Node n) {373 Parent::changeSource(e,n);374 }375 376 /// Invert the direction of an arc.377 378 ///\note The <tt>ArcIt</tt>s referencing the changed arc remain379 ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are380 ///invalidated.381 ///\warning This functionality cannot be used together with the Snapshot382 ///feature.383 void reverseArc(Arc e) {384 Node t=target(e);385 changeTarget(e,source(e));386 changeSource(e,t);387 }388 389 /// Using this it is possible to avoid the superfluous memory390 /// allocation: if you know that the digraph you want to build will391 /// be very large (e.g. it will contain millions of nodes and/or arcs)392 /// then it is worth reserving space for this amount before starting393 /// to build the digraph.394 /// \sa reserveArc395 void reserveNode(int n) { nodes.reserve(n); };396 397 /// \brief Using this it is possible to avoid the superfluous memory398 /// allocation.399 400 /// Using this it is possible to avoid the superfluous memory401 /// allocation: if you know that the digraph you want to build will402 /// be very large (e.g. it will contain millions of nodes and/or arcs)403 /// then it is worth reserving space for this amount before starting404 /// to build the digraph.405 /// \sa reserveNode406 void reserveArc(int m) { arcs.reserve(m); };407 408 ///Contract two nodes.409 410 ///This function contracts two nodes.411 ///412 ///Node \p b will be removed but instead of deleting413 ///incident arcs, they will be joined to \p a.414 ///The last parameter \p r controls whether to remove loops. \c true415 ///means that loops will be removed.416 ///417 ///\note The <tt>ArcIt</tt>s418 ///referencing a moved arc remain419 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s420 ///may be invalidated.421 ///\warning This functionality cannot be used together with the Snapshot422 ///feature.423 void contract(Node a, Node b, bool r = true)424 {425 for(OutArcIt e(*this,b);e!=INVALID;) {426 OutArcIt f=e;427 ++f;428 if(r && target(e)==a) erase(e);429 else changeSource(e,a);430 e=f;431 }432 for(InArcIt e(*this,b);e!=INVALID;) {433 InArcIt f=e;434 ++f;435 if(r && source(e)==a) erase(e);436 else changeTarget(e,a);437 e=f;438 }439 erase(b);440 }441 442 ///Split a node.443 444 ///This function splits a node. First a new node is added to the digraph,445 ///then the source of each outgoing arc of \c n is moved to this new node.446 ///If \c connect is \c true (this is the default value), then a new arc447 ///from \c n to the newly created node is also added.448 ///\return The newly created node.449 ///450 ///\note The <tt>ArcIt</tt>s referencing a moved arc remain451 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may452 ///be invalidated.453 ///454 ///\warning This functionality cannot be used together with the455 ///Snapshot feature. \todo It could be implemented in a bit456 ///faster way.457 Node split(Node n, bool connect = true) {458 Node b = addNode();459 for(OutArcIt e(*this,n);e!=INVALID;) {460 OutArcIt f=e;461 ++f;462 changeSource(e,b);463 e=f;464 }465 if (connect) addArc(n,b);466 return b;467 }468 469 ///Split an arc.470 471 ///This function splits an arc. First a new node \c b is added to472 ///the digraph, then the original arc is re-targeted to \c473 ///b. Finally an arc from \c b to the original target is added.474 ///\return The newly created node.475 ///\warning This functionality476 ///cannot be used together with the Snapshot feature.477 Node split(Arc e) {478 Node b = addNode();479 addArc(b,target(e));480 changeTarget(e,b);481 return b;482 }483 484 /// \brief Class to make a snapshot of the digraph and restore485 /// to it later.486 ///487 /// Class to make a snapshot of the digraph and to restore it488 /// later.489 ///490 /// The newly added nodes and arcs can be removed using the491 /// restore() function.492 ///493 /// \warning Arc and node deletions cannot be restored. This494 /// events invalidate the snapshot.495 class Snapshot {496 protected:497 498 typedef Parent::NodeNotifier NodeNotifier;499 500 class NodeObserverProxy : public NodeNotifier::ObserverBase {501 public:502 503 NodeObserverProxy(Snapshot& _snapshot)504 : snapshot(_snapshot) {}505 506 using NodeNotifier::ObserverBase::attach;507 using NodeNotifier::ObserverBase::detach;508 using NodeNotifier::ObserverBase::attached;509 510 protected:511 512 virtual void add(const Node& node) {513 snapshot.addNode(node);514 }515 virtual void add(const std::vector<Node>& nodes) {516 for (int i = nodes.size() - 1; i >= 0; ++i) {517 snapshot.addNode(nodes[i]);518 }519 }520 virtual void erase(const Node& node) {521 snapshot.eraseNode(node);522 }523 virtual void erase(const std::vector<Node>& nodes) {524 for (int i = 0; i < int(nodes.size()); ++i) {525 snapshot.eraseNode(nodes[i]);526 }527 }528 virtual void build() {529 Node node;530 std::vector<Node> nodes;531 for (notifier()->first(node); node != INVALID;532 notifier()->next(node)) {533 nodes.push_back(node);534 }535 for (int i = nodes.size() - 1; i >= 0; --i) {536 snapshot.addNode(nodes[i]);537 }538 }539 virtual void clear() {540 Node node;541 for (notifier()->first(node); node != INVALID;542 notifier()->next(node)) {543 snapshot.eraseNode(node);544 }545 }546 547 Snapshot& snapshot;548 };549 550 class ArcObserverProxy : public ArcNotifier::ObserverBase {551 public:552 553 ArcObserverProxy(Snapshot& _snapshot)554 : snapshot(_snapshot) {}555 556 using ArcNotifier::ObserverBase::attach;557 using ArcNotifier::ObserverBase::detach;558 using ArcNotifier::ObserverBase::attached;559 560 protected:561 562 virtual void add(const Arc& arc) {563 snapshot.addArc(arc);564 }565 virtual void add(const std::vector<Arc>& arcs) {566 for (int i = arcs.size() - 1; i >= 0; ++i) {567 snapshot.addArc(arcs[i]);568 }569 }570 virtual void erase(const Arc& arc) {571 snapshot.eraseArc(arc);572 }573 virtual void erase(const std::vector<Arc>& arcs) {574 for (int i = 0; i < int(arcs.size()); ++i) {575 snapshot.eraseArc(arcs[i]);576 }577 }578 virtual void build() {579 Arc arc;580 std::vector<Arc> arcs;581 for (notifier()->first(arc); arc != INVALID;582 notifier()->next(arc)) {583 arcs.push_back(arc);584 }585 for (int i = arcs.size() - 1; i >= 0; --i) {586 snapshot.addArc(arcs[i]);587 }588 }589 virtual void clear() {590 Arc arc;591 for (notifier()->first(arc); arc != INVALID;592 notifier()->next(arc)) {593 snapshot.eraseArc(arc);594 }595 }596 597 Snapshot& snapshot;598 };599 600 ListDigraph *digraph;601 602 NodeObserverProxy node_observer_proxy;603 ArcObserverProxy arc_observer_proxy;604 605 std::list<Node> added_nodes;606 std::list<Arc> added_arcs;607 608 609 void addNode(const Node& node) {610 added_nodes.push_front(node);611 }612 void eraseNode(const Node& node) {613 std::list<Node>::iterator it =614 std::find(added_nodes.begin(), added_nodes.end(), node);615 if (it == added_nodes.end()) {616 clear();617 arc_observer_proxy.detach();618 throw NodeNotifier::ImmediateDetach();619 } else {620 added_nodes.erase(it);621 }622 }623 624 void addArc(const Arc& arc) {625 added_arcs.push_front(arc);626 }627 void eraseArc(const Arc& arc) {628 std::list<Arc>::iterator it =629 std::find(added_arcs.begin(), added_arcs.end(), arc);630 if (it == added_arcs.end()) {631 clear();632 node_observer_proxy.detach();633 throw ArcNotifier::ImmediateDetach();634 } else {635 added_arcs.erase(it);636 }637 }638 639 void attach(ListDigraph &_digraph) {640 digraph = &_digraph;641 node_observer_proxy.attach(digraph->notifier(Node()));642 arc_observer_proxy.attach(digraph->notifier(Arc()));643 }644 645 void detach() {646 node_observer_proxy.detach();647 arc_observer_proxy.detach();648 }649 650 bool attached() const {651 return node_observer_proxy.attached();652 }653 654 void clear() {655 added_nodes.clear();656 added_arcs.clear();657 }658 659 public:660 661 /// \brief Default constructor.662 ///663 /// Default constructor.664 /// To actually make a snapshot you must call save().665 Snapshot()666 : digraph(0), node_observer_proxy(*this),667 arc_observer_proxy(*this) {}668 669 /// \brief Constructor that immediately makes a snapshot.670 ///671 /// This constructor immediately makes a snapshot of the digraph.672 /// \param _digraph The digraph we make a snapshot of.673 Snapshot(ListDigraph &_digraph)674 : node_observer_proxy(*this),675 arc_observer_proxy(*this) {676 attach(_digraph);677 }678 679 /// \brief Make a snapshot.680 ///681 /// Make a snapshot of the digraph.682 ///683 /// This function can be called more than once. In case of a repeated684 /// call, the previous snapshot gets lost.685 /// \param _digraph The digraph we make the snapshot of.686 void save(ListDigraph &_digraph) {687 if (attached()) {688 detach();689 clear();690 }691 attach(_digraph);692 }693 694 /// \brief Undo the changes until the last snapshot.695 //696 /// Undo the changes until the last snapshot created by save().697 void restore() {698 detach();699 for(std::list<Arc>::iterator it = added_arcs.begin();700 it != added_arcs.end(); ++it) {701 digraph->erase(*it);702 }703 for(std::list<Node>::iterator it = added_nodes.begin();704 it != added_nodes.end(); ++it) {705 digraph->erase(*it);706 }707 clear();708 }709 710 /// \brief Gives back true when the snapshot is valid.711 ///712 /// Gives back true when the snapshot is valid.713 bool valid() const {714 return attached();715 }716 };717 718 };719 720 ///@}721 722 class ListGraphBase {723 724 protected:725 726 struct NodeT {727 int first_out;728 int prev, next;729 };730 731 struct ArcT {732 int target;733 int prev_out, next_out;734 };735 736 std::vector<NodeT> nodes;737 738 int first_node;739 740 int first_free_node;741 742 std::vector<ArcT> arcs;743 744 int first_free_arc;745 746 public:747 748 typedef ListGraphBase Digraph;749 750 class Node;751 class Arc;752 class Edge;753 754 class Node {755 friend class ListGraphBase;756 protected:757 758 int id;759 explicit Node(int pid) { id = pid;}760 761 public:762 Node() {}763 Node (Invalid) { id = -1; }764 bool operator==(const Node& node) const {return id == node.id;}765 bool operator!=(const Node& node) const {return id != node.id;}766 bool operator<(const Node& node) const {return id < node.id;}767 };768 769 class Edge {770 friend class ListGraphBase;771 protected:772 773 int id;774 explicit Edge(int pid) { id = pid;}775 776 public:777 Edge() {}778 Edge (Invalid) { id = -1; }779 bool operator==(const Edge& arc) const {return id == arc.id;}780 bool operator!=(const Edge& arc) const {return id != arc.id;}781 bool operator<(const Edge& arc) const {return id < arc.id;}782 };783 784 class Arc {785 friend class ListGraphBase;786 protected:787 788 int id;789 explicit Arc(int pid) { id = pid;}790 791 public:792 operator Edge() const { return edgeFromId(id / 2); }793 794 Arc() {}795 Arc (Invalid) { id = -1; }796 bool operator==(const Arc& arc) const {return id == arc.id;}797 bool operator!=(const Arc& arc) const {return id != arc.id;}798 bool operator<(const Arc& arc) const {return id < arc.id;}799 };800 801 802 803 ListGraphBase()804 : nodes(), first_node(-1),805 first_free_node(-1), arcs(), first_free_arc(-1) {}806 807 808 int maxNodeId() const { return nodes.size()-1; }809 int maxEdgeId() const { return arcs.size() / 2 - 1; }810 int maxArcId() const { return arcs.size()-1; }811 812 Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }813 Node target(Arc e) const { return Node(arcs[e.id].target); }814 815 Node u(Edge e) const { return Node(arcs[2 * e.id].target); }816 Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); }817 818 static bool direction(Arc e) {819 return (e.id & 1) == 1;820 }821 822 static Arc direct(Edge e, bool d) {823 return Arc(e.id * 2 + (d ? 1 : 0));824 }825 826 void first(Node& node) const {827 node.id = first_node;828 }829 830 void next(Node& node) const {831 node.id = nodes[node.id].next;832 }833 834 void first(Arc& e) const {835 int n = first_node;836 while (n != -1 && nodes[n].first_out == -1) {837 n = nodes[n].next;838 }839 e.id = (n == -1) ? -1 : nodes[n].first_out;840 }841 842 void next(Arc& e) const {843 if (arcs[e.id].next_out != -1) {844 e.id = arcs[e.id].next_out;845 } else {846 int n = nodes[arcs[e.id ^ 1].target].next;847 while(n != -1 && nodes[n].first_out == -1) {848 n = nodes[n].next;849 }850 e.id = (n == -1) ? -1 : nodes[n].first_out;851 }852 }853 854 void first(Edge& e) const {855 int n = first_node;856 while (n != -1) {857 e.id = nodes[n].first_out;858 while ((e.id & 1) != 1) {859 e.id = arcs[e.id].next_out;860 }861 if (e.id != -1) {862 e.id /= 2;863 return;864 }865 n = nodes[n].next;866 }867 e.id = -1;868 }869 870 void next(Edge& e) const {871 int n = arcs[e.id * 2].target;872 e.id = arcs[(e.id * 2) | 1].next_out;873 while ((e.id & 1) != 1) {874 e.id = arcs[e.id].next_out;875 }876 if (e.id != -1) {877 e.id /= 2;878 return;879 }880 n = nodes[n].next;881 while (n != -1) {882 e.id = nodes[n].first_out;883 while ((e.id & 1) != 1) {884 e.id = arcs[e.id].next_out;885 }886 if (e.id != -1) {887 e.id /= 2;888 return;889 }890 n = nodes[n].next;891 }892 e.id = -1;893 }894 895 void firstOut(Arc &e, const Node& v) const {896 e.id = nodes[v.id].first_out;897 }898 void nextOut(Arc &e) const {899 e.id = arcs[e.id].next_out;900 }901 902 void firstIn(Arc &e, const Node& v) const {903 e.id = ((nodes[v.id].first_out) ^ 1);904 if (e.id == -2) e.id = -1;905 }906 void nextIn(Arc &e) const {907 e.id = ((arcs[e.id ^ 1].next_out) ^ 1);908 if (e.id == -2) e.id = -1;909 }910 911 void firstInc(Edge &e, bool& d, const Node& v) const {912 int de = nodes[v.id].first_out;913 if (de != -1 ) {914 e.id = de / 2;915 d = ((de & 1) == 1);916 } else {917 e.id = -1;918 d = true;919 }920 }921 void nextInc(Edge &e, bool& d) const {922 int de = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);923 if (de != -1 ) {924 e.id = de / 2;925 d = ((de & 1) == 1);926 } else {927 e.id = -1;928 d = true;929 }930 }931 932 static int id(Node v) { return v.id; }933 static int id(Arc e) { return e.id; }934 static int id(Edge e) { return e.id; }935 936 static Node nodeFromId(int id) { return Node(id);}937 static Arc arcFromId(int id) { return Arc(id);}938 static Edge edgeFromId(int id) { return Edge(id);}939 940 Node addNode() {941 int n;942 943 if(first_free_node==-1) {944 n = nodes.size();945 nodes.push_back(NodeT());946 } else {947 n = first_free_node;948 first_free_node = nodes[n].next;949 }950 951 nodes[n].next = first_node;952 if (first_node != -1) nodes[first_node].prev = n;953 first_node = n;954 nodes[n].prev = -1;955 956 nodes[n].first_out = -1;957 958 return Node(n);959 }960 961 Edge addEdge(Node u, Node v) {962 int n;963 964 if (first_free_arc == -1) {965 n = arcs.size();966 arcs.push_back(ArcT());967 arcs.push_back(ArcT());968 } else {969 n = first_free_arc;970 first_free_arc = arcs[n].next_out;971 }972 973 arcs[n].target = u.id;974 arcs[n | 1].target = v.id;975 976 arcs[n].next_out = nodes[v.id].first_out;977 if (nodes[v.id].first_out != -1) {978 arcs[nodes[v.id].first_out].prev_out = n;979 }980 arcs[n].prev_out = -1;981 nodes[v.id].first_out = n;982 983 arcs[n | 1].next_out = nodes[u.id].first_out;984 if (nodes[u.id].first_out != -1) {985 arcs[nodes[u.id].first_out].prev_out = (n | 1);986 }987 arcs[n | 1].prev_out = -1;988 nodes[u.id].first_out = (n | 1);989 990 return Edge(n / 2);991 }992 993 void erase(const Node& node) {994 int n = node.id;995 996 if(nodes[n].next != -1) {997 nodes[nodes[n].next].prev = nodes[n].prev;998 }999 1000 if(nodes[n].prev != -1) {1001 nodes[nodes[n].prev].next = nodes[n].next;1002 } else {1003 first_node = nodes[n].next;1004 }1005 1006 nodes[n].next = first_free_node;1007 first_free_node = n;1008 1009 }1010 1011 void erase(const Edge& arc) {1012 int n = arc.id * 2;1013 1014 if (arcs[n].next_out != -1) {1015 arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;1016 }1017 1018 if (arcs[n].prev_out != -1) {1019 arcs[arcs[n].prev_out].next_out = arcs[n].next_out;1020 } else {1021 nodes[arcs[n | 1].target].first_out = arcs[n].next_out;1022 }1023 1024 if (arcs[n | 1].next_out != -1) {1025 arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;1026 }1027 1028 if (arcs[n | 1].prev_out != -1) {1029 arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;1030 } else {1031 nodes[arcs[n].target].first_out = arcs[n | 1].next_out;1032 }1033 1034 arcs[n].next_out = first_free_arc;1035 first_free_arc = n;1036 1037 }1038 1039 void clear() {1040 arcs.clear();1041 nodes.clear();1042 first_node = first_free_node = first_free_arc = -1;1043 }1044 1045 protected:1046 1047 void changeTarget(Edge e, Node n) {1048 if(arcs[2 * e.id].next_out != -1) {1049 arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;1050 }1051 if(arcs[2 * e.id].prev_out != -1) {1052 arcs[arcs[2 * e.id].prev_out].next_out =1053 arcs[2 * e.id].next_out;1054 } else {1055 nodes[arcs[(2 * e.id) | 1].target].first_out =1056 arcs[2 * e.id].next_out;1057 }1058 1059 if (nodes[n.id].first_out != -1) {1060 arcs[nodes[n.id].first_out].prev_out = 2 * e.id;1061 }1062 arcs[(2 * e.id) | 1].target = n.id;1063 arcs[2 * e.id].prev_out = -1;1064 arcs[2 * e.id].next_out = nodes[n.id].first_out;1065 nodes[n.id].first_out = 2 * e.id;1066 }1067 1068 void changeSource(Edge e, Node n) {1069 if(arcs[(2 * e.id) | 1].next_out != -1) {1070 arcs[arcs[(2 * e.id) | 1].next_out].prev_out =1071 arcs[(2 * e.id) | 1].prev_out;1072 }1073 if(arcs[(2 * e.id) | 1].prev_out != -1) {1074 arcs[arcs[(2 * e.id) | 1].prev_out].next_out =1075 arcs[(2 * e.id) | 1].next_out;1076 } else {1077 nodes[arcs[2 * e.id].target].first_out =1078 arcs[(2 * e.id) | 1].next_out;1079 }1080 1081 if (nodes[n.id].first_out != -1) {1082 arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);1083 }1084 arcs[2 * e.id].target = n.id;1085 arcs[(2 * e.id) | 1].prev_out = -1;1086 arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;1087 nodes[n.id].first_out = ((2 * e.id) | 1);1088 }1089 1090 };1091 1092 // typedef GraphExtender<UndirDigraphExtender<ListDigraphBase> >1093 // ExtendedListGraphBase;1094 1095 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;1096 1097 1098 1099 /// \addtogroup digraphs1100 /// @{1101 1102 ///An undirected list digraph class.1103 1104 ///This is a simple and fast undirected digraph implementation.1105 ///1106 ///An important extra feature of this digraph implementation is that1107 ///its maps are real \ref concepts::ReferenceMap "reference map"s.1108 ///1109 ///It conforms to the1110 ///\ref concepts::Graph "Graph concept".1111 ///1112 ///\sa concepts::Graph.1113 ///1114 class ListGraph : public ExtendedListGraphBase {1115 private:1116 ///ListGraph is \e not copy constructible. Use GraphCopy() instead.1117 1118 ///ListGraph is \e not copy constructible. Use GraphCopy() instead.1119 ///1120 ListGraph(const ListGraph &) :ExtendedListGraphBase() {};1121 ///\brief Assignment of ListGraph to another one is \e not allowed.1122 ///Use GraphCopy() instead.1123 1124 ///Assignment of ListGraph to another one is \e not allowed.1125 ///Use GraphCopy() instead.1126 void operator=(const ListGraph &) {}1127 public:1128 /// Constructor1129 1130 /// Constructor.1131 ///1132 ListGraph() {}1133 1134 typedef ExtendedListGraphBase Parent;1135 1136 typedef Parent::OutArcIt IncArcIt;1137 1138 /// \brief Add a new node to the digraph.1139 ///1140 /// \return the new node.1141 ///1142 Node addNode() { return Parent::addNode(); }1143 1144 /// \brief Add a new edge to the digraph.1145 ///1146 /// Add a new arc to the digraph with source node \c s1147 /// and target node \c t.1148 /// \return the new edge.1149 Edge addEdge(const Node& s, const Node& t) {1150 return Parent::addEdge(s, t);1151 }1152 /// \brief Changes the source of \c e to \c n1153 ///1154 /// Changes the source of \c e to \c n1155 ///1156 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s1157 ///referencing the changed arc remain1158 ///valid. However <tt>OutArcIt</tt>s are invalidated.1159 void changeSource(Edge e, Node n) {1160 Parent::changeSource(e,n);1161 }1162 /// \brief Changes the target of \c e to \c n1163 ///1164 /// Changes the target of \c e to \c n1165 ///1166 /// \note The <tt>ArcIt</tt>s referencing the changed arc remain1167 /// valid. However the other iterators may be invalidated.1168 void changeTarget(Edge e, Node n) {1169 Parent::changeTarget(e,n);1170 }1171 /// \brief Changes the source of \c e to \c n1172 ///1173 /// Changes the source of \c e to \c n. It changes the proper1174 /// node of the represented edge.1175 ///1176 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s1177 ///referencing the changed arc remain1178 ///valid. However <tt>OutArcIt</tt>s are invalidated.1179 void changeSource(Arc e, Node n) {1180 if (Parent::direction(e)) {1181 Parent::changeSource(e,n);1182 } else {1183 Parent::changeTarget(e,n);1184 }1185 }1186 /// \brief Changes the target of \c e to \c n1187 ///1188 /// Changes the target of \c e to \c n. It changes the proper1189 /// node of the represented edge.1190 ///1191 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s1192 ///referencing the changed arc remain1193 ///valid. However <tt>InArcIt</tt>s are invalidated.1194 void changeTarget(Arc e, Node n) {1195 if (Parent::direction(e)) {1196 Parent::changeTarget(e,n);1197 } else {1198 Parent::changeSource(e,n);1199 }1200 }1201 /// \brief Contract two nodes.1202 ///1203 /// This function contracts two nodes.1204 ///1205 /// Node \p b will be removed but instead of deleting1206 /// its neighboring arcs, they will be joined to \p a.1207 /// The last parameter \p r controls whether to remove loops. \c true1208 /// means that loops will be removed.1209 ///1210 /// \note The <tt>ArcIt</tt>s referencing a moved arc remain1211 /// valid.1212 void contract(Node a, Node b, bool r = true) {1213 for(IncArcIt e(*this, b); e!=INVALID;) {1214 IncArcIt f = e; ++f;1215 if (r && runningNode(e) == a) {1216 erase(e);1217 } else if (source(e) == b) {1218 changeSource(e, a);1219 } else {1220 changeTarget(e, a);1221 }1222 e = f;1223 }1224 erase(b);1225 }1226 1227 1228 /// \brief Class to make a snapshot of the digraph and restore1229 /// to it later.1230 ///1231 /// Class to make a snapshot of the digraph and to restore it1232 /// later.1233 ///1234 /// The newly added nodes and edges can be removed1235 /// using the restore() function.1236 ///1237 /// \warning Arc and node deletions cannot be restored. This1238 /// events invalidate the snapshot.1239 class Snapshot {1240 protected:1241 1242 typedef Parent::NodeNotifier NodeNotifier;1243 1244 class NodeObserverProxy : public NodeNotifier::ObserverBase {1245 public:1246 1247 NodeObserverProxy(Snapshot& _snapshot)1248 : snapshot(_snapshot) {}1249 1250 using NodeNotifier::ObserverBase::attach;1251 using NodeNotifier::ObserverBase::detach;1252 using NodeNotifier::ObserverBase::attached;1253 1254 protected:1255 1256 virtual void add(const Node& node) {1257 snapshot.addNode(node);1258 }1259 virtual void add(const std::vector<Node>& nodes) {1260 for (int i = nodes.size() - 1; i >= 0; ++i) {1261 snapshot.addNode(nodes[i]);1262 }1263 }1264 virtual void erase(const Node& node) {1265 snapshot.eraseNode(node);1266 }1267 virtual void erase(const std::vector<Node>& nodes) {1268 for (int i = 0; i < int(nodes.size()); ++i) {1269 snapshot.eraseNode(nodes[i]);1270 }1271 }1272 virtual void build() {1273 Node node;1274 std::vector<Node> nodes;1275 for (notifier()->first(node); node != INVALID;1276 notifier()->next(node)) {1277 nodes.push_back(node);1278 }1279 for (int i = nodes.size() - 1; i >= 0; --i) {1280 snapshot.addNode(nodes[i]);1281 }1282 }1283 virtual void clear() {1284 Node node;1285 for (notifier()->first(node); node != INVALID;1286 notifier()->next(node)) {1287 snapshot.eraseNode(node);1288 }1289 }1290 1291 Snapshot& snapshot;1292 };1293 1294 class EdgeObserverProxy : public EdgeNotifier::ObserverBase {1295 public:1296 1297 EdgeObserverProxy(Snapshot& _snapshot)1298 : snapshot(_snapshot) {}1299 1300 using EdgeNotifier::ObserverBase::attach;1301 using EdgeNotifier::ObserverBase::detach;1302 using EdgeNotifier::ObserverBase::attached;1303 1304 protected:1305 1306 virtual void add(const Edge& arc) {1307 snapshot.addEdge(arc);1308 }1309 virtual void add(const std::vector<Edge>& arcs) {1310 for (int i = arcs.size() - 1; i >= 0; ++i) {1311 snapshot.addEdge(arcs[i]);1312 }1313 }1314 virtual void erase(const Edge& arc) {1315 snapshot.eraseEdge(arc);1316 }1317 virtual void erase(const std::vector<Edge>& arcs) {1318 for (int i = 0; i < int(arcs.size()); ++i) {1319 snapshot.eraseEdge(arcs[i]);1320 }1321 }1322 virtual void build() {1323 Edge arc;1324 std::vector<Edge> arcs;1325 for (notifier()->first(arc); arc != INVALID;1326 notifier()->next(arc)) {1327 arcs.push_back(arc);1328 }1329 for (int i = arcs.size() - 1; i >= 0; --i) {1330 snapshot.addEdge(arcs[i]);1331 }1332 }1333 virtual void clear() {1334 Edge arc;1335 for (notifier()->first(arc); arc != INVALID;1336 notifier()->next(arc)) {1337 snapshot.eraseEdge(arc);1338 }1339 }1340 1341 Snapshot& snapshot;1342 };1343 1344 ListGraph *digraph;1345 1346 NodeObserverProxy node_observer_proxy;1347 EdgeObserverProxy arc_observer_proxy;1348 1349 std::list<Node> added_nodes;1350 std::list<Edge> added_arcs;1351 1352 1353 void addNode(const Node& node) {1354 added_nodes.push_front(node);1355 }1356 void eraseNode(const Node& node) {1357 std::list<Node>::iterator it =1358 std::find(added_nodes.begin(), added_nodes.end(), node);1359 if (it == added_nodes.end()) {1360 clear();1361 arc_observer_proxy.detach();1362 throw NodeNotifier::ImmediateDetach();1363 } else {1364 added_nodes.erase(it);1365 }1366 }1367 1368 void addEdge(const Edge& arc) {1369 added_arcs.push_front(arc);1370 }1371 void eraseEdge(const Edge& arc) {1372 std::list<Edge>::iterator it =1373 std::find(added_arcs.begin(), added_arcs.end(), arc);1374 if (it == added_arcs.end()) {1375 clear();1376 node_observer_proxy.detach();1377 throw EdgeNotifier::ImmediateDetach();1378 } else {1379 added_arcs.erase(it);1380 }1381 }1382 1383 void attach(ListGraph &_digraph) {1384 digraph = &_digraph;1385 node_observer_proxy.attach(digraph->notifier(Node()));1386 arc_observer_proxy.attach(digraph->notifier(Edge()));1387 }1388 1389 void detach() {1390 node_observer_proxy.detach();1391 arc_observer_proxy.detach();1392 }1393 1394 bool attached() const {1395 return node_observer_proxy.attached();1396 }1397 1398 void clear() {1399 added_nodes.clear();1400 added_arcs.clear();1401 }1402 1403 public:1404 1405 /// \brief Default constructor.1406 ///1407 /// Default constructor.1408 /// To actually make a snapshot you must call save().1409 Snapshot()1410 : digraph(0), node_observer_proxy(*this),1411 arc_observer_proxy(*this) {}1412 1413 /// \brief Constructor that immediately makes a snapshot.1414 ///1415 /// This constructor immediately makes a snapshot of the digraph.1416 /// \param _digraph The digraph we make a snapshot of.1417 Snapshot(ListGraph &_digraph)1418 : node_observer_proxy(*this),1419 arc_observer_proxy(*this) {1420 attach(_digraph);1421 }1422 1423 /// \brief Make a snapshot.1424 ///1425 /// Make a snapshot of the digraph.1426 ///1427 /// This function can be called more than once. In case of a repeated1428 /// call, the previous snapshot gets lost.1429 /// \param _digraph The digraph we make the snapshot of.1430 void save(ListGraph &_digraph) {1431 if (attached()) {1432 detach();1433 clear();1434 }1435 attach(_digraph);1436 }1437 1438 /// \brief Undo the changes until the last snapshot.1439 //1440 /// Undo the changes until the last snapshot created by save().1441 void restore() {1442 detach();1443 for(std::list<Edge>::iterator it = added_arcs.begin();1444 it != added_arcs.end(); ++it) {1445 digraph->erase(*it);1446 }1447 for(std::list<Node>::iterator it = added_nodes.begin();1448 it != added_nodes.end(); ++it) {1449 digraph->erase(*it);1450 }1451 clear();1452 }1453 1454 /// \brief Gives back true when the snapshot is valid.1455 ///1456 /// Gives back true when the snapshot is valid.1457 bool valid() const {1458 return attached();1459 }1460 };1461 };1462 1463 /// @}1464 } //namespace lemon1465 1466 1467 #endif -
lemon/maps.h
r54 r30 3 3 * This file is a part of LEMON, a generic C++ optimization library 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2007 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 45 45 class MapBase { 46 46 public: 47 /// The key type of the map.47 ///\e 48 48 typedef K Key; 49 /// The value type of the map. (The type of objects associated with the keys).49 ///\e 50 50 typedef T Value; 51 51 }; … … 82 82 /// Constant map. 83 83 84 /// This is a \ref concepts::ReadMap "readable" map which assigns a 85 /// specified value to each key. 86 /// In other aspects it is equivalent to \c NullMap. 84 /// This is a readable map which assigns a specified value to each key. 85 /// In other aspects it is equivalent to the \c NullMap. 87 86 template<typename K, typename T> 88 87 class ConstMap : public MapBase<K, T> { … … 117 116 118 117 template<typename T1> 118 struct rebind { 119 typedef ConstMap<K, T1> other; 120 }; 121 122 template<typename T1> 119 123 ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {} 120 124 }; … … 135 139 /// Constant map with inlined constant value. 136 140 137 /// This is a \ref concepts::ReadMap "readable" map which assigns a 138 /// specified value to each key. 139 /// In other aspects it is equivalent to \c NullMap. 141 /// This is a readable map which assigns a specified value to each key. 142 /// In other aspects it is equivalent to the \c NullMap. 140 143 template<typename K, typename V, V v> 141 144 class ConstMap<K, Const<V, v> > : public MapBase<K, V> { … … 152 155 }; 153 156 154 ///Returns a \c ConstMap class with inlined value157 ///Returns a \c ConstMap class 155 158 156 159 ///This function just returns a \c ConstMap class with inlined value. … … 161 164 } 162 165 163 ///Map based on \cstd::map166 ///Map based on std::map 164 167 165 168 ///This is essentially a wrapper for \c std::map with addition that 166 169 ///you can specify a default value different from \c Value(). 167 ///It meets the \ref concepts::ReferenceMap "ReferenceMap" concept.168 170 template <typename K, typename T, typename Compare = std::less<K> > 169 class StdMap : public MapBase<K, T>{171 class StdMap { 170 172 template <typename K1, typename T1, typename C1> 171 173 friend class StdMap; 172 174 public: 173 175 174 typedef MapBase<K, T> Parent;175 /// Key type176 typedef typename Parent::KeyKey;177 /// Value type178 typedef typename Parent::ValueValue;179 /// Reference Type176 typedef True ReferenceMapTag; 177 ///\e 178 typedef K Key; 179 ///\e 180 typedef T Value; 181 ///\e 180 182 typedef T& Reference; 181 /// Const reference type183 ///\e 182 184 typedef const T& ConstReference; 183 184 typedef True ReferenceMapTag;185 185 186 186 private: … … 194 194 /// Constructor with specified default value 195 195 StdMap(const T& value = T()) : _value(value) {} 196 /// \brief Constructs the map from an appropriate \c std::map, and197 /// explicitlyspecifies a default value.196 /// \brief Constructs the map from an appropriate std::map, and explicitly 197 /// specifies a default value. 198 198 template <typename T1, typename Comp1> 199 199 StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T()) 200 200 : _map(map.begin(), map.end()), _value(value) {} 201 201 202 /// \brief Constructs a map from an other \refStdMap.202 /// \brief Constructs a map from an other StdMap. 203 203 template<typename T1, typename Comp1> 204 204 StdMap(const StdMap<Key, T1, Comp1> &c) … … 244 244 } 245 245 246 }; 247 248 ///Returns a \c StdMap class 249 250 ///This function just returns a \c StdMap class with specified 251 ///default value. 252 ///\relates StdMap 253 template<typename K, typename V, typename Compare> 254 inline StdMap<K, V, Compare> stdMap(const V& value = V()) { 255 return StdMap<K, V, Compare>(value); 256 } 257 258 ///Returns a \c StdMap class 259 260 ///This function just returns a \c StdMap class with specified 261 ///default value. 262 ///\relates StdMap 263 template<typename K, typename V> 264 inline StdMap<K, V, std::less<K> > stdMap(const V& value = V()) { 265 return StdMap<K, V, std::less<K> >(value); 266 } 267 268 ///Returns a \c StdMap class created from an appropriate std::map 269 270 ///This function just returns a \c StdMap class created from an 271 ///appropriate std::map. 272 ///\relates StdMap 273 template<typename K, typename V, typename Compare> 274 inline StdMap<K, V, Compare> stdMap( const std::map<K, V, Compare> &map, 275 const V& value = V() ) { 276 return StdMap<K, V, Compare>(map, value); 277 } 278 279 ///Returns a \c StdMap class created from an appropriate std::map 280 281 ///This function just returns a \c StdMap class created from an 282 ///appropriate std::map. 283 ///\relates StdMap 284 template<typename K, typename V> 285 inline StdMap<K, V, std::less<K> > stdMap( const std::map<K, V, std::less<K> > &map, 286 const V& value = V() ) { 287 return StdMap<K, V, std::less<K> >(map, value); 288 } 289 290 /// \brief Map for storing values for keys from the range <tt>[0..size-1]</tt> 291 /// 292 /// This map has the <tt>[0..size-1]</tt> keyset and the values 246 template <typename T1, typename C1 = std::less<T1> > 247 struct rebind { 248 typedef StdMap<Key, T1, C1> other; 249 }; 250 }; 251 252 /// \brief Map for storing values for the range \c [0..size-1] range keys 253 /// 254 /// The current map has the \c [0..size-1] keyset and the values 293 255 /// are stored in a \c std::vector<T> container. It can be used with 294 256 /// some data structures, for example \c UnionFind, \c BinHeap, when 295 /// the used items are small integer numbers. 296 /// This map meets the \ref concepts::ReferenceMap "ReferenceMap" concept. 257 /// the used items are small integer numbers. 297 258 /// 298 259 /// \todo Revise its name 299 260 template <typename T> 300 class IntegerMap : public MapBase<int, T>{261 class IntegerMap { 301 262 302 263 template <typename T1> … … 305 266 public: 306 267 307 typedef MapBase<int, T> Parent;308 ///\e 309 typedef typename Parent::KeyKey;310 ///\e 311 typedef typename Parent::ValueValue;268 typedef True ReferenceMapTag; 269 ///\e 270 typedef int Key; 271 ///\e 272 typedef T Value; 312 273 ///\e 313 274 typedef T& Reference; 314 275 ///\e 315 276 typedef const T& ConstReference; 316 317 typedef True ReferenceMapTag;318 277 319 278 private: … … 327 286 IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {} 328 287 329 /// \brief Constructs the map from an appropriate \cstd::vector.288 /// \brief Constructs the map from an appropriate std::vector. 330 289 template <typename T1> 331 290 IntegerMap(const std::vector<T1>& vector) 332 291 : _vector(vector.begin(), vector.end()) {} 333 292 334 /// \brief Constructs a map from an other \refIntegerMap.293 /// \brief Constructs a map from an other IntegerMap. 335 294 template <typename T1> 336 295 IntegerMap(const IntegerMap<T1> &c) … … 364 323 365 324 }; 366 367 ///Returns an \c IntegerMap class368 369 ///This function just returns an \c IntegerMap class.370 ///\relates IntegerMap371 template<typename T>372 inline IntegerMap<T> integerMap(int size = 0, const T& value = T()) {373 return IntegerMap<T>(size, value);374 }375 325 376 326 /// @} … … 409 359 ///the default conversion. 410 360 /// 411 ///This \ refconcepts::ReadMap "read only map"361 ///This \c concepts::ReadMap "read only map" 412 362 ///converts the \c Value of a map to type \c T. 413 363 ///Its \c Key is inherited from \c M. … … 426 376 ConvertMap(const M &_m) : m(_m) {}; 427 377 428 ///\e 378 /// \brief The subscript operator. 379 /// 380 /// The subscript operator. 429 381 Value operator[](const Key& k) const {return m[k];} 430 382 }; … … 441 393 ///Simple wrapping of a map 442 394 443 ///This \ refconcepts::ReadMap "read only map" returns the simple395 ///This \c concepts::ReadMap "read only map" returns the simple 444 396 ///wrapping of the given map. Sometimes the reference maps cannot be 445 397 ///combined with simple read maps. This map adaptor wraps the given … … 463 415 Value operator[](Key k) const {return m[k];} 464 416 }; 465 466 ///Returns a \c SimpleMap class 467 468 ///This function just returns a \c SimpleMap class. 469 ///\relates SimpleMap 470 template<typename M> 471 inline SimpleMap<M> simpleMap(const M &m) { 472 return SimpleMap<M>(m); 473 } 474 475 ///Simple writable wrapping of a map 476 477 ///This \ref concepts::ReadWriteMap "read-write map" returns the simple 417 418 ///Simple writable wrapping of the map 419 420 ///This \c concepts::WriteMap "write map" returns the simple 478 421 ///wrapping of the given map. Sometimes the reference maps cannot be 479 422 ///combined with simple read-write maps. This map adaptor wraps the … … 500 443 }; 501 444 502 ///Returns a \c SimpleWriteMap class503 504 ///This function just returns a \c SimpleWriteMap class.505 ///\relates SimpleWriteMap506 template<typename M>507 inline SimpleWriteMap<M> simpleWriteMap(M &m) {508 return SimpleWriteMap<M>(m);509 }510 511 445 ///Sum of two maps 512 446 513 ///This \ refconcepts::ReadMap "read only map" returns the sum of the two447 ///This \c concepts::ReadMap "read only map" returns the sum of the two 514 448 ///given maps. 515 449 ///Its \c Key and \c Value are inherited from \c M1. 516 ///The \c Key and \c Value of \cM2 must be convertible to those of \c M1.450 ///The \c Key and \c Value of M2 must be convertible to those of \c M1. 517 451 template<typename M1, typename M2> 518 452 class AddMap : public MapBase<typename M1::Key, typename M1::Value> { … … 534 468 535 469 ///This function just returns an \c AddMap class. 536 ///\todo Extend the documentation: how to call these type of functions?470 ///\todo How to call these type of functions? 537 471 /// 538 472 ///\relates AddMap … … 544 478 ///Shift a map with a constant. 545 479 546 ///This \ refconcepts::ReadMap "read only map" returns the sum of the480 ///This \c concepts::ReadMap "read only map" returns the sum of the 547 481 ///given map and a constant value. 548 482 ///Its \c Key and \c Value are inherited from \c M. … … 580 514 ///Shift a map with a constant (ReadWrite version). 581 515 582 ///This \ refconcepts::ReadWriteMap "read-write map" returns the sum of the516 ///This \c concepts::ReadWriteMap "read-write map" returns the sum of the 583 517 ///given map and a constant value. It makes also possible to write the map. 584 518 ///Its \c Key and \c Value are inherited from \c M. … … 626 560 ///Difference of two maps 627 561 628 ///This \ refconcepts::ReadMap "read only map" returns the difference562 ///This \c concepts::ReadMap "read only map" returns the difference 629 563 ///of the values of the two given maps. 630 564 ///Its \c Key and \c Value are inherited from \c M1. … … 659 593 ///Product of two maps 660 594 661 ///This \ refconcepts::ReadMap "read only map" returns the product of the595 ///This \c concepts::ReadMap "read only map" returns the product of the 662 596 ///values of the two given maps. 663 597 ///Its \c Key and \c Value are inherited from \c M1. … … 689 623 ///Scales a map with a constant. 690 624 691 ///This \ refconcepts::ReadMap "read only map" returns the value of the625 ///This \c concepts::ReadMap "read only map" returns the value of the 692 626 ///given map multiplied from the left side with a constant value. 693 627 ///Its \c Key and \c Value are inherited from \c M. … … 725 659 ///Scales a map with a constant (ReadWrite version). 726 660 727 ///This \ refconcepts::ReadWriteMap "read-write map" returns the value of the661 ///This \c concepts::ReadWriteMap "read-write map" returns the value of the 728 662 ///given map multiplied from the left side with a constant value. It can 729 663 ///also be used as write map if the \c / operator is defined between … … 773 707 ///Quotient of two maps 774 708 775 ///This \ refconcepts::ReadMap "read only map" returns the quotient of the709 ///This \c concepts::ReadMap "read only map" returns the quotient of the 776 710 ///values of the two given maps. 777 711 ///Its \c Key and \c Value are inherited from \c M1. … … 803 737 ///Composition of two maps 804 738 805 ///This \ refconcepts::ReadMap "read only map" returns the composition of739 ///This \c concepts::ReadMap "read only map" returns the composition of 806 740 ///two given maps. 807 741 ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2, … … 854 788 ///Combine of two maps using an STL (binary) functor. 855 789 /// 856 ///This \ refconcepts::ReadMap "read only map" takes two maps and a790 ///This \c concepts::ReadMap "read only map" takes two maps and a 857 791 ///binary functor and returns the composition of the two 858 792 ///given maps unsing the functor. … … 896 830 ///For example if \c m1 and \c m2 are both \c double valued maps, then 897 831 ///\code 898 ///combineMap (m1,m2,std::plus<double>())832 ///combineMap<double>(m1,m2,std::plus<double>()) 899 833 ///\endcode 900 834 ///is equivalent to … … 927 861 ///Negative value of a map 928 862 929 ///This \ refconcepts::ReadMap "read only map" returns the negative863 ///This \c concepts::ReadMap "read only map" returns the negative 930 864 ///value of the value returned by the given map. 931 865 ///Its \c Key and \c Value are inherited from \c M. … … 949 883 ///Negative value of a map (ReadWrite version) 950 884 951 ///This \ refconcepts::ReadWriteMap "read-write map" returns the negative885 ///This \c concepts::ReadWriteMap "read-write map" returns the negative 952 886 ///value of the value returned by the given map. 953 887 ///Its \c Key and \c Value are inherited from \c M. … … 991 925 ///Absolute value of a map 992 926 993 ///This \ refconcepts::ReadMap "read only map" returns the absolute value927 ///This \c concepts::ReadMap "read only map" returns the absolute value 994 928 ///of the value returned by the given map. 995 929 ///Its \c Key and \c Value are inherited from \c M. … … 1025 959 ///Converts an STL style functor to a map 1026 960 1027 ///This \ refconcepts::ReadMap "read only map" returns the value961 ///This \c concepts::ReadMap "read only map" returns the value 1028 962 ///of a given functor. 1029 963 /// 1030 964 ///Template parameters \c K and \c V will become its 1031 ///\c Key and \c Value. 1032 ///In most cases they have to be given explicitly because a 1033 ///functor typically does not provide \c argument_type and 1034 ///\c result_type typedefs. 965 ///\c Key and \c Value. They must be given explicitly 966 ///because a functor does not provide such typedefs. 1035 967 /// 1036 968 ///Parameter \c F is the type of the used functor. … … 1057 989 ///This function just returns a \c FunctorMap class. 1058 990 /// 1059 ///This function is specialized for adaptable binary function 1060 ///classes and C++ functions. 1061 /// 991 ///It is specialized for adaptable function classes and 992 ///C++ functions. 1062 993 ///\relates FunctorMap 1063 994 template<typename K, typename V, typename F> inline … … 1082 1013 1083 1014 ///This class Converts a map to an STL style (unary) functor. 1084 /// That is it provides an <tt>operator()</tt> to read its values.1015 ///that is it provides an <tt>operator()</tt> to read its values. 1085 1016 /// 1086 1017 ///For the sake of convenience it also works as 1087 ///a ususal \ refconcepts::ReadMap "readable map",1018 ///a ususal \c concepts::ReadMap "readable map", 1088 1019 ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist. 1089 1020 /// … … 1117 1048 } 1118 1049 1119 /// Just readable version of \ref ForkWriteMap1120 1121 ///This map has two \ refconcepts::ReadMap "readable map"1050 ///Applies all map setting operations to two maps 1051 1052 ///This map has two \c concepts::ReadMap "readable map" 1122 1053 ///parameters and each read request will be passed just to the 1123 ///first map. This class is the just readable map type of \cForkWriteMap.1054 ///first map. This class is the just readable map type of the ForkWriteMap. 1124 1055 /// 1125 1056 ///The \c Key and \c Value are inherited from \c M1. 1126 ///The \c Key and \c Value of \cM2 must be convertible from those of \c M1.1057 ///The \c Key and \c Value of M2 must be convertible from those of \c M1. 1127 1058 /// 1128 1059 ///\sa ForkWriteMap … … 1147 1078 ///Applies all map setting operations to two maps 1148 1079 1149 ///This map has two \ refconcepts::WriteMap "writable map"1080 ///This map has two \c concepts::WriteMap "writable map" 1150 1081 ///parameters and each write request will be passed to both of them. 1151 ///If \c M1 is also \ refconcepts::ReadMap "readable",1082 ///If \c M1 is also \c concepts::ReadMap "readable", 1152 1083 ///then the read operations will return the 1153 1084 ///corresponding values of \c M1. 1154 1085 /// 1155 1086 ///The \c Key and \c Value are inherited from \c M1. 1156 ///The \c Key and \c Value of \cM2 must be convertible from those of \c M1.1087 ///The \c Key and \c Value of M2 must be convertible from those of \c M1. 1157 1088 /// 1158 1089 ///\sa ForkMap … … 1198 1129 ///Logical 'not' of a map 1199 1130 1200 ///This bool \ refconcepts::ReadMap "read only map" returns the1131 ///This bool \c concepts::ReadMap "read only map" returns the 1201 1132 ///logical negation of the value returned by the given map. 1202 ///Its \c Key is inherited from \c M, its \cValue is \c bool.1133 ///Its \c Key is inherited from \c M, its Value is \c bool. 1203 1134 /// 1204 1135 ///\sa NotWriteMap … … 1219 1150 ///Logical 'not' of a map (ReadWrie version) 1220 1151 1221 ///This bool \ refconcepts::ReadWriteMap "read-write map" returns the1152 ///This bool \c concepts::ReadWriteMap "read-write map" returns the 1222 1153 ///logical negation of the value returned by the given map. When it is set, 1223 1154 ///the opposite value is set to the original map. 1224 ///Its \c Key is inherited from \c M, its \cValue is \c bool.1155 ///Its \c Key is inherited from \c M, its Value is \c bool. 1225 1156 /// 1226 1157 ///\sa NotMap … … 1287 1218 /// \brief Writable bool map for logging each \c true assigned element 1288 1219 /// 1289 /// A \ref concepts::ReadWriteMap "read-write" bool map for logging 1290 /// each \c true assigned element, i.e it copies all the keys set 1291 /// to \c true to the given iterator. 1220 /// Writable bool map for logging each \c true assigned element, i.e it 1221 /// copies all the keys set to \c true to the given iterator. 1292 1222 /// 1293 1223 /// \note The container of the iterator should contain space 1294 1224 /// for each element. 1295 1225 /// 1296 /// The following example shows how you can write the edges found by 1297 /// the \ref Prim algorithm directly to the standard output. 1226 /// The following example shows how you can write the edges found by the Prim 1227 /// algorithm directly 1228 /// to the standard output. 1298 1229 ///\code 1299 1230 /// typedef IdMap<Graph, Edge> EdgeIdMap; … … 1310 1241 /// 1311 1242 ///\sa BackInserterBoolMap 1312 ///\sa FrontInserterBoolMap1313 ///\sa InserterBoolMap1314 1243 /// 1315 1244 ///\todo Revise the name of this class and the related ones. … … 1377 1306 class BackInserterBoolMap { 1378 1307 public: 1379 typedef typename Functor::argument_type Key;1308 typedef typename Container::value_type Key; 1380 1309 typedef bool Value; 1381 1310 … … 1412 1341 class FrontInserterBoolMap { 1413 1342 public: 1414 typedef typename Functor::argument_type Key;1343 typedef typename Container::value_type Key; 1415 1344 typedef bool Value; 1416 1345 … … 1622 1551 } 1623 1552 1624 /// The \c setfunction of the map1553 /// Setter function of the map 1625 1554 void set(const Key& key, Value value) { 1626 1555 if (value) { -
lemon/random.cc
r39 r16 3 3 * This file is a part of LEMON, a generic C++ optimization library 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2007 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
lemon/random.h
r62 r23 3 3 * This file is a part of LEMON, a generic C++ optimization library 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2007 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 255 255 --curr; 256 256 } 257 state[0] = (((state[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^257 curr[0] = (((curr[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^ 258 258 curr[length - shift] ^ mask[curr[length - 1] & 1ul]; 259 259 … … 511 511 ///\endcode 512 512 /// 513 /// LEMONprovides a global instance of the random number513 /// The lemon provides a global instance of the random number 514 514 /// generator which name is \ref lemon::rnd "rnd". Usually it is a 515 515 /// good programming convenience to use this global generator to get … … 527 527 public: 528 528 529 /// \brief Default constructor529 /// \brief Constructor 530 530 /// 531 531 /// Constructor with constant seeding. 532 532 Random() { core.initState(); } 533 533 534 /// \brief Constructor with seed534 /// \brief Constructor 535 535 /// 536 536 /// Constructor with seed. The current number type will be converted … … 541 541 } 542 542 543 /// \brief Constructor with array seeding543 /// \brief Constructor 544 544 /// 545 545 /// Constructor with array seeding. The given range should contain … … 578 578 /// 579 579 /// It returns a random real number from the range [0, 1). The 580 /// default Number type is \cdouble.580 /// default Number type is double. 581 581 template <typename Number> 582 582 Number real() { … … 654 654 /// 655 655 /// It returns a random non-negative integer uniformly from the 656 /// whole range of the current \c Number type. The default result657 /// type of this function is <tt>unsigned int</tt>.656 /// whole range of the current \c Number type. The default result 657 /// type of this function is unsigned int. 658 658 template <typename Number> 659 659 Number uinteger() { … … 669 669 /// It returns a random integer uniformly from the whole range of 670 670 /// the current \c Number type. The default result type of this 671 /// function is \cint.671 /// function is int. 672 672 template <typename Number> 673 673 Number integer() { … … 690 690 } 691 691 692 ///\name Non -uniform distributions692 ///\name Nonuniform distributions 693 693 /// 694 694 -
lemon/tolerance.h
r49 r16 3 3 * This file is a part of LEMON, a generic C++ optimization library 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2007 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 37 37 ///as a result of a probably inexact computation. 38 38 /// 39 /// \refTolerance is a class to provide a basic way to39 ///Tolerance is a class to provide a basic way to 40 40 ///handle the comparison of numbers that are obtained 41 41 ///as a result of a probably inexact computation. 42 42 /// 43 43 ///This is an abstract class, it should be specialized for all numerical 44 ///data types. These specialized classes like \ref Tolerance <double>44 ///data types. These specialized classes like \ref Tolerance\<double\> 45 45 ///may offer additional tuning parameters. 46 46 /// … … 49 49 ///\sa Tolerance<long double> 50 50 ///\sa Tolerance<int> 51 #if defined __GNUC__ && !defined __STRICT_ANSI__ 51 52 ///\sa Tolerance<long long int> 53 #endif 52 54 ///\sa Tolerance<unsigned int> 55 #if defined __GNUC__ && !defined __STRICT_ANSI__ 53 56 ///\sa Tolerance<unsigned long long int> 57 #endif 54 58 55 59 template<class T> … … 60 64 61 65 ///\name Comparisons 62 ///The concept is that these bool functions return \c true only if66 ///The concept is that these bool functions return with \c true only if 63 67 ///the related comparisons hold even if some numerical error appeared 64 68 ///during the computations. … … 88 92 89 93 90 ///Float specialization of Tolerance.91 92 ///Float specialization of Tolerance.94 ///Float specialization of \ref Tolerance. 95 96 ///Float specialization of \ref Tolerance. 93 97 ///\sa Tolerance 94 98 ///\relates Tolerance … … 104 108 ///Constructor setting the epsilon tolerance to the default value. 105 109 Tolerance() : _epsilon(def_epsilon) {} 106 ///Constructor setting the epsilon tolerance to the given value.110 ///Constructor setting the epsilon tolerance. 107 111 Tolerance(float e) : _epsilon(e) {} 108 112 109 ///Return sthe epsilon value.113 ///Return the epsilon value. 110 114 Value epsilon() const {return _epsilon;} 111 ///Set sthe epsilon value.115 ///Set the epsilon value. 112 116 void epsilon(Value e) {_epsilon=e;} 113 117 114 ///Return sthe default epsilon value.118 ///Return the default epsilon value. 115 119 static Value defaultEpsilon() {return def_epsilon;} 116 ///Set sthe default epsilon value.120 ///Set the default epsilon value. 117 121 static void defaultEpsilon(Value e) {def_epsilon=e;} 118 122 119 123 ///\name Comparisons 120 ///See \refTolerance for more details.124 ///See class Tolerance for more details. 121 125 122 126 ///@{ … … 139 143 }; 140 144 141 ///Double specialization of Tolerance.142 143 ///Double specialization of Tolerance.145 ///Double specialization of \ref Tolerance. 146 147 ///Double specialization of \ref Tolerance. 144 148 ///\sa Tolerance 145 149 ///\relates Tolerance … … 155 159 ///Constructor setting the epsilon tolerance to the default value. 156 160 Tolerance() : _epsilon(def_epsilon) {} 157 ///Constructor setting the epsilon tolerance to the given value.161 ///Constructor setting the epsilon tolerance. 158 162 Tolerance(double e) : _epsilon(e) {} 159 163 160 ///Return sthe epsilon value.164 ///Return the epsilon value. 161 165 Value epsilon() const {return _epsilon;} 162 ///Set sthe epsilon value.166 ///Set the epsilon value. 163 167 void epsilon(Value e) {_epsilon=e;} 164 168 165 ///Return sthe default epsilon value.169 ///Return the default epsilon value. 166 170 static Value defaultEpsilon() {return def_epsilon;} 167 ///Set sthe default epsilon value.171 ///Set the default epsilon value. 168 172 static void defaultEpsilon(Value e) {def_epsilon=e;} 169 173 170 174 ///\name Comparisons 171 ///See \refTolerance for more details.175 ///See class Tolerance for more details. 172 176 173 177 ///@{ … … 190 194 }; 191 195 192 ///Long double specialization of Tolerance.193 194 ///Long double specialization of Tolerance.196 ///Long double specialization of \ref Tolerance. 197 198 ///Long double specialization of \ref Tolerance. 195 199 ///\sa Tolerance 196 200 ///\relates Tolerance … … 206 210 ///Constructor setting the epsilon tolerance to the default value. 207 211 Tolerance() : _epsilon(def_epsilon) {} 208 ///Constructor setting the epsilon tolerance to the given value.212 ///Constructor setting the epsilon tolerance. 209 213 Tolerance(long double e) : _epsilon(e) {} 210 214 211 ///Return sthe epsilon value.215 ///Return the epsilon value. 212 216 Value epsilon() const {return _epsilon;} 213 ///Set sthe epsilon value.217 ///Set the epsilon value. 214 218 void epsilon(Value e) {_epsilon=e;} 215 219 216 ///Return sthe default epsilon value.220 ///Return the default epsilon value. 217 221 static Value defaultEpsilon() {return def_epsilon;} 218 ///Set sthe default epsilon value.222 ///Set the default epsilon value. 219 223 static void defaultEpsilon(Value e) {def_epsilon=e;} 220 224 221 225 ///\name Comparisons 222 ///See \refTolerance for more details.226 ///See class Tolerance for more details. 223 227 224 228 ///@{ … … 241 245 }; 242 246 243 ///Integer specialization of Tolerance.244 245 ///Integer specialization of Tolerance.247 ///Integer specialization of \ref Tolerance. 248 249 ///Integer specialization of \ref Tolerance. 246 250 ///\sa Tolerance 247 251 template<> … … 274 278 }; 275 279 276 ///Unsigned integer specialization of Tolerance.277 278 280 ///Unsigned integer specialization of \ref Tolerance. 281 282 ///Unsigned integer specialization of \ref Tolerance. 279 283 ///\sa Tolerance 280 284 template<> … … 308 312 309 313 310 ///Long integer specialization of Tolerance.311 312 ///Long integer specialization of Tolerance.314 ///Long integer specialization of \ref Tolerance. 315 316 ///Long integer specialization of \ref Tolerance. 313 317 ///\sa Tolerance 314 318 template<> … … 341 345 }; 342 346 343 ///Unsigned long integer specialization of Tolerance.344 345 347 ///Unsigned long integer specialization of \ref Tolerance. 348 349 ///Unsigned long integer specialization of \ref Tolerance. 346 350 ///\sa Tolerance 347 351 template<> … … 376 380 #if defined __GNUC__ && !defined __STRICT_ANSI__ 377 381 378 ///Long long integer specialization of Tolerance.382 ///Long long integer specialization of \ref Tolerance. 379 383 380 384 ///Long long integer specialization of \ref Tolerance. … … 411 415 }; 412 416 413 ///Unsigned long long integer specialization of Tolerance.417 ///Unsigned long long integer specialization of \ref Tolerance. 414 418 415 419 ///Unsigned long long integer specialization of \ref Tolerance. -
test/Makefile.am
r67 r65 3 3 4 4 noinst_HEADERS += \ 5 test/digraph_test.h \6 test/map_test.h \7 5 test/test_tools.h 8 6 9 7 check_PROGRAMS += \ 10 test/digraph_test \11 8 test/dim_test \ 12 test/graph_test \13 9 test/maps_test \ 14 10 test/random_test \ … … 19 15 XFAIL_TESTS += test/test_tools_fail$(EXEEXT) 20 16 21 test_digraph_test_SOURCES = test/digraph_test.cc22 17 test_dim_test_SOURCES = test/dim_test.cc 23 #test_error_test_SOURCES = test/error_test.cc24 test_graph_test_SOURCES = test/graph_test.cc25 18 test_maps_test_SOURCES = test/maps_test.cc 26 19 test_random_test_SOURCES = test/random_test.cc -
test/dim_test.cc
r39 r14 3 3 * This file is a part of LEMON, a generic C++ optimization library 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2007 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/maps_test.cc
r39 r25 3 3 * This file is a part of LEMON, a generic C++ optimization library 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2007 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/random_test.cc
r39 r10 3 3 * This file is a part of LEMON, a generic C++ optimization library 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2007 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/test_tools.h
r39 r4 3 3 * This file is a part of LEMON, a generic C++ optimization library 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2007 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/test_tools_fail.cc
r39 r4 3 3 * This file is a part of LEMON, a generic C++ optimization library 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2007 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). -
test/test_tools_pass.cc
r39 r4 3 3 * This file is a part of LEMON, a generic C++ optimization library 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2007 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
Note: See TracChangeset
for help on using the changeset viewer.