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 / [65:bfbc57a51fbb:67:9de02aa380de] in lemon-1.0


Ignore:
Files:
25 added
21 edited

Legend:

Unmodified
Added
Removed

  • configure.ac

    r21 r64  
    33dnl Version information.
    44m4_define([lemon_version_major], [0])
    5 m4_define([lemon_version_minor], [6])
    6 m4_define([lemon_version_micro], [90])
     5m4_define([lemon_version_minor], [99])
     6m4_define([lemon_version_micro], [])
    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])
     16AM_INIT_AUTOMAKE([-Wall -Werror foreign subdir-objects nostdinc])
    1717AC_CONFIG_SRCDIR([lemon/list_graph.h])
    1818AC_CONFIG_HEADERS([config.h lemon/config.h])
    … …  
    2727AC_PROG_LIBTOOL
    2828
     29AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
     30
    2931if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes; then
    3032  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"
    3133fi
    32 
    33 AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
    3434
    3535dnl Checks for libraries.
    … …  
    3737LX_CHECK_CPLEX
    3838LX_CHECK_SOPLEX
    39 
    40 dnl Enable/disable installing the documentation
    41 AC_ARG_ENABLE([doc],
    42 AS_HELP_STRING([--enable-doc@<:@=yes|no|full@:>@], [build the documentation (full enables internal documentation too) @<:@default=yes@:>@])
    43 AS_HELP_STRING([--disable-doc], [do not build the documentation]),
    44               [], [enable_doc=yes])
    45 
    46 AC_MSG_CHECKING([whether to build the documention])
    47 case "$enable_doc" in
    48   yes)
    49     DOXYGEN_INTERNAL_DOCS=NO
    50     AC_MSG_RESULT([yes])
    51     ;;
    52   full)
    53     DOXYGEN_INTERNAL_DOCS=YES
    54     AC_MSG_RESULT([full])
    55     ;;
    56   no)
    57     DOXYGEN_INTERNAL_DOCS=NO
    58     AC_MSG_RESULT([no])
    59     ;;
    60   *)
    61     AC_MSG_ERROR([bad value $enable_doc for option --enable-doc])
    62     ;;
    63 esac
    64 AC_SUBST(DOXYGEN_INTERNAL_DOCS)
    65 AM_CONDITIONAL([WANT_DOC], [test x"$enable_doc" != x"no"])
    6639
    6740dnl Disable/enable building the demo programs
    … …  
    138111echo SOPLEX support................ : $lx_soplex_found
    139112echo
    140 echo build benchmarks.............. : $enable_benchmark
    141 echo build demo programs........... : $enable_demo
    142 echo build additional tools........ : $enable_tools
     113echo Build benchmarks.............. : $enable_benchmark
     114echo Build demo programs........... : $enable_demo
     115echo Build additional tools........ : $enable_tools
    143116echo
    144117echo The packace will be installed in
    … …  
    146119echo $prefix.
    147120echo
    148 echo The documentation will be installed in
    149 echo -n '  '
    150 eval echo ${datadir}/doc/$PACKAGE.
    151 echo
    152121echo '*********************************************************************'
    153122
    154123echo
    155 echo configure complete, now type \'make\' and then \'make install\'.
     124echo Configure complete, now type \'make\' and then \'make install\'.
    156125echo

  • doc/Makefile.am

    r2 r60  
    1 htmldir = $(datadir)/doc/$(PACKAGE)/html
    2 
    31EXTRA_DIST += \
    42        doc/Makefile \
    5         doc/Doxyfile.in
     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
    611
    7 doc:
     12doc/html:
     13        $(MAKE) $(AM_MAKEFLAGS) html
     14
     15html-local:
    816        if test ${doxygen_found} = yes; then \
    917          cd doc; \
    1018          doxygen Doxyfile; \
    1119          cd ..; \
    12         fi
    13 
    14 doc-clean:
    15         if test ${doxygen_found} = yes; then \
    16           rm -rf doc/html; \
    17           rm -f doc/doxygen.log; \
    18           cd doc; \
    19           doxygen Doxyfile; \
    20           cd ..; \
     20        else \
     21          echo; \
     22          echo "Doxygen not found."; \
     23          echo; \
     24          exit 1; \
    2125        fi
    2226
    … …  
    2529        -rm -f doc/doxygen.log
    2630
    27 doc/html:
    28         $(MAKE) $(AM_MAKEFLAGS) doc-clean
     31update-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
    2935
    30 if WANT_DOC
    31 
    32 install-data-local: doc/html
     36install-html-local: doc/html
    3337        @$(NORMAL_INSTALL)
    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 \
     38        $(mkinstalldirs) $(DESTDIR)$(htmldir)/docs
     39        for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
    3640          f="`echo $$p | sed -e 's|^.*/||'`"; \
    37           echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/$$f"; \
    38           $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/$$f; \
     41          echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f"; \
     42          $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f; \
    3943        done
    4044
    41 uninstall-local: doc/html
     45uninstall-local:
    4246        @$(NORMAL_UNINSTALL)
    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 \
     47        for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
    4448          f="`echo $$p | sed -e 's|^.*/||'`"; \
    45           echo " rm -f $(DESTDIR)$(htmldir)/$$f"; \
    46           rm -f $(DESTDIR)$(htmldir)/$$f; \
     49          echo " rm -f $(DESTDIR)$(htmldir)/docs/$$f"; \
     50          rm -f $(DESTDIR)$(htmldir)/docs/$$f; \
    4751        done
    4852
    49 endif WANT_DOC
    50 
    51 .PHONY: doc doc-clean
     53.PHONY: update-external-tags

  • lemon/Makefile.am

    r65 r67  
    1818        lemon/concept_check.h \
    1919        lemon/dim2.h \
     20        lemon/error.h \
     21        lemon/list_graph.h \
     22        lemon/maps.h \
    2023        lemon/random.h \
    21         lemon/list_graph.h \
    22         lemon/maps.h \
    2324        lemon/tolerance.h
    2425
    2526bits_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 \
    2632        lemon/bits/invalid.h \
    27         lemon/bits/utility.h
     33        lemon/bits/map_extender.h \
     34        lemon/bits/traits.h \
     35        lemon/bits/utility.h \
     36        lemon/bits/vector_map.h
    2837
    2938concept_HEADERS += \
    30         lemon/concepts/maps.h
     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

  • lemon/base.cc

    r7 r49  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2007
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    1818
    1919///\file
    20 ///\brief Some basic non inline function and static global data.
     20///\brief Some basic non-inline functions and static global data.
    2121
    2222#include<lemon/tolerance.h>

  • lemon/bits/invalid.h

    r13 r49  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2007
     5 * Copyright (C) 2003-2008
    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.
    2930  /// See \ref INVALID for the usage.
    3031  struct Invalid {

  • lemon/bits/utility.h

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

  • lemon/concept_check.h

    r27 r53  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2007
     5 * Copyright (C) 2003-2008
    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 #ifndef LEMON_CONCEPT_CHECKS_H
    37 #define LEMON_CONCEPT_CHECKS_H
     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
    3844
    3945namespace lemon {
    … …  
    4753  template <class T> inline void ignore_unused_variable_warning(const T&) { }
    4854
     55  ///\e
    4956  template <class Concept>
    5057  inline void function_requires()
    … …  
    5663  }
    5764
     65  ///\e
    5866  template <typename Concept, typename Type>
    5967  inline void checkConcept() {
    … …  
    6573  }
    6674
    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 
    10375} // namespace lemon
    10476
    105 #endif // LEMON_CONCEPT_CHECKS_H
     77#endif // LEMON_CONCEPT_CHECK_H

  • lemon/concepts/maps.h

    r28 r51  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2007
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    4242    {
    4343    public:
    44       /// Map's key type.
    45       typedef K Key;   
    46       /// Map's value type. (The type of objects associated with the keys).
     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).
    4747      typedef T Value;
    4848
    4949      /// Returns the value associated with a key.
    5050
     51      /// Returns the value associated with a key.
    5152      /// \bug Value shouldn't need to be default constructible.
    5253      ///
    … …  
    8283    {
    8384    public:
    84       /// Map's key type.
    85       typedef K Key;   
    86       /// Map's value type. (The type of objects associated with the keys).
     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).
    8788      typedef T Value;
    8889
    … …  
    114115    };
    115116
    116     /// Read/Writable map concept
     117    /// Read/writable map concept
    117118   
    118119    /// Read/writable map concept.
    … …  
    120121    template<typename K, typename T>
    121122    class ReadWriteMap : public ReadMap<K,T>,
    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).
     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).
    128129      typedef T Value;
    129130
    … …  
    147148    /// Dereferable map concept.
    148149    ///
     150    /// \todo Rethink this concept.
    149151    template<typename K, typename T, typename R, typename CR>
    150152    class ReferenceMap : public ReadWriteMap<K,T>
    … …  
    153155      /// Tag for reference maps.
    154156      typedef True ReferenceMapTag;
    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.
     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.
    160162      typedef R Reference;
    161       /// Map's const reference type.
     163      /// The const reference type of the map.
    162164      typedef CR ConstReference;
    163165
    … …  
    166168    public:
    167169
    168       ///Returns a reference to the value associated to a key.
     170      ///Returns a reference to the value associated with a key.
    169171      Reference operator[](const Key &) { return tmp; }
    170       ///Returns a const reference to the value associated to a key.
     172      ///Returns a const reference to the value associated with a key.
    171173      ConstReference operator[](const Key &) const { return tmp; }
    172174      /// Sets the value associated with a key.
    173175      void set(const Key &k,const Value &t) { operator[](k)=t; }
    174176
    175       /// \todo Rethink this concept.
    176177      template<typename _ReferenceMap>
    177178      struct ReferenceMapConcept {

  • lemon/dim2.h

    r15 r49  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2007
     5 * Copyright (C) 2003-2008
    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
    31 /// operations.
     30/// a two dimensional vector with the usual operations.
    3231///
    3332/// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox"
    … …  
    5049
    5150  /// A simple two dimensional vector (plainvector) implementation
    52   ///with the usual vector
    53   /// operators.
    54   ///
     51  /// with the usual vector operations.
    5552  template<typename T>
    5653    class Point {
    … …  
    7168      Point(T a, T b) : x(a), y(b) { }
    7269
    73       ///The dimension of the vector.
     70      ///Returns the dimension of the vector (i.e. returns 2).
    7471
    7572      ///The dimension of the vector.
    … …  
    9794      }
    9895 
    99       ///Increment the left hand side by u
     96      ///Increment the left hand side by \c u
    10097      Point<T>& operator +=(const Point<T>& u) {
    10198        x += u.x;
    … …  
    104101      }
    105102 
    106       ///Decrement the left hand side by u
     103      ///Decrement the left hand side by \c u
    107104      Point<T>& operator -=(const Point<T>& u) {
    108105        x -= u.x;
    … …  
    316313      ///if at least one point was added to the box or the coordinates of
    317314      ///the box were set).
     315      ///
    318316      ///The coordinates of an empty bounding box are not defined.
    319317      bool empty() const {
    … …  
    326324      }
    327325
    328       ///Give back the bottom left corner
    329 
    330       ///Give back the bottom left corner.
     326      ///Give back the bottom left corner of the box
     327
     328      ///Give back the bottom left corner of the box.
    331329      ///If the bounding box is empty, then the return value is not defined.
    332330      Point<T> bottomLeft() const {
    … …  
    334332      }
    335333
    336       ///Set the bottom left corner
    337 
    338       ///Set the bottom left corner.
     334      ///Set the bottom left corner of the box
     335
     336      ///Set the bottom left corner of the box.
    339337      ///It should only be used for non-empty box.
    340338      void bottomLeft(Point<T> p) {
    … …  
    342340      }
    343341
    344       ///Give back the top right corner
    345 
    346       ///Give back the top right corner.
     342      ///Give back the top right corner of the box
     343
     344      ///Give back the top right corner of the box.
    347345      ///If the bounding box is empty, then the return value is not defined.
    348346      Point<T> topRight() const {
    … …  
    350348      }
    351349
    352       ///Set the top right corner
    353 
    354       ///Set the top right corner.
     350      ///Set the top right corner of the box
     351
     352      ///Set the top right corner of the box.
    355353      ///It should only be used for non-empty box.
    356354      void topRight(Point<T> p) {
    … …  
    358356      }
    359357
    360       ///Give back the bottom right corner
    361 
    362       ///Give back the bottom right corner.
     358      ///Give back the bottom right corner of the box
     359
     360      ///Give back the bottom right corner of the box.
    363361      ///If the bounding box is empty, then the return value is not defined.
    364362      Point<T> bottomRight() const {
    … …  
    366364      }
    367365
    368       ///Set the bottom right corner
    369 
    370       ///Set the bottom right corner.
     366      ///Set the bottom right corner of the box
     367
     368      ///Set the bottom right corner of the box.
    371369      ///It should only be used for non-empty box.
    372370      void bottomRight(Point<T> p) {
    … …  
    375373      }
    376374 
    377       ///Give back the top left corner
    378 
    379       ///Give back the top left corner.
     375      ///Give back the top left corner of the box
     376
     377      ///Give back the top left corner of the box.
    380378      ///If the bounding box is empty, then the return value is not defined.
    381379      Point<T> topLeft() const {
    … …  
    383381      }
    384382
    385       ///Set the top left corner
    386 
    387       ///Set the top left corner.
     383      ///Set the top left corner of the box
     384
     385      ///Set the top left corner of the box.
    388386      ///It should only be used for non-empty box.
    389387      void topLeft(Point<T> p) {
    … …  
    669667
    670668
    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     ///
     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
    678675  template<class M>
    679676  class NormSquareMap

  • lemon/list_graph.h

    r2 r57  
     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
     31namespace 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

    r30 r54  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2007
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    4545  class MapBase {
    4646  public:
    47     ///\e
     47    /// The key type of the map.
    4848    typedef K Key;
    49     ///\e
     49    /// The value type of the map. (The type of objects associated with the keys).
    5050    typedef T Value;
    5151  };
    … …  
    8282  /// Constant map.
    8383
    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.
     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.
    8687  template<typename K, typename T>
    8788  class ConstMap : public MapBase<K, T> {
    … …  
    116117
    117118    template<typename T1>
    118     struct rebind {
    119       typedef ConstMap<K, T1> other;
    120     };
    121 
    122     template<typename T1>
    123119    ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {}
    124120  };
    … …  
    139135  /// Constant map with inlined constant value.
    140136
    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.
     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.
    143140  template<typename K, typename V, V v>
    144141  class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
    … …  
    155152  };
    156153
    157   ///Returns a \c ConstMap class
     154  ///Returns a \c ConstMap class with inlined value
    158155
    159156  ///This function just returns a \c ConstMap class with inlined value.
    … …  
    164161  }
    165162
    166   ///Map based on std::map
     163  ///Map based on \c std::map
    167164
    168165  ///This is essentially a wrapper for \c std::map with addition that
    169166  ///you can specify a default value different from \c Value().
     167  ///It meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
    170168  template <typename K, typename T, typename Compare = std::less<K> >
    171   class StdMap {
     169  class StdMap : public MapBase<K, T> {
    172170    template <typename K1, typename T1, typename C1>
    173171    friend class StdMap;
    174172  public:
    175173
     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
     180    typedef T& Reference;
     181    ///Const reference type
     182    typedef const T& ConstReference;
     183
    176184    typedef True ReferenceMapTag;
    177     ///\e
    178     typedef K Key;
    179     ///\e
    180     typedef T Value;
    181     ///\e
    182     typedef T& Reference;
    183     ///\e
    184     typedef const T& ConstReference;
    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 std::map, and explicitly
    197     /// specifies a default value.
     196    /// \brief Constructs the map from an appropriate \c std::map, and
     197    /// explicitly 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 StdMap.
     202    /// \brief Constructs a map from an other \ref StdMap.
    203203    template<typename T1, typename Comp1>
    204204    StdMap(const StdMap<Key, T1, Comp1> &c)
    … …  
    244244    }   
    245245
    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
     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
    255293  /// are stored in a \c std::vector<T>  container. It can be used with
    256294  /// some data structures, for example \c UnionFind, \c BinHeap, when
    257   /// the used items are small integer numbers.
     295  /// the used items are small integer numbers.
     296  /// This map meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
    258297  ///
    259298  /// \todo Revise its name
    260299  template <typename T>
    261   class IntegerMap {
     300  class IntegerMap : public MapBase<int, T> {
    262301
    263302    template <typename T1>
    … …  
    266305  public:
    267306
     307    typedef MapBase<int, T> Parent;
     308    ///\e
     309    typedef typename Parent::Key Key;
     310    ///\e
     311    typedef typename Parent::Value Value;
     312    ///\e
     313    typedef T& Reference;
     314    ///\e
     315    typedef const T& ConstReference;
     316
    268317    typedef True ReferenceMapTag;
    269     ///\e
    270     typedef int Key;
    271     ///\e
    272     typedef T Value;
    273     ///\e
    274     typedef T& Reference;
    275     ///\e
    276     typedef const T& ConstReference;
    277318
    278319  private:
    … …  
    286327    IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
    287328
    288     /// \brief Constructs the map from an appropriate std::vector.
     329    /// \brief Constructs the map from an appropriate \c std::vector.
    289330    template <typename T1>
    290331    IntegerMap(const std::vector<T1>& vector)
    291332      : _vector(vector.begin(), vector.end()) {}
    292333   
    293     /// \brief Constructs a map from an other IntegerMap.
     334    /// \brief Constructs a map from an other \ref IntegerMap.
    294335    template <typename T1>
    295336    IntegerMap(const IntegerMap<T1> &c)
    … …  
    323364
    324365  };
     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  }
    325375
    326376  /// @}
    … …  
    359409  ///the default conversion.
    360410  ///
    361   ///This \c concepts::ReadMap "read only map"
     411  ///This \ref concepts::ReadMap "read only map"
    362412  ///converts the \c Value of a map to type \c T.
    363413  ///Its \c Key is inherited from \c M.
    … …  
    376426    ConvertMap(const M &_m) : m(_m) {};
    377427
    378     /// \brief The subscript operator.
    379     ///
    380     /// The subscript operator.
     428    ///\e
    381429    Value operator[](const Key& k) const {return m[k];}
    382430  };
    … …  
    393441  ///Simple wrapping of a map
    394442
    395   ///This \c concepts::ReadMap "read only map" returns the simple
     443  ///This \ref concepts::ReadMap "read only map" returns the simple
    396444  ///wrapping of the given map. Sometimes the reference maps cannot be
    397445  ///combined with simple read maps. This map adaptor wraps the given
    … …  
    415463    Value operator[](Key k) const {return m[k];}
    416464  };
    417 
    418   ///Simple writable wrapping of the map
    419 
    420   ///This \c concepts::WriteMap "write map" returns the simple
     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
    421478  ///wrapping of the given map. Sometimes the reference maps cannot be
    422479  ///combined with simple read-write maps. This map adaptor wraps the
    … …  
    443500  };
    444501
     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
    445511  ///Sum of two maps
    446512
    447   ///This \c concepts::ReadMap "read only map" returns the sum of the two
     513  ///This \ref concepts::ReadMap "read only map" returns the sum of the two
    448514  ///given maps.
    449515  ///Its \c Key and \c Value are inherited from \c M1.
    450   ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
     516  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
    451517  template<typename M1, typename M2>
    452518  class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
    … …  
    468534
    469535  ///This function just returns an \c AddMap class.
    470   ///\todo How to call these type of functions?
     536  ///\todo Extend the documentation: how to call these type of functions?
    471537  ///
    472538  ///\relates AddMap
    … …  
    478544  ///Shift a map with a constant.
    479545
    480   ///This \c concepts::ReadMap "read only map" returns the sum of the
     546  ///This \ref concepts::ReadMap "read only map" returns the sum of the
    481547  ///given map and a constant value.
    482548  ///Its \c Key and \c Value are inherited from \c M.
    … …  
    514580  ///Shift a map with a constant (ReadWrite version).
    515581
    516   ///This \c concepts::ReadWriteMap "read-write map" returns the sum of the
     582  ///This \ref concepts::ReadWriteMap "read-write map" returns the sum of the
    517583  ///given map and a constant value. It makes also possible to write the map.
    518584  ///Its \c Key and \c Value are inherited from \c M.
    … …  
    560626  ///Difference of two maps
    561627
    562   ///This \c concepts::ReadMap "read only map" returns the difference
     628  ///This \ref concepts::ReadMap "read only map" returns the difference
    563629  ///of the values of the two given maps.
    564630  ///Its \c Key and \c Value are inherited from \c M1.
    … …  
    593659  ///Product of two maps
    594660
    595   ///This \c concepts::ReadMap "read only map" returns the product of the
     661  ///This \ref concepts::ReadMap "read only map" returns the product of the
    596662  ///values of the two given maps.
    597663  ///Its \c Key and \c Value are inherited from \c M1.
    … …  
    623689  ///Scales a map with a constant.
    624690
    625   ///This \c concepts::ReadMap "read only map" returns the value of the
     691  ///This \ref concepts::ReadMap "read only map" returns the value of the
    626692  ///given map multiplied from the left side with a constant value.
    627693  ///Its \c Key and \c Value are inherited from \c M.
    … …  
    659725  ///Scales a map with a constant (ReadWrite version).
    660726
    661   ///This \c concepts::ReadWriteMap "read-write map" returns the value of the
     727  ///This \ref concepts::ReadWriteMap "read-write map" returns the value of the
    662728  ///given map multiplied from the left side with a constant value. It can
    663729  ///also be used as write map if the \c / operator is defined between
    … …  
    707773  ///Quotient of two maps
    708774
    709   ///This \c concepts::ReadMap "read only map" returns the quotient of the
     775  ///This \ref concepts::ReadMap "read only map" returns the quotient of the
    710776  ///values of the two given maps.
    711777  ///Its \c Key and \c Value are inherited from \c M1.
    … …  
    737803  ///Composition of two maps
    738804
    739   ///This \c concepts::ReadMap "read only map" returns the composition of
     805  ///This \ref concepts::ReadMap "read only map" returns the composition of
    740806  ///two given maps.
    741807  ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2,
    … …  
    788854  ///Combine of two maps using an STL (binary) functor.
    789855  ///
    790   ///This \c concepts::ReadMap "read only map" takes two maps and a
     856  ///This \ref concepts::ReadMap "read only map" takes two maps and a
    791857  ///binary functor and returns the composition of the two
    792858  ///given maps unsing the functor.
    … …  
    830896  ///For example if \c m1 and \c m2 are both \c double valued maps, then
    831897  ///\code
    832   ///combineMap<double>(m1,m2,std::plus<double>())
     898  ///combineMap(m1,m2,std::plus<double>())
    833899  ///\endcode
    834900  ///is equivalent to
    … …  
    861927  ///Negative value of a map
    862928
    863   ///This \c concepts::ReadMap "read only map" returns the negative
     929  ///This \ref concepts::ReadMap "read only map" returns the negative
    864930  ///value of the value returned by the given map.
    865931  ///Its \c Key and \c Value are inherited from \c M.
    … …  
    883949  ///Negative value of a map (ReadWrite version)
    884950
    885   ///This \c concepts::ReadWriteMap "read-write map" returns the negative
     951  ///This \ref concepts::ReadWriteMap "read-write map" returns the negative
    886952  ///value of the value returned by the given map.
    887953  ///Its \c Key and \c Value are inherited from \c M.
    … …  
    925991  ///Absolute value of a map
    926992
    927   ///This \c concepts::ReadMap "read only map" returns the absolute value
     993  ///This \ref concepts::ReadMap "read only map" returns the absolute value
    928994  ///of the value returned by the given map.
    929995  ///Its \c Key and \c Value are inherited from \c M.
    … …  
    9591025  ///Converts an STL style functor to a map
    9601026
    961   ///This \c concepts::ReadMap "read only map" returns the value
     1027  ///This \ref concepts::ReadMap "read only map" returns the value
    9621028  ///of a given functor.
    9631029  ///
    9641030  ///Template parameters \c K and \c V will become its
    965   ///\c Key and \c Value. They must be given explicitly
    966   ///because a functor does not provide such typedefs.
     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.
    9671035  ///
    9681036  ///Parameter \c F is the type of the used functor.
    … …  
    9891057  ///This function just returns a \c FunctorMap class.
    9901058  ///
    991   ///It is specialized for adaptable function classes and
    992   ///C++ functions.
     1059  ///This function is specialized for adaptable binary function
     1060  ///classes and C++ functions.
     1061  ///
    9931062  ///\relates FunctorMap
    9941063  template<typename K, typename V, typename F> inline
    … …  
    10131082
    10141083  ///This class Converts a map to an STL style (unary) functor.
    1015   ///that is it provides an <tt>operator()</tt> to read its values.
     1084  ///That is it provides an <tt>operator()</tt> to read its values.
    10161085  ///
    10171086  ///For the sake of convenience it also works as
    1018   ///a ususal \c concepts::ReadMap "readable map",
     1087  ///a ususal \ref concepts::ReadMap "readable map",
    10191088  ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
    10201089  ///
    … …  
    10481117  }
    10491118
    1050   ///Applies all map setting operations to two maps
    1051 
    1052   ///This map has two \c concepts::ReadMap "readable map"
     1119  ///Just readable version of \ref ForkWriteMap
     1120
     1121  ///This map has two \ref concepts::ReadMap "readable map"
    10531122  ///parameters and each read request will be passed just to the
    1054   ///first map. This class is the just readable map type of the ForkWriteMap.
     1123  ///first map. This class is the just readable map type of \c ForkWriteMap.
    10551124  ///
    10561125  ///The \c Key and \c Value are inherited from \c M1.
    1057   ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
     1126  ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
    10581127  ///
    10591128  ///\sa ForkWriteMap
    … …  
    10781147  ///Applies all map setting operations to two maps
    10791148
    1080   ///This map has two \c concepts::WriteMap "writable map"
     1149  ///This map has two \ref concepts::WriteMap "writable map"
    10811150  ///parameters and each write request will be passed to both of them.
    1082   ///If \c M1 is also \c concepts::ReadMap "readable",
     1151  ///If \c M1 is also \ref concepts::ReadMap "readable",
    10831152  ///then the read operations will return the
    10841153  ///corresponding values of \c M1.
    10851154  ///
    10861155  ///The \c Key and \c Value are inherited from \c M1.
    1087   ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
     1156  ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
    10881157  ///
    10891158  ///\sa ForkMap
    … …  
    11291198  ///Logical 'not' of a map
    11301199 
    1131   ///This bool \c concepts::ReadMap "read only map" returns the
     1200  ///This bool \ref concepts::ReadMap "read only map" returns the
    11321201  ///logical negation of the value returned by the given map.
    1133   ///Its \c Key is inherited from \c M, its Value is \c bool.
     1202  ///Its \c Key is inherited from \c M, its \c Value is \c bool.
    11341203  ///
    11351204  ///\sa NotWriteMap
    … …  
    11501219  ///Logical 'not' of a map (ReadWrie version)
    11511220 
    1152   ///This bool \c concepts::ReadWriteMap "read-write map" returns the
     1221  ///This bool \ref concepts::ReadWriteMap "read-write map" returns the
    11531222  ///logical negation of the value returned by the given map. When it is set,
    11541223  ///the opposite value is set to the original map.
    1155   ///Its \c Key is inherited from \c M, its Value is \c bool.
     1224  ///Its \c Key is inherited from \c M, its \c Value is \c bool.
    11561225  ///
    11571226  ///\sa NotMap
    … …  
    12181287  /// \brief Writable bool map for logging each \c true assigned element
    12191288  ///
    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.
     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.
    12221292  ///
    12231293  /// \note The container of the iterator should contain space
    12241294  /// for each element.
    12251295  ///
    1226   /// The following example shows how you can write the edges found by the Prim
    1227   /// algorithm directly
    1228   /// to the standard output.
     1296  /// The following example shows how you can write the edges found by
     1297  /// the \ref Prim algorithm directly to the standard output.
    12291298  ///\code
    12301299  /// typedef IdMap<Graph, Edge> EdgeIdMap;
    … …  
    12411310  ///
    12421311  ///\sa BackInserterBoolMap
     1312  ///\sa FrontInserterBoolMap
     1313  ///\sa InserterBoolMap
    12431314  ///
    12441315  ///\todo Revise the name of this class and the related ones.
    … …  
    13061377  class BackInserterBoolMap {
    13071378  public:
    1308     typedef typename Container::value_type Key;
     1379    typedef typename Functor::argument_type Key;
    13091380    typedef bool Value;
    13101381
    … …  
    13411412  class FrontInserterBoolMap {
    13421413  public:
    1343     typedef typename Container::value_type Key;
     1414    typedef typename Functor::argument_type Key;
    13441415    typedef bool Value;
    13451416
    … …  
    15511622    }
    15521623
    1553     /// Setter function of the map
     1624    /// The \c set function of the map
    15541625    void set(const Key& key, Value value) {
    15551626      if (value) {

  • lemon/random.cc

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

  • lemon/random.h

    r23 r62  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2007
     5 * Copyright (C) 2003-2008
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    255255          --curr;
    256256        }
    257         curr[0] = (((curr[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^
     257        state[0] = (((state[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^
    258258          curr[length - shift] ^ mask[curr[length - 1] & 1ul];
    259259
    … …  
    511511  ///\endcode
    512512  ///
    513   /// The lemon provides a global instance of the random number
     513  /// 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 Constructor
     529    /// \brief Default constructor
    530530    ///
    531531    /// Constructor with constant seeding.
    532532    Random() { core.initState(); }
    533533
    534     /// \brief Constructor
     534    /// \brief Constructor with seed
    535535    ///
    536536    /// Constructor with seed. The current number type will be converted
    … …  
    541541    }
    542542
    543     /// \brief Constructor
     543    /// \brief Constructor with array seeding
    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 double.
     580    /// default Number type is \c 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 unsigned int.
     656    /// whole range of the current \c Number type. The default result
     657    /// type of this function is <tt>unsigned int</tt>.
    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 int.
     671    /// function is \c int.
    672672    template <typename Number>
    673673    Number integer() {
    … …  
    690690    }
    691691
    692     ///\name Nonuniform distributions
     692    ///\name Non-uniform distributions
    693693    ///
    694694   

  • lemon/tolerance.h

    r16 r49  
    33 * This file is a part of LEMON, a generic C++ optimization library
    44 *
    5  * Copyright (C) 2003-2007
     5 * Copyright (C) 2003-2008
    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   ///Tolerance is a class to provide a basic way to
     39  ///\ref 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__ 
    5251  ///\sa Tolerance<long long int>
    53 #endif
    5452  ///\sa Tolerance<unsigned int>
    55 #if defined __GNUC__ && !defined __STRICT_ANSI__ 
    5653  ///\sa Tolerance<unsigned long long int>
    57 #endif
    5854
    5955  template<class T>
    … …  
    6460
    6561    ///\name Comparisons
    66     ///The concept is that these bool functions return with \c true only if
     62    ///The concept is that these bool functions return \c true only if
    6763    ///the related comparisons hold even if some numerical error appeared
    6864    ///during the computations.
    … …  
    9288
    9389
    94   ///Float specialization of \ref Tolerance.
    95 
    96   ///Float specialization of \ref Tolerance.
     90  ///Float specialization of Tolerance.
     91
     92  ///Float specialization of Tolerance.
    9793  ///\sa Tolerance
    9894  ///\relates Tolerance
    … …  
    108104    ///Constructor setting the epsilon tolerance to the default value.
    109105    Tolerance() : _epsilon(def_epsilon) {}
    110     ///Constructor setting the epsilon tolerance.
     106    ///Constructor setting the epsilon tolerance to the given value.
    111107    Tolerance(float e) : _epsilon(e) {}
    112108
    113     ///Return the epsilon value.
     109    ///Returns the epsilon value.
    114110    Value epsilon() const {return _epsilon;}
    115     ///Set the epsilon value.
     111    ///Sets the epsilon value.
    116112    void epsilon(Value e) {_epsilon=e;}
    117113
    118     ///Return the default epsilon value.
     114    ///Returns the default epsilon value.
    119115    static Value defaultEpsilon() {return def_epsilon;}
    120     ///Set the default epsilon value.
     116    ///Sets the default epsilon value.
    121117    static void defaultEpsilon(Value e) {def_epsilon=e;}
    122118
    123119    ///\name Comparisons
    124     ///See class Tolerance for more details.
     120    ///See \ref Tolerance for more details.
    125121
    126122    ///@{
    … …  
    143139  };
    144140
    145   ///Double specialization of \ref Tolerance.
    146 
    147   ///Double specialization of \ref Tolerance.
     141  ///Double specialization of Tolerance.
     142
     143  ///Double specialization of Tolerance.
    148144  ///\sa Tolerance
    149145  ///\relates Tolerance
    … …  
    159155    ///Constructor setting the epsilon tolerance to the default value.
    160156    Tolerance() : _epsilon(def_epsilon) {}
    161     ///Constructor setting the epsilon tolerance.
     157    ///Constructor setting the epsilon tolerance to the given value.
    162158    Tolerance(double e) : _epsilon(e) {}
    163159
    164     ///Return the epsilon value.
     160    ///Returns the epsilon value.
    165161    Value epsilon() const {return _epsilon;}
    166     ///Set the epsilon value.
     162    ///Sets the epsilon value.
    167163    void epsilon(Value e) {_epsilon=e;}
    168164
    169     ///Return the default epsilon value.
     165    ///Returns the default epsilon value.
    170166    static Value defaultEpsilon() {return def_epsilon;}
    171     ///Set the default epsilon value.
     167    ///Sets the default epsilon value.
    172168    static void defaultEpsilon(Value e) {def_epsilon=e;}
    173169
    174170    ///\name Comparisons
    175     ///See class Tolerance for more details.
     171    ///See \ref Tolerance for more details.
    176172
    177173    ///@{
    … …  
    194190  };
    195191
    196   ///Long double specialization of \ref Tolerance.
    197 
    198   ///Long double specialization of \ref Tolerance.
     192  ///Long double specialization of Tolerance.
     193
     194  ///Long double specialization of Tolerance.
    199195  ///\sa Tolerance
    200196  ///\relates Tolerance
    … …  
    210206    ///Constructor setting the epsilon tolerance to the default value.
    211207    Tolerance() : _epsilon(def_epsilon) {}
    212     ///Constructor setting the epsilon tolerance.
     208    ///Constructor setting the epsilon tolerance to the given value.
    213209    Tolerance(long double e) : _epsilon(e) {}
    214210
    215     ///Return the epsilon value.
     211    ///Returns the epsilon value.
    216212    Value epsilon() const {return _epsilon;}
    217     ///Set the epsilon value.
     213    ///Sets the epsilon value.
    218214    void epsilon(Value e) {_epsilon=e;}
    219215
    220     ///Return the default epsilon value.
     216    ///Returns the default epsilon value.
    221217    static Value defaultEpsilon() {return def_epsilon;}
    222     ///Set the default epsilon value.
     218    ///Sets the default epsilon value.
    223219    static void defaultEpsilon(Value e) {def_epsilon=e;}
    224220
    225221    ///\name Comparisons
    226     ///See class Tolerance for more details.
     222    ///See \ref Tolerance for more details.
    227223
    228224    ///@{
    … …  
    245241  };
    246242
    247   ///Integer specialization of \ref Tolerance.
    248 
    249   ///Integer specialization of \ref Tolerance.
     243  ///Integer specialization of Tolerance.
     244
     245  ///Integer specialization of Tolerance.
    250246  ///\sa Tolerance
    251247  template<>
    … …  
    278274  };
    279275
     276  ///Unsigned integer specialization of Tolerance.
     277
    280278  ///Unsigned integer specialization of \ref Tolerance.
    281 
    282   ///Unsigned integer specialization of \ref Tolerance.
    283279  ///\sa Tolerance
    284280  template<>
    … …  
    312308 
    313309
    314   ///Long integer specialization of \ref Tolerance.
    315 
    316   ///Long integer specialization of \ref Tolerance.
     310  ///Long integer specialization of Tolerance.
     311
     312  ///Long integer specialization of Tolerance.
    317313  ///\sa Tolerance
    318314  template<>
    … …  
    345341  };
    346342
     343  ///Unsigned long integer specialization of Tolerance.
     344
    347345  ///Unsigned long integer specialization of \ref Tolerance.
    348 
    349   ///Unsigned long integer specialization of \ref Tolerance.
    350346  ///\sa Tolerance
    351347  template<>
    … …  
    380376#if defined __GNUC__ && !defined __STRICT_ANSI__
    381377
    382   ///Long long integer specialization of \ref Tolerance.
     378  ///Long long integer specialization of Tolerance.
    383379
    384380  ///Long long integer specialization of \ref Tolerance.
    … …  
    415411  };
    416412
    417   ///Unsigned long long integer specialization of \ref Tolerance.
     413  ///Unsigned long long integer specialization of Tolerance.
    418414
    419415  ///Unsigned long long integer specialization of \ref Tolerance.

  • test/Makefile.am

    r65 r67  
    33
    44noinst_HEADERS += \
     5        test/digraph_test.h \
     6        test/map_test.h \
    57        test/test_tools.h
    68
    79check_PROGRAMS += \
     10        test/digraph_test \
    811        test/dim_test \
     12        test/graph_test \
    913        test/maps_test \
    1014        test/random_test \
    … …  
    1519XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
    1620
     21test_digraph_test_SOURCES = test/digraph_test.cc
    1722test_dim_test_SOURCES = test/dim_test.cc
     23#test_error_test_SOURCES = test/error_test.cc
     24test_graph_test_SOURCES = test/graph_test.cc
    1825test_maps_test_SOURCES = test/maps_test.cc
    1926test_random_test_SOURCES = test/random_test.cc

  • test/dim_test.cc

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

  • test/maps_test.cc

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

  • test/random_test.cc

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

  • test/test_tools.h

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

  • test/test_tools_fail.cc

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

  • test/test_tools_pass.cc

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