COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [67:9de02aa380de:65:bfbc57a51fbb] in lemon


Ignore:
Files:
25 deleted
21 edited

Legend:

Unmodified
Added
Removed

  • configure.ac

    r64 r21  
    33dnl Version information.
    44m4_define([lemon_version_major], [0])
    5 m4_define([lemon_version_minor], [99])
    6 m4_define([lemon_version_micro], [])
     5m4_define([lemon_version_minor], [6])
     6m4_define([lemon_version_micro], [90])
    77m4_define([lemon_version_nano], [])
    88m4_define([lemon_version_tag], [hg])
    … …  
    1414AC_CONFIG_AUX_DIR([build-aux])
    1515AC_CONFIG_MACRO_DIR([m4])
    16 AM_INIT_AUTOMAKE([-Wall -Werror foreign subdir-objects nostdinc])
     16AM_INIT_AUTOMAKE([-Wall -Werror foreign subdir-objects])
    1717AC_CONFIG_SRCDIR([lemon/list_graph.h])
    1818AC_CONFIG_HEADERS([config.h lemon/config.h])
    … …  
    2727AC_PROG_LIBTOOL
    2828
    29 AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
    30 
    3129if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes; then
    3230  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"
    3331fi
     32
     33AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
    3434
    3535dnl Checks for libraries.
    … …  
    3737LX_CHECK_CPLEX
    3838LX_CHECK_SOPLEX
     39
     40dnl Enable/disable installing the documentation
     41AC_ARG_ENABLE([doc],
     42AS_HELP_STRING([--enable-doc@<:@=yes|no|full@:>@], [build the documentation (full enables internal documentation too) @<:@default=yes@:>@])
     43AS_HELP_STRING([--disable-doc], [do not build the documentation]),
     44              [], [enable_doc=yes])
     45
     46AC_MSG_CHECKING([whether to build the documention])
     47case "$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    ;;
     63esac
     64AC_SUBST(DOXYGEN_INTERNAL_DOCS)
     65AM_CONDITIONAL([WANT_DOC], [test x"$enable_doc" != x"no"])
    3966
    4067dnl Disable/enable building the demo programs
    … …  
    111138echo SOPLEX support................ : $lx_soplex_found
    112139echo
    113 echo Build benchmarks.............. : $enable_benchmark
    114 echo Build demo programs........... : $enable_demo
    115 echo Build additional tools........ : $enable_tools
     140echo build benchmarks.............. : $enable_benchmark
     141echo build demo programs........... : $enable_demo
     142echo build additional tools........ : $enable_tools
    116143echo
    117144echo The packace will be installed in
    … …  
    119146echo $prefix.
    120147echo
     148echo The documentation will be installed in
     149echo -n '  '
     150eval echo ${datadir}/doc/$PACKAGE.
     151echo
    121152echo '*********************************************************************'
    122153
    123154echo
    124 echo Configure complete, now type \'make\' and then \'make install\'.
     155echo configure complete, now type \'make\' and then \'make install\'.
    125156echo

  • doc/Makefile.am

    r60 r2  
     1htmldir = $(datadir)/doc/$(PACKAGE)/html
     2
    13EXTRA_DIST += \
    24        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
    116
    12 doc/html:
    13         $(MAKE) $(AM_MAKEFLAGS) html
    14 
    15 html-local:
     7doc:
    168        if test ${doxygen_found} = yes; then \
    179          cd doc; \
    1810          doxygen Doxyfile; \
    1911          cd ..; \
    20         else \
    21           echo; \
    22           echo "Doxygen not found."; \
    23           echo; \
    24           exit 1; \
     12        fi
     13
     14doc-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 ..; \
    2521        fi
    2622
    … …  
    2925        -rm -f doc/doxygen.log
    3026
    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
     27doc/html:
     28        $(MAKE) $(AM_MAKEFLAGS) doc-clean
    3529
    36 install-html-local: doc/html
     30if WANT_DOC
     31
     32install-data-local: doc/html
    3733        @$(NORMAL_INSTALL)
    38         $(mkinstalldirs) $(DESTDIR)$(htmldir)/docs
    39         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 \
    4036          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; \
    4339        done
    4440
    45 uninstall-local:
     41uninstall-local: doc/html
    4642        @$(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 \
    4844          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; \
    5147        done
    5248
    53 .PHONY: update-external-tags
     49endif WANT_DOC
     50
     51.PHONY: doc doc-clean

  • lemon/Makefile.am

    r67 r65  
    1818        lemon/concept_check.h \
    1919        lemon/dim2.h \
    20         lemon/error.h \
     20        lemon/random.h \
    2121        lemon/list_graph.h \
    22         lemon/maps.h \
    23         lemon/random.h \
     22        lemon/maps.h \
    2423        lemon/tolerance.h
    2524
    2625bits_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 \
    3226        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
    3728
    3829concept_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  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2007
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    1818
    1919///\file
    20 ///\brief Some basic non-inline functions and static global data.
     20///\brief Some basic non inline function and static global data.
    2121
    2222#include<lemon/tolerance.h>

  • lemon/bits/invalid.h

    r49 r13  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2007
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    2727  /// \brief Dummy type to make it easier to create invalid iterators.
    2828  ///
    29   /// Dummy type to make it easier to create invalid iterators.
    3029  /// See \ref INVALID for the usage.
    3130  struct Invalid {

  • lemon/bits/utility.h

    r39 r7  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2007
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/concept_check.h

    r53 r27  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2007
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    3434// See http://www.boost.org/libs/concept_check for documentation.
    3535
    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
    4438
    4539namespace lemon {
    … …  
    5347  template <class T> inline void ignore_unused_variable_warning(const T&) { }
    5448
    55   ///\e
    5649  template <class Concept>
    5750  inline void function_requires()
    … …  
    6356  }
    6457
    65   ///\e
    6658  template <typename Concept, typename Type>
    6759  inline void checkConcept() {
    … …  
    7365  }
    7466
     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
    75103} // namespace lemon
    76104
    77 #endif // LEMON_CONCEPT_CHECK_H
     105#endif // LEMON_CONCEPT_CHECKS_H

  • lemon/concepts/maps.h

    r51 r28  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2007
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    4242    {
    4343    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).
    4747      typedef T Value;
    4848
    4949      /// Returns the value associated with a key.
    5050
    51       /// Returns the value associated with a key.
    5251      /// \bug Value shouldn't need to be default constructible.
    5352      ///
    … …  
    8382    {
    8483    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).
    8887      typedef T Value;
    8988
    … …  
    115114    };
    116115
    117     /// Read/writable map concept
     116    /// Read/Writable map concept
    118117   
    119118    /// Read/writable map concept.
    … …  
    121120    template<typename K, typename T>
    122121    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).
    129128      typedef T Value;
    130129
    … …  
    148147    /// Dereferable map concept.
    149148    ///
    150     /// \todo Rethink this concept.
    151149    template<typename K, typename T, typename R, typename CR>
    152150    class ReferenceMap : public ReadWriteMap<K,T>
    … …  
    155153      /// Tag for reference maps.
    156154      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.
    162160      typedef R Reference;
    163       /// The const reference type of the map.
     161      /// Map's const reference type.
    164162      typedef CR ConstReference;
    165163
    … …  
    168166    public:
    169167
    170       ///Returns a reference to the value associated with a key.
     168      ///Returns a reference to the value associated to a key.
    171169      Reference operator[](const Key &) { return tmp; }
    172       ///Returns a const reference to the value associated with a key.
     170      ///Returns a const reference to the value associated to a key.
    173171      ConstReference operator[](const Key &) const { return tmp; }
    174172      /// Sets the value associated with a key.
    175173      void set(const Key &k,const Value &t) { operator[](k)=t; }
    176174
     175      /// \todo Rethink this concept.
    177176      template<typename _ReferenceMap>
    178177      struct ReferenceMapConcept {

  • lemon/dim2.h

    r49 r15  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2007
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    2828///
    2929/// 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.
    3132///
    3233/// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox"
    … …  
    4950
    5051  /// A simple two dimensional vector (plainvector) implementation
    51   /// with the usual vector operations.
     52  ///with the usual vector
     53  /// operators.
     54  ///
    5255  template<typename T>
    5356    class Point {
    … …  
    6871      Point(T a, T b) : x(a), y(b) { }
    6972
    70       ///Returns the dimension of the vector (i.e. returns 2).
     73      ///The dimension of the vector.
    7174
    7275      ///The dimension of the vector.
    … …  
    9497      }
    9598 
    96       ///Increment the left hand side by \c u
     99      ///Increment the left hand side by u
    97100      Point<T>& operator +=(const Point<T>& u) {
    98101        x += u.x;
    … …  
    101104      }
    102105 
    103       ///Decrement the left hand side by \c u
     106      ///Decrement the left hand side by u
    104107      Point<T>& operator -=(const Point<T>& u) {
    105108        x -= u.x;
    … …  
    313316      ///if at least one point was added to the box or the coordinates of
    314317      ///the box were set).
    315       ///
    316318      ///The coordinates of an empty bounding box are not defined.
    317319      bool empty() const {
    … …  
    324326      }
    325327
    326       ///Give back the bottom left corner of the box
    327 
    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.
    329331      ///If the bounding box is empty, then the return value is not defined.
    330332      Point<T> bottomLeft() const {
    … …  
    332334      }
    333335
    334       ///Set the bottom left corner of the box
    335 
    336       ///Set the bottom left corner of the box.
     336      ///Set the bottom left corner
     337
     338      ///Set the bottom left corner.
    337339      ///It should only be used for non-empty box.
    338340      void bottomLeft(Point<T> p) {
    … …  
    340342      }
    341343
    342       ///Give back the top right corner of the box
    343 
    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.
    345347      ///If the bounding box is empty, then the return value is not defined.
    346348      Point<T> topRight() const {
    … …  
    348350      }
    349351
    350       ///Set the top right corner of the box
    351 
    352       ///Set the top right corner of the box.
     352      ///Set the top right corner
     353
     354      ///Set the top right corner.
    353355      ///It should only be used for non-empty box.
    354356      void topRight(Point<T> p) {
    … …  
    356358      }
    357359
    358       ///Give back the bottom right corner of the box
    359 
    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.
    361363      ///If the bounding box is empty, then the return value is not defined.
    362364      Point<T> bottomRight() const {
    … …  
    364366      }
    365367
    366       ///Set the bottom right corner of the box
    367 
    368       ///Set the bottom right corner of the box.
     368      ///Set the bottom right corner
     369
     370      ///Set the bottom right corner.
    369371      ///It should only be used for non-empty box.
    370372      void bottomRight(Point<T> p) {
    … …  
    373375      }
    374376 
    375       ///Give back the top left corner of the box
    376 
    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.
    378380      ///If the bounding box is empty, then the return value is not defined.
    379381      Point<T> topLeft() const {
    … …  
    381383      }
    382384
    383       ///Set the top left corner of the box
    384 
    385       ///Set the top left corner of the box.
     385      ///Set the top left corner
     386
     387      ///Set the top left corner.
    386388      ///It should only be used for non-empty box.
    387389      void topLeft(Point<T> p) {
    … …  
    667669
    668670
    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    ///
    675678  template<class M>
    676679  class NormSquareMap

  • lemon/list_graph.h

    r57 r2  
    1 /* -*- C++ -*-
    2  *
    3  * This file is a part of LEMON, a generic C++ optimization library
    4  *
    5  * Copyright (C) 2003-2008
    6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
    8  *
    9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * 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 any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_LIST_GRAPH_H
    20 #define LEMON_LIST_GRAPH_H
    21 
    22 ///\ingroup graphs
    23 ///\file
    24 ///\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 digraphs
    297   /// @{
    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 it
    304   ///also provides several additional useful extra functionalities.
    305   ///The most of the member functions and nested classes are
    306   ///documented only in the concept class.
    307   ///
    308   ///An important extra feature of this digraph implementation is that
    309   ///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     /// Constructor
    331    
    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 s
    345     ///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 n
    352 
    353     /// Changes the target of \c e to \c n
    354     ///
    355     ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
    356     ///the changed arc remain valid. However <tt>InArcIt</tt>s are
    357     ///invalidated.
    358     ///\warning This functionality cannot be used together with the Snapshot
    359     ///feature.
    360     void changeTarget(Arc e, Node n) {
    361       Parent::changeTarget(e,n);
    362     }
    363     /// Changes the source of \c e to \c n
    364 
    365     /// Changes the source of \c e to \c n
    366     ///
    367     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing
    368     ///the changed arc remain valid. However <tt>OutArcIt</tt>s are
    369     ///invalidated.
    370     ///\warning This functionality cannot be used together with the Snapshot
    371     ///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 remain
    379     ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
    380     ///invalidated.
    381     ///\warning This functionality cannot be used together with the Snapshot
    382     ///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 memory
    390     /// allocation: if you know that the digraph you want to build will
    391     /// 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 starting
    393     /// to build the digraph.
    394     /// \sa reserveArc
    395     void reserveNode(int n) { nodes.reserve(n); };
    396 
    397     /// \brief Using this it is possible to avoid the superfluous memory
    398     /// allocation.
    399 
    400     /// Using this it is possible to avoid the superfluous memory
    401     /// allocation: if you know that the digraph you want to build will
    402     /// 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 starting
    404     /// to build the digraph.
    405     /// \sa reserveNode
    406     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 deleting
    413     ///incident arcs, they will be joined to \p a.
    414     ///The last parameter \p r controls whether to remove loops. \c true
    415     ///means that loops will be removed.
    416     ///
    417     ///\note The <tt>ArcIt</tt>s
    418     ///referencing a moved arc remain
    419     ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
    420     ///may be invalidated.
    421     ///\warning This functionality cannot be used together with the Snapshot
    422     ///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 arc
    447     ///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 remain
    451     ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
    452     ///be invalidated. 
    453     ///
    454     ///\warning This functionality cannot be used together with the
    455     ///Snapshot feature.  \todo It could be implemented in a bit
    456     ///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 to
    472     ///the digraph, then the original arc is re-targeted to \c
    473     ///b. Finally an arc from \c b to the original target is added.
    474     ///\return The newly created node. 
    475     ///\warning This functionality
    476     ///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 restore
    485     /// to it later.
    486     ///
    487     /// Class to make a snapshot of the digraph and to restore it
    488     /// later.
    489     ///
    490     /// The newly added nodes and arcs can be removed using the
    491     /// restore() function.
    492     ///
    493     /// \warning Arc and node deletions cannot be restored. This
    494     /// 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 repeated
    684       /// 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 digraphs
    1100   /// @{
    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 that
    1107   ///its maps are real \ref concepts::ReferenceMap "reference map"s.
    1108   ///
    1109   ///It conforms to the
    1110   ///\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     /// Constructor
    1129    
    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 s
    1147     /// 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 n
    1153     ///
    1154     /// Changes the source of \c e to \c n
    1155     ///
    1156     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
    1157     ///referencing the changed arc remain
    1158     ///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 n
    1163     ///
    1164     /// Changes the target of \c e to \c n
    1165     ///
    1166     /// \note The <tt>ArcIt</tt>s referencing the changed arc remain
    1167     /// 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 n
    1172     ///
    1173     /// Changes the source of \c e to \c n. It changes the proper
    1174     /// node of the represented edge.
    1175     ///
    1176     ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
    1177     ///referencing the changed arc remain
    1178     ///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 n
    1187     ///
    1188     /// Changes the target of \c e to \c n. It changes the proper
    1189     /// node of the represented edge.
    1190     ///
    1191     ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s
    1192     ///referencing the changed arc remain
    1193     ///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 deleting
    1206     /// its neighboring arcs, they will be joined to \p a.
    1207     /// The last parameter \p r controls whether to remove loops. \c true
    1208     /// means that loops will be removed.
    1209     ///
    1210     /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
    1211     /// 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 restore
    1229     /// to it later.
    1230     ///
    1231     /// Class to make a snapshot of the digraph and to restore it
    1232     /// later.
    1233     ///
    1234     /// The newly added nodes and edges can be removed
    1235     /// using the restore() function.
    1236     ///
    1237     /// \warning Arc and node deletions cannot be restored. This
    1238     /// 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 repeated
    1428       /// 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 lemon
    1465  
    1466 
    1467 #endif

  • lemon/maps.h

    r54 r30  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2007
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    4545  class MapBase {
    4646  public:
    47     /// The key type of the map.
     47    ///\e
    4848    typedef K Key;
    49     /// The value type of the map. (The type of objects associated with the keys).
     49    ///\e
    5050    typedef T Value;
    5151  };
    … …  
    8282  /// Constant map.
    8383
    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.
    8786  template<typename K, typename T>
    8887  class ConstMap : public MapBase<K, T> {
    … …  
    117116
    118117    template<typename T1>
     118    struct rebind {
     119      typedef ConstMap<K, T1> other;
     120    };
     121
     122    template<typename T1>
    119123    ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {}
    120124  };
    … …  
    135139  /// Constant map with inlined constant value.
    136140
    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.
    140143  template<typename K, typename V, V v>
    141144  class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
    … …  
    152155  };
    153156
    154   ///Returns a \c ConstMap class with inlined value
     157  ///Returns a \c ConstMap class
    155158
    156159  ///This function just returns a \c ConstMap class with inlined value.
    … …  
    161164  }
    162165
    163   ///Map based on \c std::map
     166  ///Map based on std::map
    164167
    165168  ///This is essentially a wrapper for \c std::map with addition that
    166169  ///you can specify a default value different from \c Value().
    167   ///It meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
    168170  template <typename K, typename T, typename Compare = std::less<K> >
    169   class StdMap : public MapBase<K, T> {
     171  class StdMap {
    170172    template <typename K1, typename T1, typename C1>
    171173    friend class StdMap;
    172174  public:
    173175
    174     typedef MapBase<K, T> Parent;
    175     ///Key type
    176     typedef typename Parent::Key Key;
    177     ///Value type
    178     typedef typename Parent::Value Value;
    179     ///Reference Type
     176    typedef True ReferenceMapTag;
     177    ///\e
     178    typedef K Key;
     179    ///\e
     180    typedef T Value;
     181    ///\e
    180182    typedef T& Reference;
    181     ///Const reference type
     183    ///\e
    182184    typedef const T& ConstReference;
    183 
    184     typedef True ReferenceMapTag;
    185185
    186186  private:
    … …  
    194194    /// Constructor with specified default value
    195195    StdMap(const T& value = T()) : _value(value) {}
    196     /// \brief Constructs the map from an appropriate \c std::map, and
    197     /// explicitly specifies a default value.
     196    /// \brief Constructs the map from an appropriate std::map, and explicitly
     197    /// specifies a default value.
    198198    template <typename T1, typename Comp1>
    199199    StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T())
    200200      : _map(map.begin(), map.end()), _value(value) {}
    201201   
    202     /// \brief Constructs a map from an other \ref StdMap.
     202    /// \brief Constructs a map from an other StdMap.
    203203    template<typename T1, typename Comp1>
    204204    StdMap(const StdMap<Key, T1, Comp1> &c)
    … …  
    244244    }   
    245245
    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
    293255  /// are stored in a \c std::vector<T>  container. It can be used with
    294256  /// 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.
    297258  ///
    298259  /// \todo Revise its name
    299260  template <typename T>
    300   class IntegerMap : public MapBase<int, T> {
     261  class IntegerMap {
    301262
    302263    template <typename T1>
    … …  
    305266  public:
    306267
    307     typedef MapBase<int, T> Parent;
    308     ///\e
    309     typedef typename Parent::Key Key;
    310     ///\e
    311     typedef typename Parent::Value Value;
     268    typedef True ReferenceMapTag;
     269    ///\e
     270    typedef int Key;
     271    ///\e
     272    typedef T Value;
    312273    ///\e
    313274    typedef T& Reference;
    314275    ///\e
    315276    typedef const T& ConstReference;
    316 
    317     typedef True ReferenceMapTag;
    318277
    319278  private:
    … …  
    327286    IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
    328287
    329     /// \brief Constructs the map from an appropriate \c std::vector.
     288    /// \brief Constructs the map from an appropriate std::vector.
    330289    template <typename T1>
    331290    IntegerMap(const std::vector<T1>& vector)
    332291      : _vector(vector.begin(), vector.end()) {}
    333292   
    334     /// \brief Constructs a map from an other \ref IntegerMap.
     293    /// \brief Constructs a map from an other IntegerMap.
    335294    template <typename T1>
    336295    IntegerMap(const IntegerMap<T1> &c)
    … …  
    364323
    365324  };
    366  
    367   ///Returns an \c IntegerMap class
    368 
    369   ///This function just returns an \c IntegerMap class.
    370   ///\relates IntegerMap
    371   template<typename T>
    372   inline IntegerMap<T> integerMap(int size = 0, const T& value = T()) {
    373     return IntegerMap<T>(size, value);
    374   }
    375325
    376326  /// @}
    … …  
    409359  ///the default conversion.
    410360  ///
    411   ///This \ref concepts::ReadMap "read only map"
     361  ///This \c concepts::ReadMap "read only map"
    412362  ///converts the \c Value of a map to type \c T.
    413363  ///Its \c Key is inherited from \c M.
    … …  
    426376    ConvertMap(const M &_m) : m(_m) {};
    427377
    428     ///\e
     378    /// \brief The subscript operator.
     379    ///
     380    /// The subscript operator.
    429381    Value operator[](const Key& k) const {return m[k];}
    430382  };
    … …  
    441393  ///Simple wrapping of a map
    442394
    443   ///This \ref concepts::ReadMap "read only map" returns the simple
     395  ///This \c concepts::ReadMap "read only map" returns the simple
    444396  ///wrapping of the given map. Sometimes the reference maps cannot be
    445397  ///combined with simple read maps. This map adaptor wraps the given
    … …  
    463415    Value operator[](Key k) const {return m[k];}
    464416  };
    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
    478421  ///wrapping of the given map. Sometimes the reference maps cannot be
    479422  ///combined with simple read-write maps. This map adaptor wraps the
    … …  
    500443  };
    501444
    502   ///Returns a \c SimpleWriteMap class
    503 
    504   ///This function just returns a \c SimpleWriteMap class.
    505   ///\relates SimpleWriteMap
    506   template<typename M>
    507   inline SimpleWriteMap<M> simpleWriteMap(M &m) {
    508     return SimpleWriteMap<M>(m);
    509   }
    510 
    511445  ///Sum of two maps
    512446
    513   ///This \ref concepts::ReadMap "read only map" returns the sum of the two
     447  ///This \c concepts::ReadMap "read only map" returns the sum of the two
    514448  ///given maps.
    515449  ///Its \c Key and \c Value are inherited from \c M1.
    516   ///The \c Key and \c Value of \c M2 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.
    517451  template<typename M1, typename M2>
    518452  class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
    … …  
    534468
    535469  ///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?
    537471  ///
    538472  ///\relates AddMap
    … …  
    544478  ///Shift a map with a constant.
    545479
    546   ///This \ref concepts::ReadMap "read only map" returns the sum of the
     480  ///This \c concepts::ReadMap "read only map" returns the sum of the
    547481  ///given map and a constant value.
    548482  ///Its \c Key and \c Value are inherited from \c M.
    … …  
    580514  ///Shift a map with a constant (ReadWrite version).
    581515
    582   ///This \ref concepts::ReadWriteMap "read-write map" returns the sum of the
     516  ///This \c concepts::ReadWriteMap "read-write map" returns the sum of the
    583517  ///given map and a constant value. It makes also possible to write the map.
    584518  ///Its \c Key and \c Value are inherited from \c M.
    … …  
    626560  ///Difference of two maps
    627561
    628   ///This \ref concepts::ReadMap "read only map" returns the difference
     562  ///This \c concepts::ReadMap "read only map" returns the difference
    629563  ///of the values of the two given maps.
    630564  ///Its \c Key and \c Value are inherited from \c M1.
    … …  
    659593  ///Product of two maps
    660594
    661   ///This \ref concepts::ReadMap "read only map" returns the product of the
     595  ///This \c concepts::ReadMap "read only map" returns the product of the
    662596  ///values of the two given maps.
    663597  ///Its \c Key and \c Value are inherited from \c M1.
    … …  
    689623  ///Scales a map with a constant.
    690624
    691   ///This \ref concepts::ReadMap "read only map" returns the value of the
     625  ///This \c concepts::ReadMap "read only map" returns the value of the
    692626  ///given map multiplied from the left side with a constant value.
    693627  ///Its \c Key and \c Value are inherited from \c M.
    … …  
    725659  ///Scales a map with a constant (ReadWrite version).
    726660
    727   ///This \ref concepts::ReadWriteMap "read-write map" returns the value of the
     661  ///This \c concepts::ReadWriteMap "read-write map" returns the value of the
    728662  ///given map multiplied from the left side with a constant value. It can
    729663  ///also be used as write map if the \c / operator is defined between
    … …  
    773707  ///Quotient of two maps
    774708
    775   ///This \ref concepts::ReadMap "read only map" returns the quotient of the
     709  ///This \c concepts::ReadMap "read only map" returns the quotient of the
    776710  ///values of the two given maps.
    777711  ///Its \c Key and \c Value are inherited from \c M1.
    … …  
    803737  ///Composition of two maps
    804738
    805   ///This \ref concepts::ReadMap "read only map" returns the composition of
     739  ///This \c concepts::ReadMap "read only map" returns the composition of
    806740  ///two given maps.
    807741  ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2,
    … …  
    854788  ///Combine of two maps using an STL (binary) functor.
    855789  ///
    856   ///This \ref concepts::ReadMap "read only map" takes two maps and a
     790  ///This \c concepts::ReadMap "read only map" takes two maps and a
    857791  ///binary functor and returns the composition of the two
    858792  ///given maps unsing the functor.
    … …  
    896830  ///For example if \c m1 and \c m2 are both \c double valued maps, then
    897831  ///\code
    898   ///combineMap(m1,m2,std::plus<double>())
     832  ///combineMap<double>(m1,m2,std::plus<double>())
    899833  ///\endcode
    900834  ///is equivalent to
    … …  
    927861  ///Negative value of a map
    928862
    929   ///This \ref concepts::ReadMap "read only map" returns the negative
     863  ///This \c concepts::ReadMap "read only map" returns the negative
    930864  ///value of the value returned by the given map.
    931865  ///Its \c Key and \c Value are inherited from \c M.
    … …  
    949883  ///Negative value of a map (ReadWrite version)
    950884
    951   ///This \ref concepts::ReadWriteMap "read-write map" returns the negative
     885  ///This \c concepts::ReadWriteMap "read-write map" returns the negative
    952886  ///value of the value returned by the given map.
    953887  ///Its \c Key and \c Value are inherited from \c M.
    … …  
    991925  ///Absolute value of a map
    992926
    993   ///This \ref concepts::ReadMap "read only map" returns the absolute value
     927  ///This \c concepts::ReadMap "read only map" returns the absolute value
    994928  ///of the value returned by the given map.
    995929  ///Its \c Key and \c Value are inherited from \c M.
    … …  
    1025959  ///Converts an STL style functor to a map
    1026960
    1027   ///This \ref concepts::ReadMap "read only map" returns the value
     961  ///This \c concepts::ReadMap "read only map" returns the value
    1028962  ///of a given functor.
    1029963  ///
    1030964  ///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.
    1035967  ///
    1036968  ///Parameter \c F is the type of the used functor.
    … …  
    1057989  ///This function just returns a \c FunctorMap class.
    1058990  ///
    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.
    1062993  ///\relates FunctorMap
    1063994  template<typename K, typename V, typename F> inline
    … …  
    10821013
    10831014  ///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.
    10851016  ///
    10861017  ///For the sake of convenience it also works as
    1087   ///a ususal \ref concepts::ReadMap "readable map",
     1018  ///a ususal \c concepts::ReadMap "readable map",
    10881019  ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
    10891020  ///
    … …  
    11171048  }
    11181049
    1119   ///Just readable version of \ref ForkWriteMap
    1120 
    1121   ///This map has two \ref concepts::ReadMap "readable map"
     1050  ///Applies all map setting operations to two maps
     1051
     1052  ///This map has two \c concepts::ReadMap "readable map"
    11221053  ///parameters and each read request will be passed just to the
    1123   ///first map. This class is the just readable map type of \c ForkWriteMap.
     1054  ///first map. This class is the just readable map type of the ForkWriteMap.
    11241055  ///
    11251056  ///The \c Key and \c Value are inherited from \c M1.
    1126   ///The \c Key and \c Value of \c M2 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.
    11271058  ///
    11281059  ///\sa ForkWriteMap
    … …  
    11471078  ///Applies all map setting operations to two maps
    11481079
    1149   ///This map has two \ref concepts::WriteMap "writable map"
     1080  ///This map has two \c concepts::WriteMap "writable map"
    11501081  ///parameters and each write request will be passed to both of them.
    1151   ///If \c M1 is also \ref concepts::ReadMap "readable",
     1082  ///If \c M1 is also \c concepts::ReadMap "readable",
    11521083  ///then the read operations will return the
    11531084  ///corresponding values of \c M1.
    11541085  ///
    11551086  ///The \c Key and \c Value are inherited from \c M1.
    1156   ///The \c Key and \c Value of \c M2 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.
    11571088  ///
    11581089  ///\sa ForkMap
    … …  
    11981129  ///Logical 'not' of a map
    11991130 
    1200   ///This bool \ref concepts::ReadMap "read only map" returns the
     1131  ///This bool \c concepts::ReadMap "read only map" returns the
    12011132  ///logical negation of the value returned by the given map.
    1202   ///Its \c Key is inherited from \c M, its \c Value is \c bool.
     1133  ///Its \c Key is inherited from \c M, its Value is \c bool.
    12031134  ///
    12041135  ///\sa NotWriteMap
    … …  
    12191150  ///Logical 'not' of a map (ReadWrie version)
    12201151 
    1221   ///This bool \ref concepts::ReadWriteMap "read-write map" returns the
     1152  ///This bool \c concepts::ReadWriteMap "read-write map" returns the
    12221153  ///logical negation of the value returned by the given map. When it is set,
    12231154  ///the opposite value is set to the original map.
    1224   ///Its \c Key is inherited from \c M, its \c Value is \c bool.
     1155  ///Its \c Key is inherited from \c M, its Value is \c bool.
    12251156  ///
    12261157  ///\sa NotMap
    … …  
    12871218  /// \brief Writable bool map for logging each \c true assigned element
    12881219  ///
    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.
    12921222  ///
    12931223  /// \note The container of the iterator should contain space
    12941224  /// for each element.
    12951225  ///
    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.
    12981229  ///\code
    12991230  /// typedef IdMap<Graph, Edge> EdgeIdMap;
    … …  
    13101241  ///
    13111242  ///\sa BackInserterBoolMap
    1312   ///\sa FrontInserterBoolMap
    1313   ///\sa InserterBoolMap
    13141243  ///
    13151244  ///\todo Revise the name of this class and the related ones.
    … …  
    13771306  class BackInserterBoolMap {
    13781307  public:
    1379     typedef typename Functor::argument_type Key;
     1308    typedef typename Container::value_type Key;
    13801309    typedef bool Value;
    13811310
    … …  
    14121341  class FrontInserterBoolMap {
    14131342  public:
    1414     typedef typename Functor::argument_type Key;
     1343    typedef typename Container::value_type Key;
    14151344    typedef bool Value;
    14161345
    … …  
    16221551    }
    16231552
    1624     /// The \c set function of the map
     1553    /// Setter function of the map
    16251554    void set(const Key& key, Value value) {
    16261555      if (value) {

  • lemon/random.cc

    r39 r16  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2007
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • lemon/random.h

    r62 r23  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2007
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    255255          --curr;
    256256        }
    257         state[0] = (((state[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^
     257        curr[0] = (((curr[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^
    258258          curr[length - shift] ^ mask[curr[length - 1] & 1ul];
    259259
    … …  
    511511  ///\endcode
    512512  ///
    513   /// LEMON provides a global instance of the random number
     513  /// The lemon provides a global instance of the random number
    514514  /// generator which name is \ref lemon::rnd "rnd". Usually it is a
    515515  /// good programming convenience to use this global generator to get
    … …  
    527527  public:
    528528
    529     /// \brief Default constructor
     529    /// \brief Constructor
    530530    ///
    531531    /// Constructor with constant seeding.
    532532    Random() { core.initState(); }
    533533
    534     /// \brief Constructor with seed
     534    /// \brief Constructor
    535535    ///
    536536    /// Constructor with seed. The current number type will be converted
    … …  
    541541    }
    542542
    543     /// \brief Constructor with array seeding
     543    /// \brief Constructor
    544544    ///
    545545    /// Constructor with array seeding. The given range should contain
    … …  
    578578    ///
    579579    /// It returns a random real number from the range [0, 1). The
    580     /// default Number type is \c double.
     580    /// default Number type is double.
    581581    template <typename Number>
    582582    Number real() {
    … …  
    654654    ///
    655655    /// It returns a random non-negative integer uniformly from the
    656     /// whole range of the current \c Number type. The default result
    657     /// 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.
    658658    template <typename Number>
    659659    Number uinteger() {
    … …  
    669669    /// It returns a random integer uniformly from the whole range of
    670670    /// the current \c Number type. The default result type of this
    671     /// function is \c int.
     671    /// function is int.
    672672    template <typename Number>
    673673    Number integer() {
    … …  
    690690    }
    691691
    692     ///\name Non-uniform distributions
     692    ///\name Nonuniform distributions
    693693    ///
    694694   

  • lemon/tolerance.h

    r49 r16  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2007
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    3737  ///as a result of a probably inexact computation.
    3838  ///
    39   ///\ref Tolerance is a class to provide a basic way to
     39  ///Tolerance is a class to provide a basic way to
    4040  ///handle the comparison of numbers that are obtained
    4141  ///as a result of a probably inexact computation.
    4242  ///
    4343  ///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\>
    4545  ///may offer additional tuning parameters.
    4646  ///
    … …  
    4949  ///\sa Tolerance<long double>
    5050  ///\sa Tolerance<int>
     51#if defined __GNUC__ && !defined __STRICT_ANSI__ 
    5152  ///\sa Tolerance<long long int>
     53#endif
    5254  ///\sa Tolerance<unsigned int>
     55#if defined __GNUC__ && !defined __STRICT_ANSI__ 
    5356  ///\sa Tolerance<unsigned long long int>
     57#endif
    5458
    5559  template<class T>
    … …  
    6064
    6165    ///\name Comparisons
    62     ///The concept is that these bool functions return \c true only if
     66    ///The concept is that these bool functions return with \c true only if
    6367    ///the related comparisons hold even if some numerical error appeared
    6468    ///during the computations.
    … …  
    8892
    8993
    90   ///Float specialization of Tolerance.
    91 
    92   ///Float specialization of Tolerance.
     94  ///Float specialization of \ref Tolerance.
     95
     96  ///Float specialization of \ref Tolerance.
    9397  ///\sa Tolerance
    9498  ///\relates Tolerance
    … …  
    104108    ///Constructor setting the epsilon tolerance to the default value.
    105109    Tolerance() : _epsilon(def_epsilon) {}
    106     ///Constructor setting the epsilon tolerance to the given value.
     110    ///Constructor setting the epsilon tolerance.
    107111    Tolerance(float e) : _epsilon(e) {}
    108112
    109     ///Returns the epsilon value.
     113    ///Return the epsilon value.
    110114    Value epsilon() const {return _epsilon;}
    111     ///Sets the epsilon value.
     115    ///Set the epsilon value.
    112116    void epsilon(Value e) {_epsilon=e;}
    113117
    114     ///Returns the default epsilon value.
     118    ///Return the default epsilon value.
    115119    static Value defaultEpsilon() {return def_epsilon;}
    116     ///Sets the default epsilon value.
     120    ///Set the default epsilon value.
    117121    static void defaultEpsilon(Value e) {def_epsilon=e;}
    118122
    119123    ///\name Comparisons
    120     ///See \ref Tolerance for more details.
     124    ///See class Tolerance for more details.
    121125
    122126    ///@{
    … …  
    139143  };
    140144
    141   ///Double specialization of Tolerance.
    142 
    143   ///Double specialization of Tolerance.
     145  ///Double specialization of \ref Tolerance.
     146
     147  ///Double specialization of \ref Tolerance.
    144148  ///\sa Tolerance
    145149  ///\relates Tolerance
    … …  
    155159    ///Constructor setting the epsilon tolerance to the default value.
    156160    Tolerance() : _epsilon(def_epsilon) {}
    157     ///Constructor setting the epsilon tolerance to the given value.
     161    ///Constructor setting the epsilon tolerance.
    158162    Tolerance(double e) : _epsilon(e) {}
    159163
    160     ///Returns the epsilon value.
     164    ///Return the epsilon value.
    161165    Value epsilon() const {return _epsilon;}
    162     ///Sets the epsilon value.
     166    ///Set the epsilon value.
    163167    void epsilon(Value e) {_epsilon=e;}
    164168
    165     ///Returns the default epsilon value.
     169    ///Return the default epsilon value.
    166170    static Value defaultEpsilon() {return def_epsilon;}
    167     ///Sets the default epsilon value.
     171    ///Set the default epsilon value.
    168172    static void defaultEpsilon(Value e) {def_epsilon=e;}
    169173
    170174    ///\name Comparisons
    171     ///See \ref Tolerance for more details.
     175    ///See class Tolerance for more details.
    172176
    173177    ///@{
    … …  
    190194  };
    191195
    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.
    195199  ///\sa Tolerance
    196200  ///\relates Tolerance
    … …  
    206210    ///Constructor setting the epsilon tolerance to the default value.
    207211    Tolerance() : _epsilon(def_epsilon) {}
    208     ///Constructor setting the epsilon tolerance to the given value.
     212    ///Constructor setting the epsilon tolerance.
    209213    Tolerance(long double e) : _epsilon(e) {}
    210214
    211     ///Returns the epsilon value.
     215    ///Return the epsilon value.
    212216    Value epsilon() const {return _epsilon;}
    213     ///Sets the epsilon value.
     217    ///Set the epsilon value.
    214218    void epsilon(Value e) {_epsilon=e;}
    215219
    216     ///Returns the default epsilon value.
     220    ///Return the default epsilon value.
    217221    static Value defaultEpsilon() {return def_epsilon;}
    218     ///Sets the default epsilon value.
     222    ///Set the default epsilon value.
    219223    static void defaultEpsilon(Value e) {def_epsilon=e;}
    220224
    221225    ///\name Comparisons
    222     ///See \ref Tolerance for more details.
     226    ///See class Tolerance for more details.
    223227
    224228    ///@{
    … …  
    241245  };
    242246
    243   ///Integer specialization of Tolerance.
    244 
    245   ///Integer specialization of Tolerance.
     247  ///Integer specialization of \ref Tolerance.
     248
     249  ///Integer specialization of \ref Tolerance.
    246250  ///\sa Tolerance
    247251  template<>
    … …  
    274278  };
    275279
    276   ///Unsigned integer specialization of Tolerance.
    277 
    278280  ///Unsigned integer specialization of \ref Tolerance.
     281
     282  ///Unsigned integer specialization of \ref Tolerance.
    279283  ///\sa Tolerance
    280284  template<>
    … …  
    308312 
    309313
    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.
    313317  ///\sa Tolerance
    314318  template<>
    … …  
    341345  };
    342346
    343   ///Unsigned long integer specialization of Tolerance.
    344 
    345347  ///Unsigned long integer specialization of \ref Tolerance.
     348
     349  ///Unsigned long integer specialization of \ref Tolerance.
    346350  ///\sa Tolerance
    347351  template<>
    … …  
    376380#if defined __GNUC__ && !defined __STRICT_ANSI__
    377381
    378   ///Long long integer specialization of Tolerance.
     382  ///Long long integer specialization of \ref Tolerance.
    379383
    380384  ///Long long integer specialization of \ref Tolerance.
    … …  
    411415  };
    412416
    413   ///Unsigned long long integer specialization of Tolerance.
     417  ///Unsigned long long integer specialization of \ref Tolerance.
    414418
    415419  ///Unsigned long long integer specialization of \ref Tolerance.

  • test/Makefile.am

    r67 r65  
    33
    44noinst_HEADERS += \
    5         test/digraph_test.h \
    6         test/map_test.h \
    75        test/test_tools.h
    86
    97check_PROGRAMS += \
    10         test/digraph_test \
    118        test/dim_test \
    12         test/graph_test \
    139        test/maps_test \
    1410        test/random_test \
    … …  
    1915XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
    2016
    21 test_digraph_test_SOURCES = test/digraph_test.cc
    2217test_dim_test_SOURCES = test/dim_test.cc
    23 #test_error_test_SOURCES = test/error_test.cc
    24 test_graph_test_SOURCES = test/graph_test.cc
    2518test_maps_test_SOURCES = test/maps_test.cc
    2619test_random_test_SOURCES = test/random_test.cc

  • test/dim_test.cc

    r39 r14  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2007
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • test/maps_test.cc

    r39 r25  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2007
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • test/random_test.cc

    r39 r10  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2007
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • test/test_tools.h

    r39 r4  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2007
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • test/test_tools_fail.cc

    r39 r4  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2007
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • test/test_tools_pass.cc

    r39 r4  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2007
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
Note: See TracChangeset for help on using the changeset viewer.