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 / [72:7050661bdea4:76:fc178a057bbd] in lemon


Ignore:
Files:
18 added
8 edited

Legend:

Unmodified
Added
Removed

  • Makefile.am

    r5 r70  
    11ACLOCAL_AMFLAGS = -I m4
    22
    3 AM_CPPFLAGS = -I$(top_srcdir)
     3AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)
    44LDADD = $(top_builddir)/lemon/libemon.la
    55

  • configure.ac

    r55 r64  
    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
    … …  
    146119echo $prefix.
    147120echo
    148 echo The documentation will be installed in
    149 echo -n '  '
    150 eval echo ${datadir}/doc/$PACKAGE.
    151 echo
    152121echo '*********************************************************************'
    153122

  • 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

    r32 r69  
    1616
    1717lemon_HEADERS += \
     18        lemon/concept_check.h \
    1819        lemon/dim2.h \
     20        lemon/error.h \
     21        lemon/list_graph.h \
     22        lemon/maps.h \
     23        lemon/math.h \
    1924        lemon/random.h \
    20         lemon/list_graph.h \
    2125        lemon/tolerance.h
    2226
    2327bits_HEADERS += \
     28        lemon/bits/alteration_notifier.h \
     29        lemon/bits/array_map.h \
     30        lemon/bits/base_extender.h \
     31        lemon/bits/default_map.h \
     32        lemon/bits/graph_extender.h \
    2433        lemon/bits/invalid.h \
    25         lemon/bits/utility.h
     34        lemon/bits/map_extender.h \
     35        lemon/bits/traits.h \
     36        lemon/bits/utility.h \
     37        lemon/bits/vector_map.h
    2638
    27 concept_HEADERS +=
     39concept_HEADERS += \
     40        lemon/concept_check.h \
     41        lemon/concepts/digraph.h \
     42        lemon/concepts/graph.h \
     43        lemon/concepts/maps.h \
     44        lemon/concepts/graph_components.h

  • lemon/concepts/maps.h

    r51 r74  
    5656      template<typename _ReadMap>
    5757      struct Constraints {
    58 
    5958        void constraints() {
    6059          Value val = m[key];
    … …  
    176175
    177176      template<typename _ReferenceMap>
    178       struct ReferenceMapConcept {
    179 
    180         void constraints() {
    181           checkConcept<ReadWriteMap, _ReferenceMap >();
     177      struct Constraints {
     178        void constraints() {
     179          checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
    182180          m[key] = val;
    183181          val  = m[key];
    … …  
    192190        typename _ReferenceMap::Key& own_key;
    193191        typename _ReferenceMap::Value& own_val;
    194         typename _ReferenceMap::Reference& own_ref;
     192        typename _ReferenceMap::Reference own_ref;
    195193        Key& key;
    196194        Value& val;
    197         Reference& ref;
     195        Reference ref;
    198196        _ReferenceMap& m;
    199197      };

  • lemon/list_graph.h

    r39 r73  
    1717 */
    1818
     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& arc) const {
     115      int n;
     116      for(n = first_node;
     117          n!=-1 && nodes[n].first_in == -1;
     118          n = nodes[n].next);
     119      arc.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 graphs
     297  /// @{
     298
     299  ///A general directed graph structure.
     300
     301  ///\ref ListDigraph is a simple and fast <em>directed graph</em>
     302  ///implementation based on static linked lists that are stored in
     303  ///\c std::vector structures.   
     304  ///
     305  ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
     306  ///also provides several useful additional functionalities.
     307  ///Most of the member functions and nested classes are documented
     308  ///only in the concept class.
     309  ///
     310  ///An important extra feature of this digraph implementation is that
     311  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
     312  ///
     313  ///\sa concepts::Digraph
     314
     315  class ListDigraph : public ExtendedListDigraphBase {
     316  private:
     317    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
     318   
     319    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
     320    ///
     321    ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
     322    ///\brief Assignment of ListDigraph to another one is \e not allowed.
     323    ///Use copyDigraph() instead.
     324
     325    ///Assignment of ListDigraph to another one is \e not allowed.
     326    ///Use copyDigraph() instead.
     327    void operator=(const ListDigraph &) {}
     328  public:
     329
     330    typedef ExtendedListDigraphBase Parent;
     331
     332    /// Constructor
     333   
     334    /// Constructor.
     335    ///
     336    ListDigraph() {}
     337
     338    ///Add a new node to the digraph.
     339   
     340    ///Add a new node to the digraph.
     341    ///\return the new node.
     342    Node addNode() { return Parent::addNode(); }
     343
     344    ///Add a new arc to the digraph.
     345   
     346    ///Add a new arc to the digraph with source node \c s
     347    ///and target node \c t.
     348    ///\return the new arc.
     349    Arc addArc(const Node& s, const Node& t) {
     350      return Parent::addArc(s, t);
     351    }
     352
     353    /// Change the target of \c e to \c n
     354
     355    /// Change the target of \c e to \c n
     356    ///
     357    ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
     358    ///the changed arc remain valid. However <tt>InArcIt</tt>s are
     359    ///invalidated.
     360    ///
     361    ///\warning This functionality cannot be used together with the Snapshot
     362    ///feature.
     363    void changeTarget(Arc e, Node n) {
     364      Parent::changeTarget(e,n);
     365    }
     366    /// Change the source of \c e to \c n
     367
     368    /// Change the source of \c e to \c n
     369    ///
     370    ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing
     371    ///the changed arc remain valid. However <tt>OutArcIt</tt>s are
     372    ///invalidated.
     373    ///
     374    ///\warning This functionality cannot be used together with the Snapshot
     375    ///feature.
     376    void changeSource(Arc e, Node n) {
     377      Parent::changeSource(e,n);
     378    }
     379
     380    /// Invert the direction of an arc.
     381
     382    ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
     383    ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
     384    ///invalidated.
     385    ///
     386    ///\warning This functionality cannot be used together with the Snapshot
     387    ///feature.
     388    void reverseArc(Arc e) {
     389      Node t=target(e);
     390      changeTarget(e,source(e));
     391      changeSource(e,t);
     392    }
     393
     394    /// Reserve memory for nodes.
     395
     396    /// Using this function it is possible to avoid the superfluous memory
     397    /// allocation: if you know that the digraph you want to build will
     398    /// be very large (e.g. it will contain millions of nodes and/or arcs)
     399    /// then it is worth reserving space for this amount before starting
     400    /// to build the digraph.
     401    /// \sa reserveArc
     402    void reserveNode(int n) { nodes.reserve(n); };
     403
     404    /// Reserve memory for arcs.
     405
     406    /// Using this function it is possible to avoid the superfluous memory
     407    /// allocation: if you know that the digraph you want to build will
     408    /// be very large (e.g. it will contain millions of nodes and/or arcs)
     409    /// then it is worth reserving space for this amount before starting
     410    /// to build the digraph.
     411    /// \sa reserveNode
     412    void reserveArc(int m) { arcs.reserve(m); };
     413
     414    ///Contract two nodes.
     415
     416    ///This function contracts two nodes.
     417    ///Node \p b will be removed but instead of deleting
     418    ///incident arcs, they will be joined to \p a.
     419    ///The last parameter \p r controls whether to remove loops. \c true
     420    ///means that loops will be removed.
     421    ///
     422    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
     423    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
     424    ///may be invalidated.
     425    ///
     426    ///\warning This functionality cannot be used together with the Snapshot
     427    ///feature.
     428    void contract(Node a, Node b, bool r = true)
     429    {
     430      for(OutArcIt e(*this,b);e!=INVALID;) {
     431        OutArcIt f=e;
     432        ++f;
     433        if(r && target(e)==a) erase(e);
     434        else changeSource(e,a);
     435        e=f;
     436      }
     437      for(InArcIt e(*this,b);e!=INVALID;) {
     438        InArcIt f=e;
     439        ++f;
     440        if(r && source(e)==a) erase(e);
     441        else changeTarget(e,a);
     442        e=f;
     443      }
     444      erase(b);
     445    }
     446
     447    ///Split a node.
     448
     449    ///This function splits a node. First a new node is added to the digraph,
     450    ///then the source of each outgoing arc of \c n is moved to this new node.
     451    ///If \c connect is \c true (this is the default value), then a new arc
     452    ///from \c n to the newly created node is also added.
     453    ///\return The newly created node.
     454    ///
     455    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
     456    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
     457    ///be invalidated. 
     458    ///
     459    ///\warning This functionality cannot be used together with the
     460    ///Snapshot feature.
     461    ///
     462    ///\todo It could be implemented in a bit faster way.
     463    Node split(Node n, bool connect = true) {
     464      Node b = addNode();
     465      for(OutArcIt e(*this,n);e!=INVALID;) {
     466        OutArcIt f=e;
     467        ++f;
     468        changeSource(e,b);
     469        e=f;
     470      }
     471      if (connect) addArc(n,b);
     472      return b;
     473    }
     474     
     475    ///Split an arc.
     476
     477    ///This function splits an arc. First a new node \c b is added to
     478    ///the digraph, then the original arc is re-targeted to \c
     479    ///b. Finally an arc from \c b to the original target is added.
     480    ///
     481    ///\return The newly created node.
     482    ///
     483    ///\warning This functionality cannot be used together with the
     484    ///Snapshot feature.
     485    Node split(Arc e) {
     486      Node b = addNode();
     487      addArc(b,target(e));
     488      changeTarget(e,b);
     489      return b;
     490    }
     491     
     492    /// \brief Class to make a snapshot of the digraph and restore
     493    /// it later.
     494    ///
     495    /// Class to make a snapshot of the digraph and restore it later.
     496    ///
     497    /// The newly added nodes and arcs can be removed using the
     498    /// restore() function.
     499    ///
     500    /// \warning Arc and node deletions and other modifications (e.g.
     501    /// contracting, splitting, reversing arcs or nodes) cannot be
     502    /// restored. These events invalidate the snapshot.
     503    class Snapshot {
     504    protected:
     505
     506      typedef Parent::NodeNotifier NodeNotifier;
     507
     508      class NodeObserverProxy : public NodeNotifier::ObserverBase {
     509      public:
     510
     511        NodeObserverProxy(Snapshot& _snapshot)
     512          : snapshot(_snapshot) {}
     513
     514        using NodeNotifier::ObserverBase::attach;
     515        using NodeNotifier::ObserverBase::detach;
     516        using NodeNotifier::ObserverBase::attached;
     517       
     518      protected:
     519       
     520        virtual void add(const Node& node) {
     521          snapshot.addNode(node);
     522        }
     523        virtual void add(const std::vector<Node>& nodes) {
     524          for (int i = nodes.size() - 1; i >= 0; ++i) {
     525            snapshot.addNode(nodes[i]);
     526          }
     527        }
     528        virtual void erase(const Node& node) {
     529          snapshot.eraseNode(node);
     530        }
     531        virtual void erase(const std::vector<Node>& nodes) {
     532          for (int i = 0; i < int(nodes.size()); ++i) {
     533            snapshot.eraseNode(nodes[i]);
     534          }
     535        }
     536        virtual void build() {
     537          Node node;
     538          std::vector<Node> nodes;
     539          for (notifier()->first(node); node != INVALID;
     540               notifier()->next(node)) {
     541            nodes.push_back(node);
     542          }
     543          for (int i = nodes.size() - 1; i >= 0; --i) {
     544            snapshot.addNode(nodes[i]);
     545          }
     546        }
     547        virtual void clear() {
     548          Node node;
     549          for (notifier()->first(node); node != INVALID;
     550               notifier()->next(node)) {
     551            snapshot.eraseNode(node);
     552          }
     553        }
     554
     555        Snapshot& snapshot;
     556      };
     557
     558      class ArcObserverProxy : public ArcNotifier::ObserverBase {
     559      public:
     560
     561        ArcObserverProxy(Snapshot& _snapshot)
     562          : snapshot(_snapshot) {}
     563
     564        using ArcNotifier::ObserverBase::attach;
     565        using ArcNotifier::ObserverBase::detach;
     566        using ArcNotifier::ObserverBase::attached;
     567       
     568      protected:
     569
     570        virtual void add(const Arc& arc) {
     571          snapshot.addArc(arc);
     572        }
     573        virtual void add(const std::vector<Arc>& arcs) {
     574          for (int i = arcs.size() - 1; i >= 0; ++i) {
     575            snapshot.addArc(arcs[i]);
     576          }
     577        }
     578        virtual void erase(const Arc& arc) {
     579          snapshot.eraseArc(arc);
     580        }
     581        virtual void erase(const std::vector<Arc>& arcs) {
     582          for (int i = 0; i < int(arcs.size()); ++i) {
     583            snapshot.eraseArc(arcs[i]);
     584          }
     585        }
     586        virtual void build() {
     587          Arc arc;
     588          std::vector<Arc> arcs;
     589          for (notifier()->first(arc); arc != INVALID;
     590               notifier()->next(arc)) {
     591            arcs.push_back(arc);
     592          }
     593          for (int i = arcs.size() - 1; i >= 0; --i) {
     594            snapshot.addArc(arcs[i]);
     595          }
     596        }
     597        virtual void clear() {
     598          Arc arc;
     599          for (notifier()->first(arc); arc != INVALID;
     600               notifier()->next(arc)) {
     601            snapshot.eraseArc(arc);
     602          }
     603        }
     604
     605        Snapshot& snapshot;
     606      };
     607     
     608      ListDigraph *digraph;
     609
     610      NodeObserverProxy node_observer_proxy;
     611      ArcObserverProxy arc_observer_proxy;
     612
     613      std::list<Node> added_nodes;
     614      std::list<Arc> added_arcs;
     615
     616
     617      void addNode(const Node& node) {
     618        added_nodes.push_front(node);       
     619      }
     620      void eraseNode(const Node& node) {
     621        std::list<Node>::iterator it =
     622          std::find(added_nodes.begin(), added_nodes.end(), node);
     623        if (it == added_nodes.end()) {
     624          clear();
     625          arc_observer_proxy.detach();
     626          throw NodeNotifier::ImmediateDetach();
     627        } else {
     628          added_nodes.erase(it);
     629        }
     630      }
     631
     632      void addArc(const Arc& arc) {
     633        added_arcs.push_front(arc);       
     634      }
     635      void eraseArc(const Arc& arc) {
     636        std::list<Arc>::iterator it =
     637          std::find(added_arcs.begin(), added_arcs.end(), arc);
     638        if (it == added_arcs.end()) {
     639          clear();
     640          node_observer_proxy.detach();
     641          throw ArcNotifier::ImmediateDetach();
     642        } else {
     643          added_arcs.erase(it);
     644        }       
     645      }
     646
     647      void attach(ListDigraph &_digraph) {
     648        digraph = &_digraph;
     649        node_observer_proxy.attach(digraph->notifier(Node()));
     650        arc_observer_proxy.attach(digraph->notifier(Arc()));
     651      }
     652           
     653      void detach() {
     654        node_observer_proxy.detach();
     655        arc_observer_proxy.detach();
     656      }
     657
     658      bool attached() const {
     659        return node_observer_proxy.attached();
     660      }
     661
     662      void clear() {
     663        added_nodes.clear();
     664        added_arcs.clear();       
     665      }
     666
     667    public:
     668
     669      /// \brief Default constructor.
     670      ///
     671      /// Default constructor.
     672      /// To actually make a snapshot you must call save().
     673      Snapshot()
     674        : digraph(0), node_observer_proxy(*this),
     675          arc_observer_proxy(*this) {}
     676     
     677      /// \brief Constructor that immediately makes a snapshot.
     678      ///     
     679      /// This constructor immediately makes a snapshot of the digraph.
     680      /// \param _digraph The digraph we make a snapshot of.
     681      Snapshot(ListDigraph &_digraph)
     682        : node_observer_proxy(*this),
     683          arc_observer_proxy(*this) {
     684        attach(_digraph);
     685      }
     686     
     687      /// \brief Make a snapshot.
     688      ///
     689      /// Make a snapshot of the digraph.
     690      ///
     691      /// This function can be called more than once. In case of a repeated
     692      /// call, the previous snapshot gets lost.
     693      /// \param _digraph The digraph we make the snapshot of.
     694      void save(ListDigraph &_digraph) {
     695        if (attached()) {
     696          detach();
     697          clear();
     698        }
     699        attach(_digraph);
     700      }
     701     
     702      /// \brief Undo the changes until the last snapshot.
     703      //
     704      /// Undo the changes until the last snapshot created by save().
     705      void restore() {
     706        detach();
     707        for(std::list<Arc>::iterator it = added_arcs.begin();
     708            it != added_arcs.end(); ++it) {
     709          digraph->erase(*it);
     710        }
     711        for(std::list<Node>::iterator it = added_nodes.begin();
     712            it != added_nodes.end(); ++it) {
     713          digraph->erase(*it);
     714        }
     715        clear();
     716      }
     717
     718      /// \brief Gives back true when the snapshot is valid.
     719      ///
     720      /// Gives back true when the snapshot is valid.
     721      bool valid() const {
     722        return attached();
     723      }
     724    };
     725   
     726  };
     727
     728  ///@}
     729
     730  class ListGraphBase {
     731
     732  protected:
     733
     734    struct NodeT {
     735      int first_out;
     736      int prev, next;
     737    };
     738 
     739    struct ArcT {
     740      int target;
     741      int prev_out, next_out;
     742    };
     743
     744    std::vector<NodeT> nodes;
     745
     746    int first_node;
     747
     748    int first_free_node;
     749
     750    std::vector<ArcT> arcs;
     751
     752    int first_free_arc;
     753   
     754  public:
     755   
     756    typedef ListGraphBase Digraph;
     757
     758    class Node;
     759    class Arc;
     760    class Edge;
     761   
     762    class Node {
     763      friend class ListGraphBase;
     764    protected:
     765
     766      int id;
     767      explicit Node(int pid) { id = pid;}
     768
     769    public:
     770      Node() {}
     771      Node (Invalid) { id = -1; }
     772      bool operator==(const Node& node) const {return id == node.id;}
     773      bool operator!=(const Node& node) const {return id != node.id;}
     774      bool operator<(const Node& node) const {return id < node.id;}
     775    };
     776
     777    class Edge {
     778      friend class ListGraphBase;
     779    protected:
     780
     781      int id;
     782      explicit Edge(int pid) { id = pid;}
     783
     784    public:
     785      Edge() {}
     786      Edge (Invalid) { id = -1; }
     787      bool operator==(const Edge& edge) const {return id == edge.id;}
     788      bool operator!=(const Edge& edge) const {return id != edge.id;}
     789      bool operator<(const Edge& edge) const {return id < edge.id;}
     790    };
     791
     792    class Arc {
     793      friend class ListGraphBase;
     794    protected:
     795
     796      int id;
     797      explicit Arc(int pid) { id = pid;}
     798
     799    public:
     800      operator Edge() const { return edgeFromId(id / 2); }
     801
     802      Arc() {}
     803      Arc (Invalid) { id = -1; }
     804      bool operator==(const Arc& arc) const {return id == arc.id;}
     805      bool operator!=(const Arc& arc) const {return id != arc.id;}
     806      bool operator<(const Arc& arc) const {return id < arc.id;}
     807    };
     808
     809
     810
     811    ListGraphBase()
     812      : nodes(), first_node(-1),
     813        first_free_node(-1), arcs(), first_free_arc(-1) {}
     814
     815   
     816    int maxNodeId() const { return nodes.size()-1; }
     817    int maxEdgeId() const { return arcs.size() / 2 - 1; }
     818    int maxArcId() const { return arcs.size()-1; }
     819
     820    Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
     821    Node target(Arc e) const { return Node(arcs[e.id].target); }
     822
     823    Node u(Edge e) const { return Node(arcs[2 * e.id].target); }
     824    Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
     825
     826    static bool direction(Arc e) {
     827      return (e.id & 1) == 1;
     828    }
     829
     830    static Arc direct(Edge e, bool d) {
     831      return Arc(e.id * 2 + (d ? 1 : 0));
     832    }
     833
     834    void first(Node& node) const {
     835      node.id = first_node;
     836    }
     837
     838    void next(Node& node) const {
     839      node.id = nodes[node.id].next;
     840    }
     841
     842    void first(Arc& e) const {
     843      int n = first_node;
     844      while (n != -1 && nodes[n].first_out == -1) {
     845        n = nodes[n].next;
     846      }
     847      e.id = (n == -1) ? -1 : nodes[n].first_out;
     848    }
     849
     850    void next(Arc& e) const {
     851      if (arcs[e.id].next_out != -1) {
     852        e.id = arcs[e.id].next_out;
     853      } else {
     854        int n = nodes[arcs[e.id ^ 1].target].next;
     855        while(n != -1 && nodes[n].first_out == -1) {
     856          n = nodes[n].next;
     857        }
     858        e.id = (n == -1) ? -1 : nodes[n].first_out;
     859      }     
     860    }
     861
     862    void first(Edge& e) const {
     863      int n = first_node;
     864      while (n != -1) {
     865        e.id = nodes[n].first_out;
     866        while ((e.id & 1) != 1) {
     867          e.id = arcs[e.id].next_out;
     868        }
     869        if (e.id != -1) {
     870          e.id /= 2;
     871          return;
     872        }
     873        n = nodes[n].next;
     874      }
     875      e.id = -1;
     876    }
     877
     878    void next(Edge& e) const {
     879      int n = arcs[e.id * 2].target;
     880      e.id = arcs[(e.id * 2) | 1].next_out;
     881      while ((e.id & 1) != 1) {
     882        e.id = arcs[e.id].next_out;
     883      }
     884      if (e.id != -1) {
     885        e.id /= 2;
     886        return;
     887      }
     888      n = nodes[n].next;
     889      while (n != -1) {
     890        e.id = nodes[n].first_out;
     891        while ((e.id & 1) != 1) {
     892          e.id = arcs[e.id].next_out;
     893        }
     894        if (e.id != -1) {
     895          e.id /= 2;
     896          return;
     897        }
     898        n = nodes[n].next;
     899      }
     900      e.id = -1;
     901    }
     902
     903    void firstOut(Arc &e, const Node& v) const {
     904      e.id = nodes[v.id].first_out;
     905    }
     906    void nextOut(Arc &e) const {
     907      e.id = arcs[e.id].next_out;
     908    }
     909
     910    void firstIn(Arc &e, const Node& v) const {
     911      e.id = ((nodes[v.id].first_out) ^ 1);
     912      if (e.id == -2) e.id = -1;
     913    }
     914    void nextIn(Arc &e) const {
     915      e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
     916      if (e.id == -2) e.id = -1;
     917    }
     918
     919    void firstInc(Edge &e, bool& d, const Node& v) const {
     920      int a = nodes[v.id].first_out;
     921      if (a != -1 ) {
     922        e.id = a / 2;
     923        d = ((a & 1) == 1);
     924      } else {
     925        e.id = -1;
     926        d = true;
     927      }
     928    }
     929    void nextInc(Edge &e, bool& d) const {
     930      int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
     931      if (a != -1 ) {
     932        e.id = a / 2;
     933        d = ((a & 1) == 1);
     934      } else {
     935        e.id = -1;
     936        d = true;
     937      }
     938    }
     939   
     940    static int id(Node v) { return v.id; }
     941    static int id(Arc e) { return e.id; }
     942    static int id(Edge e) { return e.id; }
     943
     944    static Node nodeFromId(int id) { return Node(id);}
     945    static Arc arcFromId(int id) { return Arc(id);}
     946    static Edge edgeFromId(int id) { return Edge(id);}
     947
     948    Node addNode() {     
     949      int n;
     950     
     951      if(first_free_node==-1) {
     952        n = nodes.size();
     953        nodes.push_back(NodeT());
     954      } else {
     955        n = first_free_node;
     956        first_free_node = nodes[n].next;
     957      }
     958     
     959      nodes[n].next = first_node;
     960      if (first_node != -1) nodes[first_node].prev = n;
     961      first_node = n;
     962      nodes[n].prev = -1;
     963     
     964      nodes[n].first_out = -1;
     965     
     966      return Node(n);
     967    }
     968   
     969    Edge addEdge(Node u, Node v) {
     970      int n;     
     971
     972      if (first_free_arc == -1) {
     973        n = arcs.size();
     974        arcs.push_back(ArcT());
     975        arcs.push_back(ArcT());
     976      } else {
     977        n = first_free_arc;
     978        first_free_arc = arcs[n].next_out;
     979      }
     980     
     981      arcs[n].target = u.id;
     982      arcs[n | 1].target = v.id;
     983
     984      arcs[n].next_out = nodes[v.id].first_out;
     985      if (nodes[v.id].first_out != -1) {
     986        arcs[nodes[v.id].first_out].prev_out = n;
     987      }     
     988      arcs[n].prev_out = -1;
     989      nodes[v.id].first_out = n;
     990     
     991      arcs[n | 1].next_out = nodes[u.id].first_out;
     992      if (nodes[u.id].first_out != -1) {
     993        arcs[nodes[u.id].first_out].prev_out = (n | 1);
     994      }
     995      arcs[n | 1].prev_out = -1;     
     996      nodes[u.id].first_out = (n | 1);
     997
     998      return Edge(n / 2);
     999    }
     1000   
     1001    void erase(const Node& node) {
     1002      int n = node.id;
     1003     
     1004      if(nodes[n].next != -1) {
     1005        nodes[nodes[n].next].prev = nodes[n].prev;
     1006      }
     1007     
     1008      if(nodes[n].prev != -1) {
     1009        nodes[nodes[n].prev].next = nodes[n].next;
     1010      } else {
     1011        first_node = nodes[n].next;
     1012      }
     1013     
     1014      nodes[n].next = first_free_node;
     1015      first_free_node = n;
     1016
     1017    }
     1018   
     1019    void erase(const Edge& edge) {
     1020      int n = edge.id * 2;
     1021     
     1022      if (arcs[n].next_out != -1) {
     1023        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
     1024      }
     1025
     1026      if (arcs[n].prev_out != -1) {
     1027        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
     1028      } else {
     1029        nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
     1030      }
     1031
     1032      if (arcs[n | 1].next_out != -1) {
     1033        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
     1034      }
     1035
     1036      if (arcs[n | 1].prev_out != -1) {
     1037        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
     1038      } else {
     1039        nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
     1040      }
     1041     
     1042      arcs[n].next_out = first_free_arc;
     1043      first_free_arc = n;     
     1044
     1045    }
     1046
     1047    void clear() {
     1048      arcs.clear();
     1049      nodes.clear();
     1050      first_node = first_free_node = first_free_arc = -1;
     1051    }
     1052
     1053  protected:
     1054
     1055    void changeTarget(Edge e, Node n) {
     1056      if(arcs[2 * e.id].next_out != -1) {
     1057        arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
     1058      }
     1059      if(arcs[2 * e.id].prev_out != -1) {
     1060        arcs[arcs[2 * e.id].prev_out].next_out =
     1061          arcs[2 * e.id].next_out;
     1062      } else {
     1063        nodes[arcs[(2 * e.id) | 1].target].first_out =
     1064          arcs[2 * e.id].next_out;
     1065      }
     1066
     1067      if (nodes[n.id].first_out != -1) {
     1068        arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
     1069      }
     1070      arcs[(2 * e.id) | 1].target = n.id;
     1071      arcs[2 * e.id].prev_out = -1;
     1072      arcs[2 * e.id].next_out = nodes[n.id].first_out;
     1073      nodes[n.id].first_out = 2 * e.id;
     1074    }
     1075
     1076    void changeSource(Edge e, Node n) {
     1077      if(arcs[(2 * e.id) | 1].next_out != -1) {
     1078        arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
     1079          arcs[(2 * e.id) | 1].prev_out;
     1080      }
     1081      if(arcs[(2 * e.id) | 1].prev_out != -1) {
     1082        arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
     1083          arcs[(2 * e.id) | 1].next_out;
     1084      } else {
     1085        nodes[arcs[2 * e.id].target].first_out =
     1086          arcs[(2 * e.id) | 1].next_out;
     1087      }
     1088
     1089      if (nodes[n.id].first_out != -1) {
     1090        arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
     1091      }
     1092      arcs[2 * e.id].target = n.id;
     1093      arcs[(2 * e.id) | 1].prev_out = -1;
     1094      arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
     1095      nodes[n.id].first_out = ((2 * e.id) | 1);
     1096    }
     1097
     1098  };
     1099
     1100  typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
     1101
     1102
     1103  /// \addtogroup graphs
     1104  /// @{
     1105
     1106  ///A general undirected graph structure.
     1107
     1108  ///\ref ListGraph is a simple and fast <em>undirected graph</em>
     1109  ///implementation based on static linked lists that are stored in
     1110  ///\c std::vector structures.
     1111  ///
     1112  ///It conforms to the \ref concepts::Graph "Graph concept" and it
     1113  ///also provides several useful additional functionalities.
     1114  ///Most of the member functions and nested classes are documented
     1115  ///only in the concept class.
     1116  ///
     1117  ///An important extra feature of this graph implementation is that
     1118  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
     1119  ///
     1120  ///\sa concepts::Graph
     1121
     1122  class ListGraph : public ExtendedListGraphBase {
     1123  private:
     1124    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
     1125
     1126    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
     1127    ///
     1128    ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
     1129    ///\brief Assignment of ListGraph to another one is \e not allowed.
     1130    ///Use copyGraph() instead.
     1131
     1132    ///Assignment of ListGraph to another one is \e not allowed.
     1133    ///Use copyGraph() instead.
     1134    void operator=(const ListGraph &) {}
     1135  public:
     1136    /// Constructor
     1137   
     1138    /// Constructor.
     1139    ///
     1140    ListGraph() {}
     1141
     1142    typedef ExtendedListGraphBase Parent;
     1143
     1144    typedef Parent::OutArcIt IncEdgeIt;
     1145
     1146    /// \brief Add a new node to the graph.
     1147    ///
     1148    /// Add a new node to the graph.
     1149    /// \return the new node.
     1150    Node addNode() { return Parent::addNode(); }
     1151
     1152    /// \brief Add a new edge to the graph.
     1153    ///
     1154    /// Add a new edge to the graph with source node \c s
     1155    /// and target node \c t.
     1156    /// \return the new edge.
     1157    Edge addEdge(const Node& s, const Node& t) {
     1158      return Parent::addEdge(s, t);
     1159    }
     1160    /// \brief Change the source of \c e to \c n
     1161    ///
     1162    /// This function changes the source of \c e to \c n.
     1163    ///
     1164    ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
     1165    ///referencing the changed arc remain
     1166    ///valid. However <tt>OutArcIt</tt>s are invalidated.
     1167    ///
     1168    ///\warning This functionality cannot be used together with the
     1169    ///Snapshot feature.
     1170    void changeSource(Edge e, Node n) {
     1171      Parent::changeSource(e,n);
     1172    }   
     1173    /// \brief Change the target of \c e to \c n
     1174    ///
     1175    /// This function changes the target of \c e to \c n.
     1176    ///
     1177    /// \note The <tt>ArcIt</tt>s referencing the changed arc remain
     1178    /// valid. However the other iterators may be invalidated.
     1179    ///
     1180    ///\warning This functionality cannot be used together with the
     1181    ///Snapshot feature.
     1182    void changeTarget(Edge e, Node n) {
     1183      Parent::changeTarget(e,n);
     1184    }
     1185    /// \brief Change the source of \c e to \c n
     1186    ///
     1187    /// This function changes the source of \c e to \c n.
     1188    /// It also changes the proper node of the represented edge.
     1189    ///
     1190    ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
     1191    ///referencing the changed arc remain
     1192    ///valid. However <tt>OutArcIt</tt>s are invalidated.
     1193    ///
     1194    ///\warning This functionality cannot be used together with the
     1195    ///Snapshot feature.
     1196    void changeSource(Arc e, Node n) {
     1197      if (Parent::direction(e)) {
     1198        Parent::changeSource(e,n);
     1199      } else {
     1200        Parent::changeTarget(e,n);
     1201      }
     1202    }
     1203    /// \brief Change the target of \c e to \c n
     1204    ///
     1205    /// This function changes the target of \c e to \c n.
     1206    /// It also changes the proper node of the represented edge.
     1207    ///
     1208    ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s
     1209    ///referencing the changed arc remain
     1210    ///valid. However <tt>InArcIt</tt>s are invalidated.
     1211    ///
     1212    ///\warning This functionality cannot be used together with the
     1213    ///Snapshot feature.
     1214    void changeTarget(Arc e, Node n) {
     1215      if (Parent::direction(e)) {
     1216        Parent::changeTarget(e,n);
     1217      } else {
     1218        Parent::changeSource(e,n);
     1219      }
     1220    }
     1221    /// \brief Contract two nodes.
     1222    ///
     1223    /// This function contracts two nodes.
     1224    /// Node \p b will be removed but instead of deleting
     1225    /// its neighboring arcs, they will be joined to \p a.
     1226    /// The last parameter \p r controls whether to remove loops. \c true
     1227    /// means that loops will be removed.
     1228    ///
     1229    /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
     1230    /// valid.
     1231    ///
     1232    ///\warning This functionality cannot be used together with the
     1233    ///Snapshot feature.
     1234    void contract(Node a, Node b, bool r = true) {
     1235      for(IncEdgeIt e(*this, b); e!=INVALID;) {
     1236        IncEdgeIt f = e; ++f;
     1237        if (r && runningNode(e) == a) {
     1238          erase(e);
     1239        } else if (source(e) == b) {
     1240          changeSource(e, a);
     1241        } else {
     1242          changeTarget(e, a);
     1243        }
     1244        e = f;
     1245      }
     1246      erase(b);
     1247    }
     1248
     1249
     1250    /// \brief Class to make a snapshot of the graph and restore
     1251    /// it later.
     1252    ///
     1253    /// Class to make a snapshot of the graph and restore it later.
     1254    ///
     1255    /// The newly added nodes and edges can be removed
     1256    /// using the restore() function.
     1257    ///
     1258    /// \warning Edge and node deletions and other modifications
     1259    /// (e.g. changing nodes of edges, contracting nodes) cannot be
     1260    /// restored. These events invalidate the snapshot.
     1261    class Snapshot {
     1262    protected:
     1263
     1264      typedef Parent::NodeNotifier NodeNotifier;
     1265
     1266      class NodeObserverProxy : public NodeNotifier::ObserverBase {
     1267      public:
     1268
     1269        NodeObserverProxy(Snapshot& _snapshot)
     1270          : snapshot(_snapshot) {}
     1271
     1272        using NodeNotifier::ObserverBase::attach;
     1273        using NodeNotifier::ObserverBase::detach;
     1274        using NodeNotifier::ObserverBase::attached;
     1275       
     1276      protected:
     1277       
     1278        virtual void add(const Node& node) {
     1279          snapshot.addNode(node);
     1280        }
     1281        virtual void add(const std::vector<Node>& nodes) {
     1282          for (int i = nodes.size() - 1; i >= 0; ++i) {
     1283            snapshot.addNode(nodes[i]);
     1284          }
     1285        }
     1286        virtual void erase(const Node& node) {
     1287          snapshot.eraseNode(node);
     1288        }
     1289        virtual void erase(const std::vector<Node>& nodes) {
     1290          for (int i = 0; i < int(nodes.size()); ++i) {
     1291            snapshot.eraseNode(nodes[i]);
     1292          }
     1293        }
     1294        virtual void build() {
     1295          Node node;
     1296          std::vector<Node> nodes;
     1297          for (notifier()->first(node); node != INVALID;
     1298               notifier()->next(node)) {
     1299            nodes.push_back(node);
     1300          }
     1301          for (int i = nodes.size() - 1; i >= 0; --i) {
     1302            snapshot.addNode(nodes[i]);
     1303          }
     1304        }
     1305        virtual void clear() {
     1306          Node node;
     1307          for (notifier()->first(node); node != INVALID;
     1308               notifier()->next(node)) {
     1309            snapshot.eraseNode(node);
     1310          }
     1311        }
     1312
     1313        Snapshot& snapshot;
     1314      };
     1315
     1316      class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
     1317      public:
     1318
     1319        EdgeObserverProxy(Snapshot& _snapshot)
     1320          : snapshot(_snapshot) {}
     1321
     1322        using EdgeNotifier::ObserverBase::attach;
     1323        using EdgeNotifier::ObserverBase::detach;
     1324        using EdgeNotifier::ObserverBase::attached;
     1325       
     1326      protected:
     1327
     1328        virtual void add(const Edge& edge) {
     1329          snapshot.addEdge(edge);
     1330        }
     1331        virtual void add(const std::vector<Edge>& edges) {
     1332          for (int i = edges.size() - 1; i >= 0; ++i) {
     1333            snapshot.addEdge(edges[i]);
     1334          }
     1335        }
     1336        virtual void erase(const Edge& edge) {
     1337          snapshot.eraseEdge(edge);
     1338        }
     1339        virtual void erase(const std::vector<Edge>& edges) {
     1340          for (int i = 0; i < int(edges.size()); ++i) {
     1341            snapshot.eraseEdge(edges[i]);
     1342          }
     1343        }
     1344        virtual void build() {
     1345          Edge edge;
     1346          std::vector<Edge> edges;
     1347          for (notifier()->first(edge); edge != INVALID;
     1348               notifier()->next(edge)) {
     1349            edges.push_back(edge);
     1350          }
     1351          for (int i = edges.size() - 1; i >= 0; --i) {
     1352            snapshot.addEdge(edges[i]);
     1353          }
     1354        }
     1355        virtual void clear() {
     1356          Edge edge;
     1357          for (notifier()->first(edge); edge != INVALID;
     1358               notifier()->next(edge)) {
     1359            snapshot.eraseEdge(edge);
     1360          }
     1361        }
     1362
     1363        Snapshot& snapshot;
     1364      };
     1365
     1366      ListGraph *graph;
     1367
     1368      NodeObserverProxy node_observer_proxy;
     1369      EdgeObserverProxy edge_observer_proxy;
     1370
     1371      std::list<Node> added_nodes;
     1372      std::list<Edge> added_edges;
     1373
     1374
     1375      void addNode(const Node& node) {
     1376        added_nodes.push_front(node);       
     1377      }
     1378      void eraseNode(const Node& node) {
     1379        std::list<Node>::iterator it =
     1380          std::find(added_nodes.begin(), added_nodes.end(), node);
     1381        if (it == added_nodes.end()) {
     1382          clear();
     1383          edge_observer_proxy.detach();
     1384          throw NodeNotifier::ImmediateDetach();
     1385        } else {
     1386          added_nodes.erase(it);
     1387        }
     1388      }
     1389
     1390      void addEdge(const Edge& edge) {
     1391        added_edges.push_front(edge);       
     1392      }
     1393      void eraseEdge(const Edge& edge) {
     1394        std::list<Edge>::iterator it =
     1395          std::find(added_edges.begin(), added_edges.end(), edge);
     1396        if (it == added_edges.end()) {
     1397          clear();
     1398          node_observer_proxy.detach();
     1399          throw EdgeNotifier::ImmediateDetach();
     1400        } else {
     1401          added_edges.erase(it);
     1402        }
     1403      }
     1404
     1405      void attach(ListGraph &_graph) {
     1406        graph = &_graph;
     1407        node_observer_proxy.attach(graph->notifier(Node()));
     1408        edge_observer_proxy.attach(graph->notifier(Edge()));
     1409      }
     1410           
     1411      void detach() {
     1412        node_observer_proxy.detach();
     1413        edge_observer_proxy.detach();
     1414      }
     1415
     1416      bool attached() const {
     1417        return node_observer_proxy.attached();
     1418      }
     1419
     1420      void clear() {
     1421        added_nodes.clear();
     1422        added_edges.clear();       
     1423      }
     1424
     1425    public:
     1426
     1427      /// \brief Default constructor.
     1428      ///
     1429      /// Default constructor.
     1430      /// To actually make a snapshot you must call save().
     1431      Snapshot()
     1432        : graph(0), node_observer_proxy(*this),
     1433          edge_observer_proxy(*this) {}
     1434     
     1435      /// \brief Constructor that immediately makes a snapshot.
     1436      ///     
     1437      /// This constructor immediately makes a snapshot of the graph.
     1438      /// \param _graph The graph we make a snapshot of.
     1439      Snapshot(ListGraph &_graph)
     1440        : node_observer_proxy(*this),
     1441          edge_observer_proxy(*this) {
     1442        attach(_graph);
     1443      }
     1444     
     1445      /// \brief Make a snapshot.
     1446      ///
     1447      /// Make a snapshot of the graph.
     1448      ///
     1449      /// This function can be called more than once. In case of a repeated
     1450      /// call, the previous snapshot gets lost.
     1451      /// \param _graph The graph we make the snapshot of.
     1452      void save(ListGraph &_graph) {
     1453        if (attached()) {
     1454          detach();
     1455          clear();
     1456        }
     1457        attach(_graph);
     1458      }
     1459     
     1460      /// \brief Undo the changes until the last snapshot.
     1461      //
     1462      /// Undo the changes until the last snapshot created by save().
     1463      void restore() {
     1464        detach();
     1465        for(std::list<Edge>::iterator it = added_edges.begin();
     1466            it != added_edges.end(); ++it) {
     1467          graph->erase(*it);
     1468        }
     1469        for(std::list<Node>::iterator it = added_nodes.begin();
     1470            it != added_nodes.end(); ++it) {
     1471          graph->erase(*it);
     1472        }
     1473        clear();
     1474      }
     1475
     1476      /// \brief Gives back true when the snapshot is valid.
     1477      ///
     1478      /// Gives back true when the snapshot is valid.
     1479      bool valid() const {
     1480        return attached();
     1481      }
     1482    };
     1483  };
     1484 
     1485  /// @} 
     1486} //namespace lemon
     1487 
     1488
     1489#endif

  • lemon/random.h

    r49 r68  
    6868
    6969#include <ctime>
    70 #include <cmath>
    71 
     70
     71#include <lemon/math.h>
    7272#include <lemon/dim2.h>
     73
    7374///\ingroup misc
    7475///\file
    … …  
    255256          --curr;
    256257        }
    257         curr[0] = (((curr[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^
     258        state[0] = (((state[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^
    258259          curr[length - shift] ^ mask[curr[length - 1] & 1ul];
    259260
    … …  
    760761      double xi,nu;
    761762      const double delta = k-std::floor(k);
    762       const double v0=M_E/(M_E-delta);
     763      const double v0=E/(E-delta);
    763764      do {
    764765        double V0=1.0-real<double>();

  • test/Makefile.am

    r32 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 \
     13        test/maps_test \
    914        test/random_test \
    1015        test/test_tools_fail \
    … …  
    1419XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
    1520
     21test_digraph_test_SOURCES = test/digraph_test.cc
    1622test_dim_test_SOURCES = test/dim_test.cc
     23#test_error_test_SOURCES = test/error_test.cc
     24test_graph_test_SOURCES = test/graph_test.cc
     25test_maps_test_SOURCES = test/maps_test.cc
    1726test_random_test_SOURCES = test/random_test.cc
    1827test_test_tools_fail_SOURCES = test/test_tools_fail.cc
Note: See TracChangeset for help on using the changeset viewer.