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


Ignore:
Files:
18 deleted
8 edited

Legend:

Unmodified
Added
Removed

  • Makefile.am

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

  • configure.ac

    r64 r55  
    1414AC_CONFIG_AUX_DIR([build-aux])
    1515AC_CONFIG_MACRO_DIR([m4])
    16 AM_INIT_AUTOMAKE([-Wall -Werror foreign subdir-objects nostdinc])
     16AM_INIT_AUTOMAKE([-Wall -Werror foreign subdir-objects])
    1717AC_CONFIG_SRCDIR([lemon/list_graph.h])
    1818AC_CONFIG_HEADERS([config.h lemon/config.h])
    … …  
    2727AC_PROG_LIBTOOL
    2828
    29 AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
    30 
    3129if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes; then
    3230  CXXFLAGS="$CXXFLAGS -Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
    3331fi
     32
     33AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
    3434
    3535dnl Checks for libraries.
    … …  
    3737LX_CHECK_CPLEX
    3838LX_CHECK_SOPLEX
     39
     40dnl Enable/disable installing the documentation
     41AC_ARG_ENABLE([doc],
     42AS_HELP_STRING([--enable-doc@<:@=yes|no|full@:>@], [build the documentation (full enables internal documentation too) @<:@default=yes@:>@])
     43AS_HELP_STRING([--disable-doc], [do not build the documentation]),
     44              [], [enable_doc=yes])
     45
     46AC_MSG_CHECKING([whether to build the documention])
     47case "$enable_doc" in
     48  yes)
     49    DOXYGEN_INTERNAL_DOCS=NO
     50    AC_MSG_RESULT([yes])
     51    ;;
     52  full)
     53    DOXYGEN_INTERNAL_DOCS=YES
     54    AC_MSG_RESULT([full])
     55    ;;
     56  no)
     57    DOXYGEN_INTERNAL_DOCS=NO
     58    AC_MSG_RESULT([no])
     59    ;;
     60  *)
     61    AC_MSG_ERROR([bad value $enable_doc for option --enable-doc])
     62    ;;
     63esac
     64AC_SUBST(DOXYGEN_INTERNAL_DOCS)
     65AM_CONDITIONAL([WANT_DOC], [test x"$enable_doc" != x"no"])
    3966
    4067dnl Disable/enable building the demo programs
    … …  
    119146echo $prefix.
    120147echo
     148echo The documentation will be installed in
     149echo -n '  '
     150eval echo ${datadir}/doc/$PACKAGE.
     151echo
    121152echo '*********************************************************************'
    122153

  • doc/Makefile.am

    r60 r2  
     1htmldir = $(datadir)/doc/$(PACKAGE)/html
     2
    13EXTRA_DIST += \
    24        doc/Makefile \
    3         doc/Doxyfile.in \
    4         doc/coding_style.dox \
    5         doc/dirs.dox \
    6         doc/groups.dox \
    7         doc/license.dox \
    8         doc/mainpage.dox \
    9         doc/namespaces.dox \
    10         doc/html
     5        doc/Doxyfile.in
    116
    12 doc/html:
    13         $(MAKE) $(AM_MAKEFLAGS) html
    14 
    15 html-local:
     7doc:
    168        if test ${doxygen_found} = yes; then \
    179          cd doc; \
    1810          doxygen Doxyfile; \
    1911          cd ..; \
    20         else \
    21           echo; \
    22           echo "Doxygen not found."; \
    23           echo; \
    24           exit 1; \
     12        fi
     13
     14doc-clean:
     15        if test ${doxygen_found} = yes; then \
     16          rm -rf doc/html; \
     17          rm -f doc/doxygen.log; \
     18          cd doc; \
     19          doxygen Doxyfile; \
     20          cd ..; \
    2521        fi
    2622
    … …  
    2925        -rm -f doc/doxygen.log
    3026
    31 update-external-tags:
    32         wget -O doc/libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag && \
    33         mv doc/libstdc++.tag.tmp doc/libstdc++.tag || \
    34         rm doc/libstdc++.tag.tmp
     27doc/html:
     28        $(MAKE) $(AM_MAKEFLAGS) doc-clean
    3529
    36 install-html-local: doc/html
     30if WANT_DOC
     31
     32install-data-local: doc/html
    3733        @$(NORMAL_INSTALL)
    38         $(mkinstalldirs) $(DESTDIR)$(htmldir)/docs
    39         for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
     34        $(mkinstalldirs) $(DESTDIR)$(htmldir)
     35        @dir='doc/html'; shopt -s nullglob; for p in $$dir/*.html $$dir/*.css $$dir/*.png $$dir/*.gif $$dir/*.dot $$dir/*.php $$dir/*.idx $$dir/*.tag ; do \
    4036          f="`echo $$p | sed -e 's|^.*/||'`"; \
    41           echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f"; \
    42           $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f; \
     37          echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/$$f"; \
     38          $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/$$f; \
    4339        done
    4440
    45 uninstall-local:
     41uninstall-local: doc/html
    4642        @$(NORMAL_UNINSTALL)
    47         for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
     43        @dir='doc/html'; shopt -s nullglob; for p in $$dir/*.html $$dir/*.css $$dir/*.png $$dir/*.gif $$dir/*.dot $$dir/*.php $$dir/*.idx $$dir/*.tag ; do \
    4844          f="`echo $$p | sed -e 's|^.*/||'`"; \
    49           echo " rm -f $(DESTDIR)$(htmldir)/docs/$$f"; \
    50           rm -f $(DESTDIR)$(htmldir)/docs/$$f; \
     45          echo " rm -f $(DESTDIR)$(htmldir)/$$f"; \
     46          rm -f $(DESTDIR)$(htmldir)/$$f; \
    5147        done
    5248
    53 .PHONY: update-external-tags
     49endif WANT_DOC
     50
     51.PHONY: doc doc-clean

  • lemon/Makefile.am

    r69 r32  
    1616
    1717lemon_HEADERS += \
    18         lemon/concept_check.h \
    1918        lemon/dim2.h \
    20         lemon/error.h \
     19        lemon/random.h \
    2120        lemon/list_graph.h \
    22         lemon/maps.h \
    23         lemon/math.h \
    24         lemon/random.h \
    2521        lemon/tolerance.h
    2622
    2723bits_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 \
    3324        lemon/bits/invalid.h \
    34         lemon/bits/map_extender.h \
    35         lemon/bits/traits.h \
    36         lemon/bits/utility.h \
    37         lemon/bits/vector_map.h
     25        lemon/bits/utility.h
    3826
    39 concept_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
     27concept_HEADERS +=

  • lemon/concepts/maps.h

    r74 r51  
    5656      template<typename _ReadMap>
    5757      struct Constraints {
     58
    5859        void constraints() {
    5960          Value val = m[key];
    … …  
    175176
    176177      template<typename _ReferenceMap>
    177       struct Constraints {
    178         void constraints() {
    179           checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
     178      struct ReferenceMapConcept {
     179
     180        void constraints() {
     181          checkConcept<ReadWriteMap, _ReferenceMap >();
    180182          m[key] = val;
    181183          val  = m[key];
    … …  
    190192        typename _ReferenceMap::Key& own_key;
    191193        typename _ReferenceMap::Value& own_val;
    192         typename _ReferenceMap::Reference own_ref;
     194        typename _ReferenceMap::Reference& own_ref;
    193195        Key& key;
    194196        Value& val;
    195         Reference ref;
     197        Reference& ref;
    196198        _ReferenceMap& m;
    197199      };

  • lemon/list_graph.h

    r73 r39  
    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 
    31 namespace lemon {
    32 
    33   class ListDigraphBase {
    34 
    35   protected:
    36     struct NodeT {
    37       int first_in, first_out;
    38       int prev, next;
    39     };
    40  
    41     struct ArcT {
    42       int target, source;
    43       int prev_in, prev_out;
    44       int next_in, next_out;
    45     };
    46 
    47     std::vector<NodeT> nodes;
    48 
    49     int first_node;
    50 
    51     int first_free_node;
    52 
    53     std::vector<ArcT> arcs;
    54 
    55     int first_free_arc;
    56    
    57   public:
    58    
    59     typedef ListDigraphBase Digraph;
    60    
    61     class Node {
    62       friend class ListDigraphBase;
    63     protected:
    64 
    65       int id;
    66       explicit Node(int pid) { id = pid;}
    67 
    68     public:
    69       Node() {}
    70       Node (Invalid) { id = -1; }
    71       bool operator==(const Node& node) const {return id == node.id;}
    72       bool operator!=(const Node& node) const {return id != node.id;}
    73       bool operator<(const Node& node) const {return id < node.id;}
    74     };
    75 
    76     class Arc {
    77       friend class ListDigraphBase;
    78     protected:
    79 
    80       int id;
    81       explicit Arc(int pid) { id = pid;}
    82 
    83     public:
    84       Arc() {}
    85       Arc (Invalid) { id = -1; }
    86       bool operator==(const Arc& arc) const {return id == arc.id;}
    87       bool operator!=(const Arc& arc) const {return id != arc.id;}
    88       bool operator<(const Arc& arc) const {return id < arc.id;}
    89     };
    90 
    91 
    92 
    93     ListDigraphBase()
    94       : nodes(), first_node(-1),
    95         first_free_node(-1), arcs(), first_free_arc(-1) {}
    96 
    97    
    98     int maxNodeId() const { return nodes.size()-1; }
    99     int maxArcId() const { return arcs.size()-1; }
    100 
    101     Node source(Arc e) const { return Node(arcs[e.id].source); }
    102     Node target(Arc e) const { return Node(arcs[e.id].target); }
    103 
    104 
    105     void first(Node& node) const {
    106       node.id = first_node;
    107     }
    108 
    109     void next(Node& node) const {
    110       node.id = nodes[node.id].next;
    111     }
    112 
    113 
    114     void first(Arc& 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

    r68 r49  
    6868
    6969#include <ctime>
    70 
    71 #include <lemon/math.h>
     70#include <cmath>
     71
    7272#include <lemon/dim2.h>
    73 
    7473///\ingroup misc
    7574///\file
    … …  
    256255          --curr;
    257256        }
    258         state[0] = (((state[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^
     257        curr[0] = (((curr[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^
    259258          curr[length - shift] ^ mask[curr[length - 1] & 1ul];
    260259
    … …  
    761760      double xi,nu;
    762761      const double delta = k-std::floor(k);
    763       const double v0=E/(E-delta);
     762      const double v0=M_E/(M_E-delta);
    764763      do {
    765764        double V0=1.0-real<double>();

  • test/Makefile.am

    r67 r32  
    33
    44noinst_HEADERS += \
    5         test/digraph_test.h \
    6         test/map_test.h \
    75        test/test_tools.h
    86
    97check_PROGRAMS += \
    10         test/digraph_test \
    118        test/dim_test \
    12         test/graph_test \
    13         test/maps_test \
    149        test/random_test \
    1510        test/test_tools_fail \
    … …  
    1914XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
    2015
    21 test_digraph_test_SOURCES = test/digraph_test.cc
    2216test_dim_test_SOURCES = test/dim_test.cc
    23 #test_error_test_SOURCES = test/error_test.cc
    24 test_graph_test_SOURCES = test/graph_test.cc
    25 test_maps_test_SOURCES = test/maps_test.cc
    2617test_random_test_SOURCES = test/random_test.cc
    2718test_test_tools_fail_SOURCES = test/test_tools_fail.cc
Note: See TracChangeset for help on using the changeset viewer.